Write-Ahead Logging: Durability Before the Data Itself

Building a Database Engine: Transactions & Concurrency

Chapter 2 · Write-Ahead Logging: Durability Before the Data Itself

Chapter 1 named the gap without closing it: write_page() calls flush() but never os.fsync(), and even if it did, a crash between logging intent and applying it could still leave a table's own pages and indexes disagreeing. A write-ahead log is the real, standard mechanism that turns "I hope this happened" into something verifiable — write down exactly what's about to change, force it to disk, and only then touch the actual data. If a crash happens after the log write, the record survives. If it happens before, nothing was promised yet. There's no third case.

A Real WAL Record Format

Each record is length-prefixed and checksummed, so a reader never has to guess where one record ends and the next begins, or trust bytes it can't verify:

# [4 bytes: payload length][4 bytes: CRC32 of payload][payload]
# payload = [8 bytes: LSN][4 bytes: page_num][PAGE_SIZE bytes: new page data]

def build_record(lsn, page_num, new_page_bytes):
    payload = struct.pack('>QI', lsn, page_num) + new_page_bytes
    crc = zlib.crc32(payload)
    return struct.pack('>II', len(payload), crc) + payload
    

The LSN (log sequence number) is a strictly increasing integer identifying each record — Chapter 3's own recovery routine will need it to know exactly where it left off. This chapter logs the entire new page image, not a small delta — deliberately simple, and it buys something important later: reapplying an already-applied record is harmless, since writing the same complete page twice produces the identical result either time (this matters directly for Exercise 1, below).

The One Non-Negotiable fsync in This Engine

class WAL:
    def append(self, page_num, new_page_bytes):
        lsn = self.next_lsn
        self.next_lsn += 1
        record = build_record(lsn, page_num, new_page_bytes)
        self.file.seek(0, os.SEEK_END)
        self.file.write(record)
        self.file.flush()
        os.fsync(self.file.fileno())      # the durability guarantee actually lives here
        return lsn

def write_page_with_wal(wal, heap_file, page_num, page):
    wal.append(page_num, bytes(page.data))   # STEP 1: log first, durably
    heap_file.write_page(page_num, page)     # STEP 2: apply to the real data file
    

Why fsync specifically here, and not everywhere

Chapter 1 pointed out that Course 1's own HeapFile.write_page() never calls os.fsync() at all — and this course still doesn't add it there. Calling fsync() on every single data-page write would be correct but needlessly slow, forcing a real disk commit on every write regardless of size. The actual guarantee a WAL needs is narrower: only the log write has to be durable before the operation is considered "logged" at all — the data page itself can be written lazily, exactly as it always was, because the log is now the thing standing behind it if a crash happens first.

Finding 1: A Logged-but-Unapplied Change Survives a Simulated Crash

A "crash" is simulated the same honest way Chapter 1 did it: call wal.append() directly and never call heap_file.write_page() at all — exactly what a process death immediately after the WAL's own fsync() returns, but before the data write runs, actually looks like.

Verified directly — the data file is honestly untouched, the log is honestly intact

After the simulated crash, reopening the heap file (a fresh HeapFile pointed at the same path) shows the target page completely unchanged from before — the intended update genuinely never happened at the data layer, exactly as expected; nothing here replays it yet. But reopening the WAL file and calling read_all_records() finds exactly one record, with the correct LSN, correct page number, and a new_page_bytes value that matches the intended update byte-for-byte. The data update was lost. The information needed to redo it wasn't.

That distinction — the update didn't happen, but nothing about it was forgotten — is the entire point of this chapter, and precisely what Chapter 3's own recovery routine will use.

Finding 2: A Torn Trailing Record — Two Very Different Failure Modes

A real crash can interrupt the WAL's own append in the middle, too — the OS commits some of a record's bytes but not all of them before the process dies. This test builds one complete record, then writes only the first half of a second record's real bytes, simulating exactly that.

Verified directly — the real reader discards the torn record cleanly

read_all_records() (bounds-checked and checksum-verified) returns exactly 1 record — the complete first one. It correctly recognizes that the second record's declared length runs past the actual end of the file, stops reading right there, and simply treats everything after that point as if it had never been logged at all — which is honest, since it never finished being written durably in the first place.

Verified directly — a naive reader is silently, actively wrong, not just careless

A naive reader with no bounds check and no checksum — one that simply trusts whatever length the (fully intact) 8-byte header of the torn record declares — doesn't crash and doesn't notice anything is wrong. It slices out whatever bytes happen to be available (Python slicing silently returns fewer bytes than requested rather than raising an error), successfully unpacks a genuinely correct LSN and page number from the surviving front of the payload, and reports a second, fully-formed-looking record — with a new_page_bytes field that is only 118 bytes long, not the required 256. Fed into a real recovery routine, this would silently write a truncated, garbage page into the middle of a real table, under a completely correct LSN and page number that give no outward sign anything is wrong. A crash here would have been the safe outcome; this is worse than a crash.

Finding 2b: Why Bounds-Checking Alone Isn't Enough

A truncated file is one kind of corruption. A single flipped bit somewhere inside an otherwise complete, correctly-sized record is another — and a length check alone has nothing to say about it.

Verified directly — only the checksum catches in-place corruption

A record was built normally, then one byte deep inside its payload (well past the LSN and page number fields) was flipped, leaving the file's own total length and the record's own declared length completely correct. A bounds-check-only reader (no checksum) reports 1 record — it accepts the corrupted payload outright, since nothing about the file's shape looks wrong. The checksum-verified reader reports 0 — it recomputes the payload's real CRC32, finds it doesn't match the stored one, and correctly rejects the record. Truncation and in-place corruption are genuinely different failure shapes, and this engine's own two independent checks — length bounds, then checksum — exist because neither one alone catches both.

Where This Connects

This chapter's finding	What it connects to
Log-before-apply ordering, and a durable-but-unapplied record	Chapter 1 (this course) — the exact `flush()`-without-`fsync()` gap identified there is what this chapter's WAL closes, specifically for the log itself, not every write
A torn trailing record correctly discarded	Chapter 3 (this course) — recovery starts by reading exactly this list of valid records and deciding what still needs to be reapplied
A naive reader silently fabricating a plausible-looking corrupted record	Building a Web Browser Engine: Layout & Rendering Chapter 8's own bounds-clipping bug, and this site's own recurring "confidently wrong is worse than a crash" theme

Hands-On Exercises

Exercise 1

Perform two writes through write_page_with_wal() to two different pages — let the first complete fully (logged and applied), then simulate a crash right after logging the second (never calling heap_file.write_page() for it). Verify the data file has page 1's update but not page 2's, while the WAL contains records for both. Explain why it has to be safe for a future recovery routine to reapply page 1's own record too, even though it was already applied.

📄 View solution

Exercise 2

Write two records to a WAL file, close it, then simulate a crash by truncating the file so that only the first record survives (matching Finding 2's own torn-write setup). Open a brand-new WAL object pointed at the same file and confirm next_lsn correctly continues from the surviving first record's own LSN, not from any value that could be parsed out of the torn second record.

📄 View solution

Exercise 3

Corrupt a single byte inside a record's own 4-byte length field (rather than inside its payload, as Finding 2b did) and confirm how read_all_records() responds. Explain, in your own words, which of the two checks — the bounds check or the checksum — actually catches this specific kind of corruption, and why.

📄 View solution

Chapter 2 Quick Reference

A WAL record: length-prefixed and checksummed — [4B length][4B CRC32][LSN][page_num][new page bytes]
The rule: log first (durably, via os.fsync()), apply to the data file second — never the other way around
Verified Finding 1: a "crashed" write leaves the data file honestly untouched, but the WAL's own record of it survives completely intact and byte-exact
Verified Finding 2: a naive reader with no bounds check or checksum doesn't crash on a torn trailing record — it silently fabricates a plausible-looking, genuinely corrupted one
Verified Finding 2b: a length/bounds check alone can't catch in-place corruption — only a checksum can
Next chapter: Crash Recovery — actually replaying a WAL's own valid records to rebuild correct state after a real simulated crash