Capstone: old rollback must not erase new commits

T1 commits key=10
T2 writes 99, aborts back to 10
T3 commits key=30
crash

Required result: 30. Why does “undo every noncommitter” produce 10?

1 / 7

Declare the executable model

  • Serial transactions; unique transaction IDs.
  • Four slots per page, map index of live records.
  • Log and page updates persist.
  • Crash loses volatile state; recovery completes atomically.

Repeated crashes between operations are covered. Interrupted rollback is not.

2 / 7

Every write needs its actual before-image

A deleted slot can be reused:

live key 1 → tombstone key 1 → live key 2

Undo in reverse: restore tombstone key 1, then live key 1.

An insertion's previous slot is not always empty.

3 / 7

Undo is a new logged page write

LSN Event
3 T2 update 10 → 99
4 T2 abort requested
5 T2 compensation: after=10
6 T2 rollback complete
7 T3 update 10 → 30
8 T3 commit

Compensation advances pageLSN. Completion prevents undoing T2 again.

4 / 7

Recover using the expanded history

  1. Analyze commits and rollback-complete markers.
  2. Redo original updates and compensation records when newer than pageLSN.
  3. Undo unfinished transactions, generating compensation and completion.
  4. Rebuild the index from live slots.

An abort request alone is not a completed rollback.

5 / 7

Test with a simpler model

Oracle: copy committed map at begin; edit working map; publish on commit; discard on abort/crash.

Test histories with:

  • Abort → later commit → crash.
  • Crash rollback → later commit → another crash.
  • Delete → slot reuse → abort.
  • Repeated crashes with no new operations.

The oracle need not know pages, LSNs, or CLRs.

6 / 7

Defend the boundary

Before adding concurrent transactions, add isolation. Before permitting crashes inside rollback, add resumable undo bookkeeping.

Explain why rebuilding a map index is valid, and why a B+Tree is an optional index replacement rather than part of this exercise's grading contract.

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