The nicest failure in a storage system is the one that leaves a note.

A disk vanishes. A host stops answering. An object shard times out. The system knows which piece failed to arrive. Annoying, yes. Mysterious, no.

That distinction is where Reed-Solomon coding gets its leverage. If the holes are named, the decoder does not have to play detective. It only needs enough surviving equations to fill them.

The bargain is small enough to fit on a label stuck to a drive tray:

split the file into k data shards
compute m parity shards
store n = k + m shards
recover from any m missing shards

The dangerous word is “any.”

A Missing Disk Is Polite

The Hamming-code story is about an unknown bit flip. Something arrived, but one position may be wrong. The decoder has to locate the bad coordinate and repair it.

The storage story is often kinder. A disk, host, rack, or object shard is missing. The system can point at the empty chair.

Reed and Solomon’s 1960 paper described polynomial codes over finite fields: take a message as coefficients of a polynomial, evaluate it at many field points, and use the redundancy to recover from corruption or loss.1 In the erasure-only case, the idea can be said in one line:

a degree k-1 polynomial is determined by any k points

In modern storage, the “points” are byte columns in shards. Each byte is an element of a finite field such as GF(256). Addition is XOR. Multiplication is table-driven arithmetic modulo an irreducible polynomial. The code in the lab uses the common GF(256) polynomial 0x11d.

This is not ordinary integer arithmetic. It is arithmetic where every nonzero byte has an inverse. That inverse is what lets recovery be matrix inversion instead of a special case for every failure pattern.

Keep the Data, Add the Equations

The polynomial picture is elegant but not always how you want to store data. If every shard is an evaluation, even reading an intact file requires decoding. Storage systems usually prefer systematic codes:

D0 D1 D2 ... D(k-1) are the original data shards
P0 P1 ... P(m-1) are parity shards

The lab constructs this form directly.

First, build a Vandermonde matrix over GF(256):

\[V_{i,j} = x_i^j.\]

Any \(k\) rows are invertible when the \(x_i\) are distinct, which is the Reed-Solomon maximum-distance-separable property in matrix clothing. Then multiply every row by the inverse of the first \(k\) rows. The top block becomes identity, so the first \(k\) encoded shards are the original data shards. The MDS property survives because multiplying by an invertible matrix does not change row independence.

That gives a generator matrix:

\[G = \begin{bmatrix} I \\ P \end{bmatrix}.\]

Encoding a stripe is:

\[\text{shards} = G \cdot \text{data}.\]

Decoding after erasures is:

  1. choose any \(k\) surviving shard rows;
  2. invert that \(k \times k\) submatrix of \(G\);
  3. multiply the surviving shard bytes by that inverse;
  4. get the original data shards back.

Plank and Ding’s correction note to the classic Reed-Solomon RAID tutorial says the desired storage matrix has identity in the first data rows and remains invertible after deleting any parity-count rows; it derives such a matrix from a Vandermonde matrix by elementary operations.2 That is exactly the shape this lab uses.

Break the Stripe on Purpose

The lab below is not a cartoon of Reed-Solomon. It performs the GF(256) work: encode a small deterministic byte payload, erase selected shards, reconstruct from surviving rows when enough rows remain, and check a recovered-payload checksum.

It also draws a deliberately simple reliability curve. The curve assumes independent shard losses at probability \(p\). Real storage failures are not that clean: racks fail together, repairs take time, latent sector errors exist, operators make correlated mistakes, and placement policy matters. Treat the curve as a calculator for the combinatorics, not as a datacenter availability model.

Data shard Parity shard Missing Recovered or selected

The encoder is systematic Reed-Solomon over GF(256). The reliability curve assumes independent shard losses and does not model repair time, placement, correlated rack failures, checksums, or silent corruption.

The default run is a 5+3 stripe: five data shards, three parity shards, 1.60x storage overhead. The cluster pattern erases D3, D4, and P0. The decoder chooses D0, D1, D2, P1, and P2, inverts those rows, and rebuilds the original payload checksum exactly.

At the toy independent shard-loss probability p = 6%, the lab reports:

raw five-shard file loss:  26.61%
5+3 RS stripe loss:        0.0746%

Those are not operational availability claims. They are the binomial shape of the promise: a raw striped file dies if any required shard dies; a 5+3 erasure-coded stripe dies only if four or more of the eight shards are missing before repair.

Push Erased shards from 3 to 4. The decoder refuses to recover. That is not a bug. With only four surviving shards and five unknown data shards, there are not enough independent equations.

Push Parity shards to 5. The storage overhead rises to 2.00x, while the displayed independent-loss probability drops again because the stripe can tolerate five missing shards. Redundancy is a knob, not a blessing.

Change Erasure pattern to parity first. Losing only parity is boring: reads of the current file can still use the data shards. It matters for future fault tolerance because the stripe is now living without its buffer.

What Any k Really Promises

The lab’s recovery path is intentionally blunt. It does not use a specialized decoder. It does this:

take k surviving generator rows
invert the k by k matrix over GF(256)
multiply the surviving shards by that inverse

The invariant sweep I ran for the lab checked every allowed subset for data shard counts 3..8 and parity counts 1..5: 4,915 generator submatrices were invertible. Across the four erasure-pattern modes, it also ran 480 exact recoveries and 660 over-budget erasure cases that correctly failed.

That is the point of an MDS code. With \(n=k+m\), the minimum distance is \(m+1\). For erasures, known missing locations, it can tolerate \(m\) missing symbols. It cannot tolerate \(m+1\) missing symbols without additional information, because fewer than \(k\) equations remain.

The algebra is sharp. The operational system around it is not.

The Datacenter Is Not a Coin Flipper

Rabin’s Information Dispersal Algorithm framed the storage version beautifully: break a file of length \(L\) into \(n\) pieces, each of length \(L/m\), so that any \(m\) pieces reconstruct the file; the total stored length is \((n/m)L\), which can be close to the original file size.3

That space efficiency is why erasure coding shows up in cold and warm storage. Facebook’s f4 warm BLOB store, for example, used Reed-Solomon 10+4 coding within a datacenter, placed blocks across racks, and reported large storage savings relative to replication.4

But the production problem is larger than “can I invert the matrix?”

Placement decides whether a rack failure looks like one erasure or many. Repair speed decides how long the stripe remains vulnerable after the first loss. Checksums and scrubbing decide whether a supposed survivor is actually trustworthy. Network topology decides how expensive reconstruction is. Hot objects may prefer replication because reads are cheap and repairs are simple. Cold objects may prefer erasure coding because bytes at rest dominate.

This is why the lab keeps the algebra in one hand and the reliability story in the other. The algebra says:

any k good shards determine the stripe

The system has to make “good” and “any” credible.

Do Not Let a Bad Shard Pretend

One last warning matters.

An erasure decoder assumes the missing locations are known. If a shard is present but wrong, the simple erasure decoder may confidently solve the wrong system. Reed-Solomon codes can also be used for unknown errors, but the budget changes: unknown errors cost roughly twice as much as named erasures.

Storage systems usually handle this by making silent corruption visible before erasure decoding: checksums, authenticated hashes, scrubbing, versioning, and end-to-end verification. A shard should either be trusted as an equation or declared missing.

The clean mental model is:

erasure coding is not backup
parity is not a checksum
reconstruction is not validation

Reed-Solomon is the algebraic core. It tells you how to recover when enough honest pieces remain. The storage system around it exists to make that sentence true when the day is loud, partial, and already going sideways.

  1. I. S. Reed and G. Solomon, “Polynomial Codes Over Certain Finite Fields”, Journal of the Society for Industrial and Applied Mathematics, 1960. DOI record: SIAM. ↩

  2. James S. Plank, “A Tutorial on Reed-Solomon Coding for Fault-Tolerance in RAID-like Systems”, Technical Report CS-96-332, 1996/1997; James S. Plank and Ying Ding, “Note: Correction to the 1997 Tutorial on Reed-Solomon Coding”, UT-CS-03-504, 2003. ↩

  3. Michael O. Rabin, “Efficient Dispersal of Information for Security, Load Balancing, and Fault Tolerance”, Journal of the ACM, 36(2), 1989. DOI: 10.1145/62044.62050. ↩

  4. Subramanian Muralidhar et al., “f4: Facebook’s Warm BLOB Storage System”, OSDI 2014. ↩