Distributed Systems Core · lesson 9 of 11 · about 28 min
How to know your data is still your data: why disks silently return wrong bits, CRCs that catch accidental damage, cryptographic hashes that catch tampering, Merkle trees that find the bad blocks in logarithmic time, scrubbing that repairs rot in time, and why checking every hop is not the same as checking the whole path. Tap any for a plain-language card.
Silent corruption
The numbers on this page come from the arithmetic only: expected errors = bits read ÷ error-interval, and the chance of at least one is 1 − e−expected. Spec-sheet rates are upper bounds quoted by vendors, and real rates vary; the point is the scale effect. At cloud size, corruption is not a risk to be avoided but a certainty to be detected, which is what the rest of this lesson is about.
With 100 TB and 1 in 1014, expect around eight bad bits on a single full read. Move to 1 in 1016 and it drops, but at a petabyte it is back.
Reading 100 TB 1 time from many enterprise drives (1 in 10^15) means about 0.80 wrong bits that the device reports as fine: a 55.1% chance of at least one. Unless something checks the data, you will not find out.
Poisson arithmetic with spec-sheet style error rates (vendor figures are conservative bounds, real rates differ). No simulation randomness.
Checksums and CRC
Below, type a message and flip one bit; the real CRC-32 (the one in Ethernet, zlib and gzip) changes completely. The bars then corrupt a 64-byte block at random in k places and show how often each checksum fails to notice.
Flip any bit and watch the CRC change. Then set k to 2 and see the plain sum miss several percent of corruptions while CRC-16 and CRC-32 miss none in 4,000 trials.
| Text | CRC-32 | |
|---|---|---|
| Original | Pay Asha 100 rupees | 7a7e57d4 |
| One bit flipped | Pcy Asha 100 rupees | 7faa3c57 |
Changing one bit of "Pay Asha 100 rupees" changed the CRC-32 from 7a7e57d4 to 7faa3c57. With 2 random bit errors in a 64-byte block the plain byte sum let 272 of 4000 through; CRC-32 let 0. A CRC detects accidental damage very well, but it is not a defence against an attacker, who can craft a change that keeps the same CRC.
Real CRC-8 (poly 0x07), CRC-16/XMODEM and CRC-32 (reflected, 0xEDB88320). Detection rates: 4,000 seeded trials per bar.
Hashes
Collisions are not impossible, only astronomically unlikely, and the bound says how unlikely: with n random b-bit hashes the chance of any two matching is about n²⁄2^(b+1). A 32-bit hash is useless for a million items; a 64-bit one is fine for millions; 256 bits is effectively collision-free forever. Type a message, then set the item count and hash size.
Compare the SHA-256 and CRC-32 rows: the hash scrambles about half its bits, while the CRC-32 only changes the bits needed to express the difference.
10^9 items hashed to 64 bits give a chance of any two colliding of 2.7%. That is too high for deduplication or content addressing: use a longer hash.
SHA-256 is a real implementation (check: SHA-256("abc") begins ba7816bf). Collision chance = 1 − e^(−n(n−1)/2^(b+1)).
Merkle trees
This is how Dynamo-style databases run repair, how Git and Bitcoin verify histories, and how storage systems prove a file arrived intact piece by piece. The tree is cheap to keep updated: changing one block rewrites only the hashes on its path to the root.
Go from 64 blocks to 65,536 with 3 bad ones: the comparisons barely grow while the naive cost explodes. Then raise the bad blocks and see the savings shrink.
3 corrupted blocks among 4,096 were located with 67 hash comparisons on a tree 13 levels tall, against 4,096 for a block-by-block comparison.
A real Merkle tree built over seeded blocks, with a fast demo hash in place of SHA-256 for speed; the walk and counts are exactly what a real implementation does.
Scrub and repair
Without scrubbing, rot just accumulates: given enough years every copy of some block eventually rots. The numbers here are exact probabilities for independent copies; real failures can be correlated (same batch of disks, same bug), which makes the true risk higher and is why placing copies on different racks, disks and vendors matters too.
Keep 2% yearly rot per copy and compare scrubbing monthly with yearly, then with never.
Out of 1e+9 blocks with 3 copies each, scrubbing every 30 days for 5 years leaves about 266 lost, against 861,784 with no scrubbing at all. A shorter interval is worth the extra read load because the loss probability falls with the cube.
Exact: P(copy rots in an interval) = 1 − e^(−rate × interval); P(all 3 in one interval)^periods. Independence between copies is assumed.
Which integrity tool?
CRCs are fast and good at accidents; hashes resist attackers; Merkle trees find differences cheaply; replicas let you fix what you find. Each answer is worth 20 XP.
Ask: accident or attacker? detect or repair? one block or millions?
Detect accidental bit flips in every 4 KB page as it is read from disk.
Tip: press 1 to 4 to answer, Enter for the next one.
Who lives by this
Four published systems and how they keep data honest.
end-to-end checksums in the parent block
ZFS stores each block's checksum in the pointer from its parent block rather than next to the data, so a damaged block cannot vouch for itself. On read it verifies the checksum and, if the pool has redundancy, repairs the bad copy from a good one (self-healing).
CRC32C per 512 bytes + block scanner
HDFS computes a checksum for every 512 bytes of data by default (CRC32C), stores them beside each block, and verifies them on read. DataNodes also run a block scanner that re-verifies stored blocks periodically (every three weeks by default) and reports corrupt replicas so the NameNode can re-replicate.
objects named by their hash
Git names every object (file contents, directory trees, commits) by a hash of its content, and each commit contains the hash of its parent. Changing any old byte changes every hash after it, so history is tamper-evident. Git has been moving from SHA-1 to SHA-256 after practical SHA-1 collisions were demonstrated.
Merkle trees in repair
Cassandra's repair process builds a Merkle tree of each replica's data for a token range, compares trees between replicas, and streams only the ranges whose hashes differ. It is how replicas that drifted apart after failures are brought back into agreement.
Interview angle
Six questions, each worth 20 XP. Integrity is a standard follow-up in any storage or replication design.
Name the checksum, say where it is stored and verified, and say how bad data gets repaired.
Why do big systems checksum data even when the disk reports success?
Tip: press 1 to 3 to answer, Enter for the next one.
Break it
This is the (Saltzer, Reed and Clark, 1984): only the two ends of a transfer can verify the whole path, so a checksum made once by the sender over the original data and checked once by the final receiver is the one that matters. Per-hop checks are still useful as an optimisation, since they catch errors early and cheaply. Set the chance a device damages data in memory and the number of hops, then switch to end-to-end.
Leave hop-by-hop on and see corrupted files delivered. Switch to end-to-end: the same damage is caught.
Every hop verified what it received and re-protected what it sent, so a bit that flipped inside a device was carried forward with a fresh, valid checksum: about 76 corrupted files per million get through.
100,000 seeded transfers at an amplified damage rate, scaled back to your setting. A device is assumed to verify on receipt and re-checksum on send.
Where to go next