Isolation, Part 1: Locking

Building a Database Engine: Transactions & Concurrency

Chapter 5 · Isolation, Part 1: Locking

Every chapter so far has run one operation at a time, alone, then checked what a crash or a failure would have done to it. Isolation is a genuinely different question: what happens when two operations run at the same time, for real? This chapter uses real Python threads — not a simulation of concurrency, actual concurrent execution — to reproduce a genuine race condition, fix it with real locks, and then reproduce a genuine deadlock.

A Real Lock Manager: Shared and Exclusive

class LockManager:
    def __init__(self):
        self.cond = threading.Condition(threading.Lock())
        self.exclusive_holder = {}   # page_key -> txn_id
        self.shared_holders = {}     # page_key -> set(txn_id)

    def acquire_shared(self, page_key, txn_id):
        with self.cond:
            while True:
                holder = self.exclusive_holder.get(page_key)
                if holder is None or holder == txn_id:
                    self.shared_holders.setdefault(page_key, set()).add(txn_id)
                    return
                self.cond.wait()      # someone else holds it EXCLUSIVELY -- wait

    def acquire_exclusive(self, page_key, txn_id):
        with self.cond:
            while True:
                holder = self.exclusive_holder.get(page_key)
                sharers = self.shared_holders.get(page_key, set()) - {txn_id}
                if (holder is None or holder == txn_id) and not sharers:
                    self.exclusive_holder[page_key] = txn_id
                    return
                self.cond.wait()      # someone else holds it, shared or exclusive -- wait
    

Shared locks (for reads) can be held by multiple transactions on the same page at once. An exclusive lock (for writes) needs the page completely to itself — no other shared or exclusive holder at all.

Finding 1: A Real, Reproducible Lost Update

Five real threads, each incrementing one shared counter twenty times — read the current value, sleep briefly (to force a genuine interleaving window), write back value + 1. No locking at all.

Verified directly — real increments genuinely go missing

Expected final value: 100 (5 threads × 20 increments). Actual measured result: as low as 20, varying run to run — always short of 100. This isn't a theoretical risk described in the abstract; it's a real, measured shortfall. Two threads reading the same value before either has written its own increment back means one thread's update is silently overwritten by the other's — a genuine lost update, reproduced on demand.

Finding 2: The Same Test, Correct Every Time With a Real Lock

Verified directly — an exclusive lock held across the whole read-modify-write cycle

The identical test, with lock_mgr.acquire_exclusive('counter', txn_id) held from just before the read to just after the write, and released only then: the final value is 100 — exactly correct, every single run. Holding the lock across the entire critical section, not just the write itself, is what closes the gap Finding 1 exploited.

Finding 3: Shared Locks Overlap, Exclusive Locks Serialize

Four threads each hold a lock on the same page for a fixed 0.15-second duration — once with a shared lock, once with an exclusive lock — measuring real wall-clock time for all four to finish.

Verified directly — real timing confirms the two lock modes behave completely differently

Four threads holding a shared lock: real elapsed time ≈ 0.151s — essentially one hold-duration, since all four genuinely overlap. Four threads holding an exclusive lock: real elapsed time ≈ 0.602s — close to four hold-durations, since each one has to wait for the previous one to finish. The two lock modes aren't just conceptually different — they produce measurably different real-world timing.

Finding 4: A Real, Reproducible Deadlock

Two transactions, each locking one page first, then trying to lock the other's page — the classic circular-wait shape. Transaction A locks page 1, then tries for page 2. Transaction B locks page 2, then tries for page 1.

Verified directly — both sides genuinely stuck, confirmed via a bounded timeout

Both transactions' second lock attempt uses a 1-second timeout (since a real test can't wait forever to prove something never finishes). Both attempts report failure — neither one acquires its second lock — and the real elapsed time is ≈1.0s, matching the timeout exactly rather than resolving early. Each transaction is waiting for a lock the other one holds, and neither will release what it's already holding until it gets what it's waiting for. Without a timeout, this genuinely never resolves on its own.

Finding 5: Wait-for-Graph Detection Catches the Cycle Immediately

A deadlock detector doesn't need to wait for anything to time out — it needs to notice, at the moment a transaction is about to wait, that doing so would close a cycle: "I'm about to wait for you, and you're already waiting for me."

def _creates_cycle(self, waiter, blockers):
    visited = set()
    stack = list(blockers)
    while stack:
        node = stack.pop()
        if node == waiter:
            return True          # found our way back to ourselves -- a cycle
        if node in visited:
            continue
        visited.add(node)
        stack.extend(self.waits_for.get(node, set()))
    return False
    

Verified directly — one side aborted instantly, the other proceeds without ever waiting on a timeout

The same two-transaction setup as Finding 4, but each acquire call now checks _creates_cycle() before blocking. Transaction A gets there first, finds no cycle, and legitimately starts waiting for page 2. Transaction B's own attempt for page 1 is checked next: the wait-for graph shows A is already waiting on B, so B waiting on A would close the loop — detected immediately, and B's call raises rather than blocking. B releases the one lock it does hold (the same real action rollback() from Chapter 4 would take for an aborted transaction), which wakes A up, and A's own attempt succeeds. Real elapsed time: ≈0.001s — nowhere near the 1-second timeout Finding 4 needed to prove its own point.

Where This Connects

This chapter's finding	What it connects to
The lost-update race condition	Chapter 1 (this course) — the third named, still-untested ACID gap ("two operations running at the same time") is finally exercised for real, with real threads, in this chapter
Aborting the deadlock's losing side by releasing its locks	Chapter 4 (this course) — a real, concrete instance of exactly what `rollback()` is for: undoing a transaction's own work when it can't be allowed to continue
Real threading used to reproduce a genuine race condition	Design Patterns (this site's Software Development subject) — the same technique (real threads, a deliberate sleep to force interleaving) reproduced a genuine Singleton race condition there

Hands-On Exercises

Exercise 1

Have one thread acquire a shared lock on a page and hold it for 0.3 seconds, while a second thread waits for the first to actually have the lock and then tries to acquire an exclusive lock on that same page. Measure how long the second thread's own acquire call takes, and confirm it genuinely blocks for close to the full 0.3 seconds rather than succeeding immediately.

📄 View solution

Exercise 2

Reproduce a deadlock among three transactions instead of two — A waits on B, B waits on C, C waits on A, closing a longer cycle. Use a real threading.Barrier to guarantee all three first locks are granted before any second attempt begins, and confirm all three attempts genuinely time out.

📄 View solution

Exercise 3

Have two transactions each need locks on the same two pages, but have both transactions acquire them in a single, consistent global order (e.g., always sorted by page key) rather than in whatever order each transaction happens to want them. Confirm both transactions succeed quickly, with no deadlock and no detector needed at all.

📄 View solution

Chapter 5 Quick Reference

Shared lock: many transactions can hold it on the same page at once (reads)
Exclusive lock: only one transaction can hold it, and no one else can hold any lock at all on that page (writes)
Verified Finding 1: a real, reproducible lost update — concurrent read-modify-write with no locking genuinely loses increments
Verified Finding 2: the same test is correct every time once an exclusive lock covers the whole critical section
Verified Finding 3: shared locks overlap in real elapsed time; exclusive locks serialize
Verified Finding 4: two transactions locking pages in opposite orders genuinely deadlock — confirmed by both sides staying blocked past a bounded timeout
Verified Finding 5: a wait-for-graph detector catches the cycle immediately and aborts one side, rather than waiting on any timeout at all
Next chapter: Isolation, Part 2 — MVCC, a real alternative to locking altogether