Vector Search hard
A corpus is hash-sharded across 32 shards. Each shard's in-memory HNSW search has a p50 of 3 ms and a p99 of 25 ms. The coordinator sends every query to all shards, asks each for its top 10, and merges the results. Global p50 is around 20 ms, and global p99 is far above 25 ms. What explains this, and what is a sound mitigation?
- A Each shard must return its top 320 (k × shards) to guarantee a correct global top 10, and moving those results dominates.
- B The query waits for the slowest shard, so tails become common. Hedge requests or use fewer, larger shards.
- C Hash sharding splits HNSW neighborhoods across shards, so the coordinator needs extra cross-shard traversal rounds per query.
- D Hash placement leaves some shards much larger than others, and those oversized shards dominate; rebalance vector counts.
Answer: B. The query waits for the slowest shard, so tails become common. Hedge requests or use fewer, larger shards.
With **fan-out**, the median of the slowest of 32 shards sits near each shard's ~98th percentile, so a rare per-shard tail becomes the typical global latency. **Hedged requests** to replicas, or fewer and larger shards, reduce this amplification at the cost of extra load or bigger per-shard indexes. Option A is a common misconception: shards are independent, so the global top 10 is always contained in the union of the per-shard top 10s.
One system design question a day, with spaced repetition so the ones you miss come back.
Get the appRelated questions
- You are building an IVF index on 20 million vectors. A teammate asks why the build needs a 'training' step before any vectors can be added. What is the reason?
- An HNSW index serves a marketplace where about 30% of listings are updated or removed each week. Each update is applied as a delete plus an insert, and deletes mark tombstones. Over a month, recall@10 drifts from 97% to 89% and p99 latency rises at the same ef_search. What is happening, and what should you do?
- Users delete documents in your primary database, but the deleted documents keep appearing in vector search results for hours. The vector index is rebuilt nightly. What is the best fix?
- Your embedding model outputs unnormalized vectors whose magnitudes vary widely. A teammate wants to switch the index from cosine similarity to dot product because it is cheaper to compute. What is the consequence?
- You are setting an SLO for a new ANN-backed recommendation search over 50 million vectors. A product manager asks for 100% recall@10 with single-digit millisecond latency. What is a realistic response?
- A B2B SaaS app serves 500 customers, and every query searches only one customer's documents. One large customer runs heavy batch queries that slow down search for everyone. Which sharding approach fits best?