Recovery from Crashes Using the WAL

From "we have a log" to "we can actually survive a crash"

The previous lesson built the write-ahead log itself — an append-only, ordered record of every write. This lesson is where that log earns its keep: simulating a crash, and proving that the database's real state (its tables, its B-tree, whatever holds the "live" data) can be fully reconstructed from nothing but the log.

The two commands

• CRASH — wipe all in-memory data as if the process died and restarted. Critically, this must not touch the WAL itself — the whole point of a write-ahead log is that it's the durable record that survives exactly this kind of event, so if CRASH deleted the log too, there'd be nothing left to recover from.
• RECOVER — replay the WAL, in sequence-number order, from the beginning, re-applying every logged operation to rebuild the in-memory state that CRASH just wiped.

function crash():
    tables = {}        // wipe everything except the WAL
    btree = empty()

function recover():
    for entry in wal, in sequence order:
        apply(entry.op, entry.table, entry.data)

After CRASH followed by RECOVER, the database should look identical to how it looked right before the crash — same rows, same tables — because every committed write was durably logged before it was ever considered "done," and recovery is just deterministically re-running that log.

Committed vs. uncommitted — this is where transactions matter

The exercise specifies: after recovery, committed data is restored, but uncommitted transactions are rolled back — not replayed. This connects directly to the Transactions & ACID chapter later in this course. If your WAL entries can be part of an in-flight transaction (started with BEGIN, not yet finished with COMMIT), recovery has to distinguish "this operation belongs to a transaction that never committed" from "this operation belongs to a transaction that committed" (or was auto-committed, outside any explicit transaction).

The standard mechanism, which you can adapt to whatever your log entries look like: log a distinct marker for transaction boundaries (BEGIN <txn_id>, COMMIT <txn_id>) alongside the write entries, tagging each write with the transaction it belongs to. Recovery then works in two passes:

1. Scan the whole log first to determine which transaction IDs have a matching COMMIT entry.
2. Replay only the writes that either have no transaction (auto-commit) or belong to a transaction ID confirmed committed in step 1. Writes belonging to a BEGIN with no corresponding COMMIT are simply skipped — that's the "rollback" of an uncommitted transaction: it never gets applied during recovery in the first place.

This two-pass approach is exactly what real write-ahead logging protocols (like ARIES, which underlies most production databases) do at a conceptual level: analyze the log to determine transaction outcomes, then redo only what's confirmed durable.

Edge cases

• RECOVER called with an empty WAL — should simply leave the (already-empty, post-crash) state as-is, not error.
• Multiple CRASH/RECOVER cycles in a row — recovery should be idempotent in effect: recovering twice in a row (without new writes in between) should produce the same state both times.
• A transaction that began but was still open (no COMMIT or ROLLBACK) at the moment of CRASH — must not reappear after RECOVER.
• Interleaved committed and uncommitted transactions in the same log — recovery must correctly separate them by transaction ID, not just by log position.

Getting this right proves the core promise of a database: once an operation is acknowledged as committed, it survives any crash, no matter when it happens — which is the "D" (Durability) in ACID, and the entire reason the WAL chapter exists.