Design a vector similarity search service

HNSW is a layered proximity graph: search starts at the top layer and greedily moves to closer neighbours, descending layers. It gives the best recall-latency trade-off in memory (recall 0.95+ at ~1-5 ms), supports inserts incrementally, but needs full vectors plus graph links in RAM and handles deletes poorly. IVF clusters vectors with k-means into, say, 65,536 lists; a query scans only the nprobe nearest lists. Combined with product quantization (each vector compressed to 64-128 bytes, distances computed from lookup tables), it fits a billion vectors in ~100 GB of RAM, at the cost of lower raw recall, which you recover by re-ranking the top 100-200 candidates with full vectors from SSD. Disk-based graphs (DiskANN-style) keep compressed vectors in RAM and the graph plus full vectors on NVMe, giving good recall at billion scale with a few SSD reads per query. Scalar int8 quantization is a cheap middle step: 4× smaller with ~1% recall loss. So pick per collection: HNSW float or int8 for collections under ~100M with tight latency, IVF-PQ or disk graph with re-ranking for the 500M collection. Always report recall measured against exact search, never just latency.

Real queries carry filters: tenant, category, in-stock, language. Post-filtering (search top 100, then drop non-matching) fails when the filter is selective: if only 1% match, the top 100 may contain one valid result. Pre-filtering (compute the matching id set, then search only those) is exact but HNSW cannot be restricted cheaply, so with few matches you brute-force them, which is fast for up to ~50-100k candidates. In-graph filtering checks the filter during traversal and keeps walking past non-matching nodes; it works well for moderate selectivity but the graph can become disconnected for very selective filters. A good engine has a small query planner: estimate selectivity from bitmap or inverted indexes on metadata, then choose brute-force on the filtered set (very selective), in-graph filtering (moderate), or plain search with a larger k and post-filter (filter matches almost everything). For hard partitions like tenant, do better than filtering: use namespaces or partition keys so each tenant's vectors live in their own segments. Test recall separately per filter selectivity bucket, because averages hide the failures.

Graph indexes are expensive to update in place, and concurrent inserts into one big HNSW graph limit throughput. So treat the index like an LSM tree or Lucene. Writes are appended to a durable log (Kafka) partitioned by shard; that ack is the durability guarantee. Query nodes tail the log into a small growing segment searched by brute force, which makes writes visible in seconds. Sealed segments are indexed by separate builder nodes so heavy index builds never steal CPU from queries, and the resulting immutable files go to S3. An upsert of an existing id becomes 'tombstone old + insert new'; queries skip tombstoned ids through a bitmap. Compaction merges small segments and physically drops deleted vectors, keeping segment count low (too many segments means too many searches per query). For read-your-writes, the upsert returns a sequence number and the caller can pass min_sequence on a query; the node waits until it has consumed that offset. Because segments are immutable and stored in S3, adding a replica or recovering a crashed node means downloading files, not rebuilding indexes, and snapshots are just a list of segment ids.

With random (hash-of-id) sharding, every query must ask every shard, and the query is as slow as the slowest of 16 nodes. If each shard has p99 of 20 ms, the chance that at least one of 16 is slow is high, so tail latency grows with fan-out. Mitigations: keep shard count moderate by using bigger nodes; hedge requests (send to a second replica if the first has not answered in the p95 time); give each shard a deadline and return partial results with a flag rather than timing out; and keep segment counts low through compaction. Ask each shard for slightly more than k (e.g. 1.5k) only if results will be filtered further. Alternatively, partition by a semantic key (cluster centroids, like IVF across machines) so a query visits only the nearest few shards; this cuts fan-out but creates hot shards for popular regions of the space. For multi-tenant collections, partitioning by tenant gives the best of both: a tenant's query touches only its shards. Separate compute roles (proxy, query nodes, builders) let you scale QPS by adding query replicas without touching ingestion.

Raising ef_search or nprobe increases recall and latency together; PQ lowers memory cost and recall. Expose these as per-collection settings with sane defaults, and publish a measured curve (recall@10 vs p99) so teams choose consciously. RAG with a reranker after retrieval can tolerate 0.90 recall; deduplication of near-identical images may need 0.99.

Most teams under ~50M vectors are well served by pgvector or OpenSearch k-NN. A dedicated service is justified at billion scale, many teams, strict latency, or cost pressure on RAM. In an interview, say when you would not build it.

Immutable segments give simple replication, snapshots and recovery, and no locking on the hot graph, at the cost of compaction work and slightly higher query cost across several segments. In-place updates give fewer segments but complex concurrency and slow recovery.

When a team switches embedding models, 500M vectors must be rewritten and re-indexed. Create a new collection, bulk-load through builders (bypassing the growing segment), dual-write during the switch, then swap an alias. Budget builder capacity for it.

One collection can take most of the QPS during a sale. Add query replicas for its shards only, and enforce per-collection QPS quotas at the proxy so it cannot starve others.

The proxy routes to the other replica of each shard; the coordinator assigns the shard to a new node, which downloads segment files from S3 and replays the log from the last sealed offset. Recovery takes minutes, with no data loss.

Growing segments get larger, brute-force cost rises and latency climbs. Alert on build lag, cap growing segment size, and apply backpressure on upserts (429) before queries degrade.

A bad parameter change or quantization can cut recall without errors. A background prober runs 1,000 sample queries per collection hourly against exact search and alerts if recall@10 falls below target.