Module 19 · Storage, indexing and recovery · Lesson 4 of 4
Write-ahead logging and crash recovery
How a database keeps atomicity and durability through crashes: failure types, the write-ahead logging rule, undo and redo records, steal and force policies, checkpoints, ARIES-style recovery in three passes.
Why it matters
When a database acknowledges a commit, it promises the change survives a power cut a millisecond later, and when a transaction aborts or crashes midway, it promises none of its changes remain. Both promises are kept by one mechanism: the write-ahead log. Recovery is a core DBMS exam topic, and the same log powers replication, point-in-time restore and change data capture, so understanding it explains a surprising amount of database operations.
The idea
What can fail
| Failure | Example | What is lost | Recovered by |
|---|---|---|---|
| Transaction failure | Constraint violation, deadlock victim, explicit rollback | That transaction's changes must be undone | Undo from the log |
| System crash | Power loss, kernel panic, database process killed | Memory (buffer pool, unflushed state) | Redo and undo from the log at restart |
| Media failure | Disk or volume destroyed | Data files | Restore a backup and replay archived log |
The write-ahead logging rule
Every change is first described in a log record appended to a sequential log: which transaction, which page, the before-image (for undo) and after-image (for redo), tagged with an increasing log sequence number (LSN). Two rules make it work.
- 1
WAL rule
A modified data page may be written to disk only after all log records describing its changes have been flushed. Each page stores the LSN of its last change (pageLSN) so the buffer manager can check. - 2
Commit rule
A transaction is committed only when its commit record, and everything before it, is on stable storage. The data pages themselves can be written later.
Writing the log is a sequential append, which is fast; writing scattered data pages is random I/O, which is slow. The log lets the database acknowledge commits after one sequential flush and write data pages lazily. Group commit batches many transactions' commit records into one flush to multiply throughput.
Buffer policies: steal and force
| Policy | Means | Requires |
|---|---|---|
| Steal | Dirty pages of uncommitted transactions may be written to disk (to free buffer frames) | Undo, to remove uncommitted changes after a crash |
| No-steal | Never write uncommitted changes | No undo, but the buffer pool must hold all of a transaction's pages |
| Force | Write all of a transaction's pages at commit | No redo, but slow random writes on every commit |
| No-force | Do not write data pages at commit | Redo, to reapply committed changes not yet on disk |
Real databases choose steal and no-force, the most flexible and fastest combination, which is exactly why the log needs both undo and redo information.
Checkpoints
Without help, recovery would replay the log from the beginning of time. A checkpoint records which transactions are active and which pages are dirty (and, in simpler schemes, flushes dirty pages). Recovery starts from the last checkpoint, and log older than what the checkpoint needs can be archived or recycled. Fuzzy checkpoints do this without stopping the world: they record the state while transactions keep running and flush pages in the background.
ARIES-style recovery
- 1
Analysis
Scan forward from the last checkpoint to rebuild the dirty page table and the list of transactions active at the crash (the losers). - 2
Redo
Scan forward from the oldest change that might not be on disk and reapply every logged change whose LSN is newer than the page's pageLSN, including changes by losers. This repeats history and restores the exact state at the crash. - 3
Undo
Roll back the losers, most recent change first, writing a compensation log record (CLR) for each undone change. CLRs are redo-only, so if the system crashes again during recovery, work already undone is not undone twice.
The same log, beyond recovery
Shipping the log to another machine and replaying it is replication (PostgreSQL streaming replication, MySQL's binlog). Archiving the log continuously and replaying it on top of a base backup gives point-in-time recovery, which is how you undo an accidental DELETE from an hour ago. Reading the log as a stream of row changes is change data capture. The System Design track uses all three; they all rest on the WAL.
Trade-offs
Write-ahead logging trades a sequential write on every change for fast commits and lazy data writes; steal and no-force maximise performance at the cost of needing both undo and redo. Frequent checkpoints shorten recovery time and cost background I/O. Synchronous commit (flush before acknowledging) gives full durability; asynchronous commit acknowledges early and risks losing the last few milliseconds of transactions in exchange for much higher throughput, a deliberate per-workload choice.
In an interview
Walk the guarantee end to end: "A commit returns once the commit record is flushed to the WAL; the data pages are written later. If we crash, recovery redoes everything after the last checkpoint and undoes transactions without commit records. So committed means durable even though the table files were never touched. Archiving that same WAL gives us point-in-time recovery and feeds the replicas."
Check yourself
Why do practical databases need both undo and redo information in their log?