vault

The ARIES Recovery Algorithm

16 min read

The ARIES Recovery Algorithm

ARIES — Algorithms for Recovery and Isolation Exploiting Semantics — is the crash-recovery algorithm designed by C. Mohan and colleagues at IBM Almaden for DB2, and published in the canonical 1992 paper (Mohan et al. 1992). It is the algorithm that nearly every serious transactional database — IBM DB2, Microsoft SQL Server, Oracle, MySQL InnoDB, and (in a simplified redo-only form) PostgreSQL — uses to restore itself to a correct state after a crash, working entirely from the Write-Ahead Log. Its central and initially counter-intuitive idea is repeat history, then undo: after a crash, ARIES first reapplies every logged change — including the changes of transactions that were doomed to roll back — to reconstruct the exact page-by-page state the buffer pool held at the instant of the crash, and only then rolls back the transactions that had not committed. This note explains why that ordering is necessary, how ARIES rebuilds its bookkeeping from the log in three passes (Analysis, Redo, Undo), and the two devices — the page Log Sequence Number and the Compensation Log Record — that make each pass idempotent so that a crash during recovery is itself fully recoverable.

This note focuses on the recovery algorithm. For the underlying discipline of logging before modifying, the two WAL rules, and the log’s role as a replication and CDC stream, see Write-Ahead Log. For how the monotonic LSN and the write-ahead invariant guarantee durability at the byte level, see Log Sequence Numbers and the Durability Guarantee. For how checkpoints bound how far back Analysis must scan, see Checkpoints and Fuzzy Checkpointing.

Mental Model — Why Both Redo and Undo Are Needed

The shape of any recovery algorithm is dictated by one design decision in the buffer manager: its buffer-management policy, described by two independent axes (CMU 15-445 L20). The steal axis asks whether the buffer pool may write a dirty page belonging to an uncommitted transaction out to disk (to reclaim a buffer frame for something else): STEAL means yes, NO-STEAL means no. The force axis asks whether all of a transaction’s dirty pages must be forced to disk before the transaction is allowed to commit: FORCE means yes, NO-FORCE means no.

These two choices determine what recovery must be able to do:

  • NO-STEAL + FORCE is the easiest to recover: an uncommitted transaction never has any page on disk (so there is nothing to undo), and a committed transaction has all its pages on disk (so there is nothing to redo). But it is ruinous for performance — commit must synchronously flush every scattered data page, and a transaction’s entire write set must fit in memory (CMU 15-445 L20).
  • STEAL + NO-FORCE is what every high-performance engine actually uses. The buffer pool is free to evict dirty pages of live transactions whenever it needs frames (steal), and commit does not wait for data pages to be flushed (no-force). This is fast — commit only forces the small sequential log, and hot pages stay in RAM and are coalesced. But it creates exactly the two problems that ARIES must solve.
flowchart TB
  subgraph POL["Buffer policy → recovery obligation"]
    direction LR
    STEAL["STEAL:<br/>a dirty page of an<br/>UNCOMMITTED txn<br/>may hit disk"] -->|"if that txn aborts,<br/>the change is on disk"| UNDO["⟹ need UNDO"]
    NOFORCE["NO-FORCE:<br/>a COMMITTED txn's<br/>data pages may NOT<br/>be on disk yet"] -->|"crash loses the page<br/>but log has the change"| REDO["⟹ need REDO"]
  end
  UNDO --> ARIES["ARIES = STEAL + NO-FORCE<br/>(redo AND undo)"]
  REDO --> ARIES

Diagram: the buffer-management policy decides the recovery obligation. What it shows: STEAL means an uncommitted transaction’s changes can reach disk, so recovery must be able to undo them; NO-FORCE means a committed transaction’s changes may not have reached disk, so recovery must be able to redo them. The insight: ARIES is the recovery algorithm for the STEAL + NO-FORCE regime, which is why — unlike shadow paging or NO-STEAL + FORCE — it needs both a redo pass and an undo pass (Mohan et al. 1992; CMU 15-445 L20).

The Bookkeeping ARIES Tracks

ARIES threads several identifiers through the log and the pages. Understanding them is prerequisite to understanding the passes (CMU 15-445 L21):

  • Log Sequence Number (LSN) — a globally unique, monotonically increasing identifier on every log record. In PostgreSQL it is literally “a byte offset into the WAL, increasing monotonically with each new record” (PostgreSQL WAL Internals). See Log Sequence Numbers and the Durability Guarantee.
  • pageLSN — stored on each data page: the LSN of the most recent log record that modified that page. This is the linchpin of idempotent redo.
  • prevLSN — stored on each log record: the LSN of the previous log record written by the same transaction. The prevLSN pointers form a backward-linked list per transaction, so undo can walk a single transaction’s records efficiently.
  • flushedLSN — an in-memory value: the highest LSN that has actually been flushed to the log on disk (see Log Sequence Numbers and the Durability Guarantee).
  • recLSN (“recovery LSN”) — held in the Dirty Page Table: for a dirty page, the LSN of the log record that first dirtied it since it was last written to disk. It marks the earliest change that might be missing from the on-disk copy of that page.
  • lastLSN — held in the Active Transaction Table: the most recent LSN written by a given transaction.
  • MasterRecord — a small, fixed location on disk holding the LSN of the most recent completed checkpoint; recovery starts by reading it.

Two in-memory tables are maintained during normal running and rebuilt during recovery:

  • The Active Transaction Table (ATT) holds one entry per transaction that has not yet finished (no TXN-END record): its transactionId, its status (Running, Committing, or Undo-Candidate), and its lastLSN. “The ATT contains every transaction without the TXN-END log record. This includes both transactions that are either committed or abort” (CMU 15-445 L21).
  • The Dirty Page Table (DPT) holds one entry per page that is dirty in the buffer pool, each carrying that page’s recLSN. It “lists all modified pages not yet written to disk,” regardless of whether the change came from a running, committed, or aborted transaction (CMU 15-445 L21).

Mechanical Walk-through — The Three Passes

After a crash, ARIES reads the MasterRecord to find the last checkpoint, then runs three passes over the log (CMU 15-445 L21; Mohan et al. 1992).

flowchart LR
  CKPT["last checkpoint<br/>(from MasterRecord)"] -->|"① ANALYSIS<br/>scan forward"| END1["end of log<br/>rebuild ATT + DPT"]
  MINREC["② REDO start =<br/>min recLSN in DPT"] -->|"scan forward,<br/>repeat history"| END2["end of log<br/>exact pre-crash state"]
  END3["③ UNDO<br/>scan backward"] -->|"roll back losers,<br/>write CLRs"| OLDEST["oldest change of any<br/>loser transaction"]

Diagram: the three passes over the log and where each begins and ends. What it shows: Analysis runs forward from the last checkpoint to the crash point, rebuilding the two tables; Redo runs forward from the minimum recLSN found in the rebuilt DPT (which may be earlier than the checkpoint); Undo runs backward from the crash point to the oldest surviving change of any transaction that had not committed. The insight: the three passes sweep the log twice forward and once backward, and each starts at a precisely computed LSN rather than blindly at the log’s start — the min-recLSN start point is exactly what checkpoints exist to advance (CMU 15-445 L21).

Pass 1 — Analysis: rebuild the tables and find the redo start point

Analysis starts at the last checkpoint (via the MasterRecord LSN) and scans the log forward to the end. Its job is purely bookkeeping — it modifies no pages (CMU 15-445 L21):

  1. Begin from the ATT and DPT snapshots captured by the checkpoint (see Checkpoints and Fuzzy Checkpointing).
  2. On a TXN-END record, remove that transaction from the ATT — it is fully finished.
  3. On any other record for a transaction, add it to the ATT (if absent) with status UNDO; on a COMMIT record, change its status to COMMIT. Transactions left in the ATT with status UNDO at end of log are the losers — in flight at the crash, never committed.
  4. On an UPDATE (or INSERT/DELETE) record for page P, if P is not already in the DPT, add it and set its recLSN to this record’s LSN — the first change to P that may not have reached disk.

When Analysis finishes, the ATT names exactly the transactions that must be undone, and the DPT names the pages that might be stale on disk. The redo start point is the minimum recLSN across all entries in the DPT — the earliest change to any dirty page that could be missing from disk. Nothing before that LSN needs redoing, because every earlier change is provably already on disk.

Pass 2 — Redo: repeat history

Redo scans forward from that minimum recLSN. Its goal, in ARIES’s own framing, is to repeat history — to reconstruct the buffer-pool state that existed at the moment of the crash, including the effects of transactions that will later be rolled back (Mohan et al. 1992; “Repeating History During Redo: On restart, retrace actions and restore database to exact state before crash,” CMU 15-445 L21).

For each redoable log record (an UPDATE or a Compensation Log Record) with LSN L affecting page P, ARIES re-applies the change unless it can prove it is already present. It skips the redo when any of the following holds (CMU 15-445 L21):

  • P is not in the DPT (the page is clean on disk — every change is already there); or
  • P is in the DPT but L < the page’s recLSN (this particular change predates the earliest missing change, so it is on disk); or
  • the pageLSN recorded on the on-disk page itself is ≥ L (the page already reflects this change or a later one). Checking this requires fetching the page from disk.

When ARIES does re-apply a change, it sets the affected page’s pageLSN to L. Crucially, redo performs no additional logging and forces no flushes — it simply replays. This pageLSN vs. LSN comparison is what makes redo idempotent: re-running Redo from scratch after an interrupted recovery cannot double-apply anything, because a re-applied change bumps the pageLSN, and the second attempt sees pageLSN ≥ L and skips. At the end of Redo, ARIES writes TXN-END records for transactions whose status is COMMIT and removes them from the ATT — they are now fully durable and done.

Why redo the changes of doomed transactions? Because undo is defined as the logical inverse of a change applied to the page as it existed. To correctly undo a loser’s change to page P, the page must first be in the exact state it was in when that change was made — which means every change up to that point, from every transaction, must be present. Repeating history reconstructs that exact state so the undo pass has a well-defined starting point (Mohan et al. 1992).

Pass 3 — Undo: roll back the losers, logging as you go

Undo reverses the changes of every transaction still marked UNDO in the ATT. To be efficient it processes all losers together in a single backward sweep, using the lastLSN of each and the prevLSN chains: at each step it picks the record with the largest LSN among all losers and undoes it, then follows that record’s prevLSN to the transaction’s next-older record (CMU 15-445 L21).

The subtlety is crash-safety: what if the machine crashes again partway through Undo? ARIES solves this with the Compensation Log Record (CLR). As it undoes a change, ARIES writes a CLR to the log describing the inverse action just performed. A CLR “has all the fields of an update log record plus the undoNextLSN pointer (i.e., the next-to-be-undone LSN)” (CMU 15-445 L21). The undoNextLSN points past the record just undone, to the next record that still needs undoing for that transaction.

Two properties follow. First, CLRs are redo-only — they are never undone. If recovery crashes and restarts, Redo will re-apply the CLRs like any other record (they are part of “history”), and Undo resumes from wherever the undoNextLSN chain left off rather than re-undoing already-compensated work. This is precisely what makes ARIES tolerant of “crashes during recovery” — a guarantee simpler logging schemes lack. Second, because the undoNextLSN chain skips over records already undone, the amount of undo work never grows on repeated crashes; it monotonically shrinks. The same CLR machinery implements partial rollback — SQL SAVEPOINT / ROLLBACK TO — by undoing only back to the savepoint’s LSN.

Worked Example — Tracing a Log Through Recovery

Consider this abridged log for a single transaction T1 that updates record A, then aborts (adapted from CMU 15-445 L21):

LSN | prevLSN | TxnId | Type    | Object | Before | After | UndoNextLSN
001 |  nil    |  T1   | BEGIN   |   -    |   -    |   -   |    -
002 |  001    |  T1   | UPDATE  |   A    |   30   |   40  |    -
011 |  002    |  T1   | ABORT   |   -    |   -    |   -   |    -
026 |  011    |  T1   | CLR-002 |   A    |   40   |   30  |   001
027 |  026    |  T1   | TXN-END |   -    |   -    |   -   |   nil

Reading it: T1 begins (001), changes A from 30 to 40 (002), then aborts (011). The abort triggers undo of record 002 — so ARIES writes CLR-002 (026), which reverses A back to 30 and sets undoNextLSN = 001 (the record before the one just undone; 001 is a BEGIN, so there is nothing more to undo). Finally TXN-END (027) marks T1 completely finished. Note that the CLR at 026 is an ordinary redoable record — if the machine crashed after 026, Redo would re-apply the “A ← 30” compensation, and Undo would find undoNextLSN = 001 and stop. The abort is thus itself crash-safe, and A is deterministically left at 30.

Physiological Logging — What Goes In an UPDATE Record

ARIES logs at a level Mohan called physiological: “physical” across pages but “logical” within a page. A record targets a single page but “identif[ies] tuples based on a slot number in the page without specifying exactly where in the page the change is located. Therefore the DBMS can reorganize pages after a log record has been written” (CMU 15-445 L20). This is the near-universal choice because it keeps records small (a slot-relative delta, not a whole page image) while still allowing the storage engine to compact a page’s free space without invalidating the log. Contrast with physical logging (byte-level before/after images at fixed offsets — like a git diff) and logical logging (record the high-level SQL operation — compact, but hard to recover under non-deterministic concurrency and slow because every transaction must be re-executed).

Failure Modes and Common Misunderstandings

“Redo only replays committed transactions.” No — this is the most common misunderstanding. Redo repeats history, replaying loser transactions’ changes too, precisely so Undo has a well-defined page state to reverse. Skipping losers in Redo would break undo correctness (Mohan et al. 1992).

Forgetting that STEAL creates on-disk uncommitted data. Because the buffer pool may evict a dirty page belonging to a live transaction, an aborted transaction’s change can be sitting on disk. Recovery must undo it. Engineers who think of the log as “just redo for committed work” miss this — it is exactly why the undo pass, the undo log (InnoDB), or MVCC-based rollback (PostgreSQL) exists (see Multiversion Concurrency Control).

Assuming recovery must scan the whole log. Redo begins at the minimum recLSN in the DPT, not at the log’s start; Analysis begins at the last checkpoint. Recovery time is therefore bounded by activity since the last checkpoint — the entire reason checkpoints exist.

Crash during recovery. ARIES handles it: crash during Analysis → rerun Analysis; crash during Redo → redo everything again (idempotent via pageLSN); crash during Undo → resume via undoNextLSN chains and never re-undo (CMU 15-445 L21). A recovery algorithm that is not crash-safe during recovery is a latent data-loss bug.

Alternatives and When to Choose Them

Shadow paging (NO-STEAL + FORCE) avoids logging altogether: updates go to copied “shadow” pages, and commit atomically swaps the database root pointer. Undo is trivial (discard shadows) and redo is unnecessary. But commit must flush the page table, root, and every updated page, it fragments related data across the disk, needs garbage collection, and typically allows only one writer at a time (CMU 15-445 L20). SQLite used a shadow-paging-like rollback journal before switching to WAL mode in 2010. Shadow paging is a reasonable choice only for tiny, low-concurrency stores.

Redo-only recovery (PostgreSQL). PostgreSQL implements a simplified ARIES: it repeats history via WAL redo but has no physical undo pass. Rolling back an aborted transaction is instead handled by Multiversion Concurrency Control — the aborted transaction’s new tuple versions are simply marked invisible via transaction status, and the prior versions remain visible. This trades a UNDO pass for MVCC bloat and vacuuming. InnoDB and Oracle keep a genuine undo log and do perform undo. Both are ARIES descendants; they differ only in where the undo information lives.

Production Notes

InnoDB’s redo log is “a disk-based data structure used during crash recovery to correct data written by incomplete transactions … replayed automatically during initialization and before connections are accepted” — pure ARIES-style redo, keyed by an “ever-increasing LSN value,” with recovery starting “at the latest checkpoint LSN” recorded in a redo file header (MySQL 8.4 — InnoDB Redo Log). Modern InnoDB parallelizes redo by grouping records per page. PostgreSQL’s WAL replay is likewise redo-forward from the last checkpoint’s redo pointer. In both engines, the ARIES structure is visible in the operational metrics: recovery time is dominated by the volume of WAL/redo between the last checkpoint and the crash, which is why checkpoint tuning is the primary lever on the recovery-time objective (see Checkpoints and Fuzzy Checkpointing).

Gray & Reuter’s Transaction Processing (1992) is the encyclopedic treatment of the recovery-manager design space in which ARIES sits; the Mohan et al. paper is the specific algorithm that won.

See Also

Graph View

Backlinks