CS PAPERS DEEP-READ · PAPER 60

ARIES: Database Crash Recovery

Mohan, Haderle, Lindsay, Pirahesh, Schwarz · IBM Almaden · ACM TODS 1992

What did this paper do?

You tap "confirm transfer" and the screen says "done." If the data center loses power one second later, could half the money vanish — debited from one account and never credited to the other? It can't. And that confidence comes in large part from ARIES, published in 1992 by a team at IBM. It took "how to tidy up the books after a crash" from a pile of house-specific folk remedies and turned it into one standard method you can explain, argue about, and copy. Most databases you touch today still run on its skeleton.

First, how hard this is

A database doesn't write each change straight to disk — far too slow. It changes things in memory, lets them pile up, and writes whole blocks back later. So at the instant the power dies, the disk holds a half-cooked mess: some transactions already told the user "done" while their changes still sit in memory (lost); others got only halfway and never committed, yet the memory they dirtied happened to be flushed to disk anyway (dirty). Both kinds coexist, tangled together on the same page.

The one core move: write the diary before the ledger

ARIES rests on a rule so plain it sounds boring: before touching the ledger, write down what you are about to do in a diary, and make sure that diary entry reaches disk first. The diary is append-only, never erased — "I changed that number on page 7 from 3 to 5." With it, the half-cooked mess is salvageable: whatever the diary records but the ledger lacks gets redone; whatever traces a half-finished transaction left behind get undone by working backwards. And the diary is written sequentially, which is far faster than scribbling in a dozen scattered spots of the ledger.

Three details that make redo and undo actually safe

1. Number every diary entry, and stamp every ledger page. Each page carries a line in its header: "I was last modified by diary entry 42." Hold diary entry 57 against it: the stamp says 42, earlier than 57, so this change hasn't landed on this page yet — redo it. If the stamp already says 90, it was applied long ago — skip. So redoing ten times gives the same result as redoing once, which matters enormously, because the power can die again mid-recovery and the whole thing starts over.

2. Replay history exactly, then undo. Recovery doesn't sort the good from the bad. It replays the diary end to end exactly as written — including changes made by the doomed half-finished transactions — restoring the database to precisely how it looked the instant before the crash, and only then cleanly undoes those half-finished transactions. Why the extra step? Because undo is an action with preconditions: to erase a record you first have to know where it is and what surrounds it. Redo only the "good" changes and the database lands in a strange state that never actually existed. It's forensic practice: put the scene back exactly as the photographs show it, then reason backwards step by step.

3. Undo itself gets written into the diary. Each time it undoes a step, it adds an entry: "just undid that one; the next one to undo is number N." If the power dies halfway through the rollback, on restart the last such entry says exactly where to resume — everything already undone is skipped wholesale and never undone twice. That is precisely what guarantees that repeated crashes still converge.

What it buys

With all this in place, a database can finally treat memory as memory: dirty data can be flushed whenever convenient (even for a transaction that hasn't committed), and a commit needn't wait for the data to land on disk — only the diary entry. Fast, and unafraid of power failure. The cost is real too: every change is written twice, so this diary becomes the busiest single lane in the system — and in the age of many-core in-memory databases, it turned into the new bottleneck.

Remember one thing

Before touching data, write the change into an append-only diary and get it on disk. After a crash, the "last modified by entry N" stamp on each page turns redo into an action that's safe to repeat any number of times; replay all of history exactly to restore the scene, then go back and undo the half-finished transactions — logging each undo step too. So no matter which instant the power dies again, recovery can pick up where it left off and is guaranteed to finish the cleanup.

Want the three-pass diagram, the CLR pointer chain, and the steal / no-force trade-off? → switch to the deep read

In one sentence

ARIES builds a three-pass recovery algorithm — Analysis → Redo → Undo — on top of write-ahead logging (WAL) and log sequence numbers (LSNs): the redo pass repeats history exactly (including the changes of transactions doomed to roll back) to restore the state at the moment of the crash, then undoes uncommitted transactions backwards, writing each undo step as a compensation log record (CLR) that is redo-only and never itself undone. It was the first method to simultaneously support a high-performance buffer policy, record-level locking, logical undo, partial rollback, and bounded, convergent recovery even when the system crashes again during recovery.

Glossary

Transaction: a group of operations that must all happen or none happen (a transfer's "debit here, credit there"). Commit = declare it in effect; rollback = treat it as never having happened. Recovery exists to deliver exactly that: no transaction half-done, no committed change lost to a power cut.
Page and buffer pool: a database reads and writes disk in fixed-size "pages" (say 8KB); the in-memory cache of pages is the buffer pool. A page modified but not yet written back is a dirty page.
Log: an append-only, never-rewritten stream of records saying "who changed what from which old value to which new value," kept separately and written sequentially — sequential writes are far faster than scattered random writes into the data files.
REDO / UNDO: redo = apply changes the log has but the disk page lacks; undo = erase traces an uncommitted transaction already left in the data.
Locking granularity: whether the unit of locking is a whole table, a page, or a single record. Finer granularity means more concurrency and harder recovery — which is exactly this paper's difficulty.
B-tree: the most common index structure; when a page gets too full it splits into two and records move house — the canonical "structural change" this paper worries about.
Idempotent: doing the operation once and doing it many times give the same result. Recovery must be idempotent, because it can crash mid-way and start over.

Where it sits

The authors are C. Mohan, Don Haderle, Bruce Lindsay, Hamid Pirahesh, and Peter Schwarz of IBM Almaden Research Center; it circulated as an IBM research report in 1989 and appeared formally in ACM TODS in 1992, running past sixty pages. It inherits System R's shadow paging (never overwrite a page — write a fresh copy and switch the page-table pointer at commit) and the transaction/logging theory of Jim Gray's line, and it launches the sister papers on index locking and concurrency (ARIES/KVL, ARIES/IM) plus the default blueprint for commercial relational recovery subsystems ever since. Codd's relational model gave databases their theoretical root; this paper gave them their engineering root.

The problem

Performance against correctness, head-on

All the difficulty comes from one fact: to be fast, the movement of pages between memory and disk cannot be aligned with the start and end of transactions. Two policy dimensions:

steal: when the buffer pool needs room, allow pages dirtied by an uncommitted transaction to be written to disk. Forbid it and a long transaction can pin the buffer pool solid; allow it and the disk may hold uncommitted traces → UNDO required.
no-force: at commit, don't force every modified data page back to disk (a pile of expensive random writes) — force only the log. So committed changes may live only in memory → REDO required.

Performance demands steal + no-force, and the price is that both redo and undo become mandatory. That is the source of the whole problem.

Fig 1 · The buffer policy decides the recovery duty: chasing performance means stealing dirty pages and not forcing at commit, so both redo and undo are mandatory.

Fine-granularity locking pushes it over the edge

What really broke earlier methods was record-level locking. Once the locking unit drops from a page to a single record, changes from several transactions sit side by side on one page: you can no longer roll a page back wholesale to an older version (that would erase someone else's committed work too). And a B-tree split moves records to other pages, so by the time you undo an insert the record may no longer be where it was — "restore the bytes in slot 3 of page 7" simply stops working. Undo has to be able to say, logically, "delete the record with key 42."

Earlier schemes each had a crack: shadow paging destroyed physical clustering and concurrency; some WAL schemes redid only the "winners," or required pages to be in some agreed state at rollback, which collides head-on with fine-granularity locking; others re-undid work when a crash happened during rollback, so the log could grow without bound. The real question was: is there an algorithm that permits steal / no-force, supports record-level locking and logical undo, and still converges with bounded work when the system crashes again at any point during recovery?

Core ideas

Part zero: WAL — the log goes first

One rule: the log record describing a change must reach stable storage before the changed page may be written back to disk; a commit need only ensure its own log records are on disk. WAL was not invented by ARIES, but ARIES got everything built on top of it right.

Part one: LSN and page_LSN — making redo testable and idempotent

Every log record carries a monotonically increasing number, its LSN. The key move: every data page stores a page_LSN in its header, the LSN of the last log record that modified it. The redo test is then a single line: apply the record only if page_LSN < the record's LSN, then set page_LSN to it. What is it computing? "Has this page already seen this particular change?" The stamp the page carries turns a question you would otherwise have to guess at into one numeric comparison, which makes redo idempotent: crash halfway through recovery, start over, and the same change is never applied twice. The reliability of everything else in ARIES rests on that one small header field.

Fig 2 · The page_LSN stamp: one numeric comparison decides whether this page has already seen this change, so redo is safe to repeat.

Part two: repeating history

The most counterintuitive and most essential decision. The redo pass does not distinguish winners (committed) from losers (uncommitted): it reapplies every redoable change in order — including changes about to be undone — bringing the database back to exactly the instant of the crash, and only then undoes the losers.

Why the detour? Because in a world of fine-granularity locking and logical undo, undo is an action with preconditions: "delete the record with key 42" only means something if the page and the index are in the shape they were when that record was logged. Redo only the winners and the database sits in a mixed state that never actually existed, with undo facing a scene it has never seen. This one decision compresses the correctness argument into a single invariant: when redo ends, the database state equals the state at the moment of the crash.

Part three: CLRs and UndoNxtLSN — logging undo, and never undoing it

When ARIES undoes a change it doesn't quietly revert it; it writes a compensation log record (CLR) describing what the undo did. Every CLR carries a pointer, UndoNxtLSN, to the record preceding the one just undone — that is, to the next thing still needing undo. And a CLR is redo-only: it can be redone, but is never itself undone.

Fig 3 · CLR and UndoNxtLSN: undo is itself logged and carries a "what to undo next" pointer, so undo work stays bounded across repeated crashes.

Three payoffs: (1) undo work is bounded — crash during rollback, and on restart the last CLR's UndoNxtLSN resumes exactly where it stopped; already-undone stretches are skipped, there is no "undo of the undo," and the log doesn't balloon across repeated crashes (precisely the crack in earlier schemes); (2) partial rollback comes free — rolling back to a savepoint mid-transaction uses the same pointer machinery; (3) undo is protected by redo — since undo actions are in the log, they can be redone, so recovery may be interrupted at any point.

Part four: three passes — Analysis, Redo, Undo

Fig 4 · The three passes: analysis fixes the starting point and the losers, redo restores the crash-instant state, undo then cleans up uncommitted work backwards.

1 · Analysis: scan from the most recent checkpoint (a periodic log entry recording roughly how the system looked) to the end of the log, rebuilding the dirty-page table (each dirty page records a recLSN: the LSN of the record that first dirtied it since it was last written out) and the transaction table (transactions still alive at the crash and their last LSN). Take the smallest recLSN in the dirty-page table as the redo starting point, RedoLSN. This pass touches no data; it only establishes where to start and who the losers are.

2 · Redo: scan forward from RedoLSN, applying the test in Fig 2. The dirty-page table saves enormous work: any page not in the table, or whose recLSN already exceeds this LSN, was written out long ago, so the record is skipped without even reading the page into memory.

3 · Undo: merge the log records of all loser transactions into one stream in descending LSN order, undoing each and writing a CLR, until every loser is rolled back to its start. Merging rather than undoing one transaction at a time keeps each page from being visited more than about once.

And the checkpoint here is a fuzzy checkpoint: it writes only those two tables into the log, forcing no dirty pages and quiescing nothing; dirty pages drain in the background, and the smallest recLSN also decides how far the log can safely be truncated.

Part five: page-oriented redo, logical undo

Here is the signature compromise. Redo is always page-oriented — a log record touches exactly one page and depends on no other page's state (the paper's physiological logging: physical to a page, logical within it, as in "delete this record from this page and shuffle the rest"), which is both fast and decidable by page_LSN alone. Undo, however, may be logical: "delete the record with key 42," with the current index deciding which page that is, because the B-tree may have split since. That pairing is exactly what makes fine-granularity locking possible.

Alongside it sits the nested top action: a structural adjustment like a B-tree page split, once done, must not be undone when the enclosing transaction rolls back (other transactions may already be working on the new structure). The trick: after the sub-action completes, write a dummy CLR whose UndoNxtLSN points to just before the sub-action began, so a rollback of the outer transaction leaps straight over it and the structural change stands.

Key results

An honest note: this is a design paper, not an experimental one — there is no benchmark table in its sixty-odd pages. Its evidence comes in three kinds: a correctness argument (spelling out why recovery still converges, with bounded work, if it crashes again at any point); a capability comparison (a long section setting ARIES against System R's shadow paging, early DB2, IMS, Tandem and others, item by item — not on speed but on what is possible at all: does it allow steal / no-force, does it support record-level locking and partial rollback, is repeated-crash recovery bounded, must checkpointing quiesce the system); and industrial deployment (by publication ARIES had been implemented in several IBM products and prototypes, including the OS/2 Extended Edition Database Manager, the Starburst prototype, and the QuickSilver distributed file system).

So ARIES "won" not on a scoreboard but because it filled in the whole capability matrix at once: steal + no-force, record-level locking, logical undo, partial rollback, bounded recovery across repeated crashes, and non-quiescing checkpoints — no prior method delivered all six together.

Why it matters

It became the default blueprint for commercial relational recovery subsystems. IBM DB2 goes without saying; Microsoft SQL Server's restart recovery is described in exactly those three phases, analysis / redo / undo; MySQL's InnoDB uses an LSN-stamped physiological redo log plus separate rollback segments — the same skeleton. PostgreSQL is an instructive contrast: it too uses WAL and LSNs and replays by the LSN test, but its MVCC leaves uncommitted versions in place, hides them by visibility rules, and cleans them up later with VACUUM — so it has no ARIES undo pass at all, which nicely shows these parts can be taken apart and used separately.

It also turned a batch of terms into industry vocabulary: WAL, LSN, dirty-page table, compensation log record, repeating history. At a higher level, its contribution was to turn recovery from a pile of ad-hoc special cases into an algorithm you can reason about — with a stated invariant and a convergence guarantee (restart at any interruption point and it continues and terminates). Before it, recovery was the dirtiest, most feared code in every database.

Limits and criticism

Complex, and hard to implement correctly: sixty-odd pages of interlocking detail (latch protocols, nested top actions, the interplay of page- and record-level information), with the index algorithms spread across further sister papers; implementations calling themselves "ARIES-style" differ considerably from one another. It also gives no quantitative evaluation — nothing on log volume, recovery time, or checkpoint impact on live traffic, so implementers must weigh the trade-offs themselves.
Write amplification and the log bottleneck: each change generally needs both redo and undo information, and the log is the one serialized shared resource in the system. In the many-core in-memory era, log contention and flush latency became the scalability limit, prompting group commit, scalable logging work, and alternatives such as command logging — record only "which stored procedure ran, with what arguments," which is very cheap at runtime but forces recovery to recompute the entire history.
Its assumptions are being rewritten: ARIES assumes pages, disks, update-in-place, and a single node. LSM-trees, copy-on-write, MVCC, non-volatile memory, and cloud architectures that treat the log itself as the database and let the storage layer replay it all sidestep its division of labor to some degree. And as PostgreSQL shows, a different concurrency-control design removes the undo path entirely — the full ARIES shape is tied to "update-in-place plus fine-granularity locking," not the only answer to recovery.

Takeaways

1 · In one line: three-pass recovery (analysis → redo → undo) on top of WAL + LSN, where redo repeats all of history and undo writes redo-only CLRs.

2 · Root of the pain: performance forces steal + no-force, so REDO and UNDO are both mandatory; record-level locking then kills whole-page rollback and kills physical undo once a B-tree splits.

3 · The bedrock part: each page's header holds page_LSN, so redo is decided by one numeric comparison — hence idempotent, hence safe when recovery crashes again.

4 · The counterintuitive move: redo makes no distinction between winners and losers, restoring the exact crash-instant state so undo has a scene it recognizes.

5 · CLR + UndoNxtLSN: undo is logged and never undone, so undo work stays bounded across repeated crashes, and partial rollback to a savepoint comes free.

6 · Page-oriented redo with logical undo (physiological logging) is the signature compromise; nested top actions keep B-tree splits from being rolled back; fuzzy checkpoints force no pages and quiesce nothing.

7 · Form of evidence: not benchmarks, but a correctness argument, a capability matrix against prior methods, and deployment in several IBM products and prototypes.

8 · Impact and limits: DB2, SQL Server, and InnoDB share the skeleton, while PostgreSQL's MVCC drops the undo pass entirely; against that, ARIES is very complex to implement correctly, offers no measurements, and its log became the scalability bottleneck of the many-core era.