Recovery Post-Crash

Concept. Recovery preserves committed changes and removes unfinished work after a crash. Committed work that never flushed is missing, so durability is at risk. Uncommitted work that did flush is present, so atomicity is at risk. Recovery fixes both in two passes over one log. The forward pass, REPLAY, re-applies every logged change top to bottom, redoing every row, committed or not, to rebuild the exact state at the crash. The backward pass, UNDO, then reverses every transaction still unfinished at the crash, with no COMMIT or ABORT in the log. A transaction that already aborted needs no undo, because the replay re-applied its rollback. Committed work survives the replay, which is durability; unfinished work is undone, which is atomicity. This repeat-history algorithm is ARIES, from IBM, and it leaves the database fully consistent, ready for new traffic.

Intuition. When the server crashes mid-rush, the log shows Mickey, Minnie, and Daffy were all mid-Premium-purchase. The forward pass replays all three in case their account-table pages never flushed, and notes that Mickey and Minnie COMMITted but Daffy did not. The backward pass then reverses Daffy's charge, because his transaction never finished. Mickey and Minnie stay Premium, Daffy is refunded, and the database is back online.

A crash interrupts running transactions; on reboot the WAL decides which committed work survives, green, and which uncommitted work is thrown away, orange.

Figure 1. A crash leaves recovery one question: which work survives, which gets thrown away. The whole answer is in the **WAL**. Committed transactions are kept, green; transactions that never committed are reversed, orange. Recovery is the procedure that reads the log and enforces both.

Recovery on One Log: Down, Then Up

The whole algorithm fits on one WAL. The example: start state A=10, B=20, C=30, D=40, E=50, update f(x) = x * 1.2, five transactions, then the server crashes. Recovery reads the log down to replay, then up to undo.

A WAL read top to bottom with the same columns as a log table, and a running database-state strip below. The replay pass runs down the left re-applying every row to rebuild the crash state A=12, B=20, C=43.2, D=48, E=60; the undo pass runs up the right reversing only the unfinished transactions' rows newest-first, E 60 to 50, C 43.2 to 36, C 36 to 30, leaving A=12, B=20, C=30, D=48, E=50. T1 and T4 committed and are kept; T2 aborted explicitly; T3 and T5 never committed. A CRASH row marks where the server stopped.

Figure 2. Recovery as two passes over one log:

  • REPLAY (down): re-apply every row exactly as it happened, redos and undos alike, to rebuild the state at the crash.
  • UNDO (up): then undo every transaction still unfinished at the crash, with no COMMIT or ABORT row, reversing its writes newest-first. T2 aborted before the crash, so the replay already rolled it back.

The undone rows are scattered, not a trailing block: T4 even commits late, after T3's writes, yet survives. What gets undone depends on commit status, not position in the log.

Why down before up. After a crash you cannot tell which data pages reached disk, so there is no consistent state to roll back from yet. The forward pass replays the whole log first and rebuilds the exact state at the crash, a known starting point. Only then does the backward pass peel off the transactions that never finished. Run the other way, undoing against half-written pages, and the result is undefined.

No separate analysis pass. You might expect a first pass just to work out who committed. You do not need one: as the forward pass reads the log, it marks each transaction finished when it meets that transaction's COMMIT or ABORT. By the crash it already knows which never finished, exactly the ones the backward pass undoes. The tracking is free. (Checkpoints are the one exception, see Optimizations below.)

After the Crash: Fix the Disk from the WAL

On reboot, RAM is gone with every in-progress change. The disk survived, but the pages that flushed before the crash are a half-written mix: some committed writes never reached disk, so committed work is missing; some uncommitted writes did reach disk, so wrong values are sitting there.

Just after the crash: RAM, red, is empty; the disk, green, is an inconsistent mix where a committed write is missing and an uncommitted write is wrongly present; the durable WAL, violet, survived untouched.

Figure 3. Just after the crash. RAM, red, is gone with every in-flight change. The disk, green, survived but is not consistent: a committed write is missing, and an uncommitted write is wrongly present. The WAL, violet, is untouched, and it is the only thing recovery can use, because RAM holds nothing.

Why can the WAL fix all of this? Because it survived the crash, and it holds every change as an old and a new value. The new values redo the committed writes that never flushed; the old values undo the uncommitted writes that did. RAM held the only other copy and it is gone, so the WAL is the sole source of truth. Not one byte of the repair comes from RAM.

Recovery Guarantees

Recovery restores the ACID guarantees across a crash: committed work survives (durability), unfinished work vanishes (atomicity), the rules hold (consistency), and rerunning it lands on the same state (repeatability). This safety has a cost.

Recovery restores two ACID guarantees: durability, the violet D icon, comes from committed work surviving the replay; atomicity, the blue A icon, comes from the undo pass; both rest on the write-ahead rule that the log reaches disk before the data.

Figure 4. Two ACID guarantees fall out of the two passes, in the order the passes run. Durability, the violet D, comes from the replay: once you see COMMIT, that work is replayed and never undone, so it survives any failure. Atomicity, the blue A, comes from the undo pass: a transaction is all or nothing, so unfinished work is reversed. Both rest on the write-ahead rule at the base, the log reaching disk before the data.

What Recovery Costs

  • Time: Can take minutes to hours for large databases.

  • I/O: Must read the WAL since the last checkpoint.

  • Availability: Database offline during recovery.

  • Complexity: Requires careful implementation.

Optimizations

Checkpointing. Periodically flush all dirty pages to disk. That limits how far back recovery must go: replay can start from the last checkpoint instead of the start of the log. The trade-off is checkpoint overhead against recovery speed.

Checkpoints are the one case where the live-transaction tracking needs its own quick scan. Instead of replaying from the start of the log, recovery scans from the last checkpoint to rebuild the table of live transactions and find where to start replaying. Without checkpoints, the forward pass starts at the beginning and the tracking is free, built as it reads.

Practice Questions

Test your understanding.

  1. Why does the forward pass run before the backward pass?

  2. What if the system crashes during recovery?

  3. How does recovery know which transactions were unfinished at crash time?