Write-Ahead Log (WAL)

The Write-Ahead Log is the single most important mechanism for ensuring database durability and crash recovery. The principle is deceptively simple: before any change is applied to data pages (the actual tables and indexes on disk), a log record describing that change must first be written to a durable, append-only log file. If the system crashes at any point -- during the write, after the log but before the data page update, or even during recovery itself -- the WAL contains enough information to reconstruct the correct state. This guarantee, known as the WAL protocol, is the foundation upon which every transactional database builds its ACID durability promise.

A WAL record typically contains a Log Sequence Number (LSN) that uniquely orders all log entries, the transaction ID identifying which transaction generated this change, the page or row identifier being modified, and before-images and after-images of the changed data. The before-image is the data as it existed before the change (used for undo/rollback), and the after-image is the data after the change (used for redo/recovery). Some systems (like PostgreSQL) use physiological logging, which combines physical page identifiers with logical operation descriptions, reducing log volume while maintaining the ability to redo operations correctly even on pages that have been reorganized. The WAL is strictly append-only and written sequentially, making it extremely fast on both HDDs and SSDs because sequential writes avoid seek overhead.

Crash recovery using the WAL follows a well-defined protocol. When the database restarts after a crash, the recovery process has two phases: redo and undo. The redo phase scans the WAL forward from the last checkpoint and replays all logged changes, whether committed or not, to bring data pages up to date. This is necessary because committed transactions may have had their WAL records fsynced to disk but their dirty data pages may not have been flushed yet (the 'steal' policy allows dirty pages to be evicted). The undo phase then rolls back any changes from transactions that were active at the time of the crash and never committed, using the before-images in the WAL records. After recovery, the database is in the exact state it would have been in if all committed transactions' changes had been applied and all uncommitted transactions had been rolled back.

Checkpoints are the mechanism that bounds recovery time. Without checkpoints, recovery would need to replay the entire WAL from the beginning of time. A checkpoint forces all dirty data pages to be flushed to disk, then records a checkpoint record in the WAL with the LSN of the oldest dirty page. Recovery only needs to start from this checkpoint LSN, not from the beginning. Fuzzy checkpoints (used by most modern databases) allow the system to continue processing transactions during the checkpoint flush, recording the set of dirty pages at checkpoint start and ensuring they are all flushed by checkpoint end. The trade-off is clear: more frequent checkpoints reduce recovery time but increase I/O overhead during normal operation. Most production databases configure checkpoint intervals of 5-15 minutes, limiting recovery time to that window.

Beyond crash recovery, the WAL serves as the backbone for database replication. PostgreSQL's streaming replication works by shipping WAL segments (typically 16MB files) from the primary to standby servers, which replay them to maintain an identical copy of the database. MySQL's binary log serves a similar purpose, recording logical or row-level changes that replicas apply in order. This dual use of WAL -- for both crash recovery and replication -- makes it the most critical component in any database deployment. Group commit is the key optimization for WAL throughput: instead of issuing an fsync for every individual transaction commit, the database batches multiple concurrent commits into a single fsync call, amortizing the expensive disk flush across dozens or hundreds of transactions. This can improve commit throughput by 10-50x under concurrent workloads.

Imagine an accountant managing a large ledger with thousands of account balances. Before changing any balance in the ledger, the accountant first writes the change in a sequential journal: 'Transfer $500 from Account A to Account B -- Account A was $2000, now $1500; Account B was $3000, now $3500.' Only after the journal entry is written in ink does the accountant update the actual ledger pages. If the accountant is interrupted mid-update (a crash), the journal shows exactly which changes were recorded but not yet applied to the ledger. A colleague can read the journal, check which ledger pages match the journal entries, and complete any unfinished updates or undo any partial changes. The journal is the WAL; the ledger pages are the data files.