§45.1–45.3Disk Failure Modes and Detecting Corruption with Checksums

Data integrity data integrity Also called data protection: ensuring that the data a storage system returns is identical to what was written to it, despite the unreliable nature of modern storage devices. This chapter's central concern — the reliability of the data itself, complementing RAID's whole-disk reliability. defined in ch. 45 — open in glossary (or data protection) asks a question RAID’s whole-disk reliability didn’t: when a storage device hands a block back, is it really the block you stored? Modern disks mostly work — but occasionally return a bad block, sometimes without even knowing it.

45.1 Disk Failure Modes

Early RAID assumed the fail-stop fail-stop The classic disk-failure model, assumed by early RAID: a disk is either entirely working or has failed completely, and the failure is straightforward to detect. Simple to build around, but it ignores partial faults like latent sector errors and corruption. defined in ch. 45 — open in glossary model: a disk is either entirely working or entirely, detectably dead. Real disks are messier. The fail-partial fail-partial The modern (fail-partial) disk-failure model: a disk can still fail entirely, but it can also seem to be working while individual blocks become inaccessible (latent sector errors) or return the wrong contents (corruption). Faults may be non-silent (an error is returned) or silent (wrong data is returned). Introduced by Prabhakaran et al.'s IRON File Systems work. defined in ch. 45 — open in glossary model (from the IRON File Systems study) says a disk can seem healthy yet have individual blocks fail:

Two single-block faults matter, and they differ in one crucial way — whether the disk knows something is wrong:

• A latent sector error latent sector error A latent sector error (LSE) occurs when a disk sector (or group of sectors) is physically damaged — e.g. a head crash scrapes the surface, or a cosmic ray flips bits. The drive's in-disk error correcting code detects the bad bits and, if it cannot fix them, returns an explicit error when the block is read. Because it is detected, an LSE is a non-silent partial fault and is relatively easy to recover from using redundancy. defined in ch. 45 — open in glossary (LSE): a sector is physically damaged (a head crash, a cosmic-ray bit flip). The drive’s in-disk error correcting codes (ECC) error correcting code Redundant bits (ECC) stored in the disk that the drive uses to determine whether a block's on-disk bits are good and, in some cases, to repair them. If the ECC cannot correct the error, the drive returns an error rather than silently handing back bad data — turning many faults into detectable (non-silent) ones. defined in ch. 45 — open in glossary catch the bad bits and, if they can’t repair them, return an error. Loud and detected.
• Block corruption block corruption A disk block silently holds the wrong contents — e.g. buggy firmware wrote it to the wrong place (a misdirected write) or it was garbled crossing a faulty bus — while the disk's ECC still reports the block as good. The disk gives no indication of the problem, so this is a silent fault that must be detected with checksums. defined in ch. 45 — open in glossary : the block holds the wrong contents (buggy firmware misdirected a write; a faulty bus garbled the bytes) but ECC still says it’s fine. The disk returns bad data with no warning — a silent fault silent fault A fault the device gives no indication of: it returns wrong data as though it were correct. Contrast a non-silent partial fault, where the disk returns an explicit error. Block corruption is the canonical silent fault, and is why checksums are needed for detection. defined in ch. 45 — open in glossary .

Just how often? Over ~1.5 million drives across three years, LSEs and corruption were rare but far from negligible:

The studies found more texture worth knowing: faults cluster in space and time (a disk with one LSE tends to get more, nearby); the annual LSE rate rises in a drive’s second year and grows with disk size; corruption rates vary wildly between models of the same class; and corruption is only weakly correlated with LSEs. The takeaway is blunt: a reliable storage system must include machinery to detect and recover from both.

45.2 Handling Latent Sector Errors

LSEs are the easy case, precisely because they are detected. When a read returns an error, the system just rebuilds the block from whatever redundancy it has — the mirror copy in a mirrored RAID, or the parity group in RAID-4/5.

There is one nasty corner, though. When a whole disk dies and the RAID rebuilds it by reading every other disk in the parity group, an LSE on one of those disks means two blocks are missing at once — more than a single parity can recover:

NetApp’s RAID-DP answers this with a second parity disk — a second independent equation — so a full-disk failure plus a stray LSE can still be reconstructed. The cost is an extra parity block per stripe (softened by WAFL’s log-structured writes). As always, redundancy is the key to both detection and recovery.

45.3 Detecting Corruption: The Checksum

Silent corruption is the hard case: before you can recover a bad block, you have to know it’s bad. The workhorse for detection is the checksum checksum A small summary (typically 4–8 bytes) produced by a function computed over a chunk of data (say a 4 KB block). Stored alongside the data and recomputed when the data is read: if the stored and computed checksums differ, the data has been corrupted. The primary mechanism modern storage systems use to preserve data integrity. Common functions include XOR, addition, the Fletcher checksum, and the CRC. defined in ch. 45 — open in glossary — a small summary (say 4–8 bytes) computed over a data block (say 4 KB). Store it with the data; on every read, recompute it and compare. A mismatch means the data changed since it was written.

Common checksum functions

Different functions trade strength against speed. The simplest is XOR: fold every chunk of the block together with exclusive-or into one word. Here it is on a 16-byte block:

Stronger options climb the cost curve. Addition (2’s-complement, ignoring overflow) is fast but fooled by shifted data. The Fletcher checksum fletcher checksum A checksum (named for John G. Fletcher) computed from two running check bytes over the data bytes d_i: s1 = (s1 + d_i) mod 255 and s2 = (s2 + s1) mod 255. Simple to compute yet nearly as strong as a CRC, detecting all single-bit, all double-bit, and many burst errors. defined in ch. 45 — open in glossary keeps two running bytes:

$\begin{aligned} s_1 &= (s_1 + d_i) \bmod 255 \\ s_2 &= (s_2 + s_1) \bmod 255 \end{aligned}$

computed over every byte $d_i$ — catching all single- and double-bit errors and many burst errors, almost as strongly as a CRC. The cyclic redundancy check cyclic redundancy check A checksum (CRC) computed by treating the data block as one large binary number and dividing it by an agreed-upon value k; the remainder is the checksum. The modulo operation can be implemented very efficiently, making CRCs popular in storage and networking alike. defined in ch. 45 — open in glossary (CRC) treats the block as one giant number and takes its remainder modulo an agreed value k; the binary modulo is cheap, which is why CRCs are everywhere (networking included).

Whatever the function, no checksum is perfect: two different blocks can produce the same summary — a collision checksum collision When two data blocks with non-identical contents produce the same checksum. Collisions are unavoidable — a checksum squeezes something large (e.g. 4 KB) into a tiny summary (e.g. 4–8 bytes) — so a good checksum function is one that merely minimizes the chance of collision while staying cheap to compute. defined in ch. 45 — open in glossary . That’s unavoidable when you squeeze 4 KB into 8 bytes; a good function just makes collisions rare while staying cheap.

Checksum layout: where do the checksums go?

Computing a checksum is only half the story — you also have to store it. Start with a plain run of data blocks and no protection:

The natural fix is one checksum right before each block. But checksums are tiny (≈8 bytes) and disks write in 512-byte sectors, so this needs special 520-byte sectors (8 extra bytes each) from the drive maker:

On ordinary disks, the file system instead packs n checksums into one sector, followed by the n data blocks they cover:

This works everywhere, but separating a block from its checksum costs I/O: to overwrite block D1 you must read its checksum sector, update C(D1), then write back both the checksum sector and the data — one read and two writes, where the per-sector layout needed just one write. Another instance of TNSTAAFL.