Recovery has two different jobs

  • No-force: committed data may be missing from disk → redo.
  • Steal: uncommitted data may be present on disk → undo.

Durable WAL must precede the corresponding page write.

1 / 8

Name the evidence

  • LSN orders log records.
  • PageLSN describes one page's persisted write history.
  • Commit status belongs to a transaction.

A high pageLSN does not prove the transaction committed.

2 / 8

Predict this recovery

Persisted page: x=7, y=0, LSN=5.

LSN Transaction Update or outcome
2 T1 x: 0 → 4
3 T1 commit
5 T2 x: 4 → 7
6 T2 x: 7 → 9
8 T3 y: 0 → 6
9 T3 commit

Which transactions win? Which updates redo? Which updates undo?

3 / 8

Three passes, three selections

  1. Analysis: winners T1, T3; loser T2.
  2. Redo: skip 2 and 5; apply 6 and 8 → x=9, y=6.
  3. Undo: reverse 6 then 5 → x=4, y=6.

The toy output pageLSN is 5. Its simplified undo rule is not a production page-history convention.

4 / 8

Reverse order is necessary

Loser writes: 4 → 7 → 9.

  • Reverse undo: 9 → 7 → 4.
  • Forward undo: 9 → 4 → 7 — wrong final value.

Each before-image reverses one update, not the whole transaction.

5 / 8

Redo idempotence does not prove restartable undo

T1 commits x=4
T2 writes x=9, then aborts to x=4
T3 commits x=12
crash

Undoing every historical noncommitter would restore 4 over 12.

What durable fact is missing?

6 / 8

Log rollback as new history

  • Compensation log record: new LSN, redoable after-image.
  • Completed rollback marker: exclude that transaction from future undo.
  • Full ARIES also records how interrupted undo resumes.

The standalone exercise is one recovery pass. The capstone adds completed rollback history and keeps recovery calls atomic.

7 / 8

Implementation checkpoint

  • Deep-copy input page slices.
  • Compare each update against its own page's LSN.
  • Redo winners and losers; undo only losers.
  • Write changed Page structs back into the map.

Explain why an already-persisted loser skips redo but still requires undo.

8 / 8
←/→ or click edges to navigate · ? help · N notes · F fullscreen