Crash Recovery

The process starts with an empty buffer pool. On disk: the log, intact up to the last fsync (a CRC on each record identifies the point where a crash truncated a partially written one), and the data files, in which each page carries the LSN of the last change written into it. Nothing else — no memory of which transactions were running, which pages were dirty, or which frames held what. The data files may be arbitrarily behind the log, and unevenly: page 7 was flushed by the background writer just before the crash and is current, page 3 was last written at the previous checkpoint and lacks two committed changes, page 12 was flushed mid-transaction and contains a change that never committed.

Recovery's job is to produce, from those two inputs, exactly the state of every committed transaction and nothing of any uncommitted one — and to do it in bounded time, and to survive crashing again halfway through.

The control file (PostgreSQL pg_control, InnoDB's log header) records the LSN of the last completed checkpoint. Everything dirtied before that checkpoint was written to disk as part of it, so no record before it can be missing from any page; recovery reads the log from there. In the example that means LSN 4: T1's records at LSNs 1–3 are never read, and page 3 is trusted as current because the checkpoint guarantees it.

With fuzzy checkpoints the start point can be earlier than the checkpoint record: the record lists the pages that were still dirty when it was taken and the LSN at which each was first dirtied, and redo begins at the smallest of those. Either way the log before the start point is dead weight and has been, or can now be, recycled. The checkpoint interval is therefore the knob that bounds recovery time: checkpoint_timeout five minutes means at most five minutes of log to replay — plus whatever was written during a slow checkpoint.

The analysis pass reads forward from the start point and builds the transaction table: every transaction id it sees, with status committed (a COMMIT record was found), aborted (an ABORT record), or active (neither — the transaction was in flight at the crash and is a loser). It also builds the dirty page table: every page mentioned by a record after the checkpoint, with the first LSN that touched it. Transactions listed as active in the checkpoint record are seeded into the table so that a transaction which started before the checkpoint and never committed is still recognised as a loser.

In the example: T2 has a COMMIT at LSN 7 — winner. T3 has BEGIN and UPDATE but no COMMIT — loser. T1 is not in the scanned range at all, which is correct: everything about it is already on disk. The committed set is what redo must guarantee; the loser set is what undo must remove.

Redo walks the range forward and, for every record that changes a page, fetches the page and compares LSNs. Page 7 carries LSN 0 and the record is LSN 6: apply the after-image (balance 400), stamp the page with LSN 6. Page 12 carries LSN 9 and the record is LSN 9: the page already contains the change — skip. That comparison is what makes redo idempotent: run recovery twice, or crash during it and run it again, and every record is applied exactly once per page, because a page that has it says so. Without the page LSN, "balance − 100" replayed twice would take 200 and nobody would know.

Notice that redo applies T3's change if the page lacks it, even though T3 will be undone. This is ARIES's "repeat history": after redo the pages are exactly what they were in memory at the crash, and undo then works from a known state using the same code path it uses for a normal ROLLBACK. Redo is also the code path of a streaming replica — it receives the same records and applies them with the same LSN comparison — which is why Replication Internals: WAL Shipping, LSNs, Lag and Failover is this lesson with a network in the middle.

Undo walks each loser's records backward — newest first, following each record's back-pointer to the previous record of the same transaction — and reverses them: restore the before-image (page 12: 870 → 900). Each reversal is itself logged as a compensation log record (CLR) carrying the undo as a redo-able change plus a pointer to the next record still to undo. If the machine crashes during undo, the next recovery's redo pass replays the CLRs (they are ordinary records to it), and its undo pass resumes from the pointer, never undoing the same record twice and never undoing a CLR. When a loser's records are exhausted, an ABORT record closes it. This is the whole of ARIES in one paragraph: analysis to learn the state, redo to repeat history, undo to remove losers, with every action expressed as a log record so recovery is itself recoverable.

Whether undo is needed at all depends on how the engine updates rows. An engine that overwrites in place (InnoDB) must physically restore before-images, and keeps them in the undo log for the purpose. An engine that writes new versions and leaves the old ones (PostgreSQL) has nothing to restore: a loser's new tuple versions carry a transaction id that will never be marked committed, so they are invisible to everyone, and VACUUM removes them later. Both are correct; one pays at recovery, the other pays in dead tuples — see MVCC Internals: Version Chains and Snapshots and UPDATE, DELETE and Dead Tuples.

The dirty pages produced by redo and undo are flushed (or left for the checkpointer — they are protected by the log either way), an end-of-recovery checkpoint is written so the next restart starts here, and the engine accepts connections. In the example the final state is page 3 = 220, page 7 = 400, page 12 = 900: exactly the committed transactions T1 and T2, nothing of T3 — and the client that waited for T3's COMMIT never received it, so nothing was promised and nothing is lost.

The cost of recovery is the cost of reading the log since the checkpoint and touching every page it mentions — usually seconds to a few minutes. The engineering decision that controls it is the checkpoint interval; the engineering mistakes that inflate it are a huge max_wal_size with no time-based checkpoint, a crash during a long-running bulk load (minutes of undo in InnoDB, a large dead-tuple cleanup in PostgreSQL), and storage whose fsync lied, which produces a log that says a page is current when it is not — the one failure recovery cannot repair.