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.
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:
- Log records must reach durable storage (
fsync/fdatasync) before the corresponding dirty data page is written to the data file. - A transaction is not committed until its
COMMITlog record (and all priorprevLSNrecords) isfsynced to the WAL.
STEAL / NO-FORCE Write Path
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.
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):prevLSNforms 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, ifpage.pageLSN >= record.LSN, that update is already reflected on disk and safely skipped. - Dirty Page Table (DPT): Maps
pageId -> recLSN, whererecLSNis 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.
In-Memory Tables vs On-Disk Page Headers
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.
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:
- Analysis Pass (Forward from Last Checkpoint):
- Reads the
END_CHECKPOINTrecord to initialize the DPT and TT. - Scans forward to the end of the WAL. When it sees a
BEGINor update for atxId, it adds/updatesTT[txId].lastLSN. When it seesCOMMITorABORT, it removestxIdfrom the active loser set. When it sees an update for apageIdnot yet in DPT, it setsDPT[pageId].recLSN = record.LSN. - At the end of Analysis,
TTcontains the exact loser transactions to undo, andredoStartLSN = min(DPT.values()).
- Redo Pass (Repeating History from
redoStartLSN):
- Scans forward from
redoStartLSNto the end of the WAL, reapplying every logged page modification—including loser transactions—unless: pageIdis not inDPT, ORrecord.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.
Analysis -> Redo (Repeating History)
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.
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
undoDatainverse operation to the page, updatepage.pageLSN, and append a Compensation Log Record (CLR) to the WAL before modifying the page (WAL invariant still applies!). - Set
CLR.undoNextLSN = record.prevLSNand pushrecord.prevLSNonto 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.
Backward Undo with CLRs
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.
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_lsnBatched WAL Append & Durable fsync
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.
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 = onin 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.
PostgreSQL FPW vs InnoDB Doublewrite Buffer
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.
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 TRANSACTIONsessions prevent WAL segment recycling, filling/var/lib/postgresql/data/pg_waland crashing the primary. - Checkpoint I/O Storms: Setting
checkpoint_completion_targettoo low (ormax_wal_sizetoo small) forces dirty pages to flush in a tight burst, saturating NVMe/EBS bandwidth and starving reads. - Misconfigured
synchronous_commit: Turningsynchronous_commit = offboosts throughput by ~3x but introduces a bounded window (e.g., up to 600 ms withwal_writer_delay = 200ms) where committed transactions can vanish on power loss.
Durability vs Throughput & RTO
1.:
2.:
Caption: Operational WAL tuning balances zero-RPO fsync guarantees against commit latency, checkpoint pacing, and bounded replication slot retention.
Practice: Make the trade-off yourself.
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?