Crash Recovery: Redo, Torn Tails, Checksums

Why this stage exists

The last stage wrote the log and promised that a commit is safe the moment its commit record is synced. Until now nothing kept that promise. Stop the program at after_log_sync and start it again: the commit is in the log, the database file never got it, and the row is not there. Stop it at mid_page_write on a new file and the database file holds a header that points at pages it does not have.

Recovery keeps the promise. When the database opens, before anything reads the header, it looks at the log. Every transaction with a commit record gets its pages written into the database file, exactly as the commit would have done. Everything else in the log is ignored. Then the log is emptied, and the session starts on a file that holds every commit and nothing more.

What changes: what the log says after a crash

A crash can leave the log in a few shapes. Recovery reads the good records, those whose length, type and checksum hold, up to the first that does not:

A torn record is the normal case, not a disaster: the program was in the middle of an append when the power went, and the checksum is how recovery tells a record written whole from one that is not. A transaction whose commit record is missing or torn never committed. Its INSERT never printed its line, so nobody was told it succeeded, and losing it breaks no promise.

What changes: redo, then forget

Recovery writes page images, not changes. That makes it idempotent: if the program crashes half way through recovery, the log is still there, the next start replays the same images onto whatever got written, and the file ends up the same. That is why the log is emptied last, after the database file is synced.

It also runs before the header is checked, because the header can be one of the pages a commit was writing. A CREATE TABLE on a new file stopped after its first page leaves a file whose header names a catalog root that is not there. Reading that header first would fail; replaying the log first fixes it.

This engine only ever redoes: no-steal means the database file never holds an uncommitted page, so there is nothing to undo. ARIES, the recovery method behind DB2, SQL Server and, in spirit, PostgreSQL and InnoDB, allows uncommitted pages on disk and so runs three passes: analysis, redo of everything, then undo of the losers.

Output contract for this stage

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

r counts good records, c transactions with a commit record, d transactions with page records and no commit record.

What you should see when done

$droid --db notes.db -c "create table notes (id int, text varchar(100));"
Create table statement executed successfully
$DROID_FAILPOINT=after_log_sync droid --db notes.db -c "insert into notes (id, text) values (1, 'buy milk');"
$droid --db notes.db
[WAL] Recovery: records=2 replayed=1 discarded=0
Welcome to droid!
>select * from notes;
id | text
1 | buy milk
(1 rows)
[EXEC] rows_examined=1
>wal status
[WAL] Status: size=16 records=0
>.exit
exiting.. good bye!
$droid --db notes.db -c "select * from notes;"
id | text
1 | buy milk
(1 rows)
[EXEC] rows_examined=1

The INSERT never printed its line, and still the row is there: its commit record was synced before the program stopped. The second start prints no recovery line, because the first one emptied the log.

Now try the same crash, delete notes.db.wal before restarting, and the row is gone. That is the whole stage in one experiment.

Common bugs in this stage

• Reading the header before recovering. A file whose commit stopped after page 0 has a header the rest of the file does not match. Recover first, then check.
• Emptying the log before the file is synced. A crash between the two loses every commit the log held. Sync the database file, then cut the log.
• Replaying a transaction because its page records are good. Only a commit record makes a transaction committed. Collect the committed ids first, then replay.
• Trusting a record's length before checking it. A torn record's length field may be garbage. Check that the length is 4116 or 20 and that the whole record is in the file before reading it.
• Going on after a bad record. The first bad record ends the log. Records after it may look fine; they are not trusted, because the log is written in order and nothing after a gap is known to be complete.
• Printing the line when there was nothing to do. A log that is missing, empty or all garbage prints nothing.
• Counting recovery's I/O. pager stats starts after recovery, so the first line after it is the header's read.

Language notes

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

• C: a positioned write puts an image at its page's place and makes the file longer when needed, with no seek to get wrong. Sync the database file before you cut the log back to its header, never after.
• C++: the same calls through the file descriptor. A std::set<uint32_t> of committed ids built in a first pass keeps the replay loop simple.
• Rust: FileExt::write_all_at (Unix) writes at an offset; sync_all, then set_len(16) on the log. A HashSet<u32> of committed ids from a first pass over the records.
• Zig: file.pwriteAll(image, offset), then file.sync(), then setEndPos(16) on the log.