02. Vector Search Engine — Low-Level Design¶
~22 min read · Part 3 of 4 (Overview → HLD → LLD → Q&A)
The HLD named the boxes. This file opens the ones that carry the design's weight — the HNSW index and how it is built, the IVF-PQ alternative, the scatter-gather coordinator with recall tuning, and hybrid fusion — and pins down the data layouts, the algorithms stepped through with the scenario's billion-vector, 95%-recall numbers, and the concurrency corners where a vector index actually breaks.
Data models¶
A shard holds three parallel arrays plus the graph, laid out for cache-friendly sequential access during a search. The logical shape:
Shard segment (immutable, memory-mapped):
vectors : float32[N][D] # N=50M, D=768 → 50M × 3072 B ≈ 154 GB
ids : uint64[N] # internal ordinal → external vector id
hnsw_graph: # the navigable small-world graph
level0_neighbors : uint32[N][M0] # M0=64 edges at base layer
upper_neighbors : uint32[·][M] # M=32 edges, only for promoted nodes
entry_point : uint32 # where every search starts
tombstones: bitset[N] # deleted-but-not-yet-reclaimed
Three deliberate choices. First, vectors are stored by internal ordinal (0..N-1), not by external id, so the graph's edges are compact uint32 offsets into a contiguous array rather than 8-byte ids — that halves edge memory and makes neighbor fetches sequential. A side ids array maps ordinal back to the caller's id at the very end. Second, the base layer gets twice the edges (M0=64) of the upper layers (M=32) because the base layer carries the fine-grained connectivity that recall depends on, while upper layers exist only for fast coarse navigation. Third, deletes are a bitset, not a graph edit: flipping a bit is O(1) and the search filters tombstoned ordinals out of results; the edges pointing into a tombstoned node stay, keeping the graph connected until the next rebuild reclaims the space.
The IVF-PQ alternative for a memory-constrained shard trades the graph for clusters and compressed codes:
IVF-PQ segment:
centroids : float32[nlist][D] # nlist=32768 coarse clusters
codes : uint8[N][m] # m=96 PQ subquantizer codes/vector
pq_books : float32[m][256][D/m] # 256 centroids per 8-dim subvector
postings : ordinal[] per cluster # which vectors fell in each cluster
Here each 768-dim float32 vector (3,072 B) becomes m=96 bytes of PQ codes — a 32× compression to 96 GB for the billion — at the cost of approximate distances that need a re-rank pass. nlist=32768 clusters comes from the √N heuristic (√1e9 ≈ 31,623, rounded to a power of two).
The metadata store is keyed by external id and holds what the index deliberately does not:
metadata[id] = { payload: {…display…},
filter_attrs: { category, price, lang, … },
segment_version: v42 } # for staleness checks
Component internals¶
Component 1 — HNSW index (build and search)¶
Responsibility: hold 50M vectors as a graph you can greedily walk to the query's neighbors in a few thousand distance computations instead of 50M, and let a single knob trade recall for latency.
The idea is a hierarchy of graphs. The base layer (level 0) contains every vector, richly connected to its near neighbors. Each higher layer is a sparse sample of the layer below — think express lanes — so a search drops in at the top, greedily hops toward the query through sparse long-range links, then descends into denser layers for the fine approach. The two build parameters that set quality are M (edges per node — connectivity) and efConstruction (how hard the builder searches for good neighbors when inserting each node).
class HnswIndex:
def search(self, q: Vector, k: int, ef_search: int) -> list[Candidate]: ...
def insert(self, ordinal: int, vec: Vector, ef_construction: int): ...
Search — the greedy walk with a candidate frontier. Start at the entry point on the top layer. At each layer, greedily move to the neighbor closest to q, descending a layer when no neighbor improves. At the base layer, switch from pure greedy to a beam search of width ef_search: keep a candidate heap of the ef_search closest nodes seen, expand the closest unexpanded one, and stop when the frontier can no longer improve. ef_search is the recall knob — a wider frontier explores more of the graph and finds more true neighbors, at the cost of more distance computations.
def search_layer(q, entry, ef, layer):
visited = {entry}
candidates = MinHeap([(dist(q, entry), entry)]) # frontier to expand
result = MaxHeap([(dist(q, entry), entry)]) # best ef so far
while candidates:
d, node = candidates.pop_min()
if d > result.peek_max(): # frontier can't beat current worst → stop
break
for nbr in neighbors(node, layer):
if nbr in visited: continue
visited.add(nbr)
dn = dist(q, nbr)
if dn < result.peek_max() or len(result) < ef:
candidates.push((dn, nbr))
result.push((dn, nbr))
if len(result) > ef: result.pop_max()
return result
Build — incremental insertion. There is no separate "build" step distinct from inserting: the graph is built by inserting each vector one at a time. To insert a node, pick its top layer by an exponentially-decaying random draw (most nodes live only on level 0, a few get promoted), run the same greedy search down to each layer using ef_construction as the frontier width, and connect the node to its M closest found neighbors on each layer — then prune each neighbor's edge list back to M using a heuristic that keeps diverse neighbors rather than only the closest, which is what keeps the graph navigable instead of clumping.
Why HNSW here. For the scenario it delivers the recall/latency curve directly: with M=32, efConstruction=200, a per-shard 50M-vector graph hits ~95% recall@10 at ef_search≈100 with a few thousand distance computations per query — versus 50M for brute force, a ~10,000× reduction — and it supports the live inserts the freshness requirement needs. The cost is the ~3.3 KB/vector RAM footprint that forced 20 shards.
Component 2 — Query coordinator (scatter-gather + recall governor)¶
Responsibility: fan a query to all shards, merge partials into a correct global top-k, hold the deadline, and keep measured recall at the 95% floor.
class Coordinator:
def query(self, q, k, filter, ef_search=None) -> list[Match]:
ef = ef_search or self.recall_governor.current_ef() # e.g. 100
allow = self._filter_strategy(filter) # pre-filter or post
deadline = now() + self.budget_ms
# scatter: one sub-query per shard, hedged replicas
futures = [self._ask_shard(s, q, k, ef, allow, deadline)
for s in self.shards]
partials = gather_with_hedge(futures, deadline, hedge_after=self.p95_ms)
merged = merge_topk(partials, k) # global top-k by score
return self._hydrate(merged)
Merging partials is a k-way merge, not a re-sort. Each shard returns its top-k already sorted by distance, so the coordinator does a k-way merge across 20 sorted lists and takes the global top-k — O(20 × k), not a sort of 20k items. The global top-k is exact given the shard candidates: the only approximation is inside each shard's ANN search, never in the merge.
The recall governor samples a fixed ground-truth probe set (say 1,000 queries whose true neighbors were computed by brute force offline) every minute, runs them at the current ef_search, and measures recall@10. If it drifts below 95% it raises ef_search; under overload it is allowed to lower ef_search to shed load, emitting a warning. This closes the loop — recall is a measured, defended number, not a set-and-forget parameter that silently rots as the corpus grows.
Component 3 — Hybrid fusion (dense + sparse via RRF)¶
Responsibility: combine the vector ranking and the BM25 keyword ranking into one list that beats either alone, without trying to compare their incomparable raw scores.
Cosine similarities (roughly 0–1) and BM25 scores (unbounded, corpus-dependent) live on different scales, so you cannot add them directly. Reciprocal Rank Fusion sidesteps this by using only rank position: an item's fused score is the sum, over each list it appears in, of 1 / (K + rank), with K≈60 damping the weight of deep positions.
def rrf_fuse(dense: list[id], sparse: list[id], K=60, k=10) -> list[id]:
score = defaultdict(float)
for rank, doc in enumerate(dense): score[doc] += 1.0 / (K + rank)
for rank, doc in enumerate(sparse): score[doc] += 1.0 / (K + rank)
return top_k(score, k)
An item ranked #1 by vectors and #3 by keywords scores 1/61 + 1/63 ≈ 0.0323; an item that only the keyword index found at #2 scores 1/62 ≈ 0.0161. Items both lists agree on float to the top, which is the whole point — agreement across two independent signals is a stronger relevance signal than a high score in either one.
Core algorithm — building and serving the billion-vector index at 95% recall¶
Walk the scenario end to end with numbers.
1. Partition the corpus. 1B vectors ÷ 20 shards = 50M per shard, assigned by hash(id) % 20 so upserts are deterministic and shards stay balanced. Each 50M-vector HNSW segment is 50M × 3.3 KB ≈ 165 GB, fitting a 256 GB box with headroom.
2. Build each shard's graph offline. For a 50M-node HNSW at M=32, efConstruction=200, insertion is roughly O(N · efConstruction · log N) distance computations. This is hours of batch compute per shard, run in parallel across shards on the build tier, producing an immutable segment written to object storage. Nothing about this touches the serving fleet.
3. Tune ef_search to the recall floor. With the segment built, run the ground-truth probe set at increasing ef_search and read the curve:
ef_search |
recall@10 | dist. computations/query (per shard) | per-shard latency |
|---|---|---|---|
| 40 | ~90% | ~1,500 | ~2 ms |
| 100 | ~95% | ~3,500 | ~4 ms |
| 200 | ~98% | ~7,000 | ~8 ms |
Pick ef_search=100: it clears the 95% floor with margin to spare and sits at ~4 ms/shard, keeping the fan-out's end-to-end p99 comfortably under 50 ms.
4. Size replication for QPS. At ef_search=100 a shard replica sustains ~2,000 shard-queries/second. The load is 10,000 QPS × 20 shards = 200,000 shard-queries/second, so 200,000 / 2,000 = 100 replica instances, i.e. 5 replicas per shard. Those five also give the coordinator a hedge target when one replica turns slow.
5. Serve and hold the line. Each query scatters to 20 shards at ef_search=100, each shard walks ~3,500 vectors (not 50M — a ~14,000× reduction), returns its local top-10, the coordinator merges to a global top-10, and the recall governor keeps sampling to confirm the fleet is still at ~95%. If a shard grows past 50M via upserts and its graph starts to spill RAM, that shard is split before it pages — the moment the ~165 GB footprint approaches the 256 GB ceiling is the moment re-sharding is triggered, because a paging index quietly turns 4 ms into 400 ms.
Sequence diagram — a hybrid query under the deadline¶
Client Coordinator Shard 1..20 BM25 index Metadata
│ query(q, k=10, text) │ │ │
├──────────▶│ │ │ │
│ ├─ ef=100 (from recall governor) │ │
│ ├─ scatter q ─────────▶│ (20 shards, parallel) │
│ ├─ keyword search ─────┼────────────▶│ │
│ │ │ HNSW walk│ │ │
│ │◀── top-10 ─┤ (~4 ms) │ │ │
│ │ (shard 7 slow: no reply by p95) │ │
│ ├─ hedge shard 7 → replica 7b ──▶│ │
│ │◀── top-10 (7b) ──────┤ │ │
│ │◀────────────────── BM25 top-50 ───┤ │
│ ├─ merge_topk(20 lists) → dense top-k │
│ ├─ rrf_fuse(dense, sparse) → top-10 │
│ ├─ hydrate ids ────────────────────────────▶│ │
│ │◀── payloads ──────────────────────────────┤ │
│◀──────────┤ 10 matches │
The slow shard is hedged to a replica rather than allowed to define the tail; the dense and sparse lists are fused by rank; only the 10 survivors are hydrated.
Concurrency and edge cases¶
- Upsert visible before it is durable: the coordinator writes the raw vector to the durable store before inserting it into the shard's in-memory graph, so a crash between the two loses only in-memory state that a rebuild reconstructs — never an acked vector. The reverse order could ack a vector that vanishes on restart.
- Concurrent inserts into one HNSW graph: graph insertion mutates neighbor lists, so two threads wiring edges to the same node race. Guard each node's neighbor list with a fine-grained lock (per-node, not a global graph lock) so inserts parallelize while edge updates stay consistent; searches read lock-free and tolerate a momentarily-half-wired node as a tiny, self-healing recall blip.
- Delete of a vector that is a graph hub: tombstoning leaves inbound edges pointing at a dead node, so searches still traverse through it (they just don't return it). If a shard's tombstone ratio climbs past ~10%, navigation degrades and recall slips — trigger a compaction rebuild for that shard rather than waiting for the scheduled one.
- Stale segment after a re-shard: when a shard splits, some ids move to a new shard. Until every coordinator refreshes its routing table, a query might scatter to the old shard for a moved id. The metadata store's
segment_versionlets the coordinator detect and re-route, and briefly querying both the old and new shard during the cutover window guarantees no id falls through the crack — over-fetch, then dedup in the merge. - IVF centroid drift: as upserts push the data distribution away from the centroids trained at the last build, more vectors pile into fewer clusters and
nprobeno longer covers the query's true neighborhood, so recall silently decays. The recall governor catches the drift as a measured recall drop and triggers a retrain-and-rebuild — the concrete reason IVF needs periodic full rebuilds where HNSW can coast longer on incremental inserts. - Filter starves the candidate budget: a highly selective filter (
category = "rare", 0.1% of the corpus) means the HNSW walk spends itsef_searchbudget mostly on vectors it will discard, so effective recall among matching items craters. The fix is the coordinator's pre-filter path: fetch the small matching id set from the metadata store and pass it as an allow-list so the walk's budget is spent only on candidates that can survive the filter.