Erasure Coding & Replication
Two different math-based strategies for surviving disk failures — full copies versus data-plus-parity chunks.
Overview
To survive drive or node failures, distributed storage systems either keep multiple full copies of data (replication) or split it into data and parity chunks (erasure coding) — two different math-based strategies for the same goal, with a real trade-off between storage overhead and reconstruction cost.
Why It Exists
Any single disk or node can, and eventually will, fail. Storing only one copy of data means one failure equals permanent data loss. Replication and erasure coding both exist to make data survive a bounded number of failures — the real difference between them is how much extra storage each approach costs to buy that protection.
Real World Example
3x replication — common in HDFS and many databases — stores 3 full copies, surviving up to 2 simultaneous failures, but costing 200% storage overhead (3 times the original data size). Erasure coding, used internally by S3 and many object stores, instead splits data into, say, 10 data chunks and 4 parity chunks (a common '10+4' scheme) using Reed-Solomon math — the original data can be reconstructed from any 10 of the 14 total chunks, surviving up to 4 failures, at only 40% storage overhead instead of 200%.
Example Data
The same fault tolerance, two very different storage costs
| Strategy | Storage Overhead | Failures Survived |
|---|---|---|
| 3x Replication | 200% (3x original size) | 2 simultaneous failures |
| 10+4 Erasure Coding | 40% (1.4x original size) | 4 simultaneous failures |
Two Strategies for Surviving Failure
Replication — Multiple Full Copies
The data itself is copied whole onto multiple nodes. Simple to understand and to read from (any copy works directly), but the storage overhead scales linearly with the number of copies kept.
Erasure Coding — Data Chunks + Parity Chunks
Data is split into N data chunks, and K additional parity chunks are computed from them. Any N of the total N+K chunks are enough to fully reconstruct the original data.
The Reed-Solomon Math, in Plain Terms
Reed-Solomon coding computes parity chunks such that the original data chunks can always be recovered as long as enough total chunks (N out of N+K) survive — conceptually similar to how a checksum lets you detect and correct certain errors, generalized to reconstruct entire missing chunks.
The Real Trade-off: Storage Cost vs. Reconstruction Cost
Erasure coding uses dramatically less storage for the same failure tolerance, but reconstructing a lost chunk (or serving a read that requires reconstruction) costs real CPU and network I/O that a simple replica read doesn't.
Diagram
The same original data, protected two different ways
Replication
3 full copies, on 3 nodes
Erasure Coding
10 data + 4 parity chunks, on 14 nodes
Common Mistakes
Assuming erasure coding is strictly 'better' than replication in every case
Why: Erasure coding saves storage but costs more CPU and network I/O to reconstruct lost chunks, and a degraded read requiring reconstruction can be noticeably slower than simply reading an intact replica.
Fix: Choose replication for latency-sensitive hot data, and erasure coding for large, less frequently accessed data where storage cost matters more than raw read speed.
Assuming 'N+K erasure coding survives K failures' means it survives them forever without repair
Why: After K failures, the data has zero further redundancy left — without a prompt repair process rebuilding lost chunks onto new nodes, the very next failure causes real, permanent data loss.
Fix: Monitor and prioritize automatic repair of degraded erasure-coded data — surviving K failures is a temporary state, not a steady one.
Applying erasure coding to small objects or files
Why: Erasure coding's fixed overhead — splitting into many chunks, tracking per-chunk metadata — dominates for small objects, making it less efficient than simple replication at small scale.
Fix: Apply erasure coding only above a size threshold, and keep small objects simply replicated, which is what many real systems do internally.
Interview Questions
What's the basic trade-off between replication and erasure coding?
Replication stores multiple full copies of data — simple, but storage cost scales linearly with the number of copies. Erasure coding splits data into data and parity chunks, achieving similar or better fault tolerance at a much lower storage overhead, at the cost of more complex and expensive reconstruction.
In a 10+4 erasure coding scheme, how many total chunk failures can the data survive, and why?
Up to 4 chunk failures. The scheme creates 14 total chunks (10 data + 4 parity) such that any 10 of the 14 are sufficient to reconstruct the original data — so losing any 4 chunks still leaves 10 recoverable ones.
An erasure-coded storage cluster has just lost 3 of the 4 parity chunks for a set of objects in a 10+4 scheme, due to correlated node failures. What's the urgency here, and why?
This is a high-urgency situation: with only 1 chunk of redundancy remaining (1 more loss and the data becomes unrecoverable), the system is one additional correlated failure away from permanent data loss. Repair should be prioritized immediately to rebuild the lost parity chunks onto healthy nodes, restoring the full 4 chunks of redundancy before another failure can occur.
Production Best Practices
Do
✓Use replication for latency-sensitive, frequently-accessed hot data.
✓Use erasure coding for large, infrequently-accessed data where storage cost matters more than read latency.
✓Prioritize and monitor repair of degraded erasure-coded data immediately after any failure.
Don't
✗Don't assume erasure coding is universally better than replication.
✗Don't treat surviving K failures in an N+K scheme as a stable, indefinite state.
✗Don't apply erasure coding to very small objects where its fixed overhead dominates.
Comparison
| Storage Overhead | Failures Survived (Example) | Reconstruction Cost | |
|---|---|---|---|
| 3x Replication | 200% | 2 | Low — read any intact copy |
| 10+4 Erasure Coding | 40% | 4 | Higher — CPU/network to reconstruct |