How Does Write-Ahead Logging Ensure Durability?

Write-Ahead Logging is a fundamental database technique that guarantees durability and atomicity without requiring dirty data pages to be written to disk on every commit. By recording changes sequentially in an append-only log before modifying the actual data pages, databases can recover from crashes quickly and safely while keeping normal transaction processing fast.

The Problem with Flushing Data Pages on Commit

In a database management system, data is stored in fixed-size blocks called pages. When a transaction modifies a record, the database loads the corresponding page into memory, updates it, and marks it as dirty. Flushing every dirty page to disk at commit time would cause severe performance bottlenecks because data pages are scattered across storage, leading to slow random disk I/O.

On the other hand, keeping dirty pages only in memory risks losing committed data if a power failure or system crash occurs. Write-Ahead Logging (WAL) solves this dilemma by separating the durability of the transaction from the physical writing of the data pages.

How Write-Ahead Logging Works

WAL relies on a strict ordering rule: every modification to a data page must first be recorded in a persistent log file on disk before the modified page itself is allowed to be written to disk, and before the transaction is considered committed.

Each log record typically contains:

  • A unique Log Sequence Number (LSN) that monotonically increases, such that \(LSN_{i} < LSN_{i+1}\).
  • The transaction ID.
  • The type of operation (insert, update, delete, commit, or abort).
  • The before-image (undo information) and after-image (redo information) of the modified data.

Because log records are appended sequentially to the end of the log file, writing them to disk is much faster than performing random writes to scattered data pages. When a transaction commits, the database only needs to flush the log buffer up to the commit record's LSN. Once that sequential write succeeds, the transaction is durable, even if the dirty data pages remain in memory.

Ensuring Atomicity and Durability

WAL supports two key buffer-management policies that maximize performance:

  • Steal: The buffer manager is allowed to write dirty pages to disk before a transaction commits, freeing up memory for other operations.
  • No-Force: The buffer manager is not required to flush dirty pages to disk when a transaction commits.

Because of the WAL rule, if a dirty page is stolen and written to disk early, its undo information is already safely in the log. If a committed transaction's dirty pages are not forced to disk at commit time, its redo information is already safely in the log.

Crash Recovery with ARIES

When a system crashes and restarts, the database uses the WAL to restore a consistent state. Most modern databases use a recovery algorithm based on ARIES (Algorithms for Recovery and Isolation Exploiting Semantics), which operates in three phases:

  1. Analysis: The database scans the log forward from the last checkpoint to identify which transactions were active at the time of the crash and which dirty pages were in memory.
  2. Redo: The database replays all logged changes from the earliest relevant LSN forward, bringing the database back to its exact state at the moment of the crash. This ensures durability for all committed transactions whose dirty pages had not yet been flushed.
  3. Undo: The database scans backward through the log for any transactions that were active (uncommitted) at the time of the crash and reverses their changes using the before-images. This ensures atomicity.

Checkpoints and Log Truncation

Without periodic maintenance, the WAL would grow indefinitely, and crash recovery would take too long. To prevent this, databases periodically create checkpoints. During a checkpoint, the database flushes dirty pages to disk and records the checkpoint in the log. Once a checkpoint completes, log records prior to the oldest active transaction or dirty page can be safely truncated or archived, keeping recovery times bounded.