Write-Ahead Logging (WAL) Fundamentals

Write-ahead logging is the cornerstone durability mechanism in nearly every database system built in the last four decades.
The core idea is deceptively simple: before modifying any data page on disk, first write a record of the intended change to a sequential log.
This single constraint, when implemented correctly, enables crash recovery, transaction atomicity, and significant performance gains through deferred writes.
Understanding WAL deeply is essential for anyone building or operating storage systems.

Why WAL Exists

Database systems face a fundamental tension.
Users expect transactions to be durable the moment they commit, but writing modified data pages to their final on-disk locations at commit time is expensive.
Data pages are scattered across the disk, requiring random I/O.
A single transaction might touch dozens of pages.
Flushing all of them synchronously on every commit would cripple throughput.

WAL resolves this tension by exploiting a key asymmetry: sequential writes are dramatically faster than random writes, on both spinning disks and SSDs.
Instead of writing dirty data pages at commit time, the system appends log records describing the changes to a sequential file and flushes only that file.
The actual data pages can be written back lazily, in the background, at a time and order chosen for efficiency.
If the system crashes before those dirty pages reach disk, the log contains everything needed to reconstruct the lost changes.

This approach rests on one invariant, sometimes called the WAL protocol:

A data page must not be flushed to disk until all log records describing changes to that page have been flushed to the log.

Violating this invariant means a crash could leave a modified page on disk with no corresponding log record, making correct recovery impossible.

Anatomy of a Log Record

Each WAL record typically contains the following fields:

• LSN (Log Sequence Number): A monotonically increasing identifier that orders records within the log. Usually the byte offset into the log file.
• Transaction ID: Identifies which transaction produced this change.
• Page ID: The page (or block) being modified.
• Previous LSN: The LSN of the previous log record for the same transaction, forming a per-transaction chain used during rollback.
• Redo information: Enough data to reapply the operation to the page (e.g., "set bytes 200-208 on page 42 to 0xDEADBEEF").
• Undo information: Enough data to reverse the operation (e.g., "restore bytes 200-208 on page 42 to their prior value 0x00000000").
• Record type: Indicates whether this is an update, a commit, an abort, a compensation log record (CLR), or a checkpoint.

The inclusion of both redo and undo data is characteristic of the ARIES recovery algorithm, which most modern systems either implement directly or use as a reference point.

ARIES and the Three Phases of Recovery

The ARIES (Algorithm for Recovery and Isolation Exploiting Semantics) protocol, published by Mohan et al. in 1992, formalized WAL-based recovery into three phases.

1. Analysis Phase

The system scans the log forward from the most recent checkpoint.
It reconstructs two critical data structures:

• The dirty page table (DPT): Tracks which pages were potentially dirty (modified but not yet flushed) at crash time. Each entry records the earliest LSN that might have dirtied the page (the recLSN).
• The active transaction table (ATT): Tracks which transactions were in progress and had not yet committed or aborted.

2. Redo Phase

Starting from the smallest recLSN in the dirty page table, the system scans forward and reapplies all logged updates.
This is sometimes called "repeating history," and it restores the database to the exact state it was in at the moment of the crash, including changes made by uncommitted transactions.
A redo is skipped for a given log record only if the page is not in the DPT or if the page's on-disk LSN is already >= the log record's LSN (meaning the page was flushed after that change).

3. Undo Phase

The system rolls back all transactions that were active at crash time (those in the ATT that never committed).
It walks backward through each transaction's log chain using the previous LSN pointers, applying undo operations and writing compensation log records (CLRs) for each undone action.
CLRs are redo-only records that ensure the undo work itself is not repeated if the system crashes again during recovery.

Walkthrough

Below is a step-by-step walkthrough of WAL operations during normal processing and crash recovery.

Normal Operation

1. Transaction T1 begins.
2. T1 wants to update page P5.
3. System writes log record L10: [LSN=10, TxID=T1, PageID=P5,
   redo="set X=7", undo="set X=3", prevLSN=null]
4. System modifies page P5 in the buffer pool (in memory).
   Page P5's pageLSN is set to 10.
5. T1 wants to update page P8.
6. System writes log record L20: [LSN=20, TxID=T1, PageID=P8,
   redo="set Y=12", undo="set Y=5", prevLSN=10]
7. System modifies page P8 in the buffer pool.
   Page P8's pageLSN is set to 20.
8. T1 issues COMMIT.
9. System writes log record L30: [LSN=30, TxID=T1, type=COMMIT]
10. System flushes log up through LSN 30 to disk (force-at-commit).
11. Commit returns success to client.
    Pages P5 and P8 may still be dirty in the buffer pool.

Crash and Recovery

Assume the system crashes after step 11.
Page P5 was flushed to disk by the buffer manager, but P8 was not.

Recovery begins:

--- ANALYSIS PHASE ---
  Scan log from last checkpoint.
  Result: DPT = {P8: recLSN=20}, ATT = {} (T1 committed)

--- REDO PHASE ---
  Start from min recLSN in DPT = 20.
  Encounter L20 (page P8, LSN=20):
    Read page P8 from disk. Its pageLSN < 20.
    Reapply: set Y=12 on P8. Update pageLSN to 20.
  Encounter L30 (commit record): no page change, skip.

--- UNDO PHASE ---
  ATT is empty (no active transactions). Nothing to undo.

Recovery complete. Database is consistent.

If T1 had not committed before the crash, the undo phase would walk its log chain (L20 then L10), reverting both changes and writing CLRs for each.

Checkpointing

Without checkpoints, recovery would need to scan the entire log from the beginning of time.
Checkpoints bound the amount of log that must be replayed.
A fuzzy checkpoint, which is what most systems use, records the current dirty page table and active transaction table to the log without requiring all dirty pages to be flushed.
This allows checkpointing to proceed without stalling ongoing transactions.

The tradeoff is straightforward: more frequent checkpoints reduce recovery time but consume I/O bandwidth during normal operation.

Performance Considerations

Group commit. Flushing the log on every single commit is expensive.
Group commit batches multiple transactions' commit records into a single fsync call, amortizing the cost of the flush across many transactions.
This is one of the most impactful WAL optimizations in practice.

Log buffer management. The log buffer is a region of memory where log records accumulate before being flushed.
Sizing it correctly matters.
Too small, and the system flushes too often.
Too large, and commit latency increases because the buffer takes longer to fill before a group commit triggers.

Log file structure. Most systems use a series of fixed-size log segment files rather than a single growing file.
Old segments can be recycled once all transactions they reference have completed and all dirty pages they cover have been flushed.
PostgreSQL's WAL segments, for example, are typically 16 MB each.

Full page writes. Some systems (PostgreSQL calls these "full page images") write the entire contents of a page to the WAL the first time that page is modified after a checkpoint.
This protects against torn pages, where a crash occurs while the OS is partway through writing a data page.
The full page image in the WAL provides a known-good baseline for redo.

WAL in Modern Systems

WAL is not confined to traditional relational databases.
It appears across distributed systems in various forms:

• Log-structured storage engines (like those in LSM-tree-based systems such as RocksDB) use a WAL to protect the in-memory memtable against crashes.
• Consensus protocols like Raft and Paxos rely on durable logs that function as write-ahead logs for replicated state machines.
• Distributed databases like CockroachDB and TiDB use WAL both locally (for single-node durability) and as part of their Raft-based replication layer.

The principle is always the same: make the change durable in a sequential log before considering it committed.

Key Points

• WAL ensures durability by forcing log records to disk before the corresponding data page modifications, converting expensive random writes into cheap sequential writes.
• The WAL protocol requires that a dirty page cannot be flushed to disk until all log records for changes on that page have been persisted to the log.
• ARIES recovery proceeds in three phases (analysis, redo, undo), with redo "repeating history" to restore crash-time state and undo rolling back uncommitted transactions.
• Compensation log records (CLRs) make the undo phase idempotent, ensuring correctness even if the system crashes repeatedly during recovery.
• Checkpoints limit recovery time by recording dirty page and active transaction state, and bounding how far back the log must be scanned.
• Group commit amortizes the cost of log flushes across multiple transactions and is one of the most important practical WAL optimizations.
• WAL principles extend beyond traditional databases into consensus protocols, distributed storage engines, and log-structured systems.

References

C. Mohan, D. Haderle, B. Lindsay, H. Pirahesh, and P. Schwarz. "ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging." ACM Transactions on Database Systems, 17(1):94-162, March 1992.

Jim Gray and Andreas Reuter. "Transaction Processing: Concepts and Techniques." Morgan Kaufmann Publishers, 1993.

Ramakrishnan Raghu and Johannes Gehrke. "Database Management Systems." 3rd Edition, McGraw-Hill, 2003.

Philip A. Bernstein, Vassos Hadzilacos, and Nathan Goodman. "Concurrency Control and Recovery in Database Systems." Addison-Wesley, 1987.