Vector Search / Semantic Index

Approximate Nearest Neighbor Search

Design a service that stores a billion embeddings with metadata and returns the most similar ones to a query in tens of milliseconds, with filters, fresh writes and deletes.

Overview

An embedding is a list of numbers (a vector) that a model produces for a piece of text, an image or a product, placed so that similar things end up close together. A vector search service stores these vectors with an ID and some metadata, and answers one main question: given a query vector, which stored vectors are closest to it? Retrieval for LLM answers (RAG), semantic search and recommendations all rest on this.

Exact search compares the query with every vector. At a billion vectors of 768 numbers, that is 768 billion multiply-adds per query, far too many for tens of milliseconds. So the service uses an approximate nearest neighbor (ANN) index, which looks at a small part of the data and usually finds most of the true nearest neighbors. How often it finds them is measured as recall@k: the share of the true top k that the index returned.

Three things make the design interesting: the index must fit in memory (or be clever about disk), filters such as 'in stock and under $50' must not silently shrink the results, and new vectors and deletes must show up within seconds without rebuilding a billion-vector index.

Questions to ask first

How many vectors, how many dimensions? — 1 billion vectors of 768 float32 values, plus about 200 bytes of metadata each
Which similarity? — Cosine on normalized vectors, which then equals the dot product
How many queries, how fast? — 10,000 a second, p99 under 50 ms (a target we chose)
What recall is good enough? — 95% recall@10 (a target we chose), measured against exact search on a sample
Filters? — Yes: equality and range filters on metadata, often very selective
Writes? — About 1,000 upserts a second, visible within a few seconds; deletes must never be returned

What you will be able to do

Explain why exact search does not scale and what recall@k measures.
Explain how HNSW and IVF find neighbors, and which knobs trade recall for speed.
Size memory for a billion vectors and choose between full precision, quantization and disk-based indexes.
Handle metadata filters without returning too few results.
Take writes, deletes and shard fan-out without losing freshness or correctness.

Key concepts

Embeddings
Cosine and dot product
Recall@k
HNSW
IVF
Product quantization
Filtered search
Segments and tombstones
Scatter-gather
Re-ranking

Functional requirements

Upsert vectors by ID with metadata, in a namespace that fixes dimension and metric
Query the top k by similarity, with optional metadata filters, returning IDs, scores and metadata
Delete by ID; deleted vectors never appear in results
Fetch vectors by ID without a similarity search
Bulk import of hundreds of millions of vectors

Non-functional requirements

Query p99 under 50 ms at 10,000 queries a second (targets we chose)
95% recall@10 or better, checked continuously against exact search on sampled queries
New and updated vectors searchable within about 5 seconds
Durable writes: an acknowledged upsert survives a node crash
Add capacity by adding shards and replicas, without downtime

Interview questions

Why not just compare the query with every vector?
How does HNSW work, and which knobs matter?
How much memory does a billion vectors need, and how do you cut it?
How do you support metadata filters?
How do new vectors become searchable within seconds?
How do you delete from an HNSW index?
How do you shard and merge?
How do you know the index is still good?