Sharding a vector index that does not fit on one node, how is it typically done, and what's the query time cost?

When an ANN index outgrows a single machine's RAM (typically past tens of millions of vectors at modern embedding dimensions), the standard fix is sharding: split the corpus across multiple nodes, each holding its own independent index. **The sharding scheme.** Almost universally random or hash based by vector ID. Compute `hash(vector_id) mod N_shards`, that shard owns the vector. Random assignment gives even load and avoids hot spots. **Each shard is its own ANN index.** HNSW or IVF-PQ, built only over the vectors assigned to that shard. The shards do not know about each other. **Query path.** A query comes in to a coordinator. The coordinator broadcasts the query to all shards. Each shard runs its local ANN search and returns its top-K. The coordinator merges the per shard results (a small heap merge over `N_shards * K` candidates) and returns the global top-K. **Replicas.** Each shard is typically replicated 2 or 3 times for availability and to handle higher read traffic. The coordinator picks any replica per shard per query. **The throughput-vs-latency tradeoff.** Sharding multiplies QPS because shards run in parallel. But it does not reduce per query latency, and the p99 latency actually gets worse: every query waits for the slowest shard, and across many shards the chance that at least one is slow grows. This is the 'fan out tail latency' problem and it is the price you pay for horizontal scale.

**Sharding scheme.** Random or hash based by vector ID is the default in Pinecone, Milvus, Weaviate, and Vespa. Each shard holds an independent ANN index (HNSW or IVF-PQ) over its slice of the corpus, with replicas per shard for availability and read scaling. Alternative schemes (cluster based sharding by vector content, tenant based sharding by namespace) exist but introduce skew risk and operational complexity; random sharding is the safe default. **Query path: scatter gather.** A coordinator node receives the query, broadcasts it to all shards in parallel, waits for each shard's local top-K, and merges into the global top-K. The merge is cheap: a heap over `N_shards * K` candidates, O(N_shards * K * log K) which is microseconds. **The consequences for QPS.** QPS scales horizontally. Adding shards adds parallel compute capacity. Adding replicas adds parallel read capacity. A well-sharded system can serve linear in shards QPS. **The consequences for latency.** Per-query latency does NOT decrease with sharding. The total wall clock is `max(shard_latency_i) + merge`, which is dominated by the slowest shard. Worse, the p99 of the maximum across N_shards is higher than the p99 of any individual shard. If a single shard's p99 is 10ms, the system's p99 across 10 shards is roughly 30 to 50ms because there are 10 independent dice rolls for the slow case. **This is the 'fan out tail latency problem'.** Jeff Dean wrote the canonical 2013 paper on it (`The Tail at Scale`). The fix is not to add more shards; it is to make the tail of each shard tighter. **Mitigations in 2026 production vector DBs:** - *Hedged requests.* Send the query to two replicas of each shard; take whichever responds first. Costs roughly 2x replica resources, eliminates most tail latency outliers from JVM GC, queue depth, or cache misses. - *Shard-affine routing.* For multi tenant deployments, route a tenant's queries only to the shards that hold their data.