Erasure Coding (EC)

Erasure coding replaces the naive N-way replica model with a systematic linear code. An object is split into k data fragments, and a coding matrix (usually a Cauchy or Vandermonde-based Reed-Solomon generator) produces m parity fragments. The storage overhead ratio becomes (k+m)/k instead of the replication factor N (e.g. 3x). A common production configuration like EC(10,4) yields 1.4x overhead while tolerating 4 concurrent fragment losses — durability comparable to 6-way replication at less than half the cost. This is why object stores (S3, Ceph, HDFS with EC pools, Azure Storage) default to EC for cold and warm tiers, reserving replication for hot, latency-sensitive paths.

The core tradeoff is read/write amplification versus CPU cost. A full write requires encoding across all k shards before any parity can be computed, which breaks the simple append-only write path replication enjoys — most systems buffer a full stripe before encoding, introducing a coordination point and increasing write latency variance. Reads are cheap in the steady state (fetch only the k data shards), but a degraded read — where one or more data shards are unavailable — forces reconstruction: read any k surviving shards (data + parity), invert the generator matrix over GF(2^w), and recompute the missing fragment. This is CPU-bound Galois Field multiplication, and at scale it becomes a real capacity planning line item, not a rounding error.

The operationally dangerous case is the rebuild storm. When a node or disk fails, every stripe that had a shard on that device must be reconstructed and re-striped elsewhere. Unlike replica repair (copy one full replica), EC rebuild requires reading k shards per stripe from potentially k different nodes to regenerate one lost fragment — multiplying network fan-in and disk IOPS by the stripe width. This is why EC clusters are far more sensitive to correlated failure domains: placing shards of the same stripe behind a shared rack switch or power zone can turn a single-fault into an unrecoverable stripe loss even though the code nominally tolerates m failures. Placement algorithms (CRUSH in Ceph, block placement policies in HDFS) must explicitly diversify shard placement across independent failure domains, not just independent disks.

Practically, EC and replication are not mutually exclusive strategies but tiers in a lifecycle. Hot, frequently-mutated, low-latency data stays replicated (cheap single-copy reads, fast small writes); once data cools and access becomes sequential/read-mostly, it’s EC-converted in the background, trading write/rebuild cost for steady-state storage efficiency. Systems exposing this as a first-class policy (Ceph’s bluestore pools, HDFS ErasureCodingPolicy) let operators tune (k, m) per namespace based on observed access patterns and blast-radius tolerance — but every increase in k for storage efficiency directly increases rebuild fan-in and stripe-loss correlation risk, so (k, m) selection is fundamentally a durability-vs-efficiency-vs-blast-radius optimization, not a tunable with a universally ‘correct’ value.