Write-Ahead Logging, Checkpoints, and ARIES
A database server loses power mid-transaction. Dirty pages are scattered across disk in no particular order. Some updates from committed transactions never made it out of the buffer pool. Some updates from aborted or in-flight transactions did. When the system reboots, it must reconstruct a state. This state must look exactly as if every committed transaction survived intact. It must also look as if every uncommitted transaction never happened. It must do this without knowing in advance which pages were flushed and which were not. This is the central problem of crash recovery. It matters because real systems crash constantly — power failures, kernel panics, container evictions, killed processes. Users expect that a committed transaction is committed forever. The solution used by essentially every serious relational database rests on three cooperating ideas. These databases include IBM DB2, PostgreSQL, SQL Server, and MySQL's InnoDB. The three ideas are the Write-Ahead Logging (WAL) rule, checkpointing, and the ARIES recovery algorithm (Algorithm for Recovery and Isolation Exploiting Semantics). WAL guarantees that a log record describing a change reaches stable storage first. It must arrive before the changed page itself does. So the log always has enough information to redo or undo any update. Checkpointing periodically records enough state to bound recovery. It limits how far back a recovery process must scan the log. This turns an unbounded recovery cost into one proportional to work since the last checkpoint. ARIES ties these together into a precise three-pass algorithm. The three passes are analysis, redo, and undo. This algorithm restores the database to a transaction-consistent state after any crash. It uses log sequence numbers (LSNs) stamped on both log records and data pages. These LSNs help avoid redoing work that already made it to disk. This article builds the mechanism from first principles. It covers the WAL invariant and why it is necessary. It covers the structure of checkpoints and the dirty page table. It also covers the full ARIES algorithm with pseudocode. This includes a worked crash trace and a careful complexity and correctness analysis. It assumes familiarity with Log-Based Crash Recovery and Isolation Levels. It explains not just what ARIES does. It also explains why each phase is required. It explains why skipping any of them breaks correctness.
- The WAL rule requires that a log record for an update reach stable storage before the corresponding data page is written back — this is what makes recovery possible at all.
- Checkpoints record active transactions and dirty pages so recovery does not need to scan the entire log history from the beginning of time.
- ARIES recovers in three passes: Analysis (find where to start), Redo (repeat history to reach the pre-crash state exactly), Undo (roll back losers).
- LSNs (log sequence numbers) stamped on log records and on data pages let redo skip updates already durable on disk — this is the key efficiency trick.
- Compensation Log Records (CLRs) make undo itself crash-safe: if the system crashes again during recovery, undo never repeats.
- Correctness rests on an invariant: repeating history during redo reconstructs the exact pre-crash state, after which undo removes only the effects of transactions that never committed.
Log first, redo everything since the last durable point exactly as it happened, then undo only the transactions that never committed — using LSNs to never redo work twice.
The idea
The Write-Ahead Logging rule states that before a modified page is written to stable storage, the log record describing that modification — and the log records of any prior updates to that page — must already be on stable storage. Equivalently: `flush(log up to LSN L)` must complete before a page whose most recent update carries LSN `L` is written to disk. This single rule is what lets a recovery algorithm always answer the question "what happened to this page before the crash?" — the answer is always in the log, because the log write always precedes the corresponding data write. Two further rules refine WAL into the exact protocol used by ARIES. First, log records must be flushed to disk at commit time, before the commit is acknowledged to the client — otherwise a "committed" transaction could vanish on crash. Second, a log sequence number (LSN) is attached to every log record (a monotonically increasing identifier, often a byte offset into the log) and every data page stores the LSN of the last log record that modified it, called the PageLSN. Comparing a log record's LSN against a page's PageLSN tells recovery, instantly, whether that specific update is already reflected on disk.
Checkpointing solves a different problem: without it, recovery after a long-running system would have to scan the log back to its very first byte, since in principle any transaction ever run might still have dirty, unflushed pages. A checkpoint periodically writes a compact summary — which transactions are active, and which pages are dirty in the buffer pool along with the earliest LSN that dirtied each one (the RecLSN) — so that recovery only needs to scan from that summary forward. ARIES uses a lightweight variant called a fuzzy checkpoint: it does not require flushing all dirty pages or halting the system, only writing the summary tables, which keeps checkpointing cheap enough to run frequently. Together, WAL plus checkpointing give ARIES everything it needs to run a bounded, three-phase recovery: Analysis, Redo, and Undo.
How it works
The data structures
ARIES recovery maintains two in-memory tables that are also the payload of every checkpoint.
- Transaction Table (TT): one entry per active transaction, storing its status (running, committing, aborting) and its LastLSN — the LSN of its most recently written log record.
- Dirty Page Table (DPT): one entry per dirty page currently in the buffer pool, storing the RecLSN — the LSN of the log record that first dirtied this page since it was last flushed. RecLSN is a lower bound: any earlier update is already safely on disk.
Every log record has a PrevLSN field linking it to the transaction's previous log record, forming a per-transaction backward chain used during undo. Update log records store enough information to redo (the "after" image or the operation) and to undo (the "before" image or the inverse operation).
Phase 0 — normal operation and checkpoints
During normal processing, every update produces a log record before the page is modified in the buffer pool, and the page's PageLSN is set to that record's LSN (satisfying WAL). Periodically a fuzzy checkpoint is taken: ``` begin_checkpoint record written end_checkpoint record written, containing: a snapshot of the Transaction Table a snapshot of the Dirty Page Table master record updated to point at this begin_checkpoint LSN ``` No page flushing is forced — this is what makes it "fuzzy" and cheap. On crash, recovery reads the master record to locate the most recent checkpoint and begins there.
Phase 1 — Analysis
Analysis reconstructs the Transaction Table and Dirty Page Table as of the moment of the crash, scanning forward from the checkpoint. ``` ANALYSIS(checkpoint_LSN): TT <- Transaction Table from end_checkpoint record DPT <- Dirty Page Table from end_checkpoint record for each log record R from checkpoint_LSN to end of log, in order: if R is an update record for transaction T on page P: if T not in TT: add T to TT with LastLSN = R.LSN, status = RUNNING else: TT[T].LastLSN = R.LSN if P not in DPT: DPT[P].RecLSN = R.LSN # first dirtying since flush else if R is a commit or abort-start record for T: update TT[T].status accordingly else if R is an end record for T: remove T from TT # transaction fully done RedoLSN <- min(RecLSN over all pages in DPT) # if DPT empty, RedoLSN = end of log return TT, DPT, RedoLSN ``` At the end of Analysis, TT tells us exactly which transactions were active (winners still running or losers to be undone) at crash time, DPT tells us which pages might have stale on-disk copies, and RedoLSN — the smallest RecLSN in the whole DPT — is the earliest point in the log from which any page could still need a redo.
Phase 2 — Redo
Redo replays every update from RedoLSN forward, for every transaction, committed or not — this is the "repeat history" principle. It uses PageLSN comparisons to skip updates already durable on disk. ``` REDO(RedoLSN, DPT): for each log record R from RedoLSN to end of log, in order: if R is an update record on page P: if P not in DPT: continue # page was flushed after crash-time state; skip if R.LSN < DPT[P].RecLSN: continue # this update predates page's dirtying window fetch P from disk (or buffer pool) if P.PageLSN >= R.LSN: continue # update already reflected on disk, skip else: reapply the update described by R to P P.PageLSN <- R.LSN ``` Both skip conditions are efficiency optimizations, not correctness requirements: the DPT check avoids fetching pages that provably need no redo, and the PageLSN check is the final, authoritative test applied once the page is actually in hand. After Redo, the database is in exactly the state it was in at the instant of the crash — including the effects of transactions that will shortly be undone.
Phase 3 — Undo
Undo rolls back every loser transaction — any transaction in TT that was not committed at crash time — in reverse chronological order, using the PrevLSN chains. ``` UNDO(TT): ToUndo <- { T.LastLSN : T in TT such that T.status != COMMITTED } (a max-heap ordered by LSN, across all loser transactions) while ToUndo is not empty: LSN <- extract max from ToUndo R <- read log record at LSN if R is a CLR (compensation log record): if R.UndoNextLSN is not NONE: push R.UndoNextLSN onto ToUndo else: write an "end" log record for R's transaction # fully undone else if R is an update record: undo the update (apply inverse action to the page) write a CLR: CLR.UndoNextLSN <- R.PrevLSN CLR.page <- R.page, CLR.data <- inverse of R's change if R.PrevLSN is not NONE: push R.PrevLSN onto ToUndo else: write an "end" log record for this transaction # reached its first record ``` Each undo step writes a Compensation Log Record (CLR) before modifying the page — CLRs are themselves logged so that undo actions are redone (never re-undone) if the system crashes again mid-recovery. A CLR's `UndoNextLSN` field points to the next record still needing undo, skipping over the one just processed; this is exactly what prevents infinite loops or repeated undo if recovery crashes again.
Complexity & correctness
Time complexity. Let `L` be the number of log records written since the RedoLSN (bounded by "since the last checkpoint" in a healthy system with regular checkpointing), and let `U` be the total number of update records belonging to loser transactions. Analysis is a single linear scan: O(L) time, with O(1) amortized work per record for hash-table updates to TT and DPT. Redo is a single linear scan from RedoLSN: O(L) time, plus one page fetch per record that is not skipped; in the worst case every record touches disk, giving O(L · pageIO), but the LSN skip tests typically make Redo touch far fewer pages than L. Undo is driven by a priority queue over loser transactions' log chains: O(U log k) where k is the number of concurrent loser transactions (heap operations), plus one page write and one CLR log write per undone update, so O(U · pageIO) in the worst case. Crucially, none of these phases requires scanning the log from its beginning — checkpointing bounds `L` by the log growth since the last checkpoint, which is why checkpoint frequency directly controls worst-case recovery time. Without checkpoints, `L` could be the entire history of the database, making recovery time unbounded and unacceptable for any production system.
Space complexity. TT and DPT each require O(k) space where k is the number of active/dirty entities at crash time — small compared to the log itself. The undo heap requires O(k) space as well, one entry per loser transaction chain frontier.
Correctness — the repeating-history invariant. The central correctness argument for ARIES is that Redo reconstructs, exactly, the database state at the instant of the crash, including the partial effects of transactions that had not yet committed. This works because: 1. By the WAL rule, every update reflected on disk has a corresponding log record with LSN ≤ that page's PageLSN, so no update can be "on disk but unlogged." 2. Analysis computes RedoLSN as the minimum RecLSN over all dirty pages — a lower bound on the earliest log record whose effect might be missing from disk. Any update before RedoLSN is provably already durable (its page was clean or flushed no earlier than that RecLSN), so it is safe to skip re-scanning further back. 3. Redo then reapplies every update from RedoLSN forward whose PageLSN indicates it is not yet reflected on disk (`PageLSN < R.LSN`), and skips every update already reflected (`PageLSN ≥ R.LSN`). Since log records for a single page are applied to it in strictly increasing LSN order (they are the record's own history), and each redo sets PageLSN to the record's LSN, by induction after processing all records up to some LSN, every page's PageLSN equals the LSN of the last update applied to it — exactly matching the pre-crash state. Once Redo completes, the database is at the pre-crash state — deliberately including uncommitted work. This is why Undo must be a separate, subsequent phase: it is only after history is fully repeated that we know precisely what every loser transaction did, and can invert exactly those actions using the PrevLSN chains recorded in the log, and only those actions.
Correctness of Undo and the CLR mechanism. Undo must itself be crash-safe: if the system crashes again during recovery, a second recovery must not re-undo already-undone actions (this would corrupt the database) and must resume undoing the remaining losers. CLRs are logged as ordinary durable log records with a well-defined `UndoNextLSN`, so a subsequent Redo pass will redo the undo actions (CLRs are never undone themselves — they carry no PrevLSN chain back through the original update), and Analysis will find losers' undo already in progress and resume from `UndoNextLSN` rather than restarting the chain. This is the reason ARIES tolerates crashes during recovery without a special case: recovery of a recovery is just recovery again, run on a longer log.
Tradeoffs. WAL forces at least one log write (and, at commit, a flush) per transaction — extra I/O compared to a naive scheme with no logging, but vastly cheaper than forcing every dirty page to disk at commit (the alternative, "force" policy). Fuzzy checkpointing keeps checkpoints cheap but means Analysis must scan forward past the checkpoint rather than trusting it completely — a small scan cost traded for near-zero checkpoint overhead. ARIES's page-level, physiological logging (log records reference physical pages but can describe logical operations) buys fine-grained concurrency and partial rollbacks (savepoints) at the cost of a genuinely intricate algorithm — simpler recovery schemes (e.g., pure undo/redo logging without fuzzy checkpoints or CLRs) sacrifice some of this flexibility for simplicity.
Worked example
Consider three transactions and a crash. The log (each entry: LSN, transaction, action) is:
| LSN | Transaction | Record |
|---|---|---|
| 00 | — | begin_checkpoint |
| 05 | — | end_checkpoint: TT={T1:running}, DPT={P1:RecLSN=? none yet} |
| 10 | T1 | update P1 (PrevLSN=none) |
| 20 | T2 | update P2 (PrevLSN=none) |
| 30 | T1 | update P2 (PrevLSN=10) |
| 40 | T2 | commit (PrevLSN=20) |
| 50 | T3 | update P1 (PrevLSN=none) |
| 60 | T1 | update P3 (PrevLSN=30) |
| — | CRASH — no more log records |
Assume before the crash, page P2 had been flushed to disk with PageLSN=30 (its update at LSN 40 is a commit record, not a page update, so P2's last data change was at LSN 30). Pages P1 and P3 are still dirty in the buffer pool, never flushed; P1's on-disk PageLSN is whatever it was before this excerpt (say 8, stale), P3 has no on-disk copy of the LSN-60 change (buffer-only).
Analysis starts at the checkpoint (LSN 5) and scans forward:
- LSN 10: T1 update P1 → TT={T1: running, LastLSN=10}; DPT={P1: RecLSN=10}
- LSN 20: T2 update P2 → TT={T1:10, T2: running, LastLSN=20}; DPT={P1:10, P2: RecLSN=20}
- LSN 30: T1 update P2 → TT[T1].LastLSN=30 (P2 already in DPT, RecLSN unchanged at 20)
- LSN 40: T2 commit → TT[T2].status=COMMITTED, LastLSN=40
- LSN 50: T3 update P1 → TT={T1, T2✓, T3: running, LastLSN=50}
- LSN 60: T1 update P3 → TT[T1].LastLSN=60; DPT adds P3: RecLSN=60
Final TT: `{T1: running/LastLSN=60, T2: committed, T3: running/LastLSN=50}`. Final DPT: `{P1: RecLSN=10, P2: RecLSN=20, P3: RecLSN=60}`. RedoLSN = min(10, 20, 60) = 10.
Redo scans from LSN 10 forward, re-applying (or skipping) every update:
- LSN 10 (P1): P1 in DPT, RecLSN=10 ≤ 10. Fetch P1, on-disk PageLSN=8 < 10 → reapply, set PageLSN=10.
- LSN 20 (P2): P2 in DPT, RecLSN=20 ≤ 20. Fetch P2, on-disk PageLSN=30 ≥ 20 → skip (already reflected — this update predates a later flush).
- LSN 30 (P2): fetch P2, PageLSN=30 ≥ 30 → skip (this is exactly the flushed version).
- LSN 50 (P1): fetch P1, PageLSN=10 < 50 → reapply, set PageLSN=50.
- LSN 60 (P3): P3 in DPT, RecLSN=60 ≤ 60. Fetch P3 (buffer-only, effectively PageLSN=−∞) → reapply, set PageLSN=60.
After Redo, disk state exactly matches the moment of the crash: P1 carries both T1's and T3's updates, P2 carries both T1's writes (already there via the earlier flush), P3 carries T1's update.
Undo rolls back losers T1 (LastLSN=60) and T3 (LastLSN=50) — T2 is committed and untouched:
- Heap = {60 (T1), 50 (T3)}. Pop 60: undo T1's P3 update, write CLR (UndoNextLSN=30), push 30.
- Heap = {50 (T3), 30 (T1)}. Pop 50: undo T3's P1 update, write CLR (UndoNextLSN=none) → write T3's end record. T3 fully undone.
- Heap = {30 (T1)}. Pop 30: undo T1's P2 update, write CLR (UndoNextLSN=10), push 10.
- Heap = {10 (T1)}. Pop 10: undo T1's P1 update, write CLR (UndoNextLSN=none) → write T1's end record. T1 fully undone.
Final state: T2's effects (P2 at LSN 20) persist; all of T1's and T3's page effects are reverted via CLRs, and the log itself now durably records that this rollback happened — safe even if the machine crashes again immediately after.
Common pitfalls & traps
| Pitfall | Why it breaks recovery |
|---|---|
| Flushing a data page before its log record is durable | Violates WAL directly — on crash, the page shows an update with no log record to justify or reverse it |
| Skipping Undo because "Redo already fixed the disk" | Redo intentionally reinstates uncommitted work too — without Undo, loser transactions' effects remain permanently |
| Forgetting to log CLRs themselves | A second crash mid-undo would have no record of what was already rolled back, risking double-undo or lost progress |
| Computing RedoLSN as the checkpoint LSN instead of min(RecLSN) | Over-conservative RedoLSN wastes work; too-recent RedoLSN silently skips genuinely un-flushed updates, corrupting redo |
| Treating fuzzy checkpoints as consistent snapshots | They are not — TT/DPT captured mid-flux, which is exactly why Analysis must still scan forward from them |
| Using PrevLSN chains instead of UndoNextLSN when resuming Undo after a CLR | Re-walking PrevLSN from a CLR re-triggers already-undone updates, an infinite or duplicated rollback |
Pioneers & history
The ARIES algorithm was developed at IBM's research labs to solve recovery for relational database engines that needed fine-grained locking, partial rollbacks, and high transaction throughput simultaneously — requirements that older, simpler undo/redo logging schemes could not satisfy without sacrificing concurrency.
Origins · 1 minC. Mohan and how this was discovered
C. Mohan led the team that designed ARIES in the late 1980s, publishing the definitive algorithm and its correctness arguments in 1992. His work on write-ahead logging, fine-granularity locking, and recovery became foundational to nearly every commercial relational database engine, earning him recognition as an IBM Fellow and ACM Fellow.
Where this matters
Every production relational database uses some variant of write-ahead logging and ARIES-style recovery. PostgreSQL's WAL subsystem directly implements the WAL rule with checkpoint records and REDO-pointer-bounded recovery. MySQL's InnoDB storage engine maintains a redo log (physiological, LSN-stamped, exactly as ARIES prescribes) and a separate undo log for rollback and for supplying old versions to Isolation Levels like snapshot isolation. IBM Db2 and Microsoft SQL Server implement ARIES essentially as originally specified, including CLRs and fuzzy checkpoints. Beyond relational engines, distributed systems and modern storage engines borrow the same ideas: log-structured merge-tree databases (Cassandra, RocksDB) use write-ahead logs for durability before flushing memtables, and distributed consensus-replicated databases layer WAL-style durability underneath replication. Anywhere a system must survive a crash without losing committed work or resurrecting uncommitted work, some descendant of WAL, checkpointing, and ARIES's analysis-redo-undo structure is doing the job.
Ask the tutor: How would ARIES need to change if the system used a "steal, no-force" buffer policy versus a "no-steal, force" policy?
Why not just force all dirty pages to disk at every commit instead of using WAL?
Forcing every dirty page to disk at commit (the "force" policy) guarantees durability without needing redo, but it is prohibitively expensive: a single transaction that touched many pages would trigger many random disk writes before it could return control to the client. WAL instead requires flushing only the (typically small, sequentially written) log records for that transaction, which is dramatically cheaper I/O. The cost is that data pages may lag behind on disk, which is exactly why a Redo phase is needed after a crash — WAL trades a small, bounded recovery-time cost for a large, ongoing reduction in commit-time I/O, which is the right tradeoff for almost every real workload.
What exactly is "repeating history" and why is it central to ARIES's correctness?
Repeating history means Redo reapplies every logged update since RedoLSN, for every transaction, regardless of whether that transaction ultimately committed or aborted — reconstructing the database exactly as it stood the instant before the crash. This matters because only after that exact state is restored can Undo correctly identify precisely what each loser transaction did and invert exactly those actions. If Redo instead tried to "smartly" skip loser transactions, it would need information (final commit/abort status resolved consistently with all page states) that isn't reliably available mid-log, and any mistake there would be invisible until it caused later corruption. Repeating history removes that guesswork entirely.
What is a fuzzy checkpoint, and why is it "fuzzy" rather than a full snapshot?
A fuzzy checkpoint writes only the Transaction Table and Dirty Page Table as they exist at that moment, without forcing any dirty pages to disk or pausing transaction processing. It is "fuzzy" because by the time recovery reads it, the true system state has already moved on — more transactions may have started, more pages dirtied. This is why Analysis must still scan forward from the checkpoint rather than trusting it as ground truth; the checkpoint is only a cheap starting point, not a consistent snapshot. The tradeoff is deliberate: a full consistent checkpoint (forcing all dirty pages) would be far more expensive and would stall the system, while a fuzzy checkpoint costs almost nothing to take frequently.
How does ARIES interact with concurrency control and isolation levels?
ARIES handles durability and atomicity recovery; concurrency control (locking, MVCC) enforces isolation, and the two must cooperate but are logically separate concerns discussed under Isolation Levels. ARIES's physiological logging (log records reference specific pages but can describe logical, higher-level operations) allows fine-grained record-level locking rather than page-level locking, because undo can be expressed as a logical inverse operation rather than a raw byte overwrite. This matters for concurrency: two transactions can safely modify different records on the same page concurrently, and ARIES's per-transaction undo still correctly reverses only its own logical changes without disturbing the other transaction's committed work on that page.
What happens if the system crashes again while ARIES recovery itself is running?
Nothing special — this is one of ARIES's key design strengths. Because Analysis, Redo, and Undo all operate purely by reading and appending to the durable log (including writing CLRs during Undo), a crash mid-recovery simply produces a longer log to recover from next time. The next Analysis pass will see the CLRs already written and correctly determine which loser transactions are partially undone, resuming via `UndoNextLSN` rather than restarting their rollback from scratch. No separate "recovery of recovery" logic is needed; the algorithm is naturally idempotent to repeated interruption.
Why does Redo check both the Dirty Page Table and the page's actual PageLSN, instead of relying on just one?
The DPT check is a cheap, in-memory filter: if a page is not in the DPT at all, or if the update's LSN is below the page's RecLSN, Analysis has already proven the update is safely on disk, so Redo can skip it without touching the disk at all. The PageLSN check is the authoritative, final test, performed only once the page is actually fetched, since RecLSN is only a lower-bound approximation reconstructed during Analysis and could in rare cases be conservative. Using both minimizes disk I/O (via the cheap DPT filter) while guaranteeing correctness (via the exact PageLSN comparison).
Does write-ahead logging alone guarantee correct recovery, or is checkpointing also required for correctness?
WAL alone is sufficient for correctness — a system without checkpoints could, in principle, scan the entire log from its very first record and still correctly recover, since WAL guarantees the log contains everything needed. Checkpointing is required for practicality: it bounds how far back that scan must go, turning an unbounded, ever-growing recovery cost into one proportional only to activity since the last checkpoint. In production systems, this distinction matters enormously — a database that ran for months without a checkpoint would take an unacceptable amount of time to recover from any crash.