Crash Recovery — Replaying the Log

The WAL's true purpose isn't logging — it's recovery. When the database restarts after a crash, the WAL is the single source of truth for restoring consistency.

The ARIES Recovery Algorithm

Most databases use a variant of ARIES (Algorithm for Recovery and Isolation Exploiting Semantics), developed at IBM. It has three phases:

1. ANALYSIS  — Scan WAL to find active transactions at crash time
2. REDO      — Replay ALL logged changes (committed + uncommitted)
3. UNDO      — Reverse changes from uncommitted transactions

REDO Phase

REDO replays the log forward, reapplying every change:

WAL Records:
  LSN=1: Txn1 INSERT into users (1, 'Alice')
  LSN=2: Txn2 INSERT into users (2, 'Bob')
  LSN=3: Txn1 COMMIT
  LSN=4: Txn2 UPDATE users SET name='Robert' WHERE id=2
  --- CRASH ---

REDO: Apply LSN 1, 2, 3, 4 in order
After REDO: Both inserts and the update are applied

REDO must be idempotent — applying the same change twice has the same effect as applying it once. This is critical because we don't know exactly which changes made it to disk before the crash.

UNDO Phase

After REDO, uncommitted transactions must be reversed:

After REDO:
  Txn1: COMMITTED (LSN=3 has COMMIT record) → keep changes
  Txn2: NO COMMIT record → UNDO all Txn2 changes

UNDO: Reverse LSN=4 (update), then LSN=2 (insert)
After UNDO: Only Alice remains, Bob is gone

Why REDO Then UNDO?

Why not just skip uncommitted changes during REDO? Because a committed transaction might have modified a page that an uncommitted transaction also modified. REDO restores all pages to their crash-time state, then UNDO cleanly removes just the uncommitted changes.

Compensation Log Records (CLRs)

During UNDO, the database writes CLR records for each undo operation. If the system crashes again during recovery, CLRs prevent re-undoing the same operations:

UNDO LSN=4 → write CLR: "Undid LSN=4"
If crash during UNDO, restart:
  REDO: Apply everything including CLR
  UNDO: Skip LSN=4 (CLR says it's already undone)

How SQLite Does Recovery

SQLite's WAL recovery is simpler than ARIES. On startup, it finds the last valid commit frame in the WAL and discards everything after it. There's no explicit UNDO — uncommitted data simply isn't copied to the database file.

Your Task

Implement CRASH (clears all in-memory data) and RECOVER (replays the WAL to restore committed data while rolling back uncommitted changes).