Erasure Coding

An erasure code transforms k data fragments into k + m total fragments. Any k suitable fragments can reconstruct the original data; the m coding fragments provide failure tolerance.

Mental model

object → k data fragments + m coding fragments
       → place across independent failure domains
       → read any sufficient k-fragment set
       → reconstruct missing fragments during degraded access or repair

The mathematical tolerance is only meaningful when fragment placement matches the actual rack, node, device, zone, and maintenance failure model.

Capacity efficiency

For a (k, m) layout:

efficiency = k / (k + m)
overhead   = m / k

A (10, 4) code stores 10 units of data using 14 units of physical capacity: 71.4% efficiency and 40% overhead relative to the data. Three-way replication is only 33.3% efficient.

Why it is not “RAID across servers”

The mathematics may resemble parity RAID, but distributed erasure coding must also handle:

• fragment placement across correlated failure domains;
• network fan-out and tail latency;
• degraded reads and repair bandwidth;
• metadata consistency;
• partial writes and small-object packing;
• background scrubbing and silent corruption.

Read and repair paths

A healthy read may need only the k data fragments. A degraded read retrieves extra fragments and performs decoding. Repair reconstructs missing fragments and writes them to new locations, consuming CPU, network, and storage bandwidth simultaneously.

Write paths

Full-stripe writes can encode a complete fragment set efficiently. Small updates may require reading old data/coding fragments, calculating a delta or new stripe, and writing multiple fragments. Distributed implementations also need an atomicity strategy so readers do not combine fragments from different object versions.

Degraded-state economics

State	Read behavior	System pressure
Healthy	fetch planned data fragments	normal fan-out and tail latency
Degraded	fetch extra fragments and decode	higher network, CPU, and latency
Repairing	decode and write replacements	background bandwidth competes with clients
Beyond tolerance	insufficient valid fragments	data unavailable or lost

Choosing parameters

Larger k generally improves capacity efficiency but increases fan-out and the number of resources involved in recovery. Larger m tolerates more failures but costs capacity and repair work.

Choose parameters from durability, correlated-failure, recovery-time, bandwidth, latency, and object-size requirements—not capacity efficiency alone.

Operational signals

• fragments unavailable, misplaced, or on correlated domains;
• degraded-read rate and decode latency;
• repair queue depth, throughput, and estimated completion time;
• scrub coverage and checksum failures;
• network saturation and tail latency during rebuild;
• remaining tolerance while maintenance is active.

Failure-domain checklist

1. Never count fragments in the same failure domain as independent protection.
2. Model simultaneous maintenance and hardware failure.
3. Bound repair time under realistic throttling.
4. Test loss of metadata separately from loss of data fragments.
5. Scrub continuously; redundancy cannot repair corruption it never detects.

Use the Erasure Coding Lab to change k+m, fail fragments, compare replication overhead, and observe the recoverability boundary.