Introduction

Picture a bank transfer: $500 moves from account A to account B. The database subtracts from A, then adds to B — two separate writes. If power dies between them, A is short $500 and B never received it. The money vanished.

That is the durability and atomicity problem. A transaction must either complete in full or leave no trace at all. The database needs a way to know, after any restart, which transactions finished and which were still in flight.

The answer that almost every production database uses today — PostgreSQL, MySQL/InnoDB, SQL Server, DB2 — is ARIES: Algorithms for Recovery and Isolation Exploiting Semantics, published by C. Mohan and colleagues at IBM Research in 1992. It solved crash recovery so thoroughly that its design has changed little in three decades.

ARIES rests on one non-negotiable rule and three recovery phases. The rule is Write-Ahead Logging (WAL): before any data page is written to disk, its log record must reach disk first. The phases are Analysis, Redo, and Undo — and together they restore the database to the exact state it would have been in if the crash had never happened.

Try It

The simulator below maintains a tiny write-ahead log and two account balances. Run a transfer, crash the database at any moment, then let ARIES recover it.

<!-- Accounts panel + WAL panel + status + controls -->
<div class="panel">
  <div class="section-title">Accounts</div>
  <div class="accounts" id="accounts"></div>
</div>
<div class="panel">
  <div class="section-title">Write-Ahead Log (WAL)</div>
  <div class="log-box" id="log-box">
    <div class="log-empty" id="log-empty">(empty — no transactions yet)</div>
  </div>
</div>
<div class="panel status-panel">
  <div id="phase-label" class="phase-label"></div>
  <div id="status" class="status-msg"></div>
</div>
<div class="btns">
  <button id="btn-transfer" type="button">Transfer $100 A→B</button>
  <button id="btn-crash" type="button" class="danger">Crash now!</button>
  <button id="btn-recover" type="button" class="recover" disabled>Recover (ARIES)</button>
  <button id="btn-reset" type="button" class="ghost">Reset</button>
</div>

/* ARIES crash-recovery demo styles */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 14px; }
.panel { background: #f4f7fa; border: 1px solid #d0dae5; border-radius: 8px; padding: .6rem .8rem; margin-bottom: .5rem; }
.section-title { font-size: .72rem; font-weight: 700; text-transform: uppercase; letter-spacing: .06em; color: #6b8099; margin-bottom: .4rem; }
.accounts { display: flex; gap: .8rem; }
.account { background: #fff; border: 1px solid #c0cdd8; border-radius: 6px; padding: .4rem .7rem; min-width: 90px; }
.account .acc-name { font-size: .72rem; color: #6b8099; }
.account .acc-bal { font-size: 1.3rem; font-weight: 700; color: #1d3557; }
.account.dirty { border-color: #e07b00; background: #fff8ee; }
.account.dirty .acc-bal { color: #e07b00; }
.log-box { font-family: ui-monospace, monospace; font-size: .8rem; max-height: 130px; overflow-y: auto; display: flex; flex-direction: column; gap: 2px; }
.log-empty { color: #aaa; font-style: italic; padding: .2rem 0; }
.log-row { display: flex; gap: .4rem; align-items: baseline; padding: 2px 4px; border-radius: 4px; }
.log-row.begin { color: #1d3557; }
.log-row.write { color: #0a7d33; }
.log-row.commit { color: #6b00cc; font-weight: 700; }
.log-row.clr { color: #e07b00; }
.log-row.undo-entry { color: #c92f3c; }
.log-row.highlighted { background: #fff3cd; }
.lsn { color: #aaa; min-width: 2ch; text-align: right; }
.status-panel { min-height: 2.6rem; display: flex; flex-direction: column; gap: .2rem; }
.phase-label { font-weight: 700; font-size: .8rem; color: #1d3557; min-height: 1em; }
.status-msg { font-size: .85rem; min-height: 1.2em; }
.status-msg.ok { color: #0a7d33; }
.status-msg.bad { color: #c92f3c; }
.status-msg.info { color: #1d3557; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 13px system-ui, sans-serif; padding: .4rem .8rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.danger { background: #c92f3c; border-color: #c92f3c; }
button.recover { background: #0a7d33; border-color: #0a7d33; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .4; cursor: default; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// ARIES (Algorithms for Recovery and Isolation Exploiting Semantics, Mohan 1992)
// WAL rule: log record must reach disk BEFORE the data page.

// In-memory database state
let accounts = { A: 500, B: 300 };
let wal = [];     // write-ahead log records
let nextLsn = 1;
let crashed = false;
let txnActive = false;
let txnId = 0;

// last flushed state (simulates what's on disk before crash)
let dirtyOnDisk = { A: 500, B: 300 };

const elAccounts = document.getElementById('accounts');
const elLogBox   = document.getElementById('log-box');
const elLogEmpty = document.getElementById('log-empty');
const elStatus   = document.getElementById('status');
const elPhase    = document.getElementById('phase-label');
const btnTransfer = document.getElementById('btn-transfer');
const btnCrash    = document.getElementById('btn-crash');
const btnRecover  = document.getElementById('btn-recover');
const btnReset    = document.getElementById('btn-reset');

function renderAccounts(vals, dirty) {
  elAccounts.innerHTML = '';
  for (const [name, bal] of Object.entries(vals)) {
    const d = document.createElement('div');
    d.className = 'account' + (dirty && dirty.has(name) ? ' dirty' : '');
    d.innerHTML = `<div class="acc-name">${name}</div><div class="acc-bal">${bal}</div>`;
    elAccounts.appendChild(d);
  }
}

function renderLog(highlight) {
  if (wal.length === 0) {
    elLogEmpty.style.display = '';
    while (elLogBox.firstChild !== elLogEmpty) elLogBox.removeChild(elLogBox.firstChild);
    return;
  }
  elLogEmpty.style.display = 'none';
  while (elLogBox.firstChild !== elLogEmpty) elLogBox.removeChild(elLogBox.firstChild);
  for (const rec of wal) {
    const row = document.createElement('div');
    const hi = highlight && highlight.has(rec.lsn) ? ' highlighted' : '';
    row.className = 'log-row ' + rec.type + hi;
    row.innerHTML = `<span class="lsn">${rec.lsn}</span><span>${rec.text}</span>`;
    elLogBox.insertBefore(row, elLogEmpty);
  }
  elLogBox.scrollTop = elLogBox.scrollHeight;
}

function setStatus(msg, cls) {
  elStatus.textContent = msg;
  elStatus.className = 'status-msg ' + (cls || '');
}
function setPhase(label) { elPhase.textContent = label; }

function appendLog(type, text, extra) {
  const rec = { lsn: nextLsn++, type, text, ...extra };
  wal.push(rec);
  return rec;
}

// Step 1 of 2 in the transfer transaction — debit A
function doTransfer() {
  if (crashed) return;
  if (txnActive) { setStatus('A transaction is already in progress.', 'bad'); return; }
  txnActive = true;
  txnId++;
  const amount = 100;
  const tid = txnId;

  // Log the transaction start
  appendLog('begin', i18nFmt('[T%tid%] BEGIN', { tid }), { tid });

  // WAL first write: debit account A before touching the page
  const oldA = accounts.A;
  const newA = accounts.A - amount;
  appendLog('write', i18nFmt('[T%tid%] WRITE A: %oldA% → %newA%', { tid, oldA, newA }), { tid, page: 'A', before: oldA, after: newA });
  accounts.A = newA;

  renderAccounts(accounts, new Set(['A']));
  renderLog();
  setStatus('Debited A. Crash now to simulate a mid-transaction failure, or commit to finish.', 'info');
  setPhase('In transaction');
  btnCrash.disabled = false;
}

// Step 2 of 2 — credit B and commit
function commitTransfer() {
  if (!txnActive || crashed) return;
  const tid = txnId;
  const amount = 100;

  // WAL second write: credit account B
  const oldB = accounts.B;
  const newB = accounts.B + amount;
  appendLog('write', i18nFmt('[T%tid%] WRITE B: %oldB% → %newB%', { tid, oldB, newB }), { tid, page: 'B', before: oldB, after: newB });
  accounts.B = newB;

  // WAL commit record — durability point
  appendLog('commit', i18nFmt('[T%tid%] COMMIT', { tid }), { tid });

  // Simulate flush of dirty pages to disk (simplified)
  dirtyOnDisk = { ...accounts };
  txnActive = false;

  renderAccounts(accounts, null);
  renderLog();
  setStatus('Transaction committed. Both writes are durable.', 'ok');
  setPhase('Committed');
  btnCrash.disabled = true;
}

let transferStep = 0;
btnTransfer.addEventListener('click', () => {
  if (crashed) return;
  if (!txnActive) {
    transferStep = 0;
    doTransfer();
    btnTransfer.textContent = 'Commit transfer';
  } else {
    commitTransfer();
    btnTransfer.textContent = 'Transfer $100 A→B';
    transferStep = 0;
  }
});

// Simulate a crash — lose in-memory state, keep only what's on disk
btnCrash.addEventListener('click', () => {
  if (!txnActive || crashed) return;
  crashed = true;
  // Restore from disk (only pages flushed before crash survive)
  accounts = { ...dirtyOnDisk };
  txnActive = false;
  renderAccounts(accounts, null);
  renderLog();
  setStatus('Crash! In-memory state lost. WAL on disk is intact.', 'bad');
  setPhase('Crashed');
  btnTransfer.disabled = true;
  btnCrash.disabled = true;
  btnRecover.disabled = false;
  btnTransfer.textContent = 'Transfer $100 A→B';
});

// ARIES three-phase recovery
async function doRecover() {
  btnRecover.disabled = true;
  const delay = ms => new Promise(r => setTimeout(r, ms));

  // Phase 1 — Analysis
  setPhase('ARIES — Phase 1: Analysis');
  setStatus('Phase 1 — Analysis: scanning the log…', 'info');
  await delay(700);

  const activeTxns = new Set();
  const committedTxns = new Set();
  for (const rec of wal) {
    if (rec.type === 'begin')  activeTxns.add(rec.tid);
    if (rec.type === 'commit') { committedTxns.add(rec.tid); activeTxns.delete(rec.tid); }
  }
  const losers = [...activeTxns];
  setStatus(i18nFmt('Analysis complete: %losers% loser(s), %committed% committed.', { losers: losers.length, committed: committedTxns.size }), 'info');
  await delay(900);

  // Phase 2 — Redo (replay all logged writes forward)
  setPhase('ARIES — Phase 2: Redo');
  setStatus('Phase 2 — Redo: replaying all logged writes…', 'info');
  await delay(700);

  const recovered = { ...dirtyOnDisk };
  const redoLsns = new Set();
  for (const rec of wal) {
    if (rec.type === 'write' || rec.type === 'clr') {
      recovered[rec.page] = rec.after;
      redoLsns.add(rec.lsn);
    }
  }
  renderLog(redoLsns);
  setStatus('Redo complete. All committed writes are applied.', 'info');
  await delay(900);

  // Phase 3 — Undo (reverse writes of uncommitted transactions)
  setPhase('ARIES — Phase 3: Undo');
  setStatus('Phase 3 — Undo: reversing uncommitted writes…', 'info');
  await delay(700);

  const undoLsns = new Set();
  for (let i = wal.length - 1; i >= 0; i--) {
    const rec = wal[i];
    if ((rec.type === 'write') && losers.includes(rec.tid)) {
      recovered[rec.page] = rec.before;
      const clrLsn = nextLsn++;
      wal.push({ lsn: clrLsn, type: 'clr', text: i18nFmt('CLR: undo LSN %lsn% — %page% restored to %val%', { lsn: rec.lsn, page: rec.page, val: rec.before }), page: rec.page, after: rec.before });
      undoLsns.add(clrLsn);
    }
  }
  accounts = { ...recovered };
  dirtyOnDisk = { ...recovered };
  crashed = false;
  renderAccounts(accounts, null);
  renderLog(undoLsns);
  setStatus('Recovery complete. Database is consistent.', 'ok');
  setPhase('Recovery complete');
  btnTransfer.disabled = false;
  btnTransfer.textContent = 'Transfer $100 A→B';
}

btnRecover.addEventListener('click', doRecover);

btnReset.addEventListener('click', () => {
  accounts = { A: 500, B: 300 };
  dirtyOnDisk = { A: 500, B: 300 };
  wal = [];
  nextLsn = 1;
  crashed = false;
  txnActive = false;
  txnId = 0;
  transferStep = 0;
  renderAccounts(accounts, null);
  renderLog();
  setStatus('', '');
  setPhase('');
  btnTransfer.disabled = false;
  btnTransfer.textContent = 'Transfer $100 A→B';
  btnCrash.disabled = true;
  btnRecover.disabled = true;
});

// Initial render
renderAccounts(accounts, null);
renderLog();
btnCrash.disabled = true;
btnRecover.disabled = true;
setStatus('Click "Transfer $100 A→B" to start a transaction.', 'info');
Result
Console

Notice the three phases. Analysis scans the log forward to decide which transactions were committed and which were still active at crash time. Redo replays every logged write from the oldest dirty page forward — even operations that already reached disk — ensuring nothing committed is lost. Undo then walks the log backward and reverses every write from a transaction that never committed, restoring the database as if those operations never happened.

The Real Complexity

The deceptively simple rule — "log before write" — hides a careful design with moving parts that must interact correctly under concurrency.

Log Sequence Numbers (LSNs). Every log record gets a monotonically increasing LSN. Each data page stores the LSN of the last operation that modified it (pageLSN). During Redo, ARIES compares the log record's LSN with pageLSN: if pageLSN >= recLSN, the page already has that update, so the redo is skipped. This makes Redo idempotent — running it twice produces the same result.

The dirty-page table and the transaction table. Analysis builds two data structures in a single forward pass over the log. The dirty-page table records each page that was modified but may not have been flushed to disk, along with the earliest LSN that must be redone for it (recLSN). The transaction table records which transactions were active at the checkpoint and whether they committed or are still in flight (loser transactions). These two tables define the exact window of log that Redo and Undo must cover.

Redo starts at the minimum recLSN, not at the crash point, and replays forward. Undo walks backward through the log using prevLSN pointers embedded in each record, reversing only the losers. Each undo step writes a Compensation Log Record (CLR) so that if a crash happens again during recovery, the undo is not repeated.

Checkpoints bound recovery time. ARIES uses fuzzy checkpoints: the engine writes a checkpoint log record containing the current dirty-page table and transaction table without stopping ongoing work. The next Analysis pass only needs to start from the most recent checkpoint, limiting the log that must be re-examined.

The result is a protocol proven correct for fine-grained locking, partial rollbacks, and savepoints — the full complexity of a real OLTP workload. ARIES is not the simplest possible recovery algorithm, but it is the one that scales. See also P vs NP for why some related verification problems are inherently hard to speed up.

Where It Matters

ARIES or close variants of it show up wherever durability is non-negotiable:

  • Relational databases: PostgreSQL calls its log the WAL; MySQL/InnoDB has the redo log and undo log; SQL Server uses a nearly identical LSN-based scheme. All implement the ARIES three-phase pattern.
  • Distributed transactions: in systems like Google Spanner or CockroachDB, each replica maintains its own WAL; the ARIES ideas of LSNs and idempotent redo extend naturally to distributed consensus.
  • File systems: journaling file systems (ext4, NTFS, APFS) borrow write-ahead logging to protect metadata — a crash during a directory rename does not leave the file system in an inconsistent state.
  • Key-value stores: RocksDB, LevelDB, and similar LSM-tree engines use a write-ahead log before data reaches the immutable sorted tables on disk.
  • Flash storage: modern SSDs maintain an internal log to protect the flash translation layer from power-loss corruption — the same principle, applied in silicon.

Understanding ARIES means understanding why halting-problem-style reasoning about infinite execution paths does not apply: recovery is finite precisely because the WAL captures the complete history of every change.

Conclusion

ARIES solved a problem that sounds deceptively simple — "make sure the database is consistent after a crash" — by recognising that the hard part is not handling any single failure, but handling arbitrary failures at arbitrary moments, including failures that happen during recovery itself.

Write-ahead logging pins down history before it can be forgotten. The Analysis phase reconstructs the exact state of the world at crash time. Redo replays history idempotently. Undo erases the traces of transactions that never finished, writing CLRs so the erasure itself survives a second crash.

The next time your database restarts after an unexpected shutdown and your data is exactly where you left it, that is ARIES — three decades old, still running under nearly every database engine that claims to be reliable, and still the clearest proof that the right abstraction, engineered carefully, outlasts any particular piece of hardware.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/aries-recovery/Content licensed under CC BY-NC 4.0.