How to design an object-storage service

An object store is one split: a tiny mutable metadata database beside an enormous immutable byte pool, and almost every property follows from it.

The split

• Object: an immutable lump of bytes (1 B to 5 TB); the service never looks inside. Key: its string name. Bucket: a named container fixing owner and region.
• Four ops named for HTTP verbs: PUT, GET (honors byte ranges), DELETE, LIST (prefix scan).
• Metadata = 27 TB: sorted, mutable, needs compare-and-swap. Small consistent DB, B-tree, range-partitioned, leader per shard, linearizable reads.
• Byte pool = 200 PB: immutable, append-only, huge cheap store on bare drives.
• Metadata is 0.0135% of the corpus, small enough to shard, replicate 3x, and take leader reads without thinking about the bill.

Request ──> touches names/order/version? ──> Metadata (27 TB, CAS, B-tree)
        └─> touches the bytes?           ──> Byte pool (200 PB, append-only)

Sizing (back of envelope)

• 100 billion objects x 2 MB avg = 200 PB. 1,000 PUT/s, 10,000 GET/s = 2 GB/s ingest, 20 GB/s egress (480 Gbps at 3x peak).
• Raw drive cost $0.01/GB-month = $10,000/PB-month. Media bill set by physical bytes per logical byte.
• Metadata row ~270 bytes -> 27 TB for 100 billion objects.
• Durability: 11 nines claimed (annual loss 1e-11). Availability: 99.99% GET, 99.9% PUT. Read-after-write guaranteed; LIST per-page only.

Erasure coding (the $72 M/year lever)

• RS(k, m): k data + m parity fragments on k+m distinct rack-diverse drives; any k reconstruct, survives m simultaneous losses.
• Storage overhead = (k+m)/k. Systematic code: data fragments are the object cut into k pieces.

• RS(10,4) beats RF 3 on both axes: saves 320 PB, $38.4 M/year, 20,000 drives, tolerates 2 more failures.

Durability numbers

• Repair window = time a stripe is one fragment short. Rebuild 16 TB onto one node over 1 Gbps = 36 h (bad); declustered across 200 nodes at 10% NIC = ~2 h. Use 2 h.
• Repair amplification 10x: reads k survivors to rebuild one fragment (replication = 1x). The 10% cap keeps bandwidth for customers.
• AFR 2% -> per-window drive death p = 4.6e-6. Loss per stripe = n x AFR x C(n-1, j) x p^j. Nines = -log10(loss).
• Model says 19 nines; operators claim 11. Gap is the correlated-failure haircut (shared power, racks, firmware batches, bad rollouts, operators). Not computable from first principles.
• Rack diversity is worth ~16 orders of magnitude. Invariant: no rack holds more than m fragments (14 fragments span >= 4 racks).

Gotchas

• Degraded read (a needed fragment is slow/dead) fetches k, so object p99 = fragment p99.9 (5x tail hit). Fix: k+2 hedged reads at 1.2x bandwidth restores the tail.
• 40 KB line = k x block (block = 4,096 B). Below it, coding an object individually wastes blocks (4 KB pays 14x). Fix: pack small objects into a sealed 1 GB extent, code the extent; the real driver is IOPS/seeks (~100 random reads/spindle), not bytes.
• No overwrite in place. A coded parity update is ~9 I/Os across 5 nodes and is a non-idempotent delta (retry = silent garbage). So every write = allocate stripe, write k+m fragments, commit one metadata row. Failure before commit leaves orphans for GC.
• Immutability buys: free retries, caches never invalidate (ETag is a content fingerprint), cheap versioning (270-byte row), lock-free background loops.

Background loops and rules

• DELETE writes a delete marker (recoverable); versioning grows the corpus, so expire noncurrent versions after 30 days by default.
• Multipart: part = max(8 MB, object / 10,000). Cap comes from in-flight metadata, not drop rates; on wired links the drop-balance formula says never chunk. complete validates the (N, ETag) list; abort expires after 7 days.
• GC = mark and sweep (never refcount: two stores, no shared transaction, undercount deletes live data). 14 min/week, mark against leaders only, 24-hour grace period.
• Scrub: ~2,240 silent corruptions per pass over 280 PB (URE ~1 per 1e15 bits) — a certainty. CRC per fragment, reconstruct from k, quarantine drive, 8-day period.
• Read-after-write covered after the 200 returns, on any frontend; not covered concurrently or on followers. LIST per-page only: a billion-key traversal is 2.8 h, no snapshot survives that.
• Tiering: archive (1/5 price) pays only below 0.4 reads per PB-month; above that a retrieval fee makes it a 10x loss.