§45.4–45.9Using Checksums: Misdirected Writes, Lost Writes, Scrubbing, and Overheads

With a checksum layout chosen, we can put checksums to work — and then meet two sneakier failures they don’t yet catch.

45.4 Using Checksums

Verifying a block is a three-step ritual on every read: fetch the stored checksum $C_s(D)$, recompute the checksum $C_c(D)$ over the bytes you got back, and compare.

If they match, the data is (almost certainly) intact. If not, corruption is detected — recover from a redundant copy if you have one, else return an error. A checksum only detects; without another copy of the block, detection just tells you precisely how out of luck you are.

45.5 A New Problem: Misdirected Writes

Basic checksums assume the right data ends up in the right place. But a disk or RAID controller can commit a misdirected write misdirected write A failure mode where the disk or RAID controller writes the data correctly but to the wrong location (wrong block, or in a multi-disk system the wrong disk). Detected by storing a physical identifier — the disk and block numbers — together with the checksum, so a read can tell whether the right block is in the right place. defined in ch. 45 — open in glossary : the data is written correctly, just to the wrong location — block D_x lands at address y (clobbering D_y), or even on the wrong disk entirely. The block that lands is internally consistent, so its checksum happily matches — the fault is purely one of place.

The fix adds a physical ID to each block’s stored info: its own disk number and offset. On read, the client checks that the stored address matches the address it meant to read:

That extra redundancy — the disk and block numbers repeated next to each block — is worthless on a perfect disk, but it’s exactly what turns a silent misplacement into a detected corruption.

45.6 One Last Problem: Lost Writes

The nastiest failure is the lost write lost write A failure mode where the device reports a write as completed but never actually persists it, leaving the old block contents behind. Basic checksums and physical IDs still match the stale block, so detection requires either a write verify (read-after-write) or a checksum kept elsewhere — e.g. ZFS stores a checksum in each inode and indirect block, so a lost data write no longer matches. defined in ch. 45 — open in glossary : the device reports a write as complete but never persists it, leaving the old contents in place. Now both of our defenses are useless — the stale block still matches its own old checksum, and its physical ID is still correct:

The classic brute-force answer is a write verify (read-after-write): read the block straight back to confirm it reached the surface — safe, but it doubles write I/O. Sun’s ZFS takes a cheaper route: store each block’s checksum in its inode and indirect blocks. The write updates the inode’s checksum, so a lost data write no longer matches it. Only if the writes to both the inode and the data are lost together does the scheme fail — unlikely, though not impossible.

45.7 Scrubbing

When do all these checksums actually get checked? At access time — but most data is read rarely, so it would sit unverified while bit rot silently corrupts every copy. Disk scrubbing disk scrubbing Periodically reading through every block of the system and re-verifying its checksum (often nightly or weekly), so that rarely-accessed data does not silently rot until every copy is corrupted. Most latent sector errors in the Bairavasundaram studies were found this way. defined in ch. 45 — open in glossary closes that gap: the system periodically reads through every block and re-verifies its checksum, typically on a nightly or weekly schedule. (In the failure studies, most latent sector errors were found precisely this way.)

45.8 Overheads of Checksumming

Nothing is free. Checksumming’s costs split into the usual two kinds — space and time:

Space is nearly a rounding error; the time cost (CPU per block, plus any extra I/O for separated checksums and scrubbing) is the one you actually tune — hence the copy-and-checksum fusion and the scheduled, off-peak scrubs.

45.9 Summary — every defense closes one gap

Each layer of protection catches a failure the previous one couldn’t. Reading the table top to bottom is the whole chapter in miniature:

Different checksums guard against different faults, and as devices evolve, new failure modes will keep appearing — forcing us to revisit these ideas or invent new ones. Redundancy remains the key: it powers both the detection here and the recovery that follows.