Erasure Coding
Split data into chunks, add parity, and reconstruct after failures.
How Erasure Coding Works
Split data into k chunks, then generate m parity chunks using math over GF(256) — the same Galois field used by Reed-Solomon codes. The encoding matrix is a Cauchy matrix whose top k rows are the identity (so data chunks are just the raw data) and bottom m rows produce parity.
Any k of the k+m total chunks are enough to reconstruct the original data. To decode, pick the k surviving rows from the encoding matrix, invert that submatrix over GF(256), and multiply by the surviving chunks.
The tradeoff: erasure coding costs compute for the math, but saves storage compared to full replication. With k=4, m=2, you get 1.5× overhead instead of 3× for triple replication — and tolerate the same number of failures.
Related: Erasure Coding