ARIES recovery simulator

Type the log from your exercise, one record per line, starting each with its LSN. The system crashes after the last line. Press "Crash and recover" and switch between the three passes: analysis shows the transaction and dirty page tables it rebuilds, redo lists every record from the redo point with the reason it is redone or skipped, and undo shows the order of undo and the compensation records it writes, numbered after the last LSN in steps of 10.

• A checkpoint line stands for a fuzzy checkpoint; its tables are taken from the log as it was at that point, including any flushes before it.
• A flush line says the buffer manager wrote that page to disk. It is not in the log, so analysis cannot see it; redo notices it through the page's pageLSN.
• "Copy answer" gives all the tables as text; "Copy link" saves the log in the address.

A database changes pages in memory and writes them to disk later. With write-ahead logging (WAL), every change is first described in a log record, and the log is written to disk before the changed page is; a transaction counts as committed once its commit record is on disk. After a crash the log is the truth: it says what was committed and what each page should contain.

ARIES is the recovery method that made this precise for systems that may write uncommitted pages to disk (steal) and need not write committed pages at commit (no-force). Both choices are good for performance and both leave the disk wrong after a crash, so recovery has to redo committed work that never reached disk and undo uncommitted work that did.

• Every log record has a log sequence number (LSN), increasing through the log, and a prevLSN linking it to the same transaction's previous record.
• Every page stores its pageLSN, the LSN of the latest change applied to it, so recovery can tell whether a change is already on disk.
• The transaction table lists running transactions with their lastLSN, where their undo would start.
• The dirty page table lists pages changed in memory but not yet written, with their recLSN, the first change since the page was last written.

A fuzzy checkpoint writes both tables to the log without stopping the system or flushing pages, which limits how far back recovery has to read.

Analysis starts from the last checkpoint's tables and reads forward to the end of the log. An update or CLR puts its transaction in the transaction table with that lastLSN and, if its page is not yet in the dirty page table, adds the page with this record as its recLSN. A commit marks the transaction committed; an end record removes it. At the end, committed transactions without an end record are given one, and every transaction still marked running is a loser that must be rolled back. Because flushes are not logged, the dirty page table may include pages that were in fact written; that is safe, and redo sorts it out.

Redo starts at the smallest recLSN in the dirty page table, the oldest change that might not be on disk, and reapplies every update and CLR from there, for winners and losers alike, so that the database returns to exactly its state at the crash. A record is skipped when:

1. its page is not in the dirty page table, so the change reached disk before the checkpoint or was never needed;
2. its page's recLSN is later than the record, so the page was written after this change and dirtied again later;
3. the page on disk has a pageLSN at least as large as the record's LSN, so the change is already there. Only this check needs the page itself to be read.

Undo collects the lastLSN of every loser and repeatedly processes the largest LSN, so all losers are rolled back together in reverse log order. For an update, it restores the old value and writes a compensation log record (CLR) whose undoNextLSN is the update's prevLSN, then continues from there. For a CLR found in the log, from a rollback that was in progress at the crash, it does nothing but jump to the CLR's undoNextLSN, so work already undone is never undone again. When a transaction has nothing left to undo, an end record is written.

Recovery itself can crash. Redo is safe to repeat because the pageLSN check skips changes already applied, and undo's progress is recorded in the CLRs, which the next redo replays and the next undo skips over. The model on this page was checked this way: on 2,000 random histories under strict two-phase locking, with random flushes, checkpoints and rollbacks, recovery left every page holding the value of its last committed update in 2,000 of them. In the 1,832 histories where undo wrote more than one record, a second crash part-way through undo followed by a second recovery gave the correct pages every time. In 1,505 histories redo skipped at least one record.

C. Mohan and colleagues at IBM published ARIES in ACM Transactions on Database Systems in 1992, and it shaped the recovery of IBM's DB2 and many later systems. Microsoft's documentation describes SQL Server's recovery without its newer Accelerated Database Recovery as following the ARIES model, with the same analysis, redo and undo phases. PostgreSQL also writes a WAL and replays it forward after a crash, but because its storage keeps multiple versions of rows, the changes of transactions that never committed are simply left invisible, and it has no undo pass.