Write-Ahead Logging Fundamentals

The durability problem

Suppose your database writes changes directly into its B-tree pages in place, and the process crashes halfway through updating a page — power loss, OS kill, whatever. The page might now be in an inconsistent, half-written state: some bytes from the new write, some stale bytes from before. There's no way to tell "how far" the write got, and no way to undo it. In-place updates and durability are fundamentally in tension.

The fix nearly every real database uses is the write-ahead log (WAL): before modifying the actual data pages, first write a description of the change to an append-only log, and only then apply it to the pages. The name says the mechanism: you log ahead of (before) you write. If a crash happens mid-write, the log has a durable, ordered record of everything that was supposed to happen, and recovery (next lesson) can finish the job by replaying it.

Why append-only?

The log is a simple sequential file (or in this exercise, an in-memory list) that only ever grows at the end. This matters for two reasons:

1. Sequential writes are cheap — no seeking, no read-modify-write of an existing structure, just appending. On real disks this is dramatically faster than random writes into a B-tree's scattered pages.
2. Ordering is implicit and unambiguous. Because entries are appended in the order operations happened, replaying the log from the start reproduces the exact same sequence of changes — this is essential for correctness on recovery.

What goes in the log

Only write operations — INSERT, UPDATE, DELETE — get logged. Reads (SELECT) don't change state, so there's nothing to redo if a crash happens during one; logging them would be pure overhead.

Each entry needs, at minimum:

• A sequence number (monotonically increasing) — this gives entries a total order and is what checkpointing (a later lesson) uses to know "everything up through sequence N is safely on disk, entries after N still need replaying."
• The operation type (INSERT / UPDATE / DELETE).
• The target table.
• The data needed to redo the operation — for an INSERT, that's the row values; for a DELETE, enough to identify which row (e.g. its key); for an UPDATE, the target and the new values.

function log_write(op, table, data):
    seq = next_sequence_number()
    entry = {seq, op, table, data}
    wal.append(entry)
    return entry

The commands in this exercise

• WAL ON — enable logging; until this is on, don't record entries (this exercise treats logging as opt-in, so you can compare behavior with/without it).
• WAL DUMP — print every logged entry, in order, in the format <sequence_number> <operation> <table> <data>. This is your debugging window into "what did the system think happened."
• WAL REPLAY — walk the log from the beginning and re-apply each entry's operation to rebuild state from scratch. This is the same mechanism crash recovery uses, just triggered manually here rather than after a simulated crash.

Edge cases

• Formatting <data> consistently — an INSERT's data (multiple column values) needs a deterministic, parseable representation so WAL DUMP's output is exact and WAL REPLAY can parse it back into the same operation it logged.
• Sequence numbers must never repeat or go backward, even across multiple WAL ON/logging sessions in one REPL run — they're the backbone of ordering.
• WAL REPLAY before anything was logged — should be a no-op, not an error.
• Logging only after WAL ON — writes issued before the log is enabled shouldn't retroactively appear in WAL DUMP.

This lesson is purely about the log itself — get logging correct and complete here, because the next two lessons (Crash Recovery, Checkpointing) build directly on replaying and truncating exactly this structure.