Erasure Coding: Cheaper Durability for Distributed Storage

Most engineers working above the storage layer learn one durability primitive: replication. Keep three copies of your data on three different machines, and you can lose two of them without losing anything. It’s easy to reason about, easy to implement, and it works. The catch is that it costs 3x your raw storage capacity.

At moderate scale that’s a reasonable tax. At petabyte or exabyte scale, it becomes a significant infrastructure cost. Erasure coding is the technique that lets large-scale storage systems do much better.

The Math Behind Three Copies

Three-way replication has a 200% overhead: for every byte of user data, you store two additional bytes. That overhead buys you tolerance for any two simultaneous failures in a replica group.

The insight erasure coding exploits is that full copies are a wasteful way to encode redundancy. You don’t need to store the entire original data multiple times — you just need enough information scattered across enough nodes that any sufficiently large subset can reconstruct the whole.

How Erasure Coding Works

The core idea is to take k data chunks and mathematically encode them into k + m chunks, where m is the number of additional “parity” chunks. The encoding has the property that any k of the k + m chunks are sufficient to reconstruct the original data. You can lose any m chunks — from disk failures, node outages, or network partitions — and still recover everything.

Reed-Solomon codes are the most common scheme used in practice. The encoding is based on polynomial arithmetic over finite fields: the k data chunks are treated as coefficients of a polynomial, which is then evaluated at k + m distinct points to produce the k + m encoded chunks. Recovering the original is a matter of polynomial interpolation from any k points.

The overhead calculation is straightforward. A 6+3 configuration (6 data chunks, 3 parity chunks) stores 9 chunks for 6 chunks of data — 50% overhead, compared to 200% for three-way replication, while tolerating the same three simultaneous failures. A 12+4 configuration brings that down to about 33%. The larger the k, the better the storage efficiency, up to a point.

The Reconstruction Penalty

Nothing comes free. The storage savings come with two costs that matter at runtime.

The first is CPU. Encoding and decoding Reed-Solomon codes requires finite field arithmetic, which is more expensive than a simple byte copy. Modern CPUs handle this efficiently with SIMD instructions, and hardware accelerators exist for the hottest paths, but it’s nonzero work.

The second cost is reconstruction latency. On a healthy read where all k chunks are available, there’s no penalty — you read k chunks in parallel and you’re done. But when a chunk is missing and you need to reconstruct data, you have to read k surviving chunks from k different nodes, perform the decode, and return the result. That’s more network I/O and more CPU than a simple replicated read, and it inflates tail latency when nodes are slow or failed.

This asymmetry shapes how erasure coding is deployed in practice.

Where It Shows Up

HDFS added erasure coding support specifically to address cold data. Files that are infrequently read — archival logs, old snapshots, deep analytics datasets — are good candidates because the reconstruction penalty is rarely paid. Hot, actively-read data typically stays on three-way replication where read amplification would be a constant penalty.

Ceph exposes erasure-coded pools as a first-class option alongside replicated pools, with operators choosing based on access patterns and cost targets.

Most cloud object storage services use erasure coding internally. The specific configurations aren’t public, but the economics make three-way replication impractical at their scale.

RAID 5 and RAID 6 on local disks are also erasure coding, with the same fundamental tradeoff: RAID 5 uses a 1-fault-tolerant scheme, RAID 6 uses a 2-fault-tolerant scheme, both at lower overhead than full disk mirroring.

Picking the Right Tool

Erasure coding and replication solve the same problem but optimize for different things. Replication is simpler, has no reconstruction cost on reads, and makes sense when storage cost is not the binding constraint. Erasure coding pays a CPU and latency penalty to cut storage overhead significantly, which makes sense when data is large, cold, and rarely accessed under failure conditions.

Most large systems use both: replication for the hot tier, erasure coding for the warm or cold tier. Understanding where each fits helps avoid applying the wrong tradeoff in the wrong place.