What is Erasure Coding and How Does It Achieve High Durability?

Definition
Erasure coding is a data protection technique that splits data into fragments, generates redundant parity fragments using mathematical formulas, and distributes all fragments across different storage nodes. Any sufficient subset of fragments can reconstruct the original data, even if some fragments are lost.
Why Not Just Replicate?
Simple replication stores 3 copies of every byte. To survive 2 failures, you need 3x storage overhead. Erasure coding achieves the same durability with 1.4x overhead. For petabyte scale storage, this difference saves millions of dollars annually in disk costs.
The math enables this efficiency. A 10+4 erasure coding scheme (called Reed Solomon coding) splits data into 10 data fragments and generates 4 parity fragments. Storing 14 fragments protects against losing any 4. Compared to 3x replication, you store 14 units instead of 30 units for the same 10 units of data.
How Reconstruction Works
Each parity fragment encodes information about all data fragments using polynomial math. Think of solving simultaneous equations: 10 unknowns need 10 equations. Any 10 fragments (data or parity) provide 10 equations, letting you solve for the original data. Lose 4 fragments? The remaining 10 still solve the system.
This is not compression or encryption. Every fragment is the same size as the data fragments. The magic is in the mathematical relationship between fragments, not in reducing data size.
Durability Calculation
Durability depends on fragment failure probability and reconstruction speed. If each disk has 1% annual failure rate and you tolerate 4 failures, losing all 5 of 14 fragments has probability roughly (0.01)^5 = 0.0000000001. That is eleven nines durability: 99.999999999%.
But this assumes failures are independent and repairs are instant. Correlated failures (entire rack loses power) and slow repairs reduce effective durability. Real systems add geographic distribution to ensure independence.
💡 Key Insight: Erasure coding trades CPU for storage efficiency. Computing parity requires processing all data fragments. The storage savings justify this cost at scale.

💡 Key Takeaways

✓Erasure coding achieves 3x replication durability with only 1.4x storage overhead using mathematical parity

✓A 10+4 scheme splits data into 10 fragments plus 4 parity, surviving loss of any 4 fragments

✓Reconstruction uses polynomial math: any k fragments (data or parity) can solve for original data

✓Eleven nines durability (99.999999999%) assumes independent failures and fast repairs

✓Storage savings over replication at petabyte scale equals millions in annual disk costs

📌 Interview Tips

1Explain the storage math concretely: 1 PB of data needs 3 PB with replication but only 1.4 PB with 10+4 erasure coding. At $25/TB/year, that is $40M versus $35M annually.

2When asked about durability, walk through the probability calculation. Five independent 1% failures is 10^-10. Then note the assumptions: independence matters, which is why fragments go on different racks.

3If the interviewer asks about CPU overhead, quantify it: encoding 1 GB takes 100-500ms on modern CPUs. For write once read many workloads, this is negligible. For high write throughput, it becomes a bottleneck.

← Back to Erasure Coding & Durability Overview