Undo logging

Why does undo exist at all, and why must its record be durable before the page it protects?

Undo is the price of steal. It has three customers, which is why it is more important than it looks.

1. Crash recovery. Changes of uncommitted transactions may already have reached disk (because of steal). They must be reversed.
2. Voluntary rollback. When the application says ROLLBACK, the same machinery runs, but on the normal request path.
3. MVCC read views. MVCC (multi-version concurrency control) lets readers see an older consistent snapshot of the data while writers continue. In InnoDB, the undo log is the version store: a reader rebuilds an old version of a row by walking undo records backwards from the current row.

The write-ahead rule has a mirror image for undo: the undo record of a change must be durable before the page carrying that change may be written to disk. In short: redo before commit, undo before page write. Undo records live in pages that are themselves protected by redo logging, so a log protects a log. The recursion ends because the outermost log is append-only and idempotent by LSN (idempotent means safe to apply more than once with the same result).

The hard case: structural changes

Undo also creates the one really hard case in recovery: structural changes cannot be reversed physically. Imagine a transaction inserts a row, which splits a B-tree page (a B-tree is the common tree-shaped database index). Other transactions then insert into the new, split structure. You cannot "un-split" the page by restoring old bytes, because other transactions already navigated the new structure.

The answer is logical undo over a nested top action: the structural change (the split) is committed permanently and independently, and the higher-level operation (the insert) is undone by running its inverse (a delete) against whatever structure now exists. This is why index maintenance is the hardest part of every storage engine to make crash-safe.

The time machine, and its hidden cost

Customer 3 has a cost that shows up far from undo: a long-running reader pins the oldest version that the cleaner is allowed to remove, so the version store grows with your slowest reader, not your write rate. How Postgres and InnoDB each pay for it is in Multiversion concurrency control (MVCC). For durability it is the first instance of a pattern this mechanism meets again and again: every storage that cannot update in place grows an indirection layer and a cleaner, and the cleaner's progress is held back by the oldest reader (Log truncation and retention policies).