Skip to main content
← CONCEPTS / DISTRIBUTED SYSTEMS & STORAGE
An end-to-end domain learning journey

Write-Ahead Logging (WAL)
& ARIES Recovery.

Write-Ahead Logging turns random dirty-page disk writes into sequential log appends, while ARIES (Analysis, Redo, Undo) reconstructs exact database state after a crash.
Start the journey7 sections
FIRST PRINCIPLES. PRODUCTION SCALE.
The idea to keep with you

Write-Ahead Logging turns random dirty-page disk writes into sequential log appends, while ARIES (Analysis, Redo, Undo) reconstructs exact database state after a crash.

TL;DR30-second simplified summary
▾

Modern databases avoid flushing scattered 8 KB or 16 KB heap/B-Tree pages on every transaction commit because random synchronous I/O destroys throughput. Instead, under a STEAL/NO-FORCE buffer pool policy, the engine appends compact mutation records—each tagged with a monotonically increasing Log Sequence Number (LSN)—to an append-only Write-Ahead Log (WAL) and calls fsync on the log tail before returning COMMIT.

During normal execution, two in-memory structures track state: the Dirty Page Table (DPT) records each modified page's recLSN (the first LSN that dirtied it since the last flush), and the Transaction Table (TT) tracks active transactions and their lastLSN. Every data page header stores pageLSN, and the WAL invariant guarantees that a dirty page cannot be evicted to disk until flushedLSN >= pageLSN.

When power fails, ARIES executes three deterministic passes. Analysis scans forward from the last fuzzy checkpoint to rebuild the DPT and identify winner versus loser transactions. Redo repeats history forward from min(recLSN) across all DPT entries, reapplying any record where pageLSN < record.LSN—even for uncommitted transactions—so page states match the exact crash instant. Finally, Undo walks prevLSN pointers backward for loser transactions, writing Compensation Log Records (CLRs) with undoNextLSN so recovery itself is idempotent even if the server crashes mid-recovery.

The primary trade-offs center on checkpoint frequency, WAL amplification, and recovery time objectives (RTO). Infrequent checkpoints keep runtime overhead low but lengthen Redo scans; full-page writes (FPWs) after checkpoints prevent torn 8 KB pages on 4 KB filesystem blocks at the cost of temporary WAL spikes; and unpaced checkpoints or pinned replication slots can saturate disk IOPS and stall foreground commits.

From patterns to decisions.

Explain how modern relational and distributed storage engines achieve high write throughput without sacrificing crash atomicity or durability.

Full walkthrough · 7 stages
01
Stage 1 • Foundationfoundation

The Random I/O Paradox & STEAL/NO-FORCE Policies.

A storage engine's buffer pool caches fixed-size pages (for example, 8 KB pages in PostgreSQL 16 or 16 KB pages in MySQL 8.0 InnoDB) in RAM. If a transaction updates 50 rows across 50 scattered B-Tree leaf pages, flushing all 50 pages synchronously on COMMIT (FORCE policy) requires 50 random I/O operations. Conversely, forbidding the buffer pool from evicting dirty pages of uncommitted transactions (NO-STEAL policy) caps active transaction size to available RAM and causes out-of-memory failures during bulk updates.

Production engines therefore adopt STEAL / NO-FORCE:

  • STEAL: The buffer manager may evict an uncommitted dirty page to disk to free a frame, provided the WAL record describing that change is already fsynced (flushedLSN >= page.pageLSN).
  • NO-FORCE: A transaction commits as soon as its commit WAL record is durable on disk; its modified data pages remain dirty in RAM and are flushed asynchronously later.

This creates the fundamental Write-Ahead Logging invariant:

  1. Log records must reach durable storage (fsync / fdatasync) before the corresponding dirty data page is written to the data file.
  2. A transaction is not committed until its COMMIT log record (and all prior prevLSN records) is fsynced to the WAL.
Buffer Pool vs WAL

STEAL / NO-FORCE Write Path

TransactionBuffer PoolWAL Buffer -> DiskStore2. Append LSN 102 + fsync

1.:

2.:

Caption: Under STEAL/NO-FORCE, transactions append sequential WAL records and fsync before commit, while dirty data pages stay in RAM and can only be evicted once their pageLSN is covered by flushedLSN.

02
Stage 2 • Core Mechanicsfoundation

LSNs, Page Headers, Dirty Page Table, and Transaction Table.

Every WAL record receives a globally ordered 64-bit Log Sequence Number (LSN)—typically the byte offset within the WAL stream (e.g., 0/1A4F208 in PostgreSQL). Four coordinated structures link log records to data pages:

  • WAL Record (LSN, txId, prevLSN, type, pageId, redoData, undoData): prevLSN forms a backward linked list per transaction so Undo can walk a single transaction's changes in reverse order without scanning unrelated records.
  • Page Header (pageLSN): Stored in the first bytes of every 8 KB/16 KB page. Updated atomically whenever a modification is applied in memory. During Redo, if page.pageLSN >= record.LSN, that update is already reflected on disk and safely skipped.
  • Dirty Page Table (DPT): Maps pageId -> recLSN, where recLSN is the earliest LSN that dirtied the page since it was last written cleanly to disk. min(recLSN) across the DPT bounds how far back Redo must start.
  • Transaction Table (TT): Maps active txId -> (status, lastLSN). Fuzzy checkpoints serialize snapshots of both the DPT and TT directly into the WAL without halting incoming writes.
ARIES Metadata

In-Memory Tables vs On-Disk Page Headers

Dirty Page TableTransaction TableData Page HeaderStorelastLSN drives Undo chain

1.:

2.:

Caption: ARIES coordinates the Dirty Page Table (recLSN), Transaction Table (lastLSN), and per-page pageLSN headers so recovery knows both where Redo begins and which transactions must be rolled back.

03
Stage 3 • Crash Recoveryintermediate

ARIES Phase 1 (Analysis) & Phase 2 (Redo: Repeating History).

Upon restart after a crash, ARIES does not immediately discard uncommitted work. Instead, it runs Analysis and Redo sequentially:

  1. Analysis Pass (Forward from Last Checkpoint):
  • Reads the END_CHECKPOINT record to initialize the DPT and TT.
  • Scans forward to the end of the WAL. When it sees a BEGIN or update for a txId, it adds/updates TT[txId].lastLSN. When it sees COMMIT or ABORT, it removes txId from the active loser set. When it sees an update for a pageId not yet in DPT, it sets DPT[pageId].recLSN = record.LSN.
  • At the end of Analysis, TT contains the exact loser transactions to undo, and redoStartLSN = min(DPT.values()).
  1. Redo Pass (Repeating History from redoStartLSN):
  • Scans forward from redoStartLSN to the end of the WAL, reapplying every logged page modification—including loser transactions—unless:
  • pageId is not in DPT, OR
  • record.LSN < DPT[pageId].recLSN, OR
  • Fetching the page from disk shows page.pageLSN >= record.LSN.
  • Why repeat history for losers? Physical/physiological B-Tree splits or space allocations by a loser transaction may be depended upon by a later committed transaction's LSN on the same page. Repeating history restores the exact physical page layout before logical Undo runs.
Recovery Passes 1 & 2

Analysis -> Redo (Repeating History)

Last Checkpoint1. Analysis2. RedoStoreJump back to min(recLSN)

1.:

2.:

Caption: Analysis scans forward from the last checkpoint to identify loser transactions and min(recLSN), then Redo replays history forward for any page whose on-disk pageLSN lags behind the WAL record.

04
Stage 4 • Crash Recoveryintermediate

ARIES Phase 3 (Undo) & Compensation Log Records (CLRs).

Once Redo completes, the database mirrors the exact physical state at the moment of the crash. Now Undo rolls back all uncommitted loser transactions in strict reverse LSN order using a max-heap priority queue of nextUndoLSN values:

  • Pop the highest LSN from the loser frontier.
  • If the record is a standard update: apply the undoData inverse operation to the page, update page.pageLSN, and append a Compensation Log Record (CLR) to the WAL before modifying the page (WAL invariant still applies!).
  • Set CLR.undoNextLSN = record.prevLSN and push record.prevLSN onto the heap.
  • If the record is itself a CLR (from an earlier aborted recovery attempt): do not undo it! Simply jump directly to CLR.undoNextLSN.

Because CLRs are Redo-only records that point past already-undone work, a second or third crash during Undo never repeats an undo step and never causes an infinite rollback loop.

Recovery Pass 3

Backward Undo with CLRs

Loser Max-HeapAppend CLRApply InverseStoreRevert page in RAM

1.:

2.:

Caption: Undo pops the highest pending loser LSN, logs a Redo-only Compensation Log Record (CLR) pointing to prevLSN, and reverts the page so even repeated crashes during recovery converge cleanly.

05
Stage 5 • Implementationintermediate

Safe WAL Append, Group Commit, and Bounded fsync Retry.

Writing and fsyncing one 4 KB block per transaction limits NVMe or cloud block storage (e.g., AWS EBS gp3) to ~2,000–5,000 commits/sec. Production engines use group commit: a leader thread batches all WAL records queued during an active fsync window and flushes them in a single os.fsync() syscall.

Below is a minimal, crash-safe WAL writer in Python with explicit fsync, CRC32 checksums, and bounded exponential backoff on transient EIO/EAGAIN errors before failing closed:

import os, struct, time, zlib, random

class WALWriter:
    def __init__(self, path: str, max_retries: int = 3):
        self.fd = os.open(path, os.O_CREAT | os.O_RDWR | os.O_APPEND, 0o644)
        self.lsn = os.lseek(self.fd, 0, os.SEEK_END)
        self.max_retries = max_retries

    def append_and_sync(self, tx_id: int, prev_lsn: int, payload: bytes) -> int:
        record_lsn = self.lsn
        header = struct.pack('>QQI', record_lsn, tx_id, len(payload))
        body = header + struct.pack('>Q', prev_lsn) + payload
        crc = zlib.crc32(body) & 0xFFFFFFFF
        frame = body + struct.pack('>I', crc)

        written = 0
        while written < len(frame):
            written += os.write(self.fd, frame[written:])

        for attempt in range(self.max_retries):
            try:
                os.fsync(self.fd)
                self.lsn += len(frame)
                return record_lsn
            except OSError as exc:
                if attempt == self.max_retries - 1:
                    # Fail closed: roll back in-memory LSN and alert caller
                    raise RuntimeError(f'WAL fsync failed at LSN {record_lsn}: {exc}') from exc
                time.sleep((0.02 * (2 ** attempt)) + random.uniform(0, 0.01))
        return record_lsn
Group Commit

Batched WAL Append & Durable fsync

Group Commit QProducerCRC32 FrameSingle os.fsyncStore

1.:

2.:

Caption: Group commit amortizes expensive fsync syscalls across concurrent transactions while CRC32 framing and fail-closed error handling protect against torn tail writes.

06
Stage 6 • Production Edge Casesadvanced

Torn Pages, Full-Page Writes (FPW), and Doublewrite Buffers.

ARIES Redo often uses physiological logging: log the page ID and the logical operation within that page (e.g., insert tuple at slot 4) rather than logging the entire 8 KB before/after image. Physiological logging is compact, but it assumes the underlying page on disk is internally consistent.

If the database uses 8 KB pages (PostgreSQL) or 16 KB pages (MySQL InnoDB) on top of 4 KB filesystem blocks and 512-byte NVMe sectors, a power outage mid-flush can leave half the page new and half old—a torn page. Applying a physiological Redo delta onto a torn page corrupts B-Tree pointers.

Engines solve this in two ways:

  • Full-Page Writes (full_page_writes = on in PostgreSQL): The first modification to any page after a checkpoint logs the entire 8 KB page image into the WAL. Redo overwrites the torn disk page wholesale before applying subsequent compact delta records.
  • Doublewrite Buffer (MySQL InnoDB): Before flushing dirty 16 KB pages to their final tablespace offsets, InnoDB writes them sequentially to a contiguous 2 MB doublewrite area and fsyncs it. On crash, InnoDB restores any torn page from the doublewrite buffer before running Redo.
Torn Page Protection

PostgreSQL FPW vs InnoDB Doublewrite Buffer

PostgreSQL FPWInnoDB DoublewriteStateStore

1.:

2.:

Caption: Full-Page Writes (PostgreSQL) and the Doublewrite Buffer (InnoDB) protect against torn multi-sector pages so physiological Redo always starts from a valid page image.

07
Stage 7 • Architecture & Operationsadvanced

Checkpoint Tuning, WAL Retention, and Distributed Consensus Logs.

The same append-only WAL principle powers distributed consensus engines like Raft (etcd, CockroachDB, TiKV) and Kafka. In Raft, the replicated log is the WAL: a leader appends an entry locally, replicates it via AppendEntries, and only applies it to the state machine (RocksDB/BoltDB) once a majority quorum fsyncs it.

Common production pitfalls include:

  • Unbounded WAL Growth: Inactive replication slots or long-running IDLE IN TRANSACTION sessions prevent WAL segment recycling, filling /var/lib/postgresql/data/pg_wal and crashing the primary.
  • Checkpoint I/O Storms: Setting checkpoint_completion_target too low (or max_wal_size too small) forces dirty pages to flush in a tight burst, saturating NVMe/EBS bandwidth and starving reads.
  • Misconfigured synchronous_commit: Turning synchronous_commit = off boosts throughput by ~3x but introduces a bounded window (e.g., up to 600 ms with wal_writer_delay = 200ms) where committed transactions can vanish on power loss.
Operational Trade-offs

Durability vs Throughput & RTO

synchronous_commit…synchronous_commit=…Distributed RaftWALStore

1.:

2.:

Caption: Operational WAL tuning balances zero-RPO fsync guarantees against commit latency, checkpoint pacing, and bounded replication slot retention.

Practice · Explain the consequences

Practice: Make the trade-off yourself.

Question 1 of 3
Score: 0/3

A buffer pool wants to evict a dirty 8 KB page with pageLSN = 4500 to disk while flushedLSN on the WAL is currently 4200. What must the storage engine do?

Recommended Learning Flow