Write-Ahead Logging and ARIES Recovery

Why a log

A database keeps its data in fixed-size pages on disk and works on copies of them in a buffer pool in memory. A transaction may change a few rows on pages scattered all over the disk. Writing those pages at every commit would mean random writes, and a crash in the middle of them would leave some written and some not. Instead every change is first described in a log: a file that is only ever appended to, so writing it is one sequential write. Once the log is on disk the change is durable, and the pages can go to disk later, whenever it is convenient. After a crash the log says what to redo (committed changes that never reached the data file) and what to undo (uncommitted changes that did).

The page runs a tiny engine: six items on three pages (P1 = A, B; P2 = C, D; P3 = E, F), a buffer pool with one frame per page, a log whose LSNs (log sequence numbers) go up by 10, and three transactions T1, T2, T3. The top half is memory and is lost in a crash; the bottom half is disk and survives. Try it: Update, Commit, Flush Page, Crash, Recover.

Memory holds the buffer pool with dirty page P1 (A = 10, pageLSN 10) and an empty log buffer; disk holds the data file with the old P1 (A = 1) and the stable log with records 10 (UPD T1 A 1→10) and 20 (COMMIT T1) up to flushedLSN 20. The log goes to disk first; the page may follow later. — T1 is committed because its COMMIT record is on disk, even though its page is not: after a crash the log can redo A = 10.

How to read the canvas. A page frame is grey when the page is not in memory, orange when it is dirty and white when it is clean. An item is yellow when it holds an uncommitted value in memory and red when an uncommitted value reached the data file on disk. The LOG has one cell per record: LSN, kind and transaction, with the fields (or prev / next pointers) underneath. Cell colour = transaction (T1 blue, T2 green, T3 pink, checkpoint grey); purple text = a CLR, whose next is its undoNextLSN; a red border marks a loser. Records left of the blue flushedLSN bar are on disk (the stable log); a white cell right of it is still in the log buffer in memory and is lost in a crash.

Steal / no-steal, force / no-force

	force (write pages at commit)	no-force (pages later)
no-steal (uncommitted pages stay in memory)	no redo, no undo; slow commits, memory must hold every running transaction's pages	redo only
steal (uncommitted pages may be written)	undo only	redo and undo: fastest, most flexible

Steal lets the buffer pool write any page to free a frame, even one that holds a change of a transaction that has not committed. No-force lets a transaction commit without writing its pages. Real engines (InnoDB, PostgreSQL, SQL Server, Db2, Oracle) choose steal + no-force, and pay for it with a recovery that must both redo and undo. In the page, Flush Page stands for the page cleaner or an eviction; Demo 2 steals T2's uncommitted C = 30.

The two WAL rules

Write-ahead: a dirty page may be written to disk only after the log is on disk up to the page's pageLSN. Then the before-image of every change on that page can be found in the log, so an uncommitted change that was stolen can be undone.
Commit = COMMIT record on disk: a transaction is committed when its COMMIT record is flushed, and only then may the client be told so. Its data pages may stay dirty (no-force), because the log can redo them.

Both rules can be switched off with the checkboxes. Demo 6 writes T3's page before its log record: after the crash B = 20 is on disk, and there is no log record that could undo it. Demo 7 acknowledges T1's commit without flushing: after the crash A = 1, a committed and acknowledged transaction has vanished. The verdict line compares the data after recovery with the committed data and names the wrong items.

LSNs and what each is for

LSN of a record: its position in the log. Real engines use the byte offset; the page counts records in tens.
prevLSN in every record of a transaction: the transaction's previous record, so its records form a backward chain for undo.
pageLSN on every page: the LSN of the last change applied to it. It travels to disk with the page, so recovery can tell whether the page on disk already has a change (pageLSN ≥ LSN).
recLSN in the dirty page table: the first change since the page was last clean. Nothing before it can be missing from the page on disk.
flushedLSN: how far the log is on disk (the blue bar on the log strip). Rule (a) compares it with pageLSN.

A commit costs an fsync of the log. Under load, many transactions commit at almost the same time, and one flush covers all of their COMMIT records: group commit. That is why a busy database can commit far more transactions per second than its disk can do fsyncs.

Checkpoints

Without a checkpoint, recovery must read the log from its very first record. A sharp checkpoint would stop all transactions and write every dirty page, which stalls the database. ARIES uses a fuzzy checkpoint: it writes BEGIN_CKPT, then END_CKPT carrying a copy of the transaction table (running transactions and their lastLSN) and of the dirty page table (dirty pages and their recLSN), flushes the log, and stores the BEGIN_CKPT's LSN in the master record. No page is written. Recovery then starts its analysis at the checkpoint, and the log before min(recLSN of the DPT, first LSN of the oldest running transaction) is no longer needed and can be truncated or recycled. A page cleaner that keeps writing old dirty pages in the background moves that point forward. Demo 5 runs the same eight actions twice, without and with a checkpoint in the middle, and compares how many records the two recoveries read.

ARIES restart: analysis, redo, undo

Analysis reads the master record, loads the ATT and DPT from END_CKPT and scans forward to the end of the log: an UPD or CLR sets its transaction's lastLSN and adds its page to the DPT (recLSN = that LSN) if it is not there; COMMIT marks the transaction committing; END removes it. At the end, committing transactions get their END, and the ones still running or aborting are the losers. redoLSN = min(recLSN).

Redo reads forward from redoLSN and, for every UPD and CLR, skips it if its page is not in the DPT, if LSN < recLSN, or (after reading the page) if pageLSN ≥ LSN; otherwise it applies it and sets pageLSN. It redoes the losers' changes too: this is repeating history. After redo the buffer pool is exactly as it was at the crash, so undo can work the same way as a normal rollback. It also means the log records can be physiological (physical to a page, logical inside it: "insert this row in slot 7 of page 12"), because each is replayed on exactly the page state it was written against.

Undo puts the lastLSN of every loser in ToUndo and repeatedly takes the largest: an UPD is undone by applying its before-value and writing a CLR (compensation log record); a CLR is never undone, undo jumps to its undoNextLSN; when a transaction has nothing left, END. Taking the largest LSN first means all losers are undone in a single backward pass over the log.

Demo 3, the classic run: T1 updates A and E and commits, T2 updates C, D and F (C is stolen by a page flush), T3 updates B (stolen too), with a checkpoint after the first two updates; the crash loses record 100 (T2's F = 60) with the log buffer. Analysis from the checkpoint at 30 finds the losers T2 (lastLSN 60) and T3 (90) and redoLSN 10. Redo applies 50 and 60 and skips 10, 20 and 90, whose pages on disk already have them. Undo writes CLRs 100 (B ← 2), 120 (D ← 4) and 130 (C ← 3) with ENDs 110 and 140. The result: A = 10 and E = 50 from T1, and nothing from T2 or T3.

The Demo 3 log from LSN 10 to 90, with record 100 lost in the crash. Analysis scans forward from the checkpoint at 30 and finds losers T2 and T3; redo scans forward from 10, applying 50 and 60 and skipping 10, 20 and 90; undo goes backwards over 90, 60 and 20 and appends CLRs 100 (B ← 2), 120 (D ← 4), 130 (C ← 3) and ENDs 110 and 140. — ARIES restart: analysis finds the losers, redo repeats history forward, undo rolls the losers back in one backward pass, logging a CLR for every change.

CLRs make recovery restartable

A crash can hit during recovery too. Redo is safe to repeat by itself, because of the pageLSN test. Undo is made safe by CLRs: each CLR records what was restored and, in undoNextLSN, the prevLSN of the record it undid, which is where undo must continue. A second recovery redoes the CLRs like any other record (repeating history), and when undo meets a CLR at the end of a loser's chain, it jumps straight to its undoNextLSN. So a change is never undone twice, and an undo is never undone. Demo 4 crashes after the second CLR (120, which undid record 60); the second recovery follows 120 → 20 and never touches 60 again. (The page flushes the log buffer when it crashes during recovery so that the CLRs written so far survive; real ARIES does not force CLRs, and losing them would just be the same as crashing before them.)

A rollback during normal operation uses the same code: Abort writes an ABORT record, a CLR per update and an END. Demo 8 aborts T2 and then crashes: the transaction has an END, so it is not a loser, and redo simply repeats its updates and its CLRs.

Torn pages

A page is 8 or 16 KB, the disk writes 4 KB or 512 bytes atomically, so a crash can leave a page half old and half new. The pageLSN test cannot help then: the page is garbage. InnoDB writes each page first to the doublewrite buffer, a separate area, and only then to its place; after a crash a torn page is copied back from there. PostgreSQL writes a full-page image into the WAL the first time a page is changed after each checkpoint (full_page_writes); redo starts from that image. The page's log records are logical per item and the page never tears.

Real engines

InnoDB is close to ARIES: a redo log of physiological records with a checkpoint LSN, plus undo logs in undo tablespaces. The undo records hold the before-images; they are themselves protected by redo. After redo, transactions that were active are rolled back from the undo logs (in the background, while the server already accepts connections). See How MySQL Runs a Query.
PostgreSQL has a redo-only WAL and no undo phase. An update never overwrites: it writes a new tuple version, and whether a version counts depends on its transaction's status in pg_xact. A transaction with no COMMIT record at the crash is simply treated as aborted and its versions are invisible; VACUUM removes them later. Recovery starts at the last checkpoint's REDO point. See How PostgreSQL Runs a Query and MVCC and Isolation Levels.
SQLite has two modes. The classic rollback journal copies the original pages to a journal before changing the database file in place (undo logging, force at commit); the WAL mode appends new pages to a -wal file and copies them back at a checkpoint (redo logging), which lets readers run while a writer writes.

What the page leaves out

LSNs count records in tens instead of byte offsets; one frame per page and no eviction policy (Flush Page stands for the page cleaner or an eviction).
Records are logical per item (B 2→20), not physiological per slot; no full-page images or doublewrite, so pages never tear.
Locking is reduced to "refuse a write to an item another running transaction wrote": no waiting, no deadlocks.
END_CKPT follows BEGIN_CKPT immediately; the fuzziness is only that dirty pages are not flushed. The END of a committed transaction is written right after its COMMIT.
A crash during recovery flushes the log buffer first; T3's log cells are pink rather than purple, so that purple can mean CLR.
Nested top actions, media recovery from a backup, log archiving and point-in-time recovery, parallel redo, logical (row-based) versus physical log records, and new transactions during undo.

See also LSM tree vs B-tree (the memtable's WAL) and Database replication (shipping the same log to replicas).