CSE Roadmap

Common tier · about 5 hours · 8 parts

Part 5 of 8 · 2 min read

Durability

Staying safe.

Disk failure. A disk may fail in any year. Suppose the yearly failure rate is 0.81 per cent (the book's figure for one model). Three copies on different disks all fail with chance 0.0081 × 0.0081 × 0.0081 = about 5.3 × 10^-7. Reliability is about 0.9999995, close to six nines. This is a rough estimate.

Failure domains. A rack shares a switch and power. A server shares its board and power supply. A data centre shares cooling and power. Putting all copies in one failure domain means one event removes them all. So replicas go in different racks and different zones.

Erasure coding. Instead of full copies, split the data into data chunks and compute extra parity chunks with a formula. Lost chunks can be rebuilt from the rest. In a 4 + 2 scheme, data is split into 4 chunks, 2 parity chunks are added, and any 2 of the 6 may be lost. In an 8 + 4 scheme, any 4 of 12 may be lost. Put each chunk in a different failure domain.

Three copies Erasure coding (8 + 4)
Extra space 200 per cent 50 per cent
Durability About six nines Around eleven nines (a published calculation)
Normal read One node At least 8 nodes
Read after failure Same speed Slower, needs rebuilding
Complexity Low High

A worked example (made up). To store 100 TB of data, three copies need 300 TB. With 8 + 4 coding, 100 TB × (12 / 8) = 150 TB is enough, so half the disks for a higher durability, at the price of slower and more complex reads.

Copies suit data that must be read fast. Coding suits large, cooler data, where cost dominates. The book builds the main design on copies.

Checksums. Memory errors can corrupt data silently. A checksum is a small value computed from the data. If the stored and recomputed values differ, the data is damaged. Store a checksum with each object, and one for the whole file when it becomes read-only. On a read, compute again. If it does not match, read another replica or rebuild from coding. A good checksum changes a lot for a tiny change.

Erasure coding

Erasure coding splits data into chunks and adds parity chunks, so the data can be rebuilt even if some chunks are lost.

Example: with 4 data and 2 parity chunks, any 4 of the 6 are enough to rebuild the object.

Check yourself: 1. Why must replicas be in different failure domains? 2. How much extra space does 8 + 4 coding need? 3. What does a checksum catch?