Sharding and Distributed Vector Search
The two ways to partition a vector collection across machines, why one preserves recall and the other preserves latency, and the fan-out arithmetic that decides tail latency.
A collection exceeding one machine's memory must be split, and the two ways to split it have opposite properties. Choosing between them is choosing which of recall and latency to protect.
Random sharding
Assign vectors to shards at random. Every shard holds a representative sample of the space, so a query must go to every shard, each returns its local top \(k\), and a coordinator merges.
Correctness is straightforward: the global top \(k\) is contained in the union of local top \(k\) results, so recall is preserved exactly relative to the single-machine approximate search. Load is balanced by construction, and adding a shard is a rebalance rather than a redesign.
The cost is fan-out. Every query touches every shard, so the query's latency is the maximum over shards, not the average. With 20 shards and a p99 shard latency of 50ms, the query's p99 approaches that 50ms even though the median shard responded in 10ms, because one slow shard delays everything. Tail latency amplification is the defining property of this design, and it worsens as shard count grows.
Semantic sharding
Cluster the vectors and assign each cluster to a shard, so a query goes only to the shards whose regions are near it. Fan-out falls dramatically, often to one or two shards, and with it the tail amplification.
The cost is recall. A query near a cluster boundary has genuine neighbours in a shard it did not query, and those are lost. Probing more shards recovers them and reduces the advantage. Load is also unbalanced, since semantic clusters have very different popularity, and the shard holding a popular region receives disproportionate traffic.
Semantic sharding is a good fit where the query distribution is known to concentrate, or where a natural partition exists that is also a filter, tenant, language, region, in which case it delivers both reduced fan-out and filter pushdown.
Replication
Replicas serve read throughput and availability, and they must be consistent enough that a query hitting different replicas gives comparable results. Approximate indexes built independently on the same data can differ, so replicas built by copying a built index rather than by independent construction avoid a subtle source of inconsistent results.
When it breaks
Coordinator merge requires over-retrieval. Each shard must return more than \(k\) for the merge to be correct under filtering or scoring adjustments, which multiplies the data transferred and the work done.
Slow shards dominate. Hedged requests, sending to a replica after a delay and taking the first response, address the tail at the cost of extra load, and they are close to necessary at high fan-out.
Rebalancing moves vectors and rebuilds indexes. Adding capacity is not a metadata change: the moved vectors must be indexed at the destination, so scaling is a background operation measured in hours.
Cross-shard filtering interacts badly. A filter matching mostly one shard's data wastes the fan-out to the others, and a cost-based planner needs per-shard selectivity statistics to avoid it, which most systems do not maintain.
12 flashcards for this concept
Click a card to reveal the answer.