Distributed Vector Search

Index sharding is the foundational technique of horizontally partitioning a large vector dataset across multiple nodes in a cluster. Each node hosts a subset of the total vectors, called a shard, along with its own local Approximate Nearest Neighbor (ANN) index (e.g., HNSW, IVF).

• Key Benefit: Enables datasets that far exceed the RAM of any single machine.
• Query Flow: A query is broadcast to all shards. Each shard performs a local search and returns its top-k results to a coordinator.
• Challenge: Requires careful data distribution (e.g., random, by metadata) to avoid hot spots and ensure balanced load.
• Example: A 10-billion vector dataset split into 100 shards, each holding 100 million vectors.

This pattern involves a coordinator node that manages the distributed query workflow. The coordinator receives the user query, broadcasts it to all relevant shards, gathers the partial results, and executes the final top-k aggregation.

• Functions: Query routing, fan-out request management, result merging, and often metadata filtering.
• Aggregation Methods: Typically performs a k-selection algorithm (e.g., a priority queue merge) over the returned candidate lists from each shard.
• Optimization: The coordinator may implement query rewriting or caching to improve efficiency.
• System Example: Elasticsearch with its vector search capabilities uses coordinating nodes in this manner.

A hierarchical pattern that combines a fast, coarse-grained search across shards with a more expensive, precise search on selected data. This optimizes the recall-latency trade-off for massive scales.

• Phase 1 - Coarse Selection: A lightweight algorithm (e.g., using compressed binary embeddings or a small IVF quantizer) quickly identifies the most promising shards or broad clusters.
• Phase 2 - Fine-Grained Search: Only the selected shards or clusters perform a full, accurate ANN search using the complete vector representation.
• Benefit: Dramatically reduces network and compute overhead compared to querying all shards with full precision.
• Analogy: Similar to multi-stage retrieval but applied at the cluster level.

Index replication creates redundant copies (replicas) of each shard on different nodes. This pattern is critical for fault tolerance and scaling query throughput.

• High Availability: If a node fails, its shards are still available on replica nodes.
• Load Balancing: Read queries (searches) can be distributed across all replicas of a shard, multiplying the system's overall Queries Per Second (QPS) capacity.
• Write Complexity: Requires a consensus mechanism (like Raft) to synchronize index updates (e.g., from incremental indexing) across all replicas.
• Trade-off: Increases total storage cost proportional to the replication factor.

This is the most common production architecture, combining sharding for scale and replication for resilience. The cluster's total vector capacity is shard_count * vectors_per_shard, while its read throughput scales with replica_count.

• Architecture: A cluster with 4 primary shards and a replication factor of 2 will have 8 total shard copies (4 primary, 4 replica) distributed across nodes.
• Query Path: The coordinator routes a search to one replica of each primary shard.
• Write Path: Indexing requests are sent to the primary shard, which then replicates the update to its replica shards.
• System Example: Milvus and Qdrant implement this hybrid pattern as their core distributed model.

A federated pattern queries multiple, independent vector search systems simultaneously and unifies the results. This is used to search across disparate data silos or specialized indices without centralizing all data.

• Use Case: Searching a vector database for unstructured text, a knowledge graph for entities, and a traditional RDBMS for structured metadata in a single query.

• Coordinator Role: The federator must understand different query languages, translate the user query, handle heterogeneous result formats, and perform cross-system ranking.

• Challenge: Managing consistency and latency variance across different underlying systems with distinct performance profiles.

A family of algorithms designed to efficiently find vectors in a high-dimensional dataset that are most similar to a query vector. ANN algorithms trade off perfect accuracy for significantly reduced search latency and computational cost, making billion-scale vector search feasible. Key algorithms include HNSW, IVF, and LSH. The core trade-off is managed by parameters that balance recall (accuracy) against query latency.

A graph-based approximate nearest neighbor search algorithm that constructs a multi-layered graph for fast traversal. Long-range connections on upper layers enable rapid zooming into the correct neighborhood, while lower layers provide high recall. It is known for excellent query latency and recall without requiring training. The efSearch parameter controls the size of the dynamic candidate list during search, directly impacting the accuracy-latency trade-off.

An indexing structure that partitions the vector space into clusters (Voronoi cells) using a coarse quantizer like k-means. During search, the system finds the nearest clusters to the query and only searches vectors within those cells, drastically reducing distance computations. The nprobe parameter determines how many clusters to search, offering a direct lever for the recall-latency trade-off. Often combined with Product Quantization (PQ) for memory efficiency.

A lossy compression technique that dramatically reduces the memory footprint of a vector index. It works by:

• Splitting each high-dimensional vector into subvectors.
• Quantizing each subspace independently using a small codebook.
• Representing the original vector as a short sequence of codebook indices (codes). Distance calculations are then performed using pre-computed lookup tables, accelerating search. This enables billion-scale indices to reside in RAM, but adds approximation error.

The fundamental engineering compromise in approximate nearest neighbor search. Higher recall (finding the true nearest neighbors) requires examining more candidate vectors, increasing computational work and query latency. This trade-off is managed by tuning algorithm-specific parameters:

• IVF: Increasing nprobe searches more clusters, improving recall at the cost of latency.
• HNSW: Increasing efSearch expands the candidate queue, with similar effect. System design involves quantifying this curve to meet application-specific Service Level Agreements (SLAs).