Write-Ahead Log (WAL)

A durability mechanism where mutations are serialized and fsynced to an append-only log before being applied to the primary data structure (e.g., a B-tree or memtable). It decouples the latency of acknowledging a write from the latency of updating complex on-disk structures, enabling crash recovery via replay.

The WAL exists to solve a fundamental impedance mismatch: updating a B-tree or LSM memtable in place is expensive (random I/O, page splits) and dangerous (a crash mid-update corrupts the structure), whereas appending a record to a sequential file is cheap and nearly atomic. The system treats the log as the source of truth; the in-memory or on-disk data structures are merely a cache that can be reconstructed by replaying the log from the last known checkpoint. This is why Postgres, MySQL InnoDB, Kafka, and virtually every embedded KV store (RocksDB, etcd’s boltdb layer) all converge on this design.

The critical engineering tension is the fsync boundary. A write is not durable until the log record has been flushed past the OS page cache to physical media (or acknowledged by an NVMe write barrier). Naive per-write fsyncs cap throughput at the device’s IOPS-per-fsync ceiling, which is why production systems batch writes into group commit windows, amortizing a single fsync across dozens or hundreds of concurrent transactions. This introduces a direct latency-vs-durability knob: innodb_flush_log_at_trx_commit or fsync=always/everyn/no in Postgres/Redis-AOF trade a bounded window of data loss (typically 0-1 seconds) for a 10-100x throughput gain.

Recovery correctness depends entirely on the log’s ordering and integrity guarantees. Each record carries a monotonically increasing Log Sequence Number (LSN), and most implementations checksum (CRC32C) each record to detect torn writes — a partially flushed sector from a crash mid-fsync. On restart, the recovery process (e.g., ARIES-style Analysis/Redo/Undo phases) scans forward from the last checkpoint, replays committed LSNs, and truncates any trailing garbage past the last valid checksum. Without this checksum boundary, a torn write can silently corrupt state by replaying a half-written record as if it were complete.

Operationally, the WAL becomes an architectural pivot point beyond crash recovery: physical replication (Postgres streaming replication, MySQL binlog-based semi-sync) is just continuous WAL shipping to standbys, and point-in-time recovery is WAL replay up to an arbitrary LSN/timestamp. This creates real capacity-planning failure modes — if a replica or archiver falls behind, WAL segments accumulate on the primary’s disk (pg_wal bloat) and can exhaust storage, forcing an operator choice between halting writes or breaking replication guarantees. Log-structured storage engines compound this by requiring periodic checkpointing to bound replay time; skipping checkpoints trades write throughput for recovery-time-objective (RTO), a tradeoff that must be tuned explicitly for systems with strict availability SLAs.