1 The durability problem
Imagine you're doing homework on a whiteboard because it's quick to write on. Every now and then you copy the finished bits into your notebook, because the notebook is what you keep forever — the whiteboard gets wiped clean every night. Now: what if the lights go out while you're half-way through copying? Did your work survive? A database has the exact same problem. It does fast work on a "whiteboard" in memory, and slowly copies it to a "notebook" on disk. A crash can strike at the worst possible moment — and the database still has to come back perfectly correct.
Back in Session 12 we met the ACID properties that a transaction must guarantee. Two of those letters are the whole reason this session exists:
- Atomicity — a transaction is all-or-nothing. Either every change it makes happens, or none of them do. A crash must never leave us with "half a transaction" (money debited from one account but never credited to the other).
- Durability — once a transaction is reported as committed, its changes survive forever, even if the machine loses power one millisecond later.
The job of the recovery manager — the component we study this whole session — is to guarantee Atomicity and Durability even in the face of crashes.
Two places your data can live
To see the problem clearly, you must understand the two layers of storage a database juggles. This is the single most important picture in the whole session.
The buffer pool is a chunk of main memory (RAM) where the database keeps copies of pages — fixed-size blocks (often 4 KB or 8 KB) of the data file. When a transaction reads or writes a row, it actually reads/writes the in-memory copy in the buffer pool, because RAM is roughly a hundred thousand times faster than a disk seek. We covered the buffer pool's mechanics in Session 3; here we care about one fact:
RAM is volatile — when the power dies, everything in the buffer pool vanishes instantly. Disk is non-volatile — it survives. So the eternal question is: at the moment of the crash, which changes had reached disk, and which were still only in RAM? Recovery is entirely about answering that question and fixing up the difference.
Dirty pages
When a transaction modifies a page in the buffer pool but that change hasn't yet been written back to disk, we call that page dirty. A dirty page is dangerous: the new data exists only in volatile memory. If we crash now, that change is gone unless we did something clever beforehand (we did — it's called logging, Topic 2).
Eventually the database flushes dirty pages to disk (writes them out), making them "clean" again. But when it is allowed to flush, and when it is forced to flush, is governed by two policy decisions.
The two policy knobs: STEAL and FORCE
These two policies define the relationship between committing a transaction and writing its pages to disk. They sound abstract, so we'll pin each one down precisely.
| Policy | The question it answers | The two choices |
|---|---|---|
| STEAL vs NO-STEAL | Can a dirty page from an uncommitted transaction be written to disk? | STEAL = yes, the buffer manager may "steal" the frame and flush an uncommitted page anytime it needs the memory. NO-STEAL = no, uncommitted changes are pinned in RAM until commit. |
| FORCE vs NO-FORCE | Must all a transaction's dirty pages be on disk before we report "committed"? | FORCE = yes, flush everything at commit time. NO-FORCE = no, commit can return while the pages are still only in RAM. |
Each choice creates a problem that recovery must solve:
- STEAL means an uncommitted change might already be sitting on disk when we crash. If that transaction never commits (it has to be aborted), we must be able to UNDO it — reach onto disk and erase a change that should never have been permanent.
- NO-FORCE means a committed change might not have reached disk yet when we crash. To honour Durability, we must be able to REDO it — re-apply a committed change that got lost in the wiped buffer pool.
STEAL and NO-FORCE are the hardest pair to recover from (they require both UNDO and REDO), but they give the best runtime performance: the buffer manager is free to flush whenever convenient, and commits are fast because they don't wait for slow random disk writes. So virtually every serious database — PostgreSQL, MySQL/InnoDB, Oracle, SQL Server — uses STEAL + NO-FORCE and pays for it with a smart logging-and-recovery scheme. That scheme is the rest of this session.
Transaction T1 transfers $100 from account A to account B:
-- both rows currently live as pages in the buffer pool UPDATE accounts SET balance = balance - 100 WHERE id = 'A'; -- page P_A now dirty UPDATE accounts SET balance = balance + 100 WHERE id = 'B'; -- page P_B now dirty COMMIT;
Now imagine three different crash timings, all real possibilities under STEAL + NO-FORCE:
- Crash before COMMIT, but P_A was already stolen to disk. Disk shows A is $100 poorer, B unchanged — $100 vanished! We must UNDO P_A on restart.
- Crash just after COMMIT, but neither page reached disk yet (NO-FORCE). Disk shows the old balances — the committed transfer is invisible! We must REDO both updates on restart.
- Crash long after, both pages flushed. Nothing to do — disk is already correct.
The point: we cannot control crash timing, so we need a mechanism that lets us correctly UNDO or REDO any change regardless of when the lights go out. Enter the log.
2 Write-Ahead Logging (WAL)
Before you do anything risky, you write down what you're about to do in a little diary — "I am moving the toy from the red box to the blue box." You write in the diary first, then move the toy. If you forget halfway (you got distracted), you can read the diary later and either finish the move or put the toy back. The diary is tiny and quick to write; moving toys around is slow. A database keeps exactly this kind of diary, called the log, and the golden rule is: write in the diary before you touch the toys.
The central trick of recovery is the log (also called the transaction log or redo log): an append-only file on disk where, before changing any data page, the database records a description of the change. Because the log is appended sequentially, writing to it is fast (disks love sequential writes), unlike the slow random writes that scatter data pages all over the drive.
Write-Ahead Logging (WAL): the log record describing a change must be
flushed to stable storage (disk) before the corresponding dirty data page
is allowed to be written to disk. In short: log before you write. And a corollary:
all of a transaction's log records — especially its COMMIT record — must
be on disk before we tell the user "committed."
Why does this rule make everything work? Because it guarantees the log always knows at least as much as the disk. If a data change made it to disk, its log record is definitely already there too — so on restart we can always find out what happened and how to undo/redo it. The log becomes the single source of truth.
What's inside a log record?
Each log record describes one event. The most important kind is the update record, which records a modification to a page. Its key fields:
| Field | Meaning |
|---|---|
| LSN | Log Sequence Number — a unique, monotonically increasing ID for this record. Think of it as the diary's line number; bigger LSN = later in time. |
| TransID | Which transaction made the change. |
| Type | UPDATE, COMMIT, ABORT, BEGIN, CHECKPOINT, etc. |
| PageID | Which data page was modified. |
| Before-image (UNDO info) | The old value, so we can roll the change back. |
| After-image (REDO info) | The new value, so we can re-apply the change. |
| prevLSN | The LSN of this transaction's previous log record — links one transaction's records into a backward chain (used during UNDO). |
Notice each update record carries both a before-image and an after-image. That's what makes STEAL + NO-FORCE possible:
- The before-image gives us the UNDO information — to erase an uncommitted change that leaked to disk (STEAL).
- The after-image gives us the REDO information — to re-apply a committed change that never reached disk (NO-FORCE).
Here is what the log might look like for our $100 transfer from A to B (with another transaction T2 interleaved, to show LSNs are shared across all transactions). Read it top to bottom — the log is the true history of the database:
LSN | Txn | Type | Page | Before → After | prevLSN 10 | T1 | BEGIN | -- | -- | -- 11 | T1 | UPDATE | P_A | A: 500 → 400 | 10 12 | T2 | BEGIN | -- | -- | -- 13 | T1 | UPDATE | P_B | B: 300 → 400 | 11 14 | T2 | UPDATE | P_C | C: 900 → 950 | 12 15 | T1 | COMMIT | -- | -- | 13 ↑ once LSN 15 is safely on disk, T1 is officially committed/durable
Follow the prevLSN chain for T1: 15 → 13 → 11 → 10.
That backward chain lets recovery walk all of T1's changes in reverse to undo them if needed. The
before-images (500, 300) are everything we'd need to UNDO; the after-images (400, 400) are
everything we'd need to REDO.
Where the LSN also lives: on the page itself
Each data page stores, in its header, the LSN of the most recent log record whose change
is reflected on that page. This is called the pageLSN. It's a small but
brilliant idea: by comparing a page's pageLSN on disk against the LSN of a
log record, recovery can instantly tell "has this change already been applied to this
page?" — and thus avoid applying it twice. We'll use this constantly in ARIES (Topic 4).
Every COMMIT must wait for the log to be physically on disk
(log force), which is a real disk write and the main cost of durability.
Systems soften this with group commit — batching many transactions' commit
records into one disk write. But you can never skip the log force entirely: if you reported a
commit and the COMMIT record wasn't durable, a crash could lose a "committed" transaction, breaking
Durability.
WAL flips the order of operations: describe the change in the log and flush that description first, then change the data later. Because the log is always at least as up-to-date as the disk, and because each record carries both before- and after-images, the log alone contains everything needed to reconstruct a perfectly consistent database after any crash.
3 Checkpoints
Imagine your diary has been running for ten years and fills a whole library. If something goes wrong, you really don't want to re-read ten years of diary to figure out where you are. So every so often you jot a summary note: "As of today, here's exactly where everything stands." Now if disaster strikes, you only re-read from the last summary onward. A database does the same: a checkpoint is a "you-are-here" marker in the log that bounds how much we ever have to re-read after a crash.
Without checkpoints, recovery would have to scan the log all the way back to the very beginning of time — every change ever made — to be sure it didn't miss something. That's impossibly slow for a database that's been running for months. A checkpoint is a special log record that captures a snapshot of system state, so recovery can start from a recent, known point instead.
A checkpoint bounds the work of recovery. It tells the recovery manager: "you don't need to look at the log before this point; everything earlier was already safely captured." More frequent checkpoints = faster recovery but more runtime overhead; it's a tunable trade-off.
The naive checkpoint (and why it hurts)
A simple "blocking" checkpoint would: (1) stop accepting new transactions, (2) wait for active ones to pause, (3) flush all dirty pages to disk, (4) write a CHECKPOINT record, then (5) resume. It's correct, but it freezes the whole database while it flushes — a terrible hiccup for a busy system.
Fuzzy checkpoints — the practical version
A fuzzy checkpoint avoids the freeze. Instead of stopping everything and flushing all dirty pages, it just records a snapshot of two small tables describing the current state, and lets normal work continue (it's "fuzzy" because transactions keep modifying pages while the checkpoint is being taken). Those two tables are the heart of ARIES bookkeeping, so learn them now:
| Table | What it tracks | Key columns |
|---|---|---|
| Transaction Table (ATT) "Active Transaction Table" |
Every transaction currently running (not yet committed or aborted). | TransID, status (running/committing), and lastLSN — the LSN of that transaction's most recent log record. |
| Dirty Page Table (DPT) | Every page that is currently dirty in the buffer pool (modified but not yet flushed). | PageID and recLSN ("recovery LSN") — the LSN of the earliest log record that dirtied this page since it was last clean. |
The recLSN in the Dirty Page Table is the secret weapon. It marks the
oldest change to a page that might not be on disk yet. The smallest recLSN
across all dirty pages tells recovery exactly how far back in the log it must go to be safe — no
further. That point is where Redo will begin (Topic 4).
Continuing our log, suppose at LSN 16 the system takes a fuzzy checkpoint. It writes the current contents of both tables right into the log:
LSN | Type | Contents 16 | CHECKPOINT | ATT = { T2: lastLSN=14 } # T1 already committed at 15 | | DPT = { P_B: recLSN=13, # T1's change to B may not be flushed | | P_C: recLSN=14 } # T2's change to C may not be flushed
Reading this snapshot, a recovery process knows: T2 was still running, and pages P_B and P_C had un-flushed changes starting at LSNs 13 and 14. The smallest recLSN is 13, so if we crashed right after this checkpoint, Redo would only need to start at LSN 13 — never earlier. The checkpoint just bounded our work.
Because the checkpoint is fuzzy (the world keeps moving while we snapshot), ARIES actually writes
two records: a begin_checkpoint and a later end_checkpoint
containing the table snapshots. A separate, known location on disk — the master
record — stores the LSN of the most recent successful checkpoint so restart can find it
instantly.
Checkpoint often → recovery is fast (little log to replay) but you pay steady runtime overhead and more frequent flushing. Checkpoint rarely → cheap at runtime but recovery after a crash can take a long time. Real systems checkpoint on a timer and/or after a certain volume of log has accumulated.
4 ARIES recovery — the three phases
The power came back on after the storm. You pick up your diary and do three passes. First pass: skim from your last summary note to the end, just to figure out what was going on when the lights went out — which chores were finished, which were half-done. Second pass: go back and redo every single chore exactly as the diary says, even ones you already finished, so the room definitely matches the diary — "repeat history." Third pass: for the chores that were only half-done and will never be finished, carefully undo them so no mess is left behind. That's ARIES.
ARIES (Algorithms for Recovery and Isolation Exploiting Semantics) is the recovery algorithm published by C. Mohan and colleagues at IBM in 1992. It's the gold standard, implemented in spirit by most real databases. ARIES recovers with three passes over the log, in this exact order:
ARIES rests on three principles that explain why the phases are shaped this way:
- Write-ahead logging (Topic 2) — the log is always at least as current as disk.
- Repeat history during Redo — ARIES first reconstructs the exact state the database was in at the moment of the crash, including changes made by transactions that will later be undone. Recover first, then sort out winners and losers.
- Log changes during Undo — even the undo actions are logged (with special CLR records, below), so a crash during recovery doesn't redo work we already undid.
Phase 1 — Analysis: who and what?
Start at the most recent checkpoint (found via the master record) and scan forward to the end of the log. The goal is to rebuild two things as they were at crash time:
- The Transaction Table (ATT) — so we know which transactions were still active. Any transaction in the ATT at the end without a COMMIT record is a loser (must be undone). Transactions that committed are winners.
- The Dirty Page Table (DPT) — so we know which pages might have un-flushed
changes. The smallest
recLSNin the final DPT is the RedoLSN: the point where Phase 2 will start.
As Analysis scans, it updates these tables: a BEGIN/UPDATE adds the txn to the ATT; a COMMIT/ABORT
end-record removes it (or marks it); an UPDATE to a page not already in the DPT adds it with
recLSN = that record's LSN.
Phase 2 — Redo: repeat history
Start at the RedoLSN and scan forward to the end. For
every update record (winners and losers alike — yes, even doomed
transactions), re-apply the after-image to the page... unless the change is already
there. How do we know it's already there? The pageLSN from Topic 2:
A change is re-applied only if all hold: the page is in the DPT, the record's
LSN ≥ the page's recLSN, and the page's on-disk
pageLSN < the record's LSN. If the page's pageLSN
is already ≥ the record's LSN, the change made it to disk before the crash — skip it. This is what
makes Redo idempotent: replaying it twice does no harm.
After Redo, the database is in the exact state it was in the instant before the crash — warts and all, including half-finished loser transactions. That's the "repeat history" philosophy.
Phase 3 — Undo: roll back the losers
Now scan backward, undoing every change made by the loser transactions, using the
before-images and following each loser's prevLSN chain. As
each change is undone, ARIES writes a Compensation Log Record (CLR) recording
that the undo happened. A CLR also stores an UndoNextLSN pointer to the next
record that still needs undoing.
Suppose we crash again in the middle of recovery. Without CLRs, on the next restart we
might re-undo a change we already undid (corrupting data). Because CLRs are logged (and are
redo-only — they're never themselves undone), the next recovery's Redo phase
replays the undos we'd already done and the UndoNextLSN pointer tells Undo
exactly where to resume. ARIES recovery is therefore restartable — crash-safe even
while recovering.
Here's a complete log up to a crash. T1 committed; T2 did not (it's a loser). Pages P_A, P_B (T1) and P_C (T2) were modified. Assume the crash happens right after LSN 17.
LSN | Txn | Type | Page | Before → After | prevLSN 16 | -- | CHECKPT | -- | ATT={T2:14}, DPT={P_B:13, P_C:14} 17 | T2 | UPDATE | P_D | D: 70 → 90 | 14 ════════════ 💥 CRASH ════════════ Earlier records (for reference): 10 T1 BEGIN · 11 T1 UPDATE P_A 500→400 · 12 T2 BEGIN 13 T1 UPDATE P_B 300→400 · 14 T2 UPDATE P_C 900→950 · 15 T1 COMMIT
① Analysis — start at checkpoint LSN 16, scan forward:
ATT after scan : { T2 : lastLSN=17 } # T1 committed (LSN 15) → winner, removed
# T2 never committed → LOSER
DPT after scan : { P_B:recLSN=13, P_C:recLSN=14, P_D:recLSN=17 }
RedoLSN = min(recLSN) = 13 # Redo starts here
② Redo — start at LSN 13, scan forward, re-apply after-images (skip any page whose on-disk pageLSN already ≥ the record's LSN):
LSN 13: set P_B.B = 400 (T1, a winner — but we repeat history regardless) LSN 14: set P_C.C = 950 (T2, a loser — still redone! "repeat history") LSN 17: set P_D.D = 90 (T2, loser — still redone) # Database now exactly matches the moment of the crash.
③ Undo — T2 is the only loser. Walk its prevLSN chain backward (17 → 14 → 12) applying before-images, logging a CLR for each undo:
Undo LSN 17: restore P_D.D = 70 → write CLR (UndoNextLSN=14) Undo LSN 14: restore P_C.C = 900 → write CLR (UndoNextLSN=12) LSN 12 is T2's BEGIN → write an END record for T2, done. # T1's committed changes (P_A=400, P_B=400) are preserved → Durability ✓ # T2's changes fully erased → Atomicity ✓
Final state on disk: A=400, B=400 (T1 durable), C=900, D=70 (T2 rolled back). The database is consistent, Atomicity and Durability both honoured — exactly what Topic 1 demanded.
"Why redo a loser transaction's changes in Phase 2, only to undo them in Phase 3? Isn't that wasted work?" It looks redundant, but redoing first puts the database into a single, well-defined state (the crash-instant state), so the Undo phase has a clean, predictable starting point and the before-images line up correctly. "Repeat history, then undo losers" is far simpler and more robust than trying to selectively redo only winners.
★ Putting it all together
You just learned how a database keeps its promises through chaos. Here's the one-paragraph story that connects all four topics:
Databases do fast work in a volatile buffer pool and slowly flush dirty pages to non-volatile disk. For speed they adopt STEAL + NO-FORCE, which means uncommitted changes can leak to disk (needing UNDO) and committed changes can be missing from disk (needing REDO). The Write-Ahead Log makes this safe: every change is described in an append-only log — with an LSN, a before-image and an after-image — and that log record is flushed before the data page (and before any commit is reported). To keep recovery fast, fuzzy checkpoints periodically snapshot the Transaction Table and Dirty Page Table, bounding how far back we must read. After a crash, ARIES runs Analysis → Redo → Undo: discover who was running, repeat history to rebuild the crash-instant state, then roll back the losers — logging CLRs so even a crash during recovery is survivable. The payoff is the Atomicity and Durability we demanded back in Topic 1.
This caps off our reliability arc: Session 12 introduced ACID transactions, Session 13 covered concurrency control (the I in ACID), and this session covered the A and D. Next, in Session 15, we'll see how these ideas get reshaped in modern distributed and cloud database architectures.
Quick self-check
What does the Write-Ahead Logging rule actually require?
The log record describing a change must be flushed to disk before the corresponding data page is flushed — and a transaction's COMMIT record must be on disk before we report the transaction committed. In short: log before you write.
Why do real databases choose STEAL + NO-FORCE despite it being the hardest to recover?
Performance. STEAL lets the buffer manager flush whenever convenient (no memory pressure), and NO-FORCE makes commits fast because they don't wait for slow random data-page writes. The cost — needing both UNDO and REDO — is paid by the logging/ARIES machinery.
What is a dirty page, and why is it dangerous?
A page modified in the buffer pool but not yet written back to disk. It's dangerous because the new data exists only in volatile RAM; a crash loses it unless its change was first recorded in the durable log.
In ARIES, why does the Redo phase re-apply changes from transactions that will be undone?
Because ARIES "repeats history" — it rebuilds the exact state at the crash instant first, giving the Undo phase a clean, well-defined starting point. Selectively redoing only winners is far more complex and error-prone.
What's the role of the pageLSN during Redo?
Each page stores the LSN of the last change applied to it. If a page's on-disk pageLSN is already ≥ a log record's LSN, that change already reached disk, so Redo skips it. This makes Redo idempotent — safe to replay.
What problem do Compensation Log Records (CLRs) solve?
They make recovery itself crash-safe. By logging each undo action (and being redo-only, never undone), CLRs ensure that if the system crashes mid-recovery, the next restart won't re-undo work already undone; the UndoNextLSN pointer tells Undo exactly where to resume.
Why take fuzzy checkpoints instead of "stop the world" checkpoints?
A blocking checkpoint freezes the whole database while it flushes all dirty pages. A fuzzy checkpoint just snapshots the Transaction Table and Dirty Page Table and lets normal work continue, bounding recovery work without a service hiccup.
📚 References & Further Reading
Class material
- 📄 Original course notes / handout (source sheet) — open the shared class material for this session.
- 📘 Class handout: "DBMS Session 14 — Logging & Recovery".
- 📝 Written assignment: "Design a recovery strategy" — given a workload and crash assumptions, choose STEAL/FORCE policies, a checkpoint cadence, and describe how your scheme would UNDO/REDO through a sample crash.
Papers, docs & deep dives
- Mohan et al., "ARIES" (ACM TODS, 1992) — the original, definitive paper on the algorithm this whole session is built around; dense but foundational.
- CMU 15-445 Database Systems — Logging & Recovery lectures — Andy Pavlo's free lectures and slides walk through WAL, checkpoints, and ARIES with great clarity.
- Silberschatz, Korth & Sudarshan, "Database System Concepts" — Recovery chapter — the standard textbook treatment of recovery, log-based recovery, and checkpoints.
- PostgreSQL Documentation — Write-Ahead Logging (WAL) — see WAL, checkpoints, and recovery as implemented in a real, production database.
- MySQL / InnoDB Documentation — Crash Recovery & the Redo Log — InnoDB's redo log and recovery, an ARIES-style scheme in widespread use.