The data we store on S3 is replicated multiple times to make sure it is never lost (even in the event of a disaster). If they simply stored multiple copies of the data, it would get expensive very quickly at the exabyte scale.
This is where erasure coding gives you the same durability for a fraction of the storage cost. Let me explain…
The idea is simple: split your data into k chunks, then compute m extra parity chunks from them, for a total of n = k + m chunks spread across different disks or nodes. You can lose any m of those n chunks and still reconstruct the original data.
Standard storage class of S3 uses an erasure coding scheme, around 9 data shards and 4 parity shards, spread across multiple availability zones. That gives 99.999999999 percent (eleven nines) durability while using roughly 1.5x the actual data size.
This would have been 3x for a naive triple replication, and thus, the additional cost is pretty low with erasure coding.
The parity math comes from Reed-Solomon codes, the same technique used in QR codes. Given any k of the n total chunks, you can solve a system of linear equations to recover the rest. You can read the Reed-Solomon wiki page for more details, or ask your fav LLM.
By the way, here, the tradeoff is compute.
Reconstructing missing chunks needs CPU cycles to run the decoding math, while replication just reads a copy. Reconstruction also gets slower as you increase the number of parity shards, since the math involves larger matrices.
This is why systems tune k and m carefully. Too few parity shards and durability suffers; too many and reconstruction becomes more expensive.
By the way, Erasure Coding is the reason cloud storage is both cheap and durable at the same time. Just a bunch of encoding math at play.