Logging and recovery: WAL and ARIES

We are on the second journey of the course, the write path. Last week (strict 2PL, deadlock, and MVCC) the transaction earned the right to modify a page: it took an exclusive lock or wrote a new version, and the page now sits dirty in the buffer pool. This week answers the question that journey never had to ask on a pure read: what happens when the lights go out before that dirty page reaches disk, or after it reaches disk but before the transaction commits. The layer above hands us a page about to change. The layer below (the buffer pool) is allowed to write that page to disk whenever it likes, even before commit, and is allowed to keep it in memory long after commit. Those two freedoms are the whole problem. We hand down a rule the buffer pool must obey (write the log first) and a log it can replay to fix any mess a crash leaves behind. Next week (LSM trees and columnar storage) reuses this exact write-ahead log idea in a new shape: the memtable plus WAL of a log-structured store.

Keep the running transaction in view:

BEGIN;
UPDATE account SET balance = balance - 100 WHERE id = 42;
COMMIT;

Why a crash can leave disk in any state

A transaction is one logical step built from many physical page writes. Two buffer-pool freedoms from weeks 4 and 5 decide how bad a crash can be.

Steal. The buffer pool may evict a page dirtied by an uncommitted transaction, writing it to disk to free the frame. No-steal would forbid this, but then a long transaction could pin the whole pool. So real systems steal. The consequence: at crash time, disk may hold changes from a transaction that never committed. Recovery must be able to undo them.

No-force. At commit, the buffer pool is not required to flush that transaction's dirty pages to disk. Force would make every commit a random write storm. So real systems use no-force. The consequence: at crash time, disk may be missing changes from a transaction that did commit. Recovery must be able to redo them.

Steal plus no-force is the fast combination, and it is the one ARIES targets [Mohan et al. 1992, Section 4]. The price is that both undo and redo become necessary. The naive alternative, shadow paging, sidesteps the problem by writing each new page version to a fresh location and keeping the old one as the recovery copy. It avoids undo and redo, but it scatters pages, wastes space, and perturbs every checkpoint and image copy [Mohan et al. 1992, Section 1.1]. In-place update with a log is the design that won.

Write-ahead logging and the page_LSN invariant

Every log record gets a log sequence number, the LSN, a monotonically increasing identifier. Each page on disk carries a field called the page_LSN, defined as the LSN of the log record that describes the most recent update applied to that page [Mohan et al. 1992, Section 4.2]. That one field is what lets recovery line up a page with the log. If a page's page_LSN is 30, then every logged change up to and including LSN 30 is already baked into the page, and nothing after it is. This is the bookkeeping that makes redo safe: you never reapply an effect that is already present.

The WAL protocol has two parts [Mohan et al. 1992, Section 1.1]:

1. Before a changed page is written to the durable data file, the log records describing its changes (at least the undo portions) must already be on stable storage. The buffer manager enforces this, forcing the log up to the page's page_LSN before it steals the page.
2. A transaction is not committed until its commit record, and all of its log up to that LSN, are forced to stable storage. Commit is exactly the moment the log says so.

Each transaction's records are chained backward by a PrevLSN field, so you can walk one transaction's history from its latest record to its first. Compensation records, written during undo, carry an extra field, UndoNxtLSN, which we reach below.

The three principles of ARIES

ARIES (Algorithm for Recovery and Isolation Exploiting Semantics) rests on three ideas [Mohan et al. 1992, abstract and Section 3].

1. Write-ahead logging. The log record reaches stable storage before the data page, and the commit record reaches it at commit. Already covered.
2. Repeating history during redo. On restart, before undoing anything, ARIES replays every logged update whose effect did not reach disk, for all transactions including the losers. This rebuilds the exact database state as of the crash, and only then are losers rolled back. This is the move that distinguishes ARIES from every method before it.
3. Logging changes during undo. When ARIES undoes an update, it writes that undo as a Compensation Log Record (CLR). CLRs are redo-only: they are never themselves undone. A CLR carries UndoNxtLSN, pointing at the next record of that transaction still to be undone, so rollback is bounded and can resume after a crash without redoing undo work.

The two tables recovery rebuilds

ARIES keeps two in-memory tables during normal running, writes them into checkpoint records, and rebuilds them at restart [Mohan et al. 1992, Sections 4.3, 4.4].

The state recovery tracks. Both are reconstructed by the Analysis pass.

Table	Per-entry fields	What it answers
Transaction Table	TransID, State, LastLSN, UndoNxtLSN	Which transactions were live, and where to start undoing each.
Dirty Pages Table	PageID, RecLSN	Which pages might have changes not yet on disk, and from what log point.

RecLSN is the subtle one. When a clean page is first dirtied in the buffer, its RecLSN is set to the current end-of-log LSN, the LSN of the next record to be written. RecLSN marks the earliest log point whose updates to that page might not be on disk yet. The minimum RecLSN over the whole Dirty Pages Table is RedoLSN, the point where the redo pass must begin: any change logged before that is guaranteed already on disk.

Simulator: the ARIES log replayer

Below is a small but real ARIES engine. The left panel is a log you can build: append updates and commits for two transactions, then crash at a chosen position. The right panels show the on-disk page_LSN values, the Transaction Table, and the Dirty Pages Table. Run Analysis, then Redo, then Undo, one step at a time, and watch the engine reconstruct the crash-time state and then roll back the losers, writing CLRs as it goes.

ARIES log replayer build a log, crash, then replay Analysis / Redo / Undo

Log (stable storage). The crash point is the red line.

On-disk page_LSN

Transaction Table

Dirty Pages Table

The three restart passes

On restart, ARIES makes exactly three passes over the log [Mohan et al. 1992, Section 6].

1. Analysis

Scan forward from the most recent checkpoint to the end of the log. Rebuild the Transaction Table and Dirty Pages Table. Identify the losers, the transactions that had neither committed nor reached the in-doubt (prepared) state of two-phase commit. Compute RedoLSN as the minimum RecLSN across the Dirty Pages Table. Analysis produces the worklist for the next two passes.

2. Redo

Scan forward from RedoLSN, repeating history. For each redoable record whose page is in the Dirty Pages Table, fetch the page and compare. Redo is conditional: reapply the change only if the page's page_LSN is less than the record's LSN, then set page_LSN to the record's LSN. If page_LSN already covers the record, the change is on disk and is skipped. Nothing is logged during redo, because redo only repeats history that is already logged. After redo, the database is exactly as it was the instant before the crash, losers and all.

3. Undo

Roll back every loser in reverse chronological order, in one sweep, by repeatedly taking the largest not-yet-undone LSN across the losers. For each loser update, apply the inverse and write a CLR. Undo is unconditional: it does not consult page_LSN, because repeating history already guaranteed every loser update is present. When the sweep meets a CLR, it jumps to that CLR's UndoNxtLSN, skipping work already undone. When no loser has any record left to undo, recovery is complete.

# ARIES restart, in three passes (pseudocode)
def restart(log, checkpoint):
    txn_tab, dpt = analysis(log, checkpoint)      # rebuild tables, find losers
    redo_lsn = min(e.rec_lsn for e in dpt)     # earliest possibly-lost change

    for rec in log.forward_from(redo_lsn):     # REDO: repeat history
        page = fetch(rec.page)
        if page.page_lsn < rec.lsn:               # conditional
            apply(rec, page); page.page_lsn = rec.lsn

    for rec in log.backward_over(losers):       # UNDO: roll back losers
        if rec.is_clr: continue                   # CLRs are never undone
        clr = write_clr(rec, undo_nxt=rec.prev_lsn)
        apply_inverse(rec)                       # unconditional

Paper viva: ARIES (Mohan et al., 1992)

This is a paper week. The examiner will press on the parts of ARIES that are easy to half-remember. Answer out loud before opening each model answer.

Model answer

WAL has two clauses. First, before a dirty page is written to the durable database, the log records describing its changes, at least the undo portions, must already be on stable storage; the buffer manager enforces this, sometimes forcing the log up to the page's page_LSN before stealing the page. Second, a transaction is not committed until its commit record and all earlier log up to that LSN are forced to stable storage [Mohan et al. 1992, Section 1.1]. Steal lets an uncommitted transaction's dirty page reach disk before commit, so a crash can leave uncommitted changes on disk, which is why undo capability is required. No-force lets a committed transaction's dirty pages stay in the buffer, so a crash can leave committed changes missing from disk, which is why redo capability is required. The first WAL clause makes undo possible (the old value is logged before the page moves); the second makes durability real (commit is the moment the log says so).

Model answer

Repeating history means the redo pass reapplies every logged update whose effect did not reach disk, for all transactions including the losers, before any undo runs. This reestablishes the exact database state as of the failure [Mohan et al. 1992, Section 3]. Redoing the losers looks wasteful, since they are about to be undone, but it guarantees a precise, fully known state at the start of undo. Earlier WAL methods that tried to skip loser redo fell into the bugs ARIES lists in Section 2: undoing an update that was never actually present on the page, undoing the same logged action more than once, or undoing a committed update that had already reached disk and then redoing it. By making every loser update provably present before undo, ARIES makes undo unconditional and sound, and it is what allows fine-granularity locking together with operation logging, where you must never redo a present effect or undo an absent one.

Model answer

A CLR is the log record written when ARIES undoes an update; it describes the undo that was performed [Mohan et al. 1992, Section 3]. It is redo-only because it is never itself undone: once undo work is logged it is permanent, and rollback proceeds forward through the remaining records to undo. Each CLR carries UndoNxtLSN, pointing to the predecessor of the record it just compensated, that is, the next record of that transaction still to be undone. So the UndoNxtLSN of the most recently written CLR records exactly how far rollback has progressed. If a system failure or a nested rollback interrupts undo, recovery resumes at that UndoNxtLSN and skips every record already compensated, so no record is undone twice and no extra CLRs are generated for already-undone work. That is what bounds logging during rollback, in contrast to IMS, which could undo the same non-CLR record multiple times, generating unbounded log. Because the CLR records what the undo actually did, the undo action also need not be the physical inverse of the original on the same page, which is what enables logical undo and the high concurrency of record-level operations.

Check yourself