Durability and erasure coding

Durability is the chance that stored data survives. S3 Standard is designed for 99.999999999% (eleven nines) of annual durability. That doesn't come from one reliable disk. Drives fail constantly at scale, so durability comes from redundancy plus fast repair.

The big idea

Think of a jigsaw puzzle with spare pieces. You can lose some pieces and still rebuild the picture. Erasure coding works the same way, with bytes instead of picture pieces.

Two numbers matter. The first is how many failures a piece of data survives. The second is how fast the store rebuilds lost redundancy. Backblaze's fleet statistics show annual failure rates of roughly 1–2% per drive. At millions of drives, failures happen every hour, so repairs must be quick.

Eleven nines in plain terms: store 10 million objects, and you can expect to lose one about every 10,000 years, on average.

Walking through it

Replication is simple. Store three full copies on three machines in different failure domains. It survives two lost copies, costs 3x the raw storage, and repairs by copying a file.

Erasure coding does better. Here is Reed-Solomon RS(10 + 4) on a 10 MB object:

Split into 10 data fragments of 1 MB each
Compute 4 parity fragments of 1 MB each
Store 14 fragments on 14 drives, across racks and zones

Storage used: 14 MB for 10 MB of data → 1.4x
Survives: any 4 lost fragments

3x replication of the same object:
Storage used: 30 MB → 3.0x
Survives: any 2 lost copies

It tolerates more failures with less than half the storage. At a petabyte, that is 1.4 PB of disk instead of 3 PB. Facebook's f4 warm-storage system moved to Reed-Solomon (10, 4) plus cross-region XOR, which brought its effective factor from 3.6x down to about 2.1x.

Erasure coding has costs:

• CPU to encode on write and decode on degraded reads.
• Repair traffic. Rebuilding one lost 1 MB fragment reads 10 MB from ten other drives. Replication would read 1 MB.
• Small-object waste. Splitting a 4 KB object into 14 fragments wastes space, so small objects are often replicated.
• Tail latency on reads that wait for k fragments.

So hot, small, latency-critical data is often replicated, and large, colder data is erasure coded. Many systems write replicated first and re-encode in the background.

Common mistakes

• Reading eleven nines as "never lost." It's an annual probability for each object. Backups still matter for mistakes such as deleting data on purpose.
• Forgetting repair time. Durability depends on how fast a second failure can be avoided. A slow repair window is a risk.
• Using erasure coding for tiny objects. The fragment overhead outweighs the savings.

Check yourself

1. With RS(10 + 4), how many fragments can you lose? Any 4 of the 14.
2. Why does erasure coding cost more repair traffic than replication? Rebuilding one lost fragment reads from ten other drives, so it moves about ten times as many bytes as copying a replica.

Key takeaways

• Eleven nines comes from redundancy plus fast repair, not from one reliable disk.
• RS(10 + 4) survives 4 losses at 1.4x storage. Three copies survive 2 losses at 3x.
• Erasure coding costs CPU and repair traffic. Replicate small or hot data, and encode large, cold data.

Further learning

James Cowling's talk on Magic Pocket, Dropbox's exabyte-scale storage system, covers erasure coding and repair from the inside.

The Google File System is the original paper on replicated chunks.

Next, read about presigned and multipart uploads, which get bytes into the store without going through your servers.