Designing Large-Scale Vector Search: From HNSW to Distributed Indexing

Engineering pitfalls: hotspot issues — certain popular data causes some nodes to be overloaded. Solution: use consistent hashing with virtual nodes (each physical node maps to multiple virtual nodes) to balance load. Another pitfall is additional latency in query routing: routing decisions must be completed within milliseconds, typically using in-memory routing tables or approximate hashing.

Consistency Models for Distributed Indexes: Balancing Eventual Consistency and Real-time

In distributed systems, how index updates (insertions, deletions, modifications) propagate to all replicas directly affects the freshness of search results. Typically, an eventual consistency model is adopted: updates are first written to the primary node, then asynchronously synced to replicas. But this may lead to queries seeing stale data, affecting user experience. Trade-offs:

Real systems (e.g., Milvus, Weaviate) commonly adopt eventual consistency plus a version number mechanism: each update is assigned an incrementing version, queries can carry the version number, and if a node's data is too old, retry. Additionally, use read-write separation: primary handles writes, replicas handle reads, and periodically pull incremental updates from primary. For deletions, be careful with tombstones to avoid resurrection.

Engineering solution: Use Apache Kafka or Pulsar as the update log; after writing to primary, publish to the message queue, and all replicas consume and apply changes. Combine with background segment merge to optimize storage. When data scale is huge, you can also use consistent hashing + version vectors to detect conflicts, achieving eventual consistency without monotonic reads.

Near-Real-Time Search: Incremental Index Building and Merge Optimization

To support fast visibility of new data, avoid full index rebuilds. A common approach is incremental segments: divide the index into multiple read-only segments, write new data into a small in-memory index (e.g., a single-layer HNSW graph), and periodically merge with disk segments.

Key point: Bloom Filters are used to quickly determine if a data item is in a segment, avoiding full segment scans. For example, in deletion scenarios, if a committed document is deleted, mark a tombstone in the segment, and queries use the bloom filter to skip segments with no hits.

Merge optimization: Segment merging is I/O intensive; if full merge is used, writes may pause. Use LSM tree style: layer segments, small segments frequently merge into medium ones, medium into large ones, controlling merge granularity. Default configuration: if segment size is below a threshold (e.g., 5GB), do not merge. Also, use faiss's IndexShards or IndexReplicas for parallel merging.

Code example: Use FAISS's IndexShards to implement a simple near-real-time index (add a small index every 1000 items, then merge).

import faiss
import numpy as np

d = 128
shard_size = 1000
n_shards = 10

# Create sharded indexes, each shard is HNSW
shards = [faiss.IndexHNSWFlat(d, 32) for _ in range(n_shards)]
for s in shards:
    s.hnsw.efConstruction = 200
index = faiss.IndexShards(d, True)  # Use 'keep_dirs'?? Here directly use IndexShards for sharding

# Simulate incremental addition and merging
for i in range(10000):
    x = np.random.rand(1, d).astype('float32')
    index.add(x)
    if i % shard_size == shard_size-1:
        # Force merge all shards (in practice use background thread)
        pass

Quantization and Compression: Application of PQ and OPQ in Distributed Vector Search

In distributed systems, vector storage and transmission bandwidth are bottlenecks. Product Quantization (PQ) can compress vectors to 1/16 or even 1/64 of the original size while preserving accuracy. Principle: split the high-dimensional vector into subspaces, each subspace is represented by k cluster centers (codebook), the vector is represented by a set of sub-codes (short ids), and distance is computed by lookup table summation.

Especially OPQ (Optimized Product Quantization) first applies an orthogonal rotation to the vector to balance the variance across subspaces, reducing quantization error. In distributed scenarios, store the codebook and quantized residuals locally; during query, do coarse filtering in the compressed space, then compute exact distances for candidates (re-ranking).

Specific application: In Milvus, you can configure index_type=PQ, with parameters nbits=8 (256 centers per subspace), m=8 or 16. Comparative experiments show that for 1024-dimensional vectors, using PQ (m=16, nbits=8) compresses to 2KB, with only 2-3% recall drop.

Engineering details: Codebook training must be done before index building, typically using a large sample (e.g., 1 million items) to train the codebook, avoiding online updates. Additionally, OPQ's rotation matrix needs to be globally computed and stored, size d*d (e.g., 1024*1024*4 bytes = 4MB), which is acceptable. In distributed settings, each node only stores its local quantized codebook and residual matrix, but the rotation matrix must be consistent, so it's usually globally shared.

The above initially constructs the core indexing mechanism from single-machine to distributed. The following will delve into advanced topics such as distributed query merging strategies, fault recovery, and multi-tenant isolation.

Fusion of Graph Index and Inverted Index: Analysis of Hybrid Retrieval Architecture

• Weighted Reciprocal Rank Fusion (RRF): Take Top-K from both retrieval results, and sum by reciprocal rank: score = Σ 1/(k + rank). Simple and effective, but sensitive to k (usually 60), and does not consider score distribution.
• Cascade re-ranking: First use sparse or dense retrieval to get a candidate set (e.g., 1000 items), then use the other method or a cross-encoder for fine ranking. Controls cost, but may miss long-tail relevant results.
• Learned fusion: Use an LTR model (e.g., LambdaMART) with both scores as features to train a ranking model. Best performance, but requires labeled data.

import requests
import numpy as np

# Simulate sparse and dense scores
sparse_scores = {"doc1": 2.5, "doc2": 1.8, "doc3": 1.2}
dense_scores = {"doc2": 0.9, "doc3": 0.8, "doc1": 0.6}

def rrf_fuse(k=60):
    fused = {}
    for scores in [sparse_scores, dense_scores]:
        for rank, doc in enumerate(sorted(scores, key=scores.get, reverse=True)):
            fused[doc] = fused.get(doc, 0) + 1.0 / (k + rank + 1)
    return sorted(fused.items(), key=lambda x: x[1], reverse=True)

# Call DeepSeek for semantic verification of top results (optional)
def deepseek_rerank(query, docs):
    api_key = "your-deepseek-api-key"
    response = requests.post(
        "https://ap
i.deepseek.com/chat/completions",
        headers={"Authorization": f"Bearer {api_key}"},
        json={
            "model": "deepseek-chat",
            "messages": [
                {"role": "system", "content": "You are a sorting assistant. Please score by relevance and output a JSON array."},
                {"role": "user", "content": f"Query: {query}\nDocuments: {docs}"}
            ]
        }
    )
    # Parse the returned sorting result...
    return response.json()["choices"][0]["message"]["content"]

print(rrf_fuse())MethodAdvantagesDisadvantagesUse CasesRRFNo training required, robustHyperparameter-sensitive, does not utilize scoresCold start, general retrievalCascade re-rankingHigh precision, controllable costCoarse filtering may truncateSufficient recall, high precision requirementLearned fusionHighest upper bound, adaptiveRequires labels, complex tuningHigh traffic, labels easily available
Challenges of Horizontal Scaling: Data Skew and Hotspot Balancing
When the index is distributed across multiple nodes, data is partitioned by ID or vector clustering, which can easily lead to data skew: some shards have data volumes far exceeding the average, causing uneven query latency. Similarly, query hotspots cause a few nodes to handle a large amount of traffic, resulting in resource waste and latency spikes. Solutions fall into two categories: 
Data skew balancing: Use load-based re-sharding (e.g., dynamically adjusting shard boundaries based on data volume or query frequency), and use virtual nodes in consistent hashing to map physical nodes to multiple virtual positions, smoothing data distribution. For example, for HNSW indexes, partitioning by center point clustering is possible, but overlapping regions must be handled to avoid cross-node queries.
Hotspot balancing: Create multiple replicas for hotspot shards and adopt a write-many-read-one strategy, so different queries hit different replicas. Additionally, add a memory cache layer (e.g., LRU) to alleviate high-frequency query pressure. A smarter approach is to predict hotspots based on query logs and migrate replicas in advance.
For example, in a 100-node cluster, if a shard's data volume is 3 times the average, its query latency might spike from 10ms to 100ms, while other nodes are idle. We can design a monitoring controller that periodically collects QPS and CPU per shard, and when the imbalance exceeds a threshold, triggers a rebalancing task to migrate data in a rolling fashion, avoiding downtime. The dynamic balancing shard log can be represented in JSON: 
{
  "rebalance_plan": {
    "trigger": "coefficient_of_variation > 0.3",
    "action": "move_shard",
    "source_node": "node-7",
    "target_node": "node-23",
    "shard_ids": ["shard-12", "shard-15"],
    "throttle_limit_mb_per_sec": 50
  }
}
Fault Recovery and Replica Strategies: Ensuring High Availability of Distributed Indexes
Distributed systems must tolerate node failures. Core mechanisms include: 
Fault detection: Use heartbeats and timeouts (e.g., Raft protocol) to detect node liveness. For memory-resident index structures like HNSW, quick detection of unavailability is needed, typically using streaming heartbeats (every 500ms) combined with TCP probes.
Failover: When the primary node fails, elect a new primary from replicas. Data consistency must be ensured: either synchronous writes to primary and backup (strong consistency) or asynchronous replication with tolerance for brief inconsistency. For index systems, eventual consistency is typically adopted, with switchover time controlled to seconds.
Replica synchronization: The primary sends write-ahead logs (WAL) asynchronously to replicas, which replay them to update local indexes. To avoid split-brain after network partitions, lease or Quorum mechanisms are introduced.
Replica strategies require trade-offs: more replicas increase fault tolerance but raise write amplification and storage costs. A common strategy is 2 replicas + 1 arbitration replica (i.e., 3 replicas), allowing one node to fail. For critical systems, different replica counts can be set per partition. For example, core indexes use 3 replicas, hot data uses 2 replicas. During switchover, clients need to reconnect via service discovery. The following replica management rules can be designed: 
Each shard maintains one leader and two followers.
The leader sends heartbeats every 100ms; followers trigger an election after a 500ms timeout.
During switchover, read-only requests can continue to be served by other replicas, while write requests are temporarily blocked or retried.
Synchronization uses incremental snapshots plus asynchronous logs to ensure eventual consistency.
Performance Evaluation Methodology: Building Benchmarks and Interpreting Metrics
Evaluating a distributed vector retrieval system requires defining clear metrics: 
Recall@K: The proportion of truly relevant results (e.g., true nearest neighbors obtained by brute-force search) among the retrieved K results.
Query throughput (QPS): The number of queries processed per second, measured while ensuring latency constraints.
Latency: P50, P95, P99 percentiles, with special attention to P99, reflecting tail performance.
Index build time and memory usage: Affects operational costs.
Evaluation method: Use standard test sets (e.g., SIFT, GIST) across different dataset sizes (e.g., 1M, 10M, 100M vectors) and dimensions. The process is as follows: 
Warm-up phase: Run 1000 queries to populate caches.
Stress testing: Gradually increase concurrency (e.g., 1, 8, 16, 32, 64) and record latency and QPS.
Compare different parameters (e.g., HNSW's M, efConstruction) and plot Recall-QPS curves to find the Pareto optimum.
Note: In a distributed environment, network bandwidth effects must be considered, and cross-machine latency should be recorded. Evaluation reports should include environment specifications, data distribution, and parameter configurations for reproducibility. For example, on a 10M dataset, HNSW (M=16) achieves Recall@10=0.95 with 5ms latency on a single machine, while with 3 distributed nodes, QPS improves 2.3x but P99 latency increases by 20%.
Engineering Practice: Pitfalls in Migrating from Single-Machine HNSW to Distributed Systems
During migration, engineers often encounter the following pitfalls: 
Parameter drift: HNSW parameters (e.g., M, efC) that are optimal on a single machine may degrade in distributed settings. Network overhead changes latency distribution, requiring re-tuning. For example, increasing efSearch improves recall but increases cross-node communication, requiring trade-offs.
Network overhead: During graph traversal, neighbors may reside on different nodes, causing numerous cross-node requests. Solutions: partition to localize graph edges as much as possible, or use graph pruning to reduce cross-edges.
Serialization cost: Use efficient serialization for vectors and graph nodes (e.g., FlatBuffers, Cap'n Proto) to avoid JSON overhead. In practice, ProtoBuf is 3-5x faster than JSON and 30% smaller.
Solutions: Design intra-shard local graphs, and for cross-shard edges, merge results at the coordinator node. Additionally, introduce a cache layer to cache high-frequency node vectors, reducing serialization calls. Key principle: partition data into multiple "independent subgraphs", each capable of handling sub-queries on a single machine, and finally aggregate rankings. Below is a migration self-check list: 
Re-evaluate data distribution to avoid single-point hotspots.
Stress-test network round-trips and set reasonable timeouts (e.g., 50ms).
Monitor serialization CPU usage; if it exceeds 30%, optimize encoding.
Gradual rollout, comparing Recall and latency before and after migration to ensure no degradation.
Case Study: Architecture Design and Optimization of a Billion-Scale Vector Retrieval System
A real system (e.g., an e-commerce image search) processes 100 million 128-dimensional vectors, designed as follows: 
Index layering: The first layer uses Product Quantization (PQ) to compress vectors to 32 bytes for coarse candidate filtering (Recall 80%), and the second layer uses original vectors for fine re-ranking on the candidate set (Recall improves to 95%).
Cache layer: For popular query vectors, use Redis to cache Top-K results, achieving a 30% hit rate and reducing load on the underlying system.
Query optimization: Use multi-threaded pipelines to overlap vector encoding, network transmission, and distance computation. Use GPUs for batch matrix operations, improving throughput by 5x.
Dynamic indexing: For new data, use incremental HNSW merging and periodic rebuilding.
System architecture: Client -> Gateway (load balancing) -> Routing layer (hash by vector ID) -> Index shards (each shard holds 20 million vectors, HNSW) -> Result fusion layer. Before and after optimization comparison: 
Metric
Before
After
Improvement
P99 latency
120ms
35ms
70%
QPS
800
5200
5.5x
Memory usage
1.2TB
0.9TB (PQ)
25%
Key takeaways: hierarchical retrieval can significantly reduce costs; hotspot caching yields substantial benefits; use asynchronous batching to reduce network round trips.
Future Trends: Potential of Graph Neural Networks and Learned Indexes in Retrieval
Learned indexes (LII) replace B-trees or hash indexes with neural networks, reducing memory and predicting data distribution. For HNSW, GNNs can be used to learn graph structures, optimize neighbor selection, and improve navigation efficiency. For example, using GraphSAGE to train a model that predicts high-quality neighbors for nodes, thereby building graphs with shorter jumps. Potential includes:
Adaptive graph construction: dynamically rewire edges based on query load to improve connectivity in hotspot regions.
Approximate distance estimation: use small networks to replace high-dimensional distance computations, accelerating pruning.
End-to-end retrieval: embed the index into the retrieval model to directly output Top-K, but current interpretability and stability are insufficient.
The challenges lie in training cost and generalization ability, but under specific distributions (e.g., multimodal data), learned indexes can reduce memory by 30% and improve recall by 20%. The DeepSeek API can be used to generate synthetic training data, for example:
import requests

def generate_training_data(query_pool):
    api_key = "your-deepseek-api-key"
    # Use DeepSeek to generate similar query pairs for training GNN edge prediction
    resp = requests.post("https://api.deepseek.com/chat/completions",
        headers={"Authorization": f"Bearer {api_key}"},
        json={"model": "deepseek-chat", "messages": [{"role": "user", "content": "Generate 10 semantically similar but differently phrased queries, in JSON list format"}], "temperature": 0.7})
    return resp.json()
Summary and Best Practices
Architecture design: adopt hybrid retrieval (sparse + dense), fuse with RRF or learned ranking; choose cascade or parallel based on business needs.
Scalability: use virtual nodes to balance data skew, dynamically migrate replicas to alleviate hotspots, and set monitoring thresholds to trigger rebalancing automatically.
High availability: at least 2 replicas, use Raft for leader election; failover in seconds, async log synchronization.
Performance evaluation: fix dataset size, measure Recall, QPS, P99, and plot cost curves; repeat multiple times and take the median.
Migration pitfalls: re-tune parameters, use efficient serialization (e.g., FlatBuffers), design locality-aware sharding, and constantly monitor network overhead.
Architecture optimization: use PQ for coarse filtering + original vectors for fine ranking; set up cache layers; leverage GPU acceleration for distance computations.
Future: pay attention to learned indexes and GNNs, but verify stability and benefits.
Final advice: all optimizations should be based on business metrics; first establish a comprehensive observability system, then iterate gradually. Distributed vector retrieval is essentially a balance between engineering and algorithms; there is no silver bullet, only fine-tuning and architectural evolution.