WAL (Write-Ahead Log)¶

What it is¶

The write-ahead log is an append-only file recording every change the database makes. The rule that gives it its name: a change must be written to the log, durably, before the data it modifies is written to its final location. Then, whatever state the data files are in after a crash, the log contains enough information to repair them.

Almost every durable storage system has one: PostgreSQL (WAL), MySQL InnoDB (redo log), SQLite (WAL mode or rollback journal), RocksDB and LevelDB (the .log file), Kafka (the log is the data), and file systems like ext4 (the journal).

Why: two problems solved at once¶

1. Durability without random writes. Committing a transaction that touched 20 pages scattered across the disk would otherwise require 20 random page writes before acknowledging the commit. With a WAL, commit requires one sequential append plus one fsync; the 20 pages are written back later, in the background, in batches.

2. Atomicity across many pages. A transaction that modifies several pages cannot write them all atomically — a crash can land between any two writes. The log makes the whole transaction one record sequence with a commit marker: after a crash, recovery either reapplies all of it (commit record present) or none of it.

The client never waits for step 3 — durability comes entirely from the WAL record being on stable storage, which is what makes commit latency depend on one sequential fsync rather than on how many pages the transaction touched.

Log records and LSNs¶

Each record gets a log sequence number (LSN) — in PostgreSQL and InnoDB, its byte offset in the log stream, so LSNs grow monotonically. A record typically contains:

LSN | transaction ID | type | page ID | redo info | (undo info) | checksum

• Redo information says how to reapply the change.
• Undo information (in some designs) says how to reverse it.
• The checksum detects torn or corrupted records at the tail of the log after a crash — recovery stops at the first record that fails it. See Binary Encoding and Checksums.

Each data page stores the page LSN of the last record applied to it. That gives two essential rules:

1. Write-ahead rule: the buffer pool may write a dirty page to disk only after the WAL has been flushed up to that page's LSN.
2. Idempotent redo: during recovery, a record is reapplied to a page only if record.LSN > page.LSN; otherwise the page already contains the change.

Physical, logical, and physiological logging¶

LSM engines use the simplest possible form: the WAL record is the write batch itself (keys, values, sequence numbers), and recovery just re-inserts it into a fresh memtable. See the WAL implementation page.

Recovery: ARIES in brief¶

ARIES (Mohan et al., IBM, 1992) is the recovery algorithm most B+Tree databases follow, in three passes:

1. Analysis: scan forward from the last checkpoint to rebuild the table of active transactions and dirty pages at the time of the crash.
2. Redo: replay history from the earliest LSN that might not be on disk, reapplying every logged change (committed or not) whose LSN is newer than its page's LSN. The database is now exactly as it was at the moment of the crash.
3. Undo: roll back the changes of transactions that never committed, writing compensation log records so that a crash during recovery is itself recoverable.

The two policies behind this design are steal (the buffer pool may write a dirty page of an uncommitted transaction — hence undo) and no-force (commit does not force data pages to disk — hence redo). Together they give the buffer pool maximum freedom. PostgreSQL avoids the undo pass altogether thanks to MVCC: uncommitted row versions are simply invisible and cleaned up by VACUUM.

Checkpoints¶

Without checkpoints, recovery would replay the log from the beginning of time, and the log would grow forever. A checkpoint flushes dirty pages and records an LSN before which no log is needed for redo. Recovery starts there, and older log segments can be recycled or archived.

PostgreSQL's checkpoint frequency (checkpoint_timeout, default 5 min, and max_wal_size) trades recovery time against I/O: frequent checkpoints mean fast recovery but more page writes. LSM engines have an equivalent: once a memtable is flushed to an SSTable, the WAL file covering it is deleted.

Torn pages: full-page writes and double-write¶

A crash in the middle of writing an 8 KB page can leave it half old, half new (disks only guarantee sector atomicity — see Storage Hardware). Redo cannot repair a page whose structure is corrupted. Two solutions:

• PostgreSQL full-page writes: the first time a page is modified after a checkpoint, the WAL record includes a full image of the page. Recovery restores the image, then replays later records on top.
• InnoDB doublewrite buffer: pages are first written to a separate doublewrite area, fsynced, and only then written in place. A torn in-place page is restored from the doublewrite copy.

Both roughly double some write volume — part of the write amplification of B+Tree engines.

Group commit¶

fsync latency (~0.1–10 ms depending on the device; see Durability and fsync) caps a single sequential committer at a few hundred to a few thousand commits per second. Group commit has concurrent transactions share one flush: while one fsync is in progress, new commit records accumulate in the WAL buffer; the next fsync makes all of them durable at once. Throughput then scales with concurrency instead of being capped by device latency. PostgreSQL's commit_delay and LevelDB's writer queue are both forms of it.

Trade-offs and knobs¶

fsync on every commit guarantees durability but adds ~1–5 ms latency per commit on typical cloud storage. PostgreSQL's synchronous_commit = off acknowledges commits before the WAL flush; a crash loses the last few hundred milliseconds of commits (up to 3 × wal_writer_delay), but never corrupts the database, because WAL ordering is preserved. LevelDB/RocksDB's WriteOptions::sync = false is the same trade-off.

Replication via WAL¶

Because the WAL is a complete, ordered description of every change, shipping it to another server and replaying it there produces a replica. PostgreSQL streaming replication does exactly this. Synchronous replication waits for the standby to confirm receipt before acknowledging the commit (zero data loss, higher latency); asynchronous replication does not (lower latency, possible loss on failover — RPO > 0). See Replication.

Common pitfall¶

Turning off fsync entirely (not just synchronous_commit) to chase write throughput is a much larger risk than it looks — fsync=off means the operating system's page cache can lose WAL data on a power loss or kernel crash, not just the last ~200ms of application commits synchronous_commit=off risks. That difference is the entire point of WAL existing in the first place: fsync=off can corrupt the database in a way that's unrecoverable, since the log meant to reconstruct a consistent state after a crash can itself be incomplete or reordered relative to the data pages. synchronous_commit=off is a real, sanctioned trade-off for non-critical writes; disabling fsync outright generally isn't.