Erasure Coding

Erasure coding is a method of encoding data with redundant information so the original can be recovered when some stored fragments are missing or unavailable. Instead of keeping complete duplicate copies, it stores data fragments and mathematically generated redundancy. It is used in distributed and object storage to balance storage capacity against the resources needed to protect and recover data.

How Erasure Coding Works

Storage systems commonly divide a unit of data into fragments and calculate additional redundant fragments, often called parity. They distribute these fragments across disks or nodes. Parity is derived from the data; it is not a separate full copy of it. Splitting data across devices, sometimes called striping, spreads storage work but provides no redundancy by itself.

When a fragment is lost or unavailable, the system reads enough surviving fragments and uses the code's mathematical relationships to reconstruct the missing information. The amount and combination of fragments needed depend on the code. Erasure coding therefore has a finite recovery limit: if too many fragments are unavailable, the remaining information is insufficient to restore the original data.

Failure Tolerance and Fragment Placement

The configured redundancy determines which fragment losses a system can withstand, but fragment tolerance is not automatically disk or node tolerance. If several fragments from the same encoded data unit sit on one node, that node's failure can remove several fragments at once. Placement across independent failure domains, such as separate nodes or racks, reduces exposure to a shared failure.

Erasure coding must therefore be considered together with placement policy. Protection against a rack outage requires appropriate distribution across racks, not merely across disks within one rack. As fragments become unavailable, the margin for further failures shrinks until repair restores redundancy. Rebuilding requires reading surviving fragments and writing replacements; it does not inherently preserve data locality or avoid performance impact.

Erasure Coding vs. Replication

• Storage Capacity: Replication stores complete copies, while erasure coding stores encoded redundancy that can provide comparable failure tolerance with less capacity. The actual saving depends on the code, replication factor and placement assumptions.
• Processing and Writes: Encoding adds computation, and frequent small updates may require reading and rewriting multiple fragments. Write-intensive workloads are therefore not automatically a good fit.
• Recovery Resources: A replica can supply an intact copy, whereas reconstruction may require reads from several locations and decoding. Network traffic, disk I/O and processing can compete with normal operations during repair.
• Total Cost and Workload: Lower capacity overhead does not guarantee lower total cost or better performance, and infrequent access alone does not establish suitability. Object size, update patterns, recovery load and implementation all affect the trade-off.

Integrity Checking and Recovery Limits

Erasure coding is not a substitute for integrity checking. Missing fragments are known erasures, but silently corrupted fragments may still appear available. Systems need an integrity mechanism, such as checksums, to identify damaged fragments before excluding them from recovery.

Once corruption is identified, affected fragments can be treated as erasures and reconstructed if enough valid fragments remain. The code alone does not guarantee detection or correction of arbitrary silent corruption. Redundancy also does not replace backups or version history: a deletion or unwanted change can be applied consistently to all encoded fragments. Recovery depends on retaining sufficient valid information, not simply on having parity stored somewhere.

A Four-Plus-Two Example

In an illustrative maximum-distance-separable code with four equal data fragments and two equal redundancy fragments, any four valid fragments can reconstruct the data. The six fragments use 1.5 times the original data capacity before metadata, padding and other implementation overhead. Losing two fragments is tolerable in this example; losing two nodes is tolerable only if their placement removes no more than two fragments from the same encoded unit.

Reed–Solomon is a family of codes commonly used for this purpose. MDS describes a mathematical recovery property rather than a separate product, while RAID describes storage arrangements that may use parity techniques. Object stores and distributed storage systems apply such coding alongside placement, integrity and repair policies. The capacity arithmetic explains potential savings, but it does not establish overall cost or performance superiority for a particular workload.