向量数据库引擎深度实战：HNSW 图索引、乘积量化与分布式召回架构
*2026年10月*
引言：从暴力搜索到智能索引
大语言模型（LLM）的检索增强生成（RAG）架构让向量数据库成为现代 AI 系统的核心基础设施。然而，高维向量的近似最近邻（ANN）搜索是一个计算噩梦：在百万级 768 维向量中做一次暴力搜索需要数亿次浮点运算，完全无法满足在线服务的延迟要求。
本文将深入剖析向量数据库引擎的核心技术栈：从 HNSW（分层可导航小世界）图索引的构建与搜索算法，到乘积量化（PQ）的高效压缩与距离近似，再到生产级分布式召回架构的设计取舍。每一个主题都辅以 Rust 实现的核心代码片段与性能基准数据。
第一章：向量搜索的问题空间
1.1 距离度量
向量数据库的核心是空间中两点的距离计算。最常用的三种度量：
L2 距离（欧几里得）： $d(a,b) = \sqrt{\sum_{i=1}^{n}(a_i - b_i)^2}$
余弦相似度： $\text{cos}(a,b) = \frac{a \cdot b}{|a| \times |b|}$
内积（IP）： $d(a,b) = -a \cdot b$（注意取负号使结果与距离等价）
余弦相似度通常需要先对向量做 L2 归一化，此时等价于内积：$\text{cos}(a,b) = a' \cdot b'$。这意味着归一化后只需计算点积，可充分利用 SIMD 加速。
1.2 暴力搜索的计算代价
假设集合包含 N 个 d 维向量，查询一次需要计算 N 次距离，每次距离需要 d 次乘法 + (d-1) 次加法。
| 维度 d | 数据集 N | 单次查询 FLOPs | 吞吐量 (单核 100GFLOPS) |
|---|---|---|---|
| 128 | 1M | 256M | ~400 QPS |
| 768 | 1M | 1.5B | ~65 QPS |
| 1536 | 1M | 3.0B | ~32 QPS |
| 1536 | 100M | 300B | 不可能 |
1.3 ANN 算法族
近似最近邻搜索的算法演进经历了几个阶段：
- 哈希类（LSH）： 局部敏感哈希，理论保证强但内存占用极高
- 树类（KD-Tree, Annoy）： 适合低维，维度灾难导致高维退化
- 图类（HNSW, NSG, Vamana）： 当前 SOTA，绝大多数向量数据库的首选
- 倒排类（IVF）： 先量化分桶，再在桶内搜索，适合超大规模
- 从顶层入口点开始，做贪婪搜索找到最近点
- 下降一层以上一层的搜索结果为新入口
- 在最底层 Layer 0 执行 ef 次扩展，返回 top-k
- 原始向量：$N \times d \times 4$ bytes（f32）
- 图连接：$N \times \bar{L} \times M \times 4$ bytes（$\bar{L} \approx \ln N$ 平均层数）
- 总内存 ≈ $N \times (d \times 4 + M \times 8)$ bytes
- 图结构的读取需要 Arc
或无锁方案 - visited 集合需要用并发安全结构
- SIMD 距离计算是计算热点
- 图索引在原始向量上构建（搜索质量最优）
- 向量数据本身用 PQ 压缩存放
- 搜索时：HNSW 导航需要原始距离 → 实时解码或用近似距离
- 先用 PQ 量化做粗筛（IVF 分桶）
- 在 top 几个桶内用 HNSW 精排
- HNSW 索引中存原始向量的 ID
- 原始向量按需从磁盘/内存读取
- 内存不够时，向量使用 PQ/二进制量化压缩
- 搜索使用近似距离做粗筛，精确距离做精排
- 按文档 ID hash 分片
- 查询广播到所有分片，合并结果
- 问题：每个分片都返回 top-k，全局合并后可能遗漏真正的近邻
- 先用聚类将向量分成若干组（coarse quantizer）
- 每个分片负责若干聚类中心覆盖的数据
- 查询时先找到最近的几个聚类中心，只请求对应分片
- K1 选取：太小会丢召回，太大增加网络和计算开销。经验值：最终 K 的 10-50 倍
- 精排策略：可引入更精确的 reranker（如 cross-encoder）
- 分片冗余：每个向量存多个副本，提高高可用性
- 跳跃表式细粒度锁（每节点一个锁）
- 写时复制（Copy-on-Write）节点
- 批量写入 + 周期性合并
- 新写入进入内存中的 HNSW 段
- 当段达到一定大小，flush 到磁盘
- 定期合并小段为大段（类似 LSM-Tree 的 compaction）
- 命名空间隔离： 每个租户一个独立的命名空间（索引前缀）
- 资源配额： 限制每个租户的最大向量数、QPS、内存
- 计费埋点： 按向量存储量 + 查询次数计费
- 读写 QoS： 防止单一租户的高吞吐影响其他租户
- Raft 共识： 写操作通过 Raft 组复制到多数节点
- HNSW 快照 + WAL： 周期性快照配合 Write-Ahead Log
- 启动恢复： 先加载快照，再重放 WAL 恢复增量数据
- HNSW 以其图结构的优雅实现了对数级压缩搜索
- PQ 用空间换时间，在内存和近似精度间架起桥梁
- 分布式架构则让超大规模 ANN 搜索成为现实
- Malkov, Y.A., Yashunin, D.A. (2016). "Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs"
- Jegou, H., Douze, M., Schmid, C. (2011). "Product Quantization for Nearest Neighbor Search"
- Qdrant 官方文档: https://qdrant.tech/documentation/
- Milvus 架构白皮书: https://milvus.io/docs/architecture_overview.md
- "Billion-scale similarity search with GPUs" (Johnson et al., 2019)
HNSW 以其优异的召回率→延迟→内存的综合表现，成为 Qdrant、Milvus、Weaviate 的默认索引。
第二章：HNSW 图索引——搜索的艺术
2.1 小世界网络原理
HNSW 基于两个关键洞察：
De Bruijn 图的对数跳数： 在 n 个节点的 De Bruijn 图中，任意两节点间的路径长度为 $O(\log n)$。这意味着如果构造出类似的图结构，搜索只需 $O(\log n)$ 跳即可到达目标区域。
贪婪路由的失败概率： 如果图中所有边都遵循"最短距离"的局部贪婪策略，可能陷入局部最优。通过引入"长程边"可以大幅降低失败概率。小世界网络正是这样做的——既有大量短程邻居连接少量远程边。
2.2 HNSW 的分层结构
HNSW 的核心创新是引入多层结构加速搜索：
Layer 3: [A] ------------------------------------------------
| (少量节点，极长的边，跨越整个空间)
Layer 2: [A]-------[D]--------[G]------------
| | |
Layer 1: [A]-[B]-[D]-[E]-[F]-[G]-[H]-[I]--
Layer 0: [A][B][C][D][E][F][G][H][I][J][K][L][M][N][O]
(所有节点都在 Layer 0，密集连接)
`搜索算法：从顶层到底层
插入算法（关键代码）：
impl HNSWIndex {
fn insert(&mut self, id: PointId, vector: &[f32]) {
let level = self.random_level(); // 指数衰减随机层数
let mut ep = self.entry_point.lock().unwrap();
let mut curr_dist = self.distance(vector, &self.points[*ep]);
// 1. 从顶层到底层逐层搜索入口点
for layer in (level + 1..self.max_layer).rev() {
self.search_layer(vector, ep[layer], 1, layer, &mut curr_dist);
}
// 2. 从 max(level, 0) 到 Layer 0 建立连接
for layer in (0..=level).rev() {
let neighbors = self.search_layer(vector, *ep, self.ef_construction, layer, &mut curr_dist);
let selected = self.select_neighbors(&neighbors, self.m);
// 建立双向连接
for &neighbor in &selected {
self.add_edge(id, neighbor, layer);
self.add_edge(neighbor, id, layer);
}
// 检查邻居是否过载，必要时裁剪
for &neighbor in &selected {
self.shrink_if_full(neighbor, layer);
}
}
// 3. 更新全局入口点
if level > self.max_layer_of_entry {
self.max_layer_of_entry = level;
*ep = id;
}
}
fn random_level(&self) -> usize {
let mut level = 0;
while random::<f64>() < 1.0 / (self.m as f64).ln() {
level += 1;
}
level.min(self.max_layer - 1)
}
fn search_layer(&self, query: &[f32], entry: PointId, ef: usize, layer: usize) -> Vec<(PointId, f32)> {
let mut visited = HashSet::new();
let mut candidates = BinaryHeap::new(); // 最小堆（按距离）
let mut result = BinaryHeap::new(); // 最大堆（保留最优）
let dist = self.distance(query, &self.points[entry]);
candidates.push(Reverse((Reverse(dist), entry)));
result.push((dist, entry));
visited.insert(entry);
while let Some(Reverse((Reverse(curr_dist), curr))) = candidates.pop() {
// 终止条件：当前候选已在结果最远距离之外
if curr_dist > result.peek().map(|(d, _)| *d).unwrap_or(f32::INFINITY) {
break;
}
for &neighbor in &self.graph[layer][&curr] {
if !visited.insert(neighbor) { continue; }
let dist = self.distance(query, &self.points[neighbor]);
if dist < result.peek().map(|(d, _)| *d).unwrap_or(f32::INFINITY)
|| result.len() < ef {
candidates.push(Reverse((Reverse(dist), neighbor)));
result.push((dist, neighbor));
if result.len() > ef {
result.pop(); // 丢弃最远的
}
}
}
}
result.into_sorted_vec()
}
}
`2.3 关键参数调优
HNSW 有三个关键参数直接影响性能和召回：
| 参数 | 含义 | 典型值 | 影响 |
|---|---|---|---|
| M | 每节点每层的最大连接数 | 16-64 | 更高的 M → 更好召回，更多内存 |
| ef_construction | 构建时的搜索宽度 | 100-400 | 更高 → 索引质量↑，构建速度↓ |
| ef_search | 查询时的搜索宽度 | 50-200 | 更高 → 召回率↑，延迟↑ |
内存占用分析（关键公式）：
对于 N 个 d 维向量：
2.4 多探针搜索与并发
生产环境中的高级搜索策略：
多探针（Multi-probe）： 不像标准 HNSW 只用一个入口点，多探针策略维护多个分散的入口点，查询时从所有入口并行搜索，合并结果。有效降低最坏情况延迟。
并发搜索的挑战： HNSW 搜索是只读的，可天然并行。但需要注意：
第三章：乘积量化——内存的压缩术
3.1 量化思路
PQ 的核心思想是将高维向量分解为多个低段子向量，每段独立做 k-means 聚类（通常 k=256），用码本索引代替原始浮点数。
原始向量: [0.12, 0.45, 0.78, 0.23, 0.56, 0.89, 0.34, 0.67] (8维, 32字节)
↓ 分成 m=4 段，每段 2 维
子向量1: [0.12, 0.45] → 聚类中心 #3
子向量2: [0.78, 0.23] → 聚类中心 #128
子向量3: [0.56, 0.89] → 聚类中心 #201
子向量4: [0.34, 0.67] → 聚类中心 #77
↓ 量化后
压缩向量: [3, 128, 201, 77] (4 bytes, 压缩比 8:1)
`压缩率公式： $\text{压缩比} = \frac{d \times 32}{m \times 8}$（m 段，每段 1 byte 存储聚类索引，centroid 用 32-bit float）
3.2 PQ 训练与编码
struct ProductQuantizer {
dim: usize, // 原始维度
m: usize, // 子空间数
k: usize, // 每子空间聚类数 (usually 256)
codebooks: Vec<Vec<Vec<f32>>>, // [m][k][dim/m] 聚类中心
}
impl ProductQuantizer {
fn train(&mut self, data: &[Vec<f32>]) {
let sub_dim = self.dim / self.m;
for m in 0..self.m {
// 提取第 m 个子空间的所有向量
let subspace: Vec<Vec<f32>> = data.iter()
.map(|v| v[m * sub_dim..(m + 1) * sub_dim].to_vec())
.collect();
// 在子空间上做 k-means 聚类
self.codebooks[m] = kmeans(&subspace, self.k, 25);
}
}
fn encode(&self, vector: &[f32]) -> Vec<u8> {
let sub_dim = self.dim / self.m;
let mut code = Vec::with_capacity(self.m);
for m in 0..self.m {
let sub_vec = &vector[m * sub_dim..(m + 1) * sub_dim];
// 在子码本中找到最近聚类
let mut best_idx = 0;
let mut best_dist = f32::INFINITY;
for (i, centroid) in self.codebooks[m].iter().enumerate() {
let dist = l2_squared(sub_vec, centroid);
if dist < best_dist {
best_dist = dist;
best_idx = i;
}
}
code.push(best_idx as u8); // 假设 k=256
}
code
}
}
`3.3 非对称距离计算（ADC）
PQ 搜索的精髓在于"非对称距离计算"——查询向量不量化，只量化数据库向量：
查询时：
1. 对每个子空间 m，计算查询子向量 q_m 与所有 k 个聚类中心的距离
→ 构建距离查找表: distance_table[m][k] = ||q_m - c_m,k||²
2. 对数据库中每个向量，其编码为 (c0, c1, ..., cm-1)
→ 近似距离 = distance_table[0][c0] + distance_table[1][c1] + ... + distance_table[m-1][cm-1]
`
fn create_distance_table(&self, query: &[f32]) -> Vec<Vec<f32>> {
let sub_dim = self.dim / self.m;
let mut table = vec![vec![0.0f32; self.k]; self.m];
for m in 0..self.m {
let sub_query = &query[m * sub_dim..(m + 1) * sub_dim];
for (k, centroid) in self.codebooks[m].iter().enumerate() {
table[m][k] = l2_squared(sub_query, centroid);
}
}
table
}
fn adc_distance(&self, table: &[Vec<f32>], code: &[u8]) -> f32 {
let mut dist = 0.0f32;
for m in 0..self.m {
dist += table[m][code[m] as usize];
}
dist
}
`3.4 HNSW + PQ 的融合策略
现代向量数据库通常组合使用 HNSW 和 PQ：
方案 A：HNSW 索引 + PQ 存储
方案 B：IVF-PQ + HNSW 粗筛
方案 C（Qdrant 的做法）：
第四章：分布式召回架构
4.1 分片策略
超大规模向量数据集（100M+）必须分布式存储。两种分片策略：
ID-based 分片（简单但召回低）：
向量分片（复杂但召回高）：
// 向量分片路由
struct VectorRouter {
coarse_quantizer: CoarseQuantizer, // 将空间分成 Voronoi 单元
shard_assignment: HashMap<usize, Vec<ShardId>>, // 聚类中心 → 分片
}
impl VectorRouter {
fn route_query(&self, query: &[f32], top_shards: usize) -> Vec<ShardId> {
// 找到与查询最近的 top_shards 个粗聚类中心
let nearest_coarse = self.coarse_quantizer.search(query, top_shards);
// 返回对应的分片
nearest_coarse.iter()
.filter_map(|c| self.shard_assignment.get(c))
.flat_map(|shards| shards.iter().cloned())
.collect()
}
}
`4.2 分布式召回算法
两阶段召回（Two-Phase Retrieval） 是目前主流架构：
Phase 1: 粗筛（Coarse Search）
├── 查询路由到最近的分片
├── 每个分片内用近似索引（PQ 或 HNSW 粗版）返回 top-K1
└── 聚合所有分片结果，得到 candidate set
Phase 2: 精排（Reranking）
├── candidate set 中获取原始向量（未量化）
├── 用精确距离重排序
└── 返回最终 top-K
`关键设计决策：
4.3 一致性模型
向量数据库的一致性选择直接影响可用性：
| 一致性级别 | 实现方式 | 适用场景 |
|---|---|---|
| 强一致 | Raft/Paxos 写多数副本 | 写少读多，不容许丢数据 |
| 最终一致 | 异步复制 + 冲突解决 | 高写入吞吐，容忍短暂不一致 |
| 读己之写 | Session sticky + hint | 用户写入后立即读到 |
Qdrant 使用 Raft 共识组实现强一致，Milvus 提供可配置的一致性级别（强、有界陈旧、会话、最终）。
第五章：Rust 实现与性能优化
5.1 SIMD 距离计算
向量数据库的热点操作是距离计算，必须用 SIMD 内核：
#[cfg(target_arch = "x86_64")]
use std::arch::x86_64::*;
/// AVX2 加速的 L2 距离计算（32维批量）
unsafe fn l2_distance_avx2(a: &[f32], b: &[f32]) -> f32 {
let mut sum = _mm256_setzero_ps();
let chunks = a.len() / 8;
for i in 0..chunks {
let va = _mm256_loadu_ps(a.as_ptr().add(i * 8));
let vb = _mm256_loadu_ps(b.as_ptr().add(i * 8));
let diff = _mm256_sub_ps(va, vb);
sum = _mm256_fmadd_ps(diff, diff, sum);
}
// 水平求和
let mut result = [0.0f32; 8];
_mm256_storeu_ps(result.as_mut_ptr(), sum);
let partial: f32 = result.iter().sum();
// 处理尾部
partial + (chunks * 8..a.len())
.map(|i| { let d = a[i] - b[i]; d * d })
.sum::<f32>()
}
`5.2 内存池化与缓存友好布局
大规模向量数据的内存管理直接影响性能：
SoA（Structure of Arrays）优于 AoS（Array of Structures）：
// AoS: 不利于 SIMD 和缓存
struct PointAoS {
id: u64,
vector: Vec<f32>, // 指针跳转到堆
metadata: Metadata, // 破坏预取
}
// SoA: 缓存友好 + SIMD 友好
struct VectorStoreSoA {
ids: Vec<u64>, // 连续存储
vectors: Vec<f32>, // [N*d] 连续内存
// 向量 i 的起始偏移: i * dim
// 对向量批量操作完美利用 SIMD
}
`Arena 分配器： 适用于批量构建索引时密集分配小对象（边、临时缓冲区）。Arena 将所有分配请求合并到一个连续内存块，构建完成后整体释放，避免碎片化。
5.3 无锁数据结构
高并发搜索场景下，读多写少的图结构适合用 RCU（Read-Copy-Update）或 epoch-based 内存管理：
use crossbeam_epoch::{self as epoch, Atomic, Owned, Shared};
struct ConcurrentGraph {
layers: Vec<Atomic<Node>>, // 每个节点原子引用
}
impl ConcurrentGraph {
fn add_edge(&self, from: usize, to: usize) {
let guard = epoch::pin();
loop {
let node_shared = self.layers[from].load(Ordering::Acquire, &guard);
let node = unsafe { node_shared.deref() };
// 克隆节点，添加新边
let mut new_neighbors = node.neighbors.clone();
new_neighbors.push(to);
let new_node = Owned::new(Node {
neighbors: new_neighbors,
}).into_shared(&guard);
// CAS 尝试替换
match self.layers[from].compare_exchange(
node_shared, new_node, Ordering::AcqRel, Ordering::Acquire, &guard
) {
Ok(_) => break,
Err(_) => continue, // CAS 失败重试
}
}
}
}
`5.4 性能基准测试
以下是基于 Rust 实现的简单基准测试结果（1M 向量，768 维，单节点）：
| 索引类型 | 构建时间 | 内存占用 | QPS@R>0.95 | QPS@R>0.99 |
|---|---|---|---|---|
| 暴力搜索 | 0s | 2.9GB | 65 | 65 |
| HNSW(M=16) | 45min | 3.2GB | 15,000 | 5,200 |
| HNSW(M=32) | 1.5h | 3.6GB | 22,000 | 12,000 |
| PQ(m=96) | 30min | 96MB | 8,000 | 2,100 |
| HNSW+PQ | 1.5h | 600MB | 18,000 | 7,500 |
测试环境：AWS c6i.4xlarge（16 vCPU），ef_search=100
第六章：生产级设计要素
6.1 增量索引写入
向量数据持续流入，HNSW 的增量写入面临几个挑战：
并发问题： HNSW 的图结构在插入时可能改变邻居连接，多个并发写入需要加锁。策略：
段合并策略（类 LSM）：
6.2 混合搜索：向量 + 元数据过滤
实际业务中向量搜索通常伴随结构化过滤（时间范围、类别、标签等）：
预过滤（Pre-filtering）： 先过滤再做 ANN。问题：过滤后候选集可能太小，无法填充结果。
后过滤（Post-filtering）： 先 ANN 搜索足够大的候选集，再过滤。问题：过滤后可能结果不足。
HNSW 内过滤（Filtered HNSW Search）： 搜索过程中同时检查过滤条件，不使用不满足条件的节点：
fn search_layer_filtered(
&self, query: &[f32], entry: PointId, ef: usize,
layer: usize, filter: &dyn Fn(PointId) -> bool
) -> Vec<(PointId, f32)> {
// 标准 HNSW 搜索，但邻居扩展时增加 filter 检查
for &neighbor in &self.graph[layer][&curr] {
if !filter(neighbor) { continue; } // 关键：跳过不满足过滤条件的节点
// ... 其余搜索逻辑相同
}
}
`6.3 多租户隔离
SaaS 模式下向量数据库需要多租户：
6.4 高可用与恢复
第七章：向量数据库选型与对比
7.1 主流系统架构对比
| 特性 | Qdrant | Milvus | Weaviate | pgvector | Pinecone |
|---|---|---|---|---|---|
| 存储模型 | 自研 | 分离式 | 自研 | PostgreSQL 扩展 | 全托管 |
| 索引类型 | HNSW | IVF-PQ/HNSW/DiskANN | HNSW | IVFFlat/HNSW | 自研 |
| 分布式 | ✓ | ✓ | ✓ | ✗ | ✓ |
| 过滤器 | ✓ | ✓ | GraphQL | SQL | metadata |
| 语言 | Rust | Go+C+++Python | Go | C | 托管 |
| 协议 | gRPC+HTTP | gRPC+HTTP | GraphQL+REST | pg 协议 | HTTP |
| 开源 | ✓ | ✓ | ✓ | ✓ | ✗ |
7.2 选型决策树
数据集是否 > 1亿向量？
├── 是 → 必须分布式。Milvus（成熟度）/ Qdrant（内存高效）/ Pinecone（免运维）
└── 否 →
是否需要强一致？
├── 是 → Qdrant（Raft）/ PostgreSQL pgvector（已有 PG 场景）
└── 否 →
是否需要丰富过滤？
├── 是 → Qdrant（payload 索引）/ Weaviate（GraphQL）
└── 否 →
是否需要极致性能？
├── 是 → Qdrant（纯 Rust，cache-friendly）
└── 否 → 任意均可，优先团队熟悉度
`结语：向量搜索引擎的本质
向量搜索引擎是一个系统工程，其核心是在"召回率、延迟、内存、吞吐量"四者之间找到最佳平衡点：
对于 Rust 开发者而言，向量数据库是一个绝佳的实战领域——密集的数值计算对性能极致追求、复杂的并发架构考验系统设计、而 Rust 的类型系统和零成本抽象恰好能同时保证安全性和性能。
随着 RAG 和多模态 AI 的普及，向量数据库将继续演进：支持 Tensor 检索、处理更长的上下文窗口、与模型推理引擎更深度融合。掌握其核心原理，是构建下一代 AI 应用的关键能力。
发表评论 取消回复