Capstone: Make Rollback Part of Durable History

The earlier recovery exercise reconstructs one crash snapshot. A storage engine must also continue processing transactions afterward. That difference exposes a dangerous bug: an old undo action can erase a newer committed write.

Build the mini-db exercise as an integration of slot identity, physical update logging, rollback, and index reconstruction. The graded index is a map from key to record location. Replacing it with your B+Tree is an optional extension.

State the model before claiming correctness

The engine processes serial transactions, with at most one active transaction and no reused transaction IDs. Pages have four fixed record slots. Each operation finishes atomically; log appends and page modifications are durable. A crash removes the in-memory index and active-transaction state, then runs recovery atomically to completion.

These assumptions let you reason about repeated crashes between operations. They do not simulate crashes inside rollback, partial log records, concurrent transactions, or torn page writes. The lock-manager primitive is therefore not wired into this capstone; serial execution supplies isolation.

The required behavior is concrete: committed updates survive crashes, unfinished updates disappear after a crash, abort restores the previous state, and later commits are not damaged by old aborted history. If the input ends with an active transaction and no crash/abort, return its current visible writes too; this is a simulator of current state, not a read-committed client API.

Three representations must agree

A page slot contains (Key, Val, Tombstone, Valid). A slot with !Valid or a tombstone is reusable. A page LSN tracks its latest logged write. The index maps only live records to their page/slot locations.

For a put, locate the existing live slot or choose the lowest available page and slot. Save the actual prior record, append the update log record, then write the after-image and advance the page LSN. The index points to that slot. For delete, write a tombstone and remove the index entry.

The actual prior record matters when a deleted slot is reused. Suppose a transaction deletes key 1, inserts key 2 into that same slot, then aborts. Undo must restore the tombstoned key 1 record for the insertion, then restore live key 1 for the deletion. “Insertion always has an empty before-image” is not a valid invariant once slots can be reused.

After abort or recovery, rebuild the index by scanning all live slots. This avoids trusting an index whose locations may reflect writes just undone. A record-location map is derived state; the logged page contents are the evidence.

The regression that a single-crash test misses

Follow one key:

Transaction / event	Action	Visible value
T1	Put 10, commit	10
T2	Put 99	99
T2	Abort and restore before-image	10
T3	Put 30, commit	30
Crash	Rebuild from durable history	must be 30

A recovery implementation that undoes every update whose transaction lacks a commit will find T2 and restore 10 again. It has treated “never committed” as “still needs rollback.” Those are different facts.

A boolean flag in memory is insufficient: the next crash loses it. Completion of rollback must become durable history. Its page changes also need fresh LSNs so their ordering is represented correctly.

Log undo as a new write

For every original update being reversed, append a compensation log record (CLR) with a new LSN and an after-image equal to that update's before-image. Apply the CLR like a page write: replace the slot and advance pageLSN. After all updates of that transaction have been reversed, append an end marker.

For the example above, abbreviating begin records away:

LSN	Record	Page value after applying it
1	T1 update 0 → 10	10
2	T1 commit	10
3	T2 update 10 → 99	99
4	T2 abort requested	99
5	T2 CLR, after=10	10
6	T2 rollback end	10
7	T3 update 10 → 30	30
8	T3 commit	30

Undo at LSN 5 is later history than the original write at LSN 3. PageLSN advances to 5, not backward to 3. The rollback-end marker means T2 is finished; it must not be undone again at the later crash.

CLRs are redoable and are not themselves undone. Their use follows the recovery principle in the original ARIES paper, section 3. Full ARIES also supports resuming interrupted rollback using undo-next links. This capstone omits those links because recovery and abort are atomic input operations; do not claim that it implements all of ARIES.

Derive recovery from the new log

First identify transactions with commit records and transactions with completed rollback (end). Both are finished. An abort request alone does not imply completion: it describes intent before all compensating writes are applied.

Next redo original updates and CLRs, in LSN order, if newer than each page's LSN. Finally, undo original updates of unfinished transactions in reverse order, appending new CLRs and an end marker. Rebuild the index from live slots.

In this simulator all page updates already persist, so many redo comparisons will skip. Retain the redo rule anyway: it explains what evidence each page LSN represents and keeps the log/page model explicit. To genuinely test missing page writes as well, a future API would need separate persistence events.

The same rollback helper should serve explicit abort and recovery. They differ in what selected the loser, not in how an update is compensated. On a later crash, the helper's end record prevents the transaction from being selected again.

Check invariants across module boundaries

After every logged page write, pageLSN equals that write's LSN and its slot matches the after-image. After rollback completes, the transaction's before-state is restored, a completion marker exists, and the index points only at live slots. After recovery, no unfinished transaction remains active.

Commit records and rollback-end records have no page write of their own. Do not set every page's LSN to the last record in the whole log: pageLSN is local to that page's history.

Deterministic allocation helps make traces reproducible. Go map iteration order is not a page-allocation policy; scan page IDs and slots in an explicit order. Correct output should not depend on which map entry happens to be visited first.

Test behavior with a simpler oracle

A useful independent oracle needs no pages or log records. Keep a committed key/value map. At begin, copy it into a working map. Apply puts/deletes there. Commit replaces the committed map; abort or crash discards working changes. Generate valid serial histories with repeated updates, deletes, slot reuse, and crashes. Compare the engine's visible result after each completed transaction with this snapshot model.

This tests the result of the architecture without duplicating its LSN and undo implementation. Also keep small named regressions: abort → new commit → crash; crash rollback → new commit → another crash; delete → reuse → abort; consecutive crashes with no new work. A test that only inserts an uncommitted new key and crashes cannot distinguish these failure modes.

Reconstruct and check

1. Why not mark aborted transactions finished immediately?

Answer: A durable decision to abort can precede the compensating writes. Completion means all rollback work is finished, not merely requested. The atomic operation model simplifies interruption, but the record meanings should remain precise.

2. T1 rolls back at LSN 20; T2 writes the same slot at LSN 24 and commits. Should T1's original before-image be applied after a crash?

Answer: No. T1's end record excludes it from new undo; any redoable compensation is ordered before T2's LSN 24. The final value is T2's.

3. A transaction inserts six keys, deletes two, then aborts. What must happen to newly allocated empty pages?

Answer: The API does not require deallocating them. It requires their live records and index entries to reflect rollback. Physical space reclamation is a separate feature from transactional visibility.

4. What would invalidate the current proof?

Answer: Allowing a second transaction to overwrite an unresolved first transaction, or crashing halfway through rollback, introduces cases outside the declared model. Add isolation or resumable recovery state before making those guarantees.