Engineering Atlas › System Design Fundamentals

Surviving disk loss with erasure coding

13 min read · last reviewed 2026-10-17

Open in the interactive app: practice, quiz, mock interview →

In one minute

How it works

The idea

The simplest erasure code is a single XOR parity, as in RAID 5. With data blocks A, B, C, store P = A XOR B XOR C. Lose any one block and XOR the remaining three to rebuild it. That is a 3+1 code: any 3 of 4 fragments recover the data, at 1.33x overhead.

To survive more than one loss you need more independent parity fragments. Reed-Solomon (background) treats the k data fragments as values of a polynomial over a finite field (usually GF(2^8), so every byte is a field element) and computes m additional evaluations as parity. Any k distinct evaluations determine the polynomial, so any k fragments rebuild the rest. Encoding and decoding are matrix multiplications over the field, implemented with lookup tables and SIMD at several GB/s per core.

Choosing k and m

The two parameters set three things:

Fragments must be placed in independent failure domains. A 6+3 stripe across 9 racks survives losing 3 racks. Spreading across 3 availability zones with 3 fragments each survives losing a whole zone, since 6 fragments remain.

Read and write behaviour

A healthy read can fetch only the data fragments, so there is no decoding unless something is missing; this is a systematic code. A degraded read must fetch k fragments from different hosts and decode, so tail latency rises during failures. Some systems read k + 1 fragments and use the first k to arrive, trading extra traffic for lower latency.

Writes are best done for whole stripes. Updating 4 KB in the middle of a 10+4 stripe means reading old data and parity, recomputing, and writing several fragments, which is why erasure coding suits immutable objects, sealed log segments, and append-only files, and why systems often write new data replicated first and convert it to erasure-coded form once it is sealed. Azure Storage is the textbook case: it appends to extents held as three full copies, seals an extent at around 1 GB, erasure codes it lazily in the background, and only then deletes the copies (Huang et al., ATC 2012).

Local Reconstruction Codes

Most failures are single fragments. Azure's LRC splits a 12-fragment data stripe into two groups of 6, each with a local XOR parity, plus 2 global parities (12+2+2). A single lost fragment is rebuilt from its group of 6 instead of 12, halving repair reads, while the global parities still cover rarer multi-fragment losses. Overhead rises slightly (1.33x versus 1.17x for 12+2) in exchange for cheaper, faster repairs. The paper frames the win the other way round too: against the 6+3 Reed-Solomon code that GFS's successor used, 12+2+2 keeps the same six-fragment repair cost while cutting overhead from 1.5x to 1.33x (Huang et al.).

Down the stack

Layer 1The contract

A Reed-Solomon k+m code is maximum distance separable: any k of the k+m fragments reconstruct the stripe, and no code with the same overhead can tolerate more losses. The guarantee is about erasures, fragments known to be missing; the code does not on its own identify which fragment is corrupt, so every fragment carries its own checksum and a bad checksum turns corruption into an erasure. The durability a system advertises is not a property of the code alone: it depends on fragment placement across independent failure domains, on how fast lost fragments are detected and rebuilt, and on correlated failures such as a bad batch of drives.

Layer 2The mechanism

Practical libraries work in GF(2^8), where each byte is a field element, addition is XOR, and multiplication is defined modulo an irreducible polynomial (0x11D is a common choice). Encoding multiplies the k data fragments by an (k+m) × k generator matrix whose top k rows are the identity, so data fragments are stored as-is (a systematic code) and the bottom m rows produce parity. The parity rows come from a Vandermonde or Cauchy construction chosen so that every k × k submatrix is invertible. Decoding picks any k surviving rows, inverts that k × k matrix once per failure pattern, and multiplies.

HDFS ships policies named by their layout, such as RS-6-3-1024k (enabled by default) and RS-10-4-1024k: files are striped across k DataNodes in 1 MB cells, round-robin, with parity cells on m more nodes (HDFS erasure coding). Ceph erasure-coded pools take k and m in a profile fixed at pool creation. Older guides name Jerasure as the default plugin, but from the Tentacle release the default is Intel's ISA-L and Jerasure is no longer maintained (Ceph erasure code). Partial overwrites, needed for block and file data, require allow_ec_overwrites on BlueStore, and Tentacle adds an opt-in, irreversible allow_ec_optimizations mode that reads and writes only the touched part of a stripe. Backblaze describes its Vaults as splitting each file into 17 data and 3 parity shards, one on each of 20 storage pods in 20 cabinets, so a pod, cabinet power or cabinet network failure costs one shard (Backblaze docs), and S3 likewise Reed-Solomon codes objects into k data and m parity shards (Warfield, 2023).

Layer 3The machine

Multiplying a byte by a constant in GF(2^8) is a table lookup. Libraries such as Intel ISA-L split each byte into two 4-bit halves and look each up in a 16-entry table with the pshufb shuffle instruction, which performs 16 lookups at once in SSE and 32 in AVX2, then XOR the results. Encoding runs at several gigabytes per second per core, so arithmetic is rarely the bottleneck; memory bandwidth and the network are.

Repair is where the cost lands. Rebuilding one lost 1 MB cell in a 10+4 stripe reads 10 MB from 10 machines; rebuilding a failed 16 TB drive under that code moves roughly ten times its capacity across the network, against one times for 3-way replication. Degraded reads wait for the slowest of k hosts, so tail latency rises. Small writes are penalised too: updating 4 KiB inside a stripe means reading old data and parity, recomputing, and writing data plus m parity fragments, so systems avoid in-place updates and code only sealed, immutable data. Small files fit badly: a file smaller than one cell still needs its full set of parity cells, so overhead for tiny files can exceed that of replication.

Repair traffic is also attackable with better codes. Regenerating codes such as Clay read a little from more survivors instead of whole fragments from k of them. Ceph's documentation gives the numbers for a k=8, m=4 pool losing a 1 GiB shard: Reed-Solomon downloads 8 GiB, a Clay profile downloads 250 MiB from each of 11 survivors, 2.75 GiB in all (Ceph Clay). The cost is more, smaller disk reads per repair.

Why it's built this way

  1. Replication triples the hardware bill, so large stores use codes that tolerate the same failures at 1.2 to 1.5 times overhead.
  2. Field arithmetic is cheap with SIMD table lookups, so the cost shifts from CPU to reading k fragments over the network.
  3. Repair traffic grows with k, so wider stripes save disk but slow recovery, which motivates local reconstruction codes.
  4. Partial stripe updates are expensive read-modify-write cycles, so erasure coding is applied to immutable, sealed data, often after an initial replicated phase.
  5. Codes handle erasures, not silent errors, so every fragment is checksummed and scrubbed to turn corruption into a known loss.

Diagram

flowchart LR
    O["Object (60 MB)"] --> S["Split into k=6 data fragments"]
    S --> D1["D1 10 MB"]
    S --> D2["D2"]
    S --> D3["D3"]
    S --> D4["D4"]
    S --> D5["D5"]
    S --> D6["D6"]
    S --> E["Reed-Solomon encode"]
    E --> P1["P1 10 MB"]
    E --> P2["P2"]
    E --> P3["P3"]
    D3 -.->|"lost"| R["Repair: read any 6 of the 8 survivors, decode"]
    R --> N["New D3"]

Worked example

A storage team holds 20 PB of logical warm data and compares 3x replication with RS 10+4.

Capacity. Replication needs 60 PB raw. RS 10+4 needs 28 PB raw. With 16 TB disks, that is about 3,750 disks instead of 1,750 disks for erasure coding, a difference of 2,000 disks plus servers, power, and rack space.

Durability. Replication survives 2 simultaneous losses of the same object's copies; RS 10+4 survives 4. With fragments in independent failure domains and repair within hours, the probability of losing data under 10+4 is orders of magnitude lower than under 3x replication.

Repair. A 16 TB disk fails. Under replication, the cluster copies 16 TB. Under 10+4, rebuilding each lost fragment reads 10 others, so 160 TB crosses the network. With 500 hosts each giving 100 MB/s to repair (50 GB/s in total), replication finishes in about 5 minutes and erasure coding in about an hour, 10 times the network load. The team throttles repair to protect foreground traffic and prioritises stripes that have lost 2 or more fragments.

Latency. Healthy reads look the same. Degraded reads of a 1 MB range now need 10 parallel fetches and a decode, adding a few milliseconds and raising p99. Hot data under 1 MB stays replicated.

In the wild

Trade-offs

OptionStrengthsWeaknessesChoose when
3x replicationSimple, fast reads and repairs, cheap small updates3x storage, tolerates only 2 lossesHot data, small objects, databases
RS narrow (6+3)1.5x overhead, tolerates 3 losses, moderate repairStill costs network on repairWarm data, mid-size clusters
RS wide (17+3)About 1.18x overheadExpensive repairs, many hosts per readCold archives
LRC (12+2+2)Cheap single-fragment repair, low overheadMore complex, slightly more overhead than plain RSLarge clouds with frequent disk churn
Replicate first, then encodeFast writes, efficient long-term storageBackground conversion workAppend-heavy systems like HDFS and log stores

Pitfalls in production

Leadership lens

Check yourself

  1. Why does RS 10+4 tolerate more failures than 3x replication while using less than half the space?

    Show answer

    Any 10 of 14 fragments rebuild the data, so 4 losses are survivable, and parity costs only 40% extra instead of 200%.

  2. Why is repair more expensive under erasure coding?

    Show answer

    Rebuilding one fragment requires reading k surviving fragments over the network, not one copy.

  3. Why do systems often write data replicated and convert it to erasure coding later?

    Show answer

    Small or changing writes are cheap with replicas, while coding is efficient only for large, immutable, full stripes.

  4. What problem does LRC solve?

    Show answer

    It lets the common single-fragment failure be repaired from a small local group instead of all k fragments.

Sources and further study

Primary

Systems docs

Books

Other curricula

Watch

Free resources

Open in the interactive app: practice, quiz, mock interview →