Crash Recovery: Replaying the Log

Building a Database Engine: Transactions & Concurrency

Chapter 3 · Crash Recovery: Replaying the Log

Chapter 2 built a log that survives a crash. It never actually used that log for anything — the whole point of Chapter 2's own Finding 1 was that the data file stayed wrong even though the WAL was perfectly intact. This chapter closes that loop: read every record the log can prove is real, and reapply it to the data file, on startup, before anything else runs.

The Real Recovery Routine

def recover(heap_file, wal_path):
    records = read_all_records(wal_path)      # Chapter 2's own checksum-verified reader
    records.sort(key=lambda r: r['lsn'])
    for r in records:
        page = load_page(r['new_page_bytes'])
        heap_file.write_page(r['page_num'], page)
    

That's the whole mechanism. It has no idea which of these records were already applied before the crash and which weren't — and, as the next finding shows, it doesn't need to.

Finding 1: A Crashed Write, Actually Restored

Chapter 2's own Finding 1 logged an update, simulated a crash before it was applied, and confirmed the data file stayed untouched while the WAL held a complete, correct record of what was meant to happen. Running recover() against that exact same scenario closes the gap.

Verified directly — the update is genuinely restored

Before recovery: the target page's bytes are still blank, exactly as Chapter 2 left them. After calling recover(heap_file, wal_path): the page matches the intended update exactly, and recover() reports 1 record applied. What Chapter 2 could only prove survived in the log now genuinely exists in the data file.

Finding 2: Replaying an Already-Applied Record Is Safe

A real crash rarely interrupts a single write in isolation — by the time it happens, some earlier writes in the log have usually already made it all the way to the data file. Chapter 2's own Exercise 1 built exactly this scenario: one page fully written and applied, a second page logged but never applied, both sitting in the same WAL.

Verified directly — reapplying a correct record changes nothing

Running recover() over a WAL containing both records applies both — including page 1's own record, even though page 1 was already correct before recovery ever ran. After recovery, both pages match their intended data exactly, with no different or wrong outcome from having replayed the already-correct one a second time. Recovery never has to work out which records are "new" — it can unconditionally replay everything, every time, because Chapter 2's own decision to log the complete new page rather than a delta makes reapplying an already-applied record a genuine no-op.

Finding 3: Truncating the Log Too Early Can Lose Data Forever

A WAL that's never cleared grows without bound — the obvious next step is to truncate it once recovery has replayed everything, reclaiming the space. The obvious place to put that truncation call is at the start of recovery, right after reading the records out: it feels safe, since the records are already sitting in a local Python list by then.

def recover_naive_truncate_first(heap_file, wal_path):
    records = read_all_records(wal_path)
    records.sort(key=lambda r: r['lsn'])
    open(wal_path, 'wb').close()          # BUG: clears the log before replay is confirmed done
    for r in records:
        page = load_page(r['new_page_bytes'])
        heap_file.write_page(r['page_num'], page)
    

This looks completely reasonable — the records are already read into memory, so what could truncating the file underneath them possibly break? The test: log three writes, apply none of them, then simulate a second crash during recovery itself — right after the first record has been applied, before the other two.

Verified directly — pages 1 and 2's own updates are genuinely, permanently gone

After the second crash: page 0 (applied before the interruption) is correct. Pages 1 and 2 — never reached — are still blank. And read_all_records(wal_path) now returns zero records: the log was already truncated, at the very start of this same recovery run, before any of the three records had actually been confirmed applied. The updates for pages 1 and 2 exist nowhere at all anymore — not in the data file, not in the log. This is the exact durability failure Chapter 2's entire WAL was built to prevent, reintroduced by the recovery routine meant to fix it.

The Fix: Truncate Last, Only Once Everything Is Confirmed Durable

def recover_safe_truncate_last(heap_file, wal_path):
    records = read_all_records(wal_path)
    records.sort(key=lambda r: r['lsn'])
    for r in records:
        page = load_page(r['new_page_bytes'])
        heap_file.write_page(r['page_num'], page)
    heap_file.file.flush()
    os.fsync(heap_file.file.fileno())        # confirm every applied page is durably on disk
    open(wal_path, 'wb').close()          # ONLY NOW is it safe to clear the log
    

Verified directly — the same interruption, no data lost

Simulating the identical second crash (same interruption point, same three records) against this version: right after the crash, read_all_records(wal_path) still returns all 3 records — the truncate call is the very last line in the function, and was never reached. Simply re-running recover_safe_truncate_last() from scratch — no special "resume from where I left off" logic anywhere — applies all three records correctly (redoing page 0's own record harmlessly, per Finding 2), and only then, with everything genuinely durable, does the log finally get cleared.

Finding 2 and Finding 3 depend on each other directly: it's only because replaying an already-applied record is provably safe that "just keep the log around and re-run recovery in full after any interruption" is a correct strategy at all, rather than something that risks corrupting already-correct pages.

Where This Connects

This chapter's finding	What it connects to
Recovery closing Chapter 2's own crash-survival gap	Chapter 2 (this course) — the exact scenario built there is resolved here, not re-explained from scratch
Idempotent replay of already-applied records	Chapter 2's own Exercise 1 — the "WAL ahead of the data file" scenario built there is directly reused as this chapter's own opening test
Truncating too early destroying otherwise-recoverable data	Building a Database Engine: Storage & Query Fundamentals Chapter 4 (Course 1) — the dormant, never-written page-header bug found there was also a case of code that looked obviously safe until a real restart exposed it

Hands-On Exercises

Exercise 1

Run a write through completely (logged, applied, heap file fsynced, WAL cleanly truncated), then call recover() against that now-empty WAL. Confirm it applies zero records and leaves the already-correct page completely unchanged.

📄 View solution

Exercise 2

Log three separate updates to the same page (three genuinely different versions of its content), never apply any of them, then run recover(). Confirm all three replay in LSN order and the final page matches the last one logged — exactly as if the original three writes had never been interrupted at all.

📄 View solution

Exercise 3

Log updates to two different pages, simulate a crash inside recover() itself right after the first page is applied but before the second. Confirm the WAL is untouched by this plain recover() (unlike the naive truncate-first version), then re-run recover() a second time and confirm both pages end up correct.

📄 View solution

Chapter 3 Quick Reference

Recovery: read every valid WAL record, sort by LSN, reapply each one to the heap file — unconditionally, every time
Verified Finding 1: a write Chapter 2 showed surviving only in the log is now actually restored to the data file
Verified Finding 2: reapplying an already-applied record is a genuine no-op — safe because each record logs the complete new page, not a delta
Verified Finding 3: truncating the WAL before replay is confirmed complete can permanently lose data if recovery itself is interrupted — fix: fsync the data file, then truncate the log, never the other way around
Next chapter: Atomicity — undo logging and rollback, closing the multi-step "insert a row, then update its indexes" gap Chapter 1 opened this course with