Write-Ahead Logging and Recovery

• Buffer pool — memory. Fast, and gone the instant power is lost.
• Data pages — durable, but scattered across the disk, so writing them means random I/O.
• Log — durable and strictly append-only, so writing it is sequential and therefore cheap.

The entire design follows from that asymmetry. Do the cheap durable thing (append to the log) immediately, and the expensive durable thing (write data pages) whenever convenient.

1. 1The log record for a change must reach disk before the changed data page does. Otherwise a crash could leave a modified page on disk with no undo information — atomicity broken.
2. 2All of a transaction's log records must reach disk before its commit is acknowledged. Otherwise a crash could lose work the user was told had succeeded — durability broken.

An update record ⟨T, item, old, new⟩ carries both values: old so the change can be undone, new so it can be redone. Both directions are needed, because at recovery time you do not yet know which transactions committed.

Redo — scan forward and reapply the new value of every update record, including ones from transactions that never committed. This is deliberate: applying everything makes recovery idempotent, so a crash during recovery is harmless and it can simply be run again.

Undo — scan backward for transactions with a begin record but no commit record, and restore their old values. What remains is exactly the committed work and nothing else.

Without checkpoints, recovery would scan from the beginning of time. A checkpoint flushes dirty pages and records which transactions were active, so recovery starts there — which is what bounds restart time.

Two policy choices decide what recovery has to do. Steal allows an uncommitted transaction's pages to be written to disk — which is why undo is needed. No-force allows a transaction to commit without its pages being written — which is why redo is needed.

Real systems run steal / no-force, the combination requiring both undo and redo, because it gives the buffer manager complete freedom about when to write anything. The alternative — no-steal/force — needs neither, and cripples the buffer pool. ARIES is the algorithm that implements steal/no-force properly, and it is what almost every relational database uses.