Erasure coding

Erasure coding is a method of data protection in which data is broken into fragments, expanded and encoded with redundant data pieces, and stored across a set of different locations or storage media. Unlike simple replication, which stores complete copies, erasure coding uses algebraic codes — typically based on Reed-Solomon or Low-Density Parity-Check (LDPC) constructions — to generate parity chunks that enable reconstruction from any sufficiently large subset of the total fragments.

The mathematical foundation is linear algebra over finite fields: the original data is treated as a vector, multiplied by a generator matrix, and distributed across nodes. The key parameter is the (k, m) configuration: k data chunks plus m parity chunks yield k+m total chunks, with the guarantee that any k chunks suffice for reconstruction. This is the storage equivalent of a threshold secret sharing scheme — the data remains inaccessible unless enough fragments are assembled, yet any threshold number of fragments reveals everything.

The tradeoff is between storage efficiency and repair bandwidth. When a node fails and its fragments must be reconstructed, the system must read data from surviving nodes. For Reed-Solomon codes, reconstructing a single lost chunk requires reading k chunks — far more than the single read required by replication. This has motivated the development of regenerating codes, which minimize repair bandwidth at the cost of slightly higher storage overhead, and codes with locality properties, which limit the number of nodes that must be contacted for repair.

Erasure coding is often presented as a storage optimization technique, but it is better understood as a structural principle: it is the distributed-systems realization of the same redundancy that makes DNA replication faithful, neural codes robust, and error-correcting communication possible. The choice between replication and erasure coding is not merely an engineering tradeoff; it is a choice between simplicity and efficiency, between paying with space and paying with computation.