Where the Truth Stops

Torn writes, CRC, and finding the edge of what survived.

Picture recovery scanning a log forward from the last checkpoint. It reaches the final record. There is a valid magic byte. There is a length field reading 200. And there are 200 bytes following it that parse cleanly into a well-formed record.

Every check passes. The record is fiction.

The first 71 bytes are real: they made it to disk before the crash. The remaining 129 are whatever happened to be occupying that block before this write ever started. And nothing about the record's structure tells us where the truth stops and the leftovers begin.

Corruption that looks like corruption is a gift. Nobody ever writes a postmortem about the bytes that looked wrong.

That is the thing I want you to sit with. Torn writes do not announce themselves. They do not arrive corrupted-looking. They look like data, because they are data. They are just somebody else's.

6.1 Two Candidates and a Missing Number

If structure cannot tell us where the record stops, we need to ask what can. There are two answers, and they differ in a way we can put a number on, which is the whole reason to prefer one.

The first: trust the framing. If the magic bytes check out and the length field points at something parseable, the record is real.

The second: do not trust framing at all. Verify the content.

The ratio that separates them is a coincidence rate, and it is a lopsided one. Structural framing has no floor on how often it accidentally looks right. A length field is two to four bytes. When a device has whole sectors of stale data sitting immediately behind your last good write, the odds of some short field reading as a plausible small number are not remotely negligible. They are not even small.

A 32-bit checksum has a known, tiny coincidence rate: roughly 1 in 4,294,967,296 that an altered message hashes to the same value by chance.

Four billion to one against, versus whatever the stale bytes happen to look like today. That is not a close call, and it is not a judgement call either.

6.2 The Axioms

So we want an arithmetic check rather than a structural one. Before we build it, here is what the standard one actually promises, because the guarantees are sharper than most people expect and the one gap in them is the whole of section 6.4.

The mechanism here is arithmetic, not heuristic, and that distinction is the reason it does not share framing's blind spot. A CRC does not care whether the bytes look like a record. It has no opinion about what a record looks like. It only cares whether they divide down to the value the writer committed to before the crash.

6.3 Doing the Division

Long division, with subtraction swapped for XOR. You already know how to do this; you just did not know it had a Galois field in it.

I want to do this by hand. Not because you will ever need to, but because "it's just arithmetic" is the sort of phrase that stays abstract forever unless somebody makes you watch it happen once.

Take the message 1101011011 and the generator polynomial x⁴+x+1, which is 10011, degree 4, so a 4-bit CRC. Append four zero bits and divide, XOR-ing the generator in wherever the leading bit is 1:

  11010110110000    ← message with 4 zero bits appended
  10011              XOR (leading bit at pos 0 is 1)
  ───────────
  01001110110000
   10011             XOR (leading bit at pos 1 is 1)
   ───────────
  00000010110000                     (pos 2–5: leading bit 0, skip)
        10011        XOR (leading bit at pos 6 is 1)
        ───────────
  00000000101000
          10011       XOR (leading bit at pos 8 is 1)
          ───────────
  00000000001110

  remainder: 1110   ← the CRC

That is long division. The kind you learned at nine years old. The only difference is that subtraction has been replaced by XOR, so there are no carries and no borrowing, which if anything makes it easier than the version they taught you.

That 4-bit remainder ships alongside the message. On read-back we run the same division over the record including its stored remainder, and a clean write divides evenly and lands on zero.

Four billion to one is a comfortable margin. It is also a number you will meet in person if you write enough records.

A torn write, real bytes followed by stale ones, essentially never does. And the reason is worth stating plainly: the stale tail was not chosen to satisfy this particular division. It was chosen by whatever used to live on that block, months ago, by a process that had never heard of us.

6.4 What This Rules Out

This rules out "trust the length field" as a recovery strategy. Good.

But it also sets a trap for the checksum itself, and I want to walk into it deliberately, because it is the most satisfying mistake in this book.

Start the division register at zero, and an all-zero payload always produces an all-zero remainder.

Work it through with the long division above. If every bit of the message is zero, the leading bit is never 1, so the divisor never gets XORed in, not once. Zero goes in. Zero comes out. Every time.

Now, you might reasonably file that as a corner case not worth worrying about. I would like to talk you out of that, because zeroed blocks are one of the most common shapes a torn write takes. Plenty of filesystems and devices hand back zero-filled bytes for storage that was allocated but never written. This is not exotic. This is Tuesday.

Zero is the most popular number in computing, and every check you write should be asked what it does when handed a great many of them.

So picture the crash that leaves us a real header, followed by all zeros where the payload and the checksum should be. The zero-seeded CRC computes 0. It reads the stored trailer, which is also 0. It declares a match.

And there it is: corruption that looks valid, which is the exact failure this chapter opened with, sneaking back in through the one mechanism we built specifically to catch it. We did not fail to check. We checked, carefully, with real arithmetic, and the arithmetic said yes.

The fix is one line. Seed the register with a nonzero value before you start. CRC-32's standard does exactly this, with 0xFFFFFFFF. An all-zero message no longer produces an all-zero result, the degenerate case that used to sail through now perturbs the register, and it gets caught like anything else.

Thirty-two bits of careful mathematics, defeated by a block of nothing at all, and fixed by starting somewhere other than nothing.

One line. And you only ever find it by asking what your own check does on its worst input, rather than on a typical one.

6.5 The Pictorial

Here is what recovery sees when it walks the log and hits the crash. Two good records, then one that passes every structural test it has and fails the only test that counts:

 record 1 [ok, CRC matches]
 record 2 [ok, CRC matches]
 record 3 [header parses ✓] [71 real bytes][129 stale bytes] [CRC: NO MATCH]
                                           ▲
                                   the edge of truth
                               recovery stops replaying
                                      right here