DBMS internals

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)

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)

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

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))

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