Skip to content

Erasure Coding

1. What is it? (2-3 lines)

Erasure Coding is a mathematical data protection method where a data object is split into \(K\) data chunks and encoded with \(M\) parity chunks (using Reed-Solomon polynomial math). The original data can be fully reconstructed from ANY \(K\) out of the total \(K + M\) chunks.

2. Why does it exist?

Traditional 3x Replication achieves high availability by storing 3 full copies of data, resulting in a 200% storage overhead (\(3\times\) raw storage cost). Erasure Coding provides the exact same fault tolerance (tolerating \(M\) node failures) with only a 25-50% storage overhead, saving millions of dollars in cloud object storage.

3. Where is it used?

  • Cloud Object Storage: AWS S3, Google Cloud Storage, Azure Blob.
  • Distributed Blob Stores: MinIO, Ceph, HDFS (Erasure Coding policy), Backblaze B2.
  • RAID Configurations: RAID 5 (1 parity), RAID 6 (2 parity).

4. How does it work? (simple flow)

  1. Splitting (\(K=4\)): A 64MB file is split into 4 equal data chunks (\(16\text{MB}\) each: \(D_1, D_2, D_3, D_4\)).
  2. Parity Generation (\(M=2\)): Reed-Solomon linear algebra generates 2 parity chunks (\(P_1, P_2\)). Total chunks = \(K + M = 6\).
  3. Distribution: The 6 chunks are scattered across 6 separate server racks/nodes.
  4. Failure Reconstruction: If Nodes 2 and 5 crash (\(D_2\) and \(P_1\) lost), the system reads the remaining \(K=4\) chunks (\(D_1, D_3, D_4, P_2\)) and solves the linear system of equations to perfectly reconstruct the lost \(D_2\) data in memory!

5. Advantages

  • Dramatic Storage Savings: \(RS(8, 4)\) achieves 3x fault tolerance with only 50% storage overhead (vs 200% for 3x replication).
  • Customizable Durability: Configure \(M\) parity chunks to survive up to \(M\) simultaneous node/disk failures.
  • Ideal for cold/warm large-file object storage (AWS S3 Glacier).

6. Limitations

  • High CPU Overhead: Encoding and decoding require matrix multiplication math (Galois Field arithmetic), increasing CPU load.
  • Reconstruction Latency (Rebuild Penalty): Reading a file when 1 chunk is missing requires fetching \(K\) separate chunks over the network and computing the matrix solution, slowing down read latency.

7. Common interview questions (10)

  1. What is the mathematical concept behind Reed-Solomon Erasure Coding?
  2. Compare 3x Replication vs Erasure Coding \(RS(8, 4)\) in terms of storage overhead, fault tolerance, and CPU usage.
  3. How does AWS S3 achieve 11 9s (\(99.999999999\%\)) durability using Erasure Coding?
  4. Why is Erasure Coding preferred for Cold Storage (S3 Glacier) while Replication is used for Hot Databases (PostgreSQL)?
  5. What is the Reconstruction Penalty when reading a file with a missing data chunk in an Erasure Coded cluster?
  6. How does Galois Field \(GF(2^8)\) arithmetic accelerate Erasure Coding matrix operations?
  7. What is Local Reconstruction Codes (LRC) and how does Microsoft Azure Blob Storage use it to reduce repair network traffic?
  8. How does MinIO handle disk repair when a node fails in an Erasure Coded set?
  9. What happens to Erasure Coding performance for small files (<100KB)?
  10. How do hardware AVX-512 / SIMD instructions accelerate Reed-Solomon encoding?

8. Common misconceptions

  • Misconception: Erasure Coding is just compression. Fact: Erasure Coding adds redundant parity data; compression shrinks data. Erasure coding provides fault tolerance, not size reduction.
  • Misconception: Erasure Coding replaces backups. Fact: Erasure coding protects against disk/node hardware failures; it cannot protect against user deletion or application bugs.

10. 30-second cheat sheet

  • Formula: \(K\) Data + \(M\) Parity chunks \(\implies\) Can reconstruct from ANY \(K\) chunks. Tolerates \(M\) node failures.
  • Storage Overhead: \(\text{Overhead} = M / K\).
  • 3x Replication = 200% Overhead (\(3\times\) cost).
  • Erasure Coding \(RS(8, 4)\) = 50% Overhead (\(1.5\times\) cost).
  • Tradeoff: Massive storage cost savings (\(50-75\%\)) at the cost of higher CPU math and slower repair read latency.
  • Best For: Object Storage (AWS S3, MinIO, Blob storage).