Crash recovery and durable commit — extended reference

This reference preserves the earlier detailed chapter and its citations. Start with the guided explanation, then use these sections for additional mechanisms and qualifications. References to the original lesson sequence are historical.

Part 4: Transactions, concurrency, and recovery

Prerequisites: Lesson 23 and the preceding foundations.

Learning outcomes

• Follow recovery from a checkpoint through redo and, where required, undo.
• Explain torn-write protection, checksums, log flushing, group commit, and restartable recovery.
• Calculate replay time and distinguish amortized flush cost from individual transaction latency.

Recovery must handle a crash during recovery

A server crashes while writing a page. The log contains a committed transfer, but the data page has only part of its new bytes. Restart begins replay, then power fails again. A recovery algorithm must reach the same valid committed state after another restart rather than assuming that cleanup runs uninterrupted.

Crash recovery connects persistent ordering with transaction outcome. It needs a failure model, valid-record detection, a checkpoint interpretation, redo and possibly undo rules, and a legal acknowledgment boundary. A process restarting successfully is not sufficient evidence that the recovered data is correct.

State the failure model

A process crash loses volatile application state while leaving whatever storage made durable. A machine power loss can also erase volatile device or controller buffers. A device failure can remove entire durable files. Filesystem corruption, operator mistakes, and replicated logical errors require different recovery mechanisms.

An engine’s synchronous commit guarantee depends on its interfaces and hardware honoring the relevant persistence operations. The application cannot strengthen that guarantee by labeling a response committed. Conversely, a correct engine can acknowledge before data pages are flushed if a durable log can reconstruct them.

The model also states whether storage writes can be partial, reordered, or torn at the page granularity. A database page larger than the device’s atomic write unit cannot be assumed indivisible. Recovery needs evidence to detect and repair a partially installed representation.

Checkpoints are recovery boundaries

A checkpoint records enough state to limit or organize recovery. It may identify dirty pages, active transactions, and log positions. A fuzzy checkpoint allows ordinary work to continue while collecting information; it is not necessarily a fully flushed snapshot of every page at one instant.

The checkpoint must itself be published safely. If restart points to an incomplete checkpoint, recovery may miss required history. Keeping a previous valid checkpoint until the new one is complete provides one common pattern. Exact files and metadata differ by engine.

Checkpoint frequency trades foreground and background work against restart cost and retained log. Frequent checkpoints can increase writeback and page-image traffic. Infrequent checkpoints can lengthen replay and consume log space. The right interval follows recovery objectives and the actual write workload.

Analysis, redo, and undo

ARIES organizes recovery around analysis, redo, and undo, with additional mechanisms for partial rollback and repeated recovery. Analysis reconstructs relevant transaction and dirty-page state. Redo repeats necessary history according to page and log metadata. Undo removes the effects of incomplete transactions under the design’s rules.

The phrase repeat history does not mean blindly applying every logical operation twice. Log sequence numbers and operation-specific recovery rules distinguish already reflected changes from missing work. Reapplying a debit as a new business transaction would be wrong; replay reconstructs the original transaction’s state.

Compensation records can record progress made while undoing, allowing another recovery to resume safely. The detailed ARIES algorithm has specific invariants and data structures; this lesson uses its phases to explain responsibilities rather than presenting abbreviated pseudocode as a complete implementation.

Torn pages and integrity

A checksum can detect some invalid page contents. It cannot recreate the missing correct bytes. Recovery may need a valid full-page image, another copy, or a storage protocol that preserves a recoverable page version. The engine must distinguish detection from repair.

PostgreSQL’s WAL configuration describes mechanisms related to full-page writes and checkpoint behavior. SQLite’s atomic-commit documentation provides another concrete recovery design. Their exact protocols differ, so their individual rules should not be mixed casually into a new engine.

A useful crash matrix examines failure before log append, during record write, after log durability, during page write, during checkpoint publication, and after commit before reply. For every point, the design states which records form a valid prefix, which transaction outcomes exist, and which pages can be trusted or reconstructed.

Durable commit and group scheduling

A commit waits for its required durable log position under the configured contract. Multiple transactions can share one flush, but each acknowledgment must be associated with a durable watermark that covers its commit information. An in-memory append position is not the same watermark.

A device synchronization failure is not an ordinary transaction validation error. Continuing to acknowledge durable success after the engine has lost its persistence guarantee can cause data loss. A safe implementation may reject further writes or enter a controlled failure state while preserving diagnostic evidence.

Asynchronous durability can be a deliberate mode. It reduces waiting while permitting a recent acknowledged window to disappear after a crash, depending on the exact interface. Such a mode can be useful for some workloads, but comparisons against synchronous systems must identify the different contract.

Recovery-time arithmetic

Suppose an illustrative recovery must process 120 GB of log at an effective 400 MB/s, using decimal units. Replay alone takes 120000/400 = 300 seconds. Startup, checkpoint loading, random page reads, validation, and rebuilding derived state add further time. A raw storage bandwidth figure is not necessarily the effective replay rate.

Replay can be CPU-limited, dependency-limited, or constrained by random access. Parallel replay requires proof that work can be reordered or executed concurrently without changing the recovered state. A log’s total byte size therefore does not fully determine restart duration.

Recovery objectives should be tested with realistic log age, data size, and cache temperature. A tiny development database restarting quickly provides little evidence for a multi-terabyte deployment. The time needed to reconnect clients and restore useful capacity also belongs in the service’s recovery objective.

Log retention and backup

The oldest required log position can be held back by checkpoints, replicas, backups, or change consumers. Deleting log solely because the primary no longer needs it can break another supported recovery path. Retention ownership must be explicit and observable.

A backup must represent a consistent recoverable state and include the required accompanying history. Copying files while they change without a supported protocol can produce an unusable mixture. A replica does not replace an independent backup when logical deletion or corruption can propagate to every live copy.

Encryption keys, metadata, and format versions are recovery dependencies too. A complete set of encrypted pages is not useful without keys and a compatible engine. Backup procedures should record and protect these dependencies without placing secrets in ordinary diagnostics.

Recovery testing as a design method

Testing should interrupt operations at persistence boundaries and compare recovered state against accepted transaction outcomes. Checksums, row invariants, index consistency, and operation identities provide different evidence. A crash test that merely confirms the process starts misses silent logical loss or duplication.

Storage faults should also include failed writes, short writes where applicable, full devices, and delayed I/O. The engine’s error paths must release or preserve ownership correctly. A temporary-file failure should not corrupt durable tables; a log failure should not produce false durable acknowledgments.

Repeated crashes test whether recovery itself is restartable. A design that writes cleanup metadata must ensure those writes have their own valid ordering and integrity rules. Recovery is ordinary fallible execution operating over unusual state, not a privileged interval in which failures stop occurring.

Work a small recovery history end to end

Use a simplified page-oriented undo/redo design to make recovery responsibilities concrete. Page P stores Alice’s balance; page Q stores Bob’s. T1 transfers 20 and commits. T2 then tentatively debits another 5 from Alice but never commits. Assume the log contains before and after information appropriate for undo and redo, and that write-ahead ordering was respected before any data-page flush.

Suppose P’s data file contains 75 because uncommitted pages may be flushed, while Q still contains 50. A crash occurs after the log through 50 is durable. Restart must retain T1’s complete result and remove T2’s effect. It cannot simply trust P because its page is newer, or trust Q because it is undamaged. Physical freshness is not transaction correctness.

Analysis identifies T1 as committed and T2 as incomplete and reconstructs the necessary dirty-page and transaction information. Redo reconstructs required history according to pageLSNs and recovery rules: Q needs T1’s credit; P may already represent the update history through T2. Undo then removes T2’s debit, returning P to 80. The accepted final balances are 80 and 70.

This example uses the responsibilities associated with undo/redo recovery, not a complete ARIES implementation. ARIES has detailed rules for transaction tables, dirty-page tables, compensation log records, undo chains, and restart handling. A teaching log omitting those fields cannot claim to implement the paper merely because it uses three named phases.

Compensation records make undo restartable

Suppose recovery undoes T2’s debit and then crashes before finishing cleanup. If the next recovery cannot tell which undo actions already occurred, it may repeat them incorrectly or lose track of remaining work. A compensation log record, or CLR, records an undo action’s redoable effect and where undo should continue.

The next restart redoes a CLR if necessary so the undone state is restored, then follows the recorded continuation rather than undoing the same original action again. CLRs are not ordinary user transactions and are not undone in the same way as the actions they compensate. This structure makes progress through rollback durable even when rollback itself fails.

The database must respect write-ahead ordering for recovery’s own writes. A page changed by undo cannot become durably installed ahead of the record explaining that change. Recovery is not exempt from the logging protocol. This is the central reason a restart algorithm needs its own failure analysis rather than assuming it runs to completion.

A simpler private-write engine can avoid undoing shared pages because uncommitted state was never installed there. Its restart process still needs valid snapshots, complete transaction replay, and safe publication. The absence of an undo phase is a consequence of its storage and visibility restrictions, not proof that undo is unnecessary for all engines.

Checkpoint publication needs a valid fallback

A checkpoint is useful only if recovery can identify a complete and compatible checkpoint generation. Imagine writing metadata file C2, then updating a small pointer to say C2 is current. If the pointer reaches storage but C2’s contents do not, restart can lose the only apparent recovery boundary. The publication order must make a complete checkpoint durable before advertising it as authoritative.

One conceptual design retains C1, writes and validates C2, synchronizes its contents, publishes a durable manifest selecting C2, and only later retires C1 when no required recovery path depends on it. Filesystem operations have their own guarantees; the database must account for file and directory metadata persistence where applicable. An atomic rename is not a substitute for a complete persistence argument.

A fuzzy checkpoint can collect metadata while transactions continue. It may point recovery to log positions earlier than the checkpoint record because pages or transactions were already dirty or active. Deleting all log before the checkpoint’s own LSN would then be unsafe. The truncation rule follows the oldest recovery dependency, not the newest file’s timestamp.

Checkpoint completion can create I/O pressure. Flushing a large dirty set in a burst may saturate storage and raise foreground commit latency. Spreading work reduces bursts but can lengthen checkpoint duration and keep more history alive. A recovery-time target and a foreground latency target jointly determine the sustainable policy.

Torn pages require reconstructable bytes

Suppose an eight-kilobyte page is written in smaller storage units and a crash leaves half old bytes and half new bytes. The result may contain a header claiming one structure while its slots refer to another. A checksum can identify that the page is not trustworthy, but replaying a tiny logical change against arbitrary corrupted structure may be impossible.

A full-page image provides a known base from which subsequent log changes can be replayed. A double-write or shadow-copy style protocol preserves another valid page representation before overwriting the main location. Different engines choose different mechanisms and assumptions. The common requirement is to obtain a valid page image before interpreting its internal offsets and applying incremental changes.

Integrity checks should verify identifiers, format versions, lengths, slot bounds, and checksums before following pointers or allocating based on stored sizes. Corruption is untrusted input at the recovery boundary. A parser that trusts a damaged page’s length field can turn a storage fault into a memory-safety failure.

A checksum mismatch in the active data file, a torn suffix in the log, and missing archived history are different events. Treating all three as “skip the bad record” can silently discard accepted work. The failure response should preserve safety, report the affected object and recovery position, and follow documented repair or restore procedures.

Calculate recovery from its resource stages

The earlier 120 GB replay example assumes an effective processing rate of 400 MB/s and gives five minutes of replay. Suppose startup and checkpoint loading add twenty seconds, validation adds thirty seconds, and reconnecting enough clients to restore useful capacity adds forty seconds. The illustrative service recovery interval becomes 390 seconds, or 6.5 minutes, before any additional variance.

The replay rate itself can depend on cache temperature and locality. Sequentially reading log at a gigabyte per second does not guarantee applying it at that rate if each record triggers a random page fetch. Sorting or grouping replay work can improve locality only if dependencies and transaction semantics allow that scheduling. Parallel replay needs ownership rules for pages, indexes, and metadata.

If recovery reconstructs subscriptions or caches, the foreground may technically open before it can serve normal latency. Opening too aggressively can cause a thundering herd of cold reads. Staged admission and controlled cache warming can improve the time to stable service, even if the first health check passes slightly later.

Recovery objectives should therefore name the endpoint: process ready, writes accepted, all replicas caught up, or normal SLOs restored. A claim of thirty-second restart is ambiguous if hours of background catch-up remain and failover safety is reduced during that interval.

Retention watermarks need separate owners

The primary may no longer need an old log segment for local restart after a checkpoint. A lagging replica may still need it, a backup may reference it, and a change-data-capture reader may not yet have consumed it. Segment deletion must respect every supported dependency or explicitly invalidate the lagging consumer according to policy.

A useful operational view lists each retention owner and its oldest required position. The minimum determines the physical retention frontier. If one consumer stops advancing, disk use can grow without bound unless the service has quotas, alerts, and a recovery policy. Forcing deletion restores space only by changing which recovery paths remain possible.

Backups create another chain. A base backup plus contiguous archived log can support point-in-time recovery within the retained interval. Missing one required segment may make later segments unusable for that chain even if their files are present. Verification should test completeness and successful replay rather than count archive objects.

Encryption adds dependencies on key versions and access authority. Losing the old key while retaining old encrypted log is equivalent to losing the history. Rotating keys safely means preserving the ability to decrypt every recovery artifact that policy still promises to retain. Recovery documentation must include metadata and keys without exposing secrets in ordinary logs.

A failure-injection scenario with an oracle

A meaningful recovery test records submitted operation identities and the responses actually observed by the harness. It injects crashes at log append, synchronization, page write, checkpoint publication, and reply boundaries. After restart, it compares database state with the set of outcomes allowed by the acknowledgment contract.

An acknowledged durable transfer must remain. A transaction with an explicit abort must not appear. A request whose connection failed before a definite outcome may be either committed or absent, but must not appear twice under the operation-identity protocol. This distinction avoids falsely labeling every uncertain result as lost data or accepting duplication as harmless.

The oracle can also enforce independent invariants: the sum of balances, nonnegative stock, unique item ownership, and consistency between table and index access. A crash that preserves totals but loses an index entry still fails. A restart that reconstructs rows correctly but leaks every temporary file may pass logical checks while exposing a separate operational defect.

Injected storage errors should include a full device, delayed completion, failed synchronization, and truncated temporary files. The expected response differs by resource. A failed analytical spill can return a query error; failure of the authoritative log must prevent false durable success. Error categorization is part of recovery design because not every I/O failure has the same correctness impact.

Foreground speed is borrowed from recovery capability

No-force commit avoids flushing every modified data page because durable redo can finish installation later. Group commit amortizes synchronization because each waiting transaction is tied to a covered durable watermark. Fuzzy checkpoints let work continue because recovery retains enough metadata and history to interpret the changing state. Each optimization is justified by a reconstruction argument.

That relationship gives a practical review method: for every removed foreground write or wait, identify the durable evidence that makes it safe. If no evidence exists, the implementation has weakened the contract rather than optimized its implementation. If evidence exists but recovery has never been tested at realistic scale, the performance result is incomplete because its deferred cost remains unmeasured.

Visualize group commit without confusing latency and amortization

T1: append commit -> [batch wait........][durable flush] -> reply
T2:       append commit -> [batch wait..][same flush...] -> reply
T3:                  append commit -> [same flush...] -> reply
                                    one covered durable boundary

All three transactions can share the same flush only if their complete required log positions are included. T1 may wait longer for batching than T3. The device work is amortized across the group, but each transaction experiences its own elapsed interval. Reporting flush duration divided by group size as individual latency would be misleading.

An adaptive policy can flush promptly under light load and group naturally under heavy load, while bounding the oldest wait. The implementation should record queue residence, batch size, bytes, and device synchronization time separately. A sudden rise in commit latency can come from larger batching delay, device slowdown, or increased queue depth, and each requires a different response.

The crash test for this timeline verifies that every released reply has a recoverable commit and that unreplied transactions are interpreted according to surviving evidence. A transaction joining after the flush’s covered position must wait for the next durable advance even if its caller happens to wake at the same time as the current batch.

Design conclusion

Recovery is part of the normal write protocol because every acknowledged optimization relies on a valid reconstruction path. The engine can defer page work only when the log, checkpoint, and visibility rules explain how to finish safely after interruption.

The next part extends the failure model to several machines. Durable local state is necessary but insufficient when nodes disagree, messages are delayed, and leadership changes while old processes remain alive.

Sources and further reading

• ARIES original paper, IBM, 1992
• PostgreSQL 18 WAL configuration
• Atomic commit in SQLite

Course index · Lesson plan