Write-ahead log

A database changes pages in memory, and those changes must survive a power cut. Writing every modified page to its final place on disk, at each commit, would be slow. Its writes land in random places. So databases use the write-ahead log (WAL): an append-only file of change records. Each change is written and forced to disk before the page holding it is written.

That single rule is the core of durability: log first, data later. A crash can then always be repaired by replaying the log against the older data pages.

The big idea

A commit becomes durable when its log records reach stable storage, after an fsync. The page changes can wait in the buffer pool and be written later, in batches, at a checkpoint. Writes to the log are sequential and cheap. Writes to pages are random and expensive, so the log turns many random writes into one sequential one.

Walking through it

Each record holds a log sequence number (LSN), a rising number that orders the changes. Each data page remembers the LSN of the last change it holds. Recovery uses that to avoid applying a change twice.

Here is a small redo-only sketch. The log records changes, and recovery replays them on top of the older data.

import json
log = [{"lsn": 1, "key": "balance:A", "val": 60},
       {"lsn": 2, "key": "balance:B", "val": 40}]
data = {"balance:A": 100, "balance:B": 0}     # pages on disk, stale after the crash

for rec in log:                               # redo the log in LSN order
    data[rec["key"]] = rec["val"]

print(data, sum(data.values()))

Output:

{'balance:A': 60, 'balance:B': 40} 100

The total stays 100, because the transfer was logged as a single change. Real systems also add an undo pass for transactions that were still open at the crash. The classic design is ARIES (Algorithms for Recovery and Isolation Exploiting Semantics, from IBM, 1992). It runs three passes: analysis, redo and undo. Most engines follow its ideas.

Group commit

Each fsync is expensive, so engines share them. When several transactions commit close together, one fsync covers all their log records. This is group commit. It keeps per-commit cost low under load, at the price of a small added latency.

Checkpoints

The log grows forever unless something trims it. A checkpoint writes dirty pages to their home locations and records how far the log is safe to discard. Recovery then starts at the last checkpoint, not at the start of the log. Frequent checkpoints make recovery faster but add write I/O. Rare checkpoints do the opposite.

Common mistakes

• Turning off fsync for speed on a primary database and assuming nothing is lost.
• Sizing the log too small, so checkpoints run constantly and recovery takes long.
• Assuming a replicated database doesn't need the WAL. Replicas often receive the same log, which is how streaming replication works.

Check yourself

• Why must the log reach disk before the page does? Answer: so that after a crash, the log holds the change needed to repair a page that was only partly written or never written.
• Why does group commit cut cost without weakening durability? Answer: one fsync covers several commits' records, and no commit is acknowledged before its records are on disk.

Key takeaways

• Write the log before the data page. Log writes are sequential, which is cheap.
• A commit is durable after its log record is fsynced.
• Recovery replays the log, and ARIES adds undo for open transactions.
• Group commit shares fsync costs, and checkpoints bound recovery time.

Further learning

The CMU Database Systems lectures on logging and recovery cover ARIES in detail, with worked examples.

Search for Andy Pavlo's CMU Database Systems lectures on YouTube.

Next, see composite and covering indexes, where the index design meets the query plan.