Shadow Paging vs Write-Ahead Logging (WAL): How Storage Engines Guarantee Crash Recovery

A database management system (DBMS) must satisfy the Atomicity and Durability properties of ACID. If power is cut in the middle of a multi-megabyte transaction update, the database file on disk must never end up in a half-written, corrupted state upon reboot.

Storage engines achieve crash recovery using one of two primary architectural patterns: Shadow Paging or Write-Ahead Logging (WAL).

1. Shadow Paging

Shadow paging (copy-on-write page management) avoids overwriting existing database pages in place. Instead, it maintains two page tables during a transaction:

• Current Page Table: Points to newly written pages on disk containing uncommitted transaction modifications.
• Shadow Page Table: Points to original, pristine pages on disk representing the last committed state.

During a transaction, any updated page is written to a newly allocated block elsewhere on disk. The Current Page Table is updated to point to the new block, while the Shadow Page Table remains untouched.

[Root Pointer] ----> [Shadow Page Table (Committed State)]
                          |---> Page 1 (Old)
                          |---> Page 2 (Old)

[Active Txn]   ----> [Current Page Table (Uncommitted State)]
                          |---> Page 1 (Old)
                          |---> Page 2' (New Copy on Disk)

The Commit Phase: To commit, the database engine updates a single atomic root pointer on disk (via a single disk sector write or atomic hardware operation) to swap the active pointer to the Current Page Table. Once the pointer flips, the transaction is committed. The old shadow pages are freed to the garbage collector.

Crash Recovery: If power is lost before the root pointer is updated, the database simply boots up reading the old Shadow Page Table pointer. All partial writes are naturally ignored—zero recovery log scanning required.

Used in: LMDB, SQLite (classic rollback journal mode), CouchDB.

2. Write-Ahead Logging (WAL)

In a Write-Ahead Logging system, database pages are updated in memory (buffer pool) and written back to disk in-place. However, before any dirty data page is written to disk, the corresponding modification record must first be written sequentially to a dedicated append-only log file on disk—the WAL log.

1. Append modification record to WAL file on disk: [Txn 101: Set A=50] -> fsync()
2. Mark page dirty in Memory Buffer Pool
3. Async background writer flushes dirty data pages to main DB file in-place

Every log record contains a Log Sequence Number (LSN). Data pages on disk store the LSN of the last update applied to them. The core WAL invariant dictates:

$$ ext{PageLSN}_{ ext{disk}} le ext{FlushedLSN}_{ ext{WAL}}$$

Crash Recovery: The ARIES Algorithm

When a database using WAL boots up after a crash, it executes the 3-phase ARIES recovery process over the log file:

1. Analysis Phase: Scans the WAL forward from the last checkpoint to identify active transactions and dirty pages at the moment of the crash.
2. Redo Phase: Replays all logged modifications forward to restore the database buffer state to the exact instant of the crash.
3. Undo Phase: Rolls back modifications of all uncommitted ("loser") transactions by scanning backward and applying Compensation Log Records (CLRs).

Used in: PostgreSQL, MySQL InnoDB, RocksDB, CockroachDB.

Shadow Paging vs WAL: Tradeoff Matrix

Factor	Shadow Paging (Copy-on-Write)	Write-Ahead Logging (WAL)
Write Pattern	Random I/O (allocating new pages across disk)	Sequential I/O (append-only log writes)
Crash Recovery Time	Instant (flip single root pointer)	Requires log replay (Redo/Undo phase)
Disk Fragmentation	High (pages become scattered over time)	Low (main database file maintains structured layout)
Concurrency	Limited (single writer serialization)	High (MVCC + concurrent log append + dirty page flush)

Summary

Shadow Paging provides instant crash recovery and simplicity, making it ideal for embedded databases (LMDB) and read-heavy workloads. Write-Ahead Logging delivers superior write throughput and high concurrent transaction performance, making it the industry standard for enterprise relational databases (Postgres, InnoDB).