ARIES recovery

Deep dive

How it works

Parts:

• log record — LSN, prevLSN, txn, type, pageID, redo info, undo info, undoNextLSN
• pageLSN — LSN of the last record applied to a page; makes redo idempotent
• transaction table — txn → status, lastLSN (saved in checkpoints)
• dirty page table — page → recLSN (first LSN that dirtied it since its last write)
• fuzzy checkpoint — writes both tables to the log without quiescing
• CLR — redo-only compensation record that points to the next record to undo

Log record: LSN, prevLSN (same transaction), txn, type, pageID, redo info, undo info, undoNextLSN (CLR only). Runtime tables, saved in checkpoints: transaction table (txn → status, lastLSN) and dirty page table (page → recLSN, the first LSN that dirtied it since it was last written).

log: ... [begin_ckpt] ... [end_ckpt: ATT, DPT] ... updates ... CRASH
          Analysis ─────────────────────────────────────────────►
     Redo from min(recLSN) ─────────────────────────────────────►
                              ◄───────────── Undo losers (max LSN first)

1. Analysis: start at the last checkpoint with its tables. Scan forward. Every record updates the transaction's lastLSN; commit marks it a winner; end removes it. Each update or CLR adds its page to the DPT if missing, with recLSN = LSN. At the end, losers are transactions still active and not committed.
2. Redo: from RedoLSN = min(recLSN), for each update or CLR, skip it if the page is not in the DPT, if LSN < recLSN, or if pageLSN ≥ LSN (this check needs the page read). Otherwise apply it and set pageLSN = LSN. Afterwards the database is exactly as it was at the crash.
3. Undo: put the lastLSN of each loser into a max-set. Pop the largest LSN. For an update, undo it, write a CLR with undoNextLSN = prevLSN and continue at prevLSN. For a CLR, jump to its undoNextLSN (never undo an undo). When a chain ends, write an end record.

Code

use std::collections::{BTreeSet, HashMap};

#[derive(Clone, Debug)]
pub enum Kind {
    Update { page: u32, before: i64, after: i64 },
    Clr { page: u32, after: i64, undo_next: Option<u64> }, // redo-only
    Commit,
    End,
}
#[derive(Clone, Debug)]
pub struct Rec { pub lsn: u64, pub prev: Option<u64>, pub txn: u32, pub kind: Kind }
pub struct Page { pub lsn: u64, pub val: i64 }

/// LSNs are 1-based positions in `log`. `disk` = page images found on disk after the crash.
pub fn recover(log: &mut Vec<Rec>, disk: &mut HashMap<u32, Page>) {
    // Analysis (from log start; a real system starts at the last checkpoint's tables)
    let mut att: HashMap<u32, (u64, bool)> = HashMap::new(); // txn -> (lastLSN, committed)
    let mut dpt: HashMap<u32, u64> = HashMap::new(); // page -> recLSN
    for r in log.iter() {
        match &r.kind {
            Kind::End => { att.remove(&r.txn); continue; }
            Kind::Commit => { att.insert(r.txn, (r.lsn, true)); continue; }
            Kind::Update { page, .. } | Kind::Clr { page, .. } => { dpt.entry(*page).or_insert(r.lsn); }
        }
        att.entry(r.txn).or_insert((r.lsn, false)).0 = r.lsn;
    }

    // Redo: repeat history, losers included
    let start = dpt.values().copied().min().unwrap_or(log.len() as u64 + 1);
    for r in &log[start as usize - 1..] {
        let (page, val) = match r.kind {
            Kind::Update { page, after, .. } | Kind::Clr { page, after, .. } => (page, after),
            _ => continue,
        };
        if dpt.get(&page).map_or(true, |&rec| r.lsn < rec) { continue; }
        let p = disk.entry(page).or_insert(Page { lsn: 0, val: 0 });
        if p.lsn >= r.lsn { continue; } // already on disk
        p.val = val;
        p.lsn = r.lsn;
    }

    // Undo: losers, newest record first, each step logged as a CLR
    let mut todo: BTreeSet<(u64, u32)> =
        att.iter().filter(|(_, v)| !v.1).map(|(&t, v)| (v.0, t)).collect();
    let mut last: HashMap<u32, u64> = att.iter().map(|(&t, v)| (t, v.0)).collect();
    while let Some((lsn, txn)) = todo.pop_last() {
        let r = log[lsn as usize - 1].clone();
        let next = match r.kind {
            Kind::Update { page, before, .. } => {
                let clr = log.len() as u64 + 1;
                log.push(Rec { lsn: clr, prev: Some(last[&txn]), txn,
                               kind: Kind::Clr { page, after: before, undo_next: r.prev } });
                last.insert(txn, clr);
                let p = disk.entry(page).or_insert(Page { lsn: 0, val: 0 });
                p.val = before; // WAL rule: the CLR must be durable before this page is written
                p.lsn = clr;
                r.prev
            }
            Kind::Clr { undo_next, .. } => undo_next, // skip work already undone before the crash
            _ => r.prev,
        };
        match next {
            Some(n) => { todo.insert((n, txn)); }
            None => log.push(Rec { lsn: log.len() as u64 + 1, prev: Some(last[&txn]), txn, kind: Kind::End }),
        }
    }
}

Winners that committed but have no end record need nothing. Real systems also write their end records.

Complexity and constants

• Analysis: one sequential scan from the checkpoint. Redo: one scan from min(recLSN) plus a random read for every DPT page not in cache. That read is usually the dominant cost. Undo: proportional to the losers' work.
• Recovery time scales with the checkpoint interval. A 5-minute interval at 100 MB/s of log means about 30 GB to scan: order of minutes on NVMe if the page reads are prefetched.
• Overhead in normal operation: one log record per change, an 8-byte pageLSN per page, and DPT/ATT entries in each checkpoint.

Efficiency

• Cost: runtime is one log record per change plus an 8-byte pageLSN per page; recovery is a sequential log scan plus random page reads. Bound: I/O, with redo's random page reads dominating.
• Levers:
  • frequent fuzzy checkpoints and a background writer — keeps min(recLSN) near the log head, so less log is scanned and fewer pages read — always
  • skip redo without reading the page — page not in the DPT or LSN < recLSN — large dirty-page tables
  • sort the DPT pages and prefetch with deep queues (io_uring) — turns random reads into queued reads (order of) — cold recovery on NVMe
  • CLRs with undoNextLSN — a crash during recovery never repeats undo work — long rollbacks
  • group commit — amortizes the commit fsync — many concurrent committers
• Naive → standard → state of the art:
  • force every page at commit, no-steal · random page writes on the commit path
  • ARIES with fuzzy checkpoints · one sequential log flush per commit, bounded recovery
  • instant recovery · database opens before redo finishes

Implementation notes

• Prefetch during redo: sort the DPT pages and issue the reads early (io_uring, posix_fadvise). The log tells you which pages you will need.
• Logical undo: a B-tree record may have moved to another page through a split since it was logged. Undo of index changes must be logical ("delete key k"), not physical. Structure changes (splits) run as nested top actions that are never undone once complete.
• Checkpoint: write begin_checkpoint, copy ATT and DPT without stopping work, write end_checkpoint with the copies, then store the begin LSN in a master record that is updated atomically.
• Background writer: flushing the oldest dirty pages keeps min(recLSN) close to the log head and recovery short.
• Transaction rollback at runtime uses the same undo code with CLRs. Savepoints are partial rollbacks to an LSN.

Pitfalls

• Skipping the pageLSN comparison makes redo apply changes twice (fatal for logical or delta records).
• Undoing CLRs, or writing CLRs without undoNextLSN, makes repeated crashes during recovery loop or corrupt data.
• Setting recLSN on the last change instead of the first one. Redo then starts too late and misses changes.
• Physical undo after a page split corrupts the tree.
• One long-running loser forces undo to walk far back, and the log cannot be truncated past its first record.

Variants and alternatives

In production

• Relational databases: IBM DB2 (where ARIES started), SQL Server, InnoDB (ARIES-style redo plus undo logs), Oracle (redo plus undo segments).
• Many teaching and embedded engines. No verified use outside transactional storage engines was found; the mechanic is tied to a steal/no-force buffer pool.

Implementations

ARIES lives inside database engines; no standalone library is listed.

Sources

• C. Mohan, D. Haderle, B. Lindsay, H. Pirahesh, P. Schwarz, ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging, ACM TODS, 1992. paper
• R. Ramakrishnan, J. Gehrke, Database Management Systems, 3rd ed., 2003 (crash recovery chapter).
• P. Antonopoulos et al., Constant Time Recovery in Azure SQL Database, VLDB, 2019. paper
• G. Graefe, W. Guy, C. Sauer, Instant Recovery with Write-Ahead Logging, Synthesis Lectures on Data Management, 2014. book