Implement a Write-Ahead Log (WAL) in C

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.

c
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 implements a simplified Write-Ahead Log.

Requirements:

Define a LogRecord struct with: lsn (int), page_id (int), old_value (int), new_value (int), checksum (unsigned int)
Implement a checksum function: XOR of all fields plus a magic number 0xDEADBEEF
Implement wal_append() that adds a record to an in-memory log array
Implement wal_recover() that scans the log and replays changes to a page array
Simulate a database with 4 pages, initially all zeros
Simulate transactions:
- T1: set page 1 to 100, page 2 to 200
- T2: set page 1 to 150 (overwrite)
- T3: set page 3 to 300
Append all changes to the WAL with proper checksums
Print the WAL contents (each record with LSN, page, old, new, checksum)
Simulate a crash by resetting pages to a "checkpoint" state: page 1=50, others=0 (simulating that only some changes reached disk)
Run recovery: replay WAL records where new_value should be applied
Print pages before and after recovery
Simulate log corruption by modifying one record's new_value and show that the checksum detects it

Log Before Data Pages Change

WAL Record Shape

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

c
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 implements a simplified Write-Ahead Log.

Requirements:

Define a LogRecord struct with: lsn (int), page_id (int), old_value (int), new_value (int), checksum (unsigned int)
Implement a checksum function: XOR of all fields plus a magic number 0xDEADBEEF
Implement wal_append() that adds a record to an in-memory log array
Implement wal_recover() that scans the log and replays changes to a page array
Simulate a database with 4 pages, initially all zeros
Simulate transactions:
- T1: set page 1 to 100, page 2 to 200
- T2: set page 1 to 150 (overwrite)
- T3: set page 3 to 300
Append all changes to the WAL with proper checksums
Print the WAL contents (each record with LSN, page, old, new, checksum)
Simulate a crash by resetting pages to a "checkpoint" state: page 1=50, others=0 (simulating that only some changes reached disk)
Run recovery: replay WAL records where new_value should be applied
Print pages before and after recovery
Simulate log corruption by modifying one record's new_value and show that the checksum detects it

Topic Overview

Log Before Data Pages Change

WAL Record Shape

Working Through the Exercise

Why for this exercise

Implementation Task

Progressive Hints

Resources

Open Source

Implement a Write-Ahead Log (WAL) in C

Topic Overview

Log Before Data Pages Change

WAL Record Shape

Working Through the Exercise

Why for this exercise

Implementation Task

Progressive Hints

Resources

Open Source