Crash Recovery & Write-Ahead Logging

A crash can strike at any instant, potentially with transactions half-applied. Recovery restores a clean, consistent state and upholds two ACID guarantees: durability (a committed transaction's changes survive any later crash) and atomicity (an unfinished transaction leaves no trace). The mechanism behind both is the write-ahead log.

Write-ahead logging (WAL)

The rule is simple: *record the change before applying it*. Before a data page is modified, the database appends a log record <transaction, item, old value, new value> to permanent storage. Because the log always leads the actual data, recovery has enough information to redo a change that never reached the disk, or undo one that did.

Checkpoints

Without help, recovery would have to replay the entire log from the beginning of time. A checkpoint is a periodic marker meaning everything up to it is safely on disk — so recovery need only scan back to the *last* checkpoint, not the start of history.

The three recovery phases (ARIES)

1. 1Analysis — scan forward from the last checkpoint to rebuild which transactions were in flight and which had committed.
2. 2Redo — re-apply the *new values* of every logged change since the checkpoint, bringing the on-disk state up to the moment of the crash (including work that had committed but not yet been flushed).
3. 3Undo — for every transaction that had *not* committed at the crash, roll its changes back using the *old values*, as if it never ran.

A worked crash

Consider this log. T1 commits; T2 does not before the crash.

<T1 start>
<T1, A, 500, 400>      -- old 500, new 400
<CHECKPOINT>
<T1 commit>
<T2 start>
<T2, B, 200, 300>      -- old 200, new 300
         *** CRASH ***  (no <T2 commit>)

Recovery from the checkpoint:
  REDO T1:  A = 400   (T1 committed -> apply new value)
  UNDO T2:  B = 200   (T2 uncommitted -> restore old value)