Erasure Coding vs Replication

Three Copies Is Expensive

In Distributed File Systems you kept every chunk on three machines. That ×3 replication is wonderfully simple and it survives two machine deaths — but look at the invoice. To store 1 PB of data you buy and power 3 PB of disk. Two-thirds of your storage fleet exists purely as insurance, holding bytes you already have. At a laptop's scale nobody notices. At a data center's scale, that is the single biggest line item in the budget, and doubling it to survive one more failure (×4, ×5) is brutal.

So here's the question this whole lesson answers: is there a way to survive machine death without paying for a full extra copy of everything? There is, and it's one of the prettiest pieces of engineering math in the whole field — erasure coding. It buys the same durability as replication for a fraction of the storage. Here are the two schemes side by side; the rest of the lesson earns every number on this page.

Two ways to survive the same failures, at very different prices. On the left, REPLICATION: one object drawn as three identical full copies on three machines — durable against two losses, but it stores three petabytes of disk for every one petabyte of data, an overhead of 3.0 times. On the right, ERASURE CODING: the same object split into ten data shards plus four computed parity shards, fourteen pieces spread across fourteen machines, where any ten of the fourteen rebuild the whole object — so it also survives four losses, but stores only 1.4 petabytes of disk per petabyte of data, an overhead of 1.4 times. A bar under each scheme compares the storage bill: replication's bar towers at 3.0 times while erasure coding's sits at 1.4 times. The bottom line: the same durability, a fraction of the storage — which is why cold, large data at petabyte scale is erasure-coded, not replicated.

Parity: Survive a Loss Without a Full Copy

Start with the smallest possible version of the trick. Instead of a second copy of a block, keep one extra block that is the XOR of all the others. XOR (^) has a magic property: it's its own inverse. If P = D0 ^ D1 ^ D2, then any single block equals the XOR of everything that's left — D1 = D0 ^ D2 ^ P. Lose a block, and you recompute it from the survivors. No copy needed.

That's not a story — it's arithmetic, and here it is running for real on three data blocks plus one parity block:

3 data blocks + 1 parity  →  4 shards,  overhead 1.33×    (a mirror copy would be 2.0×)
parity  =  D0 ^ D1 ^ D2

💀  lose D1
reconstruct = D0 ^ D2 ^ P   =   'WORLD___'
recovered == original D1 ?   True

One extra block — not a whole second copy — bought a full failure of tolerance. The overhead is 1.33× (four shards for three blocks of data) instead of the 2.0× a mirror would cost. That is the entire idea of erasure coding in one line: the parity is a function of the data, and any lost piece is a function of what remains. This exact scheme, one parity block over a stripe, is what RAID-5 does across the disks in a single box.

XOR parity survives exactly one loss, though — XOR a second missing block against the parity and you have one equation with two unknowns. To survive two, three, four losses we need more parity, and parity that's cleverer than a plain XOR. That's Reed-Solomon.

Reed-Solomon: k Data, m Parity, Any k Reconstruct

Reed-Solomon is the general form. Take your object, split it into k data shards, and compute m parity shards — k + m shards in all. The guarantee is the beautiful part: any k of the k+m shards reconstruct the entire object. So you can lose any m shards — data shards, parity shards, any mix — and still rebuild everything. (The math is polynomial arithmetic over a finite field, GF(2⁸); XOR parity is just Reed-Solomon with m = 1, and RAID-6 is m = 2.)

That "any m" is worth pausing on, because it kills a common misconception: you do not have to keep the parity shards safe and only lose data shards. Every shard is equal. Lose four out of fourteen — even if two of them were parity — and the surviving ten still contain enough information to recompute all four.

This isn't a whiteboard claim. par2 (the Parchive tool) is a real Reed-Solomon codec; here it is guarding a 6 MB object, then repairing it after we take a hammer to the middle of the file:

$ head -c 6M /dev/urandom > data.bin                 # a 6 MB "object"
$ par2create -r50 data.bin                           # Reed-Solomon parity, ~50% redundancy
    made: data.bin.par2, data.bin.vol0000+NN.par2    (5.3M of parity guarding 6.0M of data)

$ dd if=/dev/zero of=data.bin seek=2000000 \
     count=1500000 conv=notrunc                      # 💥 corrupt 1.5 MB in the middle
    md5 changed:  YES

$ par2repair data.bin.par2
    Repair is required.
    Repair is possible.
    → restored bit-for-bit:  YES ✓

It rebuilt the destroyed 1.5 MB exactly — the same md5 it had before — using nothing but the parity. That is the identical math S3, Ceph, and HDFS erasure coding run at petabyte scale, sitting right there on one machine. And the overhead is simply the count: k + m shards for k shards of data, so (k+m)/k. RS(10,4) is 14/10 = 1.4× and survives 4 losses.

Here's the mechanism in one picture — split, lose any m, decode from any k:

How Reed-Solomon rebuilds a lost shard. Across the top, an object is split into ten data shards, d0 through d9, drawn in blue, plus four parity shards, p0 through p3, drawn in amber — fourteen shards total, each on its own machine. In the middle, four of them are struck out with skulls: two data shards and two parity shards are gone, four simultaneous losses. Below, an arrow shows the ten surviving shards feeding into a Reed-Solomon decode box, which recomputes the four missing shards exactly. At the bottom, the verdict from a real par2 run: 5.3 megabytes of parity guarded 6.0 megabytes of data, 1.5 megabytes were corrupted, and the repair restored the object bit-for-bit. The rule stated plainly: with k data and m parity shards, any k of the k-plus-m reconstruct everything, so you survive the loss of any m shards — data or parity, it does not matter which.

Durability per Dollar

Now put the two schemes on the same failure budget and read the storage bill. This is the whole point of erasure coding, and it's stark:

survive 2 losses:   replication ×3 = 3.0×    vs    RS(4,2) = 1.5×   ·   RS(10,2) = 1.2×
survive 4 losses:   replication ×5 = 5.0×    vs    RS(10,4) = 1.4×   (same durability, ~3.6× less)

Read the bottom row again. To survive four simultaneous failures with replication you keep five copies — 5.0× the storage. Reed-Solomon(10,4) survives the same four losses at 1.4×. Same durability, ~3.6× less disk. On a 1 PB dataset that's the difference between buying 5 PB and buying 1.4 PB — at cloud prices, tens of thousands of dollars a month, every month, forever.

The overhead knobs are just two formulas — replication = N×, erasure coding = (k+m)/k — but the feel of the trade is easier to grab by hand than by formula. Drive it: pick a scheme, tune the shards, and kill machines until it breaks.

Buy durability two ways and watch the bill. Pick REPLICATION and choose N copies, or ERASURE CODING and choose k data + m parity shards — the scoreboard shows the storage overhead, how many simultaneous losses you survive, the read cost, and the monthly bill per petabyte. Then click shards to kill them: lose no more than you can afford and it reconstructs from the survivors; lose one too many and it goes DATA LOST. Set erasure coding to survive the same failures as ×3 replication and watch the storage bill collapse — then notice the read-cost meter climb from 1 shard to k. That is the whole trade in one widget.

The Catch: Reads and Rebuilds Cost More

If erasure coding is so much cheaper, why does anything still replicate? Because that cheap storage isn't free — you pay it back on reads and rebuilds.

A degraded read is expensive. With replication, a read touches one shard — grab any surviving copy, done. With erasure coding, as long as every data shard is healthy the read is fine (a systematic code stores the data shards verbatim, so you read them directly). But the moment a needed shard is missing, you must fetch k shards and run the decode to reconstruct it — for RS(10,4) that's 10 reads and a CPU pass to serve what replication served from one disk. More I/O, more latency, more CPU.
Rebuilding a lost shard amplifies. When a machine dies and you need to recreate its shard, erasure coding reads k shards across the network to compute the one — RS(10,4) reads 10 shards to rebuild 1. Replication just copies a single surviving replica. So a big EC cluster losing a node moves far more data to heal than a replicated one.
Small objects hurt. Splitting a 4 KB object into 10 shards makes ten tiny fragments scattered across ten machines, plus parity — the per-shard bookkeeping and the k-way read swamp the tiny payload. Erasure coding wants big objects.

So the rule writes itself. Erasure-code data that is large, cold, and read rarely — where storage is the dominant cost and the occasional expensive rebuild is fine. Replicate data that is small, hot, and latency-sensitive — where a one-shard read and a trivial recovery are worth the extra copies. And a very common pattern is both in sequence: replicate while hot, then re-encode to erasure coding as it ages cold.

(Two more traps while we're here. "More parity is always better" — no; each parity shard adds overhead and rebuild cost, so you size m to the failures you expect during a repair window, not to infinity. And "replication is obsolete" — also no; it stays the right tool for hot, small data, which is why every real system runs both.)

Where Each Wins (and a Word on RAID)

This trade is running under storage you use every day. Amazon S3 and its cheaper tiers (S3 Infrequent Access, Glacier), Azure, and Google's Colossus erasure-code cold and warm data; HDFS erasure coding, Ceph EC pools, and Backblaze vaults (a 17+3 layout) run it at the storage layer; and Facebook's f4 warm-BLOB store famously uses RS(10,4) = 1.4× for photos and videos that are rarely re-read. The hot path in front of all of them — the replicas serving live traffic — stays replicated. Cold and huge, code it; hot and small, copy it.

One piece of family history. RAID is erasure coding's single-machine ancestor: the same idea spread across the disks of one box instead of across a data center. RAID-0 stripes with no parity (pure speed, zero durability); RAID-1 mirrors (that's replication ×2); RAID-5 keeps one parity block (XOR — survives one disk); RAID-6 keeps two (survives two). Distributed erasure coding is really just "RAID across the network."

And one warning that has saved careers: RAID and erasure coding are not backups. They survive a disk or machine failure — nothing else. They will happily replicate your rm -rf, your buggy migration, your ransomware, and your data-center fire across every shard, faithfully and instantly. Durability against hardware death is not the same thing as recoverability from mistakes. You still need real backups, versioning, and off-site copies.

What to Remember

⭐ Durability costs money, and you pay it one of two ways. Replication keeps N full copies — survive N−1, overhead N×, reads touch 1 shard, recovery just copies a survivor. Erasure coding keeps k data + m parity — survive any m, overhead (k+m)/k, reads on a loss touch k shards, recovery reads k to rebuild 1.
⭐ The math builds up cleanly. XOR parity (one parity block, survive 1, RAID-5) is Reed-Solomon with m=1; general Reed-Solomon(k, m) gives you any-m durability — measured, par2 restored a corrupted 1.5 MB bit-for-bit from parity alone.
⭐⭐ Same durability, a fraction of the storage. To survive 4 losses: replication needs 5.0×; RS(10,4) needs 1.4× — roughly 3.6× less disk for identical failure tolerance. At petabyte scale that's the storage budget.
But EC isn't free. Degraded reads and rebuilds cost k shards + CPU, and small objects hurt — so erasure-code cold/large data, replicate hot/small data (often replicate hot, then re-encode cold).
Neither is a backup. RAID/EC survive disk failure, not deletion, corruption, or disaster.

You now know how to store a petabyte durably and cheaply. But we've been hand-waving how the petabyte gets in — you don't PUT a 4 GB video in one shot over a flaky network and hope. Next, Media Chunking: uploading enormous objects in pieces, resuming after a drop, and stitching them back together — the polite way to move big things.