Design S3-like object storage

The API is trivial — PUT, GET, LIST, DELETE on a bucket/key. The whole problem is one promise: an object you acknowledged is never lost, even as disks die at 2% a year forever. Durability is a number you design toward, not a feature you bolt on.

Source: Vol. 2 Ch. 9, archive Case drill Durability math first

First principle — durability is a probability you engineer

Disks fail. Not "might fail" — will fail, at a measurable annual rate (AFR ≈ 2%/yr for fleet drives). So "don't lose data" is not achievable; "lose data with probability below 10⁻¹¹ per object per year" is. That target — eleven nines — is the forcing function for this entire design. Every later choice (how many copies, how fast we repair, where we place fragments) is downstream of one equation: the probability that all redundant copies of an object die inside one repair window. Get that equation right and the rest of the system is plumbing.

0. Interview hinge

The hinge is the moment the prompt stops being generic and the architecture becomes forced. Here it is: you cannot store one copy of anything, and you cannot afford infinite copies, so the entire design is a negotiation between storage overhead and the probability of correlated loss. Replication and erasure coding are the two answers; the durability equation tells you which one a given object class deserves.

Invariant to protect

An acknowledged PUT is durable. The instant you return 200 to the client, the object must already survive the loss of any single failure domain (disk, node, rack, ideally AZ). This is a write-quorum decision, not a background-repair decision — see deep dive 4. Corollary: never ack before W durable replicas exist.

Tempting but wrong

"Use erasure coding everywhere — it's cheaper." EC's 50% overhead is seductive, but EC turns a single-fragment loss into a read-k-fragments-to-reconstruct-one repair, and turns a small-object GET into a scatter-gather across k nodes. For hot, small objects that read amplification dominates the storage saving. Pick the redundancy scheme per object class, not globally (deep dive 1).

1. Clarify the contract

Treat the prompt as a product contract before a box diagram. What it must do:

PUT / GET / DELETE an object by (bucket, key); LIST by prefix.
Eleven nines of durability (99.999999999%) and several nines of availability.
Read-after-write consistency for new objects (a GET right after a successful PUT returns the bytes).
Self-healing: detect and repair lost/corrupt copies automatically, forever.
Immutable objects: a key's bytes don't mutate in place — a new PUT creates a new version. This is the single assumption that makes durability tractable.

What it explicitly need not do: no random in-place writes (objects are write-once, replace-whole), no POSIX semantics (no rename, no append, no directory locks), no cross-object transactions. And multipart / resumable upload is deferred — that mechanism (chunking, idempotent commit, resume-after-failure) is taught in full at its anchor, C17. Here we assume the bytes arrive; our job is to place and keep them.

2. Put numbers on the shape — the durability calculation

This is the load-bearing math of the case. Skipping it is how candidates fail this question.

Storage overhead first. Two redundancy schemes:

3× replication: store 3 full copies. To keep 1 PB of user data you buy 3 PB of disk → 200% overhead.
(6+3) erasure coding: split each object into k=6 data fragments, compute m=3 parity fragments (Reed–Solomon), store all 9; any 6 of 9 reconstruct the object. To keep 1 PB you buy 9/6 = 1.5 PB → 50% overhead, and you tolerate any 3 simultaneous fragment losses.

Now the nines. Model a disk's annual failure rate as AFR = 2% = 0.02. The thing that actually kills an object is not "a disk failed" — we repair those — it's "all redundant copies die inside the repair window before we can rebuild." Let the repair window be t years (how long it takes to notice a lost copy and rebuild it elsewhere). The per-copy probability of dying inside that window is roughly p = AFR · t. With N independent copies, losing all of them in the same window is:

P(object loss / window) ≈ p^N = (AFR · t)^N

The leverage is the exponent N and the smallness of t. Make repair fast and copies independent, and the probability collapses geometrically. Suppose we detect-and-repair a dead copy within 1 hour: t = 1/8760 yr, so p = 0.02 / 8760 ≈ 2.3·10⁻⁶. With 3 replicas:

P(loss/window) ≈ (2.3·10⁻⁶)³ ≈ 1.2·10⁻¹⁷

There are 8760 such windows per year, so the annual loss probability per object is ≈ 8760 · 1.2·10⁻¹⁷ ≈ 10⁻¹³ — about thirteen nines, comfortably past our eleven-nines target. That is the "eleven nines" intuition made concrete: 3 copies + fast repair, not 30 copies. The number of copies barely matters once repair is fast — the exponent does the work. Slow repair is the silent killer: stretch the window to 1 week and p ≈ 3.8·10⁻⁴, giving p³ ≈ 5.6·10⁻¹¹ per window — orders of magnitude worse, now flirting with the target. Durability is bought with repair speed, then redundancy.

3× replication overhead

200%

(6+3) EC overhead

50%

3 copies, 1h repair

~13 nines

3 copies, 1wk repair

~10 nines

Caveat to say out loud: this p^N model assumes independent failures. The real enemy is correlated failure — a whole rack loses power, an AZ floods, a bad firmware push bricks a disk model. That correlation is exactly why placement spreads copies across failure domains (next section): independence is something you engineer, not something you get for free.

3. Define the surface area

Keep the API small; it expresses the product operation and hides placement, fragments, and repair entirely.

API / operation	Why it exists
`PUT /bucket/key`	Write-once object create/replace; acks only after W durable copies exist.
`GET /bucket/key`	Read object bytes; metadata lookup resolves placement, then stream from data plane.
`HEAD /bucket/key`	Existence + version + size + checksum without the body — pure metadata-plane op.
`LIST /bucket?prefix=`	Ordered key enumeration — the metadata-plane scaling pain point (deep dive 2).
`DELETE /bucket/key`	Tombstone the version; reclaim fragments asynchronously.

4. Model the data — two planes

The defining structural decision: separate the metadata plane from the data plane. They scale on different axes and fail differently, so they must be different systems.

Data plane — the bytes. Stored as immutable replicas or EC fragments on dumb, cheap, dense storage nodes. Scales by adding disks. Addressed by an opaque internal blob ID, never by user key.
Metadata plane — the index. Maps (bucket, key, version) → {blob IDs, placement, size, checksum, ACL}. Small per entry but must answer existence, version, and ordered listing at the full object count. Scales by partitioning the key space (foundation lesson 07).

bucketobject metadata (key→blobs)versionplacement mapchecksumEC fragment / replica

5. Linearized design

Walk a request the way it actually moves. The first bottleneck (metadata) falls out naturally.

1. Front-end authenticates and authorizes the (bucket, key) operation.
2. For a PUT, the placement policy picks target nodes across distinct failure domains (different racks/AZs), and bytes are written there as replicas or split into EC fragments.
3. Only after W durable writes ack do we commit the metadata entry (key→blob IDs, checksum, version) and return 200. This ordering is the durability invariant.
4. A GET resolves metadata first (one partitioned lookup), then streams bytes from a data node (or scatter-gathers k EC fragments).
5. Background scrubbers continuously read fragments, verify checksums, and rebuild anything missing/corrupt — this is the engine that keeps the repair window t small, i.e. keeps the nines high.
6. Lifecycle/version policies tombstone and reclaim space asynchronously.

CLIENT │ PUT /bucket/key (bytes) ▼ ┌───────────────┐ ┌──────────────────────────────────────┐ │ FRONT-END / │ │ METADATA PLANE │ │ API gateway │─────▶│ partitioned index (lesson 07) │ │ authn · authz │ │ (bucket,key,ver) → {blobIDs, csum} │ └───────┬───────┘ │ answers: exists? version? LIST? │ │ └──────────────────────────────────────┘ │ split object into parts / fragments ▼ ┌───────────────────────── DATA PLANE ──────────────────────────┐ │ object → [ part0 | part1 | ... ] (or EC: 6 data + 3 parity) │ │ │ │ placement spreads copies/fragments across FAILURE DOMAINS: │ │ │ │ AZ-a AZ-b AZ-c │ │ ┌───────┐ ┌───────┐ ┌───────┐ │ │ │rack 1 │ │rack 4 │ │rack 7 │ │ │ │ frag0 │ │ frag2 │ │ frag4 │ ← any k=6 of the │ │ │ frag1 │ │ frag3 │ │ frag5 │ 9 reconstruct │ │ │parity0│ │parity1│ │parity2│ the object │ │ └───────┘ └───────┘ └───────┘ │ └──────────────────────────────────────────────────────────────────┘ scrubbers patrol every fragment → checksum mismatch ⇒ rebuild

6. Deep dives

(1) Replication vs erasure coding: the read-amplification / repair-cost curve

Both schemes hit our durability target; they differ in what you pay per operation. The honest comparison is three costs, not one:

Cost axis	3× replication	(6+3) erasure coding
Storage overhead	200%	50%
Read amplification (normal GET)	1 node, 1 read — stream a whole copy.	Read 6 fragments from 6 nodes, recombine. Scatter-gather; tail latency = slowest of 6.
Repair cost (one lost copy/fragment)	Copy 1 full object from a surviving replica → 1× object bytes over the network.	Read k=6 fragments to reconstruct the 1 lost fragment → 6× the fragment's bytes read across 6 nodes.

That last row is the EC tax that candidates forget. Replication repair is trivial: stream one good copy to a new disk, costing 1× the object's bytes. EC repair is k×: to rebuild a single 10 MB fragment you must read 6 fragments (60 MB) from 6 different nodes and run the Reed–Solomon decode. So a correlated rack loss that knocks out thousands of fragments triggers a repair-bandwidth storm that is k times worse under EC — and repair bandwidth competes with live customer reads. The design rule that falls out: replicate hot/small objects, erasure-code cold/large objects. Small objects can't even be split into 6 useful fragments; cold objects are read rarely so the read-amplification tax almost never gets paid, while their 50% storage saving is paid every single day. This is the same partitioning-by-access-pattern logic as a tiered cache (foundation lesson 08 on what a copy actually buys you).

(2) Metadata scaling is the hidden bottleneck

"Just add disks" scales the data plane forever — bytes are embarrassingly partitionable. The metadata plane is where the design quietly dies. Consider the scale: a bucket with 10¹¹ small objects has 100 billion index rows that must answer three different question shapes:

Point existence/version (HEAD, GET): hash-partition (bucket, key) across thousands of metadata shards — uniform, easy, fast.
Ordered LIST by prefix: this fights the point-lookup partitioning. A prefix scan must hit keys in sorted order, but hash partitioning scatters sorted keys everywhere. So listing wants a range-partitioned, sorted index (think LSM-tree / sorted-string semantics, DDIA Ch. 3) — a different physical layout than the point index wants.
Hot prefixes: range partitioning re-introduces the hot-shard problem (lesson 07) — a customer hammering one prefix overloads one shard. Real systems (S3) historically had per-prefix request-rate limits for exactly this reason.

The takeaway: the data plane is dumb-and-scalable, the metadata plane is the database, and it inherits all of DDIA Ch. 6's partitioning tensions — point access vs. range access pulling toward incompatible layouts. When this case gets hard, it gets hard here, not on the bytes.

(3) Read-after-write forces metadata coordination

The contract says: a GET issued right after a successful PUT returns the new bytes. That is a read-after-write (read-your-writes) consistency guarantee, and it lives entirely in the metadata plane — the bytes are already durably on disk before we acked; the only question is whether the index lookup sees the new version. This is DDIA Ch. 5's read-your-writes guarantee applied to an index. The trap: if the metadata write goes to a leader but reads can be served by an eventually-consistent follower, a GET routed to a lagging replica returns 404 for an object you just successfully wrote — a contract violation that looks like data loss to the client. Options: commit metadata to a quorum and read from a quorum (W+R>N, lesson 08), or pin the writing key to its leader for reads, or return the new version's locator in the PUT response so the immediate GET is self-routing. The data plane is the easy half; read-after-write is a metadata-coordination problem (foundation lesson 09).

7. Trade-offs

Choice	Buys	Costs	Choose when
Replication vs erasure coding	simple 1× reads & 1× repair	200% storage vs EC's 50%	hot or small objects; EC for cold/large
Strong metadata vs eventual metadata	read-after-write, no phantom 404s	quorum coordination on every write/read	new-object PUTs (the visible contract)
Large part size vs small part size	less metadata per object	worse retry granularity, coarser EC	very large objects (defers to C17)
Immediate delete vs tombstone	frees space sooner	race with in-flight replicas / repairs	non-versioned, low-risk buckets

The sharpest one to narrate is the first. EC's 50% overhead vs replication's 200% looks like an obvious win — at exabyte scale it's the difference between buying 1.5 PB and 3 PB of disk per PB stored, real money. But the trade is paid in operations, not capital: every EC GET is a 6-way scatter-gather (tail latency = slowest of six nodes) and every EC repair reads 6 fragments to rebuild 1. A senior answer doesn't pick a side globally — it tiers by access pattern: replicate the hot, small, latency-sensitive objects; erasure-code the cold archive where reads are rare and the storage saving compounds daily. The redundancy scheme is a per-object-class decision, and saying that is the signal.

8. Failure modes

Failure	Mitigation
Silent bit rot / corruption	End-to-end checksums stored with every fragment; scrubbers patrol and rebuild on mismatch — a bad copy doesn't count toward durability.
Correlated rack/AZ loss	Placement spreads replicas/fragments across failure domains so a domain loss never takes more than (N−1) copies — the only way the p^N independence assumption holds.
Repair storm after big failure	Throttle repair bandwidth, prioritize under-replicated objects (those nearest to total loss rebuild first), keep repair off the customer-read path. Especially acute under EC (k× bandwidth).
Rack dies mid-PUT, before W copies	Don't ack until W durable copies exist (see Q&A 1). If W not met, the PUT fails and the client retries — no phantom durable object.
LIST inconsistency	Version metadata mutations; define listing semantics (eventually-consistent listing is acceptable, point read-after-write is not).

9. Interview Q&A — be ready for these

You acked a PUT, then a rack died before replication finished — did you lose data? (senior answer) Not if the ack discipline is correct. You must define a write threshold W and only return 200 after W durable copies in distinct failure domains exist. With W=2 across two AZs, a single rack/AZ dying after the ack still leaves a copy, and the scrubber rebuilds back to full redundancy. If instead you acked after the first write and replicated lazily, then yes — that rack death is silent data loss, and it's the canonical wrong answer. The invariant is "ack implies durable," which is a write-quorum (W) decision (lesson 08), not something background repair can fix after the fact.
Why is 3 copies enough for eleven nines — why not 5 or 10? (senior answer) Because durability is (AFR·t)^N — exponential in N but also driven hard by the repair window t. With 1-hour repair, 3 copies already give ~13 nines; more copies barely move it while doubling cost. The real lever is fast repair, not more copies: shrinking t from a week to an hour gains far more nines than adding a fourth replica. Spend on detection + rebuild speed before redundancy.
When erasure coding over replication, and what does it cost you? (senior answer) EC for cold/large objects: 50% overhead vs 200%, same durability. The cost is read amplification (a GET scatter-gathers k fragments, tail = slowest of k) and k× repair bandwidth (rebuild one fragment by reading k). So EC where reads are rare and objects are large enough to split; replicate hot/small objects where those taxes dominate.
What's the hidden bottleneck — the bytes or the index? (senior answer) The index. Bytes partition trivially (add disks). Metadata must answer point existence/version and ordered prefix LIST — which pull toward incompatible partitioning (hash for points, range for listing), and range partitioning re-introduces hot shards (lesson 07, DDIA Ch. 6). The data plane is dumb and scalable; the metadata plane is the real distributed database.
How do you guarantee read-after-write? (senior answer) It's a metadata problem — the bytes are already durable before the ack. Either commit metadata to a quorum and read from a quorum so W+R>N (lesson 08/09), or route the immediate read to the leader/partition that took the write. The failure to avoid is serving GETs from a lagging follower that returns 404 for a just-written object (DDIA Ch. 5 read-your-writes).
A scrubber finds a fragment whose checksum doesn't match — what now? (senior answer) Treat the corrupt fragment as lost (it never counts toward the durability quorum), reconstruct it from the surviving replicas/fragments, and write a fresh good copy. This is why checksums are stored with the data end-to-end: silent corruption that still "exists" is more dangerous than an obvious missing copy, because a naive system would serve the bad bytes.
How do you keep repair from taking down the cluster after a big failure? (senior answer) Throttle repair bandwidth and prioritize the most-endangered objects (those with the fewest surviving copies rebuild first — they're closest to crossing into actual loss). Keep repair traffic isolated from customer reads. This matters most under EC, where rebuild reads k× the data and a rack loss can saturate the network.

Related foundation & cases

Multipart / resumable upload is deliberately deferred to its anchor C17 (chunking, idempotent commit, resume-after-failure). For the redundancy mechanics, foundation lesson 08 (replication) grounds the W-quorum ack discipline; the metadata plane's point-vs-range tension is lesson 07 (partitioning); and read-after-write is lesson 09 (consistency / CAP).

C17 · multipart upload (anchor) 07 · Partitioning 08 · Replication 09 · Consistency / CAP 13 · Fault tolerance

Takeaway

Object storage hides a trivial API over one ruthless promise: an acked object is never lost. That promise is a number — eleven nines — and it's bought by the equation P(loss) ≈ (AFR·t)^N, where the exponent (redundancy) and the smallness of t (repair speed) do the work, with placement across failure domains making the N copies actually independent. Choose redundancy per object class — replicate hot/small, erasure-code cold/large, paying EC's k× read-and-repair tax only where reads are rare. And remember the real bottleneck isn't the bytes (just add disks) but the metadata plane, which must serve read-after-write point lookups and ordered listings out of partitioning layouts that fight each other.