Erasure coding
Durability with less than three copies: parity across machines.
01The intuition
The problem it solves
You want to keep a 10-page letter safe even if a page gets lost. The obvious way is three complete photocopies in three drawers: 30 pages of storage for 10 pages of content, and losing any two drawers still leaves one copy. A cleverer way: keep the 10 pages once, plus 4 extra "check pages" computed from them, and spread all 14 across 14 drawers. Lose any 4 drawers and the remaining 10 can rebuild everything. That is 14 pages of storage instead of 30 for better protection.
Object stores hold exabytes, and at that size tripling every byte is most of the bill. Erasure coding is the check-page trick done with arithmetic: split data into k pieces, compute m parity pieces, store all k + m on different machines, and survive the loss of any m.
Build it one piece at a time
Step 1: one parity piece. Take two numbers, 5 and 9, and store their sum, 14, as well. Lose the 9 and you recover it as 14 − 5. Three pieces stored, any one can be lost. That is RAID 5 in miniature, and the "sum" is usually XOR over bits.
Step 2: more parity, any losses. With k data pieces and m parity pieces computed as different weighted sums (Reed–Solomon codes do this over a finite field so every subset of k pieces is enough), any k of the k + m pieces reconstruct the data.
| Scheme | Storage per byte | Survives | Pieces touched to read |
|---|---|---|---|
| 3 full copies | 3.0× | any 2 losses | 1 |
| 6 + 3 erasure coded | 1.5× | any 3 losses | 6 |
| 10 + 4 | 1.4× | any 4 losses | 10 |
Step 3: place the pieces. Each of the 14 pieces goes on a different machine, in different racks and ideally different zones, so one failure takes one piece. The object's metadata records where each piece is.
Step 4: read and repair. A read fetches any 10 pieces and decodes; if all 10 data pieces are healthy it just concatenates them. When a machine dies, a repair job reads 10 surviving pieces of each affected object and recomputes the missing one onto a new machine.
Step 5: choose what to code. Decoding costs CPU and 10 reads instead of 1, so hot, small, frequently read objects stay replicated, and large, cold objects (backups, old videos, archives) are erasure coded. Many stores do both: replicate on write for speed, convert to erasure coding after the object cools.
Why it works, with the numbers
The storage overhead is the ratio of total pieces to data pieces, and durability grows with m:
overhead = (k + m) ÷ k; for 10 + 4 that is 1.4×, versus 3× for triplication, a saving of more than half the disks
With a 2 percent yearly disk failure rate and repair within a day, losing 5 of 14 specific disks in the same day is astronomically unlikely, so 10 + 4 is more durable than three copies while costing less. The price appears in the failure modes: repair traffic (rebuilding one lost piece reads 10 others, so a dead disk of 10 TB causes 100 TB of reads), slow reads of cold objects (10 network fetches plus decoding), and the need for all pieces of an object to be placed carefully, which makes small objects wasteful (14 pieces of a 1 KB file is overhead, so small objects are packed together before coding).
The trade-off you must say out loud
Erasure coding trades read latency, repair bandwidth and CPU for storage cost. Say which objects get it and when (on write, or after cooling), and say your k and m. The interviewer may ask why not code everything; the answer is the 10-fetch read path and repair amplification, which is why hot data stays replicated.
Where it shows up in the 100 Google problems
- Design a blob / object storage service: the deep dive on durability per dollar is this article; say "replicate hot, erasure code cold" and give the numbers.