A 15-part series building a persistent key-value store from first principles in Python, inspired by the DBDB chapter of The Architecture of Open Source Applications. Covers append-only storage, immutable B-trees, value references, locking, atomic commits, compaction, AVL trees, and thread-safe updates.
Why the first commit was a smoke test, not storage code. Setting up pyproject.toml (PEP 621), pytest with pythonpath, pytest-bdd Gherkin smoke, conftest plugin loading, and a tiny Makefile so...
Append-only records, a 4096-byte superblock, big-endian length prefixes, flush vs fsync ordering for durable commits, advisory file locks with portalocker, and why DBDB trades disk space for a simple atomic...
Why `ValueRef` separates “where on disk” from “what’s in RAM”: lazy `get()`, idempotent `store()`, `prepare_to_store` for subclasses, UTF-8 vs Python 3 strings, and `BytesValueRef` for pickled nodes without touching the...
How immutable binary search tree nodes, copy-on-write path updates, and address-only node serialization give DBDB atomic reads with minimal locking. Includes `from_node` length deltas, post-order persistence, and lazy child loading...
How `LogicalBase` manages lifecycle while `BinaryTree` owns algorithms: root refresh policy, `_follow` as the indirection boundary, immutable insert/delete path copying, in-order predecessor deletion, and why the storage contract stays duck-typed...
A full write-then-read trace for `apple -> red` across Storage, ValueRef, BinaryNode, and LogicalBase. See exactly when bytes hit disk, when refs stay lazy, and why the root-pointer flip is...
The OS lock queues writers correctly but doesn't tell them what they missed. Trace the two-writer race that silently drops commits, then see how `lock()` returning `True` vs `False` carries...
`commit()` is two lines — a bottom-up cascade that writes every dirty node, then an 8-byte root pointer flip. This post wires `get`, `set`, `pop`, and `commit` into `LogicalBase`, closes...
55 lines of facade code that hide an entire architecture. `DBDB.__init__` wires Storage into BinaryTree so the caller never sees either. The dictionary protocol, `_assert_not_closed`, `__contains__` via try/except, and an...
`tool.py` is 62 lines that translate dict syntax into shell commands. Three decisions worth examining: why `finally` handles `close()` rather than each branch, why `set` auto-commits while the Python API...
Append-only storage never reclaims space — every overwrite leaves orphaned bytes. Compaction fixes this by copying the live dataset to a fresh file and atomically swapping it in. The hard...
Eleven posts, six layers, one guarantee. This retrospective traces the design thread that ran from append-only storage through compaction — why each decision followed from the last, what each layer...
The benchmark was supposed to find a known limitation, but it found two other bugs first: an N+1 query problem and a recursion depth error from inserting sorted keys. Both...
Binary trees are tall and thin, leading to many disk reads. B-trees are short and fat, promising faster queries. This post adds a B-tree implementation to DBDB, with nodes that...
A fifty-thread benchmark test reveals a lost update problem. This post adds a pessimistic `DBDB.update()` to provide atomic read-modify-write, then debugs three concurrency bugs that only appear with threads: fcntl...