ARIES Crash Recovery: Analysis, Redo, and Undo with LSN Tracking

The Problem: Steal, No-Force, and the Durability Gap

A transactional database must guarantee atomicity (all-or-nothing) and durability (committed data survives crashes) even though it caches pages in a volatile buffer pool. Two buffer-management choices create the recovery problem:

• Steal: the buffer manager may evict (write to disk) a dirty page belonging to an uncommitted transaction. If that transaction later aborts or the system crashes, those changes must be undone on disk.
• No-Force: a transaction may commit without forcing all its dirty pages to disk. If the system crashes before those pages are flushed, the committed changes must be redone from the log.

Steal + No-Force gives the best runtime throughput (no flush-at-commit stalls, free eviction), but it means recovery needs both redo and undo. ARIES solves this with write-ahead logging: before any data page is written to disk, the log record describing that change must already be on stable storage (the WAL rule). The log is the ground truth; the on-disk data pages are merely a possibly-stale cache that ARIES reconciles after a crash.

How ARIES Works: LSNs, the Log, and Three Phases

Every log record gets a monotonically increasing Log Sequence Number (LSN). Each data page stores in its header the pageLSN — the LSN of the most recent log record whose change is reflected on that page. Comparing a log record's LSN to a page's pageLSN tells recovery, in O(1), whether a change is already present. Update records carry a prevLSN pointer, forming a per-transaction backward chain.

Two in-memory tables are rebuilt during recovery:

• Transaction Table (TT): active transactions and each one's lastLSN.
• Dirty Page Table (DPT): dirty pages and each one's recLSN — the LSN that first dirtied that page since it was last flushed.

The three phases:

1. Analysis: scan forward from the last checkpoint, rebuilding TT and DPT and finding the crash point.
2. Redo (repeat history): replay every logged change — committed or not — from the smallest recLSN in the DPT, restoring the exact pre-crash state.
3. Undo: roll back all transactions that were live at the crash (the losers), writing compensation records as it goes.

Complexity, CLRs, and a Worked Step-Trace

Recovery cost is O(R + U) log I/O: Redo touches every record from the oldest recLSN forward; Undo touches every record belonging to loser transactions, backward. Fuzzy checkpoints bound the redo distance, so cost is proportional to work-since-checkpoint, not database size. Normal-run overhead is one sequential log append per update — amortized O(1).

The redo step is idempotent via LSN check: apply the change only if pageLSN < recordLSN; otherwise it is already on the page. Undo emits a Compensation Log Record (CLR) for each undone action. A CLR is redo-only and stores undoNextLSN = the prevLSN of the action it just reversed. This is the crucial trick: if the system crashes mid-undo, recovery follows undoNextLSN and never re-undoes an already-compensated action — bounding total work.

LSN 10 T1 update P5   (prevLSN 0)
LSN 20 T2 update P7   (prevLSN 0)
LSN 30 T1 commit
LSN 40 T2 update P5   (prevLSN 20)   <-- CRASH after this

Analysis: TT={T2:lastLSN 40}; DPT={P5:recLSN 10, P7:recLSN 20}
Redo    : from LSN 10, reapply 10,20,40 where pageLSN < LSN
Undo    : loser=T2. Undo 40 -> CLR undoNextLSN=20;
          Undo 20 -> CLR undoNextLSN=0; done. T1 kept.

Where ARIES Runs in Real Systems

ARIES came out of IBM's DB2 development and remains the reference design for durable, high-concurrency storage engines:

• IBM Db2 and Microsoft SQL Server implement ARIES-style WAL recovery essentially as described in the paper, including CLRs and fuzzy checkpoints.
• PostgreSQL uses WAL with LSNs, full-page writes, and redo-based crash recovery driven by checkpoints; its design is ARIES-influenced though it relies on MVCC (rather than in-place undo) to hide uncommitted rows, so it has no separate on-disk undo pass.
• SQLite's WAL mode and MySQL/InnoDB's redo log + rollback segments echo the same steal/no-force + LSN discipline.

The same ideas — a monotonic sequence number, an idempotent replay log, and a checkpoint to bound replay — reappear far beyond databases: in journaling filesystems (ext4/XFS metadata journals), Kafka log offsets, Raft/Paxos replicated logs, and LSM-tree write-ahead logs (RocksDB, Cassandra). ARIES is the canonical articulation of "the log is the database."

ARIES vs. the Alternatives

The main rival at ARIES's birth was shadow paging: instead of logging, a transaction writes modified pages to new disk locations and atomically swaps a page-table root at commit. Recovery is trivial (discard uncommitted shadow pages), but shadow paging scatters logically sequential data across the disk, destroying locality, complicating concurrent access, and requiring expensive garbage collection. ARIES keeps updates in place, preserving clustering and enabling fine-granularity locking and partial rollbacks — impossible with page-granular shadowing.

Against simpler logging schemes:

• Undo-only logging needs Force (flush committed pages at commit) — heavy commit-time I/O.
• Redo-only logging needs No-Steal (pin all dirty pages of active transactions) — buffer-pool pressure.

ARIES accepts the complexity of doing both undo and redo precisely so it can run the cheapest runtime policy (Steal + No-Force). Its signature refinements over textbook undo/redo are repeating history before undo (which cleanly supports logical undo and CLRs) and physiological logging (physical-to-a-page, logical-within-a-page), which shrinks log volume while keeping replay page-local and idempotent.

Pitfalls, Failure Modes, and Significance

ARIES is subtle, and implementations fail in characteristic ways:

• WAL-rule violations: flushing a data page before its log record reaches stable storage. A crash then leaves an on-disk change with no log record to undo it — silent corruption. The log must also be flushed up to a transaction's commit LSN before reporting commit.
• Non-idempotent redo: forgetting the pageLSN < recordLSN guard double-applies a change (e.g., increments a counter twice) if recovery restarts.
• Torn / partial page writes: a crash mid-write leaves a page half-old, half-new with an unreliable pageLSN. Systems defend with checksums plus full-page-write journaling (PostgreSQL) or double-write buffers (InnoDB).
• Losing CLR undoNextLSN chaining: re-undoing already-compensated actions, which can loop or corrupt.

Its significance is foundational: ARIES showed you can have maximal runtime concurrency and throughput and provably correct, restartable recovery at once. Thirty-plus years on, its LSN-plus-idempotent-log pattern underpins essentially every serious durable data system.

ARIES vs. other crash-recovery / logging strategies

Method	Buffer policy	Recovery cost	Tradeoff
ARIES (WAL + physiological logging)	Steal + No-Force	3 log passes; redo from oldest recLSN, undo losers	Small runtime overhead (log I/O); fastest normal-run throughput; complex to implement
Shadow paging	No-Steal + Force (page copy-on-write)	Near-instant (swap page table root)	No log needed but fragments data, kills locality, poor for concurrency
Force / No-Steal (undo-only or redo-only)	No-Steal or Force	One phase only	Cripples runtime: forces flushes at commit or pins dirty pages until commit
Undo-only logging	Steal + Force	Undo losers only, no redo	Must flush all committed pages before commit -> heavy commit-time I/O
Redo-only logging	No-Steal + No-Force	Redo winners only, no undo	Cannot steal frames -> buffer pool must hold every dirty page of active txns