Start here: the problem it solves#
TL;DRthe 30-second version
- Disks and machines fail, so a storage system keeps redundant copies. The simplest form is replication: store the same object on three separate disks, and you survive two of them dying.
- Replication is expensive. Three-way replication triples your storage bill and your write bandwidth for every byte you keep.
- Erasure coding gets the same durability for far less. It splits an object into k data shards and computes m parity shards, for n = k + m shards total, and any k of them rebuild the object.
- Losing up to m shards is fully recoverable — the missing shards are computed back from the survivors. Lose m + 1 and the object is gone.
- RS(6,3) survives three failures at 1.5x storage; three-way replication survives two failures at 3x. That is the whole reason erasure coding exists: durability without the copies.
Every storage system has to answer one uncomfortable question: what happens when a disk dies? Disks fail constantly at scale — in a fleet of tens of thousands, several are dead or dying on any given day. A machine loses power, a rack switch fails, a controller corrupts a sector. If your only copy of an object lived on that hardware, the object is gone. So systems keep redundancy: more than one way to get the data back.
The oldest and simplest form of redundancy is replication. Keep three complete copies of every object on three different disks, ideally in three different racks. If one disk dies you still have two copies; if two die you still have one. Reads can go to any copy, and recovery is trivial: copy a surviving replica onto a fresh disk. This is what HDFS did by default for years, and what most databases do for their replicas.
The problem is the bill. Three-way replication means every usable byte costs three bytes of disk, three bytes of write bandwidth, and three bytes of long-term power and cooling. For hot data that is read constantly, paying that is fine, because the extra copies also serve reads. But most stored data is cold: photos from years ago, backups, logs, archives that are almost never read. Paying a 200% storage tax to protect data nobody touches is a lot of money sitting idle.
The idea that already works: a single parity shard#
Start with the smallest version of the idea, the one behind RAID-5. Take an object and split it into a few equal data shards, say four of them: D0, D1, D2, D3. Now compute one extra shard, P, as the exclusive-or of all four: P = D0 xor D1 xor D2 xor D3. Store all five shards on five different disks.
Exclusive-or has a property that makes this work. If any one of the five shards is lost, you can rebuild it from the other four by xor-ing them together. Lose D2, and D2 = D0 xor D1 xor D3 xor P. Lose the parity P, and you just recompute it from the data. Either way, one lost shard out of five is always recoverable, and the cost was one extra shard for four data shards — 1.25x storage instead of replication's 2x for the same one-failure tolerance.
That is the entire spirit of erasure coding: redundancy stored as a computed combination of the data rather than as a copy of it. The single-parity scheme has one clear limit, though. It survives exactly one failure. If two disks die at once, xor gives you two unknowns and only one equation, and you cannot solve it. To survive m failures at once you need m independent parity shards, and plain xor can only give you one.
The mechanism: k data shards, m parity shards, any k rebuild it#
A Reed-Solomon code is described by two numbers, k and m. The object is split into k equal data shards. From those, the code computes m parity shards. Together that is n = k + m shards, and the defining guarantee is this: any k of the n shards are enough to rebuild the original object. It does not matter which k survive — any k data shards, any k parity shards, or any mix. That is why up to m losses are always survivable.
- Split: cut the object into k data shards of equal size. Because the code is systematic, these shards are just the raw object sliced up, so a normal read that finds all k data shards needs no decoding at all.
- Encode: compute each of the m parity shards as a distinct weighted combination of the k data shards, using arithmetic in a finite field so the mixes stay independent.
- Distribute: place all n shards on different disks, machines, and racks, so no single failure can take out more than one shard of the stripe.
- Recover: if some shards are lost, gather any k of the survivors, solve the k linear equations they represent, and the original data shards fall back out — then recompute any lost parity from them.
The finite field is the part that makes the parity shards independent. Reed-Solomon works over a Galois field, usually GF(256), where every byte is treated as an element you can add, multiply, and divide with the results always landing back in a single byte. Each parity shard is computed with its own set of field coefficients, so the m parity equations are linearly independent of each other and of the data. The specific field arithmetic is not the insight to carry away — the property to remember is that k independent equations recover k unknowns, so any k shards reconstruct the whole.
The object is split into 4 data shards; 2 parity shards are mixed from them. Any 4 of the 6 survive to rebuild it.
Because the code is systematic, the k data shards hold the object verbatim. In the common case where nothing has failed, a reader just concatenates the k data shards and is done — the parity is never touched. Parity only comes into play when a shard is missing, and then the reader pulls whichever k shards it can find and decodes. This is why erasure-coded reads are cheap when healthy and more expensive only during repair.
Go deeperWhy any k shards suffice: the linear-algebra view
Think of encoding as multiplying the vector of k data shards by an n-by-k matrix. The top k rows are the identity, which is why the data shards come out unchanged (the systematic part). The bottom m rows are the coding coefficients that produce the parity shards. Each shard is therefore one linear equation in the k unknown data values.
Recovery is solving that system. Pick any k surviving shards; they give you k equations. As long as those k rows of the matrix are linearly independent, the k-by-k system has a unique solution, and inverting it returns the original data. Reed-Solomon chooses its matrix (a Vandermonde or Cauchy matrix over the field) precisely so that every k-by-k submatrix is invertible. That is the algebraic reason any k of the n shards are guaranteed to work.
This optimality has a name: Reed-Solomon is a Maximum Distance Separable (MDS) code, meaning an (n, k) code tolerates exactly n − k = m erasures, the most any code can for that storage. You cannot survive more failures without either more parity or more copies.
A worked example: encode, lose two, rebuild#
Take an eight-byte object and an RS(4,2) code. Split it into four data shards of two bytes each, then compute two parity shards from them. You now have six shards spread across six disks, and the object survives any two failures.
- Encode: D0, D1, D2, D3 are the four raw two-byte slices. P0 and P1 are each a Reed-Solomon mix of all four, so they hold no readable text — only redundancy.
- Fail: two disks die, taking D1 and P0 with them. Four shards survive: D0, D2, D3, and P1. That is exactly k = 4, the minimum needed.
- Reconstruct: gather the four survivors, solve their four coding equations for the four data values, and D1 comes back byte for byte. P0 is then recomputed from the recovered data.
- The object is whole again, having survived losing a third of its shards, at a storage cost of 1.5x rather than replication's 3x.
Now push it one failure further to see the boundary. Suppose three disks die instead of two, taking D1, D2, and P0. Only three shards survive, and the code needs four. Three equations cannot solve for four unknowns, so there is no way to recover — the object is lost. This is the hard cliff of a k-of-n code: it protects perfectly up to m losses and fails completely at m + 1. There is no graceful degradation, no partial object. You either have k shards or you do not.
PredictWith RS(4,2), you lose both parity shards P0 and P1 but all four data shards survive. Is the object recoverable, and does it need decoding?
Hint: Count the survivors against k, and remember the code is systematic.
Yes, and it needs no decoding at all. Four shards survive, which meets k = 4, so the object is recoverable. And because the code is systematic, the four survivors are exactly the data shards D0..D3 — the raw object itself. The reader just concatenates them; no linear system to solve. Losing both parity shards costs you future fault tolerance (you now have zero redundancy until they are recomputed), but the data was never in danger. This is the everyday healthy-read case: as long as all k data shards are present, a read is a plain concatenation.
Storage, speed, and the repair cost#
The headline number is storage overhead, which is simply n/k. RS(4,2) is 6/4 = 1.5x; RS(6,3) is 1.5x while surviving three failures; RS(10,4) is 1.4x surviving four; RS(17,3) is about 1.18x surviving three. Every one of these beats three-way replication's 3x, and wider codes push the overhead down toward 1x while keeping strong fault tolerance.
- Storage overhead is n/k — the total shards divided by the data shards. Pick k and m to hit your target overhead and fault tolerance; RS is MDS, so you always survive exactly m = n − k losses.
- Encoding cost is a matrix multiply over the field: computing m parity shards from k data shards. It is linear in the data size and done once at write time.
- A healthy read is free of decoding: with all k data shards present, the object is just their concatenation. Only a degraded read (some data shard missing) pays for a decode.
- A decode or repair must read k full shards to rebuild one lost shard. That is the real tax: repairing a single failed disk pulls k shards' worth of data across the network, versus replication's single copy.
Variants and relatives
- RAID-5 is single-parity erasure coding (m = 1) over a set of disks: one xor parity, survives one disk failure. RAID-6 is m = 2, using a second Reed-Solomon parity so it survives two.
- Systematic vs non-systematic: a systematic code keeps the data shards as raw slices (so healthy reads skip decoding); a non-systematic code stores only coded shards and always decodes. Almost all production systems use systematic codes.
- Local Reconstruction Codes (LRC), used in Azure Storage, add extra local parity so the common case — repairing one lost shard — reads only a small local group instead of all k, cutting repair bandwidth at a small storage cost.
- Regenerating codes trade a little storage for provably minimal repair traffic, a research direction aimed squarely at erasure coding's repair-amplification problem.
- The field size sets the maximum stripe width: GF(256) supports up to 255 shards in a stripe, which is far more than any practical k + m.
Strengths, limits, and when to reach for it
Erasure coding makes a clear bargain against replication: dramatically less storage for the same or better durability, paid for with higher repair bandwidth, higher read latency when degraded, and a hard failure cliff.
- Storage efficiency — the headline win. RS(6,3) gives three-failure durability at 1.5x storage, where surviving three failures with replication needs 4x. On a large fleet this is the difference between one and three data centers of disk.
- Tunable durability — choose k and m to set exactly how many simultaneous failures you survive and how much overhead you pay. There is no such dial with fixed replication.
- Repair cost — the main limit. Rebuilding one lost shard reads k shards' worth of data, so recovery after a failure is bandwidth-heavy and slower than replication's single copy. Local codes soften this.
- Degraded-read latency — when a data shard is missing, a read must fetch k shards and decode instead of reading one replica, adding latency and cross-node traffic on the failure path.
- The cliff — protection is perfect up to m losses and total at m + 1. Correlated failures (a rack losing power, a bad batch of drives) that take out m + 1 shards of one stripe destroy the object, so shard placement across failure domains is essential.
Erasure coding vs replication
| 3-way replication | RS(6,3) erasure coding | |
|---|---|---|
| Failures survived | 2 | 3 |
| Storage overhead | 3x | 1.5x |
| Healthy read | read 1 copy | concatenate k data shards |
| Repair traffic (1 loss) | copy 1 replica | read k shards, decode |
| Update in place | cheap (rewrite copies) | expensive (re-encode stripe) |
| Best for | hot, small, mutable data | cold, large, immutable data |
The two are not rivals so much as tools for different data temperatures. Replication is simple, fast to repair, and cheap to update, but its storage cost scales with the number of copies. Erasure coding is storage-optimal and tunable, but repair and updates are expensive. Large systems use both: replicate hot and recently-written data, then convert it to erasure coding as it ages and cools.
Note the update column especially. Changing one byte of an erasure-coded object means recomputing the parity shards for its whole stripe, because each parity depends on all k data shards. That is why erasure coding is aimed at immutable, write-once data, while anything mutated in place stays replicated.
Where erasure coding runs in the wild
- HDFS — since Hadoop 3, erasure coding is built in, with RS(6,3) as a standard policy: 50% storage overhead surviving three failures, versus 200% for the old three-way replication default. It is applied to cold data while hot data stays replicated.
- Facebook f4 — the warm BLOB store uses RS(10,4), laying shards across racks so it survives disk, machine, and rack failure while cutting the storage the old replicated store needed. It held tens of petabytes in production.
- Backblaze — its Vaults use RS(17,3): 17 data plus 3 parity, tolerating three failures at roughly 1.18x storage. Backblaze open-sourced its Reed-Solomon implementation.
- Azure Storage — uses Local Reconstruction Codes, an erasure-coding variant that adds local parity groups so the common single-shard repair reads only a few shards instead of all k.
- Ceph and most object stores — offer erasure-coded pools alongside replicated ones, letting operators pick the trade per pool: replicate the hot pool, erasure-code the archive pool.
Common misconceptions & gotchas
Do the parity shards contain readable copies of the data?
No. A parity shard is a field-arithmetic mix of all k data shards, so it looks like noise and holds no readable slice of the object on its own. It carries only the redundancy needed to solve for a missing shard. That is why a healthy read touches only the data shards: the parity is useless as data and useful only for reconstruction.
Does losing more shards degrade the object gradually?
No — the failure is a cliff, not a slope. Up to m losses, the object is recovered perfectly with every byte intact. At m + 1 losses, there are fewer than k survivors, the linear system is unsolvable, and the object is completely gone. There is no partial recovery. This is why placing shards across independent failure domains matters so much: you must avoid any single event knocking out m + 1 shards of one stripe.
Why not just use erasure coding for everything?
Because repair and updates are expensive. Rebuilding one lost shard reads k shards and decodes, so recovery is bandwidth-heavy; and updating any byte forces re-encoding the whole stripe's parity. For hot, small, or frequently-updated data, replication is faster to repair, cheaper to update, and its extra copies also serve reads. Erasure coding wins on cold, large, immutable data where storage cost dominates.
Is more parity always better?
More parity means more fault tolerance and more storage and more repair cost, so it is a trade, not a free win. You choose m from your failure model: how many correlated failures could plausibly hit one stripe before repair completes. Beyond that, extra parity is wasted space. Real systems cluster around m = 2 to 4.
QuizAn RS(10,4) stripe currently has 4 shards lost. A fifth disk holding one of its shards now fails before repair finishes. What happens?
- The object is lost — only 9 shards survive, below the k = 10 needed
- Nothing — RS(10,4) survives any number of failures
- The object is fine because 4 parity shards can fix 5 losses
- Half the object is recoverable
Show answer
The object is lost — only 9 shards survive, below the k = 10 needed — RS(10,4) has n = 14 shards and survives up to m = 4 losses, because any k = 10 must survive to decode. With 4 already lost, exactly 10 remain — the minimum. A fifth loss drops survivors to 9, below k, so the linear system is unsolvable and the object is gone. This is the hard boundary of a k-of-n code, and it is why systems race to repair a degraded stripe before another failure lands, and why shards are spread across failure domains to keep correlated failures from crossing the m threshold.
In an interview
Lead with the problem and the one-line win. Replication protects data by keeping whole copies, but three-way replication costs 3x storage. Erasure coding gets the same or better durability far cheaper: split an object into k data shards, compute m parity shards, and any k of the n = k + m shards rebuild it — so RS(6,3) survives three failures at 1.5x storage instead of 3x.
Then give the mechanism in three moves. First, split the object into k equal data shards. Second, encode m parity shards as independent weighted mixes of the data over a finite field, so any k shards form a solvable system. Third, to recover, gather any k survivors and solve for the originals; because the code is systematic, a healthy read with all k data shards present just concatenates them and skips decoding entirely.
If pushed, name the trade-offs and the real systems. The costs are repair bandwidth (rebuilding one shard reads k shards) and expensive in-place updates (re-encoding the stripe), which is why erasure coding is for cold, immutable data while hot data stays replicated. Cite HDFS RS(6,3), Backblaze RS(17,3), and Facebook f4 RS(10,4), and mention Local Reconstruction Codes as the standard fix for repair cost. Then open the simulator: encode a stripe, fail m shards and watch reconstruction rebuild them, then fail one more to hit the unrecoverable boundary.
References & further reading
- Apache Hadoop — HDFS Erasure Coding — the official design: RS(6,3) and RS(10,4) policies, systematic codes, and the 50% vs 200% overhead comparison
- Cloudera — Introduction to HDFS Erasure Coding in Apache Hadoop — a readable walkthrough of the storage-overhead and durability trade versus replication
- Muralidhar et al. — f4: Facebook's Warm BLOB Storage System (OSDI 2014) — production RS(10,4) across racks; the design goals and failure model of a warm store at scale
- Backblaze — Reed-Solomon erasure coding, open sourced — an approachable explanation of RS math plus the RS(17,3) Vault design at 1.18x overhead
- Huang et al. — Erasure Coding in Windows Azure Storage (USENIX ATC 2012) — Local Reconstruction Codes: adding local parity to cut the repair-bandwidth cost of plain Reed-Solomon
Ready to try it?
The simulator is a real, deterministic implementation — pick a scenario and step through it, scrubbing the timeline forward and backward through every change.