Write-Ahead Logging (WAL) & ARIES Crash Recovery: How Databases Guarantee Durability

Suppose your production database server processes 10,000 transaction updates per second.

Writing every modified 16KB data page to disk during a COMMIT statement forces hundreds of random disk page writes per second, causing I/O bottlenecks.

To avoid random disk I/O, database engines keep modified pages in RAM (the Buffer Pool) and write to disk asynchronously in background batches.

Now consider what happens when a physical power outage strikes while 5,000 dirty, modified table pages sit un-written inside server RAM.

When power is restored, how does the database storage engine reconstruct committed data and undo partial uncommitted writes without corrupting tables?

The answer is Write-Ahead Logging (WAL) and the ARIES Crash Recovery Algorithm.

The Fundamental WAL Protocol Rule

Write-Ahead Logging replaces expensive random page writes with fast sequential log writes.

The WAL protocol enforces one mandatory rule:

WAL Protocol Rule: Every modification log record MUST be written and flushed to physical disk (fsync) BEFORE the corresponding dirty data page is written to disk.

=====================================================================
                      WAL PROTOCOL EXECUTION FLOW
=====================================================================
1. User executes UPDATE statement.
2. Engine appends change record to WAL Buffer in memory.
3. Engine flushes WAL Buffer to disk (fsync) during COMMIT.  <--- MUST HAPPEN FIRST!
4. Engine writes dirty 16KB table page to disk later asynchronously.
=====================================================================

If power fails after Step 3, the database recovers committed data by reading the sequential WAL file from disk during startup.

Log Sequence Numbers (LSN)

To coordinate log records with data pages, database engines assign a monotonically increasing 64-bit integer called a Log Sequence Number (LSN) to every operation.

LSNs are tracked across three locations:

LogLSN: The highest LSN written to the WAL log file on disk.
PageLSN: A 64-bit header field inside every 16KB data page recording the LSN of the latest update applied to that specific page.
FlushedLSN: The highest LSN flushed to physical disk storage.

PAGE HEADER (Inside 16KB Data Page)
+-------------------------------------------------------+
| Page Number: 42                                       |
| PageLSN: 10450  <--- Tracks latest update on this page|
+-------------------------------------------------------+

The Flushing Invariant:

A database engine can write Page 42 to disk if and only if:

$\text{PageLSN} \le \text{FlushedLSN}$

This invariant guarantees the log record describing a page change is on disk before the modified page itself touches disk.

The ARIES Crash Recovery Algorithm

When a database server restarts after an abnormal termination, it executes the ARIES (Algorithms for Recovery and Isolation Exploiting Semantics) recovery framework.

ARIES operates in three distinct sequential phases:

                                ARIES 3-PHASE RECOVERY
                                
  CRASH POINT
       |
       v
+-----------------------------------------------------------------------------------+
| PHASE 1: ANALYSIS PHASE                                                           |
| Scans WAL forward from last Checkpoint to reconstruct active transactions & dirty pages |
+-----------------------------------------------------------------------------------+
       |
       v
+-----------------------------------------------------------------------------------+
| PHASE 2: REDO PHASE ("Repeat History")                                            |
| Scans WAL forward to re-apply all committed changes (reconstructs state to crash time) |
+-----------------------------------------------------------------------------------+
       |
       v
+-----------------------------------------------------------------------------------+
| PHASE 3: UNDO PHASE                                                               |
| Scans WAL backward to roll back all uncommitted (loser) transactions              |
+-----------------------------------------------------------------------------------+

Phase 1: Analysis Phase

The engine scans the WAL file forward starting from the most recent Checkpoint LSN:

Reconstructs the Transaction Table: Identifies which transactions were active (uncommitted) at the exact moment of the crash.
Reconstructs the Dirty Page Table: Identifies which data pages in the buffer pool contained un-flushed modifications.

Phase 2: Redo Phase (“Repeating History”)

The engine scans the WAL file forward starting from the lowest RecLSN found in the Dirty Page Table.

It re-applies every logged change (both committed and uncommitted transactions) to bring the database to the exact state it was in at the moment of the crash. This process is called repeating history.

Page LSN Optimization:

Before re-applying a WAL log record to a data page, the engine compares the log record’s LSN against the page’s PageLSN:

$\text{If } \text{LogRecord.LSN} \le \text{Page.PageLSN} \longrightarrow \text{Skip Redo (Change already on disk!)}$

This check prevents redundant page modifications during recovery.

Phase 3: Undo Phase (Rolling Back Loser Transactions)

The engine scans the WAL file backward to undo the effects of all loser transactions (transactions that were active at crash time and never committed).

For every undone operation, the engine writes a Compensation Log Record (CLR) to the WAL.

UNDO RECOVERY REVERSE SCAN:
Log Record: Tx 101 Update Page 42 -> Write CLR record & restore old page bytes!
Log Record: Tx 101 Update Page 18 -> Write CLR record & restore old page bytes!
Tx 101 Undo Complete!

Why Compensation Log Records (CLRs) Matter:

If another power crash occurs during the Undo Phase, CLR records prevent the engine from attempting to undo an operation that was already undone, guaranteeing idempotent recovery.

Checkpointing: Bounding Recovery Time

If a database runs for months without purging old WAL logs, crash recovery would require scanning terabytes of historical logs.

Database engines perform Checkpointing periodically:

Write a CHECKPOINT_START record to WAL.
Flush dirty pages from Buffer Pool to disk.
Write a CHECKPOINT_END record to WAL recording current active transactions and Dirty Page Table state.
Truncate old WAL log files prior to the checkpoint.

Checkpointing bounds crash recovery times to seconds rather than hours.

Quick Summary

Write-Ahead Logging (WAL) requires log records to touch disk (fsync) before corresponding table pages can be written.
Log Sequence Numbers (LSNs) coordinate log entries with page states (PageLSN <= FlushedLSN).
ARIES crash recovery executes 3 phases: Analysis (reconstruct state), Redo (repeat history), and Undo (roll back uncommitted loser transactions).
Compensation Log Records (CLRs) ensure crash recovery itself is idempotent and safe against repeated failures.

References & Further Reading

O’Neil, P., O’Neil, E., & Weikum, G. (1996). The Log-Structured Merge-Tree (LSM-Tree). Acta Informatica, 33(4), 351–385.
Meta Open Source. RocksDB Architecture Wiki: Leveled Compaction & Write Amplification Analysis. GitHub.
Sears, R., & Ramakrishnan, R. (2012). bLSM: A General Purpose Log Structured Merge Tree. ACM SIGMOD, 217–228.