Recovery, write-ahead logs, and checkpoints

Prerequisites: Transactions, dirty buffer pages, and durable storage.

Learning objectives

• Apply the write-ahead ordering rule.
• Distinguish redo from undo and commit durability.
• Explain what a checkpoint does and does not guarantee.

A crash can occur between any two durable writes. Memory may disappear while storage contains a mixture of old and new pages. Recovery must reconstruct a database state consistent with the system's transaction guarantees. A write-ahead log records changes in an append-oriented history that can be made durable separately from scattered data pages. The essential ordering rule is that the relevant log information reaches durable storage before a changed page is allowed to do so.

Suppose transaction T changes balance from 100 to 130. Its update log record has log sequence number 40, and its commit record has number 41. The buffer page can still contain the new balance only in memory when the commit log is flushed through 41. A crash then loses that page version, but recovery can redo the committed update from the durable log. Acknowledging commit does not necessarily require writing every modified data page immediately.

Now consider the opposite order: the page containing 130 reaches storage before the update log record. A crash could leave the changed page without enough durable history to identify or recover the operation. That is why the ordering rule is about stable storage, not merely calling a logging function before a page-write function. Device caches, synchronization calls, and failure assumptions are part of implementing the guarantee.

Recovery needs depend on buffer-management policy. Steal permits uncommitted dirty pages to reach storage; such designs generally require a way to undo or otherwise hide uncommitted effects. No-force permits committed pages to remain unwritten; such designs require redo or an equivalent recovery mechanism. Real engines combine logging, versions, page metadata, and transaction status differently. Do not assume every system follows the same textbook recovery algorithm.

A page log sequence number records which changes the page already contains, allowing suitable redo logic to avoid applying the same logged update twice. Repeating recovery after another crash must itself be safe. In ARIES-style recovery, compensation log records describe undo work already performed, supporting restartable rollback. The important idea is to design recovery operations as carefully as normal operations, because recovery can also be interrupted.

Checkpoints bound the amount of history recovery must inspect by recording useful state and coordinating flushing. A checkpoint is not automatically a backup, does not mean all old logs can be deleted immediately, and does not remove the need for commit records. Backup restoration and point-in-time recovery require an explicit compatible base image and log chain.

Draw a timeline of log append, log flush, page write, commit acknowledgement, and crash. For each cut in that timeline, list what survives. That exercise exposes a durability claim far more clearly than treating the word transaction as an unexplained promise.

Practice problem

T commits after its update and commit records are durable, but its modified page has not been written. U has written an uncommitted dirty page under a steal policy, with its update log safely durable but no commit record. The machine crashes. Explain the required treatment of T and U, why WAL alone is not a backup, and why recovery must tolerate a second crash during its own work.

Worked solution

T’s acknowledged changes must be recovered, typically by redo because its data page may still be old. U’s uncommitted changes must not become committed visible state; an undo-based engine reverses them using its recovery machinery, while other designs may use version visibility or equivalent mechanisms. WAL provides a recoverable history relative to suitable database state, but losing both the database and its only log copy still loses the information. Backups and retained logs address a different failure scope. A second crash can interrupt redo or undo, so page sequence checks, compensation records, or other idempotent recovery mechanisms must make restarting safe.

Check your understanding

A synchronous commit has durable update and commit records, but its data page remains dirty in memory. A crash occurs. What does a no-force design require?

• Recover the committed change from durable history as needed.
• Ask the client to repeat the business operation without checking recovery.
• Lose the transaction because its page was not flushed.
• Treat it as uncommitted because dirty pages cannot contain committed data.

Explanation

No-force permits deferred data-page writes; durable recovery information preserves the acknowledged commit.

A dirty page reflects log record LSN 40. The durable log ends at LSN 35. Which action respects write-ahead logging?

• Flush the page now and append the missing log later.
• Acknowledge the transaction and rely on the buffer cache surviving.
• Delete older log records to make room for the page.
• Make the log durable through at least 40 before making that page durable.

Explanation

A crash preserving the page must also preserve the log information needed to recover its changes.

Primary reading

• Write-ahead logging: PostgreSQL Global Development Group
• Database Systems: lectures, notes, and projects: Carnegie Mellon University

Open the study and save your work →