25 — Design An S3-like Object Storage

“Design a service that stores objects: PUT a blob under a key, GET it back, at exabyte scale, and never lose one.”

An object store is a service that keeps arbitrary files — a photograph, a log file, a database backup — and hands them back on demand by name.

This chapter builds one end to end. How to size it. How to hold 200 petabytes of customer data for less than half the price of the obvious approach. Why it flatly refuses to let you edit a stored file in place. And what the industry’s famous “eleven nines of durability” claim really is.

When you finish you should be able to explain, to someone who has never seen the inside of one, why an object store is neither a filesystem nor a database — and why those two refusals are the design rather than limitations of it.

The vocabulary, once, before anything else

Seven words carry the whole chapter. Read them now and the rest of the text stops needing footnotes.

• Object — an immutable lump of bytes. The service never looks inside one, so an object may be a one-byte note or a five-terabyte video.
• Blob — the same idea said informally: binary large object, bytes with no interpretation.
• Key — the string name an object is filed under, such as logs/2026-07-31/web-01.gz.
• Bucket — a named container of keys. It fixes who owns the data and which region holds it.
• PUT, GET, DELETE, LIST — the four operations, named after the HTTP verbs: store an object, fetch it, remove it, enumerate the keys.
• Metadata — the small record describing an object: its name, its size, its fingerprint, and where its bytes physically live. Not the bytes themselves.
• Exabyte scale — the whole corpus is measured in units of 10^18 bytes. That is a thousand petabytes, or a million terabytes.

What goes in and what comes out

The contract fits in four lines, and the whole chapter is the cost of honouring it a hundred billion times over.

In: PUT /photos/cat.jpg with two million bytes in the request body.

Out: an HTTP 200 response carrying an ETag — a short fingerprint of the content, so a client can check that what landed is what it sent — and a VersionId identifying that particular write of that particular key.

Later, in: GET /photos/cat.jpg. Out: those same two million bytes, byte for byte, or any contiguous slice of them the caller asks for.

That is all of it. There is no editing a stored object, no appending to it, and no renaming it.

The one split everything follows from

Almost every candidate opens with “metadata in a database, bytes on disk,” which is right and is where the interview starts, not where it ends. The architecture is one split — a small mutable index and an enormous immutable byte pool — and every hard property in this chapter is a consequence of it.

There are three ways to lose this round.

• Quoting “eleven nines” as though it fell out of an arithmetic model. It did not, and the gap between the model and the claim is the interesting part (8c durability and what eleven nines is a claim about).
• Selling erasure coding as free storage savings. Erasure coding is a way of storing data as fragments plus mathematical parity, so that a few fragments can be lost without losing the data. It is not free; you pay in extra read work, and you have to name that price (8d what you pay the degraded read).
• Offering an interface that lets a caller overwrite a few bytes in the middle of a stored object. That turns out to require a coordinated commit across five machines on every write (9a the arithmetic that forbids it).

Three habits from earlier chapters are used here and not re-derived. You do not need any of them to follow this chapter; each is a place to go for more depth.

• Estimation technique — rounding to one significant figure and carrying units: chapter 02.
• Deciding which machine owns which piece of data — the hash ring of chapter 05, which maps both data and machines onto a circle so that adding a machine moves only a small slice of the data.
• The client-side half of this problem — cutting a file into chunks, syncing devices, deduplicating identical data across users: chapter 15.

1. Framing: what decision, and what breaks

The whole design turns on a single decision: where you spend consistency.

Consistency here means the guarantees that make concurrent writers safe: that operations happen in some agreed order, that a reader sees the latest write, and that two writers racing on the same record cannot both win.

A database sells you those guarantees. It gives you ordered indexes, transactions, and compare-and-swap (CAS) — an atomic “change this value to B, but only if it is still A”, which is how two racing writers are made to produce one winner rather than a mess.

And it charges for them on every single write. Three of those charges come up repeatedly below (sql/03):

• Page cache — a copy of recently touched disk pages held in memory.
• Write-ahead log (WAL) — a sequential journal that every change is appended to before the change is applied, so a crash can be replayed forward.
• MVCC, multi-version concurrency control — each update leaves the old version of a row in place, so that readers already in flight still see a coherent snapshot.

Objects need none of that. Metadata needs all of it. The table below is the same claim, property by property: read down the two right-hand columns and notice that they disagree on every single row.

Six terms in that table are worth pinning down before they are used again.

• Prefix scan — reading every key that starts with a given string, in sorted order. That is what LIST objects under logs/2026-07/ means.
• Shard — one horizontal slice of a dataset with its own machine or machines. You shard when the data no longer fits on, or can no longer be served by, one box.
• Fragment — one of the pieces an object’s bytes are cut into and spread across drives. Defined properly in 8a the overhead arithmetic.
• B-tree — the sorted, balanced on-disk index a relational database uses. A lookup descends a handful of levels; a range query walks the leaves sideways in order.
• Leader-per-shard — one designated machine per slice accepts all writes for that slice. That is what makes an ordering exist at all.
• Extent — a large append-only region of a raw disk. No directories, no file names, just bytes appended at a moving tail.

Say it as one sentence: “0.0135% of the bytes need a database and 99.9865% need an append-only log, so I will run a small expensive consistent store and an enormous cheap one, and every design question is which side of that line something falls on.”

Three things actually break in production. They are listed in frequency order, and each one is the subject of a section later.

• A hot LIST range. A bucket whose keys all begin with today’s date sends the entire write load of the fleet to whichever single shard owns that key range (11b why list cannot be a snapshot).
• A repair storm — the burst of rebuild traffic that fires when a rack of machines comes back after an outage. It issues so many reads that ordinary customer requests are starved of bandwidth (Bottlenecks and scaling).
• Garbage collection racing an upload. The background job that reclaims bytes nothing points at any more deletes a fragment that was about to be referenced (12a orphans and why reference counting loses).

2. Requirements

The framing named what breaks; the requirements fix what the service must promise, and the handful of numbers that every later derivation is measured against.

Functional

Six capabilities, of which the last four are the ones candidates forget and the interviewer is listening for.

• PUT, GET, DELETE an object under (bucket, key); GET supports byte ranges.
• Bucket create/delete; LIST objects by prefix, paginated, in key order.
• Versioning: a PUT over an existing key creates a version; DELETE writes a delete marker.
• Multipart upload for large objects, resumable, with per-part retry.
• Lifecycle policies: transition by age to a colder class, expire noncurrent versions.
• Presigned URLs so the byte path never traverses the customer’s servers.

Five of those terms need unpacking.

• Versioning — a second PUT to the same key does not destroy the first. The old bytes stay, reachable by their version identifier, and the key merely points somewhere new.
• Delete marker — how deletion is expressed in that world. Rather than erasing anything, a DELETE appends a new version saying “as of here, this key reads as absent”. That is why undelete is possible.
• Multipart upload — a client cuts a huge object into numbered parts, uploads them independently and in parallel, retries any single part that fails, then declares the set complete. It is the only way a five-terabyte upload survives a network that drops connections.
• Lifecycle policy — a standing rule the service applies on the customer’s behalf, such as “after 30 days move this to cheaper, slower storage”. Colder is the industry’s word for that cheaper class: cheap to keep, expensive to read.
• Presigned URL — a link the service signs in advance, granting a specific operation on a specific key for a limited time. A browser can then upload straight into the store, and the customer’s own servers never have to carry the bytes.

Out of scope, said out loud: POSIX semantics, server-side search over object contents, and cross-region replication. POSIX is the Unix file interface — the one that lets you rename a file, append to the end of it, or overwrite a few bytes in the middle. Refusing it is the interesting one of the three, because refusing it is exactly what makes everything else in this chapter possible.

Non-functional — the rows that decide everything below

Two words get confused constantly, and the difference is the first row of the table below.

Durability is the probability that data you successfully stored is still readable later. Availability is the probability that the service answers a request right now.

They are different failures. An unavailable object comes back when the service recovers; a non-durable one never comes back at all. Say which one you are quoting.

Two terms from that table, since both recur:

• “Eleven nines” is shorthand for a durability of 99.999999999%, that is, an annual loss probability of 1e-11. Each additional nine is another factor of ten less likely.
• Read-after-write is the guarantee that once a write has been acknowledged, a subsequent read returns it rather than the older state. It is the property that stops a user from uploading a file and immediately being told it does not exist.

3. Back of the envelope

Those requirements only become arguable once they are numbers: how many bytes, how fast they arrive and leave, what the drives cost, and how much of the corpus is metadata. Six or seven figures come out of this section, and the rest of the chapter argues about them.

3a. Bytes, rates, and what the media costs

Start with the byte pool and the drives under it, because pricing them produces the single largest number in the chapter.

Two words for direction of traffic, because they are used throughout: ingest is data flowing into the service (PUTs), egress is data flowing out of it (GETs).

Rates are quoted in bits per second (Gbps, gigabits per second) because that is how network links are sold. Capacity is quoted in bytes (TB = 10^12, PB = 10^15). That mismatch is why factors of eight keep appearing: every conversion from a byte rate to a link rate multiplies by 8.

The block below starts from four assumptions and derives five numbers. The one to watch is the last line — the price of a petabyte of raw drive for a month, which every dollar figure in the chapter is built from.

assume  100,000,000,000 objects, 2 MB average,
        1,000 PUT/s and 10,000 GET/s averaged over the day, peak 3x,
        all-in cost of raw drive capacity $0.01 per GB-month

logical bytes
  100,000,000,000 x 2,000,000            =  200,000,000,000,000,000
the same, in PB
  200,000,000,000,000,000 / 1,000,000,000,000,000  =  200
ingest, B/s
  1,000 x 2,000,000                      =  2,000,000,000
ingest, Gbps
  2,000,000,000 x 8 / 1,000,000,000      =  16
egress, B/s
  10,000 x 2,000,000                     =  20,000,000,000
egress, Gbps
  20,000,000,000 x 8 / 1,000,000,000     =  160
egress at peak, Gbps
  160 x 3                                =  480
raw capacity, $/PB-month
  0.01 x 1,000,000                       =  10,000

Now price the obvious way to survive a dead drive: keep whole extra copies. Three copies is the industry default, because three copies survive two simultaneous losses. That is called replication factor 3, written RF 3.

Three replicas of 200 PB is 600 PB of media, at 600 x 10,000 = $6,000,000 per month. Over a year that is 6,000,000 x 12 = $72,000,000.

That single line is why this chapter is mostly about erasure coding: nothing else in the design has a $72 M/year lever attached to it.

3b. Metadata, and the ratio that licenses the whole architecture

Now measure the descriptive records against the bytes they describe. The ratio that falls out is what permits an expensive database on one side of the split.

Each object needs one small row recording its name, size, fingerprint and location. Adding those fields up gives the row width in bytes; the row width times the object count gives the whole metadata corpus.

The index and row overhead 100 line is not padding — a database stores more than your columns: page headers, per-row version stamps, and the index entries that make the row findable.

metadata row: bucket_id 8 + key 100 + version_id 16 + size 8 + etag 16
              + created_at 8 + storage_class 2 + placement_id 8 + flags 4
              + index and row overhead 100
  8 + 100 + 16 + 8 + 16 + 8 + 2 + 8 + 4 + 100  =  270
metadata bytes
  100,000,000,000 x 270                  =  27,000,000,000,000
in TB
  27,000,000,000,000 / 1,000,000,000,000 =  27
metadata as a share of the corpus
  27,000,000,000,000 / 200,000,000,000,000,000  =  0.000135

27 TB against 200 PB — 0.0135%.

That is small enough to shard across a few hundred boxes, replicate it three ways, run a leader per shard, and take linearizable reads on it — all without thinking about the bill. Linearizable means a read is guaranteed to observe every write that was acknowledged before the read started, as if all operations happened one at a time in a single global order. It is the strongest and most expensive thing a distributed store can promise, and 0.0135% of the corpus is small enough to afford it.

That ratio is the permission slip for everything in Deep dive 1 why metadata needs a database and bytes do not.

4. API sketch

With the numbers fixed, write out the API — the application programming interface, the exact set of calls a client is allowed to make. Four choices in it are the ones a candidate is most likely to get wrong.

The sketch below has three groups: the everyday single-object calls on top, the multipart upload sequence in the middle, and bucket configuration at the bottom. Notice what is missing from the first group — there is no verb for changing part of an existing object.

PUT    /{bucket}/{key}                       -> 200 {ETag, VersionId}
GET    /{bucket}/{key}[?versionId=]          -> bytes; honours Range:
HEAD   /{bucket}/{key}                       -> metadata only, no byte path
DELETE /{bucket}/{key}[?versionId=]          -> writes a delete marker
GET    /{bucket}?list-type=2&prefix=&continuation-token=&max-keys=1000

POST   /{bucket}/{key}?uploads               -> {UploadId}
PUT    /{bucket}/{key}?partNumber=N&uploadId=  -> {ETag}
POST   /{bucket}/{key}?uploadId=             -> complete; body lists (N, ETag)
DELETE /{bucket}/{key}?uploadId=             -> abort

PUT    /{bucket}?lifecycle                   -> transition and expiry rules

Three pieces of HTTP vocabulary in that sketch:

• HEAD — the verb that asks for a response’s headers without its body. It returns an object’s metadata and never touches the bytes.
• Range: — a request header asking for a contiguous slice of an object rather than all of it.
• continuation-token — an opaque cursor the server hands back with each LIST page, so the next call resumes exactly where the last one stopped.

Four choices in that sketch are deliberate, and each is defended later at length.

• There is no PATCH and no append. 9a the arithmetic that forbids it derives why: updating bytes inside a stored object requires an all-or-nothing commit across five machines, and — worse — it cannot be made idempotent, meaning a retried request would not be harmless the second time.
• DELETE is a write. It appends a delete marker rather than removing rows, so delete is as recoverable as any other version and costs the same 270-byte row.
• Range is first-class, and it is the reason coding is applied per stripe unit rather than per object (8d what you pay the degraded read). A range read of a healthy object touches one node.
• Multipart’s complete is the linearization point — the single instant at which the operation counts as having happened, before which no reader sees anything and after which every reader does. Parts are durable bytes with no name; the object exists at the moment one metadata row commits. That is the same two-store ordering as Deep dive 6 two stores one commit, where bytes are made durable first and a single small commit publishes them, and for the same reason.

5. Data model

Behind that API sit six tables in the metadata store, and three modelling choices in them that everything downstream depends on.

Read the schema below looking for one thing: objects is the only table with a row per object, and it is 270 bytes wide. Everything else is a small side table shared by many objects.

buckets    bucket_id PK, name UNIQUE, owner_id, region, versioning_state,
           created_at, lifecycle_rules JSON

objects    (bucket_id, key, version_id DESC) PRIMARY KEY   -- range-partitioned
           size, etag, content_type, storage_class,
           is_delete_marker BOOL, placement_id, extent_id, extent_offset

placement  placement_id PK, code ('RS_10_4' | 'RF_3'), generation,
           node_ids[k + m]                                 -- rack-diverse

extents    extent_id PK, placement_id, sealed BOOL, bytes_used, created_at

uploads    upload_id PK, bucket_id, key, created_at, storage_class
parts      (upload_id, part_number) PK, etag, size, extent_id, extent_offset

Three pieces of notation in that schema:

• PK marks a table’s primary key — the column or columns that uniquely identify a row, and by which the table is physically sorted on disk.
• Placement is the choice of which specific machines hold a given object’s fragments. It is stored once per group of objects rather than once per object, because a list of 14 node identifiers is far too bulky to repeat a hundred billion times.
• Sealed means an extent has been closed to further appends. A sealed extent is safe to encode, and is never written to again.

Three things are worth defending.

The primary key is sorted, and that sort order is the LIST index. (bucket_id, key) ascending with version_id descending means a prefix scan is a range scan and the current version of each key is the first row in its group. There is no second index to keep consistent, which matters because the second index is what would have to be transactional.

The objects table is range-partitioned, not hash-partitioned. The two differ in where neighbouring keys land. Range partitioning gives each shard a contiguous slice of the key order, so a/1 and a/2 sit on the same machine. Hash partitioning scatters keys by their hash, so those two land anywhere.

Ordered LIST requires range partitioning. That choice imports a hot-shard problem — one shard taking a disproportionate share of the load — that the scattering approach does not have (sql/03). 11b why list cannot be a snapshot prices it at 300x.

extents exist so that small objects are not coded individually. An object row points at an offset inside a sealed extent, and the extent — not the object — carries the placement.

The reason that matters is allocation granularity. A block is the smallest unit of space a drive will hand out, here 4,096 bytes, so anything smaller than a block still consumes a whole one. Below k x block = 10 x 4,096 = 40 KB, an object cannot fill even one block per fragment, which 8e small objects and the 40 kb line prices.

6. High-level architecture

Data model in hand, the whole machine fits in one diagram.

The diagram has two halves. The top half — client, frontend, metadata, placement, data nodes — is the request path, the machines a customer waits on. The four boxes hanging off the bottom (scrubber, repair, GC, lifecycle mover) are background loops that no customer ever waits for. Colour marks the two stores of Framing what decision and what breaks: blue is the metadata database, green is the byte pool.

flowchart TD
    C["Client / SDK"] -->|"PUT, GET, LIST"| FE["Frontend<br/>auth, presigning, ranges"]
    FE -->|"row read/write, CAS"| MD[("Metadata service<br/>range-partitioned on bucket+key<br/>leader per shard")]
    FE -->|"pick a placement"| PL["Placement service<br/>rack-diverse node sets"]
    FE -->|"k+m fragment writes"| DN["Data nodes<br/>append-only extents"]
    FE -->|"k fragment reads"| DN
    DN --> DR[("Bare drives<br/>no filesystem tree, no RMW")]
    SCR["Scrubber<br/>CRC every fragment"] --> DN
    REP["Repair<br/>declustered rebuild"] --> DN
    GC["Mark and sweep GC<br/>weekly"] --> DN
    GC --> MD
    LC["Lifecycle mover<br/>age -> colder class"] --> MD
    LC --> DN

    style MD fill:#1d3557,color:#fff
    style DN fill:#2d6a4f,color:#fff
    style GC fill:#9d0208,color:#fff
    style REP fill:#bc6c25,color:#fff

The request path, box by box

Follow one PUT through the diagram from the top.

1. The client. The top box is the client SDK, the software development kit — the vendor-supplied library that speaks the service’s protocol. A plain browser or curl works just as well. It issues one of the four operations: PUT, GET, LIST or DELETE.

2. The frontend. The request arrives at a stateless tier with exactly three jobs, which is why its box reads auth, presigning, ranges.

• Auth checks the caller’s signature and that they are permitted this operation.
• Presigning mints the time-limited signed links described in Requirements.
• Ranges translates a byte range the caller asked for into offsets inside fragments.

3. The metadata service. The frontend does one small row read or write against it. When it must move the current-version pointer safely it uses the compare-and-swap of Framing what decision and what breaks. The service is range-partitioned on bucket+key with a leader per shard, exactly as Data model modelled it.

4. The placement service. To store bytes, the frontend asks for a placement: a set of k + m machines chosen to be rack-diverse, meaning spread across independent racks so that one rack losing power cannot take out more fragments than the code can survive.

5. The data nodes. The frontend writes k + m fragments, and each data node appends its fragment into an extent on a bare drive — a raw block device with no filesystem tree above it and no RMW, no read-modify-write. Nothing on a data node ever reads a byte back in order to change it.

A GET runs the same path backwards: k fragment reads, decoded at the frontend.

The four background loops

None of these is on the request path, and none of them appears in most candidates’ diagrams.

• Scrubber — re-reads stored fragments and checks each one’s CRC, its cyclic redundancy check. A CRC is a short checksum stored beside the data, whose job is to detect a drive that silently returned the wrong bytes (12b scrubbing the errors that are certain rather than probable).
• Repair — performs a declustered rebuild, regenerating fragments lost with a dead drive by spreading the work across the whole fleet (8b the repair window derived from bandwidth).
• Garbage collector — runs weekly in two phases. Mark asks the metadata which fragments are still referenced; sweep deletes the ones nothing pointed at (12a orphans and why reference counting loses).
• Lifecycle mover — the policy engine that shifts objects by age to a colder class, updating metadata and data nodes together (12c lifecycle and tiering).

Scrub, repair and GC are the parts nobody draws and every incident review mentions.

The one choice in the diagram that matters

The frontend, not the data node, does the coding.

That is the load-bearing decision. The data node is a dumb append-only store: it never reads what it wrote, never computes parity, and never talks to another data node on the write path.

Every distributed-systems problem in the byte path is therefore pushed into a stateless tier you can restart at will.

7. Deep dive 1: why metadata needs a database and bytes do not

The split of Framing what decision and what breaks has so far been asserted; it deserves a defense operation by operation, and a price on getting it wrong in either direction.

Take the operations one at a time and ask what each one requires. The first three rows below are metadata questions and every one of them needs a database feature; the last two are byte questions and neither needs anything more than an offset.

pread and pwrite are the two Unix system calls that read and write at an explicit byte offset — the cheapest operations an operating system offers on storage, one instruction’s worth of intent with no index, no lock and no transaction behind them.

The right column is the argument. The byte path never sorts, never scans a range, never needs isolation between two writers (there is only ever one writer per extent offset), and never updates in place.

So everything a database charges for is pure overhead on this workload: MVCC version chains, the page cache, the query planner, and the fsync of the write-ahead log before a commit is acknowledged. fsync is the call that forces the operating system to push buffered data all the way onto physical media and wait for the drive to confirm — the slowest thing a database routinely does (Transactions acid precisely).

Pricing the mistake

Suppose you stored 2 MB objects as rows in a relational table. Every PUT then writes 2 MB into the write-ahead log and then 2 MB again into the table’s own pages, so the physical write is twice the logical one. That ratio is called write amplification, and here it is exactly 2:

WAL amplification for a 2 MB row write, bytes
  2,000,000 x 2                          =  4,000,000
ingest into the WAL at 1,000 PUT/s, B/s
  1,000 x 4,000,000                      =  4,000,000,000
as a multiple of a 1 GB/s sequential NVMe device
  4,000,000,000 / 1,000,000,000          =  4

An NVMe device is a solid-state drive attached directly to the machine’s high-speed expansion bus — the fastest storage you can buy per unit. A good one sustains roughly 1 GB/s of sequential writes.

The payload those writes are carrying is 1,000 PUT/s x 2,000,000 bytes = 2,000,000,000 bytes/s, or 2 GB/s. So: four NVMe devices saturated with pure sequential writes, every second, to store 2 GB/s of payload — and you have bought nothing with it, because the workload uses none of the database features you paid for.

Now the other side of the split, for the same second. The metadata for those 1,000 PUTs is 1,000 x 270 = 270,000 bytes, which against a 1 GB/s device is 270,000 / 1,000,000,000 = 0.00027, or 0.027% of one device. That contrast — four saturated devices against a third of a thousandth of one — is the whole section.

The converse mistake

Putting the metadata in the object store is just as wrong, and worth naming out loud. Then LIST is a directory walk, compare-and-swap does not exist, and the “current version” pointer has no home.

Object stores are not databases in exactly the way databases are not object stores.

8. Deep dive 2: erasure coding, derived

Here is the lever attached to 3a bytes rates and what the media costs’s $72 M/year line. What erasure coding is, how much storage it saves, how fast a lost drive can be rebuilt, and what durability follows all chain together — each derivation uses the number the previous one produced — and then two bills arrive: a worse latency tail, and a floor on object size.

8a. The overhead arithmetic

Erasure coding starts from one idea: you do not need whole spare copies of data in order to survive losing some of it.

Instead you cut the data into pieces, compute some extra pieces from them by arithmetic, scatter all the pieces across different drives, and arrange matters so that any sufficiently large subset of the pieces is enough to rebuild the original.

Two names for the parts:

• Parity — the extra computed pieces. They hold no plaintext of their own, only the results of equations over the data pieces. Their job is to let you solve for whichever pieces went missing.
• Stripe and fragment — a stripe is the set of pieces belonging to one encoded unit; a fragment is one individual piece.

Reed-Solomon, written RS(k, m), is the standard construction. It splits an object into k data fragments, computes m parity fragments over them, and stores all k + m on distinct drives.

Any k of the k + m reconstruct the original. Any k at all — not a privileged subset. That is the property that makes the scheme usable, and it is exactly what the code in 8f working code is built to demonstrate.

So RS(10,4) means ten data fragments, four parity fragments, fourteen drives, and survival of any four simultaneous losses.

Two consequences follow immediately. Storage overhead below means physical bytes stored per logical byte of customer data: divide the fragments you keep by the fragments that carry real data.

storage overhead, RS(6,3)
  (6 + 3) / 6                            =  1.5
storage overhead, RS(10,4)
  (10 + 4) / 10                          =  1.4
failures tolerated                                       m

Now apply each scheme to the 200 PB corpus of 3a bytes rates and what the media costs. Each row multiplies 200 PB by the overhead to get physical bytes, prices those at the $10,000/PB-month from §3a, and divides by a 16 TB drive to get a fleet size. Read the bottom row against the top one — it is better in every column.

physical at RF 3, PB
  200 x 3                                =  600
physical at RS(10,4), PB
  200 x 1.4                              =  280
saving, PB
  600 - 280                              =  320
saving, $/year
  (6,000,000 - 2,800,000) x 12           =  38,400,000
drives no longer bought
  37,500 - 17,500                        =  20,000

RS(10,4) stores less than half the media of triple replication and tolerates two more simultaneous failures.

That is not a tradeoff, it is a dominance. If the chapter stopped here nobody would ever replicate anything. 8d what you pay the degraded read and 8e small objects and the 40 kb line are where the bill actually arrives.

8b. The repair window, derived from bandwidth

Savings banked, the first operational question: when a drive dies, how long does a stripe spend one fragment short? Every durability figure in the next subsection is a function of that one duration.

A stripe missing one or more fragments is degraded: still readable, because k survivors are enough, but with less margin than it was designed for.

The time between a drive dying and the missing fragment being regenerated elsewhere is the repair window. It matters because a second failure inside that window is what actually loses data — outside it, the stripe is back to full strength and nothing is at risk.

So derive the window from bandwidth rather than assuming a comfortable number. Start with the naive version: one dead 16 TB drive, one replacement machine, one network card.

capacity of one drive, bytes                             16,000,000,000,000
rebuild onto a single replacement node at 1 Gbps, seconds
  16,000,000,000,000 x 8 / 1,000,000,000 =  128,000
in hours
  128,000 / 3,600                        =  35.6

Thirty-six hours is a catastrophic repair window, and it is what naive placement gives you. The reason is the funnel: a dedicated spare node has one network interface card (NIC) at 1 Gbps, and every rebuilt byte has to squeeze through it.

The fix is declustering. Rather than giving each drive a fixed partner that inherits all its work, spread the failed drive’s stripes across the whole pool. Every node in the fleet then contributes a slice of the rebuild, and no single node is the funnel.

Redo the arithmetic with 200 nodes each lending a tenth of their card:

nodes lending bandwidth to the rebuild                   200
share of each 1 Gbps NIC given to repair                 0.10
aggregate rebuild bandwidth, bits/s
  200 x 1,000,000,000 x 0.10             =  20,000,000,000
rebuild time, seconds
  16,000,000,000,000 x 8 / 20,000,000,000  =  6,400
in hours
  6,400 / 3,600                          =  1.78

The 0.10 in that block is a deliberate cap: repair is allowed one tenth of each machine’s network card, and the other nine tenths stay reserved for customers. Add failure detection and scheduling to the 1.78 hours and call the repair window 2 hours. That number is used unchanged for the rest of the chapter.

Repair amplification, the cost hiding in that block

To regenerate a single lost fragment, the repair job must read k surviving fragments and solve for the missing one. Under RS(10,4) it therefore moves ten bytes of network traffic for every one byte it lost.

That ratio is repair amplification, and at 10x it is why the 10% bandwidth cap is a real engineering constraint rather than a formality: uncapped repair would out-consume the customers it exists to protect.

Replication has a repair amplification of 1 — you copy the lost bytes and nothing more. That is the quiet advantage the storage table in 8a the overhead arithmetic does not show. The same “you move more than you lost” accounting appears in Deep dive 1 what block level sync actually saves.

8c. Durability, and what “eleven nines” is a claim about

With a repair window in hand, a probability model for losing a stripe can be built — and it produces a far larger number than any operator advertises. The gap is the actual interview question.

The one input, and the probability it produces

The model needs one number from the drive vendor. The annualized failure rate (AFR) is the fraction of drives in a fleet that die in a year. 2% is a normal published figure — one drive in fifty, per year.

Combine the AFR with the 2-hour repair window and you can ask the only question that matters: what is the chance that enough additional drives holding fragments of the same stripe die before the first loss is repaired?

A year is 8,760 hours, so a 2-hour window is a small slice of one. The arithmetic starts by working out how small, then scaling the AFR down by that slice.

assume  a per-drive annualized failure rate of 2%, and the 2-hour
        repair window from 8b

repair window as a fraction of a year
  2 / 8,760                              =  0.00022831
p, one drive dies inside one repair window
  0.02 x 0.00022831                      =  0.0000045662

So p = 4.566e-6: given some moment in the year, the chance that any one specific drive dies inside a particular 2-hour window is about four and a half in a million.

The formula

A stripe is lost when a first drive fails and then enough of the survivors also fail before repair completes. Written out, with n fragments per stripe and j further failures needed to lose it:

annual loss per stripe  =  n x AFR  x  C(n-1, j)  x  p^j
                           ^^^^^^^     ^^^^^^^^^     ^^^
                           any of the  ways to pick  each of
                           n drives    j unlucky     them dies
                           dies first  survivors     in-window

C(n, j) is the binomial coefficient: the number of ways to choose j items out of n without regard to order. C(13, 4) = 715 means there are 715 different four-drive subsets of thirteen survivors, and any one of them dying is enough to lose the stripe — which is why a wider code is not automatically safer.

One presentation trick in the next block. To keep the numbers readable, p is written in units of 1e-6, so p = 4.566 stands for 4.566e-6. A product of j such factors therefore carries a scale of 1e-6 raised to the power j — which is why the RF 3 result is labelled 1e-12 (two factors) and the RS(10,4) result 1e-24 (four factors).

3x replication -- both survivors gone inside the window
first failure, per replica-set-year
  3 x 0.02                               =  0.06
both survivors, and there is C(2,2) = 1 way for that to happen
  4.566 ^ 2                              =  20.85
scaled product, in units of 1e-12
  0.06 x 20.85                           =  1.251

RS(10,4) -- four more of thirteen gone inside the window
first failure, per stripe-year
  14 x 0.02                              =  0.28
ways to choose four of the thirteen survivors, C(13,4)
  715
each of those four dying inside the window
  4.566 ^ 4                              =  434.6
scaled product, in units of 1e-24
  0.28 x 715 x 434.6                     =  87,007

The same formula run for all three schemes, with the RS(6,3) row using n = 9, j = 3 and C(8,3) = 56:

The “nines” column is just the loss probability restated. A probability of 1e-11 is eleven nines, and in general the count of nines is -log10(annual loss probability). So 1.251e-12 is 11.9 nines and 8.70e-20 is 19.1.

The independence model says RS(10,4) delivers nineteen nines. Every operator that runs it advertises eleven. The eight-order-of-magnitude gap is the answer to the question.

First, eleven nines is a statement about scale

Run the advertised figure against this corpus and see what it actually promises:

objects
  100,000,000,000
expected objects lost per year at 11 nines
  100,000,000,000 x 0.00000000001        =  1

One object per year, in expectation. That is why the number is quoted per-object-per-year and never as a probability the customer experiences.

Second, it is a statement about correlation

The arithmetic above assumes independence in exactly one place: writing p^4. Multiplying p by itself four times is only legitimate if the four failures are independent — if one drive dying tells you nothing at all about whether another will.

In a real datacenter they frequently are not. Drives share power, cooling, network switches, manufacturing batches and software. The table below lists the five ways that assumption breaks, and what you do about each.

Three pieces of datacenter vocabulary from that table:

• Rack — a physical cabinet of perhaps forty machines.
• PDU — its power distribution unit, the strip that feeds all of them.
• ToR switch — the top-of-rack switch that carries all their network traffic.

Each is a shared component whose failure takes the whole rack with it, which is precisely the correlation the model ignored.

Pricing the rack case

The rack row is the one with a clean number, so do that one properly.

Suppose all 14 fragments sit in one rack, and a rack has a 1-in-1,000 chance per year of an outage longer than the repair window. Then the rack outage is the stripe loss, so the stripe’s annual loss probability is 0.001 — three nines, not nineteen.

Placement diversity is therefore worth sixteen orders of magnitude, and it costs exactly one constraint in the placement service: no rack holds more than m fragments.

Work out what that constraint implies. With m = 4, a stripe of 14 fragments must span at least ceil(14 / 4) = 4 racks. In practice you use 7 racks, which puts 14 / 7 = 2 fragments in each — so two entire racks can be down and the stripe is still only 2 x 2 = 4 fragments short, exactly what m = 4 tolerates.

Say this out loud: “eleven nines is not the output of my model — my model says nineteen. Eleven is nineteen minus a correlated-failure haircut nobody can compute from first principles, rounded down to a number the operator is willing to defend.”

8d. What you pay: the degraded read

Now the first of the two bills: a read that must gather k pieces is as slow as the slowest of them, so the tail latency gets much worse. It can be bought back, at a price worth knowing.

The Reed-Solomon construction used here is systematic, meaning the k data fragments are literally the object itself cut into k consecutive pieces, with the parity added alongside rather than replacing it.

That property decides how many nodes each kind of read touches:

• A healthy range read touches one node — the one holding the piece that covers the range. No decoding is needed when the plaintext is right there.
• A healthy full-object read touches k, because it wants all k pieces.
• A degraded read touches k no matter how few bytes were asked for. A read is degraded when a data fragment the caller needs is unavailable — its drive is dead, or just slow — so the frontend must fetch k fragments from k different nodes and solve the equations to reconstruct the missing one.

The rest of this subsection is about what that third case does to latency. Start with what one fragment fetch costs:

per-fragment fetch: 500 us datacenter round trip + 100 us SSD random read
  500 + 100                              =  600
assume  the per-fragment distribution has p50 600 us, p99 10 ms, p99.9 50 ms

Those p numbers are percentiles of the latency distribution. p50 is the median, the time half of fetches beat. p99 is the time 99% of fetches beat, so one fetch in a hundred is slower. p99.9 is the one-in-a-thousand figure. Percentiles rather than averages, because a user experiences slow requests individually and an average hides them.

The 600-microsecond floor comes from the hardware costs in ch 02: a round trip across the datacenter plus one random read from a solid-state drive. The long tail above it comes from queueing behind other work, retransmitted network packets, and drives that are simply having a bad day.

Why needing k fragments wrecks the tail

A full-object read is only done when its slowest fragment arrives. So the object’s latency is the maximum of k draws from that distribution, not one draw — and the maximum of ten draws is much worse than one.

The arithmetic below assumes the ten fetches are independent, which is why 99% raised to the tenth power is the chance that all ten land inside the per-fragment p99:

probability all 10 fragments arrive within the per-fragment p99
  0.99 ^ 10                              =  0.904
share of full-object GETs that exceed it
  1 - 0.904                              =  0.096
per-fragment quantile needed so that 99% of objects clear it
  0.99 ^ 0.1                             =  0.9990

Read the last line as an inverted requirement. To give the object a 99th-percentile guarantee, each individual fragment fetch must now hit its own 99.9th percentile, because 0.999 raised to the tenth power is what leaves 99% of objects clear.

So: ten percent of erasure-coded object reads are slower than the per-fragment p99, and the object’s p99 is the fragment’s p99.9 — 50 ms instead of 10 ms, a 5x tail regression, for a change that was sold as a storage optimization.

A replicated read issues one fetch and inherits the fragment tail unchanged. That is the advantage the storage table in 8a the overhead arithmetic hides.

Buying the tail back with hedging

Hedging means asking for more copies of the work than you need and using whichever answers arrive first, so one slow responder is ignored rather than waited for.

Here the redundancy is already paid for — it is sitting in the parity fragments. Request k + 2 fragments and decode from whichever k arrive first. The probability that at least 10 of 12 land inside the per-fragment p99 is a binomial sum, and it is far closer to 1 than the 0.904 above:

requests issued
  10 + 2                                 =  12
probability at least 10 of the 12 land inside the per-fragment p99
  0.999794
share of GETs that exceed it
  1 - 0.999794                           =  0.000206
extra read bandwidth
  12 / 10                                =  1.2

Sweeping the number of extra fragments requested shows how fast the tail collapses. The first row is the unhedged case from above; each further row costs 10% more read bandwidth.

Twenty percent more read bandwidth buys back the entire tail regression and then some. The object’s p99 returns to the fragment’s p99, and its p99.9 is better than a single replicated read’s.

This is the same hedging a replicated store gets for free by having three copies. Erasure coding makes you buy it explicitly — and the fact that you can is the strongest argument for m >= 2.

What does not get worse: bytes moved

Reconstructing a 4 KB range needs the same 4 KB offset from k fragments, not the whole object.

The reason is that the code operates symbol-wise: each byte position is its own independent little system of equations, so byte 500 of the original is recovered from byte 500 of the survivors and nothing else.

So a degraded range read moves 10 x 4,096 = 40,960 bytes, not 2 MB. What it does spend is 10 IOPS — input/output operations per second, the count of separate seek-and-read requests a drive is asked to perform. On a spinning disk IOPS is a far scarcer resource than bandwidth, which is the thread 8e small objects and the 40 kb line picks up.

8e. Small objects, and the 40 KB line

The second bill arrives at the small end of the object-size range: below a threshold that the code parameters themselves determine, splitting an object into fourteen pieces costs far more than keeping three whole copies of it.

The culprit is allocation. Drives do not hand out space by the byte — they allocate in blocks, here 4,096 bytes, and a fragment of 50 bytes still occupies a whole block.

So below some object size the k + m fragments cannot each fill a block. Every fragment then wastes most of one, and the nominal 1.4x overhead becomes a fiction.

The block below finds that size. The break-even line sets the physical cost of the floor case, (k+m) x block, equal to what the nominal overhead claims an object of size S should cost, ((k+m)/k) x S, and solves for S. The (k+m) cancels, leaving S = k x block.

allocation granularity on a data node, bytes             4,096
fragments per stripe under RS(10,4)
  10 + 4                                 =  14
physical bytes for an object too small to fill a fragment
  14 x 4,096                             =  57,344
break-even: (k+m) x block = ((k+m)/k) x S, so S = k x block
  10 x 4,096                             =  40,960

Below 40 KB, coding an object individually costs more than its nominal overhead. By 4 KB it costs 57,344 / 4,096 = 14x — and 14x is 14 / 3 = 4.7, nearly five times worse than the triple replication it was supposed to beat.

It also spends 14 IOPS to write and 10 to read something that should have been one of each.

The fix: pack, then code the extent

Rather than encoding each tiny object on its own, append many of them into a 1 GB extent, seal the extent, and erasure-code the extent as a unit.

Thousands of small objects then share one stripe and one placement, and every fragment is enormous — 100 MB rather than 50 bytes. The object’s row carries (extent_id, offset, length), so a small-object GET is still one range read on one node in the healthy case.

The threshold is k x block. It is not a tuning knob, and it moves whenever the code parameters or the block size do.

The IOPS line behind the storage line

Packing is not optional, and the reason is seeks rather than bytes.

A spindle here means one spinning hard drive. A spinning drive sustains only about 100 separate random reads per second, no matter how few bytes each one asks for, because the arm has to physically move (ch 02).

Count the seeks the current workload needs. Under RS(10,4) with k+2 hedging, 10,000 full-object GET/s become 10,000 x 12 = 120,000 fragment reads/s, which at 100 IOPS per spindle is 120,000 / 100 = 1,200 spindles. Capacity already demands 17,500, so capacity binds by 17,500 / 1,200 = 15x and IOPS is not a consideration.

Now shrink the average object 10x, to 200 KB. The same 20 GB/s of bytes now arrives as 100,000 GET/s, so IOPS demands 100,000 x 12 / 100 = 12,000 spindles against the same 17,500 that capacity wants. The 15x headroom is gone — and at the 3x peak of 3a bytes rates and what the media costs, 3 x 12,000 = 36,000 spindles, so the fleet is now sized by seek rate rather than terabytes.

That is the real reason production systems pack: not the 40 KB storage line, the IOPS line behind it.

8f. Working code

The “any k fragments will do” property is easy to claim and easy to get subtly wrong, so here it is made concrete: a complete, runnable Reed-Solomon encoder and decoder.

Three ideas make the code readable.

First, the arithmetic does not happen in ordinary integers. Reed-Solomon works over a finite field: a number system with a fixed, finite set of elements in which addition, subtraction, multiplication and division all behave the way you expect and never overflow.

GF(256), the Galois field of 256 elements, is the one everybody uses, because each element is exactly one byte. Addition in it is bitwise exclusive-or — which is why the code below has no minus signs anywhere.

Multiplication is done by table lookup. Pick a field polynomial (here 0x11D) that defines how products wrap around, find a generator — an element whose successive powers cycle through every non-zero element of the field — and you can build logarithm and exponent tables that turn multiplication into addition of logs, exactly as slide rules once did for real numbers.

Second, encoding is a matrix multiplication. The m parity fragments are m different weighted combinations of the k data fragments, so the whole code is described by an m x k matrix of coefficients. Decoding is then solving the resulting linear system by Gauss-Jordan elimination, the standard textbook procedure of eliminating one unknown at a time.

Third, the choice of matrix is the whole correctness argument. “Any k fragments reconstruct the object” is the statement that every k x k submatrix you could be left with is invertible.

A Cauchy matrix, whose entries are 1 / (x_i + y_j) for two disjoint sets of field elements, has that property for every square submatrix by construction. A Vandermonde matrix, the other common choice, does not have it in general once stacked under an identity — it works for most subsets of survivors and fails for some.

Four things to look at in the code below: loss_prob is the durability formula of 8c durability and what eleven nines is a claim about in three lines; the two for _i loops build the log and exponent tables; cauchy is the matrix that makes “any k” true; and the assert at the bottom deletes three data fragments and one parity fragment and still recovers the original bytes.

"""RS(k,m) over GF(256), plus the durability model of 8c. Any k of the
k+m fragments reconstruct the object -- for EVERY k-subset, not just the
convenient ones, which is what the Cauchy construction below buys."""
from math import comb, log10

AFR, HOURS, WINDOW = 0.02, 8_760, 2.0     # 8c inputs, 8b window


def loss_prob(n, tolerated):
    """One drive fails, then `tolerated` more before repair finishes.
    Independence assumed -- the assumption 8c spends a table attacking."""
    p = AFR * WINDOW / HOURS
    return n * AFR * comb(n - 1, tolerated) * p ** tolerated


# Polynomial 0x11d, for which 2 is a generator. AES's 0x11b is NOT usable:
# 2 has order 51 there, so the log table is not a bijection and every
# inverse is wrong -- silently, as corrupted decodes rather than an error.
EXP, LOG, _x = [0] * 512, [0] * 256, 1
for _i in range(255):
    EXP[_i], LOG[_x] = _x, _i
    _x = (_x << 1) ^ (0x11D if _x & 0x80 else 0)
for _i in range(255, 512):
    EXP[_i] = EXP[_i - 255]

gmul = lambda a, b: 0 if a == 0 or b == 0 else EXP[LOG[a] + LOG[b]]
gdiv = lambda a, b: 0 if a == 0 else EXP[LOG[a] - LOG[b] + 255]
# Cauchy: every square submatrix is invertible. That IS the "any k" property.
cauchy = lambda k, m: [[gdiv(1, i ^ (m + j)) for j in range(k)]
                       for i in range(m)]


def encode(data, k, m):
    """data: k equal-length byte strings -> k data + m parity fragments."""
    out = list(data)
    for row in cauchy(k, m):
        par = bytearray(len(data[0]))
        for j in range(k):
            for b, byte in enumerate(data[j]):
                par[b] ^= gmul(row[j], byte)
        out.append(bytes(par))
    return out


def _solve(rows, rhs):
    """Gauss-Jordan over GF(256); addition is XOR, so there are no signs."""
    k = len(rows)
    a = [list(r) + [rhs[i]] for i, r in enumerate(rows)]
    for c in range(k):
        piv = next(r for r in range(c, k) if a[r][c])
        a[c], a[piv] = a[piv], a[c]
        inv = gdiv(1, a[c][c])
        a[c] = [gmul(v, inv) for v in a[c]]
        for r in range(k):
            if r != c and a[r][c]:
                f = a[r][c]
                a[r] = [v ^ gmul(f, a[c][i]) for i, v in enumerate(a[r])]
    return [row[k] for row in a]


def decode(frags, have, k, m):
    """`have`: any k surviving fragment indices, in increasing order."""
    par = cauchy(k, m)
    rows = [[int(c == i) for c in range(k)] if i < k else par[i - k]
            for i in have]
    out = [bytearray(len(frags[have[0]])) for _ in range(k)]
    for b in range(len(out[0])):
        col = _solve(rows, [frags[i][b] for i in have])
        for j in range(k):
            out[j][b] = col[j]
    return [bytes(o) for o in out]


if __name__ == "__main__":
    for nm, n, tol in (("RF 3", 3, 2), ("RS(6,3)", 9, 3), ("RS(10,4)", 14, 4)):
        p = loss_prob(n, tol)
        print(f"{nm:9} annual loss {p:.3g}  ->  {-log10(p):.1f} nines")

    k, m = 10, 4
    data = [bytes((i * 31 + b * 7) & 0xFF for b in range(16)) for i in range(k)]
    frags = encode(data, k, m)
    lost = {0, 3, 7, 11}                  # three data fragments and one parity
    assert decode(frags, sorted(set(range(k + m)) - lost), k, m) == data
    print("recovered 10 data fragments from 10 of 14")

The field polynomial is not a free choice, and the Cauchy construction is not decoration: a Vandermonde matrix stacked under an identity fails on some k-subsets and passes on others, which is the worst shape a bug can have in a durability system — it survives every test you thought to write.

9. Deep dive 3: immutability, versioning, and why overwrite-in-place is not offered

The most surprising thing about the interface is that you cannot change a stored object, only replace it. That refusal has arithmetic behind it, properties it buys, and a bill it sends — in that order.

9a. The arithmetic that forbids it

Price the operation the API refuses, and the fatal problem turns out not to be its cost but that it cannot be retried safely.

Suppose the API offered “write these d bytes at this offset.”

Under RS(10,4) that stripe has 4 parity fragments, each computed from all 10 data fragments. Because every parity fragment is a combination of all the data, changing d bytes of one data fragment changes every one of the four parity fragments — even if d is 1.

Count the device operations that implies:

node I/Os to overwrite d bytes in a coded stripe
  read the old d bytes                                   1
  read-modify-write each parity fragment  4 x 2       =  8
  total device operations                 1 + 8       =  9
nodes that must commit atomically
  1 + 4                                               =  5

The “read-modify-write” line counts two operations per parity fragment, because each one must be read before it can be recomputed and written back.

Nine device operations to write d bytes is bad. It is not what kills the idea.

The part that actually kills it

The parity update is a delta applied to the old parity, so it is not idempotent.

Idempotence is what lets a client retry after a timeout without knowing whether the first attempt landed — and a network gives you ambiguous timeouts constantly.

Adding a difference into existing parity is not such an operation. A retry after an ambiguous timeout applies the delta twice, and the stripe then silently decodes to garbage. No error is raised anywhere; the damage surfaces the next time something needs to reconstruct that stripe.

The usual escape does not work here either. Content addressing — naming data by a hash of its own bytes, so writing the same content twice is indistinguishable from writing it once — is what makes every other retry in this design free (Deep dive 5 cross user dedup and the side channel it opens). It cannot help with parity, because the thing being written is a function of what is already there rather than a function of itself.

What refusing it buys

An in-place API would therefore require a distributed transaction on every write: five machines made to agree to apply their part or none of them does, with a recovery log per stripe to finish or undo a commit interrupted by a crash. At 200 PB of stripes.

Refusing the API is not a limitation; it is the design.

Every write instead becomes three steps: allocate a new stripe, write 14 fragments once, commit one metadata row. A failure at any point leaves orphaned fragments — bytes on disk that no metadata row points at — which is a cost problem for the garbage collector rather than a correctness problem for the data.

9b. What immutability buys

The refusal in 9a the arithmetic that forbids it is a good trade rather than a concession, because once nothing is ever modified, four properties fall out for free.

• Retries become free. A repeated fragment write puts identical bytes at a new location, so the loser of the race is garbage rather than corruption.
• Caches never need invalidating. The ETag is a fingerprint of the content, so a given ETag can only ever mean one sequence of bytes. A CDN — a content delivery network, the fleet of caches spread near users that serves popular objects without asking the origin — can hold an object forever. The whole protocol family for telling edge caches to forget something does not exist here.
• Versioning is cheap. A version is a 270-byte row, not a copy of the bytes.
• Undelete is trivial. It is deleting a marker.

The underrated one is the background loops.

In a mutable store, repair and scrub must coordinate with foreground writes. Here they cannot conflict, so neither needs a lock or a lease. A fragment is regenerated from k others with no writer to race, and a checksum mismatch is unambiguously corruption rather than a possible in-flight update.

9c. What it costs, and the lifecycle rule that is not optional

Immutability has a flip side, and one lifecycle rule has to be on by default because of it.

Versioning with no expiry means the corpus only grows: every overwrite adds bytes and removes none.

assume  20% of objects are overwritten once per month, versioning on

logical bytes added per month, PB
  200 x 0.20                             =  40
physical at RS(10,4), PB
  40 x 1.4                               =  56
media added, $/month
  56 x 10,000                            =  560,000

Half a million dollars a month of pure accumulation — growing every month, from a feature the customer turned on and forgot.

Note that the $560,000 is the first month. The second month adds another 56 PB on top, and nothing ever leaves. A lifecycle rule — “expire noncurrent versions after 30 days” — is therefore part of the default bucket configuration, not an advanced option.

The other cost is the one to name in the interview: a one-byte change to a 5 TB object rewrites 5 TB.

Object storage is the wrong store for a mutable working set, and saying so is how you show you know the boundary of what you just designed. Mutable small records belong in a database (sql/03); this store is for things written once and read many times.

10. Deep dive 4: multipart upload, and where the part size comes from

How large should the pieces of a large upload be? The question is more interesting than it looks, because the textbook formula for it produces a number nobody would ship, so a completely different constraint ends up setting the value.

The textbook formula first, in one paragraph, so you do not need the other chapter.

When you upload a big file in pieces over a connection that occasionally drops, small pieces waste time on per-piece setup and large pieces waste time re-sending work when a drop happens. Balancing those two gives an optimal piece size:

S* = rate x sqrt(2h / p)

where rate is the client’s throughput, h is the fixed handshake cost of starting a piece, and p is the probability per second that the connection drops. Chapter 14 derives it; it is not re-derived here.

What matters here is that in this regime the formula stops binding. Substitute a wired datacenter link and watch it produce nonsense:

assume  a datacenter client at 10 Gbps, a wired drop hazard p = 0.0002/s
        (one drop per 5,000 s), and a handshake h = 0.05 s

client rate, MB/s
  10,000 / 8                             =  1,250
2h / p
  2 x 0.05 / 0.0002                      =  500
sqrt of that
  500 ^ 0.5                              =  22.4
optimal part size, MB
  1,250 x 22.4                           =  28,000

Twenty-eight gigabyte parts. A part six times larger than the largest object the service accepts.

That is the finding, not a mistake in the algebra: on a wired link, drops are so rare that retry waste is nearly free, so the formula happily recommends never chunking at all. Part size has to be set by something else entirely.

What actually sets the part size

That something else is in-flight metadata.

Every part is a row in parts, and that row must be held from initiate until complete or abort. An abandoned upload holds its rows forever, because nothing forces a client to clean up after itself.

bytes per part row: upload_id 16 + part_number 4 + etag 16 + size 8
                    + extent locator 16 + row overhead 40
  16 + 4 + 16 + 8 + 16 + 40              =  100
metadata per upload at a 10,000-part cap, bytes
  10,000 x 100                           =  1,000,000
concurrent in-flight uploads, assumed                    100,000
metadata pinned by uploads that may never complete, GB
  100,000 x 1,000,000 / 1,000,000,000    =  100

100 GB of metadata held hostage by uploads that produced no object — against a total metadata corpus of 27 TB — is the reason for a part-count cap.

Fix the cap at 10,000 parts and the part size follows. The block below asks what part size that cap forces at each end of the object-size range:

minimum part size for a 5 TB object, bytes
  5,000,000,000,000 / 10,000             =  500,000,000
minimum part size for a 5 GB object, bytes
  5,000,000,000 / 10,000                 =  500,000
floor from section 8e -- a part below the packing line is pathological, bytes
  8,000,000
largest object the scheme can express, bytes
  10,000 x 5,000,000,000                 =  50,000,000,000,000

The floor of 8 MB in that block is not arbitrary either. It comes from 8e small objects and the 40 kb line: a part smaller than the packing threshold would be encoded as pathologically undersized fragments.

The rule is part = max(8 MB, object / 10,000). Substituted at four object sizes:

The largest object the scheme can express is 10,000 parts x 5 GB per part = 50 TB, so the advertised 5 TB object limit keeps a 10x margin under it.

Two supporting requirements candidates skip:

• Parts are addressed by number, and complete sends the full (number, ETag) list, which the server validates against what it holds. That list is the only place a lost or duplicated part is detectable. Without it, a client resuming from a stale offset assembles a corrupt object silently.
• abort is advisory — the client is asked to call it, but nothing forces it to. So a lifecycle rule expires incomplete uploads after 7 days. The 100 GB above is what happens when you trust clients to clean up.

11. Consistency: what read-after-write covers, and why LIST is the weakest thing here

Uploads settled, one contract question remains: which guarantees does the service offer, and which does it not? Stated precisely, the answer is narrower than most candidates assume — and the weakest operation in the whole design is the one that looks most innocent.

11a. Read-after-write, stated precisely

What may a client assume after a successful PUT? The answer is worth stating exactly, because what it may not assume is the more useful half in an interview.

PUT returns after the metadata row commits on the shard leader — the one replica per shard that accepts writes and therefore defines their order. The bytes were already durable before that commit; the commit is what publishes them.

So the guarantee has two halves that hold and two that do not:

• Covered: a GET issued after the PUT’s 200 was received, by any client, on any frontend, returns that version. The commit is a single-shard, single-row transaction, so it is linearizable and there is no cross-shard coordination to be eventually consistent about.
• Covered: GET by explicit versionId for any version that ever committed, forever, on any replica — because versions are immutable and append-only, a replica can only be missing a row, never wrong about one.
• Not covered: a GET issued concurrently with the PUT. It may return either version. Two operations that overlap in time have no happens-before relationship — neither one finished before the other started, so no order between them exists to be preserved — and pretending otherwise is where candidates invent guarantees.
• Not covered: a GET served from a follower replica, one of the copies that trails the leader by replaying its writes, if it has not yet applied the commit. Which means metadata point reads go to the leader.

Leader reads sound expensive and are not, for the reason 3b metadata and the ratio that licenses the whole architecture established:

metadata shards, assumed                                 300
GET rate to metadata, per shard leader
  10,000 / 300                           =  33
peak, at 3x
  33 x 3                                 =  99

About a hundred point lookups per second per shard leader — you can afford linearizable reads on the metadata precisely because the metadata is 0.0135% of the bytes. This guarantee is what 3b metadata and the ratio that licenses the whole architecture’s ratio was computed to license.

11b. Why LIST cannot be a snapshot

Listing a large bucket cannot be given a consistent point-in-time view — provably, not as a matter of taste — and ordered listing creates a second, more operational problem besides.

LIST is a paginated range scan over (bucket_id, key). It walks the keys in sorted order, a page at a time, handing back a cursor between pages.

A snapshot would mean every page reflecting the same instant, as though the bucket had been frozen for the whole traversal. To see why that is impossible, first work out how long a traversal takes:

keys in the bucket, assumed                              1,000,000,000
keys per page                                            1,000
pages in a full traversal
  1,000,000,000 / 1,000                  =  1,000,000
at 10 ms per page, seconds
  1,000,000 x 0.010                      =  10,000
in hours
  10,000 / 3,600                         =  2.8

A full listing takes 2.8 hours, and there is no such thing as a 2.8-hour snapshot.

Holding one would mean retaining every version written to that shard for the whole traversal, so that the walk could keep seeing the old ones. That is exactly the MVCC bloat problem — old row versions a database must keep alive because some long-running reader might still need them, piling up in proportion to how long that reader runs (Mvcc and deadlocks).

Price it: a shard taking 100 writes/s over a 10,000-second traversal accumulates 100 x 10,000 = 1,000,000 undead row versions. Per traversal. Nobody accepts that.

So the contract is: each page is internally consistent; the traversal is not.

• An object created during the walk may or may not appear, depending on whether its key sorts before or after the cursor.
• An object deleted during the walk may still appear.

That is not a weakness of the implementation. It is the only contract the operation can have, and stating it as such is the answer.

The second LIST problem, which is the one that pages people

Ordered listing forces range partitioning. Range partitioning puts neighbouring keys on the same machine. So a customer whose keys look like logs/2026-07-31/host/... sends every write of the day to a single range shard.

That means all 1,000 writes/s hit one shard, against a per-shard mean of 1,000 / 300 = 3.3 writes/s — a 300x imbalance created purely by a naming convention, with no bug anywhere.

Every mitigation costs something:

• Split the hot range aggressively. The split lags the burst by minutes.
• Ask the customer for a hash prefix in the key. That breaks their listing, which is why they chose the naming in the first place.
• Run a second hash-partitioned index for GET. That doubles the metadata write path.

Naming the tradeoff is the answer; the standard treatment is sql/03.

12. Garbage collection, scrubbing, and lifecycle

Three background jobs never appear in an architecture diagram and always appear in an incident review: reclaiming bytes nothing points at, detecting drives that lie about what they stored, and moving cold data to cheaper media.

12a. Orphans, and why reference counting loses

An orphan is a fragment sitting on a drive that no metadata row refers to any more — bytes you are paying for and can never serve. Four things produce them:

• A PUT whose fragments landed and whose metadata commit then failed.
• An abandoned multipart upload.
• A version removed by a lifecycle rule.
• A repair that regenerated a fragment onto a new node just before the placement changed.

Why the obvious design loses

The obvious design is reference counting: keep a counter beside each fragment saying how many metadata rows point at it, and delete the fragment when the counter reaches zero.

It is rejected for the reason Deep dive 6 two stores one commit derives. The counter and the metadata live in different stores with no shared transaction, so a crash between updating one and updating the other leaves a wrong count — and the two ways of being wrong are not equally bad:

• Too high is a leak. It merely wastes money.
• Too low deletes data a customer still owns.

From the outside there is no way to tell which of the two happened, which means there is no repair procedure either.

Mark and sweep takes the opposite approach. Mark walks the metadata and writes down every fragment it references; sweep walks the fragments and deletes anything not marked. It asks the metadata what it references — a question with exactly one authoritative answer, held in one store.

Size the job before dismissing it as too slow:

fragments, upper bound with every object coded individually
  100,000,000,000 x 14                   =  1,400,000,000,000
fragment index at 40 B/entry, bytes
  1,400,000,000,000 x 40                 =  56,000,000,000,000
mark: scan 27 TB of metadata at 1 GB/s, seconds
  27,000,000,000,000 / 1,000,000,000     =  27,000
sweep: scan the 56 TB fragment index, seconds
  56,000,000,000,000 / 1,000,000,000     =  56,000
both, across 100 nodes, seconds
  (27,000 + 56,000) / 100                =  830
in minutes
  830 / 60                               =  13.8

A full mark-and-sweep is a fourteen-minute hundred-node job, so run it weekly and stop optimizing it.

That 14 minutes is a comfortable upper bound, because it assumed every object was coded individually. Packing small objects into extents (8e small objects and the 40 kb line) cuts the fragment count by more than an order of magnitude.

Two safety rules, and the second is the one that causes incidents

Never collect a fragment younger than the longest possible in-flight upload. A grace period is a minimum age below which the collector refuses to touch anything, and it must exceed the slowest upload the service will accept.

Derive it. A 5 TB object over a 1 Gbps client link takes 5,000,000,000,000 x 8 / 1,000,000,000 = 40,000 seconds, which is 40,000 / 3,600 = 11.1 hours. Round up with margin: the grace period is 24 hours.

The reason it must exist at all: a fragment written but not yet referenced looks exactly like an orphan. Only age separates them.

The mark phase reads shard leaders, never followers. A follower missing a recent commit reports fewer references than actually exist, and the sweep then deletes live data.

This is the single most dangerous code path in the system, and it is worth saying so unprompted.

12b. Scrubbing: the errors that are certain rather than probable

Silent data corruption at this scale is not a risk to be hedged against; it is an arithmetic certainty on every pass, and a job has to be sized to catch it.

Drives sometimes return the wrong bytes and report success. The failure carries no error code, which is why it is called silent corruption.

Vendors publish a rate for it: the unrecoverable read error rate, conventionally one bad read per 1e15 bits transferred. Multiply that rate by the size of the corpus and you get the expected number of bad reads in a single pass over everything:

bits in one full pass over 280 PB
  280,000,000,000,000,000 x 8            =  2,240,000,000,000,000,000
expected unrecoverable errors per pass
  2,240,000,000,000,000,000 / 1,000,000,000,000,000  =  2,240

Two thousand silent errors per scrub pass is a certainty, not a risk.

That certainty is why every fragment carries a CRC written alongside it — cheap to compute, reliable at detecting the kinds of change a failing drive produces — and why the reader recomputes it rather than trusting the drive’s report of success.

A scrub is the background pass that reads everything and checks every one of those checksums. The principle behind running it at all: corruption you find while the stripe is otherwise healthy is repairable, and corruption you find during an outage may not be.

A mismatch is handled exactly like a missing fragment — reconstruct from k others, write a replacement, and quarantine the drive, meaning stop placing new data on it pending replacement.

Now size the pass. The question is how long one sweep over the whole 280 PB takes, given that scrubbing is allowed only a tenth of each drive’s read throughput:

sequential read per HDD, B/s                             200,000,000
scrub bandwidth at 10% of 17,500 drives, B/s
  17,500 x 200,000,000 x 0.10            =  350,000,000,000
one full pass over 280 PB, seconds
  280,000,000,000,000,000 / 350,000,000,000  =  800,000
in days, at 100,000 s/day
  800,000 / 100,000                      =  8

The 100,000 s/day in that last line is the rounded day of ch 02; against the exact 86,400 seconds the answer is a little over nine days. Either way the period is about a week.

The rule the number has to satisfy: the scrub period must be well under the time it takes for m independent corruptions to reach the same stripe.

Check it. Those 2,240 errors per pass are spread across 1.4e12 fragments, so the chance of any two of them landing in the same 14-fragment stripe within one pass is negligible, let alone four of them. Eight days clears the bar comfortably.

12c. Lifecycle and tiering

The last background job is a money question: there is an access rate below which moving data to cheap archival storage saves money — and above which it loses a great deal of it.

Tiering means keeping data on media matched to how often it is read: fast expensive drives for hot data, slow cheap ones for cold. The mechanism is covered in Deep dive 3 storage tiering and generating the tail on demand.

What is specific to an object store is the break-even calculation. The cold class is not simply cheaper — it charges a retrieval fee, a per-gigabyte price for reading the data back out. That fee is what turns tiering from an obvious win into an arithmetic question.

The block below computes the monthly saving per petabyte, the cost of reading that petabyte back once, and then divides the first by the second to get the number of reads per month at which the two cancel:

assume  archive storage at 1/5 of standard, and a $0.02/GB retrieval fee

archive, $/PB-month
  10,000 / 5                             =  2,000
saving, $/PB-month
  10,000 - 2,000                         =  8,000
cost to read a whole PB back, $
  0.02 x 1,000,000                       =  20,000
break-even access rate, reads per PB per month
  8,000 / 20,000                         =  0.4
physical bytes older than 30 days at a 5-year retention, PB
  280 x 0.984                            =  275.5
saving if all of it moves, $/month
  275.5 x 8,000                          =  2,204,000

Archiving pays only for objects read less than 0.4 times per month.

Quote that number when someone proposes archiving “everything older than 30 days” without looking at the access distribution. An object read weekly is read about 4 times a month, costing 4 x 20,000 = 80,000 per PB-month in retrieval fees against an 8,000 saving — a 10x loss.

Where it does pay, it pays enormously, because age distributions here are extreme. Objects younger than 30 days are 30 / 1,825 = 0.016 of a 5-year corpus, so 98.4% of the bytes are eligible on age alone: $2.2 M/month of a $2.8 M/month bill.

Tiering is the second-largest lever after coding, and unlike coding it is a policy change rather than a rewrite.

13. Bottlenecks and scaling

Tier by tier: what runs out first, and what do you do about it? “Binding constraint” below means the resource that limits the tier before any other one does.

The right-hand column is the one to read carefully: it says where each scaling move stops working, which is the difference between a plan and a hope.

Two phrases in that table are worth naming.

• Embarrassingly parallel — the work divides into independent pieces with no coordination between them, so throughput scales linearly with machines added. The happiest possible scaling story.
• Foreground traffic — requests a customer is waiting on, as opposed to background work the system does for itself. The distinction matters because background work that starves foreground work is an outage even though nothing has failed.

The row that actually needs attention is repair.

Repair reads k fragments to regenerate one, so a rack returning from maintenance generates 10x its own data volume in reads — the repair amplification of 8b the repair window derived from bandwidth, arriving all at once.

Two controls. First, rate-limit repair with a token bucket: a counter that refills at a fixed rate and is spent one token per unit of work, so the long-run rate is capped while short bursts are still allowed. Size the refill rate as a fraction of each node’s measured idle bandwidth (Token bucket).

Second, prioritize stripes by how many fragments they are missing. A stripe that is down 3 of its 4 tolerated failures is worth a hundred stripes that are down 1, because it is one more failure from being unrecoverable.

14. Failure modes

What breaks, what an operator actually sees when it breaks, and the response — each response linked to the section that derived it.

The middle column is the useful one during an incident: it is what shows up on a dashboard, and it is rarely the same thing as the failure.

Two terms from that table:

• Failure domain — the set of things that die together: a drive, a machine, a rack, a drive model. The whole placement strategy is the exercise of making sure a stripe never has more than m fragments inside one domain.
• Leader election — the protocol by which the surviving replicas of a shard agree on a new leader when the old one stops answering.

15. Alternatives rejected

Seven designs a reasonable person proposes instead, and the number that kills each one. Every row’s right-hand column points at a section above, so none of these rejections is an opinion.

16. Interviewer pushback

Six questions an interviewer asks when they want to find out whether you understand your own design, each answered the way you would say it out loud.

“You claimed eleven nines. Show me.”

I cannot, and neither can anyone else — that is the honest answer. My model gives nineteen nines for RS(10,4) at a 2% AFR and a 2-hour repair window, and it gets there by assuming the four post-first failures are independent. They are not: one rack, one drive model, one bad deploy. Eleven nines is nineteen minus a correlated-failure haircut that is estimated from incident history, not computed. What I can defend is the model’s inputs and the controls on each correlated mode — rack diversity, model mixing, staged rollouts, a GC grace period — because those are the things that actually move the real number.

“Erasure coding is strictly better in your table. Why would anyone replicate?”

Two reasons and they are both in Deep dive 2 erasure coding derived. Small objects: below 40 KB, fourteen fragments cannot fill fourteen allocation blocks, so RS(10,4) costs 14x rather than 1.4x — replication or packing wins there. And latency: a replicated read is one fetch, a coded read is ten, so the coded object’s p99 is the fragment’s p99.9. I can buy that back with k+2 hedging at 1.2x read bandwidth, which is what I would do, but it is a real cost that the storage table does not show.

“Why not let me overwrite a byte range? Every filesystem does.”

Because the parity is a function of the whole stripe. Updating d bytes means reading the old bytes, computing a delta, and applying it to four parity fragments on four nodes — nine device operations and a five-node atomic commit. Worse, the parity update is a delta applied to existing content, so it is not idempotent: a retry after a timeout applies it twice and the stripe decodes to garbage with no error anywhere. Immutability is what makes every retry in this system safe, and I would not trade that for an API a database already provides better.

“Your LIST is eventually consistent. Customers hate that.”

They do, and the alternative is worse. A billion-key bucket is a million pages; at 10 ms per page that is 2.8 hours of traversal, and a snapshot over 2.8 hours means retaining every row version written in that window. Per page I give a consistent view, and the cursor is a key position rather than an offset so pagination is stable under inserts before the cursor. If a customer genuinely needs a point-in-time inventory, the right product is a daily manifest generated from the metadata, not a synchronous API.

“A customer’s bucket is taking all the write traffic for one shard. Fix it live.”

Split the range, but understand that the split is minutes behind the burst, so the first mitigation is admission control: rate-limit that bucket at the frontend so one tenant’s key naming does not become everyone’s latency. Then split, then talk to the customer about a hash component in the key prefix. The underlying tension is that ordered LIST forces range partitioning, and range partitioning is hostage to the customer’s naming — a hash-partitioned store would not have this problem and could not offer LIST.

“Where does the 2-hour repair window come from? It sounds convenient.”

From bandwidth. A 16 TB drive rebuilt onto one replacement node over a 1 Gbps NIC is 128,000 seconds, or 36 hours — unusable. Declustering the rebuild across 200 nodes at 10% of each NIC gives 20 Gbps aggregate and 6,400 seconds, so under two hours including detection. The 10% cap is not arbitrary either: repair reads ten fragments per fragment regenerated, so uncapped repair would starve foreground reads. The window is the output of the placement width and the repair bandwidth budget, and if either changes, every durability number in 8c durability and what eleven nines is a claim about moves with it.

The assumption ledger

Every design is a set of assumptions with a diagram attached, and the diagram is only correct relative to them. Collected in one place, everything the design has leaned on can be stated in twenty seconds — along with what replaces the design when each assumption fails.

Sort each assumption into one of three bins.

• State it — you are free to pick, and being wrong costs a re-derivation and nothing more.
• Ask it — the answer moves a policy or a threshold, and is worth an interviewer’s time.
• Load-bearing — if it is wrong the design is not suboptimal, it is invalid. A box appears or disappears, rather than the count inside a box changing.

The one-line test, from ch 03: move the assumption an order of magnitude in each direction and ask whether the set of boxes changes, or only the number of machines inside them.

If you take one row from this table, take the first.

The chapter’s central decision — erasure coding rather than whole replicas — is not driven by the cost table in 8a the overhead arithmetic. That table is only the reward. The decision is driven by the assumption that objects are never modified after they are written.

That single assumption is what makes coding available; the cost table is what makes it attractive. Take immutability away and the money argument becomes irrelevant, because the scheme is no longer buildable at an acceptable price in coordination.

Cheat sheet

Everything above, compressed to the lines worth having in memory when the whiteboard is in front of you.

Next: 29 — Design A Stock Exchange is the same track with the opposite constraint — there the entire budget is 11.55 microseconds and nothing is allowed to be eventually anything. The client half of this store is 15 — Google Drive; the arithmetic habits are 02 — Back Of The Envelope.