Write-Ahead Logging and Crash Recovery

A transaction changes dozens of database pages. Writing every page to its final location before acknowledging commit would turn one logical operation into many random synchronous writes. Letting the buffer pool flush whenever convenient is faster, but a crash could leave some changes on disk and others only in vanished memory. The database needs a durable description of the transition before the pages themselves become durable.

Write-ahead logging (WAL) provides that description. The engine appends recovery records to an ordered log and forces the required prefix before it allows related data pages or a commit acknowledgement to outrun that prefix. After a crash, recovery reads the log to reconstruct the state promised by completed transactions and remove or ignore work that never completed.

The thesis is that WAL separates transaction durability from data-page placement by imposing durable ordering. Checkpoints bound how much log recovery must inspect; redo and, in some designs, undo reconcile pages with transaction outcomes; page-protection schemes handle writes that fail below page granularity. This is a database protocol over database records. A filesystem journal may protect filesystem structures, but it does not know which database transaction committed or how to repair a database page.

The Write-Ahead Rules Define Durability #

A database buffer pool holds mutable copies of pages. A transaction can update those pages in memory while the WAL manager appends records describing each change. Two ordering rules make later recovery possible:

1. Before a dirty data page reaches durable storage, WAL describing all changes reflected on that page must be durable through the page’s log sequence number.
2. Before the database reports a transaction committed, the commit record and all earlier WAL records required for that transaction must be durable.

The first rule prevents a page from containing a change whose recovery record was lost. The second defines the normal single-node commit contract: after acknowledgement, restart can rediscover the commit and its changes even if none of the modified data pages had been written yet.

“Durable” must be defined against the actual storage stack. A database asks the operating system to flush, but correctness also depends on kernel, filesystem, hypervisor, controller, drive cache, and power-loss behavior honoring the requested ordering. A successful write into a page cache is not necessarily stable storage. Databases expose settings that weaken synchronous commit for latency; using them deliberately changes which acknowledged transactions may disappear after a host failure.

WAL records can be physical, describing byte changes to a page; logical, describing a row-level operation; or physiological, identifying a page while expressing a structured operation within it. Physical records make redo direct but can be verbose. Logical records are useful for replication and auditing but may not be sufficient for idempotent low-level crash repair. Engines often use a purpose-built mix.

Log Sequence Numbers Connect Records and Pages #

Each WAL record receives a monotonically increasing log sequence number (LSN), usually representing a byte position in the log stream. Records identify the transaction, affected page or object, operation, and links or data needed for recovery. Data pages store a pageLSN indicating the newest WAL change already reflected in that page image.

During redo, recovery compares a record’s LSN with the page’s LSN. If the page already reflects that record or a later one, the operation can be skipped. If the page is behind, redo reapplies the change and advances pageLSN. This makes redo repeatable: a second recovery attempt after another crash does not apply increments twice merely because it starts again.

Transaction chains also matter. An ARIES-style log record can point to the transaction’s previous LSN. Recovery follows those chains backward to undo incomplete work. A compensation log record (CLR) describes an undo already performed and where rollback should continue. If recovery itself crashes, replaying the CLR prevents the same undo from being treated as a new forward action.

LSN 310 | tx=71 | UPDATE page=8 slot=2 | before=500 | after=460 | prev=0
LSN 328 | tx=71 | UPDATE page=9 slot=4 | before=210 | after=250 | prev=310
LSN 344 | tx=71 | COMMIT                              | prev=328
LSN 352 | tx=71 | END                                 | prev=344

Real records rarely store neat field values exactly like this. They may encode offsets, tuple fragments, index operations, full-page images, checksums, and alignment metadata. The simplified form exposes the recovery relationships: ordered global position, transaction history, page identity, and enough information to redo or undo according to the engine’s algorithm.

Log segments can be recycled only after every consumer has moved beyond them. Crash recovery, archival backup, point-in-time recovery, replicas, and change-data capture may each retain a lower required LSN. A stalled consumer can therefore turn a logically bounded append stream into disk exhaustion.

Worked Example: A Crash During a Transfer #

Consider transaction 71 transferring 40 units from account A on page 8 to account B on page 9. Both pages begin on disk with pageLSN=280. The buffer pool changes A from 500 to 460 and emits WAL at LSN 310, then changes B from 210 to 250 and emits WAL at LSN 328.

Suppose the buffer manager flushes page 8 before commit. It must first ensure WAL is durable through LSN 310. Page 8 reaches disk with A=460 and pageLSN=310. Page 9 remains dirty only in memory. The transaction then appends commit at LSN 344, and the log is forced through 344. The database acknowledges success.

Power fails before page 9 is written. On restart, disk appears inconsistent: A shows the debit, while B still shows 210. The durable WAL contains both update records and the commit. Recovery sees page 8 already at LSN 310 and skips that redo; page 9 is behind LSN 328, so it reapplies the credit and writes pageLSN=328. The committed transfer is restored without requiring both data pages to have been synchronous at commit time.

Now move the crash earlier, before LSN 344 becomes durable. Page 8 may still contain the debit because the engine permits uncommitted dirty pages to be flushed, a policy called steal. Transaction 71 has no durable commit record and is a loser. In an ARIES-style engine, recovery first repeats applicable history, then undoes the loser: it restores A to 500, records the compensation, and leaves B at 210. If page 9 had also reached disk, both updates would be undone.

Not every MVCC database physically undoes loser tuple changes during restart. Some redo structural effects and rely on transaction-status metadata to keep aborted versions invisible until cleanup. The invariant remains: recovery must make incomplete work unable to masquerade as committed state.

Checkpoints Bound Recovery Without Stopping Time #

Without checkpoints, restart might scan the log from database creation. A checkpoint records a recovery starting point and enough metadata to find dirty pages and active transactions. It also drives page flushing so old log ranges eventually become unnecessary for crash recovery.

A simple sharp checkpoint pauses updates, flushes every dirty page, records the checkpoint, and resumes. Its reasoning is easy and its latency is unacceptable for many systems. A fuzzy checkpoint records state while transactions continue. Dirty pages may remain dirty, and updates can race with checkpoint progress. Recovery starts from a conservative LSN that precedes the oldest change still needed, not merely from the instant a “checkpoint complete” message appears.

In ARIES terminology, analysis reconstructs a transaction table and dirty-page table from checkpoint and later records. Each dirty page has a recLSN, the earliest log record that may not be reflected on disk. Redo can begin at the smallest relevant recLSN, then use page LSN checks to skip already-applied records. A checkpoint therefore narrows uncertainty; it does not assert that every page matches the latest log.

Checkpoint frequency is a tradeoff. Frequent checkpoints bound recovery work and release log sooner, but generate write bursts and compete with foreground I/O. Infrequent checkpoints smooth ordinary operation but increase dirty data, recovery time, and retained log. Engines spread checkpoint writes over time and adapt to log volume to avoid an end-of-checkpoint storm.

Redo and Undo Depend on Buffer Policies #

Buffer policies are often summarized as force/no-force and steal/no-steal. Force writes every changed page by commit; no-force allows commit after WAL is durable while pages remain dirty. Steal allows an uncommitted page to be evicted; no-steal keeps such pages out of durable data files.

No-force requires redo because committed changes may exist only in WAL. Steal requires a way to undo incomplete changes or make their versions permanently invisible. Most high-performance general-purpose engines use no-force because forcing every page defeats WAL’s batching advantage. Many also permit steal to keep the buffer pool from being hostage to a large transaction.

An ARIES-style restart has three conceptual phases:

1. Analysis reconstructs dirty pages and identifies winner and loser transactions.
2. Redo repeats history from the earliest necessary LSN, restoring pages to the state reached before the crash, including some loser changes.
3. Undo traverses loser transaction chains backward, emits compensation records, and completes rollback.

Repeating history before undo simplifies interleaved page operations and structural changes such as page splits. Other engines organize recovery differently, especially MVCC systems that represent abort through transaction status, but all need an idempotent answer for records already reflected on pages and a durable answer for incomplete transactions.

Long-running transactions make undo and retention expensive. They keep old transaction state and log relevant, may dirty many pages, and can make rollback take as long as forward execution. Operational limits on transaction size and duration are therefore recovery controls, not only concurrency controls.

Protect Against Torn and Misordered Page Writes #

WAL ordering assumes a data page can later be interpreted well enough to compare or redo it. Storage may violate that convenience: a database page commonly spans several device sectors, and a power loss can leave a torn page containing a mixture of old and new sectors. Its header or pageLSN may claim an update that the rest of the page does not contain.

Checksums detect many torn or corrupted pages but do not reconstruct correct bytes. Engines use several strategies. PostgreSQL can log a full-page image on the first modification after a checkpoint so redo has a known complete page if that write tears. Some systems use a doublewrite area: write the complete page to a protected staging region before its home location, then recover from the staging copy. Copy-on-write trees publish new pages through parent/root changes rather than overwriting a live page in place.

Full-page images increase WAL volume, especially shortly after checkpoints when many pages receive their first update. Doublewrite adds data I/O. Smaller atomic-write units or storage guarantees can reduce cost but must be verified for the exact hardware and deployment layer. Disabling protection because a benchmark improves turns power loss into an untested data-format experiment.

A filesystem journal solves a different problem. It may ensure that file allocation and metadata changes are crash-consistent and, depending on its mode, order file data. It does not understand tx=71, know that pages 8 and 9 form one transfer, compare database page LSNs, or perform database redo and undo. Database WAL still needs explicit flush and page-integrity assumptions on top of the filesystem interface.

Group Commit Trades Queueing for Fewer Flushes #

For small transactions, the expensive commit step is often forcing the log, not appending a few bytes. Group commit lets several transactions share one durable flush. If transactions have commit records at LSNs 700, 730, and 760, one flush through 760 can make all three durable. Followers wait for a leader or log writer rather than issuing independent barriers.

The batching window trades latency for throughput. Waiting briefly can gather more commits and reduce flushes per transaction, but waiting too long adds avoidable response time when load is light. Under sustained concurrency, a natural queue may already form without an explicit delay. Implementations coordinate durable-LSN waiters so a transaction returns only after the flushed position reaches its own commit record.

Asynchronous commit returns before that condition. The transaction may become visible to other sessions yet be lost after an operating-system or power failure, depending on engine semantics. This can be reasonable for reconstructible telemetry and wrong for a payment acceptance. Label durability classes at the operation boundary and test them; do not hide the choice in a global tuning file.

Monitor WAL generation rate, bytes and records per transaction, flush count and latency, group size, commit wait time, checkpoint write volume, dirty-buffer age, retained segment bytes, archival lag, and estimated restart work. A rising flush latency can affect every committing transaction even when query CPU is idle. A sudden WAL-volume increase may come from larger transactions, full-page images, index churn, or a checkpoint pattern rather than more logical business writes.

Test Recovery as a State Space #

Recovery tests should crash the database at controlled boundaries, not shut it down politely. For the transfer example, inject failure before each update record, after each WAL append but before flush, after a data page write, before and after commit flush, during checkpoint, during redo, and during undo. After every restart, assert the invariant A + B = constant and whether transaction 71 is committed according to the acknowledgement point.

Repeat recovery itself: crash while writing a compensation record or while replaying a page, then restart again. Duplicate WAL records, truncate only the final partial record where the format permits detection, corrupt checksums, and present a page whose LSN is ahead of its contents. The engine must reject unrecoverable corruption rather than quietly inventing state.

Exercise realistic storage settings in an isolated environment, including abrupt process termination, host termination, and simulated power loss where the platform supports it. A process kill does not test volatile controller caches. Verify backup restoration by loading a base backup, replaying archived WAL to a chosen target, and comparing logical invariants and checksums. Record the recovery point and timeline so the test proves which history was selected.

Operational drills should estimate recovery time under peak WAL volume, ensure retained segments have disk headroom, alert on failed archival and stuck consumers, and document what happens when the final WAL segment is corrupt. Measure recovery objectives from detection through service readiness, not only replay speed. A database that replays quickly but then rebuilds caches or replicas for hours has a larger service recovery window.

Takeaways #

• WAL makes transaction durability independent of immediate data-page flushing by enforcing log-before-page and log-before-acknowledgement ordering.
• LSNs, page LSNs, transaction chains, and durable outcomes make restart operations repeatable.
• Fuzzy checkpoints bound analysis while allowing ordinary work to continue; they do not imply every data page is current.
• No-force policies require redo, while steal policies require undo or an equivalent way to hide incomplete versions.
• Torn-page protection complements WAL because a corrupt page may not be a usable redo target.
• Group commit amortizes storage flushes, with explicit latency and durability tradeoffs.
• Database WAL recovers database transactions; filesystem journaling cannot infer those transaction semantics.
• Crash-point, repeated-recovery, corruption, and restore tests are the evidence that the durability contract holds.

Write-ahead logging is powerful because it turns a sprawling set of page writes into one ordered recovery narrative. The engine may place pages lazily and restart in the middle of recovery, but if every durable edge respects that narrative, acknowledged transactions can be reconstructed without pretending storage changes happen all at once.