DBMS internals

1 · ACID — the correctness contract

Here's the story that makes this whole chapter urgent. You transfer $30 from Alice to Bob. The code debits Alice, and then — the instant before it credits Bob — the server loses power. Reboot. Alice is out $30 and Bob never got it; $30 has simply vanished from the world. That is not a hypothetical: it is the exact failure that every bank, every ledger, every "confirm your order" button would suffer if the database underneath didn't make a very specific promise. ACID is that promise, and it's why you trust a database with money in a way you'd never trust a plain file.

The everyday analogy is a group text you can un-send. Imagine you could type five messages, and either all five get delivered together the moment you hit send, or — if you change your mind — none of them ever existed. No half-sent, no "I saw the first three but not the rest." That all-or-nothing delivery is the heart of a transaction: a bundle of changes the database treats as a single indivisible unit, not as the individual reads and writes it's actually made of.

Why it earns four separate letters, and the mistake beginners make. The common trap is to assume "the database saved it, so I'm safe" — as if writing data were one atomic act. It isn't. There are four distinct ways a group of operations can go wrong, and a real guarantee has to close all four holes: the transfer can apply half-way (atomicity), it can leave a rule broken like an order pointing at a product that no longer exists (consistency), it can collide with someone else's transaction running at the same millisecond (isolation), or it can be acknowledged and then evaporate in a crash (durability). Miss any one and you get silent, hard-to-reproduce corruption — the worst kind of bug, because it passes every test and only shows up under real load with real money. ACID names each hole so you can reason about which one a given design actually plugs.

A transaction is a group of operations that must behave as one unit. ACID is the four-part guarantee a relational database makes about transactions: Atomicity (all-or-nothing — no half-applied transfer), Consistency (it moves the database from one valid state to another, honouring constraints), Isolation (concurrent transactions don't corrupt each other), and Durability (once committed, it survives a crash — the job of the WAL in §5).

atomicity.py# MODEL: a transaction buffers changes and applies them ALL on commit, or
# discards them ALL on rollback. That all-or-nothing is atomicity.
class Txn:
    def __init__(self, db):
        self.db = db
        self.staged = {}
    def write(self, key, value):
        self.staged[key] = value        # not yet visible to the db
    def commit(self):
        self.db.update(self.staged)      # apply everything at once
        self.staged = {}
    def rollback(self):
        self.staged = {}                 # throw the batch away

db = {"alice": 100, "bob": 50}
t = Txn(db)
t.write("alice", 100 - 30)
t.write("bob", 50 + 30)
# crash BEFORE commit -> rollback: neither change applied
t.rollback()
print("after rollback:", db)
t2 = Txn(db); t2.write("alice", 70); t2.write("bob", 80); t2.commit()
print("after commit:  ", db)

after rollback: {'alice': 100, 'bob': 50}
after commit:   {'alice': 70, 'bob': 80}

2 · Isolation levels & the anomalies they prevent

Picture two people editing the same shared spreadsheet at the same instant. You read a cell that says 100, do a little maths, and start typing. In the half-second between your reading it and your writing it back, your colleague changes that same cell to 150 and saves. Now what should you see, and what should the final value be? Databases face this a thousand times a second, and the "obvious" answer — "just let everyone see the latest" — quietly produces wrong reports, double-charged cards, and vanished inventory. Isolation is the dial that decides how much of other people's in-flight work leaks into your transaction.

The tempting mistake is to crank that dial to maximum and forget it. There is a setting — Serializable — where every transaction behaves as if it were completely alone in the universe, and it is gloriously simple to reason about. But it isn't free: to deliver that illusion the database has to hold locks or abort-and-retry conflicting transactions, and on a busy system that throttles your throughput hard. So SQL gives you a ladder of weaker guarantees, each one cheaper and each one permitting a specific, named way for reality to bleed through. Choosing a level is choosing which anomalies you can tolerate in exchange for speed — and the only way to choose well is to know exactly what each anomaly looks like.

So learn the three anomalies as concrete scenes, not vocabulary. A dirty read is reading a number your colleague typed but hasn't saved yet — they might still hit undo, and then you've acted on a value that never truly existed. A non-repeatable read is reading a cell, looking away, reading it again, and finding it changed underneath you because someone committed an edit in between — the same row, a different value. A phantom is subtler and catches even experienced engineers: you run "count all rows where status = pending," look away, run the exact same query again, and get a bigger number because someone inserted brand-new matching rows — not a changed value, an entirely new row that appeared. That "changed value vs. new row" distinction is precisely why Repeatable Read stops non-repeatable reads but still permits phantoms, and why only Serializable closes the last gap. The table below is that ladder, from most-permissive to most-strict.

Perfect isolation (every transaction runs as if alone) is expensive, so SQL defines isolation levels that trade correctness for concurrency. Each level permits or forbids three classic anomalies: a dirty read (reading another txn's uncommitted change), a non-repeatable read (re-reading a row and getting a different committed value), and a phantom (a re-run query returns new rows that another txn inserted).

anomaly.py# MODEL: two transactions interleave. T1 reads a row twice; T2 commits a change
# in between. Under READ COMMITTED, T1 sees two different values -> non-repeatable.
committed = {"balance": 100}

def read_committed(key):        # READ COMMITTED always sees latest committed value
    return committed[key]

# --- interleaving ---
first = read_committed("balance")    # T1 first read
committed["balance"] = 150           # T2 commits an update in between
second = read_committed("balance")   # T1 second read

print("T1 first read: ", first)      # 100
print("T1 second read:", second)     # 150 -> non-repeatable!
print("non-repeatable read:", first != second)

T1 first read:  100
T1 second read: 150
non-repeatable read: True

3 · Locking & two-phase locking (2PL)

Think of the last time you booked a seat online and saw "someone else is looking at this seat." That little message is a lock. The system has decided that while you're deciding, nobody else may grab 14C, because if two people both "read available, then wrote booked," you'd both walk onto the plane with the same boarding pass. Locking is the database's version of that reservation: before a transaction touches data, it claims the right to do so and makes conflicting transactions wait their turn.

There are two flavours of lock, and the reason there are two is worth internalising. Many people can safely read the same row at once — reading doesn't change anything, so it can't corrupt anyone — so a shared lock lets multiple readers coexist. But the moment someone wants to write, they need everyone else out of the room, because a write in progress is a half-truth nobody else should see; that's an exclusive lock, and only one transaction may hold it. Shared blocks exclusive and exclusive blocks everything: that's the whole conflict matrix, and it maps directly onto "many can look, only one can change."

But here's the non-obvious part, and the mistake that even careful engineers make. Just taking locks does not guarantee correctness. If a transaction grabs a lock, releases it, does some more work, then grabs another, it can still interleave with others in a way that produces a result no serial ordering could — the locks were held, yet the outcome is corrupt. The fix is a discipline, not more locks: two-phase locking. A transaction must do all its acquiring first (the growing phase), and only once it stops acquiring may it begin releasing (the shrinking phase) — never acquire again after the first release. That single rule is what mathematically guarantees the schedule is equivalent to running the transactions one-at-a-time. The catch, which §2PL shares with the operating-systems chapter, is that two transactions each waiting for a lock the other holds will wait forever — a deadlock — which is the price of this guarantee. The diagram traces the two phases and the "lock point" where growing flips to shrinking.

One way to get isolation is locking: a transaction takes a shared lock to read and an exclusive lock to write, blocking conflicting access. Two-phase locking (2PL) is the rule that makes locking produce serializable schedules: a transaction has a growing phase (it may only acquire locks) and then a shrinking phase (it may only release them). Once you release any lock you may never acquire another. This discipline is what guarantees the interleaving is equivalent to some serial order — at the cost of possible deadlock (SD9's Coffman conditions again).

4 · MVCC — readers don't block writers

Locking has an infuriating side effect you feel the moment a report meets a busy write load. Picture your analytics query — a big read that scans a million rows to build a dashboard — running while customers are placing orders. Under pure locking, your read holds shared locks that block their writes, or their writes hold exclusive locks that stall your read; either way, the "just looking" report and the "actually working" transactions are fighting over the same rows, and someone waits. That fight is the problem MVCC was invented to end.

The trick is a photograph, and it's the analogy to hold onto. When your transaction begins, MVCC hands it a snapshot — effectively a photo of the database at that instant. You read from your photo. Meanwhile writers don't erase and overwrite the old value; they keep the old version and add a new version stamped with their transaction, so the row now has a little history: "this value from txn 1, that value from txn 3." Your photo still shows the version that was current when the shutter clicked, no matter how many new versions pile up afterward. So a reader never waits for a writer and a writer never waits for a reader — they're looking at different frames of the same film. This is exactly the "frozen view" that gives you Repeatable Read from §2, delivered without a single read lock.

The mistake is thinking versions are free — they aren't, and knowing the cost tells you how MVCC behaves in production. All those old row versions accumulate; something has to eventually notice that no live snapshot can still see them and reclaim the space (PostgreSQL calls this VACUUM). A long-running transaction that holds its snapshot open for hours pins every version created since it started, so the database bloats and can't clean up — which is why "kill that idle-in-transaction connection" is a real operational reflex. MVCC trades storage and a background cleanup job for the enormous win of readers and writers never blocking each other. The lab below builds the whole idea in about ten lines: a per-key list of versions, and a read that returns the newest version at or before your snapshot.

Pure locking makes readers and writers fight. MVCC (Multi-Version Concurrency Control) avoids that by keeping multiple versions of each row, each tagged with the transaction that created it. A reader sees a consistent snapshot — the versions that were committed when it started — so it never blocks a writer and never sees half-finished work. This is how PostgreSQL and others give you repeatable reads without read locks.

mvcc.py# MODEL: each key keeps a list of (version_txn, value). A reader with snapshot S
# sees the newest version committed at or before S.
class MVCC:
    def __init__(self):
        self.versions = {}              # key -> list of (txn_id, value)
        self.clock = 0
    def begin(self):
        self.clock += 1
        return self.clock               # a transaction id / snapshot
    def write(self, txn, key, value):
        self.versions.setdefault(key, []).append((txn, value))
    def read(self, snapshot, key):
        visible = [(t, v) for (t, v) in self.versions.get(key, []) if t <= snapshot]
        return visible[-1][1] if visible else None

db = MVCC()
t1 = db.begin(); db.write(t1, "x", 10)          # version at txn 1
reader = db.begin()                              # snapshot = 2
t3 = db.begin(); db.write(t3, "x", 99)          # later version at txn 3
print("reader sees:", db.read(reader, "x"))      # 10 (its snapshot, not 99)
print("newest sees:", db.read(db.begin(), "x"))  # 99

reader sees: 10
newest sees: 99

5 · Indexing & B+ trees

This is the single most common "it was fast in testing, it's dying in production" bug, and it has one cause. You write WHERE email = ?, it returns instantly on your 500-row dev database, you ship it, and six months later that same query takes eight seconds because the table now has two million rows. Nothing about the query changed — but with no index, the database has no choice but to look at every single row to find the one you asked for. That's a full table scan: O(n), and it grows linearly with your success. An index is what turns that eight-second scan back into a millisecond.

The analogy is the back of a textbook, and it's exact. To find every mention of "durability" in a 900-page book, you do not read all 900 pages — you flip to the index, which is sorted alphabetically, jump straight to the D's, and it tells you the pages. A database index is precisely that: a separate, sorted structure that maps a key to where the row lives, so the database can jump instead of scan. And notice the index is extra — it's a second copy of the keys kept in order, which is why indexes cost storage and slow down writes (every insert must also update the index). That trade — pay a little on writes and disk to make reads enormously faster — is the whole game, and it's why you index the columns you search on, not every column.

Now, why a B+ tree specifically, when a hash table gives O(1) lookups? Here's the mistake people make: they reach for the fastest point-lookup structure and get burned on their first range query. A hash index can answer "email = x" in one hop, but it stores keys in scrambled order, so it is useless for "created_at BETWEEN March AND June" or "ORDER BY price" — there's no notion of "next key" in a hash. The B+ tree keeps every key sorted, and links its leaf nodes left-to-right, so a range query becomes "seek to the low bound, then walk the leaves until you pass the high bound." It's a balanced, high-fan-out tree — each node holds hundreds of keys, so even a billion rows sit only three or four levels deep, meaning three or four page reads to find anything. Point lookups in O(log n), range scans and ordered reads nearly free: that combination is why the B+ tree, not the hash, is the default index in every major SQL database. The lab models it as a sorted key list you binary-search and slice.

Without an index, finding a row means scanning the whole table — O(n). An index is an auxiliary structure that turns that into a fast lookup. Most relational databases use a B+ tree: a balanced, high-fan-out tree that keeps keys sorted, so it supports both point lookups (O(log n)) and range scans (walk the sorted leaves). High fan-out means the tree is shallow, so even a billion rows are only a handful of levels — a handful of disk reads.

index.py# MODEL: a B+-tree behaves, for queries, like a sorted key list you binary-search
# for a point lookup and slice for a range scan. bisect models the sorted leaves.
import bisect

class OrderedIndex:
    def __init__(self):
        self.keys = []
        self.rows = {}
    def insert(self, key, row):
        i = bisect.bisect_left(self.keys, key)
        if i == len(self.keys) or self.keys[i] != key:
            self.keys.insert(i, key)     # keep keys sorted (like B+ leaves)
        self.rows[key] = row
    def lookup(self, key):               # point query: O(log n) search
        i = bisect.bisect_left(self.keys, key)
        if i < len(self.keys) and self.keys[i] == key:
            return self.rows[key]
        return None
    def range(self, lo, hi):             # range scan: slice the sorted keys
        i = bisect.bisect_left(self.keys, lo)
        j = bisect.bisect_right(self.keys, hi)
        return [self.rows[k] for k in self.keys[i:j]]

idx = OrderedIndex()
for k in [50, 20, 80, 10, 35, 65]:
    idx.insert(k, f"row-{k}")
print("sorted keys:", idx.keys)
print("lookup 35:", idx.lookup(35))
print("range 20..65:", idx.range(20, 65))

sorted keys: [10, 20, 35, 50, 65, 80]
lookup 35: row-35
range 20..65: ['row-20', 'row-35', 'row-50', 'row-65']

6 · Query planning & the write-ahead log

Two ideas share this section, and both answer questions you've probably muttered at a database. The first: "I added the index — why is it still slow?" The second: "the server lost power mid-write — how did my confirmed order survive?" The query planner explains the first; the write-ahead log explains the second. Together they're the difference between a database that merely stores data and one that runs your queries intelligently and never loses a committed byte.

Start with the planner, and the analogy that demystifies it: a GPS choosing a route. When you write SQL you say what you want — "give me these rows" — not how to get them, exactly as you tell a GPS a destination, not which streets to take. The planner is the routing engine: it looks at your query, at what indexes exist, at statistics about how many rows match, and estimates the cost of each possible plan — full scan vs. index scan, this join order vs. that one, this join algorithm vs. another — then picks the cheapest. This is why adding an index doesn't force its use: if the planner estimates your WHERE matches most of the table, it will correctly ignore the index, because jumping around the disk for two-thirds of the rows is slower than reading them all sequentially. The common mistake is assuming "index exists therefore index used"; the planner's cost model is the reason that isn't so, and Exercise 5 makes the crossover concrete.

Now durability, and the beautifully simple idea that guarantees it: write it down before you do it. The naïve approach — just change the data on disk when a transaction commits — has a fatal gap: if the power dies half-way through updating the data pages, you're left with a corrupt, half-written mess and no way to know what was supposed to happen. The write-ahead log closes that gap with one rule: log first, then data. Before touching a single data page, the database appends a compact record of the intended change to an append-only log and flushes that log to disk. Only then does it modify the actual data (and it can do that lazily, later). The analogy is a chef writing every order on a ticket rail before cooking: if the kitchen burns down, the tickets survive, and a new cook can replay them to reproduce exactly the orders that were confirmed — while any order that was never fully written down simply never happened. That replay is crash recovery: redo everything up to a commit marker, discard anything after the last one. It's also why durability is cheap — a sequential append is fast, and it's the only thing that must hit disk before you tell the user "committed." The final lab builds a WAL you can crash and recover.

The query planner turns your SQL into an execution plan. SQL is declarative — you say what, not how — so the planner chooses how: which index to use, join order, and join algorithm, picking the plan with the lowest estimated cost from table statistics. Choosing an index scan over a full table scan is the single most common plan decision, and it is why the index in §5 matters.

Durability comes from the write-ahead log (WAL): before changing a data page, the database first appends a record of the change to an append-only log and flushes it to disk. If the server crashes, recovery replays the log to redo committed transactions and discards uncommitted ones. "Log first, then data" is the rule that makes "committed means durable" true even across a power failure.

wal.py# MODEL: log-before-data. A crash loses in-memory data pages but NOT the flushed
# WAL, so recovery replays committed records to rebuild the correct state.
class Database:
    def __init__(self):
        self.data = {}                  # in-memory pages (lost on crash)
        self.wal = []                   # append-only log (survives crash)
    def txn(self, changes):             # changes: dict of key->value
        for k, v in changes.items():
            self.wal.append(("set", k, v))   # 1. write-ahead: log first
        self.wal.append(("commit",))         #    then a commit marker
        for k, v in changes.items():
            self.data[k] = v                 # 2. apply to data pages
    def crash(self):
        self.data = {}                  # volatile memory is gone; WAL remains
    def recover(self):
        pending, self.data = {}, {}
        for rec in self.wal:
            if rec[0] == "set":
                pending[rec[1]] = rec[2]
            elif rec[0] == "commit":
                self.data.update(pending); pending = {}   # redo committed
        # pending left over = uncommitted at crash -> discarded

db = Database()
db.txn({"alice": 70, "bob": 80})        # committed
db.wal.append(("set", "carol", 999))    # a write with NO commit (in-flight)
db.crash()
print("after crash, data:", db.data)    # {} -- memory lost
db.recover()
print("after recovery:  ", db.data)     # committed txn restored, carol dropped

after crash, data: {}
after recovery:   {'alice': 70, 'bob': 80}

Knowledge check

class Txn:
    def __init__(self, db): self.db, self.staged = db, {}
    def write(self, k, v): self.staged[k] = v
    def commit(self): self.db.update(self.staged); self.staged = {}
    def rollback(self): self.staged = {}

db = {"alice": 100, "bob": 50}
t = Txn(db); t.write("alice", 70); t.write("bob", 80)
t.rollback()
print("rolled back:", db)          # unchanged
t2 = Txn(db); t2.write("alice", 70); t2.write("bob", 80); t2.commit()
print("committed:  ", db)          # both applied

committed = {"balance": 100}

def read_committed(k):        # always the latest committed value
    return committed[k]

# Non-repeatable read under READ COMMITTED:
r1 = read_committed("balance")
committed["balance"] = 150    # another txn commits in between
r2 = read_committed("balance")
print("read committed:", r1, r2, "-> differs:", r1 != r2)

# A frozen SNAPSHOT (repeatable read) captures the value at start:
snapshot = dict(committed)    # taken when the txn began
committed["balance"] = 999    # later commit is invisible to the snapshot
s1 = snapshot["balance"]; s2 = snapshot["balance"]
print("snapshot:      ", s1, s2, "-> differs:", s1 != s2)

import bisect

class OrderedIndex:
    def __init__(self): self.keys, self.rows = [], {}
    def insert(self, k, row):
        i = bisect.bisect_left(self.keys, k)
        if i == len(self.keys) or self.keys[i] != k: self.keys.insert(i, k)
        self.rows[k] = row
    def lookup(self, k):
        i = bisect.bisect_left(self.keys, k)
        return self.rows[k] if i < len(self.keys) and self.keys[i] == k else None
    def range(self, lo, hi):
        i, j = bisect.bisect_left(self.keys, lo), bisect.bisect_right(self.keys, hi)
        return [self.rows[k] for k in self.keys[i:j]]

idx = OrderedIndex()
for k in [50, 20, 80, 10, 35, 65]: idx.insert(k, f"row-{k}")
print(idx.lookup(35))          # row-35
print(idx.range(20, 65))       # ordered slice

class MVCC:
    def __init__(self): self.versions, self.clock = {}, 0
    def begin(self): self.clock += 1; return self.clock
    def write(self, txn, k, v): self.versions.setdefault(k, []).append((txn, v))
    def read(self, snap, k):
        vis = [(t, v) for t, v in self.versions.get(k, []) if t <= snap]
        return vis[-1][1] if vis else None

db = MVCC()
t1 = db.begin(); db.write(t1, "x", 10)
reader = db.begin()               # snapshot before the next write
t3 = db.begin(); db.write(t3, "x", 99)
print("old reader:", db.read(reader, "x"))   # 10
print("new reader:", db.read(db.begin(), "x"))  # 99

import math

def choose_plan(rows, selectivity, random_penalty=4):
    """selectivity = fraction of rows matched. A full scan reads sequentially
    (1 unit/row); an index scan pays a seek plus RANDOM I/O per matched row,
    and random I/O is modelled as `random_penalty`x costlier than sequential."""
    full_scan = rows
    index_scan = math.log2(rows) + rows * selectivity * random_penalty
    plan = "index" if index_scan < full_scan else "full-scan"
    return plan, round(full_scan, 1), round(index_scan, 1)

rows = 1_000_000
for sel in (0.00001, 0.01, 0.1, 0.5, 0.9):
    plan, fs, ix = choose_plan(rows, sel)
    print(f"selectivity={sel:<8} -> {plan:9s} (full={fs}, index={ix})")

class Database:
    def __init__(self): self.data, self.wal = {}, []
    def txn(self, changes):
        for k, v in changes.items(): self.wal.append(("set", k, v))  # log first
        self.wal.append(("commit",))
        for k, v in changes.items(): self.data[k] = v                # then apply
    def crash(self): self.data = {}          # volatile pages gone; WAL survives
    def recover(self):
        pending, self.data = {}, {}
        for rec in self.wal:
            if rec[0] == "set": pending[rec[1]] = rec[2]
            elif rec[0] == "commit": self.data.update(pending); pending = {}

db = Database()
db.txn({"alice": 70, "bob": 80})       # committed
db.wal.append(("set", "carol", 999))   # in-flight, never committed
db.crash()
print("post-crash:", db.data)          # {}
db.recover()
print("recovered: ", db.data)          # alice/bob restored, carol dropped