Log-Based Crash Recovery

A recovery log (or transaction log) is a sequential, append-only file of log records, each describing one state-changing event: a transaction starting, a transaction updating a data item, a transaction committing, or a transaction aborting. The log lives on stable storage — storage assumed to survive crashes and, ideally, media failure (mirrored disks, replicated storage). The database's actual data pages live in a buffer pool in volatile memory and are written back ("flushed") to disk pages at times the buffer manager chooses, not necessarily when a transaction commits. An update log record for transaction $T_i$ writing data item $X$ has the form

recording the transaction id, the item modified, its value before the write ($V_{old}$, needed for undo), and its value after the write ($V_{new}$, needed for redo). Special records mark control events:

• $\langle T_i\ \mathtt{start}\rangle$ — $T_i$ has begun.
• $\langle T_i\ \mathtt{commit}\rangle$ — $T_i$'s updates are permanent; this is the point of no return.
• $\langle T_i\ \mathtt{abort}\rangle$ — $T_i$ has been rolled back.

The central invariant governing all of this is the Write-Ahead Logging (WAL) rule, previewed here and detailed in Write-Ahead Logging: > Before a data page containing an update by $T_i$ is written to disk, the log record for that update must already be on stable storage. Before a transaction commits, all its log records (including the commit record) must be on stable storage. Given WAL, the log always contains a strictly complete or ahead picture of what has happened to the database, relative to what is actually on disk. That asymmetry — log always at least as current as data — is exactly what recovery exploits: any update visible on disk is guaranteed to also be recorded in the log, so the log alone suffices to reconstruct or repair the database state after a crash.

Recovery must handle two categories of transactions active at crash time, discovered by scanning the log: 1. Committed transactions whose $\mathtt{commit}$ record is in the log — their effects must survive (be redone if not already reflected on disk). 2. Uncommitted / unfinished transactions with a $\mathtt{start}$ but no $\mathtt{commit}$ or $\mathtt{abort}$ — their effects must be erased (undone), because atomicity forbids partial results. Two classical policies govern how buffer pages relate to logging, and each yields a different recovery algorithm.

Deferred database modification (redo-only recovery). A transaction's updates are only written into its log records while it runs; the actual database pages are not modified until after the transaction commits. During normal execution, uncommitted changes exist only in the log and in private buffers, never on the shared disk copy. Consequently, at crash time no uncommitted transaction could possibly have modified the on-disk database — so no undo is ever needed. Recovery only has to redo committed transactions, in the order their updates were logged, to make sure their effects are actually reflected on disk. This scheme is simple and elegant but has practical costs: buffering all writes of a possibly long transaction requires extra memory, and it precludes early flushing that concurrency and buffer-pressure sometimes need.

Immediate database modification (undo/redo recovery). Data pages may be updated on disk while the transaction is still running, as soon as WAL has logged the corresponding old/new values. This is what real buffer managers do — they cannot wait for commit before evicting a dirty page. Now an uncommitted transaction's changes might already be on disk when the crash hits, so recovery needs both operations:

• UNDO: for every unfinished transaction, restore each item it touched to $V_{old}$, scanning the log backward (most recent update first) so that multiple updates to the same item are undone in the correct reverse order.
• REDO: for every committed transaction, reapply $V_{new}$ to each item it touched, scanning the log forward, so that if a page was lost or an update never made it to disk, it is correctly reinstated.

Both scans are needed because a page on disk might reflect a mixture — some committed, some uncommitted work interleaved by the buffer manager — and only the log's global order tells you the truth about each individual write.

The recovery algorithm

The standard two-pass procedure (analysis conceptually folded into the passes here; the ARIES scheme formalizes an explicit analysis pass, foreshadowed but not detailed) works as follows: ``` procedure RECOVER(): undo_list := {} # transactions needing rollback redo_list := {} # transactions to reapply

# ---- Pass 1: scan the log forward, classify transactions ---- for each record r in log, in the order written: if r = : add Ti to undo_list else if r = or r = : remove Ti from undo_list if r = : add Ti to redo_list

# after this pass:

# undo_list = transactions with start but no commit/abort -> losers

# redo_list = transactions with a commit record -> winners

# ---- Pass 2: undo losers, scanning backward ---- for each record r in log, in REVERSE order: if r = and Ti in undo_list: write V_old to data item X on disk append to log # compensation record (optional variant) for each Ti in undo_list: append to log

# ---- Pass 3: redo winners, scanning forward ---- for each record r in log, in the order written: if r = and Ti in redo_list: write V_new to data item X on disk flush all modified pages to stable storage ``` For deferred modification, the algorithm collapses: `undo_list` is provably always empty (no uncommitted transaction ever wrote to disk), so Pass 2 is skipped entirely and only Pass 3 (REDO of committed transactions) executes. A subtlety in Pass 2 deserves attention: undoing must proceed backward through the log. If $T_i$ wrote $X$ twice — first $10\!\to\!20$, then $20\!\to\!35$ — undoing forward would restore $X$ to $10$ then immediately overwrite it back to $20$ from the first record misapplied out of order; undoing backward correctly restores $35\!\to\!20$ then $20\!\to\!10$, landing on the true pre-transaction value. Real systems (as in ARIES) also write compensation log records (CLRs) during undo, so that if the system crashes again during recovery, the partial undo already performed is never repeated — a detail this article foreshadows for the fuller treatment of ARIES Recovery.

Time complexity. Let $L$ be the number of log records written since the last checkpoint (or since the log began, absent checkpointing). Each pass over the log performs $O(1)$ work per record — a comparison of transaction id against membership in a hash set, plus one disk write per data-item update touched during undo/redo. So a full recovery costs

I/O and CPU work, dominated in practice by the random disk writes needed to reinstate or roll back individual pages, not by the sequential log scan itself (which is cheap, since the log is read sequentially — good locality). Because $L$ can in principle grow without bound between checkpoints, unbounded log growth means unbounded worst-case recovery time; this is precisely the problem checkpoints solve (foreshadowed, detailed under Checkpoints): a checkpoint record fixes a known-consistent point, and recovery can restrict its backward scan to transactions active at or after that point, plus a forward redo starting there — bounding $L$ to "log since last checkpoint" rather than "log since time zero."

Space complexity. The log itself is $O(L)$ records, each $O(1)$ size for a fixed-size item (larger for variable-length values, but still bounded by the size of the update). Recovery needs $O(A)$ auxiliary memory, where $A$ is the number of transactions active at crash time, to hold the undo/redo transaction-id sets — negligible compared to database size.

Correctness argument. The key claim to justify is: after RECOVER() terminates, the database is exactly as if every committed transaction ran to completion and every uncommitted transaction never ran at all (the Durability and Atomicity guarantees of ACID Properties). The argument rests on three facts: 1. WAL guarantees the log is never behind reality. Because a data page write is preceded by its log record hitting stable storage, at crash time, for any update reflected on disk, the corresponding log record is guaranteed present. The converse can fail (a log record may exist for an update not yet on disk) — but that asymmetry is exactly what redo is for. 2. Classification is exhaustive and exclusive. Pass 1 partitions every transaction that ever wrote a `start` record into exactly one of: committed (has a `commit` record — put in redo_list) or unfinished (no `commit`/`abort` — put in undo_list). No transaction is double-counted because commit/abort removes it from undo_list, and no transaction is missed because every update log record belongs to some transaction with a `start` record earlier in the log (transactions cannot write without starting). 3. Idempotence of undo/redo makes reapplication safe regardless of what was already on disk. Applying $V_{new}$ to $X$ (redo) or $V_{old}$ to $X$ (undo) results in the same final value of $X$ whether or not that write had already happened before the crash. Formally, redo and undo actions are idempotent: applying them once or many times yields the same state. This matters because recovery cannot know, for a given item, exactly how far the previous flush got — it simply reapplies every relevant log record and trusts idempotence to make the outcome correct regardless. This is also why recovery is safe to re-run if it is itself interrupted by a second crash: repeating Pass 2/3 changes nothing once the correct final values are already in place. Given (1)–(3): every committed transaction's final writes are guaranteed to end up on disk (by redo, forward order preserves multiple-write ordering correctly since later log records for the same item overwrite earlier reapplications with the true final value), and every unfinished transaction's writes are guaranteed erased (by undo, backward order correctly unwinds multiple writes to the same item). No partial transaction outcome can survive. $\blacksquare$

Honest tradeoffs. Deferred-update recovery is simpler (no undo logic at all) but forces transactions to buffer all their writes until commit, which is memory-expensive and blocks early write-back under memory pressure — a poor fit for long-running or bulk-update transactions. Immediate-update recovery scales better in normal operation but requires a correct, carefully ordered undo pass and, in production systems, additional machinery (compensation log records, dirty-page tables) to make recovery itself crash-safe — machinery that ARIES Recovery formalizes. Both schemes' recovery time grows with unbounded log length absent checkpointing, which is why virtually no production system omits checkpoints.

Consider three transactions on an account database with items $A$, $B$, $C$ (initial values $A{=}500,\ B{=}200,\ C{=}300$), using immediate modification. The log accumulated before a crash:

Note: `` never appears — $T_2$ was interrupted mid-transaction. $T_3$ never committed either. Because this is immediate modification, the buffer manager may have already flushed some of these writes to disk (say pages holding $A$ and $C$ were flushed, $B$'s page was not) — recovery must work correctly regardless of which subset actually reached disk, which is the point of idempotent redo/undo.

Pass 1 — classify.

• $T_1$: has `start` (record 1) and `commit` (record 4) → redo_list.
• $T_2$: has `start` (record 5), no commit/abort → undo_list.
• $T_3$: has `start` (record 7), no commit/abort → undo_list.

Pass 2 — undo, scanning backward from record 9 to record 1, acting only on records belonging to $\{T_2, T_3\}$:

After Pass 2: append `` and `` to the log. At this point $A{=}400, B{=}300, C{=}300$ — exactly $T_1$'s post-commit state, with $T_2$ and $T_3$ fully erased.

Pass 3 — redo, scanning forward, acting only on records belonging to $\{T_1\}$:

Final state: $A = 400,\ B = 300,\ C = 300$. Check: this is exactly the state after $T_1$ alone runs to completion from the initial values ($500{-}100=400$, $200{+}100=300$), with $T_2$'s and $T_3$'s partial work fully absent, $C$ correctly restored to its pre-$T_2$ value of $300$. Every dollar is accounted for — atomicity held even though pages were flushed in an arbitrary, interleaved order before the crash.

The theory and engineering of log-based recovery grew out of the transaction-processing research of the 1970s–80s, much of it at IBM, as relational databases moved from research prototypes (System R) to industrial systems requiring real fault tolerance.

Log-based recovery is not a textbook abstraction — it is the load-bearing mechanism inside nearly every production database and storage engine. PostgreSQL's WAL subsystem, MySQL/InnoDB's redo log and undo log tablespaces, Oracle's redo log and rollback segments, SQL Server's transaction log, and SQLite's WAL mode all implement variants of the redo/undo scheme described here, layered with checkpointing and, in most, an ARIES-style analysis/redo/undo restart procedure. Distributed systems built on top — Kafka's log-structured storage, etcd and Raft-based consensus logs, cloud data warehouses' commit logs — borrow the same append-first-then-apply discipline for the same reason: sequential writes are fast and durable, and a log of intent is easier to reason about than mutable shared state. Anywhere a system must survive a crash without losing or duplicating work — banking, e-commerce order processing, distributed file systems, message queues — some descendant of this algorithm is running underneath.

Ask the tutor: How do compensation log records make undo itself crash-safe during a second failure?