00. Design a Vector Search Engine (ANN)

~20 min read · Level: advanced · Part 1 of 4 (Overview → HLD → LLD → Q&A)

Problem

A vector search engine takes a query embedding — a list of a few hundred floating-point numbers that encodes the meaning of some text, image, or audio — and returns the stored items whose embeddings sit closest to it in that high-dimensional space. This is the retrieval layer behind semantic search, image similarity, recommendation candidate generation, and the "retrieve" half of every RAG pipeline. It powers Pinecone, Weaviate, Milvus, the vector indexes inside Elasticsearch and pgvector, and the internal engines behind Google's and Meta's embedding retrieval. Someone embeds the phrase "waterproof hiking boots for cold weather" into a 768-dimensional vector, and the engine hands back the 10 catalog items whose vectors are nearest by cosine similarity — even though none of them contains those exact words.

What makes this a genuine system-design problem, rather than "sort by distance," is that the naive answer does not scale. Finding the true nearest neighbors means comparing the query against every stored vector, and at a billion vectors that is a billion distance computations per query. No latency budget survives that. So the entire field is built on a bargain: give up the guarantee of finding the exact nearest neighbor, and in exchange do thousands of times less work. The engine returns approximate nearest neighbors, and the quality of that approximation — how often the items it returns are actually the true closest ones — is a number you tune, not a given.

To keep the reasoning concrete, thread one scenario through the whole design: serve nearest-neighbor search over 1,000,000,000 embeddings at 10,000 queries/second while holding roughly 95% recall. A billion 768-dimensional vectors, ten thousand searches a second, and a promise that the results the engine returns overlap the true top-k about 95% of the time. That triangle — the corpus size, the query rate, and the recall floor — pins down every decision below, because you cannot move one corner without paying at another.

Functional requirements

• k-NN search: given a query vector and a k, return the approximate k nearest stored vectors by a chosen distance metric (cosine, dot product, or L2).
• Filtered search: restrict results by structured metadata (category = "boots" AND price < 200) evaluated alongside the vector search, not as a separate pass that throws recall away.
• Hybrid search: combine dense vector similarity with sparse keyword (BM25) relevance and fuse the two ranked lists into one.
• Upsert / delete: add, update, and remove vectors, with new vectors becoming searchable within seconds to minutes, not on the next full rebuild.
• Recall/latency knob per query: let the caller trade recall for latency at request time (a search-as-you-type box wants speed; an offline dedup job wants recall).

De-scoped for this round, and worth naming so the interviewer sees it as a choice: we do not own or train the embedding model itself (vectors and query embeddings arrive already computed by an upstream service), we do not do cross-encoder reranking with a second neural model (re-ranking here means re-scoring candidates with the full-precision vectors), and we skip multi-tenant billing and access control. Those sit beside the core and do not change its shape.

Non-functional requirements

The dominant constraint is p99 tail latency at a fixed recall floor. Everything downstream — keeping the index in RAM, sharding, quantization, the choice of HNSW over brute force — exists to answer a query in tens of milliseconds without letting recall fall below the promised 95%. Latency and recall are not independent; they are the two ends of one knob, and the architecture's whole job is to hold both.

• Latency: p99 end-to-end under ~50 ms, p50 under ~15 ms, so semantic search feels as responsive as keyword search.
• Recall: hold recall@10 at ~95% against the true nearest neighbors. This is an SLO with a number, monitored continuously, not a vague "good results."
• Freshness: an upserted vector should be searchable within seconds to a few minutes. Not real-time, but not a nightly batch either.
• Availability: search reads must stay up (target four nines); index rebuilds and ingestion can tolerate more fragility than serving.
• Memory ceiling: the index must fit in aggregate RAM to hit the latency target, and RAM is the expensive resource, so memory footprint per vector is a first-class design variable, not an afterthought.

Scale estimation

Start with the corpus. 1 billion vectors at 768 dimensions, float32 is 1e9 × 768 × 4 bytes = 3.072 TB of raw vector data. That number alone kills the single-machine dream: no commodity box holds 3 TB in RAM, and reading vectors from disk per query blows the latency budget. Two levers respond to it, and the design uses both.

First, the graph index adds overhead on top of the raw vectors. An HNSW index with M = 32 neighbors per node stores roughly M × 2 × 4 bytes ≈ 256 bytes of edge pointers per vector on top of the 3,072 bytes of raw float32 — call it ~3.3 KB per vector, or ~3.3 TB for the billion. Sharded across 20 shards of 50M vectors each, that is ~165 GB of index per shard, which fits in a machine with 256 GB of RAM. So the corpus size forces sharding: 20 shards is not a scaling nicety, it is the smallest number that makes the index fit in RAM at all.

Second, quantization trades recall for a smaller footprint. Product-quantizing each 768-dim vector down to 96 bytes (a 32× compression) shrinks the billion to ~96 GB — small enough to fit far fewer machines — but the compressed distances are approximate, so recall drops and you must re-rank the top candidates against full-precision vectors. This is the recall-vs-memory tradeoff in one move, and which way you lean depends on whether RAM or recall is scarcer.

Now the query load. 10,000 QPS with 20 shards means every query fans out to all 20 shards (you do not know which shard holds a query's neighbors), so the internal work is 10,000 × 20 = 200,000 shard-queries/second. If one shard replica sustains ~2,000 shard-queries/second at the efSearch setting that yields 95% recall, you need 200,000 / 2,000 = 100 shard-serving instances — a replication factor of 100 / 20 = 5 per shard. Replication here buys QPS, not just availability: five replicas per shard is what turns 200k internal queries/second into headroom.

Bandwidth reconciles cleanly. Each query vector is 768 × 4 = 3,072 bytes ≈ 3 KB; at 10k QPS that is ~30 MB/s of ingress, trivial. But the fan-out multiplies it: the coordinator ships the query vector to all 20 shards, so internal traffic is 200,000 × 3 KB ≈ 600 MB/s — real, and a reason to keep the coordinator and shards on the same fast network and to consider not re-shipping the vector when a shard already caches recent queries. Results are tiny (k=10 IDs plus scores, a few hundred bytes), so egress is negligible.

API sketch

POST /v1/indexes/{index}/query
  body: { "vector": [0.12, -0.04, …],        # 768 floats
          "k": 10,
          "filter": { "category": "boots", "price": {"$lt": 200} },
          "ef_search": 100,                    # recall/latency knob, optional
          "hybrid": { "text": "waterproof", "alpha": 0.5 } }   # optional
  200:  { "matches": [ {"id": "sku_8412", "score": 0.87, "payload": {…}}, … ] }

POST /v1/indexes/{index}/upsert
  body: { "vectors": [ {"id": "sku_8412", "values": […], "payload": {…}}, … ] }
  200:  { "upserted": 128 }

DELETE /v1/indexes/{index}/vectors/{id}
  200:  { "deleted": true }

GET /v1/indexes/{index}/stats
  200:  { "count": 1000000000, "shards": 20, "recall_estimate": 0.951, "dim": 768 }

Solutioning

Start from the constraint that a billion vectors will not fit in one machine's RAM and that exact search is off the table, and the system shape follows. The first move is to pick an approximate index that turns "scan a billion vectors" into "walk a few thousand," and the two mainstream families are HNSW (a navigable small-world graph you greedily traverse toward the query) and IVF (partition the space into clusters, then search only the few clusters nearest the query). HNSW gives higher recall at a given latency and supports incremental inserts, but costs the most RAM. IVF plus product quantization gives a far smaller footprint and cheap inserts into existing clusters, but its recall degrades as the data distribution drifts away from the clusters it was trained on. The reframing to hold onto: serving a billion vectors at 10k QPS is not a storage problem; it is a memory-residency problem — the index has to live in RAM, and everything about sharding and quantization is in service of fitting it there while holding the latency line.

The second decision is how to spread the corpus across machines, and it is fan-out, not partition-by-key. Unlike a URL shortener where a code lives on exactly one shard, a query vector's neighbors can be on any shard, so every query scatters to all shards and the coordinator gathers and merges their top-k into a global top-k. That makes the tail latency the slowest shard's latency — one slow replica drags every query's p99 — which is why replication is sized for QPS and for hedging (fire a duplicate request to a second replica when the first is slow). The 20-shard, 5-replica layout from the math is the direct consequence: 20 to fit RAM, times 5 to serve 200k internal queries/second with a slow-replica cushion.

The third tension, and the one interviewers push hardest on, is recall versus latency, governed by a single knob. In HNSW that knob is efSearch — the size of the candidate frontier the greedy walk keeps. Turn it up and the walk explores more of the graph: recall climbs from ~90% at efSearch=40 to ~95% at efSearch=100 to ~98% at efSearch=200, but per-shard latency roughly doubles at each step (more distance computations). The engine holds 95% recall by measuring it against a ground-truth sample and tuning efSearch to sit just above the floor, rather than guessing. The memory hook: ANN at scale is not about finding the exact nearest neighbor; it is about bounding how often you miss it — recall is a dial you set, monitor, and defend, not a property you assume.

Two more decisions round out the shape. Index builds are offline and swapped in atomically: building or retraining a billion-vector index takes hours, so a build pipeline produces immutable segments in object storage and shards load them, while a much cheaper incremental path handles the trickle of upserts between builds — full rebuild for correctness and compaction, incremental for freshness. And hybrid search fuses two rankings rather than filtering one: dense vector results and sparse BM25 keyword results are each retrieved, then merged with Reciprocal Rank Fusion, because a pure vector search misses exact-term matches (product codes, rare names) and pure keyword search misses paraphrase — the two lists cover each other's blind spots, and fusing ranks sidesteps the problem that their raw scores live on incomparable scales. The following files take each decision down to components (HLD) and then to schemas, graph-build internals, and the concurrency corners where a vector index actually breaks (LLD).