Architecture Study: Ceph — RADOS, CRUSH Map & BlueStore NVMe Engine

1. Problem & Architecture Scope

Project Identity, Version & License Baseline

Scaling distributed storage to hundreds of petabytes and exabytes presents fundamental distributed systems dilemmas:

1. The Metadata Scalability Bottleneck:
   • Traditional distributed storage systems (such as early Google File System or Apache HDFS) maintain a centralized master server (the NameNode) holding the physical block location of every chunk in RAM.
   • When storing billions of small objects (such as photos, medical scans, or database commit logs), the metadata server exhausts physical memory, saturates its network interfaces, and creates an existential single point of failure (SPOF).
2. The Double-Write Penalty on Modern NVMe Storage:
   • Early storage software ran on top of standard Linux filesystems (Ext4, XFS, Btrfs).
   • Because standard POSIX filesystems do not support atomic multi-block transactions, storage daemons were forced to write data twice: once to a write-ahead journal file, and once to the target file system block. This double-write penalty halved raw NVMe hardware throughput and doubled SSD write amplification.
3. Hardware Heterogeneity & Topology Fault Domains:
   • Enterprise clusters mix high-density mechanical spinning disks (HDDs) for archival data with ultra-low-latency NVMe SSDs for transactional block devices.
   • Replicas must be placed across independent failure domains (different power rails, top-of-rack network switches, server rooms, and geographic availability zones) to guarantee surviveability under facility failures.

Ceph is the open-source, massively distributed storage system engineered to solve these challenges at exabyte scale.

This architecture study deconstructs:

• RADOS (Reliable Autonomic Distributed Object Store): The underlying self-healing object fabric.
• The CRUSH Algorithm: Algorithmic, rule-based pseudo-random data placement completely eliminating centralized metadata lookups.
• Ceph Monitors (MONs) & OSD Peering: Paxos-coordinated cluster maps and peer-to-peer failure detection.
• BlueStore Storage Engine: Raw block NVMe device consumption without Linux filesystem or double-write overhead.

2. Mental Model & Architectural Abstraction

Ceph unifies three distinct client interfaces on top of a single unified storage substrate:

[ Object Gateway (RGW: S3 / Swift) ]  [ Block Device (RBD) ]  [ POSIX Filesystem (CephFS) ]
                              │                      │                     │
                              └──────────────────────┼─────────────────────┘
                                                     ▼
                             ┌──────────────────────────────────────────────┐
                             │  LIBRADOS: Native Client C++/Rust/Go Library │
                             │  - Embeds CRUSH placement calculation in RAM │
                             │  - Communicates directly with target OSDs    │
                             └──────────────────────┬───────────────────────┘
                                                    │ Algorithmic Mapping
                                                    ▼
                             ┌──────────────────────────────────────────────┐
                             │  Placement Group (PG) Layer                  │
                             │  Hash(object_name) % num_pgs -> PG ID       │
                             └──────────────────────┬───────────────────────┘
                                                    │ CRUSH Rule Evaluation
                                                    ▼
                             ┌──────────────────────────────────────────────┐
                             │  RADOS Cluster (OSDs 0 ... N)                │
                             │  - Primary-Copy Replication Protocol         │
                             │  - BlueStore Raw NVMe Engine on each OSD     │
                             │  - OSD Peer Heartbeats & Self-Healing Repair │
                             └──────────────────────────────────────────────┘

The core architectural breakthrough is algorithmic placement:

• A client wishing to write or read object "photo-992.jpg" does NOT query a master metadata server.
• The client reads a compact cluster topology map (the Cluster Map, updated via Paxos monitors only during membership changes).
• The client applies the CRUSH function locally: $$\text{Target OSDs}=\text{CRUSH}(\text{ClusterMap},\text{Hash}(\text{"photo-992.jpg"}),\text{Rule})$$
• The client connects directly over TCP to the calculated Primary OSD and streams the raw payload.

3. Core Terminology & Guarantees

4. System Architecture & Component Anatomy

SYSTEM ARCHITECTURE BLUEPRINTDISTRIBUTED SYSTEMS

⤢Expand

ARCHITECTURAL FLOW · STEP 1 OF 3

1. Client Access and LIBRADOS & RGW (RADOS Gateway)

Establishes the ingress and structural boundary across Client Access and LIBRADOS & RGW (RADOS Gateway): S3 and Swift Compatible REST APIs; Linux Kernel Driver / QEMU-KVM; MDS (Metadata Server) Cluster.

Architectural Invariant: Embeds CRUSH calculation in client Calculates target OSD directly Zero centralized metadata bottleneck Direct TCP stream to Primary OSD.

ARCHITECTURAL FLOW · STEP 2 OF 3

2. Step 2: CRUSH Function Evaluation & Topology Hierarchy (CRUSH Bucket Tree)

Coordinates core data-plane execution and state transitions through Step 2: CRUSH Function Evaluation & Topology Hierarchy (CRUSH Bucket Tree): osd_list = CRUSH(map, pgid, rule, failure_domain="rack"); Rule: Select 3 replicas across distinct racks and hosts; Deterministic, pseudo-random, weight-proportional selection.

Architectural Invariant: Maintains master Cluster Map: Epoch, OSD states, CRUSH rules Never in client data path!.

ARCHITECTURAL FLOW · STEP 3 OF 3

3. BlueStore Storage Engine Internals (Direct NVMe Block Access Without Linux Filesystem) & Raw Block Device Bypass

Enforces durability, state convergence, and output verification across BlueStore Storage Engine Internals (Direct NVMe Block Access Without Linux Filesystem) & Raw Block Device Bypass: Consumes raw NVMe block partition directly Eliminates Linux VFS, Ext4/XFS journaling overhead Zero double-write penalty for large objects; Stores object metadata, chunk extents, checksums; Runs on BlueFS: minimal in-memory pseudo filesystem.

Architectural Invariant: New writes allocated in unallocated raw blocks Atomic metadata pointer swap in RocksDB Hardware CRC32c verification on every block read.

Deep Architecture Anatomy:

1. The Ceph Monitor Cluster (ceph-mon):
   • Standard deployment runs 3 or 5 monitor nodes executing Paxos consensus.
   • Monitors maintain incremental versions (epochs) of the OSD Map: which drives are up, down, in, or out.
   • When an OSD dies, peer OSDs detect missed heartbeats and report failure to the MONs. MONs commit a new OSD Map epoch and broadcast it asynchronously to clients and OSDs.
2. The CRUSH Placement Engine:
   • Organizes physical hardware into a directed tree hierarchy: root $\to$ datacenter $\to$ room $\to$ rack $\to$ host $\to$ osd.
   • Rules specify failure domains: e.g., "take root default; chooseleaf firstn 3 type rack; emit".
   • The rule forces CRUSH to select 3 OSDs located in three completely different server racks, ensuring surviveability if an entire rack loses power.
3. The BlueStore Storage Engine:
   • Data Path: Writes raw object payloads directly to raw disk sectors using asynchronous kernel-bypass I/O (libaio / io_uring).
   • Metadata Path: Writes object keys, extended attributes (omap), allocation bit maps, and checksums to an embedded RocksDB instance running on a dedicated fast NVMe partition.
   • Copy-on-Write: Updates write to newly allocated unwritten blocks, followed by an atomic RocksDB transaction updating the extent pointer.

5. Detailed Request Flows & Protocols

5.1 The RADOS Primary-Copy Write Path

Client (LIBRADOS)             Primary OSD                   Secondary OSD 1               Secondary OSD 2
       │                           │                               │                             │
       ├── 1. Compute CRUSH ───────┤                               │                             │
       │   PG -> [OSD 1, 2, 3]     │                               │                             │
       │                           │                               │                             │
       ├── 2. Write Object ───────>│                               │                             │
       │                           ├── 3. Write locally (BlueStore)│                             │
       │                           │                               │                             │
       │                           ├── 4. Replicate payload ──────>│                             │
       │                           ├── 4. Replicate payload ────────────────────────────────────>│
       │                           │                               ├── 5. BlueStore Commit       ├── 5. BlueStore Commit
       │                           │<── 6. Replica Commit ACK ─────┤                             │
       │                           │<── 6. Replica Commit ACK ───────────────────────────────────┤
       │                           │                               │                             │
       │<── 7. Write Complete ─────┤ (All replicas committed)      │                             │

1. Local Calculation: The client library hashes the object name to find its Placement Group ($PG=\text{hash}(name)(\mathrm{mod}M)$) and executes CRUSH to determine the acting set: e.g., $[OS{D}_1,OS{D}_2,OS{D}_3]$.
2. Primary Submission: The client sends the write request directly to the primary ($OS{D}_1$).
3. Local & Parallel Replication:
   • $OS{D}_1$ writes the payload to its local BlueStore engine.
   • Simultaneously, $OS{D}_1$ forwards the exact payload and mutation log to secondary replicas ($OS{D}_2$ and $OS{D}_3$) over a high-speed private cluster network.
4. Replica Commitment: Secondary OSDs write the data to their BlueStore engines and acknowledge completion to $OS{D}_1$.
5. Client Notification: Once all replicas in the write quorum acknowledge persistent commit, the primary OSD sends an ACK to the client. The write is linearizable and crash-proof.

6. Mathematical Modeling & Hardware Physics

6.1 The CRUSH Straw2 Bucket Algorithm

CRUSH uses the Straw2 algorithm to select items proportional to their weight. Given an input hash $x$ (derived from the PG ID) and a set of candidate items $i\in \{1\dots n\}$ with weights $w_i$:

1. For each item $i$, CRUSH generates a pseudo-random value using a hash function seeded with $(x,i,r)$ where $r$ is the replication attempt counter:

2. The selection score $S_i$ scales the random draw by the natural logarithm of $u_i$ divided by the item’s weight:

3. The item with the maximum (least negative) score $S_i$ is selected:

This mathematical formulation guarantees that:

• The probability of selecting item $i$ is exactly proportional to its weight $w_i/\sum w_j$.
• Changing the weight of item $k$ causes data to migrate only between item $k$ and other items, with zero reshuffling among unchanged nodes.

6.2 Durability: 3x Replication vs. Reed-Solomon Erasure Coding

Let:

• Raw user data be $D=10\text{ Petabytes}$.
• Usable drive size per OSD be $20\text{ Terabytes}$.

1. Three-Way Replication ($3\times$): $$\text{Storage Required}=3\times 10\text{ PB}=30\text{ PB of raw drives}$$ $$\text{Drive Count}=\frac{30\text{ PB}}{20\text{ TB}}=1,500\text{ drives}$$ $$\text{Storage Efficiency}=\frac{1}{3}\approx 33.3\%(200\%\text{ storage overhead})$$

2. Reed-Solomon Erasure Coding (8+4):

   • Data chunks $K=8$, Parity chunks $M=4$.
   • Tolerates the simultaneous loss of any 4 drives in the same PG. $$\text{Storage Required}=\frac{8+4}{8}\times 10\text{ PB}=1.5\times 10\text{ PB}=15\text{ PB of raw drives}$$ $$\text{Drive Count}=\frac{15\text{ PB}}{20\text{ TB}}=750\text{ drives (50\% fewer drives than 3x replication!)}$$ $$\text{Storage Efficiency}=\frac{8}{12}\approx 66.7\%(\text{Only }50\%\text{ overhead})$$

7. Production TypeScript Implementation

This self-contained TypeScript simulation implements:

1. CRUSHMap: Hierarchical topology tree (Datacenter $\to$ Rack $\to$ Host $\to$ OSD).
2. Straw2Bucket: Mathematical Straw2 pseudo-random item selection algorithm.
3. PlacementGroupRouter: Object-to-PG hashing and deterministic multi-replica OSD selection.
4. CephClusterSimulator: Demonstrates failure detection and minimal data migration.

Execute with: npx tsx ceph-crush-capstone.ts

/**
 * ARCHITECTURE STUDY: Ceph Distributed Object Storage & CRUSH Map
 * Production architectural simulation: Straw2 CRUSH Selection,
 * Placement Group Mapping, Topology Fault Domains, and Minimal Migration.
 */

// ==========================================
// 1. Topology & CRUSH Tree Data Structures
// ==========================================

export interface CRUSHNode {
  id: number;
  name: string;
  type: 'root' | 'rack' | 'host' | 'osd';
  weight: number;
  children?: CRUSHNode[];
  isFailed?: boolean;
}

export class Straw2Bucket {
  private static hash(seed: number, id: number, r: number): number {
    let h = 0x811c9dc5 ^ seed;
    h = Math.imul(h ^ id, 0x01000193);
    h = Math.imul(h ^ r, 0x01000193);
    return Math.abs(h);
  }

  /**
   * Evaluates Straw2 score: S_i = ln(u_i) / w_i
   */
  public static selectItem(items: CRUSHNode[], seed: number, replicaIndex: number): CRUSHNode {
    let bestItem: CRUSHNode | null = null;
    let maxScore = -Infinity;

    for (const item of items) {
      if (item.isFailed || item.weight <= 0) continue;

      const rawHash = this.hash(seed, item.id, replicaIndex);
      // Uniform random float in (0, 1]
      const u = (rawHash % 1000000 + 1) / 1000000.0;
      const score = Math.log(u) / item.weight;

      if (score > maxScore) {
        maxScore = score;
        bestItem = item;
      }
    }

    if (!bestItem) throw new Error("No healthy candidate found in CRUSH bucket");
    return bestItem;
  }
}

// ==========================================
// 2. Placement Group & CRUSH Engine
// ==========================================

export class CRUSHEngine {
  private root: CRUSHNode;
  private numPGs: number;

  constructor(topology: CRUSHNode, numPGs: number = 64) {
    this.root = topology;
    this.numPGs = numPGs;
  }

  private hashString(str: string): number {
    let hash = 5381;
    for (let i = 0; i < str.length; i++) {
      hash = ((hash << 5) + hash) + str.charCodeAt(i);
      hash = hash & 0x7fffffff;
    }
    return hash;
  }

  public getPlacementGroup(objectName: string): number {
    return this.hashString(objectName) % this.numPGs;
  }

  /**
   * Executes CRUSH placement rule:
   * Rule: Choose 3 distinct Racks, then select 1 OSD per Rack
   */
  public selectOSDs(objectName: string, numReplicas: number = 3): number[] {
    const pgId = this.getPlacementGroup(objectName);
    const selectedOSDs: number[] = [];
    const usedRacks = new Set<number>();

    const racks = this.root.children || [];
    let r = 0;

    while (selectedOSDs.length < numReplicas && r < 50) {
      // 1. Select distinct Rack (seed combines pgId and root bucket ID)
      const chosenRack = Straw2Bucket.selectItem(racks, pgId ^ this.root.id, r);
      if (!usedRacks.has(chosenRack.id)) {
        // 2. Traverse down Rack -> Hosts -> OSDs (mix bucket/rack/host ID into PRNG seed
        // so rack-level and OSD-level Straw2 draws are statistically independent)
        const hosts = chosenRack.children || [];
        const rackSeed = Math.imul(pgId ^ chosenRack.id, 0x9e3779b1);
        const chosenHost = Straw2Bucket.selectItem(hosts, rackSeed, r);
        const osds = chosenHost.children || [];
        const hostSeed = Math.imul(rackSeed ^ chosenHost.id, 0x85ebca6b);

        try {
          const chosenOSD = Straw2Bucket.selectItem(osds, hostSeed, r);
          selectedOSDs.push(chosenOSD.id);
          usedRacks.add(chosenRack.id);
        } catch {
          // Retry next attempt if host has no healthy OSD
        }
      }
      r++;
    }

    return selectedOSDs;
  }
}

// ==========================================
// 3. Execution & Verification Harness
// ==========================================

export function runCephDemo() {
  console.log("=== ARCHITECTURE STUDY: Ceph CRUSH Map Placement Engine ===");

  // Construct a 2-Rack topology tree
  const clusterTopology: CRUSHNode = {
    id: 100,
    name: "datacenter_root",
    type: "root",
    weight: 4.0,
    children: [
      {
        id: 201,
        name: "rack_A",
        type: "rack",
        weight: 2.0,
        children: [
          {
            id: 301,
            name: "host_A1",
            type: "host",
            weight: 2.0,
            children: [
              { id: 1, name: "osd.1", type: "osd", weight: 1.0 },
              { id: 2, name: "osd.2", type: "osd", weight: 1.0 },
            ],
          },
        ],
      },
      {
        id: 202,
        name: "rack_B",
        type: "rack",
        weight: 2.0,
        children: [
          {
            id: 302,
            name: "host_B1",
            type: "host",
            weight: 2.0,
            children: [
              { id: 3, name: "osd.3", type: "osd", weight: 1.0 },
              { id: 4, name: "osd.4", type: "osd", weight: 1.0 },
            ],
          },
        ],
      },
    ],
  };

  const ceph = new CRUSHEngine(clusterTopology, 32);

  const sampleObjects = [
    "user_avatar_101.png",
    "backup_database_2026.tar.gz",
    "metrics_timeseries_shard0.parquet",
    "vm_disk_image_ubuntu.raw",
  ];

  console.log("\n[1] Algorithmic CRUSH Placement (Zero Metadata Lookups):");
  for (const obj of sampleObjects) {
    const pg = ceph.getPlacementGroup(obj);
    const osdSet = ceph.selectOSDs(obj, 2);
    console.log(`  Object "${obj}" -> PG: ${pg.toString().padStart(2)} -> Target OSDs: [osd.${osdSet.join(', osd.')}]`);
  }

  // Simulate Drive Failure & Self-Healing
  console.log("\n[2] Simulating Hardware Failure on osd.1 in Rack A:");
  const osd1 = clusterTopology.children![0].children![0].children![0];
  osd1.isFailed = true;
  console.log("  osd.1 marked FAILED in cluster map. Re-evaluating placements...");

  for (const obj of sampleObjects) {
    const osdSetAfter = ceph.selectOSDs(obj, 2);
    console.log(`  Object "${obj}" -> Updated Active Set: [osd.${osdSetAfter.join(', osd.')}]`);
  }

  console.log("\n=== Ceph CRUSH Simulation Complete. Invariants Verified. ===");
}

runCephDemo();

8. Real-World Case Studies

8.1 CERN (Large Hadron Collider Data Fabric)

• Stores over 1 Exabyte of scientific particle collision data in Ceph.
• Operates tens of thousands of OSDs across multiple data center buildings, leveraging CRUSH rules to survive entire facility power outages without data unavailability.

8.2 Bloomberg (Massive Market Data & Cloud Infrastructure)

• Deploys Ceph as the multi-tenant block and object storage substrate for their internal OpenStack and Kubernetes clouds.
• Utilizes RBD (RADOS Block Device) thin provisioning and instant copy-on-write snapshots to spin up thousands of financial analysis virtual machines in seconds.

8.3 DigitalOcean (Spaces Object Storage & Block Storage)

• Powers the public “Spaces” S3-compatible cloud storage product using Ceph RADOS Gateway (RGW) and custom NVMe BlueStore clusters.

9. Edge Cases, Failure Modes & Antipatterns

9.1 Placement Group (PG) Undersizing & Oversizing

• Undersizing Failure: If a pool with 1,000 OSDs is created with only 512 PGs, many OSDs will receive zero PGs, leaving drives completely unused while others saturate and trigger out-of-space warnings.
• Oversizing Failure: Creating 10,000 PGs per OSD consumes excessive CPU and RAM, as each OSD must maintain peering state machines and send heartbeats for every hosted PG.
• Golden Rule: Target approximately 100 to 250 Placement Groups per physical OSD.

9.2 OSD Flapping Storms

• Failure Mode: When network switches drop packets, an OSD misses heartbeats and is marked down. Seconds later, it successfully pings peers and is marked up. Rapid flapping floods monitors with map updates, saturating the Paxos cluster.
• Remediation: Configure mon_osd_down_out_interval (default 600s). Ceph delays data migration for 10 minutes when an OSD goes down, allowing transient reboots or cable swaps to resolve without triggering petabytes of network rebalancing.

9.3 Deep Scrubbing I/O Starvation

• Failure Mode: Ceph periodically executes Deep Scrubbing: reading every byte of every object and recalculating CRC32c checksums to detect silent disk bit rot. If deep scrub runs during peak client business hours, background read I/O saturates NVMe disk queues.
• Remediation: Restrict deep scrubbing to off-peak maintenance windows using osd_scrub_begin_hour and osd_scrub_end_hour.

10. Observability, Metrics & Production Telemetry

11. Guided Hands-On Lab / Engineering Exercises

Lab 1: Implement CRUSH Failure Domain Isolation

• Objective: Extend CRUSHEngine to support multi-level failure domain isolation (chooseleaf type room).
• Deliverable: Verify that even if an entire server room is marked failed, all objects remain readable from surviving rooms.

Lab 2: Measure Minimal Migration under Straw2 vs. Modulo Hashing

• Objective: Simulate 100,000 objects mapped across 10 OSDs. Add an 11th OSD.
• Deliverable: Show that naive modulo hashing moves $>90\%$ of objects, whereas Straw2 CRUSH moves exactly $1/11\approx 9.1\%$ of objects.

Lab 3: Simulate Degraded Read Recovery During OSD Outage

• Objective: In a $3\times$ replicated pool, inject a permanent read failure on the Primary OSD.
• Deliverable: Trace how LIBRADOS catches the error, consults the updated OSD Map, and redirects reads to Secondary Replica 1 seamlessly.

// Generalized recursive chooseleaf traversal supporting 'room' | 'rack' | 'host':
public selectOSDsByFailureDomain(
  objectName: string,
  failureDomain: 'room' | 'rack' | 'host',
  numReplicas: number = 3
): number[] {
  const pgId = this.getPlacementGroup(objectName);
  const domains = this.collectBucketsOfType(this.root, failureDomain);
  const selectedOSDs: number[] = [];
  const usedDomains = new Set<number>();

  let r = 0;
  while (selectedOSDs.length < numReplicas && r < 64) {
    const domainSeed = Math.imul(pgId ^ this.root.id, 0x9e3779b1);
    const chosenDomain = Straw2Bucket.selectItem(domains, domainSeed, r);

    if (!usedDomains.has(chosenDomain.id)) {
      try {
        const leafOSD = this.descendToOSD(chosenDomain, pgId, r);
        selectedOSDs.push(leafOSD.id);
        usedDomains.add(chosenDomain.id);
      } catch {
        // Selected failure domain has no healthy leaf OSDs; increment r and retry
      }
    }
    r++;
  }
  return selectedOSDs;
}

private descendToOSD(node: CRUSHNode, pgId: number, r: number): CRUSHNode {
  let curr = node;
  while (curr.type !== 'osd') {
    const children = curr.children || [];
    const levelSeed = Math.imul(pgId ^ curr.id, 0x85ebca6b);
    curr = Straw2Bucket.selectItem(children, levelSeed, r);
  }
  return curr;
}

12. Comprehensive Summary & Decision Framework

Enterprise Storage Architecture Comparison

Production Deployment Checklist

1. Network Separation: Provide two physically separate 25GbE/100GbE networks: a Public Network for client I/O and a Cluster Network dedicated to OSD replication and backfill traffic.
2. Dedicated WAL/DB SSDs: In hybrid clusters with mechanical HDDs, place BlueStore’s RocksDB metadata on fast NVMe SSD partitions sized at $\ge 4\%$ of the OSD data disk capacity.
3. Monitor Sizing: Always deploy an odd number of Ceph Monitors (3 or 5) across distinct power and network failure domains.
4. Scrub Scheduling: Confine deep scrubbing to off-peak weekend hours to prevent background I/O contention during peak client traffic.

13. Authoritative References & Version Context

• Sage A. Weil et al. (2006), “Ceph: A Scalable, High-Performance Distributed File System”, USENIX OSDI ‘06 — usenix.org/conference/osdi-06/ceph-scalable-high-performance-distributed-file-system
• Sage A. Weil, Scott A. Brandt, Ethan L. Miller, and Carlos Maltzahn (2006), “CRUSH: Controlled, Scalable, Decentralized Placement of Replicated Data”, ACM SC ‘06 — doi.org/10.1145/1188455.1188582
• Ceph Architecture Documentation (Reef / Squid Releases) — docs.ceph.com/en/reef/architecture/
• Version Context: Architecture reflects Ceph Reef (18.x) and Squid (19.x) with BlueStore raw block engines and multi-datacenter CRUSH failure domains.