Implement a Write-Ahead Log (WAL) in C

Topic Overview

Log Before Data Pages Change

Write-ahead logging records intent in an append-only log before dirty pages hit disk. PostgreSQL WAL, SQLite rollback journal's successor, and RocksDB WAL all follow this pattern so crash recovery can redo committed work and undo incomplete transactions.

WAL Record Shape

Each entry carries a type, transaction id, payload checksum, and length. Appends are sequential, matching SSD and HDD strengths.

cCopy
Loading…

• Checkpointing truncates replay time by flushing dirty pages first
• Group commit batches multiple transactions per fsync
• Log sequence numbers order recovery replay
• Never mutate data pages before the WAL entry is durable

Working Through the Exercise

Keep the relevant documentation open while you implement. When your output disagrees with the reference, trace one failing case by hand before changing random lines.

• Trace first: walk one failing input step by step
• Read the manual: skim the official doc for the mechanism named in this task
• Compare baselines: save measurements from the prior step so speedups are honest

Why for this exercise

You will append records to a WAL buffer and implement redo application on recovery. This exercise requires writing the log record before updating the in-memory page copy.

Write a C program that recovers 8 pages from a write-ahead log, using LSNs and checksums to decide what to replay.

Input (stdin):

• First line: "checkpoint n": checkpoint is the highest LSN already flushed to the page files; n is the number of WAL records
• Next n lines: "lsn page_id old_value new_value checksum"
  • checksum = lsn ^ page_id ^ old_value ^ new_value ^ 0xDEADBEEF (unsigned 32-bit)

Recovery rules (scan records in order; replay is idempotent):

• Checksum mismatch: the record was torn by a crash mid-write: print "TORN LSN=<l>" and stop; nothing after a torn record can be trusted
• lsn <= checkpoint: the change is already on the page files: print "SKIP LSN=<l>", do not replay
• lsn > checkpoint with a valid checksum: print "REPLAY LSN=<l> page=<p> <old> -> <new>" and set page[p] = new_value
• If the scan reaches the end without a torn record: print "RECOVERY_COMPLETE"

Output (after the per-record lines):

• "REPLAYED r" and "SKIPPED s" counts
• "PAGES v0 v1 ... v7": page contents after recovery (all pages start at 0)
• "MIN_LSN <l>": the first LSN that had to be replayed, or -1 when nothing was replayed (empty log, everything already durable, or a torn first record)