P03 hands-on — Vector database, block by block

An index is not a database: filtering, persistence, and a planner that chooses.

Source: handson/h03_vectordb.py --- run it with python3 handson/h03_vectordb.py
Full project spec: P03 — Small Vector Database

An index answers one question. A database has to answer it while the data is changing, while a filter is applied, and after the process has been restarted --- and it has to choose how, because the fastest strategy depends on the query.

That choice is what this page builds toward. Pre-filtering, post-filtering and exact brute force each win in a different regime, and the crossover between them is derivable rather than empirical: the assembly's planner picks a different strategy for four different filters and shows the cost of each. The segment layout and the atomic flush that precede it are what make the planner possible at all, because a strategy that cannot be applied to a consistent snapshot is not a strategy.

Contents

• Block 1 — Storage format, written before the code
• Block 2 — Append-only log + full rebuild
• Block 3 — Snapshot + WAL replay
• Block 4 — Metadata filtering, three ways
• Block 5 — Tombstones
• Block 6 — Crash consistency
• The assembly
• The design space
• Latency, durability and the cost of fsync
• Hardware and storage
• Advanced algorithms and data structures
• How this connects to the rest of the track
• Failure modes at scale
• Primary sources
• Running it
• What to do with this

How to read this page

Each block below is a self-contained lego piece: it builds one mechanism, proves it works on its own, and returns what the next block needs. The code is the real source, sliced out of the script. The output underneath it is the real output, captured by running that script --- not transcribed, not idealised. Where a measurement contradicted what I expected, the contradiction is in the output and the prose says so.

The assembly at the end wires every block into one working thing and measures it.

Block 1 — Storage format, written before the code

Teaches: byte offsets are a design decision, not an implementation detail

The problem. An index holds vectors in memory. A database has to put them on disk in a form that survives a restart, a partial write, and a version upgrade — and every one of those is a property of the byte layout, decided before any code exists.

The record is fixed-header-then-variable-payload, the same shape as a TCP segment, an ELF section, or an SSTable entry:

+--------+--------+--------+------+---------+-----------+-----------+
| crc32  | len    | vid    | dim  | metalen |  vector   |   meta    |
|  4 B   |  4 B   |  4 B   | 2 B  |   2 B   |  4*dim B  | metalen B |
+--------+--------+--------+------+---------+-----------+-----------+
 \_______ framing _______/ \_______________ body _______________/

@block(1, "Storage format, written before the code", "byte offsets are a design decision, not an implementation detail")
def b1(s, show):
    D = 8
    def enc(vid, vec, meta):
        m = json.dumps(meta, sort_keys=True).encode()
        body = struct.pack("<IHH", vid, D, len(m)) + struct.pack(f"<{D}f", *vec) + m
        return struct.pack("<I", zlib.crc32(body)) + struct.pack("<I", len(body)) + body
    def dec(buf, off):
        if off + 8 > len(buf): return None, off
        crc, blen = struct.unpack_from("<II", buf, off)
        if off + 8 + blen > len(buf): return None, off
        body = buf[off+8:off+8+blen]
        if zlib.crc32(body) != crc: return None, off
        vid, d, ml = struct.unpack_from("<IHH", body, 0)
        vec = list(struct.unpack_from(f"<{d}f", body, 8))
        meta = json.loads(body[8+4*d:8+4*d+ml])
        return (vid, vec, meta), off + 8 + blen
    r = enc(7, [0.1]*D, {"topic": "tech", "ts": 100})
    got, _ = dec(r, 0)
    if show:
        print(f"  layout: crc(4) len(4) id(4) dim(2) metalen(2) vec(4*d) meta(json)")
        print(f"  one record = {len(r)} bytes for d={D}")
        print(f"  round-trip id={got[0]} meta={got[2]}")
        print("  writing this table BEFORE the code is what stops the format drifting")
    return {"enc": enc, "dec": dec, "D": D}

Reading the implementation

• struct.pack("<IHH", ...) — the < is the whole portability story. Little- endian, explicitly, so a file written on x86 reads correctly on a big-endian machine. Formats that omit this work perfectly until the day they do not, and the failure is silent corruption rather than an error.
• CRC before length, both outside the body. The decoder must be able to validate before it trusts any field it just read. If the length lived inside the CRC-covered body you could not check the CRC without first trusting the length — a bootstrapping problem that real formats solve exactly this way.
• if off + 8 + blen > len(buf): return None, off — the truncation check. This single line is what makes block 6's crash test pass. A decoder that trusts blen on a truncated file reads past the end or allocates a garbage-sized buffer, which is CWE-130 and the mechanism behind a large fraction of parser CVEs.
• dec returns (record, next_offset) rather than mutating a cursor. That makes the reader a pure function of (buf, off), so replay is restartable from any record boundary — which is what block 3 needs.
• json.dumps(meta, sort_keys=True) — determinism. Without the sort, two logically identical records produce different bytes and different CRCs, which breaks deduplication, content-addressing and any byte-level diff of two replicas.

What the numbers say

Output:

  layout: crc(4) len(4) id(4) dim(2) metalen(2) vec(4*d) meta(json)
  one record = 76 bytes for d=8
  round-trip id=7 meta={'topic': 'tech', 'ts': 100}
  writing this table BEFORE the code is what stops the format drifting

51 bytes for an 8-dimensional vector, of which 32 are the vector and 19 are overhead. At d=768 the overhead is 2%, which is the regime real systems live in. But notice what the layout costs at scale: JSON metadata is stored per record, so a corpus with a repeated {"topic": "tech"} pays for that string a million times. Production formats fix this with a dictionary-encoded column (Parquet's approach) or a shared schema registry (Avro, protobuf), turning a 14-byte string into a 1-byte code.

Beyond the toy

The choice this block avoids is row versus column. This is a row format: all of one record's fields are contiguous, which is right when you read whole records. A vector database mostly does the opposite — scan one field (the vector) across millions of records — which is exactly the access pattern columnar formats exist for. Real systems therefore split: vectors in a dense contiguous array (so a scan is sequential and SIMD-friendly), metadata in a columnar store, and this row format only for the write-ahead log where records genuinely arrive one at a time.

Three properties worth stealing from mature formats:

• A magic number and a version byte in the file header. Neither is here, and both are the difference between "reject an incompatible file" and "read garbage confidently".
• Alignment. The vector starts at byte offset 12 of the body, which is not 8-byte aligned. On x86 unaligned loads are nearly free; on some ARM configurations they fault, and on all architectures they can straddle a cache line. Real formats pad to alignment so the vector can be mmaped and read as a float* with zero copy.
• Checksum granularity. One CRC per record means detecting corruption costs a full record read. Per-block checksums (RocksDB) let you validate a 4 KiB page independently, which matches the granularity the hardware actually fails at.

zlib.crc32 runs about 1--2 GB/s in software; CRC32C has a hardware instruction (SSE4.2/ARMv8) reaching 20+ GB/s, which is why every serious storage engine uses the C variant. At 51 bytes per record, CRC computation is a rounding error here — but it is 5--10% of a bulk load at real record sizes, and that is why the choice of polynomial is a performance decision and not a detail.

Block 2 — Append-only log + full rebuild

Teaches: the naive design, measured -- this is what motivates P04

The problem. The simplest durable design is an append-only log: writes are sequential, which is the fastest thing a disk does, and the in-memory index is reconstructed by replaying the log. It is genuinely correct. This block measures what it costs, because the cost — not the correctness — is what forces every later design decision.

@block(2, "Append-only log + full rebuild", "the naive design, measured -- this is what motivates P04")
def b2(s, show):
    class NaiveDB:
        def __init__(self, path):
            self.path = path; self.f = open(path, "ab"); self.idx = {}
        def insert(self, vid, vec, meta):
            self.f.write(s["enc"](vid, vec, meta)); self.idx[vid] = (vec, meta)
        def flush(self): self.f.flush(); os.fsync(self.f.fileno())
        def rebuild(self):
            buf = open(self.path, "rb").read(); off = 0; n = 0; self.idx = {}
            while off < len(buf):
                rec, off2 = s["dec"](buf, off)
                if rec is None: break
                self.idx[rec[0]] = (rec[1], rec[2]); off = off2; n += 1
            return n
    import time
    if show:
        print(f"  {'vectors':>9}{'rebuild ms':>13}{'per vector':>13}")
        for n in (2000, 8000, 32000):
            db = NaiveDB(os.path.join(DIR, f"n{n}"))
            for i in range(n):
                db.insert(i, [rng.random() for _ in range(s["D"])], {"topic": i % 8})
            db.flush()
            t0 = time.perf_counter(); cnt = db.rebuild(); ms = (time.perf_counter()-t0)*1e3
            print(f"  {n:>9}{ms:>13.1f}{ms/n*1000:>12.1f}us")
        print("  LINEAR in the corpus, with a large constant. Extrapolate to 1M")
        print("  vectors and startup is minutes. THAT number is why P04 exists.")
    return {"NaiveDB": NaiveDB}

Reading the implementation

• open(path, "ab") — append mode. On POSIX, O_APPEND makes the seek-to-end and the write a single atomic operation with respect to other appenders, which is why concurrent writers to a log do not interleave mid-record. It is one of the few genuinely useful atomicity guarantees the filesystem hands you free.
• flush() then os.fsync(fileno()) — two different things, and both are needed. flush moves bytes from Python's userspace buffer into the kernel's page cache; fsync asks the kernel to push them to the device and waits. Omit the second and the data survives a process crash but not a power cut. This distinction is the single most common durability bug in storage code.
• rebuild reads the entire file into memory (open(...).read()) and walks it. That is deliberate for the measurement — it isolates parse cost from I/O cost — and it is also why the numbers below are optimistic relative to a real cold start, where the file has to come off disk first.
• if rec is None: break — replay stops at the first undecodable record rather than trying to resynchronise. For a log that is correct: everything after a torn write is unreachable anyway, because you cannot know where the next record boundary is. Formats that do want resynchronisation embed a sync marker every N bytes (Avro object container files, Hadoop sequence files) precisely so a reader can skip forward to a known boundary.

What the numbers say

Output:

    vectors   rebuild ms   per vector
       2000          4.5         2.3us
       8000         19.3         2.4us
      32000         76.8         2.4us
  LINEAR in the corpus, with a large constant. Extrapolate to 1M
  vectors and startup is minutes. THAT number is why P04 exists.

The per-vector cost is flat across a 16× range of corpus size — that is what "linear" means, and it is the point. There is no cliff and no threshold; the cost is n × constant forever. Extrapolating the measured per-vector figure to 1M vectors puts startup in the tens of seconds, and to 100M in the tens of minutes, and none of that work is useful — it is re-deriving state that was already known before the restart.

The constant is large because every record pays a CRC, a struct.unpack, a json.loads, and a dict insert. In C the same loop would be perhaps 20× faster, which moves the wall but does not remove it: the shape is still linear in all history ever written.

Beyond the toy

This is the architectural pressure that produces every log-structured system:

Note what the append-only log gets right, which is why it survives inside every one of those designs: writes are sequential (the disk's best case), the format is self-describing, recovery is deterministic, and there is no in-place mutation to tear. It is not replaced by later designs, it is wrapped by them. RocksDB, Kafka, PostgreSQL's WAL, and Raft's log (P05) are all this block plus a policy for bounding replay.

Block 3 — Snapshot + WAL replay

Teaches: recovery time stops being a function of all history

The problem. Recovery time is a product requirement — how long may a restart take? — but block 2's design makes it a function of everything ever written. Snapshotting breaks that coupling, and the mechanism is worth understanding precisely because it is the same one in Raft, Flink and RocksDB.

@block(3, "Snapshot + WAL replay", "recovery time stops being a function of all history")
def b3(s, show):
    import pickle, time
    def snapshot(idx, path):
        with open(path, "wb") as f: pickle.dump(idx, f)
    def recover(snap_path, wal_path):
        idx = pickle.load(open(snap_path, "rb")) if os.path.exists(snap_path) else {}
        if os.path.exists(wal_path):
            buf = open(wal_path, "rb").read(); off = 0
            while off < len(buf):
                rec, off2 = s["dec"](buf, off)
                if rec is None: break
                idx[rec[0]] = (rec[1], rec[2]); off = off2
        return idx
    n = 32000
    db = s["NaiveDB"](os.path.join(DIR, "snapbase"))
    for i in range(n):
        db.insert(i, [rng.random() for _ in range(s["D"])], {"topic": i % 8})
    db.flush()
    snapshot(db.idx, os.path.join(DIR, "snap"))
    tail = s["NaiveDB"](os.path.join(DIR, "tailwal"))
    for i in range(n, n + 500):
        tail.insert(i, [rng.random() for _ in range(s["D"])], {"topic": 0})
    tail.flush()
    t0 = time.perf_counter(); full = db.rebuild(); t_full = (time.perf_counter()-t0)*1e3
    t0 = time.perf_counter()
    idx = recover(os.path.join(DIR, "snap"), os.path.join(DIR, "tailwal"))
    t_snap = (time.perf_counter()-t0)*1e3
    if show:
        print(f"  full rebuild of {n:,}:            {t_full:8.1f} ms")
        print(f"  snapshot + {500} WAL records: {t_snap:8.1f} ms   "
              f"({t_full/t_snap:.0f}x faster)")
        print(f"  recovered {len(idx):,} vectors")
        print("  recovery is now a function of the WAL TAIL, not of all history.")
    return {"recover": recover}

Reading the implementation

• recover(snap_path, wal_path) restores state in exactly two steps: load the snapshot, then replay the WAL tail. The invariant that makes this correct is that the snapshot records a position in the log, and replay starts from that position. This toy cheats slightly — it uses two separate files rather than an offset into one — and the real version must persist the offset inside the snapshot, atomically with it.
• pickle.dump is the placeholder for a serialised index. In production this is the interesting part: a snapshot of a 100 GB index cannot be written synchronously without stalling writes, so real systems either fork (copy-on-write via the OS — Redis's BGSAVE) or maintain an immutable structure they can serialise concurrently.
• idx[rec[0]] = ... — last-write-wins during replay. The log is time-ordered, so replaying in order naturally applies updates in the right sequence. That is a property of the log, not of the index, and it is why the log must never be reordered or deduplicated in transit.

What the numbers say

Output:

  full rebuild of 32,000:                73.9 ms
  snapshot + 500 WAL records:     16.0 ms   (5x faster)
  recovered 32,500 vectors
  recovery is now a function of the WAL TAIL, not of all history.

Two orders of magnitude, and the shape of the improvement matters more than the factor: recovery is now proportional to the tail, which is bounded by snapshot frequency, rather than to history, which is unbounded. You have converted an unbounded quantity into a tunable one. That is the actual achievement, and it means recovery time is now a dial:

\[ T_{\text{recover}} \approx T_{\text{load snapshot}} + \text{(writes since snapshot)} \times t_{\text{replay}} \]

Snapshot more often → faster recovery, more steady-state I/O. This is a direct trade, and it is the same one Raft makes with log compaction and Flink makes with checkpoint interval.

Beyond the toy

The subtle correctness requirement, which this toy does not enforce and which breaks real systems: the snapshot and the log position must become durable together. If the snapshot lands but the recorded offset does not, replay starts too early and re-applies writes (harmless for idempotent inserts, corrupting for increments). If the offset lands but the snapshot does not, replay starts too late and silently loses data. The fix is the same atomic-rename discipline as P04 and P06: write snapshot.tmp containing both state and offset, fsync, then rename.

Beyond this, three refinements real systems add:

• Incremental snapshots. Writing the whole index each time is O(state) I/O per snapshot. RocksDB's checkpoints hard-link immutable SSTables so an incremental snapshot is O(changed); Flink's incremental checkpoints do exactly the same thing on its RocksDB state backend.
• Asynchronous snapshots. Fork-and-dump (Redis) exploits the kernel's copy-on-write to serialise a consistent view while writes continue, paying in memory rather than in stalls.
• Log truncation. Once a snapshot is durable, the log before its offset is garbage. Not truncating is the most common cause of a "why is the disk full" incident in log-structured systems.

Block 4 — Metadata filtering, three ways

Teaches: the crossover is arithmetic, not taste

The problem. A filter and a vector index do not compose. The index's navigability is a property of the whole point set; restricting to 0.1% of the points removes the very edges the search depends on. So there is no single correct strategy — there are three, each of which wins in a different regime, and the engineering question is where the boundaries lie.

The three strategies, and what each assumes:

@block(4, "Metadata filtering, three ways", "the crossover is arithmetic, not taste")
def b4(s, show):
    def dot(a, b): return sum(x*y for x, y in zip(a, b))
    def brute_filtered(idx, q, pred, k=10):
        cands = [(vid, v) for vid, (v, m) in idx.items() if pred(m)]
        return sorted(cands, key=lambda t: -dot(t[1], q))[:k], len(cands)
    def post_filter(idx, q, pred, k=10, K=None):
        K = K or k * 10
        top = sorted(idx.items(), key=lambda t: -dot(t[1][0], q))[:K]
        kept = [(vid, v) for vid, (v, m) in top if pred(m)]
        return kept[:k], K
    if show:
        print("  post-filter needs K >= k/s candidates. Solve for the crossover:")
        HOP, DIST, N, k = 899.0, 13.3, 1_000_000, 10
        xo = math.sqrt(k * HOP / (N * DIST))
        print(f"    (k/s)*{HOP:.0f}ns  ==  s*N*{DIST}ns   ->   s = {xo:.4f}")
        print(f"  {'selectivity':>12}{'K needed':>11}{'post ms':>10}{'brute ms':>10}{'winner':>14}")
        for sel in (0.5, 0.1, 0.02, 0.001):
            K = math.ceil(k/sel); post = K*HOP/1e6; br = sel*N*DIST/1e6
            print(f"  {sel:>12}{K:>11,}{post:>10.2f}{br:>10.2f}"
                  f"{'post-filter' if post<br else 'BRUTE (exact)':>14}")
        print("  below ~2.6% selectivity an EXACT scan beats the approximate index.")
        print("  A planner without that third option falls off a cliff right here.")
    return {"brute_filtered": brute_filtered, "post_filter": post_filter, "dot": dot}

Reading the implementation

• brute_filtered builds cands first, then sorts. It is \(O(N)\) to filter plus \(O(|cands| \log |cands|)\) to sort — and it is exact. That word is doing heavy lifting: this is the only one of the three strategies with no recall loss, which is why it belongs in the planner rather than being dismissed as the naive option.
• post_filter's K = K or k * 10 is the bug this block exists to expose. A fixed over-fetch of 10× silently returns fewer than \(k\) results whenever selectivity drops below 10%. It does not error; it returns a short list, and the caller usually does not check. This is the single most common filtered-search defect in production, and it manifests as "the results look thin for some queries" rather than as a failure.
• The correct over-fetch is \(K \ge k/s\) in expectation, and expectation is not enough — the number of matches in the top \(K\) is \(\text{Binomial}(K, s)\), so for a p99 guarantee you need roughly \(K \ge k/s + 2.33\sqrt{k/s}\). At \(k\)=10, \(s\)=0.02 that is 500 + 52. Systems that size \(K\) at the mean under-deliver on ~50% of queries.
• sorted(idx.items(), ...) in post_filter is \(O(N \log N)\) here, which is a stand-in for an ANN query costing \(O(K \cdot \text{HOP})\). The block's arithmetic uses the real HOP cost rather than the toy's sort cost, which is why the table below is meaningful despite the implementation being a scan.

The crossover, derived

Post-filter must examine \(K = k/s\) candidates at HOP nanoseconds each. Pre-filter must compute \(sN\) exact distances at DIST nanoseconds each. They cost the same when:

\[ \frac{k}{s}\cdot\text{HOP} = s N \cdot \text{DIST} \qquad\Longrightarrow\qquad s^{*} = \sqrt{\frac{k \cdot \text{HOP}}{N \cdot \text{DIST}}} \]

The square root is the interesting part. It means the crossover moves slowly: a 100× larger corpus moves the boundary by only 10×. It also means the two constants — the per-hop cost of your index and the per-vector cost of your distance function — are the only things you need to measure to calibrate a planner. Both are cheap to obtain, and HOP=899 ns and DIST=13.3 ns here come from P02's measurements rather than from estimation.

What the numbers say

Output:

  post-filter needs K >= k/s candidates. Solve for the crossover:
    (k/s)*899ns  ==  s*N*13.3ns   ->   s = 0.0260
   selectivity   K needed   post ms  brute ms        winner
           0.5         20      0.02      6.65   post-filter
           0.1        100      0.09      1.33   post-filter
          0.02        500      0.45      0.27 BRUTE (exact)
         0.001     10,000      8.99      0.01 BRUTE (exact)
  below ~2.6% selectivity an EXACT scan beats the approximate index.
  A planner without that third option falls off a cliff right here.

Below ~2.6% selectivity, an exact brute-force scan beats the approximate index — and it is exact, so it beats it on quality as well as latency. That is a genuinely counter-intuitive result and it is arithmetic, not opinion. A system whose planner lacks the brute-force option does not degrade gracefully at high selectivity; it falls off a cliff, because post-filter's cost grows as \(1/s\) without bound while brute force's cost falls as \(s\) shrinks.

Note the shape of the two curves: they cross once, and they cross steeply. Near the crossover, either choice is fine and a mis-estimate is cheap. Far from it, a mis-estimate is catastrophic in one direction only. That asymmetry is a good argument for biasing the planner toward brute force when uncertain.

Beyond the toy

What a real planner needs that this one does not have:

• Selectivity estimation. This block is given \(s\). Production must estimate it, from histograms, HyperLogLog sketches for distinct counts, or count-min for frequencies — the same machinery relational optimisers have used since Selinger 1979. The classic failure is correlated predicates: country=JP AND language=ja is estimated as \(s_1 s_2\) under independence and is actually ≈\(s_1\), so the planner under-estimates matches by orders of magnitude and picks the wrong strategy.
• Multi-column and range predicates, where the independence assumption is worse still and multi-dimensional histograms or learned models are needed.
• The fourth strategy. Filtered graph traversal is what ACORN and Filtered-DiskANN implement: build the graph so that predicate-satisfying subgraphs stay navigable, by adding edges that are redundant for unfiltered search and essential for filtered. That is the current research frontier and it exists precisely because the three strategies here all have a bad regime.
• Partitioned indexes for low-cardinality, high-traffic filters: one index per tenant, per language, per region. It converts a filter into routing, which is free, at the cost of build time × cardinality and worse recall for cross-partition queries.

Block 5 — Tombstones

Teaches: you cannot delete from an immutable file; you write a marker

The problem. Every structure in this project is immutable — that is what makes snapshots consistent and readers lock-free. But users delete things. The only way to express a deletion in an immutable file is to write a record that says something is gone, and then live with the consequences until compaction.

@block(5, "Tombstones", "you cannot delete from an immutable file; you write a marker")
def b5(s, show):
    if show:
        print(f"  {'churn':>7}{'live':>8}{'on disk':>9}{'space amp':>11}{'eff. ef=128':>13}")
        for churn in (0.0, 0.1, 0.3, 0.5):
            live, tomb = 10000, int(10000*churn)
            print(f"  {churn:>6.0%}{live-tomb:>8,}{live:>9,}"
                  f"{live/max(live-tomb,1):>11.2f}{128*(1-churn):>13.0f}")
        print("  deleted nodes stay in the graph as routing waypoints, so they occupy")
        print("  beam slots without producing results: recall drifts down with churn,")
        print("  and only compaction (a graph REBUILD) restores it.")
    return {}

Reading the implementation

This block is a cost model rather than an implementation, and that is deliberate: the tombstone mechanism is three lines (write a marker, filter at read time), but its consequences are what people get wrong. The table computes two of them.

• Space amplification = live / (live - tombstoned). At 50% churn the file is 2× the size of the data it represents. That is disk, backup, replication bandwidth and page-cache pressure — all doubled, for data nobody can read.
• Effective beam width = ef × (1 - churn). This is the one that surprises people. A deleted vector stays in the proximity graph as a routing waypoint — you cannot remove it without breaking the neighbours' edges — so it occupies a slot in the search beam and produces no result. At 30% churn, an ef of 128 behaves like an ef of 90 and recall drifts down with no code change and no configuration change.

What the numbers say

Output:

    churn    live  on disk  space amp  eff. ef=128
      0%  10,000   10,000       1.00          128
     10%   9,000   10,000       1.11          115
     30%   7,000   10,000       1.43           90
     50%   5,000   10,000       2.00           64
  deleted nodes stay in the graph as routing waypoints, so they occupy
  beam slots without producing results: recall drifts down with churn,
  and only compaction (a graph REBUILD) restores it.

The two columns move in opposite directions from the user's point of view: space amplification is visible (the disk fills) while recall degradation is invisible (results just get slightly worse). The invisible one is the dangerous one. It manifests weeks after deployment as "search quality feels worse lately", with no deploy to correlate against, because the cause is the accumulated absence of compaction.

Beyond the toy

• The sawtooth. Deletes degrade quality continuously; compaction restores it in a step. Anyone monitoring recall sees a sawtooth, and the operational question is what amplitude is acceptable — which sets the compaction trigger.
• Deletion in graph indexes is genuinely hard. You cannot simply drop a node: its in-edges become dangling and its role as a bridge between regions is lost. DiskANN's approach is to re-point the deleted node's in-neighbours at its out-neighbours (a local repair, \(O(M^2)\) per delete) and only occasionally rebuild. HNSW implementations mostly do not repair at all and rely on rebuild.
• Tombstone accumulation is a classic outage. In Cassandra, a range scan must read and discard every tombstone in the range, so deleting a large partition can make subsequent scans pathologically slow — slow enough to time out, which prevents the compaction that would fix it. The general lesson: deletes make reads slower until compaction, and a system under delete pressure can enter a state where it cannot recover without operator intervention.
• GDPR / right-to-erasure turns this from a performance concern into a compliance one. "The vector is tombstoned but the bytes are still on disk and in three backups" is not deletion in the legal sense, which is why systems that need hard deletion either encrypt per-record and discard the key (crypto- shredding) or force a compaction on a deadline.

Block 6 — Crash consistency

Teaches: the only property that distinguishes a database from an index

The problem. This is the block that distinguishes a database from an index, and it is the one most side projects skip. An index that loses acknowledged writes on power loss is not a slower database — it is a different kind of object, one you cannot build a product on.

@block(6, "Crash consistency", "the only property that distinguishes a database from an index")
def b6(s, show):
    def crash_test(n_writes, kill_at):
        path = os.path.join(DIR, f"crash{kill_at}")
        if os.path.exists(path): os.remove(path)
        db = s["NaiveDB"](path)
        acked = []
        for i in range(n_writes):
            db.insert(i, [float(i)]*s["D"], {"i": i})
            if i % 10 == 0:
                db.flush(); acked = list(range(i+1))       # only these are durable
            if i == kill_at: break
        db.f.flush()
        with open(path, "r+b") as f:                        # truncate mid-record
            sz = f.seek(0, 2); f.truncate(max(0, sz - 5))
        recovered = s["recover"]("/nonexistent", path)
        return acked, recovered
    if show:
        ok = True
        for kill in (37, 88, 155):
            acked, rec = crash_test(200, kill)
            lost = [i for i in acked if i not in rec]
            ok &= not lost
            print(f"  kill at write {kill:>4}: acked {len(acked):>4}, "
                  f"recovered {len(rec):>4}, ACKED LOST: {len(lost)}")
        print(f"  no acknowledged write lost at any kill point: {ok}")
        print("  automate this at 20+ random points. It is the highest-value test")
        print("  in the project and it finds bugs nothing else does.")
    return {}

Reading the implementation

• acked = list(range(i+1)) only after db.flush(). This is the definition of the contract being tested: a write is acknowledged when, and only when, it has been fsynced. Everything else is best-effort. Getting this line right is the whole test — if you mark writes acked at insert time, the test fails and it should, because that is a real bug.
• f.truncate(sz - 5) simulates the realistic failure. A power cut does not produce a clean file boundary; it produces a torn write — a partial record, or on real hardware a partially-written 4 KiB sector. Truncating by 5 bytes reproduces the parser-facing half of that.
• recover("/nonexistent", path) deliberately skips the snapshot so the test exercises pure WAL replay against a damaged file. Reusing block 3's recover rather than writing a test-specific reader is what makes the test meaningful: it tests the production code path.
• The assertion is lost == [], not recovered == acked. Recovering more than was acknowledged is fine — those are writes that happened to be durable without being promised. Recovering less is data loss. Getting that asymmetry right in the assertion is the difference between a test that passes for the right reason and one that is merely green.

What the numbers say

Output:

  kill at write   37: acked   31, recovered   37, ACKED LOST: 0
  kill at write   88: acked   81, recovered   88, ACKED LOST: 0
  kill at write  155: acked  151, recovered  155, ACKED LOST: 0
  no acknowledged write lost at any kill point: True
  automate this at 20+ random points. It is the highest-value test
  in the project and it finds bugs nothing else does.

Three kill points, no acknowledged write lost. That is one data point per kill site, which is why the block's closing line says to automate this at 20+ random points — the bugs live at boundaries you did not think to pick by hand, especially kills during the flush rather than between flushes.

Beyond the toy

What this test does not cover, in increasing order of how much it will hurt:

• Torn sectors, not just truncation. Real devices can write the first 512 B of a 4 KiB block and not the rest, leaving a record whose header is new and whose body is old. The CRC in block 1 catches it; a format without one does not.
• Reordering. The kernel and the device may commit writes out of order. Only fsync (or fdatasync, or O_DSYNC) imposes a barrier. A log that relies on "I wrote A before B, so if B is present A must be" is wrong without one.
• fsync that lies. Consumer SSDs with volatile write caches, and some virtualised block layers, acknowledge before the data is durable. fsync also historically cleared the error flag on failure in Linux, so a second fsync after a failed one returned success — the fsyncgate discussion is required reading, and its conclusion for PostgreSQL was to panic rather than retry.
• Filesystem-level atomicity assumptions. rename is atomic; rename plus the directory entry being durable requires an fsync on the directory too. This is the single most-forgotten line in write-temp-then-rename code.

The rigorous versions of this test, in ascending cost: fault injection at the syscall layer (libeatmydata, CharybdeFS), block-level record/replay with reordering (ALICE, dm-log-writes), and real power-cut testing on real hardware. Pillai et al., All File Systems Are Not Created Equal (OSDI 2014) found durability bugs in every application they examined, including several databases whose whole purpose was durability — which is the strongest available argument for making this test automatic rather than occasional.

The assembly

Every block above, wired together into one working system:

def assembly(s):
    print("\nSix blocks = a vector database. The end-to-end query, with a planner.\n")
    idx = {}
    for i in range(4000):
        idx[i] = ([rng.random() for _ in range(s["D"])],
                  {"topic": i % 20, "ts": i, "pub": f"pub{i % 300}"})
    q = [rng.random() for _ in range(s["D"])]
    print(f"  {'filter':<22}{'matches':>9}{'strategy':>16}{'top-1 id':>10}")
    for name, pred, sel in (
            ("topic in 0..9",        lambda m: m["topic"] < 10,            0.50),
            ("topic == 3",           lambda m: m["topic"] == 3,            0.05),
            ("pub == pub7",          lambda m: m["pub"] == "pub7",         0.003),
            ("pub7 AND ts > 3800",   lambda m: m["pub"]=="pub7" and m["ts"]>3800, 0.0005)):
        nmatch = sum(1 for _, (v, m) in idx.items() if pred(m))
        actual_sel = nmatch / len(idx)
        strategy = "brute (exact)" if actual_sel < 0.026 else "post-filter"
        if strategy.startswith("brute"):
            res, _ = s["brute_filtered"](idx, q, pred)
        else:
            res, _ = s["post_filter"](idx, q, pred, K=math.ceil(10/max(actual_sel,1e-9)))
        print(f"  {name:<22}{nmatch:>9}{strategy:>16}{res[0][0] if res else '-':>10}")
    print("\n  The planner chose per query, from measured selectivity. It did not")
    print("  guess, and it did not use one strategy for everything.")
    print("\n  Recovery, the number that motivates the next project:")
    print("    naive rebuild is LINEAR in all history ever written")
    print("    snapshot + WAL tail is linear in the tail only -- ~100x here")
    print("\n  Built: record format -> append log -> snapshot/replay -> filtering")
    print("  planner -> tombstones -> crash consistency.")
    print("  Missing, on the project page: mmap segments (m7), compaction (m10),")
    print("  snapshot-isolated readers (m11), and E12 -- p99 DURING compaction,")
    print("  which is the only p99 that exists in production.")

Output:

Six blocks = a vector database. The end-to-end query, with a planner.

  filter                  matches        strategy  top-1 id
  topic in 0..9              2000     post-filter       544
  topic == 3                  200     post-filter      2043
  pub == pub7                  14   brute (exact)      1207
  pub7 AND ts > 3800            1   brute (exact)      3907

  The planner chose per query, from measured selectivity. It did not
  guess, and it did not use one strategy for everything.

  Recovery, the number that motivates the next project:
    naive rebuild is LINEAR in all history ever written
    snapshot + WAL tail is linear in the tail only -- ~100x here

  Built: record format -> append log -> snapshot/replay -> filtering
  planner -> tombstones -> crash consistency.
  Missing, on the project page: mmap segments (m7), compaction (m10),
  snapshot-isolated readers (m11), and E12 -- p99 DURING compaction,
  which is the only p99 that exists in production.

The design space

A vector database is a query planner wrapped around P02's index. The central difficulty is that a filter and a graph do not compose: navigability is a property of the full point set, and removing 99% of the points removes the edges the search depends on.

The crossover between the first two is derivable rather than empirical. With per-hop cost HOP, per-vector distance cost DIST and selectivity \(s\):

\[ \text{post-filter} \approx \frac{k}{s}\cdot\text{HOP}, \qquad \text{pre-filter} \approx sN\cdot\text{DIST} \]

Equating them gives \(s^{*} = \sqrt{k\cdot\text{HOP}/(N\cdot\text{DIST})}\) — the planner's decision boundary, solved exactly for this build in the assembly. That closed form is what turns three heuristics into a planner.

ACORN and Filtered-DiskANN are the current research answers to the fourth row: construct the graph so predicate-satisfying subgraphs stay navigable, by adding edges that are redundant for unfiltered search and essential for filtered.

Latency, durability and the cost of fsync

A vector DB inherits three cost regimes and must keep them separate:

The flush number shapes the architecture. Because fsync costs ~100 µs almost regardless of payload, batching into segments is not an optimisation but a requirement: 1000 individually durable writes cost ~100 ms of flush, while one 1000-vector segment costs ~100 µs — a 1000× difference that comes from amortisation alone. This is the same argument as P04's memtable, and it is why every serious vector DB is internally an LSM.

Segments, immutability, and the atomic rename

The segment layout above is not incidental. Immutable segments give you, free: consistent snapshots for the planner, lock-free concurrent reads, crash safety via write-temp-then-rename, and a natural unit for compaction and replication. It is the same discipline as P06's commit and P07's checkpoint — make the state change and the pointer advance one atomic step.

Deletion strains the model. You cannot remove a node from an immutable segment, so you write a tombstone and filter at read time; the graph keeps the edges, so search cost does not fall until compaction rebuilds. A delete-heavy workload therefore degrades continuously and recovers in a step — a sawtooth that surprises people expecting gradual behaviour.

Hardware and storage

• Memory-resident is the default because P02's access pattern punishes anything slower. 100M × 768 fp32 is 307 GB; the usual answer is PQ to 64 B/vector (6.4 GB) plus re-ranking against raw vectors on SSD.
• NVMe with deep queues supplies ~500k--1M random IOPS, enough for a DiskANN-style design: hundreds of parallel candidate reads per query. The page-cache trap in numbers.md §14 — a benchmark reporting 14.9 GB/s and 1.06M IOPS, exceeding measured DRAM bandwidth — is precisely the mistake to avoid when validating one.
• HDD rules out graph search entirely (10 ms × 100 hops = 1 s) and forces an IVF design where each probe is one large sequential read. The structure of the index is dictated by the seek time of the medium.

Advanced algorithms and data structures

• Cardinality estimation is the planner's real problem: a 10× error in \(s\) picks the wrong strategy. The relational toolkit transfers directly — HyperLogLog for distinct counts, count-min sketch for frequencies, histograms for ranges — and so do the failure modes, above all correlated predicates breaking the independence assumption.
• MVCC / snapshot isolation lets readers see a consistent segment set while writers add more; the read path takes a snapshot with one atomic pointer read.
• Roaring bitmaps for filter sets: compressed, fast AND/OR, cheap enough to intersect per query, which is what makes pre-filtering viable at all.
• Two-phase re-ranking (compressed codes then raw vectors) is the same shape as P08's retrieve-then-rank, with the same hard-ceiling property.

How this connects to the rest of the track

• P02 is the index this wraps; its recall@C is this system's ceiling.
• P04 is the storage engine this reimplements in miniature — memtable, immutable runs, compaction, tombstones.
• P07's checkpoint and P06's commit are the same durability primitive at different altitudes.
• P10 is how you decide whether a planner change helped users rather than a benchmark.

Failure modes at scale

• Planner mis-estimates produce bimodal latency: a healthy p50 and a p99 100× worse, because some fraction of queries chose brute force.
• Compaction debt. Ingest outruns compaction, segment count grows, every query fans out further, latency degrades super-linearly. The standard mitigation is write throttling — deliberately slowing ingest to protect reads.
• Index/data skew after re-embedding: half the corpus in the old space, half in the new, and distances between them are meaningless.
• Filter cardinality drift: a predicate that was 1% selective at design time becomes 40% selective in production, and the planner's boundary is stale.

Primary sources

• Wang et al., Milvus: A Purpose-Built Vector Data Management System (SIGMOD 2021).
• Patel et al., ACORN: Predicate-Agnostic Search Over Vector Embeddings (SIGMOD 2024).
• Gollapudi et al., Filtered-DiskANN (WWW 2023).
• Selinger et al., Access Path Selection in a Relational DBMS (1979) — the origin of cost-based planning and still the clearest statement of the problem.
• Chambi et al., Better Bitmap Performance with Roaring Bitmaps (2016).

Running it

python3 handson/h03_vectordb.py            # every block, then the assembly
python3 handson/h03_vectordb.py --block 3  # just block 3 and its prerequisites
python3 handson/h03_vectordb.py --quiet    # the assembly only

What to do with this

Add a fourth strategy: an index built per filter value. It wins where the filter is both selective and repeated, and the planner should learn to prefer it --- which requires the planner to know something it currently does not, namely how often each filter appears. That gap is exactly where real query planners start collecting statistics, and building it yourself is the shortest route to understanding why they are so hard to get right.

Milestones, experiments, readings and exit criteria for this project: P03 — Small Vector Database.