Write-Ahead Log (WAL)

Problem statement (interviewer prompt)

A database server crashes mid-write. When it restarts, partially-updated data pages may be on disk but the transaction never committed. Design a mechanism that guarantees either every committed change is durable or every uncommitted change is reversed.

The write-ahead log is the universal trick for crash-safe storage: write the intent before the change. Every mutation is appended to a sequential log file; data pages are updated lazily; on crash, the log replays committed records and discards uncommitted ones.

flowchart TB
  App[Transaction] -->|1. append| WAL[(WAL on disk<br/>append-only)]
  WAL -->|2. fsync| Disk[disk durable]
  App -->|3. commit ack| Done
  WAL -. async checkpoint .-> Heap[(Heap pages)]

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
    classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
    classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
    classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;
    class App service;
    class WAL,Heap datastore;

Used by Postgres (WAL), MySQL InnoDB (redo log), Oracle (redo log), SQLite (rollback journal / WAL mode), Cassandra (commitlog), Kafka (the log IS the database).

The write-ahead log is the single most important data structure in any durable database. Get it right and crashes become recoverable; get it wrong and you lose committed data.

The basic invariant

Before any change reaches the data files, a description of that change must be safely on disk in the log.

This is the "write-ahead" rule. Combined with fsync(), it guarantees that on crash, the WAL contains everything needed to reconstruct the committed state.

Anatomy of a WAL record

LSN: 0x12340000        # log sequence number, monotonic
type: UPDATE
txn_id: 42
table: orders
key: (id=7)
before: {status: NEW}
after: {status: PAID}

The Log Sequence Number (LSN) orders every operation across the whole database.

ARIES recovery

Most modern DBs use ARIES (Algorithms for Recovery and Isolation Exploiting Semantics, 1992):

flowchart LR
  Crash --> Analysis[1. Analysis<br/>find last checkpoint] --> Redo[2. Redo<br/>replay log after checkpoint] --> Undo[3. Undo<br/>rollback uncommitted txns]

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
    classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
    classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
    classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;
    class Analysis,Redo,Undo service;

• Analysis: read from last checkpoint; identify which txns were in-flight at crash.
• Redo: re-apply every log record (idempotent), bringing pages up to date.
• Undo: roll back in-flight txns using before-image.

Checkpointing

Without checkpoints, recovery would replay the entire log since database creation. A checkpoint:

1. Forces dirty pages to disk.
2. Writes a CHECKPOINT record with all in-flight txn ids.
3. Future recovery starts from this LSN.

Trade-off: frequent checkpoints = small recovery window, high I/O. Postgres tunes via checkpoint_timeout and max_wal_size.

Group commit

Each fsync() is slow (1ms on SSD, 10ms on HDD). Group commit batches:

sequenceDiagram
  participant T1
  participant T2
  participant T3
  participant WAL
  T1->>WAL: append (LSN 100)
  T2->>WAL: append (LSN 101)
  T3->>WAL: append (LSN 102)
  WAL->>WAL: single fsync up to 102
  WAL-->>T1: commit ack
  WAL-->>T2: commit ack
  WAL-->>T3: commit ack

One fsync amortized across N transactions. Throughput skyrockets at the cost of slightly higher per-txn latency.

Physical vs logical WAL

Style	What's logged	Use
Physical	Block/page changes	Same-DB crash recovery, byte-for-byte standby
Logical	Row operations (UPDATE orders SET ... WHERE id=7)	Replication across versions, CDC, downstream consumers
Hybrid	Physical primary; logical decoder	Postgres logical replication, MySQL binlog

Postgres WAL is physical; the logical decoder parses it into logical changes for replication slots.

Log shipping for replication

flowchart TB
  Primary[Primary] -->|ship WAL| StandbyHot[Hot Standby]
  Primary -->|ship WAL| StandbyCold[Disaster recovery]
  Primary -->|CDC stream| Kafka[(Kafka)]
  Kafka --> DW[(Data warehouse)]
  Kafka --> Cache[(Cache invalidation)]

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
    classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
    classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
    classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;
    class Primary,StandbyHot,StandbyCold,DW datastore;
    class Kafka queue;
    class Cache cache;

Streaming the WAL to a standby gives near-realtime replication. CDC tools (Debezium, Maxwell, Outbox) decode the same WAL for downstream consumers.

Logs are sometimes the DB itself

Kafka, Datomic, and event-sourced systems make the log canonical: the WAL is the state. Reads project state from the log on demand.

Operational notes

• WAL must be on durable storage. Cloud SSDs with cache: confirm fsync survives power loss.
• synchronous_commit=off trades a small data-loss window for huge throughput.
• WAL fills disk if replication lags or archiving fails - monitor.
• pg_wal size + wal_keep_size matter for streaming replication.

Where WAL connects

flowchart TB
  WAL((Write-ahead<br/>log))
  ACID[ACID properties<br/>A and D depend on WAL]
  SE[Storage engines LSM / B-Tree<br/>both use WAL]
  REPL[Replication leader/follower<br/>log shipping]
  CDC[Change Data Capture<br/>parses the WAL]
  WAL --> ACID
  WAL --> SE
  WAL --> REPL
  WAL --> CDC

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
    classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
    classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
    classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;
    class WAL service;
    class ACID,SE,REPL,CDC datastore;

Glossary & fundamentals

Tag	Concept	What it is	Page
HLD	ACID properties	the contract WAL implements	acid-properties
HLD	Storage engines LSM B-Tree	LSM trees also use WAL	storage-engines-lsm-btree
HLD	Replication leader follower	log shipping powers replicas	replication-leader-follower
HLD	Change Data Capture	CDC reads the WAL	change-data-capture

Quick reference

Core invariant

Log the change before applying it to data pages.

ARIES recovery

1. Analysis - find last checkpoint
2. Redo - replay all log records
3. Undo - rollback uncommitted txns

Commit path

1. Append WAL record
2. fsync up to commit LSN
3. Return success
4. Data pages updated lazily

Group commit

Batch fsyncs across many txns → throughput up, latency slightly up.

Checkpointing

• Forces dirty pages to disk
• Bounds recovery time
• Tunable: checkpoint_timeout, max_wal_size

Physical vs logical

Style	Used for
Physical	Same-DB crash recovery, byte-for-byte standby
Logical	Cross-version replication, CDC

Used by

PG, MySQL InnoDB redo log, Oracle redo, SQLite WAL mode, Cassandra commitlog, Kafka (log-as-DB).

Operational

• WAL on durable storage; verify fsync semantics
• synchronous_commit=off for throughput, small loss window
• Monitor WAL disk usage (replication lag, archival)

Refs

• Mohan et al. - ARIES (1992)
• PG WAL docs
• Kreps - The Log: What every engineer should know
• Petrov - Database Internals

FAQ

What is a write-ahead log?

A sequential log file where every mutation is recorded before the data pages are updated. On crash, replaying the log redoes committed work and undoes uncommitted work.

Why is WAL faster than direct writes?

Sequential appends to a log are dramatically faster than scattered page updates. The database flushes pages lazily in the background while still guaranteeing durability via the log.

When does the WAL call fsync?

At least once per commit so the log is persisted before the client is told success. Group commit batches many transactions into one fsync to amortize the cost under high concurrency.

How is WAL used for replication?

Streaming replication ships WAL records to standby servers, which replay them to stay in sync with the primary. The same log powers point-in-time recovery from a base backup.

What is the difference between physical and logical WAL?

Physical WAL records byte-level page changes and only replays on the same engine version. Logical WAL records row-level operations, enabling cross-version replication and CDC pipelines.

Related Topics

• ACID Properties: WAL implements the A and D
• Storage Engines LSM B-Tree: LSM compaction relies on WAL for durability before flushing memtable
• Change Data Capture: CDC parses the WAL for downstream consumers

Further reading

• Paper - Mohan et al. - ARIES: A Transaction Recovery Method (1992)
• Doc - PostgreSQL - Write-Ahead Logging
• Blog - Confluent - The log: What every software engineer should know
• Book - Database Internals - Petrov (WAL chapter)