ARIES Crash Recovery

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.

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.

<!-- {{c_html_comment}} -->
<div class="panel">
  <div class="section-title">{{label_accounts}}</div>
  <div class="accounts" id="accounts"></div>
</div>
<div class="panel">
  <div class="section-title">{{label_wal}}</div>
  <div class="log-box" id="log-box">
    <div class="log-empty" id="log-empty">{{log_empty}}</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">{{btn_transfer}}</button>
  <button id="btn-crash" type="button" class="danger">{{btn_crash}}</button>
  <button id="btn-recover" type="button" class="recover" disabled>{{btn_recover}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

/* {{c_css_comment}} */
* { 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; }

// Code not found

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 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.

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.

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.