Write-Ahead Logging (WAL) for Crash Recovery

In an ideal world, database servers would never crash, memory would never lose power, and physical disks would commit modifications instantaneously.

In reality, database servers crash unpredictably, power cuts cause abrupt halts, and dirty memory pages can be lost in milliseconds.

To guarantee ACID Durability without sacrificing performance, modern databases (PostgreSQL, MySQL InnoDB, SQLite, CockroachDB, RocksDB) rely on a fundamental architectural invariant: The Write-Ahead Log (WAL).

---

1. The Core Invariant: Why Write-Ahead Logging is Mandatory

The fundamental invariant of Write-Ahead Logging is:

$\text{No database page modification in memory may be written to physical table storage until the corresponding WAL record has been flushed to persistent storage via fsync().}$

The Buffer Pool Dilemma: Steal vs Force Policy

Database buffer managers are categorized by two orthogonal architectural policies (Haerder & Reuter, 1983):

Modern high-performance engines use a STEAL / NO-FORCE policy:

• NO-FORCE requires REDO logging (to reconstruct committed transactions whose dirty pages were still in RAM during a crash).
• STEAL requires UNDO logging (to rollback uncommitted transaction data that was flushed to disk before the crash).

---

2. Anatomy of a WAL Record

Every WAL record represents an atomic delta of state and contains strict metadata for ordering and integrity:

Log Types: Physical vs Logical vs Physiological Logging

1. Physical Logging: Stores raw before-and-after byte images of disk pages. High disk overhead, but completely deterministic and idempotent.
2. Logical Logging: Stores SQL statements (e.g. UPDATE accounts SET balance = balance - 50). Compact, but non-deterministic if triggers, timestamps, or subqueries are involved.
3. Physiological Logging (Industry Standard): Logical operations applied to physical pages (e.g. "In Page 42, insert tuple at slot 3"). Used by PostgreSQL and InnoDB for optimal balance of compactness and recovery safety.

---

3. Checkpointing: Bounding Recovery Time

If a database ran for 3 years without maintenance, the WAL file would be petabytes in size, and recovering from a crash would require days of replaying history.

Checkpointing is the process of synchronizing all dirty memory pages with disk so that older WAL segments can be safely truncated.

Fuzzy Checkpointing (Non-Blocking):

Modern databases cannot freeze all queries while flushing gigabytes of RAM to disk. Instead, they use Fuzzy Checkpoints:

1. Write a BEGIN_CHECKPOINT record to the WAL.
2. Capture a snapshot of the Dirty Page Table (DPT) and Active Transaction Table (ATT).
3. Allow ongoing queries to continue mutating pages while background writer threads flush dirty pages to disk asynchronously.
4. Once all dirty pages referenced at the start are flushed, write an END_CHECKPOINT record.
5. On crash recovery, replay only needs to start from the oldest unwritten page recorded in the snapshot (CheckPoint_LSN).

---

4. The ARIES Recovery Algorithm

The gold standard for database crash recovery is the ARIES (Algorithm for Recovery and Isolation Exploiting Semantics) algorithm developed by C. Mohan at IBM Research.

ARIES executes in 3 sequential phases:

Compensation Log Records (CLRs):

What happens if the database crashes while it is executing crash recovery? To prevent infinite crash-recovery loops, ARIES writes a Compensation Log Record (CLR) for every undone operation. CLRs are never undone, guaranteeing that recovery always makes monotonic forward progress.

---

5. Code Deep-Dive: Append-Only Write-Ahead Log Engine

---

6. Production Failure Postmortem: The Torn Page WAL Checksum Failure

Incident Overview:

In 2021, an enterprise analytics cluster suffered severe data corruption across its primary replica following an emergency generator failover during a power outage.

What Happened:

1. The server power cut occurred while the database was mid-way through writing an $8\text{KB}$ page to disk.
2. The NVMe controller wrote $4\text{KB}$ of new data and $4\text{KB}$ of garbage (a Torn Write / Torn Page).
3. On restart, the database engine lacked page-level checksum verification and attempted to replay the partially written WAL record.
4. The half-applied binary struct corrupted internal index pointers, causing the storage engine to segfault immediately upon boot.

Key Lesson:

• Never trust sector writes to be atomic across power cuts. Production storage engines must use CRC32 Checksums on every WAL header and maintain a Doublewrite Buffer (like MySQL InnoDB) or Full-Page Writes (like PostgreSQL full_page_writes = on) to detect and heal torn pages during crash recovery.

---

7. Chapter Summary & WAL Invariant Checklist