Atomicity: Undo Logging & Rollback

Building a Database Engine: Transactions & Concurrency

Chapter 4 · Atomicity: Undo Logging & Rollback

This course opened with a real, verified bug: a two-step insert — write the row, then update the index — that leaves the table and its own index silently disagreeing if anything interrupts it between the two steps. Chapters 2 and 3 closed the durability half of that story: a crash before a write is applied is now recoverable. But Chapter 1's own original scenario wasn't a crash — it was one step succeeding and the next one failing outright. This chapter closes that half: wrap the whole operation in a transaction, and if any part of it fails, undo everything that already happened.

A Real Undo Log

Where Chapter 2's WAL recorded each page's new content, an undo log records each page's old content — captured the first time, and only the first time, a transaction touches it:

class Transaction:
    def __init__(self):
        self.undo_log = []      # [(file_name, page_num, old_bytes_or_None), ...]
        self.touched = set()    # {(file_name, page_num)} -- captured ONCE per page

    def record_write(self, file_name, real_heap_file, page_num):
        key = (file_name, page_num)
        if key in self.touched:
            return                # already captured -- this write doesn't need a new record
        if page_num < real_heap_file.num_pages():
            old_bytes = bytes(real_heap_file.read_page(page_num).data)
        else:
            old_bytes = None       # this page didn't exist before the transaction touched it
        self.undo_log.append((file_name, page_num, old_bytes))
        self.touched.add(key)

    def commit(self):
        self.undo_log = []; self.touched = set()      # discard -- the changes stand

    def rollback(self, real_heap_files):
        for file_name, page_num, old_bytes in reversed(self.undo_log):
            heap_file = real_heap_files[file_name]
            if old_bytes is not None:
                heap_file.write_page(page_num, load_page(old_bytes))
            else:
                heap_file.write_page(page_num, Page())    # blank it -- see below
        self.undo_log = []; self.touched = set()
    

Making the write side of every table transparently participate needs no changes at all to Course 1's own HeapTable — only a thin wrapper implementing the exact same interface, so HeapTable genuinely has no idea it's being run inside a transaction:

class TransactionalHeapFile:
    def __init__(self, real_heap_file, transaction, file_name):
        self.real = real_heap_file
        self.transaction = transaction
        self.file_name = file_name
    def num_pages(self): return self.real.num_pages()
    def read_page(self, page_num): return self.real.read_page(page_num)
    def write_page(self, page_num, page):
        self.transaction.record_write(self.file_name, self.real, page_num)
        self.real.write_page(page_num, page)
    def allocate_page(self):
        page_num = self.num_pages()
        self.write_page(page_num, Page())   # goes through OUR write_page -- captured too
        return page_num
    

Finding 1: Commit Keeps Changes, Rollback Fully Undoes Them

Verified directly — two independent pages, rolled back cleanly

A transaction writes new content to two different pages, then rollback() is called instead of commit(). Both pages come back byte-for-byte identical to their state before the transaction began — the writes are genuinely undone, not merely left inconsistent.

Finding 2: First-Touch Capture Restores the TRUE Original, Not an Intermediate State

A single transaction writes to the same page twice — once with content V1, then again with different content V2.

Verified directly — one undo record, not two

The undo log ends up with exactly 1 entry for that page, not 2 — the second write finds the page already in self.touched and skips capturing anything. After rollback(), the page matches its true pre-transaction state exactly, and is confirmed not equal to V1 — the intermediate state the page passed through partway through the transaction. Capturing on first touch only means rollback always reaches all the way back to where the transaction began, no matter how many times a page was rewritten along the way.

Finding 3: The Payoff — Genuinely Resolving Chapter 1's Own Bug

Chapter 1's own opening scenario, unmodified: insert a row, then update an index for it. This time, both steps run inside a transaction, and the index update is made to fail on purpose.

def transactional_insert_with_index(txn, real_heap_file, schema, values, index_root, should_fail):
    thf = TransactionalHeapFile(real_heap_file, txn, 'accounts')
    table = HeapTable(thf, schema)              # Course 1's own HeapTable, completely unmodified
    location = table.insert(values)             # STEP 1 -- goes through the transactional wrapper
    if should_fail:
        raise RuntimeError("simulated failure updating the index")
    new_root = btree_insert(index_root, values[0], location)   # STEP 2
    return location, new_root

txn = Transaction()
try:
    transactional_insert_with_index(txn, real_heap, schema, [2, 'Bob', 300], index_root, should_fail=True)
except RuntimeError:
    txn.rollback({'accounts': real_heap})
    

Verified directly — the row was never inserted, as far as the table can tell

After catching the exception and calling rollback(), a real scan() of the table finds zero rows. Compare this against Chapter 1's own Finding 1, where the exact same interrupted-operation shape left a row genuinely, permanently present but unindexed. Here, the row insertion itself is undone along with everything else — the table is back to exactly where it was before the attempt, with no inconsistency at all. Running the same operation with should_fail=False and calling commit() instead confirms the successful path still works correctly too: the row is present, and the index correctly points at its real location.

Finding 4: Why a Non-Deduped Undo Log Must Replay in Reverse

This chapter's own Transaction class sidesteps a subtle ordering problem entirely, by construction, since it never keeps more than one undo record per page. A log that captures every write — not just the first one per page — doesn't get that guarantee for free.

Verified directly — forward-order replay leaves the page at an intermediate state

Two writes to the same page (V1, then V2) are logged without deduplication — two separate undo entries: (before V1) and (before V2, i.e. V1). Replaying them in the order they were captured — the natural-looking first instinct — applies (before V1) first, then (before V2), landing the page on V1, not the true original. Replaying the exact same two records in reverse order lands correctly on the true pre-transaction state. "Undo" means walking history backward — a log that isn't already deduplicated to one entry per page depends on that being done explicitly, not assumed.

Where This Connects

This chapter's finding	What it connects to
Genuinely atomic insert-plus-index-update	Chapter 1 (this course) — the exact scenario opened there is fully resolved here, closing the loop this entire course started with
Reverse-order replay for a non-deduped log	Chapter 3's own `recover()` — a structurally similar "replay records in the right order" concern, though redo (Chapter 3) and undo (this chapter) need opposite orderings for the same underlying reason
A newly-allocated page that can't be shrunk back on rollback	An honest, deliberate scope limitation of this engine — real systems solve this with a free-page/deallocation map, not attempted here

Hands-On Exercises

Exercise 1

Within a transaction, allocate a brand-new page (via TransactionalHeapFile.allocate_page()) and write a row to it, then call rollback(). Confirm num_pages() does not shrink back down (the file itself can't reclaim the space), but the page's own content is blanked and a real scan() finds no rows there.

📄 View solution

Exercise 2

Within a transaction, read a page (via TransactionalHeapFile.read_page()) but never write to it, then write to a different page and roll back. Confirm the undo log contains exactly one entry — for the written page only — and that the read-only page's own real content is completely unaffected by the rollback.

📄 View solution

Exercise 3

Write to the same page three times within one transaction (three genuinely different contents), then roll back. Confirm the undo log still contains only one entry (not three), and that the page ends up matching its true pre-transaction state, not any of the three intermediate versions.

📄 View solution

Chapter 4 Quick Reference

Undo log: captures each page's before-image, but only on its first touch within a transaction
rollback(): restores every touched page to its pre-transaction state, in reverse order
Verified Finding 1: rollback fully undoes writes across multiple pages
Verified Finding 2: first-touch capture restores the TRUE original, not an intermediate state, no matter how many times a page was rewritten
Verified Finding 3 — the payoff: wrapping Chapter 1's own insert-plus-index-update in a transaction and rolling back on failure leaves the table genuinely, completely unchanged — no more silent index/data inconsistency
Verified Finding 4: a non-deduped undo log MUST replay in reverse order, or it lands on an intermediate state instead of the true original
Next chapter: Isolation, Part 1 — locking, and a real, verified deadlock