How to design an object-storage service

In this lesson, we’ll design an object store: a service that keeps arbitrary files, a photograph, a log file, a database backup, and hands them back on demand by name. You PUT a blob under a key, GET it back, at exabyte scale, without ever losing one.

We build it end to end: how to size it, how to hold 200 petabytes for less than half the price of whole-copy replication, why it refuses to edit a stored file in place, and what the “eleven nines of durability” claim actually means. An object store is neither a filesystem nor a database, and those two refusals are the design, not limitations of it. By the end you’ll be able to size the two tiers, derive the erasure-coding saving, explain where “eleven nines” really comes from, and defend each refusal with a number.

Vocabulary

Seven terms recur throughout.

• 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, size, fingerprint, and where its bytes physically live. Not the bytes themselves.
• Exabyte scale, the whole corpus is measured in units of 10^18 bytes: a thousand petabytes, or a million terabytes.

The contract

The interface fits in four lines.

• In: PUT /photos/cat.jpg with two million bytes in the body.
• Out: an HTTP 200 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 key.
• Later, in: GET /photos/cat.jpg.
• Out: those same two million bytes, byte for byte, or any contiguous slice the caller asks for.

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

The one split everything follows from

The architecture is a single split: a small mutable index and an enormous immutable byte pool. Every hard property in this chapter is a consequence of it.

flowchart TD
    R["Request: PUT / GET / LIST / DELETE"] --> S{"What does it touch?"}
    S -->|"names, ordering, current version"| M["Metadata: 27 TB<br/>sorted, mutable, needs compare-and-swap<br/>small consistent database"]
    S -->|"the bytes themselves"| B["Byte pool: 200 PB<br/>immutable, append-only<br/>huge cheap store"]

The split turns on one 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 instead of a mess. And it charges for them on every write, through machinery covered in the database-internals chapter: a page cache (recently touched disk pages held in memory), a write-ahead log (WAL) (a sequential journal every change is appended to before it is applied, so a crash can be replayed forward), and MVCC (multi-version concurrency control: each update leaves the old row version in place so in-flight readers still see a coherent snapshot).

Objects need none of that. Metadata needs all of it. The two disagree on every property:

Terms from that table, used again below:

• 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(s). 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.
• 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.

Roughly 0.0135% of the bytes need a database and the rest need an append-only log. So you run one small expensive consistent store and one enormous cheap one, and every design question is which side of that line something falls on.

Three failures the design has to survive

• 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.
• A repair storm: the burst of rebuild traffic when a rack comes back after an outage issues so many reads that ordinary customer requests are starved of bandwidth.
• Garbage collection racing an upload: the job that reclaims unreferenced bytes deletes a fragment that was about to be referenced.

Each is the subject of a section below.

Requirements

Functional

• 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 does not destroy the first. The old bytes stay, reachable by their version id; the key points somewhere new. A DELETE appends a delete marker saying “as of here, this key reads as absent” instead of erasing anything, which 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 failed part, then declares the set complete. It is the only way a five-terabyte upload survives a network that drops connections.
• Lifecycle policies: standing rules the service applies on the customer’s behalf, such as “after 30 days move this to cheaper, slower storage”. Colder is the industry word for that class: cheap to keep, expensive to read.
• Presigned URLs: links the service signs in advance, granting a specific operation on a specific key for a limited time, so a browser can upload straight into the store and the customer’s own servers never carry the bytes.

Out of scope: POSIX semantics (the Unix file interface that lets you rename, append, or overwrite bytes in the middle), server-side search over object contents, and cross-region replication. Refusing POSIX is the interesting one, because refusing it is exactly what makes everything else here possible.

Non-functional

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.

“Eleven nines” is shorthand for a durability of 99.999999999%, an annual loss probability of 1e-11. Each additional nine is another factor of ten less likely.

Back of the envelope

Byte pool. 100 billion objects at 2 MB average is 200 PB of logical data. At 1,000 PUT/s and 10,000 GET/s that is 2 GB/s ingest (16 Gbps) and 20 GB/s egress (160 Gbps, or 480 Gbps at a 3x peak). Rates are in bits per second because links are sold that way; capacity is in bytes; the factor of 8 between them is why conversions keep multiplying by 8.

At an all-in raw-drive cost of $0.01 per GB-month ($10,000 per PB-month) the media bill is set by how many physical bytes you keep per logical byte. The obvious survival scheme is whole extra copies: replication factor 3 (RF 3) survives two simultaneous losses. Three copies of 200 PB is 600 PB, at $6 M/month, $72 M/year. That single line is why this chapter is mostly about erasure coding, nothing else has a $72 M/year lever attached.

Metadata. Each object needs one row: bucket_id, key, version_id, size, etag, timestamps, storage class, placement pointer, plus page headers, per-row version stamps, and index entries. That is about 270 bytes, so 100 billion objects is 27 TB, 0.0135% of the corpus. That ratio is the permission slip for the whole architecture: 27 TB is small enough to shard across a few hundred boxes, replicate three ways, run a leader per shard, and take linearizable reads on it without thinking about the bill. Linearizable means a read observes every write acknowledged before it started, as if all operations ran one at a time in a single global order, the strongest and most expensive thing a distributed store can promise.

API sketch

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

HEAD returns headers without a body, metadata with no byte path. Range: asks for a contiguous slice. continuation-token is an opaque cursor the server hands back with each LIST page so the next call resumes where the last stopped.

Four choices in the sketch are deliberate:

• No PATCH and no append. Updating bytes inside a stored object requires an all-or-nothing commit across five machines, and worse, cannot be made idempotent (safe to retry). Both are derived under immutability.
• DELETE is a write. It appends a delete marker instead of removing rows, so delete is as recoverable as any other version and costs the same 270-byte row.
• Range is first-class. A range read of a healthy object touches one node, which is why coding is applied per stripe unit, not per object.
• Multipart’s complete is the linearization point, the instant the operation counts as having happened. Parts are durable bytes with no name; the object exists at the moment one metadata row commits.

Data model

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

objects is the only table with a row per object; everything else is a small side table shared by many objects. Placement (the choice of which machines hold an object’s fragments) is stored once per group of objects, because a list of 14 node identifiers is far too bulky to repeat 100 billion times. Sealed means an extent has been closed to further appends; a sealed extent is safe to encode and never written to again.

Three modelling choices carry the design:

• 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 transactional.

• objects is range-partitioned, not hash-partitioned. 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 them anywhere. Ordered LIST requires range partitioning, which imports a hot-shard problem that scattering does not have, priced below.

• extents exist so small objects are not coded individually. A block is the smallest unit of space a drive hands out, here 4,096 bytes, so anything smaller still consumes a whole one. Below k x block = 40 KB an object cannot fill even one block per fragment; packing many small objects into a sealed extent and coding the extent fixes this, and is priced below.

High-level architecture

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 read-modify-write")]
    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 top half (client, frontend, metadata, placement, data nodes) is the request path. The four boxes hanging off the bottom are background loops no customer ever waits for.

The request path. A PUT arrives at a stateless frontend that checks the caller’s signature, mints presigned links, and translates byte ranges into fragment offsets. It does one small row write against the metadata service (range-partitioned on bucket+key, leader per shard), using compare-and-swap to move the current-version pointer safely. To store bytes it asks the placement service for a set of k + m machines chosen to be rack-diverse, spread across independent racks so one rack losing power cannot take out more fragments than the code can survive. It 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 and 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 background loops. The scrubber re-reads fragments and checks each one’s CRC (a short checksum stored beside the data that detects a drive silently returning wrong bytes). Repair regenerates fragments lost with a dead drive, spreading the work across the whole fleet. The garbage collector runs weekly in two phases: mark asks the metadata which fragments are still referenced, sweep deletes the rest. The lifecycle mover shifts objects by age to a colder class.

The one load-bearing choice is that the frontend, not the data node, does the coding. The data node is a dumb append-only store: it never reads what it wrote, never computes parity, 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.

Metadata needs a database; bytes do not

Take the operations one at a time. The first three are metadata questions and each needs a database feature; the last two are byte questions and neither needs anything more than an offset.

pread and pwrite are the Unix system calls that read and write at an explicit byte offset, one instruction’s worth of intent, no index, no lock, no transaction. 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 here: MVCC version chains, the page cache, the query planner, and the fsync of the WAL before every commit (the call that forces buffered data all the way onto physical media and waits for the drive to confirm, the slowest thing a database routinely does).

Pricing the mistake makes it concrete. Store 2 MB objects as rows in a relational table and every PUT writes 2 MB to the WAL and 2 MB again to the table pages, a write amplification of 2. At 1,000 PUT/s that is 4 GB/s of writes, about four saturated NVMe devices (an NVMe drive sustains roughly 1 GB/s sequential), carrying 2 GB/s of payload while using none of the database features you paid for. The metadata for the same 1,000 PUTs is 270,000 bytes/s, 0.027% of one device. Four saturated devices against a third of a thousandth of one.

The converse is just as wrong: put metadata in the object store and LIST becomes a directory walk, compare-and-swap does not exist, and the current-version pointer has no home. An object store makes a poor database for the same reasons a database makes a poor object store.

Erasure coding, derived

Here is the lever attached to the $72 M/year line. Erasure coding starts from one idea: you do not need whole spare copies to survive losing some data. You cut the data into pieces, compute extra pieces from them by arithmetic, scatter all the pieces across drives, and arrange that any sufficiently large subset rebuilds the original.

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

Reed-Solomon, written RS(k, m), 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, not a privileged subset. So RS(10,4) means 10 data fragments, 4 parity, 14 drives, and survival of any four simultaneous losses.

flowchart TD
    O["Object bytes"] --> D["Cut into k = 10 data fragments"]
    D --> P["Compute m = 4 parity fragments"]
    D --> W["Write all 14 fragments to 14 drives<br/>on rack-diverse nodes"]
    P --> W
    W --> RC["Any 10 of the 14 rebuild the object<br/>survives 4 simultaneous losses"]

The overhead

Storage overhead is physical bytes stored per logical byte: (k + m) / k. Applied to the 200 PB corpus at $10,000/PB-month and 16 TB drives:

RS(10,4) stores less than half the media of triple replication and tolerates two more simultaneous failures: a saving of 320 PB, $38.4 M/year, and 20,000 fewer drives. This is not a tradeoff but a strict improvement on both axes. The bill arrives later, in the read tail and at the small end of the object-size range.

The repair window

When a drive dies, how long does a stripe spend one fragment short? A stripe missing a fragment is degraded: still readable, because k survivors suffice, but with less margin. The repair window is the time between a drive dying and the missing fragment being regenerated elsewhere. It matters because a second failure inside that window is what actually loses data.

Rebuilding one 16 TB drive onto a single replacement node over a 1 Gbps network card takes about 128,000 seconds, 36 hours, catastrophic. The funnel is the single card every rebuilt byte squeezes through. The fix is declustering: instead of a fixed partner inheriting all the work, spread the failed drive’s stripes across the whole pool. With 200 nodes each lending 10% of a 1 Gbps card, aggregate rebuild bandwidth is 20 Gbps and rebuild takes about 6,400 seconds, under 2 hours including detection and scheduling. That 2-hour window is used unchanged for the rest of the chapter. The 10% cap keeps the other nine tenths reserved for customers.

To regenerate one lost fragment, repair reads k surviving fragments and solves for the missing one, so it moves ten bytes for every one lost. That repair amplification of 10x is why the 10% cap is a real constraint: uncapped repair would out-consume the customers it protects. Replication has a repair amplification of 1: you copy the lost bytes and nothing more, the quiet advantage the storage table hides.

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

With a repair window in hand you can build a probability model for losing a stripe, and it produces a far larger number than any operator advertises.

The model needs one vendor number: the annualized failure rate (AFR), the fraction of drives that die per year. 2% is normal, one drive in fifty. A 2-hour window is 2/8,760 of a year, so the chance any one specific drive dies inside a given window is about p = 4.6e-6.

A stripe is lost when a first drive fails and then enough survivors also fail before repair completes:

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 from n. For RS(10,4), C(13,4) = 715 four-drive subsets of the 13 survivors could each finish the stripe off, which is why a wider code is not automatically safer. Run the formula for all three schemes (j = the failures tolerated):

The nines column is just -log10(annual loss). The independence model says RS(10,4) delivers nineteen nines, yet every operator that runs it advertises eleven, and that eight-order-of-magnitude gap is the real subject.

First, eleven nines is a statement about scale. At 11 nines, the expected loss over 100 billion objects is one object per year. 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 model assumes independence in exactly one place: writing p^j. In a real datacenter drives share power, cooling, switches, manufacturing batches, and software, so failures are not independent. Five ways the assumption breaks, and the control for each:

The rack case has a clean number. If 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: annual loss 0.001, three nines, not nineteen. Placement diversity is therefore worth sixteen orders of magnitude, and it costs exactly one constraint: no rack holds more than m fragments. With m = 4, a 14-fragment stripe must span at least ceil(14/4) = 4 racks; in practice 7 racks put 2 fragments each, so two entire racks can be down and the stripe is still only 4 fragments short.

Eleven nines, then, is not the output of the model. The model says nineteen. Eleven is nineteen minus a correlated-failure haircut nobody can compute from first principles, estimated from incident history and rounded to a number the operator is willing to defend.

What coding costs: the degraded read

The Reed-Solomon construction here is systematic: the k data fragments are literally the object cut into k consecutive pieces, with parity added alongside. So a healthy range read touches one node (the piece covering the range, no decoding needed), a healthy full-object read touches k, and a degraded read touches k, a read is degraded when a needed data fragment is unavailable (dead or slow drive), forcing the frontend to fetch k fragments and solve for the missing one.

That third case wrecks the tail. Each fragment fetch has a distribution: say median (p50) 600 microseconds, p99 10 ms, p99.9 50 ms, the floor being one datacenter round trip plus one SSD random read. A full-object read finishes only when its slowest fragment arrives, so its latency is the maximum of k draws. With ten independent draws, the chance all land inside the per-fragment p99 is 0.99^10 = 0.904. So 10% 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 sold as a storage optimization. A replicated read issues one fetch and inherits the fragment tail unchanged, the advantage the storage table hides.

The tail can be bought back with hedging. Hedging means asking for more copies of the work than you need and using whichever arrive first. The redundancy is already sitting in the parity fragments: request k + 2 and decode from whichever k arrive first.

Twenty percent more read bandwidth buys back the entire tail regression: the object’s p99 returns to the fragment’s p99. This is the same hedging a replicated store gets for free by having three copies; coding makes you buy it explicitly, and the fact that you can is the strongest argument for m >= 2.

What does not get worse is bytes moved. The code operates symbol-wise (each byte position is its own little system of equations) so reconstructing a 4 KB range needs the same 4 KB offset from k fragments, not the whole object. A degraded range read moves about 41 KB, not 2 MB. What it spends is 10 IOPS (separate seek-and-read requests), and on a spinning disk IOPS is far scarcer than bandwidth, the thread the next section picks up.

Small objects, and the 40 KB line

Drives allocate space in 4,096-byte blocks, and a 50-byte fragment still occupies a whole block. So below some object size the k + m fragments cannot each fill a block, every fragment wastes most of one, and the nominal 1.4x overhead becomes fiction. Setting the floor cost (k+m) x block equal to the nominal cost ((k+m)/k) x S and solving gives the break-even S = k x block = 40 KB.

Below 40 KB, coding an object individually costs more than its nominal overhead. At 4 KB it costs 14 x 4,096 / 4,096 = 14x, nearly five times worse than the triple replication it was meant to beat, and spends 14 IOPS to write and 10 to read something that should have been one of each.

The fix is to pack, then code the extent. Append many small objects into a 1 GB extent, seal it, and erasure-code the extent as a unit. Thousands of small objects share one stripe and one placement, every fragment is enormous (100 MB, not 50 bytes), and the object’s row carries (extent_id, offset, length) so a small-object GET is still one range read on one node. The threshold k x block is not a tuning knob; it moves whenever the code parameters or block size do.

The deeper reason to pack is seeks, not bytes. A spindle (one spinning hard drive) sustains only about 100 random reads per second no matter how few bytes each asks for, because the arm has to move. Today, 10,000 full-object GET/s with k+2 hedging is 120,000 fragment reads/s, 1,200 spindles, against the 17,500 that capacity already demands, a 15x cushion. Shrink the average object 10x to 200 KB and the same 20 GB/s arrives as 100,000 GET/s, or 12,000 spindles; at the 3x peak that is 36,000 spindles against 17,500. The fleet is then sized by seek rate, not terabytes. That is why production systems pack.

The code that makes “any k” concrete

The “any k fragments will do” property is easy to claim and easy to get subtly wrong, so here is a complete, runnable Reed-Solomon encoder and decoder plus the durability model above.

Three ideas make it readable. The arithmetic runs in a finite field, not ordinary integers, GF(256), the field of 256 elements (one byte each), where addition is bitwise exclusive-or (so the code has no minus signs) and multiplication is done by log/exponent table lookup built from a field polynomial (0x11D). Encoding is a matrix multiplication: the m parity fragments are m weighted combinations of the k data fragments, and decoding solves the resulting system by Gauss-Jordan elimination. The choice of matrix is the whole correctness argument: “any k reconstruct” means every k x k submatrix you could be left with is invertible. A Cauchy matrix (entries 1 / (x_i + y_j)) has that property for every square submatrix by construction; a Vandermonde matrix stacked under an identity does not, failing on some subsets of survivors, the worst shape a bug can have in a durability system, because it survives every test you thought to write.

"""RS(k,m) over GF(256), plus the durability model. 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     # 2% AFR, year in hours, 2h window


def loss_prob(n, tolerated):
    """One drive fails, then `tolerated` more before repair finishes.
    Independence assumed -- the assumption the durability table attacks."""
    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 assert deletes three data fragments and one parity fragment and still recovers the original bytes.

Immutability, versioning, and why there is no overwrite-in-place

You cannot change a stored object, only replace it. That refusal has arithmetic behind it, properties it buys, and a bill it sends.

The arithmetic that forbids it

Suppose the API offered “write these d bytes at this offset.” Under RS(10,4) every one of the four parity fragments is computed from all ten data fragments, so changing d bytes of one data fragment changes all four parity fragments, even if d is 1. Counting operations: read the old bytes, then read-modify-write each of four parity fragments (two operations each): nine device operations, committed atomically across five nodes, to write a few bytes.

Nine I/Os is bad but not fatal. What kills it is that the parity update is a delta applied to the old parity, so it is not idempotent. Idempotence is what lets a client retry after an ambiguous timeout (which a network hands you constantly) without knowing whether the first attempt landed. A retried delta applies the difference twice, and the stripe then silently decodes to garbage, surfacing only the next time something reconstructs it. The usual escape does not help: content addressing (naming data by a hash of its own bytes, so writing the same content twice is indistinguishable from writing it once) cannot cover parity, because parity is a function of what is already there, not of itself.

An in-place API would therefore require a distributed transaction on every write (five machines agreeing to apply their part or none, with a per-stripe recovery log) at 200 PB of stripes. Refusing it is not a limitation; it is the design. Every write instead becomes three steps, and a failure before the commit leaves only orphaned fragments (bytes no metadata row points at), a cost problem for the garbage collector, not a correctness problem for the data.

flowchart LR
    A["Allocate a new stripe"] --> B["Write k+m fragments once<br/>durable bytes, not yet named"]
    B --> C["Commit one metadata row<br/>object now exists"]
    B -. failure before commit .-> O["Orphaned fragments<br/>reclaimed by GC"]

What immutability buys

Once nothing is ever modified, four properties fall out for free:

• Retries are free. A repeated fragment write puts identical bytes at a new location, so the loser of a race is garbage, not corruption.
• Caches never need invalidating. The ETag is a fingerprint of the content, so a given ETag can only ever mean one byte sequence. A CDN (a content delivery network, caches near users that serve popular objects without asking the origin) can hold an object forever; the whole protocol family for telling 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 just deleting a marker.
• Background loops need no locks. In a mutable store, repair and scrub must coordinate with foreground writes. Here they cannot conflict: a fragment is regenerated from k others with no writer to race, and a checksum mismatch is unambiguously corruption, not a possible in-flight update.

What it costs

Versioning with no expiry means the corpus only grows. If 20% of objects are overwritten once a month, that is 40 PB of new logical data monthly, 56 PB physical at RS(10,4), $560,000/month, in the first month, growing every month because nothing ever leaves. So “expire noncurrent versions after 30 days” is part of the default bucket configuration, not an advanced option.

The other cost: a one-byte change to a 5 TB object rewrites 5 TB. Object storage is the wrong store for a mutable working set; mutable small records belong in a database. This store is for things written once and read many times.

Multipart upload, and where the part size comes from

How large should the pieces of a large upload be? The textbook formula balances per-piece setup cost against re-sending work when a connection drops:

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

where rate is the client’s throughput, h the fixed handshake cost per piece, and p the per-second drop probability (derived in the video-streaming chapter). On a wired datacenter link (10 Gbps, a drop hazard of one per 5,000 s, a 0.05 s handshake) it produces 28 GB parts, six times larger than the largest object the service accepts. That is the finding, not an algebra mistake: on a wired link drops are so rare that retry waste is nearly free, so the formula recommends never chunking. Part size has to be set by something else.

That something else is in-flight metadata. Every part is a row in parts held from initiate until complete or abort, and nothing forces an abandoned upload to clean up. At a 10,000-part cap, one upload pins about 1 MB of metadata; 100,000 concurrent uploads pin 100 GB, against a 27 TB corpus, enough to justify a part-count cap.

Fix the cap at 10,000 and the part size follows: part = max(8 MB, object / 10,000). The 8 MB floor comes from the packing line, a smaller part would be encoded as pathologically undersized fragments.

The largest object the scheme can express is 10,000 x 5 GB = 50 TB, so the advertised 5 TB limit keeps a 10x margin. Two supporting rules: complete sends the full (number, ETag) list, which the server validates, the only place a lost or duplicated part is detectable, without which a client resuming from a stale offset assembles a corrupt object silently. And abort is advisory, so a lifecycle rule expires incomplete uploads after 7 days.

Consistency: read-after-write, and why LIST is the weakest thing here

Read-after-write, stated precisely

PUT returns after the metadata row commits on the shard leader (the one replica per shard that accepts writes and defines their order); the bytes were durable before that commit, and the commit publishes them. 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 with no cross-shard coordination.
• Covered: GET by explicit versionId for any version that ever committed, forever, on any replica: versions are immutable and append-only, so a replica can only be missing a row, never wrong about one.
• Not covered: a GET issued concurrently with the PUT. Two operations that overlap in time have no happens-before relationship, so no order exists between them to preserve; it may return either version.
• Not covered: a GET served from a follower (a replica that trails the leader by replaying its writes) that has not yet applied the commit. So metadata point reads go to the leader.

Leader reads are cheap here for the reason the metadata ratio established: across 300 shards, 10,000 GET/s is about 33 reads/s per leader, 99 at the 3x peak. You can afford linearizable reads precisely because metadata is 0.0135% of the bytes.

Why LIST cannot be a snapshot

LIST is a paginated range scan over (bucket_id, key), walking keys in sorted order a page at a time behind a cursor. A snapshot would mean every page reflecting one instant. But a billion-key bucket at 1,000 keys/page is a million pages; at 10 ms/page that is 2.8 hours, and there is no such thing as a 2.8-hour snapshot. Holding one would mean retaining every row version written to the shard for the whole traversal (the MVCC bloat problem) accumulating about a million undead versions per traversal on a shard taking 100 writes/s. Nobody accepts that.

So the contract is that each page is internally consistent while 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 the only contract the operation can have.

There is a second, operational LIST problem. Ordered listing forces range partitioning, and 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 one shard: all 1,000 writes/s against a per-shard mean of 3.3, a 300x imbalance created purely by a naming convention, with no bug anywhere. Every mitigation costs something: splitting the hot range lags the burst by minutes, asking for a hash prefix breaks the customer’s listing, and a second hash-partitioned index doubles the metadata write path.

Garbage collection, scrubbing, and lifecycle

Three background jobs never appear in an architecture diagram and always appear in an incident review.

Orphans, and why reference counting loses

An orphan is a fragment no metadata row refers to any more, bytes you pay for and can never serve. They come from a PUT whose commit failed after its fragments landed, an abandoned multipart upload, a version removed by a lifecycle rule, or a repair that regenerated a fragment just before the placement changed.

The obvious design, reference counting (a counter beside each fragment, deleted at zero), fails because the counter and the metadata live in different stores with no shared transaction. A crash between the two updates leaves a wrong count, and the two ways of being wrong are not equally bad: too high merely leaks money, too low deletes data a customer still owns, and from the outside you cannot tell which happened, so there is no repair procedure.

Mark and sweep takes the opposite approach: mark walks the metadata and records every referenced fragment, sweep deletes anything not marked. It asks the metadata what it references, a question with exactly one authoritative answer in one store. Sizing it: an upper bound of 1.4e12 fragments (every object coded individually) means a 56 TB fragment index and a 27 TB metadata scan; at 1 GB/s across 100 nodes the whole job is about 14 minutes, so run it weekly and stop optimizing. Packing small objects into extents cuts the fragment count by more than an order of magnitude, so 14 minutes is a comfortable upper bound.

Two safety rules. A grace period refuses to collect any fragment younger than the slowest upload the service accepts: a 5 TB object over a 1 Gbps link takes 11 hours, so the grace period is 24 hours, because a fragment written but not yet referenced looks exactly like an orphan and only age separates them. And the mark phase reads shard leaders, never followers: a follower missing a recent commit reports fewer references than exist, and the sweep then deletes live data. This is the single most dangerous code path in the system.

Scrubbing: the errors that are certain, not probable

Drives sometimes return the wrong bytes and report success: silent corruption, no error code. Vendors publish an unrecoverable read error rate of about one bad read per 1e15 bits. Over 280 PB that is 280 PB x 8 / 1e15 = 2,240 silent errors per full pass, a certainty, not a risk. That is why every fragment carries a CRC written beside it and the reader recomputes it instead of trusting the drive.

A scrub is the background pass that reads everything and checks every checksum. A mismatch is handled like a missing fragment: reconstruct from k others, write a replacement, and quarantine the drive (stop placing new data on it). Allowed 10% of each drive’s read throughput, a pass over 280 PB at 350 GB/s takes about 8 days. The rule it satisfies: the scrub period must be well under the time for m independent corruptions to reach one stripe: with 2,240 errors spread across 1.4e12 fragments, the chance of even two landing in the same 14-fragment stripe in one pass is negligible.

Lifecycle and tiering

Tiering keeps data on media matched to how often it is read. What is specific to an object store is that the cold class charges a retrieval fee (a per-gigabyte price to read data back) which turns tiering from an obvious win into an arithmetic question.

At archive pricing of one fifth of standard, moving a petabyte saves $8,000/month but costs $20,000 to read back once, so the break-even is 0.4 reads per PB per month. Archiving pays only below that. An object read weekly (about 4 reads/month) costs $80,000/PB-month in retrieval fees against an $8,000 saving, a 10x loss. But age distributions here are extreme: objects younger than 30 days are 1.6% of a 5-year corpus, so 98.4% of the bytes are eligible on age alone, worth $2.2 M/month of the $2.8 M bill. Tiering is the second-largest lever after coding, and unlike coding it is a policy change, not a rewrite.

Bottlenecks and scaling

Embarrassingly parallel means the work divides into independent pieces with no coordination, so throughput scales linearly with machines. Foreground traffic is what a customer waits on, as opposed to background work the system does for itself, and background work that starves foreground work is an outage even though nothing failed.

The row that needs attention is repair. A rack returning from maintenance generates 10x its own data volume in reads, arriving all at once. Two controls: rate-limit repair with a token bucket (a counter that refills at a fixed rate and is spent one token per unit of work, capping the long-run rate while allowing short bursts), sized as a fraction of each node’s idle bandwidth; and prioritize stripes by how many fragments they are missing: a stripe down 3 of its 4 tolerated failures is worth a hundred stripes down 1, because it is one failure from unrecoverable.

Failure modes

A failure domain is the set of things that die together (a drive, a machine, a rack, a drive model) and the whole placement strategy is making sure a stripe never has more than m fragments inside one domain. Leader election is the protocol by which surviving replicas agree on a new leader when the old one stops answering.

Alternatives rejected

What the design rests on

Move each assumption an order of magnitude in each direction and ask whether the set of boxes changes or only the count of machines inside them. These are the ones that change the boxes:

• Objects are immutable: written once, replaced whole, never edited in place. This is the assumption the erasure-coding choice rests on, and it comes before the cost table, not after. Coding is available only because nothing is modified; the $38.4 M/year saving is what makes it attractive. Allow in-place updates and coding needs a five-node atomic commit per write that cannot even be retried safely, and the design that survives is replication (3x media, $38.4 M/year more) or a database for small records. The coding decision does not survive a mutable workload at any price.
• The average object is 2 MB, far above the 40 KB coding floor. A corpus averaging 4 KB pays 14x instead of 1.4x for coding. The design that survives makes packing objects into extents the primary write path, not an optimization.
• Media cost dominates: $2.8 M/month of drives before any compute. If compute or egress dominated, the storage saving would be noise and triple replication would win on simplicity, 1x repair amplification, and an untouched latency tail.
• The 2-hour repair window. Every durability figure is a function of it; widen it to the 36 hours a dedicated spare node gives and the same code delivers far fewer nines.
• LIST is consistent per page, not across a traversal. If a point-in-time inventory is genuinely required, no synchronous API can supply it at a billion keys; the product that replaces it is a daily manifest generated offline from the metadata.

Everything else (the 2% AFR, the 1-in-1,000 rack outage rate, the concurrent-upload count, archive pricing, the workload rates and drive sizes) scales the numbers without changing the structure.

Summary

Conclusion

An object store is built from one split (a tiny consistent metadata database beside an enormous immutable byte pool) and almost every property follows from it. Immutability is what makes erasure coding buildable, and erasure coding is what makes 200 PB affordable, cutting the media bill to less than half of triple replication while tolerating more failures. The advertised “eleven nines” is not a model output but a model’s nineteen nines minus a correlated-failure haircut, which is why rack-diverse placement and model mixing matter more than the code parameters. Coding is not free: it costs a worse read tail (bought back with k+2 hedging) and a floor on object size (fixed by packing small objects into coded extents). And the interface refuses in-place edits not out of laziness but because a coded overwrite is a non-idempotent five-node transaction, the refusal is the design.

One line to remember: put the 0.0135% of bytes that need ordering and compare-and-swap in a database, code the other 99.9865% because nothing there is ever modified, and read the “eleven nines” as nineteen nines of independence minus the correlated-failure haircut that placement diversity exists to shrink.

Further reading

• Cheng Huang et al., Erasure Coding in Windows Azure Storage, USENIX ATC 2012: the local-reconstruction codes that reduce repair traffic in production.
• Daniel Ford et al., Availability in Globally Distributed Storage Systems, OSDI 2010 (Google): measured correlated failures and why independence models overstate durability.
• Subramanian Muralidhar et al., f4: Facebook’s Warm BLOB Storage System, OSDI 2014: erasure coding for a warm object tier at scale.
• James S. Plank, A Tutorial on Reed-Solomon Coding for Fault-Tolerance in RAID-like Systems, Software: Practice and Experience, 1997: the finite-field arithmetic behind the encoder above.

Related chapters on this site: the client half of this store is the file-storage chapter; the arithmetic habits are in the back-of-the-envelope chapter; the database machinery is in the database-internals chapter; the opposite constraint (a microsecond latency budget where nothing may be eventually anything) is the stock-exchange chapter.