ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging

In one breath — the whole paper, compressed

ARIES is a write-ahead-logging recovery method that makes crash recovery correct in the presence of record-level locking, operation logging, and variable-length records. Its central move is counter-intuitive: during restart it first repeats history, redoing every logged update that is missing from a page, including updates made by transactions that never committed, and only then rolls the losers back. Repeating history restores the page LSN stamped in each page to a true description of that page's state, which is what makes it safe to undo operations logically and to log increments rather than before-images. Rollback work is itself logged, as redo-only compensation log records (CLRs) whose UndoNxtLSN pointer skips over already-undone records, so a transaction's undo cost is bounded no matter how many nested rollbacks or restart failures occur. Restart is three passes over the log, analysis then redo then undo, driven by a fuzzy checkpoint that forces no pages and only records the dirty-page table and transaction table.

Before this paper — the world it landed in

By the late 1980s the two dominant recovery lineages both had a hole in them. System R and SQL/DS used shadow pages: recovery started from an action-consistent shadow version of the whole database, so there were no page LSNs, no compensation records, and no logging of index or space-management changes, at the cost of very expensive checkpoints, lost clustering, and lock-step recovery of related objects. WAL-based products such as DB2, IMS, Encompass, and NonStop SQL had adopted WAL but carried over System R paradigms, notably selective redo, in which restart redoes only the updates of committed and in-doubt transactions. Selective redo worked in those systems only because they locked at page granularity or logged physical byte ranges, and it produced pathological logging: DB2 and Encompass would compensate their own compensation records, so repeated failures during restart could grow the log exponentially. Meanwhile customers wanted record-level locking, hot-spot lock modes such as increment and decrement, variable-length records without offline reorganization, and restart fast enough for hot standbys, and none of the existing methods delivered all of that together.

The problem — what was actually breaking

Selective redo is unsafe with fine-granularity locking: if a nonloser's update to a page is redone after a loser's earlier update to the same page, the page LSN is pushed past the loser's LSN, and the undo pass can no longer tell whether the loser's update is actually present on the page.
Reversing the order does not help either: if undo runs before redo, as in System R, the CLR written during undo raises the page LSN above a later committed update's LSN, so that committed update is never redone and durability is violated.
Operation logging, which is what semantically rich lock modes such as increment and decrement require, is intolerant of imprecision: redoing an operation already present in a page or undoing one that is absent silently corrupts the data, unlike value logging where such repeats are idempotent.
Existing WAL systems logged rollback work in ways that did not terminate cleanly: DB2, Encompass, and AS/400 undo CLRs and so write compensations for compensations, and IMS undoes the same non-CLR more than once, giving unbounded log growth under nested rollbacks or repeated failures during restart.
Flexible storage management for variable-length records demands that a page be garbage-collected by moving records within it without locking or logging those moves, which rules out the physical byte-range locking and logging used by IMS, VAX DBMS, and VAX Rdb/VMS.
A no-steal buffer policy is not an escape hatch: under record locking a hot page may permanently contain some uncommitted update and therefore never be written out, forcing the system either to quiesce the page or to pay an enormous restart redo cost.

Core ideas — the contributions, and why they work

Repeating history before undo

The redo pass of ARIES reapplies every logged update whose effect is missing from the page on disk, without regard to whether the writing transaction committed, aborted, or was still running at the crash. This reestablishes the exact database state as of the moment of failure, including the uncommitted work of loser transactions and including the compensations written during rollbacks that were in flight. The reason this matters is that it makes the page LSN an honest description of the page again, so the undo pass never has to ask whether an update is present: it just undoes unconditionally, walking the transaction's backward chain. As the paper puts it, without repeating history the page LSN is no longer a true indicator of the state of the page, and that is precisely why selective redo breaks under record locking.

One page LSN as the state variable

Every database page carries a single field, the page LSN, holding the LSN of the log record describing the most recent update to that page, and every log record's LSN is monotonically increasing. This single value is the whole correlation mechanism between the log and the physical state of the data, and it is what gives idempotence of redo without imposing any constraints on the data itself. Contrast Encompass and NonStop SQL, which require every record to have a unique key so that a misapplied undo can be detected, or DB2, which needs an extra LSN per minipage when an index leaf is subdivided. ARIES deliberately refuses per-object LSNs because they waste and fragment page space and cannot cope with deleted or variable-length objects.

Redo-only CLRs chained by UndoNxtLSN

Every update performed during a rollback, whether a normal rollback, a partial rollback to a savepoint, or restart undo, is itself logged as a compensation log record. A CLR in ARIES is never undone, so it needs to carry redo information only, and it carries an UndoNxtLSN pointer set to the PrevLSN of the record it just compensated. Following that pointer during a later rollback jumps straight over everything already undone, so a non-CLR is never undone twice and a CLR is never compensated. The consequence is a hard bound on logging: a rolled back transaction writes exactly as many CLRs as it wrote undoable records going forward, however many nested rollbacks or restart crashes intervene.

Page-oriented redo with logical undo

Redo in ARIES is always page-oriented: the log record names the page, that page is fetched, and nothing else in the database, no catalog descriptor and no index traversal, is consulted. Undo, by contrast, is allowed to be logical and may touch a page different from the one originally modified. The motivating case is a key inserted on page 10 of a B-tree by an uncommitted transaction and then moved to page 20 by another transaction that splits the leaf; the first transaction's rollback retraverses the tree, deletes the key from page 20, and writes a CLR describing that deletion. Because the CLR describes what actually happened rather than the inverse of the original action, the resulting state remains page-redoable, which is what buys both high concurrency and recovery independence between pages.

Fuzzy checkpoints and the Dirty Pages table

A checkpoint in ARIES writes a begin-chkpt record, then an end-chkpt record containing the transaction table and the buffer pool dirty-pages table, and then stores the begin-chkpt LSN in a master record; no dirty page is ever forced. Each dirty-pages entry pairs a page identifier with a RecLSN, the end-of-log LSN at the moment the clean page was first fixed for modification, which bounds how far back updates for that page might be missing from disk. The minimum RecLSN over the table is the RedoLSN, the point from which the redo pass must start, and the table also filters which pages redo needs to touch at all. Because the checkpoint is fuzzy, the table may be gathered a hundred entries at a time under separate latch acquisitions, and staleness is harmless because analysis also folds in every log record written since the begin-chkpt.

Nested top actions via a dummy CLR

Some updates, canonically a file extension whose new space other transactions immediately start using, must survive even if the enclosing transaction aborts, yet must still be atomic in themselves. ARIES gets this without starting an independent transaction, which would cost a commit force and could deadlock against its own parent. The transaction remembers the LSN of its last log record, performs the actions with ordinary undo-redo log records, and on completion writes a dummy CLR whose UndoNxtLSN points back to that remembered LSN. A later rollback of the enclosing transaction follows the dummy CLR's pointer and jumps clean over the whole sequence, while a crash before the dummy CLR is written leaves ordinary undoable records that get rolled back normally. This trick works only because history is repeated.

How it works — the mechanism, concretely

Log records and the page structure

A log record carries its LSN, a Type (update, compensation, prepare, rollback, end, OSfile-return), the TransID, a PrevLSN pointing to the previous log record of the same transaction, a PageID for update and compensation records, and the redo and/or undo Data. PrevLSN is zero in the first record of a transaction, so no explicit begin-transaction record is needed. UndoNxtLSN appears only in CLRs and holds the PrevLSN of the record being compensated, or zero when nothing is left to undo. Data may be logical: only changed fields need logging, free-space bookkeeping on the page need not be logged at all, and for increment or decrement operations the operation code and the delta suffice instead of before and after images. Every page holds exactly one page LSN, the LSN of the most recent update or CLR applied to it.

The normal update path

To update a record the transaction first locks the record, fixes the page in the buffer pool, X-latches it, performs the update, appends the log record, copies the log record's LSN into the page LSN and into the transaction table, then unlatches and unfixes. The latch is deliberately held across the call to the logger so that the order of log records for a page matches the order of updates on that page, which is what makes physical redo of derived fields safe under repeating history. Latches, not locks, provide physical page consistency, and at most two page latches are held at once, so a transaction never waits on a latch inside a deadlock cycle. When the record identity is not known until the page is examined, as during an insert, the lock is requested conditionally while the latch is held, and if it is not granted the latch is dropped, the lock requested unconditionally, the page relatched, and the previously verified conditions rechecked.

Savepoints, rollback, and the CLR chain

Establishing a savepoint just remembers SaveLSN, the LSN of the transaction's most recent log record, in virtual storage; DB2-style systems set one before every updating SQL statement to get statement-level atomicity. ROLLBACK takes a SaveLSN and a TransID and walks backward: a non-CLR is undone, a CLR is written whose UndoNxtLSN is that record's PrevLSN, and the walk continues from PrevLSN; a CLR encountered on the way is not undone, and the walk continues from its UndoNxtLSN; redo-only records are skipped. No locks are acquired during rollback and only latches are taken, so a rolling-back transaction cannot become a deadlock victim. Because a given object's first update is undone exactly once, its lock can be released as soon as that CLR is written, which makes it feasible to break a deadlock with a partial rollback rather than a total one.

Analysis pass

Restart reads a master record to find the begin-chkpt of the last complete checkpoint and scans forward to the end of the log. It seeds the transaction table and dirty-pages table from the end-chkpt record, then for each subsequent record updates LastLSN and UndoNxtLSN for the transaction, inserts any page not already in the dirty-pages table with the current LSN as its RecLSN, sets state to prepared on a prepare record and unprepared on a rollback record, deletes the entry on an end record, and drops all pages of a returned file on an OSfile-return record. Transactions left with state unprepared and UndoNxtLSN zero had fully rolled back before the crash but lack an end record, so analysis writes one and removes them. The pass outputs the loser list, the dirty-pages table, and RedoLSN, the minimum RecLSN in that table; if the table is empty the redo pass is skipped entirely. The pass is an optimization, not a requirement, and the OS/2 Extended Edition implementation of ARIES has no analysis pass at all.

Redo pass

Starting at RedoLSN the log is scanned forward. A redoable update or compensation record is a candidate only if its PageID is in the dirty-pages table and its LSN is greater than or equal to that entry's RecLSN; otherwise it is skipped without any I/O, which is how RecLSN limits the number of pages read. For a candidate the page is fixed and X-latched and its page LSN compared with the log record's LSN; if the page LSN is smaller the update is applied and the page LSN set to the log record's LSN, and if not, the entry's RecLSN is advanced to the page LSN plus one because the page evidently reached disk after the checkpoint. Nothing is logged during redo, which is what allows aggressive parallelism: the dirty-pages table lets the system issue asynchronous reads for all needed pages up front and hand per-page queues of log records to separate processes, since reordering across pages is harmless as long as a single page's updates are reapplied in log order.

Undo pass

The undo pass rolls back all losers in a single backward sweep, repeatedly picking the maximum UndoNxtLSN among the still-unfinished unprepared transactions and processing that record. The dirty-pages table is not consulted and the page LSN is not compared, because history has already been repeated and the update is therefore known to be present. Undoing an update writes a CLR, stamps the CLR's LSN into the page and into LastLSN, and sets the transaction's UndoNxtLSN to the undone record's PrevLSN; reaching PrevLSN zero means the transaction is fully undone, so an end record is written and the entry removed. A CLR encountered during the sweep contributes only its UndoNxtLSN. Undo can be parallelized, but a single transaction must be handled entirely by one process because of the UndoNxtLSN chaining; after undo, locks are reacquired for prepared transactions and a checkpoint is taken.

Checkpoints during restart and media recovery

ARIES can checkpoint in the middle of restart, which bounds the damage of a crash during recovery. After analysis the checkpoint simply records the analysis-time tables; during redo the buffer manager updates the restart dirty-pages table by setting a written page's RecLSN to the LSN up to which all records have been processed; at the start of undo the restart table becomes the buffer pool table, is cleaned of non-resident pages, and is maintained as in normal operation. Media recovery uses a fuzzy image copy taken directly from nonvolatile storage, concurrently with updates and therefore possibly containing uncommitted data, tagged with the begin-chkpt of the most recent complete checkpoint. The media recovery redo point is the minimum of the RecLSNs of that entity's dirty pages in that checkpoint and the begin-chkpt LSN itself; recovery reloads the copy, redoes forward from that point, and then undoes any in-progress transactions that touched the entity. Because every page's change is logged individually, a single damaged page can be restored from an image copy and rolled forward alone, and DB2 uses the same idea to repair a page corrupted by an abnormally terminating process, detected by a bit set in the page header while the page is latched for update.

What the paper showed — measurements and proofs

Bounded rollback logging: for a rolled back transaction the number of CLRs written equals exactly the number of undoable log records written during its forward processing, and this holds even under nested rollbacks and repeated failures during restart, whereas the paper reports that in Encompass and DB2, which undo CLRs, the number of log records written under repeated restart failures grows exponentially in the worst case, and grows linearly in IMS and in Schwarz's operation logging method.
Because CLRs are never undone they carry redo information only, so on average the log space consumed by rolling a transaction back is half the space consumed by its forward processing.
Permanent nonvolatile space overhead is one LSN per page and nothing else, versus DB2, which must keep an additional LSN for each of the 2 to 16 minipages a user may divide an index leaf page into, fragmenting the space available for keys.
In the no-conflict case acquiring and releasing a latch costs tens of instructions against hundreds for a lock, a transaction holds at most two or three latches at a time and at most two page latches simultaneously, and since no locks at all are acquired during rollback a rolling-back transaction can never be involved in a deadlock.
Restart requires only one backward traversal of the log, the undo pass, and media recovery requires only one forward traversal, which matters when part of the log lives on tape; the redo pass reads only pages listed in the dirty-pages table whose RecLSN does not exceed the log record's LSN.
A simulation study of ARIES cited by the authors reports fast recovery even with long intercheckpoint intervals and states that the difference between mean transaction response time and the duration a transaction would take alone in a never-failing system is negligibly small, evidence that the recovery method composes well with fine-granularity locking.

Limits and trade-offs — conceded and discovered

Conceded in the paper: repeating history redoes updates of loser transactions that will immediately be undone, so some redo work and some page dirtying is provably unnecessary; the authors point to follow-on work that restricts how much history is repeated for losers.
Conceded: deferred or selective restart breaks down when a loser transaction needs a logical undo on an offline object, because the affected page cannot be predicted; for the high-concurrency index methods of ARIES/IM one cannot even predict in advance whether page-oriented undo will suffice, so such transactions must be stopped and finished later while holding their locks.
Conceded: the space reservation problem, keeping space freed by an uncommitted delete from being consumed by another transaction, is explicitly left to a separate paper, and undo parallelism is limited because the UndoNxtLSN chain forces one process to handle a whole transaction.
Conceded: the paper covers a single-site log and does not treat message logging and recovery, and nested transactions, shared-disk data sharing, and index-specific concurrency all required separate follow-on papers rather than falling out of ARIES directly.
Exposed by later work: ARIES ties recovery to in-place update with undo logging, which is a poor fit for multiversion engines that keep old versions in the data itself; PostgreSQL, for example, uses ARIES-style physiological WAL and per-page LSNs but has no undo pass at all, relying on MVCC visibility and vacuum instead.

What it became — the systems that inherited it

ARIES became the default answer to crash recovery in relational engines, and the paper itself lists implementations in IBM's OS/2 Extended Edition Database Manager, DB2, Workstation Data Save Facility/VM, Starburst and QuickSilver, plus the University of Wisconsin's EXODUS and Gamma database machine. The same group extended it into ARIES/KVL and ARIES/IM for B-tree key-value and index-management concurrency and ARIES/LHS for hash-based storage, which is where the logical-undo machinery really pays off. Microsoft SQL Server implements ARIES directly, with analysis, redo, and undo phases named as such, and its later constant-time recovery work is built on top of that structure. InnoDB in MySQL inherits the core apparatus, a per-page LSN, write-ahead redo logging with a checkpoint LSN, fuzzy checkpointing, and separate undo information for rollback. PostgreSQL took the physiological WAL and per-page LSN but deliberately dropped the undo pass, using MVCC and vacuum in its place, which is the clearest evidence of where the design's boundary lies. The vocabulary the paper coined, LSN, page LSN, CLR, RecLSN, dirty-page table, repeating history, fuzzy checkpoint, is now the standard textbook language for recovery, and log-centric cloud designs such as Amazon Aurora, which treats the redo log as the database and ships log records instead of pages, are recognizable descendants of ARIES's insistence that the log, not the data page, is the authoritative record of history.

In the paper’s words — verbatim

“We introduce the paradigm of repeating history to redo all missing updates before performing the rollbacks of the loser transactions during restart after a system failure.”

Abstract

“By not repeating history, the page LSN is no longer a true indicator of the current state of the page.”

§10.1

“In brief, ARIES accomplishes the goals that we set out with by logging all updates on a per-page basis, using an LSN on every page for tracking page state, repeating history during restart recovery before undoing the loser transactions, and chaining the CLRs to the predecessors of the log records that they compensated.”

§13

Vocabulary — as this paper uses it

LSN (log sequence number): A monotonically increasing identifier assigned to every log record when it is appended, typically the record's logical address in the ever-growing log. It is the universal currency for ordering and for correlating log positions with page states.
page LSN: A field in every database page holding the LSN of the log record describing the most recent update applied to that page, whether a regular update or a CLR. Comparing it with a log record's LSN is how ARIES decides whether an update is already reflected in the page.
CLR (compensation log record): The log record written to describe an update performed during a rollback. In ARIES a CLR is redo-only and is never itself undone, so it needs no before-image and never triggers a compensation of its own.
UndoNxtLSN: A field present only in CLRs, holding the PrevLSN of the log record that CLR compensated, that is, the next record of the transaction still to be undone. Following it during a later rollback skips over everything already undone.
RecLSN (recovery LSN): The value recorded with a page in the dirty-pages table when a clean page is first fixed with intent to modify, equal to the end-of-log LSN at that moment. It marks the earliest point in the log from which updates to that page might be missing on nonvolatile storage.
Repeating history: The ARIES restart discipline of redoing every logged update missing from a page before any rollback begins, including updates of transactions that never committed. It restores the database to its exact state at the moment of failure so that undo can proceed unconditionally.
Loser transaction: A transaction that had neither committed nor reached the in-doubt state of two-phase commit when the system failed. Losers' updates are redone during the redo pass like everyone else's and then rolled back in the undo pass.
Nested top action: A subsequence of a transaction's actions that must not be undone once it completes, even if the enclosing transaction rolls back, while still being atomic in itself. ARIES implements it by writing a dummy CLR at the end whose UndoNxtLSN points back to before the sequence started.
Latch: A cheap semaphore-like primitive used to guarantee physical consistency of a page while it is read or modified, as distinct from a lock, which guarantees logical consistency of data. Latches are held briefly, are not tracked by the deadlock detector, and are requested so as never to participate in deadlocks.

On the timeline — where this sits in the story

Year1992

MilestoneARIES recovery algorithm

Problem solvedDatabases needed fast, correct recovery after crashes while supporting fine-grained locking and high concurrency.

How it solved itARIES used write-ahead logging, repeating history during redo, and logical undo for robust crash recovery.

Why it matteredBecame one of the most influential recovery algorithms in commercial database systems.

DDIACh. 8: Transactions

View on the timeline