Database Recovery: WAL & The ARIES Protocol

Module Overview

Operating systems crash, power grids fail, and servers unexpectedly reboot. A production database must be architected so that committed transactions are never lost, and uncommitted transactions leave zero trace upon restart. In this ninth installment, we analyze the engineering of database resilience: storage buffer management policies (Steal vs. No-Steal, Force vs. No-Force), Write-Ahead Logging (WAL), and the legendary ARIES Recovery Protocol with its three-pass Analysis, Redo, and Undo algorithms.

1. Buffer Pool Management Policies: Steal & Force

The design of a database crash recovery engine is dictated by how its buffer pool interacts with non-volatile disk blocks during transaction execution:

Steal vs. No-Steal (Atomicity)

Steal Policy: The buffer pool manager is permitted to write dirty pages modified by an uncommitted transaction to disk to free up frame memory for other queries. (Requires Undo Logging to reverse partial writes on crash).

No-Steal: Dirty pages can never be written to disk until the transaction commits, severely constraining memory when large transactions exceed RAM capacity.

Force vs. No-Force (Durability)

No-Force Policy: At transaction commit time, the DBMS is not required to synchronously flush all modified table pages to disk before acknowledging success. (Requires Redo Logging to replay missing updates on restart).

Force: Every transaction commit synchronously flushes all its dirty pages to disk, inducing catastrophic random I/O bottlenecks.

Virtually all high-performance enterprise database engines (PostgreSQL, MySQL InnoDB, Oracle, SQL Server) implement the STEAL + NO-FORCE architectural combination, which delivers maximum runtime throughput but necessitates a sophisticated crash recovery subsystem.

2. The Write-Ahead Logging (WAL) Protocol

Under the Write-Ahead Logging (WAL) protocol, any change to a database page must first be recorded in an append-only sequential log on non-volatile storage before the corresponding dirty page can be written to disk.

The Fundamental WAL Invariant

pageLSN ≤ flushedLSN

Before page $P$ is flushed from the buffer pool to disk, the log file on disk must be flushed up to at least the Log Sequence Number ($LSN$) recorded in page $P$'s header.

3. The ARIES Recovery Algorithm

Developed by C. Mohan at IBM in 1992, ARIES (Algorithms for Recovery and Isolation Exploiting Semantics) is the industry-standard crash recovery methodology. Upon server reboot following a catastrophic failure, ARIES executes three sequential passes over the persistent log:

Pass 1: Analysis Pass (Scan Forward from Checkpoint)

Scans forward from the most recent checkpoint record to the end of the log. It reconstructs the internal state at the moment of the crash: determining which transactions were active and uncommitted (the Losers set), and determining the smallest RecLSN across all dirty pages in the Dirty Page Table (DPT) where redo must begin.

Pass 2: Redo Pass (Repeating History)

Scans forward from the smallest RecLSN identified during Analysis, replaying the exact sequence of actions recorded in all log entries—reapplying updates for both committed transactions and loser transactions. This restores the database to the exact byte-level state it occupied immediately preceding the crash.

Pass 3: Undo Pass (Rolling Back Losers)

Scans backward from the end of the log, reversing all modifications made by active transactions that had not committed before the crash. For every undone action, it writes a Compensation Log Record (CLR) to the log. CLRs prevent cyclic work: if the database crashes a second time during the undo phase, the recovery process never re-undoes previously undone operations!

Next in Curriculum

In our final capstone installment, Part 10: Distributed Databases: Partitioning, Sharding, 2PC & CAP Theorem, we analyze distributed database architecture, horizontal sharding, consensus protocols, and CAP trade-offs.