Page Checksums

Why this stage exists

Every stage so far has trusted the file. The program writes a page, reads it back later, and uses whatever bytes come back. Usually they are the bytes it wrote. Not always.

Disks return the wrong sector. A cable flips a bit. A power cut leaves half a page new and half old. A bug in some other program, or in this one, writes over the wrong offset. None of these announce themselves. The program reads the damaged page, finds a slot count that is a little off or a key that is not the one it stored, and does what those bytes say: returns a row that was never inserted, skips one that was, or follows a child pointer into the middle of nowhere. The worst outcome is not a crash. It is an answer that looks right and is not.

This stage makes damage loud. Every page carries a checksum of itself, written each time the page goes to the file and checked each time it comes back. A page that does not match is an error the moment it is read, before any of its bytes are believed.

It comes last in Flexible Storage because it changes a page layout, the subject of this part, and it comes before the write-ahead log because recovering from a crash starts with knowing which pages a crash has torn.

What changes: every page ends with a trailer

The last four bytes of every page, 4092 to 4095, are its trailer: the CRC32 of the page's other 4092 bytes, stored little-endian like every integer in the file.

Every page has one, whatever it holds: the header, the catalog and table leaves, internal nodes, slotted pages made by page init, and a page that only pager write ever touched. The program does not need to know what a page is to check it, which is the point: a damaged header must be caught before the program reads the header to find out what everything else is.

When it is written. Whenever a page goes to the file, the trailer is computed from the bytes the page holds at that moment and written with it. In this part that is the end of the session. The copy of a page in memory is never checked and its last four bytes mean nothing; only the file's copy has to be right.

When it is checked. Whenever a page comes from the file, the first time a session needs it, its trailer is checked before any byte of it is used. A page that does not match is 00609. The command that needed it prints that one line and nothing else: no rows, no partial result, and nothing changes. The bad page is not kept in memory, so the next command that needs it reads it and fails again, and a command that does not need it works as before. Opening checks page 0 the same way, after its magic, version and page size: a damaged header is 00609, the only line, with exit status 1.

CRC32 is not cryptography. It catches accidents, every change of a single byte and every burst of changes up to 32 bits long, but anyone who wants to change a page on purpose can recompute it. PostgreSQL uses a 16-bit checksum in each page header; InnoDB keeps its checksum in a trailer at the end of each page, as this tutorial does, and SQLite can with its checksum extension.

What changes: pages end at 4092

A layout that ran to the last byte of the page has to stop four bytes earlier. Internal nodes, the header's fields and the text pager write stores never come near the end, so they do not change. Slotted pages do: their records grew from byte 4096 down, and now they grow from 4092.

So:

• An empty slotted page has a record start of 4092 and free_space=4076. The first record ends at byte 4092.
• A new root leaf is 01 01, zeros up to byte 14, then fc 0f: a record start of 4092.
• A leaf holds 4076 bytes of cells and slots. Rows of 21 bytes still fit 140 to a leaf, since 4076 / 29 rounds down to 140 as 4080 / 29 did, but rows whose cells and slots take 510 bytes now fit seven, not eight.
• Any four cells still fit in an empty leaf: four of the largest take 4032 bytes, well within 4076.

Earlier cases that pinned 4096 or 4080, or compared a whole page of the file byte for byte, are retired here by name in the manifest. What they checked about SQL still has to pass.

What changes: db verify

db verify checks the whole file, and is how you find out which pages are damaged without tripping over them one statement at a time. For each page, in order, a page already in memory counts as good: it was checked when it was read, or made in this session and not written yet. Every other page is read and checked as any read is, so a good page stays in memory afterwards and a bad one does not. It changes nothing, and on a file with no pages it reports none and creates nothing.

Output contract for this stage

The full definition is on the output contract page, section 20.

Errors are checked by code, never by message. A wrong magic, version or page size is still 00608, checked before the trailer.

What you should see when done

A table, a restart, a check of the whole file:

Welcome to droid!
>create table users (id int, name varchar(1000), email varchar(1000));
Create table statement executed successfully
>insert into users (id, name, email) values (1, 'dan', 'd@e');
Insert statement executed successfully (1 rows)
>btree dump 2
[BTREE] Page 2: type=LEAF num_cells=1 free_space=4047
[BTREE]   Cell 0: key=1 (21 bytes)
>.exit
exiting.. good bye!

Welcome to droid!
>db verify
[DB] Verify: pages=3 bad=0
>.exit
exiting.. good bye!

Now damage one byte of page 2 in the file, anywhere, even in the empty middle of the page, and open it again:

Welcome to droid!
>select * from users;
[ERROR:00609] Page 2 failed its checksum
>select * from users;
[ERROR:00609] Page 2 failed its checksum
>db verify
[DB] Verify: pages=3 bad=1
[DB]   Page 2: checksum mismatch
>.exit
exiting.. good bye!

Things to notice. The SELECT printed no header and no rows, not even (0 rows): it did not get far enough to have a result. The second SELECT failed again, because the bad page was never kept. And db verify found page 2 without being told where to look.

Damage page 0 instead, and the program never gets as far as the welcome line:

$droid --db notes.db
[ERROR:00609] Page 0 failed its checksum
$echo $?
1

Common bugs in this stage

• Checking the page in memory. The trailer is written when the page goes to the file. A page you changed a moment ago has a stale trailer in memory, and that is fine; checking it there raises alarms on every write.
• Computing the checksum over 4096 bytes. The trailer cannot cover itself. It is the CRC32 of bytes 0 to 4091.
• Forgetting a kind of page. The header, the catalog, raw pages from pager write: every page the file holds gets a trailer, or the first db verify after a restart finds it bad.
• Writing the trailer big-endian. Every integer in the file is little-endian, this one too.
• A slotted page that still ends at 4096. The first record goes over the trailer, and the page fails its checksum after the next restart, or the record is cut when the trailer is written. Every place that knew the page ended at 4096 now needs 4092: the empty record start, free space, compaction and the capacity of a leaf.
• Keeping the bad page. A page that failed its check must not stay in memory, or the second statement reads it without complaint.
• Checking the header before its magic. A file that is not a droid database at all is still 00608; only a droid header with a wrong trailer is 00609.

Language notes

The page above is the same for every language. These are the only language-specific hints.

• C: there is no CRC32 in the standard library. Write the bitwise version first and check it against 0xCBF43926, then add a 256-entry table if you like. Use uint32_t throughout so the shifts are unsigned.
• C++: the same as C; std::array<uint32_t, 256> built once holds the table.
• Rust: write it yourself with u32 and >>, or compare yours with the crc32fast crate in a test. u32::to_le_bytes gives the trailer's four bytes.
• Zig: std.hash.Crc32 computes exactly this checksum; writing your own is still worth doing once. std.mem.writeInt with .little stores the trailer.