Erasure Coding

Erasure coding is a data protection technique that splits data into fragments, expands them with redundant parity fragments, and distributes them across storage nodes. Unlike simple replication which stores complete copies, erasure coding uses mathematical encoding so that any subset of fragments can reconstruct the original data. A common configuration like Reed-Solomon (10,4) splits data into 10 data fragments and 4 parity fragments — any 10 of the 14 fragments can recover the full data, tolerating 4 simultaneous node failures with only 1.4x storage overhead instead of 3x for triple replication.

Why This Matters

Storing data reliably across distributed nodes traditionally uses replication — keeping 3 copies provides tolerance for 2 node failures but triples storage costs. At petabyte scale, this is enormously expensive. Erasure coding provides equivalent or better durability at a fraction of the storage overhead. A Reed-Solomon (10,4) code stores 14 fragments totaling 1.4x the original data size while tolerating any 4 fragment losses — compared to 3x overhead for triple replication with only 2 failure tolerance. The tradeoff is computational: writing requires encoding across fragments, and reading may require decoding from multiple nodes. Cloud storage providers like AWS S3 and Azure Blob Storage use erasure coding internally to achieve 99.999999999% (11 nines) durability while keeping storage costs manageable at exabyte scale.

The Building Blocks

• Data Fragments: The original data split into k equal-sized pieces, each containing a portion of the source data that will be distributed across storage nodes
• Parity Fragments: Additional m fragments computed using mathematical encoding (typically Reed-Solomon) from the data fragments, providing redundancy for reconstruction
• Encoding: The mathematical process of generating parity fragments from data fragments using Galois field arithmetic, creating the redundancy needed for fault tolerance
• Reconstruction: The ability to recover the original data from any k of the total k+m fragments, using matrix inversion on the encoding coefficients
• Fragment Placement: Strategic distribution of fragments across failure domains (different racks, zones, regions) to ensure that correlated failures cannot destroy more fragments than the code tolerates

Under the Hood

Erasure coding works through linear algebra over finite fields (Galois fields). In a Reed-Solomon (k,m) code, the original data is divided into k equal-sized data fragments. An encoding matrix (a k+m by k matrix based on Vandermonde or Cauchy matrices) is multiplied by the data fragments to produce k+m total fragments — the original k data fragments plus m parity fragments. The mathematical property guarantees that any k of the k+m fragments contain enough information to solve the system of equations and recover all original data.

Reconstruction uses the inverse of a k-by-k submatrix selected from the encoding matrix, corresponding to the k available fragments. This matrix inversion and multiplication recovers the missing fragments. When all data fragments are available (no failures), reconstruction is unnecessary — the data is read directly. When data fragments are missing, the decoder reads k available fragments (possibly including parity) and computes the missing ones. This decode step adds CPU overhead and cross-node read latency.

The critical operational consideration is failure domain alignment. In a (10,4) configuration, fragments must be placed across at least 14 independent failure domains. If a single rack holds 3 fragments and loses power, only 11 remain — still sufficient. But if placement is careless and 5 fragments share a failure domain, a single failure loses them all and data is unrecoverable. Modern systems like HDFS erasure coding and Ceph enforce placement policies that distribute fragments across racks or availability zones, ensuring that correlated failures cannot exceed the coding tolerance.

How Companies Actually Do This

Amazon S3 uses erasure coding internally to achieve 11 nines of durability across availability zones while maintaining cost efficiency at exabyte scale storage

Facebook Saved over 50% of storage for their cold data warehouse by replacing 3x replication with Reed-Solomon erasure coding, recovering petabytes of capacity

Microsoft Azure Blob Storage uses Local Reconstruction Codes (LRC), an optimized erasure coding scheme that reduces cross-rack repair traffic compared to standard Reed-Solomon

Common Pitfalls

1. Placing too many fragments in the same failure domain (rack, availability zone) — a single correlated failure can exceed the code's tolerance even though enough total fragments exist elsewhere
2. Using erasure coding for frequently accessed hot data where the decode overhead significantly impacts read latency — replication is better for latency-sensitive workloads
3. Not accounting for repair bandwidth — when a node fails, reconstructing its fragments requires reading k fragments from other nodes, which can saturate network links in large clusters

Interview Questions Worth Practicing

1. How does erasure coding achieve the same durability as triple replication with lower storage overhead?
2. What is the read latency tradeoff of erasure coding versus replication, and when does it matter?
3. How do failure domains affect fragment placement strategy in an erasure-coded storage system?

The Tradeoffs

• Storage Efficiency vs. Read Latency: Erasure coding uses 1.4-1.8x storage versus 3x for replication but reading degraded data requires fetching k fragments and decoding, adding latency
• Durability vs. Repair Cost: Higher parity ratios tolerate more failures but require more fragments for repair, consuming more network bandwidth when a node is lost
• CPU vs. Disk: Encoding and decoding require non-trivial CPU computation on Galois field arithmetic; this is acceptable for throughput-oriented storage but not for latency-sensitive reads

How to Explain This in an Interview

Here is how I would explain Erasure Coding in a system design interview:

Erasure coding protects data by splitting it into k data fragments and computing m parity fragments using Reed-Solomon encoding. Any k of the k+m total fragments can reconstruct the original data. For example, RS(10,4) tolerates 4 simultaneous failures at only 1.4x storage overhead, compared to 3x for triple replication which only tolerates 2 failures. AWS S3 uses erasure coding to achieve 11 nines of durability. The tradeoff is read latency — accessing degraded data requires reading from multiple nodes and decoding. Fragment placement across independent failure domains is critical — if too many fragments share a rack, a single rack failure can exceed the coding tolerance. I would use erasure coding for large cold data and replication for hot, latency-sensitive data.

Related Topics

• Data Replication
• Fault Tolerance
• Availability
• Disaster Recovery

Original DosiBridge notes for Erasure Coding

This section is written specifically for this page, not copied from a general system-design checklist. The useful way to study Erasure Coding is to connect the concept to a production service where growth exposes the first weak assumption in the original design. That framing changes the design discussion from definitions to operating choices.

What makes this topic distinct

• Membership: For Erasure Coding, decide the membership before choosing tools; otherwise the design looks clean but fails when erasure changes.
• Clock Drift: For Erasure Coding, decide the clock drift before choosing tools; otherwise the design looks clean but fails when coding changes.
• Retry Semantics: For Erasure Coding, decide the retry semantics before choosing tools; otherwise the design looks clean but fails when erasure changes.
• Partition Behavior: For Erasure Coding, decide the partition behavior before choosing tools; otherwise the design looks clean but fails when coding changes.
• Reconciliation: For Erasure Coding, decide the reconciliation before choosing tools; otherwise the design looks clean but fails when erasure changes.

Production review question

If a team adopts Erasure Coding, what observable signal proves it helped instead of only making the architecture diagram more fashionable?

Practical metric to track

Track erasure-coding health as a named dashboard or review item: combine one user-facing metric, one saturation metric, and one correctness metric. For Erasure Coding, this keeps the discussion grounded in behavior that can be measured after deployment instead of generic advice that sounds good in an interview but never gets verified.