CHAPTER DEEP READ · System Design Interview Vol 2 · Ch 9
System Design Interview Vol 2 · Ch 9 · Alex Xu & Sahn Lam · 2022
The photos your phone backs up, the images and videos on every website, the logs your company is never allowed to delete — most of them live in something called object storage. This chapter builds one from scratch: how to make it hold everything, never lose anything, and still be cheap.
This kind of warehouse has a rule that sounds ridiculous: once something is stored, you may not edit it in place. Want to change one character? Store the whole thing again.
And yet that single concession buys everything else. Because nothing ever changes, you never have to worry about whether the copies agree with each other. Because you never have to worry, you can freely keep extra copies, put them far away, and put them on very cheap disks. It isn't stuck this way — it deliberately gave up one ability to buy a pile of others.
The familiar way to store things is nested folders, like on your laptop. Fine for a few thousand items; hopeless for a few billion, because the directory itself gives out first — the ledger of "what is this called and where does it live" grows too big for any one machine.
Small items are worse. The warehouse staples a registration card to every single item. A photo may be only tens of kilobytes, but its card costs the same as any other. A few billion cards weigh more than the goods.
① Split the ledger from the shelves. "What is it called, whose is it, when did it arrive" goes into a ledger; the bytes themselves get piled on shelves. A claim ticket links the two. The ledger is edited constantly, so it uses a system good at edits; the shelves are append-only, so they use the cheapest disks going.
② Bundle the small stuff. Don't give every tiny photo its own box. Stack hundreds of them into the same big crate and note in the ledger: "crate 7, this far in, this long." To fetch one, reach straight to that stretch — no need to unpack the crate.
③ Three copies, or shards plus spare cards. The clumsy way to survive loss is three identical copies, costing three times the space. The clever way: split one item into 8 pieces, then compute 4 extra spare cards from those 8. Put all 12 on different machines. Lose any 4 and the rest still reconstruct the original — like knowing a recipe well enough to work out a missing ingredient. It costs only half again as much space, yet survives more.
④ Regular checkups. Bytes on a disk quietly rot, with nothing reporting an error. So record a "fingerprint" on the way in, have a background job re-check it periodically, and silently repair from a good copy whenever it fails to match.
Shards save space, but fetching means gathering several pieces and reassembling them, so it is slower than grabbing one ready-made copy — which is why popular items usually still get plain duplicates.
Object storage is a deliberate subtraction: give up editing in place, and you get near-infinite scale, cheap disks and extraordinary safety. You do it by splitting the ledger from the shelves, bundling small items so their registration cards stop dominating, replacing three full copies with "shards plus spare cards" at one-and-a-half times the space, and running checkups so bytes can't rot unnoticed. The cost: fetching means reassembling, so it's a little slower.
Want the mechanisms, the notation and the diagrams? → Switch to the deep read
On the surface this chapter builds an S3. What it actually teaches is a far more portable piece of craft: split the system along the seam between mutable and immutable. The huge, tiny, constantly-edited metadata goes into a database; the enormous, write-once, never-modified bytes go into a different warehouse, joined by nothing but a claim ticket. Once split, each half can be optimized to an extreme the other could never tolerate: indexes and transactions on one side; sequential appends, small-object packing, erasure coding and cold tiers on the other. Object storage's powers were not added on — they were bought with the subtraction of in-place update.
/ in a key is just an ordinary character in the name.k chunks, compute m parity chunks; any loss of up to m chunks is recoverable. Space overhead is (k+m)/k.Chapter 9 of Volume 2. It follows Ch8 (Distributed Email Service), which threw attachments over the fence to "some object store nearby" — this chapter opens up the thing on the other side of that fence. Together with Ch4 (Distributed Message Queue) it forms Volume 2's distinctive "build the component, don't just wire it up" thread. Real-world counterparts: S3, Google Cloud Storage, Azure Blob Storage, Ceph, MinIO — and the floor under every data lake, backup system and CDN origin.
The stated goals are modest: hold 100 PB, keep 99.99% service availability, make durability high enough that loss is effectively off the table, and keep the cost down. That last one is the engine of the whole chapter — the first three can be met by simply keeping more copies. Only once cost is on the table do erasure coding and small-object packing become mandatory.
Turn 100 PB into physical objects: at 4 TB per spinning disk, 100PB / 4TB = 25,000 disks. A spinning disk manages roughly 100–150 random seeks per second, so the cluster's random IOPS budget is fixed at a couple of million per second, and no amount of money buys more. Every design that makes a read take one extra hop spends from that budget.
The book estimates a mix of roughly 40% small objects (under 1 MB), 20% medium and 40% large — an average object in the hundreds-of-MB range and object counts in the billions. At about 1 KB of metadata per object, the metadata table alone is terabytes: too big for one machine, so it must be sharded.
The lethal part is that 40% of small objects. Store each object as a file in a Linux filesystem and each one consumes an inode (~256 bytes). A few billion inodes is hundreds of gigabytes of pure overhead — and worse, reading a 10 KB thumbnail costs one IOPS to look up the inode and another to read the data, doubling the spend from that fixed budget. "Lots of small objects" is not a tuning problem; it is an architecture problem.
Block storage hands you a raw disk, file storage hands you a directory tree, object storage hands you a flat, fetch-the-whole-thing-by-name HTTP interface (details in Table 1). The difference isn't "does it look like folders" — it is what was given up. Object storage gave up in-place update and real directories, and a chain of difficulties vanished with them: if an object never changes, copies never need to agree with each other; if they never need to agree, they can be scattered across racks, datacenters and media; if it is written once, it can be appended sequentially, batched, and compacted later. S3's "throw in as much as you like" was paid for the moment that interface was designed.
This is the skeleton of the chapter. One upload is cut in two and lands in two entirely different systems:
UUID and the position inside that file.(bucket_id, object_name) → UUID, plus size, time, content type and permissions.The order cannot be reversed: always land the data first, the metadata second. Do it the other way and a crash in between leaves a metadata row pointing at bytes that do not exist — visible to the user, un-fetchable, the worst kind of broken. Crash in the correct order and the worst case is an orphaned blob nobody claims, which a background sweep cleans up. Better to leave garbage than a dangling pointer.
If the inode is a fixed cost, the answer is never let the filesystem know there are that many objects. Each data node keeps a small number of writable files of a few GB each; every new object is appended to the tail of the current one. When it fills up, seal it read-only and open another.
The object-to-location mapping lives in a node-local object_mapping table: UUID → (file, offset, length). A read is one mapping lookup plus one sequential read at an offset — inode overhead amortized to nearly nothing, and IOPS back down from two to one.
The cost lands on deletes. The file is already sealed read-only, so deleting an object just writes a tombstone in the mapping; the bytes still sit there. Space comes back through compaction: a background job picks files with a high fraction of dead data, moves the live objects into a new file, rewrites the mapping, then drops the old file whole. This is the LSM-tree bargain applied at the object layer — writes stay sequential, and the bill is deferred to a background batch.
The blunt way to survive loss is three copies, 3× space: 100 PB of data needs 300 PB of disk. At this scale that bill is fatal.
Erasure coding takes another route: split the object into 8 data chunks, compute 4 parity chunks, scatter all 12 across 12 machines. Any loss of up to 4 chunks is recoverable, at 12/8 = 1.5× space. The intuition is solving equations: 12 equations for 8 unknowns; cross out any 4 and the rest still solve. The point is that this is not "cheaper but riskier" — it is cheaper and safer: three replicas tolerate 2 simultaneous losses, 8+4 tolerates 4. This is how public clouds can claim eleven nines of durability on well under 3x overhead.
The costs come in three layers: ① repair amplification — losing one chunk means reading 8 to rebuild it, where a replica only needs one copy; ② read tail latency — a read must gather several chunks and waits on the slowest; ③ CPU — the coding is real computation. So real systems nearly always tier: hot data on replicas, converted to erasure coding by a background job once it cools.
One layer is easy to miss: no amount of redundancy stops bit rot. When a disk silently flips a bit without reporting an error, the system has no idea which copy to trust. So every chunk stores a checksum alongside it, a background scrubber recomputes and compares, and any mismatch is rebuilt from a good chunk — the step that upgrades durability from "keep more copies" to "verifiable".
There are two metadata tables. The bucket table is tiny (a user typically has a handful to a few dozen buckets) — one machine plus read replicas is plenty. The object table is billions of rows and terabytes, so it must be sharded, and the shard key decides which operation gets expensive. Shard by bucket_id and listing a bucket scans one shard in natural order — but a big bucket becomes a hotspot, and buckets with hundreds of millions of objects are routine, so that path collapses first. Shard by a hash of the full object path and distribution is perfectly even with single-object reads and writes always hitting one shard — but listing a bucket must fan out to every shard and merge.
The book takes the latter: single-object GET is overwhelmingly the hot path, while listing is a low-frequency administrative operation; if it really must be fast, maintain a separate bucket-ordered index for it. The trade is worth memorizing: a shard key always protects the hottest path, rather than trying to make no path slow.
Two more things fall out of the same table. Versioning: add a version column, and a new version of the same key is another row rather than an overwrite; GET returns the newest by default. Deletion: with versioning on, a delete is one more appended row carrying a delete marker, and the old versions remain on disk — which is both why accidental deletions can be recovered and why "deleted" objects keep showing up on the bill. Actual reclamation is left to lifecycle rules and compaction.
Large objects use multipart upload: split a 10 GB file into parts (S3's floor is 5 MB), upload in parallel, retry only the failed part, and let one final complete call assemble them into a single object in the metadata. Parts that never reach complete are pure garbage and need a lifecycle rule to sweep them — otherwise you pay, indefinitely, for bytes nobody can see.
Table 1 · Three storage types: not better or worse, but what each gave up
| Type | What it gives you | The honest cost | When to pick it |
|---|---|---|---|
| Block storage | Random read/write at any offset, lowest latency (microseconds to milliseconds) | Usually attaches to one machine; capacity capped per volume; expensive | Database files, anything that overwrites in place |
| File storage | A directory tree shared across machines; applications need almost no changes | The tree itself becomes the scaling wall; the metadata service gives out first at billions of files | Team shares, lifting legacy apps into the cloud |
| Object storage (this chapter) | Near-unlimited capacity, lowest unit cost, addressable over HTTP, highest durability | No in-place edits; no real directories, so renaming a "folder" is O(n) renames; tens to hundreds of ms to first byte | Images, video, backups, archives, data lakes — anything write-once, read-many |
Table 2 · Redundancy: replicas vs erasure coding
| Scheme | Strength | The honest cost | Decision rule |
|---|---|---|---|
| 3 replicas | Simple; repair is a plain copy; lowest read latency; friendly to small objects | 3× space — 100 PB needs 300 PB; tolerates only 2 simultaneous losses | Hot data, small objects, latency-critical |
Erasure code 8+4(the book's pick) | Only 1.5× space and higher fault tolerance (any 4 chunks); at scale it saves an order of magnitude | Repair amplification: one lost chunk means reading 8; reads gather many chunks, hurting tail latency; burns CPU | Warm/cold data, large objects, cost-driven |
| Tiering (real systems) | Replicas while hot, erasure coding once cold — both benefits | An extra background conversion pipeline; data exists in two forms mid-flight, raising operational complexity | Large scale with a clear hot/cold split |
Table 3 · Shard key for object metadata: which path are you protecting?
| Shard key | What gets fast | What gets expensive | Decision rule |
|---|---|---|---|
bucket_id | Listing a bucket scans one shard, already sorted by name | A big bucket is a hotspot: hundreds of millions of objects crush that shard, and it cannot be split further | Private deployments with bounded bucket sizes |
| Hash of the full path (the book's pick) | Perfectly even distribution; single-object GET/PUT always hits one shard | Listing a bucket fans out to every shard and merges; prefix queries likewise | Public-cloud shape: single-object access dominates |
| Hash + a separate listing table | Both paths are fast | A second index to maintain; writes become double writes, consistent only eventually | Only when listing really is hot (data-lake scans) |
This chapter is worth far more than "can recite the S3 architecture". The split into small mutable metadata plus large immutable data is the universal shape of modern data infrastructure: a data lake (Iceberg, Delta Lake) is a metadata table over Parquet files in object storage; Kafka's segmented log is the same trick; last chapter's mailbox throwing attachments over the fence was too. Faced with any "huge pile of unstructured data" question, asking "do these bytes ever change?" already gets you half the answer.
8+4's repair amplification hurts enough to justify designing new codes.Huang et al. · Erasure Coding in Windows Azure Storage · USENIX ATC 2012 · publication page/ in a/b/c.jpg is just a character. So "renaming a folder" renames every object underneath it — O(n), not O(1). This is precisely why early big-data jobs writing results straight to S3 were so painfully slow (the commit phase is a rename storm).① Object storage's powers come from a subtraction: give up in-place update and real directories, and you buy unlimited scale, the lowest unit cost and the highest durability.
② The skeleton is data plane / metadata plane separation: immutable bytes in one system, mutable small rows in a database, joined only by a UUID claim ticket.
③ Write order is not negotiable: data first, metadata second. Better an orphan blob (GC handles it) than a dangling pointer (visible but un-fetchable).
④ 100 PB ≈ 25,000 4 TB disks, and the cluster's random IOPS is a fixed budget — every extra hop on a read spends from it.
⑤ Masses of small objects is an architecture problem: append into GB-sized files, locate via UUID → (file, offset, length), and both the inode cost and the extra IOPS disappear.
⑥ Deletes only write tombstones; space returns through background compaction — writes stay sequential and the bill is paid in batches later.
⑦ 8+4 erasure coding: 1.5× space, tolerates any 4 lost chunks — cheaper and safer than three replicas. The cost is repair amplification, read tails and CPU.
⑧ Redundancy cannot stop bit rot: checksum every chunk and scrub in the background, so durability becomes verifiable rather than merely plentiful.
⑨ Sharding by full-path hash protects the overwhelmingly hot single-object GET; the price is that listing a bucket must fan out and merge.
⑩ The two costliest misreadings: eleven nines is not a substitute for backup (the leading cause of loss is accidental deletion), and object storage is not a filesystem (renaming a "folder" is O(n)).