Everyone builds vector search the same way the first time: load the embeddings into a list, and for each query compute the cosine similarity against every vector, then sort and take the top 10. It works on ten thousand vectors. Then the interviewer makes it the real problem: a billion 768-dimensional embeddings, a query vector has to come back with its approximate nearest neighbors in under 50ms, new vectors are upserted continuously and must be searchable within a second, the index is far too big to keep fully in RAM on one machine, and recall (how many of the true nearest neighbors you actually return) must stay above 95% even as you shard across memory-constrained nodes.
Brute-force cosine similarity cannot do any of that. It is O(N * d) per query - for a billion 768-dim vectors that is ~768 billion multiply-adds per query, and you run tens of thousands of queries per second. That is physically impossible. A vector search engine changes the problem from “compare the query to every vector” to “navigate a precomputed index that gets you to the right neighborhood in logarithmic hops, then compare against only the few hundred candidates there.” That one data structure - the approximate nearest neighbor (ANN) index, almost always HNSW or IVF - is the whole game. Get the ANN index right (how it is built, sharded, kept fresh under upserts, and tuned for the recall/latency/memory triangle) and everything else is routing and plumbing. Get it wrong and you either scan forever, return low-recall garbage, blow your memory budget, or have to re-index the world every time a vector changes.
Let me do it properly.
Functional Requirements (FR)
In scope:
- Upsert vectors. Given a vector (an id, a dense float embedding of fixed dimension d, and optional metadata like
tenant_id,created_at,category), insert or replace it in the index so it becomes searchable. Vectors arrive continuously (new documents embedded, old ones re-embedded) and must be searchable quickly - near-real-time, not a nightly rebuild. - k-NN query. Given a query vector and a
k, return thekapproximate nearest neighbors by a distance metric (cosine, dot product, or L2/Euclidean), ordered closest-first, with their ids, distances, and optionally metadata. This is the core read. - Metadata filtering. Combine the vector search with structured filters (
tenant_id = "acme",category = "docs",created_at > last week). “Find the 10 nearest vectors that also match this filter” is the common real query, not pure vector search. - Deletes and updates. Vectors get deleted or re-embedded (model upgrades, content edits). The index must reflect that without rebuilding the whole structure.
- Tunable recall. The caller (or the system) can trade recall for latency: a query can ask for higher accuracy at more cost, or faster at slightly lower recall. ANN is approximate by definition, and that approximation must be a dial, not a surprise.
- Near-real-time. A vector upserted now is searchable within ~1 second.
Explicitly out of scope (say this to control scope):
- Generating the embeddings. We index vectors handed to us. The embedding model (how text/images become vectors) is upstream; we take fixed-dimension floats as the contract. We do note embedding-version migrations because they drive mass re-index.
- Lexical / keyword search. Classic inverted-index BM25 full-text search is a different index type. We build the dense-vector ANN tier; we note where a hybrid (lexical + vector) layer bolts on.
- Re-ranking with a cross-encoder. A heavy model that re-scores the top-K candidates is a downstream precision stage. We return a good ANN top-K cheaply; we mention where the reranker attaches.
- The RAG application on top. Prompt assembly, LLM calls, chunking strategy - all upstream/downstream. We are the retrieval engine.
The one decision that drives everything: a vector search engine is a read-optimized system built around a precomputed ANN index, where the scarce resources are query latency and memory, and the central tension is the recall/latency/memory triangle. You pay a lot at build time (construct a graph or cluster the space) and in RAM (the index wants to live in memory) to make reads cheap (navigate to a neighborhood, scan a few hundred candidates). So the design is dominated by the ANN index - how it is structured, how it fits in a memory budget via quantization, how it is sharded, how it absorbs concurrent upserts without a full rebuild, and how recall holds up across shards.
Non-Functional Requirements (NFR)
- Scale: target ~1B vectors, dimension d = 768 (a typical sentence/embedding size), float32. Read-heavy: on the order of 10K-50K queries/sec at peak, with upsert throughput of ~10K-50K vectors/sec (continuous ingestion plus re-embeds). The raw vectors alone are multiple terabytes; the index must live across many nodes, and as much of it as possible in RAM.
- Latency (the hard target): p99 query latency < 50ms for a top-k search over the full corpus, including scatter-gather across shards, graph traversal, filtering, and merge. This is the number the whole design serves.
- Recall (the other hard target): recall@10 >= 95% against the true (exact) nearest neighbors. ANN trades exactness for speed; 95% recall at 50ms is the spec. Recall must not silently degrade when we shard or quantize.
- Availability: 99.9%+ for the query path. Semantic search / RAG retrieval going down is a visible outage. The system must keep serving reads when nodes fail, which forces replication.
- Consistency: search is eventually consistent and that is acceptable. A vector searchable ~1s after upsert, or a just-deleted vector appearing for a moment, is fine. We do not promise read-your-writes on the search path. The source of truth (the vectors + metadata) lives in durable storage; the ANN index is a derived, rebuildable view - but rebuilding it is expensive, so we still replicate and persist it.
- Durability: the index is derived and could be rebuilt from stored vectors, but rebuilding an HNSW graph over 1B vectors takes hours, so we treat both the raw vectors and the built index as needing durability - a write-ahead log for upserts plus persisted index segments plus replica copies, so a single node loss never forces a full rebuild and never loses an acknowledged upsert.
- Memory budget (the constraint that shapes everything): keeping 1B x 768 x 4 bytes = ~3 TB of raw float32 vectors in RAM, plus graph overhead, is wildly expensive. Memory is the binding constraint, which is why quantization and the memory/recall trade are first-class, not afterthoughts.
Back-of-the-Envelope Estimation (BoE)
Let me ground the design in numbers before drawing boxes.
Vector and index size:
Vectors: 1,000,000,000 (1B)
Dimension d: 768
float32 per component: 4 bytes
Raw vector size = 1B * 768 * 4 bytes
= 1B * 3,072 bytes
≈ 3.07 TB of raw float32 vectors.
HNSW adds a graph: each vector stores M neighbor links per layer.
With M = 32 and ~8 bytes per link id, graph overhead is roughly
1B * 32 * 8 bytes ≈ 256 GB just for the top-layer links,
and a bit more for lower layers. Call HNSW overhead ~0.3-0.5 TB.
So a full float32 HNSW index ≈ 3 TB vectors + ~0.4 TB graph
≈ ~3.4 TB, and HNSW really wants this in RAM.
Why memory is the whole fight:
3.4 TB in RAM, on nodes with (say) 128 GB RAM each usable for index:
3.4 TB / 128 GB ≈ 27 nodes MINIMUM just to hold one copy in RAM,
before replicas, before headroom. With 2 replicas: ~80 nodes.
This is the pain. The fix is quantization (shrink each vector):
Product Quantization (PQ) to ~96 bytes/vector (vs 3,072):
1B * 96 bytes ≈ 96 GB of compressed codes -> fits on ONE big node.
Scalar quantization (int8) to ~768 bytes/vector:
1B * 768 ≈ 768 GB -> a handful of nodes.
Quantization is not optional at a billion vectors; it is how the
index fits in a sane memory budget at all. (It costs some recall;
we rescore with full-precision vectors to win it back - deep dive.)
Query load (reads):
Peak queries/sec: 50,000 QPS
Each query scatters to all shards it must touch (corpus-wide
semantic search touches every shard), each runs an ANN search.
Fan-out factor: ~N shards (say 50) per user query.
Effective internal shard-searches/sec = 50K * 50 = 2,500,000
shard-level ANN searches per second across the cluster.
Per node (say 50 nodes, 1 shard each): ~50K ANN searches/sec/node.
Each ANN search visits ~efSearch (say 128-512) candidate vectors
and computes a distance per candidate. 512 * 768 multiply-adds
≈ 400K FLOPs per shard search - trivial vs brute force's 768B.
That 1,000,000x reduction is the entire point of the ANN index.
Upsert/write load:
Upsert rate: ~20,000 vectors/sec sustained
Each upsert: append to WAL, insert into the in-memory graph of
the target shard (HNSW insert is ~O(log N) graph hops * M links).
WAL write: 20K * ~3 KB (vector + metadata) ≈ 60 MB/sec durable
append across the cluster, spread across shards.
Periodically, in-memory segments are flushed and merged into the
big immutable index (the re-index cost; covered in the deep dive).
Cache / RAM sizing:
The index IS the cache - ANN wants to be RAM-resident:
1. Compressed (PQ/int8) codes + graph for every shard, in RAM.
With PQ at ~96 GB for 1B vectors, this is affordable.
2. Full-precision vectors for the top candidates, used to
RESCORE after the quantized search. These can live on
fast SSD or a slice of RAM; only the top few hundred per
query are read in full precision.
3. Query/result cache for repeated identical queries is weak
here (query vectors are rarely byte-identical), so we lean
on the index being fast, not on a result cache.
The takeaway: this is a memory-bound, read-amplified, fan-out system. One user query becomes tens of parallel shard ANN searches, and the 50ms p99 is a budget split across all of them plus the gather-and-merge - while the whole index is fighting to fit in RAM. Every design choice - the index type (HNSW vs IVF), quantization, shard key, upsert handling, replica placement - exists to keep that fan-out fast, the recall high, and the memory footprint survivable.
High-Level Design (HLD)
A vector search engine is two paths that meet at the ANN index: an upsert path (vectors in, ANN index built and kept fresh) and a query path (query vector in, scatter to shards, ANN search, gather, merge, optionally rescore, return). The index is partitioned into shards (for scale and memory) and each shard has replicas (for availability and read throughput). A coordinator routes queries and upserts; it holds no index data itself.
UPSERT PATH QUERY PATH
┌──────────────────┐ ┌──────────────────┐
│ Upsert API │ │ Query API │
│ (vectors in) │ │ (query vec + k) │
└────────┬─────────┘ └────────┬─────────┘
│ │
┌────────▼───────────────────────────────────────────▼─────────┐
│ COORDINATOR NODE │
│ - route vector to shard (hash(id) or learned route) (write) │
│ - scatter query to one replica of EACH shard (read) │
│ - gather partial top-k, merge by distance, rescore (read) │
└───────┬───────────────────────────────────────────┬──────────┘
│ upsert scatter │ query
│ (fan-out) │
┌────────▼───────────┐ ┌───────────────┐ ┌────────▼─────────┐
│ SHARD 1 group │ │ SHARD 2 grp │...│ SHARD N group │
│ ┌───────┐┌───────┐ │ │ │ │ │
│ │PRIMARY││REPLICA│ │ │ PRIMARY │ │ PRIMARY │
│ │ ││ x2 │ │ │ REPLICA x2 │ │ REPLICA x2 │
│ └───┬───┘└───────┘ │ └───────────────┘ └──────────────────┘
└─────┼──────────────┘
│ inside one shard:
┌────▼──────────────────────────────────────────────┐
│ WAL (durable append) │
│ WRITE BUFFER: small in-memory HNSW (fresh upserts)│
│ │ periodic flush + merge │
│ ▼ │
│ IMMUTABLE INDEX SEGMENTS (quantized HNSW/IVF) │
│ + full-precision vectors (SSD/RAM) for rescore
│ A shard search = search buffer + all segments, merge
└────────────────────────────────────────────────────┘
┌──────────────────────────────────────────────────────────────┐
│ Cluster control plane (Raft-backed master nodes): │
│ shard allocation, replica placement, node health, failover │
└──────────────────────────────────────────────────────────────┘
Upsert path - one vector, end to end:
- A vector hits the Upsert API and reaches a coordinator. The coordinator computes the target shard:
shard = hash(id) % num_shards(or a tenant-based route - covered in the deep dive). - The write goes to that shard’s primary. The primary first appends the operation to its WAL (write-ahead log) so the upsert survives a crash, then inserts the vector into an in-memory write buffer - a small, mutable HNSW graph holding only recent upserts.
- The primary forwards the operation to its replicas in parallel. Once enough copies ack, the upsert is acknowledged to the client. This is what makes an acked upsert durable and highly available.
- The vector is now searchable (it is in the in-memory buffer, which every query also searches). This gives near-real-time freshness without touching the big immutable index.
- In the background, the write buffer is periodically flushed into a new immutable index segment (a quantized HNSW/IVF structure), and small segments are merged into larger ones. This is where the expensive index construction happens, off the hot path. The WAL is truncated once its operations are safely in persisted segments.
Query path - one search, end to end:
- A query vector +
k+ optional filter hits the Query API and a coordinator. - The coordinator scatters the query to one replica of every shard group (it only needs one copy of each shard’s data). This is the fan-out - a corpus-wide semantic query touches every shard.
- Each shard, in parallel, runs an ANN search against its local index: navigate the HNSW graph (or probe the nearest IVF cells) using the compressed/quantized vectors to cheaply find candidate neighbors, applying the metadata filter during traversal, and returns its local top-k candidates
(id, approx_distance). This is the cheap, approximate phase. - The coordinator gathers the partial top-k lists from all shards and merges them by distance into a global candidate set (say the top few hundred).
- Rescore (optional but standard): because the ANN phase used quantized vectors, the coordinator (or the owning shards) recomputes exact distances for the merged candidates using the full-precision vectors, and re-sorts. This recovers the recall that quantization cost. It only touches the final few hundred candidates, not the billion.
- The coordinator assembles the final top-k (ids + distances + optionally metadata/source) and returns it.
Failure handling: if a shard replica is slow or down during scatter, the coordinator routes that shard’s query to another replica (adaptive replica selection); if a primary dies, the control plane promotes a replica to primary (failover). Because the WAL + replicas hold every acked upsert and segments are persisted, no acknowledged data is lost and no full rebuild is forced.
The architectural insight: the ANN index is partitioned for scale and memory and replicated for speed and safety, every query is a parallel scatter-gather whose latency is set by the slowest shard, and quantization plus a two-stage (approximate then rescore) search is how you hit high recall under a tight memory budget. Coordinators are stateless routers; the intelligence (graph traversal, quantized distance, filtering, rescore) lives inside each shard.
Component Deep Dive
Four hard parts: (1) the ANN index itself - HNSW vs IVF - and how a search executes fast, (2) fitting a billion vectors in a memory budget via quantization while keeping recall high, (3) concurrent upserts without a full re-index, and (4) sharding plus filtered scatter-gather under 50ms. I walk each from naive to scalable.
1. The ANN Index: HNSW vs IVF and Fast Search
The ANN index answers “which stored vectors are closest to this query vector?” without comparing against all of them. Everything hinges on it.
Approach A: Brute-force exact k-NN (the naive instinct)
Store all vectors; for each query, compute the distance to every vector, sort, take top-k.
query q:
for each of 1,000,000,000 vectors v:
dist[v] = cosine(q, v) # 768 multiply-adds
return top-k smallest dist
Where it breaks - immediately and fatally: this is O(N * d) per query. At 1B vectors x 768 dims that is ~768 billion multiply-adds per query, and you run tens of thousands of queries/sec. Even with SIMD and GPUs this is orders of magnitude over budget. It is exact (100% recall) but hopelessly slow. The access pattern - touch every vector - is exactly what we must avoid. (Brute force is still useful as a ground-truth oracle to measure recall offline, just not as the serving path.)
Approach B: IVF (inverted file / cluster-and-probe)
Partition the vector space into clusters once, at build time. Search only the few clusters nearest the query.
BUILD: run k-means to find, say, 65,536 centroids (cluster centers).
assign every vector to its nearest centroid -> inverted lists:
centroid_12 -> [ v5, v88, v301, ... ] (vectors in cell 12)
centroid_13 -> [ v6, v41, ... ]
...
SEARCH q:
1. compare q to the 65,536 centroids (cheap), pick the nProbe
nearest cells (say nProbe = 32).
2. scan ONLY the vectors in those 32 cells, compute distances,
return top-k.
- Why it is fast: you compare against ~32 cells out of 65,536, so you scan roughly
32/65536 ≈ 0.05%of the corpus (~500K vectors instead of 1B). That is a ~2000x reduction. - The recall knob is
nProbe: probe more cells -> higher recall, more scan, more latency. Probe fewer -> faster, lower recall. This is the explicit recall/latency dial. - The weakness: vectors near a cell boundary may have their true nearest neighbor in an adjacent, un-probed cell -> missed, hurting recall. And building requires a representative training set for k-means. IVF shines for very large, more static datasets where its small memory overhead (just centroids + lists) matters, and it pairs naturally with PQ (next deep dive).
Approach C: HNSW (hierarchical navigable small-world graph)
Build a multi-layer graph where each vector is a node linked to its ~M nearest neighbors, with sparse upper layers for long-range jumps. Search = greedy navigation down the layers.
LAYER 2 (sparse, long hops): o--------------o--------o
| |
LAYER 1 (denser): o--o--o------o--o--o--o--o
| | | | | | |
LAYER 0 (all vectors): o-o-o-o-o-o-o-o-o-o-o-o-o-o-o
SEARCH q:
1. enter at the top layer's entry point.
2. greedily hop to the neighbor closest to q; descend a layer
when no neighbor is closer.
3. at layer 0, do a best-first search keeping the efSearch
closest candidates found; return the top-k of those.
- Why it is fast: navigation is ~O(log N) hops. The upper layers are an express highway to the right neighborhood; layer 0 refines. A search visits ~
efSearchcandidate nodes (say 128-512), not a billion. - The recall knobs:
M(links per node, set at build) controls graph connectivity/quality;efSearch(candidate list size, set at query time) is the latency/recall dial - biggerefSearch= more candidates visited = higher recall, more latency.efConstructiontunes build quality. - The weakness: HNSW has high memory overhead (it stores the graph links and wants the vectors in RAM), and inserts mutate the graph (the concurrency challenge - deep dive #3). It generally gives the best recall-at-low-latency of any ANN method, which is why it dominates production systems.
Choosing, and what breaks next
| Index | Build cost | Memory | Query speed | Recall | Upserts | Verdict |
|---|---|---|---|---|---|---|
| Brute force | none | full vectors | O(N*d), far too slow | 100% | trivial | Oracle only |
| IVF (+PQ) | k-means train | low (centroids+codes) | fast, nProbe dial | good, boundary misses | re-train drift | Best for huge/static, tight memory |
| HNSW | high (graph build) | high (graph+vectors) | fastest at high recall | best | graph mutation | Default for most workloads |
The common production answer: HNSW for the recall/latency it buys, combined with quantization (next) to survive the memory cost; IVF+PQ when the dataset is enormous and more static and memory is the hardest constraint. Many engines offer both. Either way, a single index over 1B vectors is terabytes and cannot live on one node, nor serve 50K QPS - which forces sharding (deep dive #4). The index structure is correct; it just has to be cut into shards and compressed.
2. Fitting a Billion Vectors in RAM: Quantization and the Recall/Memory Trade
HNSW wants the vectors in RAM, but 3 TB of float32 is brutally expensive. The whole second battle is shrinking each vector while keeping recall high.
Approach A: Keep full float32 in RAM (naive)
Store every 768-dim float32 vector as-is in memory.
Where it breaks: 1B x 3,072 bytes = ~3 TB, plus graph overhead, needs dozens of big-RAM nodes just for one copy. RAM is the dominant cost of the whole system, and you multiply it by replicas. At a few million vectors this is fine; at a billion it makes the system uneconomical. Memory, not CPU, is the wall.
Approach B: Scalar quantization (int8)
Map each float32 component to an int8 (1 byte) using a per-dimension min/max scale.
float32 component (4 bytes) -> int8 (1 byte) # 4x smaller
v_q[i] = round( (v[i] - min[i]) / (max[i]-min[i]) * 255 )
768 dims: 3,072 bytes -> 768 bytes per vector.
1B vectors: 3 TB -> 768 GB. Distances computed on int8 (SIMD-fast).
- Simple, 4x smaller, small recall loss (often <1% with rescore), and int8 SIMD distance is actually faster than float32. A solid default first step.
- Still 768 GB - better, but a billion vectors still spans several nodes.
Approach C: Product Quantization (PQ) - the big win
Split each 768-dim vector into m sub-vectors (say m=96, each 8-dim). For each sub-space, learn a codebook of 256 centroids via k-means. Replace each sub-vector with the 1-byte id of its nearest centroid.
vector (768 float32 = 3,072 bytes)
split into 96 sub-vectors of 8 dims each
each sub-vector -> nearest of 256 centroids -> 1 byte code
stored as 96 bytes of codes. # 32x smaller!
1B vectors: 3 TB -> ~96 GB. Fits on ONE big-RAM node per copy.
DISTANCE (asymmetric): precompute, per query, a lookup table of
query-subvector-to-each-centroid distances (96 x 256 entries),
then a vector's approx distance = sum of 96 table lookups.
No full float math per candidate - just table adds. Very fast.
- PQ is how a billion vectors becomes affordable. 32x compression turns a dozens-of-nodes problem into a few nodes, and asymmetric distance (ADC) via table lookups is cheap.
- The cost is recall. PQ codes are lossy; two different vectors can share codes, so the approximate distances are noisy and the ANN phase returns a slightly wrong ordering.
The fix that makes quantization safe: two-stage search with rescore
This is the key pattern. Use the compressed index for the cheap first pass, then re-rank the finalists with exact distances.
STAGE 1 (cheap, over the whole shard): search the HNSW/IVF graph
using PQ/int8 distances. Over-fetch: ask for top-200, not top-10.
STAGE 2 (rescore, tiny): for those ~200 candidates, load their
FULL-PRECISION float32 vectors and recompute exact distances,
then re-sort and keep the true top-10.
- The lossy, compressed index gives you the right neighborhood (200 candidates that almost certainly contain the true top-10); exact rescoring on 200 vectors is cheap and restores recall to 95%+.
- Full-precision vectors only need to be reachable for rescore - they can live on fast SSD or a RAM slice, read only for the few hundred finalists per query, not held in the hot index. This decouples the memory-cheap search index from the full-precision rescore store.
So the memory strategy is layered: PQ/int8 codes + graph live in RAM for the fast approximate search; full-precision vectors live cheaper (SSD/cold RAM) and are touched only to rescore the top candidates. Over-fetch factor and whether you rescore are additional recall/latency dials on top of efSearch/nProbe.
3. Concurrent Upserts Without a Full Re-Index
Vectors arrive at 20K/sec and must be searchable within ~1s, without rebuilding the billion-node graph and without losing acked upserts on a crash. The naive approaches all fail; the solution is a mutable write buffer plus immutable persisted segments plus a WAL.
Approach A: Insert directly into the big HNSW graph (naive)
On each upsert, run the HNSW insert against the full billion-node graph in place.
Where it breaks: an HNSW insert searches the graph for the new node’s neighbors and then rewrites the neighbor lists of multiple existing nodes (the back-links). At a billion nodes under 50K concurrent reads/sec, these in-place graph mutations need locking against readers - a node’s neighbor list being rewritten while a query traverses it corrupts the search. Fine-grained locking the whole graph kills query throughput, and the insert itself competes for the same hot RAM the queries need. Worse, deletes are even nastier: HNSW has no clean node removal - you cannot just cut a node without orphaning parts of the graph. In-place mutation of a huge shared graph at this rate is a non-starter.
Approach B: Segmented index - small mutable buffer + immutable segments
Never mutate the big index. Insert new vectors into a small in-memory HNSW buffer; periodically flush that buffer into a new immutable segment; search is the union of buffer + all segments.
new upserts ─► small in-memory MUTABLE HNSW (the write buffer)
│ every ~1s searchable; flush when it grows
▼
new IMMUTABLE segment (quantized HNSW/IVF, persisted)
│
searchable shard = write_buffer ∪ seg0 ∪ seg1 ∪ seg2 ...
A query searches the buffer AND every segment, then merges top-k.
- The buffer is small, so mutating it is cheap and the lock contention is bounded (a few thousand nodes, not a billion). Fresh upserts are instantly searchable there - that is the near-real-time freshness.
- Immutable segments buy lock-free reads. Once a segment is built it never changes, so queries traverse it with no locks at all. Writers only ever append a new segment. This decouples readers from writers, which is how you sustain 50K QPS and 20K upserts/sec at once.
- Deletes become tombstones. You cannot cleanly remove a node from an immutable HNSW segment, so a delete just records the id in a per-segment “deleted” bitmap; queries skip tombstoned ids in their results; the space is reclaimed later during a merge. An update/re-embed is a delete of the old id + an insert of the new vector into the buffer.
The problem Approach B creates: segment explosion
Flushing a buffer every few seconds piles up many segments, and a query must search every segment and merge - so query latency grows with segment count. Hundreds of little HNSW graphs is slow.
Approach B-fixed: background merge / compaction (and this is the “re-index,” done incrementally)
A background process merges many small segments into fewer large ones by rebuilding a fresh HNSW/IVF over the union of their live (non-tombstoned) vectors, then atomically swapping it in.
seg0 seg1 seg2 (small, some tombstones) ──merge──► seg_A (large, clean)
During merge: tombstoned vectors are physically dropped, a fresh
compact graph is built over the survivors, the new segment is
swapped in, old segments deleted. Reads keep using old segments
until the atomic swap, so no query blocks.
- This is incremental re-indexing. Instead of ever rebuilding the whole billion-vector index, you continuously rebuild small pieces in the background. The expensive graph construction happens off the hot path, bounded to one segment at a time. The system never needs a global stop-the-world re-index for normal upserts/deletes.
- Merges reclaim deletes and keep segment count low so query fan-out across segments stays cheap. Merge throttling keeps it from starving query traffic.
- The one case that does force a global rebuild: an embedding-model version change re-embeds every vector into a new space, which is a genuine full re-index. The pattern is to build the new-model index in a shadow index alongside the live one and cut over atomically - never mutate in place. That is the exception that proves the rule: normal upserts never need it.
Durability: the WAL
A vector in the in-memory write buffer is searchable but not yet in a persisted segment; a crash would lose it. So every upsert is first appended to a per-shard WAL (fsync per request or per short interval) before entering the buffer. On restart, the shard replays the WAL to rebuild the un-flushed buffer, and reloads persisted segments from disk. No acked upsert is lost. The WAL is truncated up to the point where a flush has persisted those operations into a segment.
So three clocks run per shard: flush (buffer -> immutable segment, by size/time), merge (compact segments, continuous background), and WAL truncation (after flush). Confusing freshness (buffer, instant) with persistence (flush, periodic) is the classic mistake.
4. Sharding and Filtered Scatter-Gather Under 50ms
The index does not fit on one node (memory) and one node cannot serve 50K QPS, so we cut it into shards, each a complete, independent ANN index over a subset of vectors. The hard questions are how to partition, how a query reassembles results, and how to filter without wrecking recall or latency.
Partitioning: random vs semantic vs tenant
- Random partition (
shard = hash(id) % N): each shard holds a random slice. A query must fan out to all shards (any shard might hold a true neighbor), but each shard’s ANN search is independent and parallel, and load is perfectly even. This is the safe default - no shard is hotter than another, and recall is preserved because together the shards cover the whole space. Downside: full fan-out on every query. - Semantic partition (cluster vectors, put each cluster on a shard): route a query only to the shards whose region it falls in, pruning fan-out. Tempting, but it recreates the IVF boundary problem at the shard level - a query near a region boundary has true neighbors on an un-probed shard, tanking recall - and it creates hot shards when queries cluster (everyone searches the “popular” region). Generally rejected for general search; the recall risk is not worth the fan-out saving.
- Tenant partition (route by
tenant_id): in multi-tenant systems, keep each tenant’s vectors together (one or a few shards). A tenant-scoped query then hits only that tenant’s shards instead of all N - a huge fan-out reduction and natural data isolation. This is the big practical win and is how production vector DBs scope “namespaces.” Watch for skew: a giant tenant needs its own dedicated shards.
Default to random (or tenant-scoped) partitioning; reject semantic partitioning because it sacrifices recall and creates hot shards.
The scatter-gather, and why the slowest shard owns your p99
A corpus-wide query fans out to all N shard groups (one replica each), each returns its local top-k candidates (over-fetched for rescore), and the coordinator merges by distance and rescores. Total latency is max(shard latencies) + merge + rescore. With an N-way fan-out, p99 is governed by the slowest of N parallel searches - classic tail-latency amplification. Fixes:
- Right-size shards. Each shard small enough that its ANN search is fast and its index fits comfortably in its node’s RAM (the memory constraint caps shard size directly - this is unusual vs other systems where latency caps it). More shards = each faster but more fan-out coordination; fewer = less coordination but each slower and more RAM-hungry.
- Adaptive replica selection. Send each shard’s sub-query to the replica currently fastest/least-loaded, not round-robin, so one slow node does not drag the whole query.
- Over-fetch then rescore centrally. Each shard returns top-200 approx candidates; the coordinator merges and rescores with full precision once. Over-fetching guards recall against the case where a shard’s true neighbors ranked just outside its local top-k under quantization noise.
- Tenant routing to collapse fan-out. When the query carries a
tenant_id, hit only that tenant’s shard(s). This is the single biggest latency lever for multi-tenant workloads.
Filtered search: the trap that quietly destroys recall
The real query is “10 nearest vectors where category = docs and created_at > X.” There are three ways to combine filtering with ANN, and the naive two are broken.
PRE-FILTER (filter first, then search the survivors):
get the set of ids matching the filter, then ANN over just those.
BREAKS: the HNSW graph is built over ALL vectors; you cannot
cheaply traverse "only the subset" - the graph's navigation may
route you through excluded nodes with no in-subset neighbors,
stranding the search. For a tiny subset, it is near brute force.
POST-FILTER (ANN first, then drop non-matching results):
do a normal top-k ANN, then throw away results failing the filter.
BREAKS: if the filter is selective (matches 0.1% of vectors), your
top-200 ANN candidates may contain ZERO matches -> you return
nothing or must re-query with a bigger k, blowing latency/recall.
The production answer is filtering during graph traversal (in-line / single-stage filtering):
- Evaluate the metadata predicate on each node as the graph search visits it, keeping only matching nodes in the candidate list but continuing to traverse through non-matching nodes (so navigation is not stranded). This keeps recall high without the pre/post-filter failure modes.
- For high-cardinality, frequently-used filters (like
tenant_id), do not filter at all - partition so each value is its own shard/namespace, and the filter becomes routing (free). This is why tenant partitioning matters. - For low-selectivity filters (match most vectors), post-filter is actually fine and cheap. For extreme selectivity (match a handful), fall back to a brute-force exact scan over just the matching subset - if the filter yields 5,000 vectors, exact k-NN over 5,000 is trivially fast and perfectly accurate, beating any ANN trick. Pick the strategy by estimated selectivity.
So the filtering strategy is adaptive: route when you can (partition by the filter), filter in-line during traversal for general predicates, and brute-force the subset when the filter is extremely selective. A single fixed strategy will wreck either recall or latency on some query shape.
API Design & Data Schema
A vector search engine exposes an upsert API, a query API, and an admin API. Internally it is a set of specialized stores.
Upsert / vector API
POST /indexes/{index}/vectors/upsert # insert or replace vectors
{
"vectors": [
{ "id": "doc_8812",
"values": [0.021, -0.44, ...], # 768 float32
"metadata": { "tenant_id": "acme",
"category": "docs",
"created_at": "2026-11-19T..." } },
... # batched, thousands/request
]
}
-> routed by id (or tenant) to shard, WAL-appended, buffer-inserted,
replicated.
-> { "upserted": 1200, "shard_hits": [3,7,9] }
POST /indexes/{index}/vectors/delete # tombstone by id or filter
{ "ids": ["doc_8812", "doc_9001"] }
(or) { "filter": { "category": "stale" } }
POST /indexes/{index}/vectors/fetch # get raw vectors by id
{ "ids": ["doc_8812"] }
Query / search API
POST /indexes/{index}/query
{
"vector": [0.011, -0.33, ...], # query embedding (768)
"top_k": 10,
"metric": "cosine", # cosine | dotproduct | euclidean
"filter": { # metadata predicate
"tenant_id": { "$eq": "acme" },
"created_at": { "$gt": "2026-11-01" }
},
"namespace": "acme", # scopes fan-out to a tenant shard
"ef_search": 256, # recall/latency dial (HNSW)
"rescore": true, # exact rescore of candidates
"include_metadata": true
}
-> {
"took_ms": 21,
"matches": [
{ "id": "doc_441", "score": 0.912, "metadata": {...} },
{ "id": "doc_77", "score": 0.903, "metadata": {...} },
...
]
}
Admin API
PUT /indexes/{index} # create index
{ "dimension": 768,
"metric": "cosine",
"index_type": "hnsw", # hnsw | ivf_pq
"params": { "M": 32, "ef_construction": 200,
"pq_subvectors": 96 },
"shards": 50, "replicas": 2 }
POST /indexes/{index}/_compact # force segment merge (off-peak)
GET /cluster/health # shard allocation, node status
POST /indexes/{index}/_reindex # shadow rebuild (e.g. new model)
Data model - specialized stores, not a single DB
The index is not stored in a relational database. SQL vs NoSQL is the wrong framing: a vector engine is its own storage engine built around the ANN index, and it sits alongside a durable blob/object store for the raw vectors. We choose a purpose-built (NoSQL-style) store because the core access pattern - “nearest vectors by distance” - is not expressible as an indexed column scan in a relational DB; no B-tree helps you with high-dimensional proximity. (pgvector bolts HNSW onto Postgres for smaller scale, but at a billion vectors you want the dedicated engine.)
1. Per-shard ANN index (the graph/cluster structure + quantized codes, RAM-resident):
hnsw_index (per segment, per shard, in RAM)
node_id INT64 # internal id
pq_code BYTES[96] # product-quantized vector (or int8[768])
neighbor_links PER LAYER # M ids per layer (the graph)
entry_point INT64 # top-layer start node
- immutable per segment; the hot structure every query traverses
- size driven by quantization choice (deep dive #2)
ivf_index (alternative)
centroids FLOAT32[nlist][d] # cluster centers (small, RAM)
inverted_lists centroid -> [ (node_id, pq_code), ... ]
2. Full-precision vector store (for rescore, SSD or cold RAM):
vectors_full
id STRING (external) -> node_id (internal)
values FLOAT32[768] # exact vector
- read ONLY in the rescore phase for the merged top candidates
- cheaper tier (SSD); not in the hot search path
3. Metadata store (columnar, for filtering):
metadata (column-oriented, per field)
node_id -> { tenant_id, category, created_at, ... }
- stored column-wise so a filter predicate reads one column
- supports the in-line filtering during traversal (deep dive #4)
- tenant_id often promoted to a PARTITION/namespace key, not a filter
4. WAL (per-shard write-ahead log, durability):
wal
seq_no INT64 # monotonic per shard
op ENUM # upsert | delete
id STRING
payload BLOB # vector + metadata, for replay
- append-only, fsynced; replayed on crash recovery
- truncated up to the last flush (segment persist) point
5. Cluster metadata (on Raft-backed master nodes):
cluster_state
index -> { dimension, metric, index_type, params, shards, replicas }
shard -> { primary_node, [replica_nodes], segment_list, state }
nodes -> { id, address, ram_free, health }
- small, strongly consistent (Raft), the source of truth for
WHERE each shard/segment lives; consulted to route reads/writes
Why these choices: the ANN index is a read-optimized, RAM-resident graph/cluster structure with quantized codes - not rows - because high-dimensional nearest-neighbor is not a relational operation. Full-precision vectors are split into a cheaper tier read only for rescore, since keeping all of them in RAM is the memory problem we are solving. Metadata is columnar so filters touch one field. The WAL is a classic durability log. Cluster metadata is small and strongly consistent, so it lives in a Raft store separate from the huge, eventually-consistent index data. The durable source of truth for the raw vectors lives in object storage / a primary datastore; the ANN index is a derived, rebuildable projection fed by the upsert path or a CDC/embedding pipeline.
Bottlenecks & Scaling
Where it breaks first, in order, and the fix for each:
1. Brute-force k-NN per query (breaks before anything else). O(N * d) per query dies at a few hundred thousand vectors.
Fix: an ANN index (HNSW or IVF) that navigates to the right neighborhood in ~O(log N) hops / a few probed cells, scanning hundreds of candidates instead of a billion, with efSearch/nProbe as the explicit recall/latency dial. This is the foundational fix everything else builds on.
2. Index too big for RAM. 1B x 768 float32 = ~3 TB plus graph; RAM is the dominant, binding cost. Fix: quantization - int8 (4x) or Product Quantization (32x, ~96 GB for 1B) to shrink codes so the search index fits in a sane RAM budget, with two-stage search: approximate search on quantized codes, then exact rescore of the top ~200 candidates using full-precision vectors kept on a cheaper tier. Recall comes back to 95%+ while memory stays affordable.
3. Index too big for one node / one node too slow. Even compressed, the corpus and 50K QPS exceed one machine.
Fix: sharding - partition vectors across nodes (random hash(id) by default, tenant_id for multi-tenant), each shard a complete independent ANN index. Scales linearly by adding shards/nodes; shard size is capped by per-node RAM. Semantic partitioning is rejected (recall boundary misses + hot shards).
4. Tail latency from scatter-gather. An N-way fan-out makes p99 the max of N parallel shard searches; one slow shard ruins the query. Fix: adaptive replica selection (fastest replica per shard), right-sized shards, over-fetch + central rescore, and tenant routing to collapse fan-out to one shard/namespace when the query is tenant-scoped.
5. In-place graph mutation on upsert (write path). Inserting into the billion-node HNSW graph needs locking against readers and has no clean delete; impossible at 20K upserts/sec. Fix: segmented index - a small mutable in-memory HNSW write buffer (instant searchability) plus immutable persisted segments (lock-free reads), with deletes as tombstones and updates as delete+reinsert.
6. Segment explosion / incremental re-index. A new segment every few seconds means many segments and queries that search them all. Fix: background merge/compaction - rebuild fresh compact HNSW/IVF over the live vectors of several small segments and atomically swap in, physically dropping tombstones. This is incremental re-indexing - the system never stops the world to rebuild the whole billion-vector graph for normal upserts. A shadow index handles the one true full rebuild (embedding-model version change).
7. Durability vs a crash before flush. The write buffer is searchable but not persisted; a crash loses it. Fix: a per-shard WAL fsynced on each upsert and replayed on restart; periodic flush persists segments and truncates the WAL. Flush, merge, and WAL truncation run on independent schedules.
8. Node failure / availability. A node holding a primary dies; without copies, that shard’s data and the RAM-resident graph are gone and queries over it fail. Fix: replica shards on different nodes - upserts go primary -> replicas and ack after enough copies; reads use any replica. On primary loss, the control plane promotes a replica (failover). WAL + replicas + persisted segments mean no acked upsert is lost and no full rebuild is forced.
9. Filtered search wrecking recall or latency. Pre-filter strands graph traversal; post-filter returns nothing on selective filters. Fix: adaptive filtering - partition by high-cardinality filters (tenant_id becomes routing, free), filter in-line during traversal for general predicates (keep matches, traverse through non-matches), and brute-force the subset when a filter is extremely selective (exact k-NN over a few thousand survivors is trivially fast and perfectly accurate).
10. Hot shards / skew and recall drift. A giant tenant overloads one shard; k-means centroids (IVF) drift as the data distribution shifts.
Fix: random hash(id) routing spreads load; dedicate shards to huge tenants; for IVF, periodically re-train centroids on current data (in a shadow index) when recall degrades. Monitor recall continuously against a brute-force oracle on a query sample - recall drift is silent otherwise.
Wrap-Up
The trade-offs that define this design:
- Approximate, not exact - and that is a dial, not a defect. Brute-force exact k-NN is impossible at a billion vectors, so we navigate an ANN index (HNSW/IVF) that trades a few percent of recall for a 1,000,000x speedup, and we expose the trade as explicit knobs (
efSearch,nProbe, over-fetch) so callers choose their point on the recall/latency curve. - Memory is the binding constraint, so quantize and rescore. A billion float32 vectors do not fit in RAM affordably, so we compress with PQ/int8 (up to 32x) to make the search index RAM-resident, accept that compressed distances are noisy, and recover recall by exactly rescoring only the top few hundred candidates with full-precision vectors from a cheaper tier. The memory-cheap search index and the full-precision rescore store are deliberately separate layers.
- Never re-index the world. Upserts go into a small mutable buffer (instant freshness) and flush to immutable segments (lock-free reads); background merge rebuilds small pieces incrementally; deletes are tombstones reclaimed at merge. Only an embedding-model change forces a true full rebuild, done as an atomic shadow-index cutover. We trade ~1s staleness and merge write-amplification for sustained concurrent reads and writes without ever stopping the world.
- Document-random (or tenant) partition, not semantic. We shard by
hash(id)so load is even and recall is preserved, accepting full fan-out, and we collapse fan-out to a namespace when the query is tenant-scoped. We reject semantic partitioning because region boundaries would silently drop true neighbors and concentrate load. - Filter adaptively. Route by high-cardinality filters, filter in-line during graph traversal for general predicates, and brute-force extremely selective subsets - because any single fixed filtering strategy wrecks either recall or latency on some query shape.
- Replicate for both speed and survival. Replica shards serve read throughput and stand by for failover, while a per-shard WAL plus persisted segments guarantee no acked upsert is lost and no node loss forces a rebuild.
One-line summary: a document-sharded, quantized HNSW (or IVF+PQ) index returns approximate nearest neighbors in a parallel scatter-gather under 50ms, a two-stage approximate-then-rescore search keeps recall above 95% inside a tight RAM budget, a mutable buffer plus immutable segments plus background merge absorb concurrent upserts and deletes without ever re-indexing the world, and replica shards with a WAL make the whole thing fault-tolerant at a billion vectors - trading a few percent of exactness and ~1s freshness for cheap, high-recall, highly available semantic retrieval.
Comments