What is Erasure Coding?

Erasure coding (EC) is a method of data storage in which a data object is broken into multiple fragments called shards and expanded with additional parity fragments. The original data can be recovered from any subset of the fragments that meets a minimum size requirement. EC offers a trade-off between storage overhead and fault tolerance compared to simple replication, making it attractive for large-scale storage systems.

In a typical erasure coding scheme, a data object is divided into k data shards. Then m parity shards are computed using a mathematical algorithm, for example Reed-Solomon codes. The total number of shards is n = k + m. The system can tolerate up to m shard failures: if any m shards are lost, the original data can be reconstructed using any k surviving shards. The reconstruction process involves solving a system of linear equations. Common configurations include k=10 with m=2 (20 percent overhead) or k=6 with m=3 (50 percent overhead). Each shard is typically stored on a different storage node or failure domain.

Erasure coding is widely deployed in cloud object storage systems. Azure Blob Storage, Google Cloud Storage, and Amazon S3 use erasure coding (or similar techniques) to achieve high durability with lower storage overhead than replication. EC is also used in distributed storage systems like Ceph and in archival storage for cold data. However, the computational cost of encoding and reconstructing data is higher than replication, so cloud providers often use replication for hot data and erasure coding for data that is accessed less frequently. EC is a foundational technology for cost-effective reliable storage at scale.