STAGE 4 · THE WAL TAPE

The Black Box

Write down what you are about to do, fsync it, then do it, and the main file becomes disposable.

What you're wiring up

Right now a kill -9 at the wrong instant leaves your tree half written: a torn page, or a split that landed in the child but never reached the parent. No amount of careful ordering inside the main file fixes this on its own, because the disk can tear any single write.

Write-ahead logging is the promise that does fix it. Before touching the real file, append what you are about to do to a log and fsync it. Committed now means safely on the tape, and the main file is rebuildable: at every startup you replay complete frames and throw away a torn tail, detected by checksum.

This is the stage where your database stops being a toy. The harness will crash your process on purpose, at named points inside your own commit sequence, hundreds of times, and check one invariant: every batch is either fully present or fully absent.

# one WAL frame
[ pageID u32 | length u32 | payload | CRC32 of all prior bytes ]

# one transaction on the tape
frame(page 7)  frame(page 2)  frame(pageID = COMMIT)

# anything after the last valid COMMIT is discarded on replay

Assembly steps

[ 01 ]

Give the engine begin and commit: dirty pages accumulate in the cache and nothing touches the main file mid-transaction. A bare set or delete auto-wraps in a tiny transaction.

hint

Stage 1's dirty-page map already is the transaction's write set. You mostly have this for free.

[ 02 ]

Define the WAL frame (page id, length, payload, CRC over everything before it) appended to a .wal file, with a commit frame sealing each transaction.

hint

Checksum the header too. A torn header is just as real as a torn payload, and only the CRC can tell you.

[ 03 ]

Implement commit in exactly this order: append all frames plus the commit frame, sync the WAL, write pages to the main file, sync the main file, truncate the WAL. Write the order out as a numbered comment block.

hint

Both Sync calls are load-bearing. Delete either one and the crash tests will find you, which is precisely what they exist for.

[ 04 ]

Implement recovery inside Open: scan frames checking CRCs, replay every transaction that has a valid commit frame, discard everything after the first bad frame, sync, truncate.

hint

Recovery must be idempotent. A crash during recovery is just another crash, so replaying twice has to be harmless, and the harness tests exactly that.

[ 05 ]

Place the crash points the harness drives: honor BYHDB_CRASH_AT for wal_partial, after_wal_sync, db_partial, before_truncate and during_recovery.

hint

The starter ships crashpoint.Here(name). Placing each one honestly at a boundary in your commit sequence buys you a free proof about one ordering claim.

Go deeper (after it passes)

Read DDIA on reliability and on making B-trees reliable. The passages about fsync semantics and torn writes land completely differently after the gauntlet. Then look one layer down: filesystem journaling is the same idea, and the Redis track's flight recorder was its simplest possible form.