Wait, What?
A database can acknowledge COMMIT, lose power one microsecond later, and still be expected to remember the transaction.
Crash recovery is the machinery that turns durability from a promise into an algorithm. The central trick is that the database does not try to make every data page perfectly current on disk at every instant. Instead it records enough ordered evidence to reconstruct a valid state after failure.
This is a beautiful systems topic because every optimisation creates an obligation: if dirty pages can reach disk before commit, undo information matters; if committed pages need not be forced immediately, redo information matters; if the log grows forever, checkpoints matter.
Quick Answer
Learn recovery through the route ACID durability → volatile versus stable state → buffer pool → STEAL/NO-STEAL and FORCE/NO-FORCE → log records → LSNs → write-ahead logging → commit rule → checkpoints → crash → analysis → redo → undo → compensation log records → idempotence → point-in-time recovery → testing with fault injection. A beginner should explain why the log must reach durable storage before a dirty data page. A professional should trace a crash history, identify winners and losers, reason about redo/undo boundaries, validate recovery under repeated crashes and measure recovery-time versus write-amplification trade-offs.
1. Start With the Failure Model
Assume memory disappears on a crash while durable storage survives. The database may have acknowledged some transactions, left others incomplete and written only some modified pages. Recovery must restore a state that respects atomicity and durability.
2. The Buffer Pool Creates the Need for Recovery Logic
Database pages are cached in memory because accessing storage for every operation would be too slow. Modified pages become dirty. Once memory and disk can temporarily disagree, the system needs a disciplined protocol for deciding what must be persisted and in what order.
3. FORCE Versus NO-FORCE
A FORCE policy writes all pages changed by a transaction before acknowledging commit. This simplifies redo needs but makes commits expensive. NO-FORCE allows commit without flushing every changed page, improving throughput but requiring enough log information to redo committed effects later.
4. STEAL Versus NO-STEAL
A STEAL buffer manager may write a page containing changes from an uncommitted transaction to disk to free memory. That improves flexibility but means recovery may have to undo loser transactions. NO-STEAL avoids that particular problem but constrains memory management.
5. WAL Is an Ordering Rule
Write-Ahead Logging requires the log record describing a change to become durable before the corresponding changed data page is allowed to reach durable storage. This gives recovery a trusted history even when page flushing is asynchronous.
PostgreSQL 18 documents WAL as the basis for crash recovery and replication. See PostgreSQL 18: Write Ahead Log.
6. Commit Has Its Own Durability Rule
Before a transaction is reported as committed under the normal durable contract, the relevant commit/log information must be safely persisted. The database may delay data-page writes, but it cannot lose the evidence needed to reconstruct the committed transaction.
7. Log Sequence Numbers Put History in Order
Recovery schemes commonly assign monotonically ordered Log Sequence Numbers (LSNs) to log records. Pages can remember which log record their current state reflects, allowing recovery to decide whether a particular action has already been applied.
8. Physical, Logical and Physiological Logging Differ
A log can record low-level byte/page changes, higher-level operations or hybrids that are logical within a page. Each choice affects log volume, concurrency, redo/undo logic and coupling to storage structures.
9. Checkpoints Bound How Far Back Recovery Must Reason
A checkpoint records enough recovery metadata that restart need not scan the entire history from the beginning of time. The trade-off is that checkpoints themselves create I/O and coordination work.
PostgreSQL’s current WAL configuration documentation separates settings for checkpoints, archiving and recovery, making this operational relationship visible.
10. A Crash Divides Transactions Into Winners and Losers
Some transactions committed before the crash; others were active and incomplete. Recovery must preserve the committed effects and remove effects that cannot remain. The exact algorithm depends on the logging and buffer policies.
11. ARIES Organises Restart Into Analysis, Redo and Undo
The classic ARIES protocol first reconstructs recovery metadata, then repeats history through redo, and finally undoes incomplete transactions. The surprising phrase is repeat history: recovery may reconstruct the exact pre-crash state, including effects of loser transactions, before systematically removing those losers.
CMU’s crash-recovery notes summarise ARIES as Analysis → Redo → Undo. See CMU 15-445: Database Crash Recovery.
12. Analysis Reconstructs What Was Happening
The analysis pass identifies transactions that were active and pages that may have been dirty around the crash. In ARIES terminology this includes structures such as an active-transaction table and dirty-page information used to choose efficient redo starting points.
13. Redo Repeats History Safely
Redo scans forward and reapplies actions that may not yet be reflected on disk. Page LSN checks help make redo idempotent: if the page already contains the effect, recovery can skip redundant reapplication.
14. Undo Walks Loser Transactions Backward
Transactions that did not commit must not leave permanent effects. Undo follows their logged actions backward, applying compensating changes until their work is removed.
15. Compensation Log Records Make Recovery Recoverable
If the system crashes while it is itself undoing work, recovery must know what has already been undone. Compensation Log Records record undo progress so restart can continue rather than blindly repeating completed undo work.
16. Recovery Must Tolerate a Crash During Recovery
A robust recovery procedure is not a one-shot script that assumes the restart phase cannot fail. Idempotent redo rules and logged compensation are examples of design choices that allow the recovery process itself to be restarted safely.
17. Checkpointing Is Not the Same as Backup
A checkpoint helps the live database bound restart work. A backup protects against broader failures such as lost or corrupted storage. Point-in-time recovery combines a base backup with archived log history to reconstruct the database to a selected time.
PostgreSQL 18 explains how WAL archives plus base backups enable Point-in-Time Recovery. See PostgreSQL 18: Continuous Archiving and PITR.
18. WAL Serves More Than One Job
The same ordered change stream that supports crash recovery can support replication, archiving, change capture and storage architectures that reconstruct state from log history. But those uses impose different retention, throughput and correctness requirements.
19. Recovery Performance Is a Design Variable
Frequent checkpoints can reduce restart scanning but increase foreground I/O. Large logs can improve write batching but increase recovery work and retention costs. There is no useful tuning rule without stating the workload and recovery objectives.
20. Distinguish RPO From RTO
Recovery Point Objective (RPO) asks how much committed data loss is acceptable in a disaster scenario. Recovery Time Objective (RTO) asks how long service may take to return. Crash-recovery algorithms, replication and backup design influence these objectives differently.
21. Build a Paper Recovery Trace
Create a log with two pages and three transactions. Let T1 commit, T2 remain active, and T3 update a page whose dirty version reaches disk before crash. Mark LSNs, pageLSNs, commit records and the checkpoint. Then perform analysis, redo and undo by hand.
22. Build a Fault-Injection Laboratory
- Crash immediately before commit-log flush.
- Crash immediately after commit-log flush but before data-page flush.
- Crash after an uncommitted dirty page is written under a STEAL policy.
- Crash during checkpoint activity.
- Crash during recovery after some redo work.
- Crash during undo and verify compensation/restart behaviour.
- Corrupt or remove required log segments in a disposable environment and observe failure handling.
23. Verify Outcomes, Not Just Successful Restart
After each injected crash, independently check committed rows, absent loser effects, constraints, indexes and application-level invariants. A process that restarts without error is not proof that recovery was correct.
24. Common Learning Failure States
- Thinking WAL means data pages are written before the log.
- Confusing commit-log durability with flushing every changed data page.
- Treating checkpoints as backups.
- Assuming redo means only committed transactions are replayed in ARIES.
- Assuming undo can run without being logged.
- Memorising STEAL/NO-STEAL and FORCE/NO-FORCE without connecting them to redo and undo requirements.
- Forgetting a crash can occur during recovery.
- Testing recovery by clean shutdown rather than fault injection.
- Measuring normal throughput but never restart time.
- Discussing durability without stating the storage and replication assumptions.
25. A Beginner-to-Professional Learning Ladder
- Level 1: distinguish volatile memory from durable storage.
- Level 2: explain dirty pages and why buffering exists.
- Level 3: derive redo/undo needs from FORCE/NO-FORCE and STEAL/NO-STEAL.
- Level 4: enforce the WAL ordering rule in a toy engine.
- Level 5: trace checkpoints, commit records and LSNs.
- Level 6: hand-execute ARIES analysis, redo and undo.
- Level 7: explain compensation log records and restartable recovery.
- Level 8: test recovery with repeated crash injection.
- Level 9: measure checkpoint overhead and recovery time.
- Level 10: design recovery, backup and PITR around explicit RPO/RTO requirements.
26. Teach the Persistence Order Visually
Give learners three columns: memory log buffer, durable log, durable data pages. Move one record at a time and ask which moves are legal. This makes the WAL invariant concrete before ARIES terminology arrives.
27. Use Faded Worked Examples for Restart Traces
First provide a fully annotated log showing winners, losers, dirty pages and redo starting points. Then remove selected labels. Finally provide only the raw log and crash point. Fading forces the learner to reconstruct the recovery state rather than copy a memorised script.
Worked-example research in programming supports high initial guidance with deliberate reduction as learners gain competence. See Shin et al. (2023): Worked-Out Examples and Metacognitive Scaffolding.
28. Connect to the Existing eduKateSengkang Database Stack
Use LSM-Tree Algorithms for write-path and storage-structure trade-offs and B+ Tree Algorithms for page-oriented indexing. This article owns the distinct job of crash-safe persistence, WAL ordering and restart recovery.
29. Use Current Systems as Reality Checks
PostgreSQL 18’s current documentation states that WAL records every change to data files primarily for crash safety, and that replay since the last checkpoint can restore consistency after a crash. Current CMU database curricula continue to treat recovery, logging and checkpoints as core DBMS implementation topics.
30. Professional Direction
Advanced study includes ARIES internals, physiological logging, fuzzy checkpoints, group commit, WAL compression, replication slots, logical versus physical replication, storage-engine recovery, distributed commit recovery, consensus logs, cloud-separated storage, incremental backup, snapshotting, write-behind approaches on persistent memory and verified crash consistency. The professional test is uncompromising: after any allowed failure point, can the system reconstruct exactly the state its durability and atomicity contract promised?
31. Recovery Correctness Has Two Sides: Safety and Liveness
Safety means recovery never produces a state that violates the durability/atomicity contract: committed effects that should survive do survive, and loser effects do not remain. Liveness means recovery can actually finish despite large logs, repeated restarts and damaged-but-detectable inputs. Production engineering needs both. An algorithm that is theoretically correct but requires unbounded restart time can still miss the system’s availability objective.
32. Group Commit Changes the Performance Story
Durable log flushes are expensive, so databases often batch commit records from multiple transactions into a smaller number of storage synchronisation operations. Group commit preserves each transaction’s durability contract while amortising flush cost. The consequence is that commit latency and throughput become coupled to batching, storage latency and concurrency; measure distributions under realistic sync settings rather than benchmarking with durability disabled.
33. PageLSN Checks Are a Concrete Example of Idempotence
During redo, a recovery routine can compare a page’s recorded LSN with the log record it is considering. If the page already reflects that record or something later, redo can skip it. This local test is more than an optimisation: it is part of making repeated recovery safe. The general systems lesson is to attach enough version evidence to state so repeated application can be recognised.
34. A Professional Exercise: Build a Crash Matrix
For each critical write path, enumerate crash points before log append, after log append, before log flush, after log flush, before page write, after page write, during checkpoint, during redo and during undo. Automate restart and invariant verification at each point. Track both correctness and recovery duration. This turns recovery from a chapter in a textbook into a falsifiable reliability claim.
35. Final Learning Check
Without notes, explain the WAL ordering rule, derive why NO-FORCE needs redo, derive why STEAL needs undo, explain why ARIES repeats history, state the purpose of a compensation log record, and distinguish a checkpoint from a backup. If any answer is memorised vocabulary rather than a causal explanation, rebuild the paper trace.
eduKate Sengkang 