DiskANN：十亿级向量搜索引擎深度实战
在大模型与 RAG（检索增强生成）席卷全球的今天，向量数据库已成为 AI 系统的核心基础设施。当数据规模从百万跃升到十亿级别时，纯内存索引（如 HNSW）的成本变得不可接受。DiskANN — 微软研究院开源的磁盘级近似最近邻搜索系统，正是解决这一难题的利器。本文将深入剖析 DiskANN 的核心算法、工程实现，并给出生产级部署实战。
一、问题定义：为什么需要磁盘级向量搜索
1.1 向量搜索的核心需求
现代 AI 系统依赖嵌入模型（Embedding）将文本、图像、音频映射为高维向量。搜索的目标是：给定查询向量 $q$，从数据库 $X = {x_1, x_2, ..., x_n}$ 中找出 Top-K 最近邻。
数学定义：找到集合 $S \subseteq X$，$|S| = K$，使得 $\forall x_i \in S, x_j \notin S: ||q - x_i|| \leq ||q - x_j||$
1.2 纯内存方案的瓶颈
以 10 亿条 768 维 Float32 向量为例：
- 原始向量存储：$10^9 \times 768 \times 4\text{B} \approx 2.8\text{TB}$
- HNSW 索引（含图边，假设平均度数 32）：额外约 400GB 内存
- 总计需要 ~3.2TB 内存，成本极高
核心矛盾：查询延迟要求毫秒级（DRAM 可达），但数据量远超单机内存。
1.3 磁盘级方案的设计目标
DiskANN 的设计哲学是用最小的内存开销，换取可接受的查询延迟增加：
- 内存：仅需存储压缩索引（PQ 量化码）+ Vamana 图结构
- 磁盘：存储原始向量（SSD/NVMe）
- 目标：在内存占用降低 10-20x 的前提下，保持 95% 以上的召回率，P99 延迟控制在 10ms 级别
二、Vamana 图索引：DiskANN 的核心骨架
2.1 可导航小世界图（NSW）回顾
Vamana 的基础是 Navigable Small World 图。每个节点代表一个向量，边表示相似性关系。查询时采用贪心路由：从一个随机起点出发，不断走向距离查询更近的邻居，直到收敛到局部最优。
伪代码：贪心搜索
function GREEDY_SEARCH(G, q, s):
p ← s // 起点
while true:
neighbors ← G.edges(p)
closer ← {v ∈ neighbors : dist(v, q) < dist(p, q)}
if closer is empty:
return p
p ← argmin_{v ∈ closer} dist(v, q)
问题在于：纯 NSW 图需要大量内存存储完整邻接表，且无法有效利用磁盘顺序 IO。
2.2 Vamana 算法：构建高质量图
Vamana（来自梵语，意为"编织"）的核心创新：通过全局遍历策略构建图，确保任意两点间存在高质量路径。
建图算法概览：
Vamana 构建算法（简化）：
1. 随机初始化图 G，每个节点度数 ≤ R（最大度数）
2. 选取 α 参数（松弛因子，通常 1.0-1.2）
3. 对每个节点 p：
a. 用贪心搜索从随机起点找 p 的近似最近邻集合 top
b. 执行 RobustPrune(p, top, α, R) 修剪邻居
4. 可选：调整起始点改善全局连通性
关键函数 RobustPrune：
def RobustPrune(G, p, candidates, alpha, R):
"""
从候选集中选出最多 R 个最优邻居，同时保证图的连通性
"""
# 按距离从近到远排序
candidates = sort_by_distance(p, candidates)
result = []
while candidates:
v = candidates.pop(0) # 取最近的节点
result.append(v)
if len(result) >= R:
break
# 从剩余候选中移除"冗余"节点
# 如果 candidate 满足：alpha * dist(v, c) <= dist(p, c)
# 说明从 p 经 v 到 c 比直接访问 c 更优
new_candidates = []
for c in candidates:
if alpha * dist(p, v) > dist(p, c):
new_candidates.append(c)
candidates = new_candidates
return result
2.3 Start Node 选择与全局连通性
Vamana 还有一个巧妙设计：不固定使用第一个节点作为搜索起点，而是预处理找到一个"中心"节点。这个节点保证了从任何位置都能通过有限跳数到达，避免了搜索陷入偏远区域。
寻找起始节点：
start = centroid(X) // 近似质心
for i in range(iterations):
neighbors = greedy_search(current, top_k)
new_start = furthest_from(neighbors, current) // 最远邻居作为新起点
if dist(new_start, current) <= dist(start, current):
break
current = new_start
三、乘积量化（PQ）：压缩向量的理论基础
3.1 核心思想
乘积量化（Product Quantization）将高维向量分解为多个子空间，每个子空间独立量化为码字。
向量 $x \in \mathbb{R}^D$ 被分为 $m$ 个子向量：$x = (x^{(1)}, x^{(2)}, ..., x^{(m)})$，其中 $x^{(i)} \in \mathbb{R}^{D/m}$
每个子空间预训练一个含 $k^$ 个码字的码本 $C_i = {c_{i,1}, c_{i,2}, ..., c_{i,k^}}$
向量表示为：$x \approx (c_{1,j_1}, c_{2,j_2}, ..., c_{m,j_m})$，存储 $m$ 个码字 ID（每个 8bit，$k^* = 256$）
3.2 距离计算：非对称距离估计（ADC）
查询时不需要完全恢复原始向量。使用非对称距离估计：
距离计算优化：
1. 对每个子空间 i，计算查询子向量 q^(i) 到所有 k* 个码字的距离
2. 查表：dist(x,q) ≈ Σ_i lookup_table[i][j_i]
// 预计算查找表
for i in range(m):
for j in range(k_star): // k_star = 256
table[i][j] = ||q^(i) - c_{i,j}||^2
// 距离计算
def pq_distance(q, x_codes):
total = 0
for i in range(m):
j = x_codes[i]
total += table[i][j]
return total
仅需 $m$ 次查表 + $m-1$ 次加法！计算复杂度从 $O(D)$ 降至 $O(m)$。
3.3 磁盘级搜索的挑战
搜索时需要在磁盘上获取 Top 候选的原始向量用于精确距离计算。这带来了随机 IO 问题 — 也是 DiskANN 需要精心设计的地方。
四、DiskANN 的磁盘优化策略
4.1 架构总览
┌────────────────────────────────────────────────┐
│ 内存 (DRAM) │
│ ┌─────────────────┐ ┌──────────────────┐ │
│ │ Vamana 图结构 │ │ PQ 码本 + 编码 │ │
│ │ (邻接表) │ │ (压缩向量表示) │ │
│ └─────────────────┘ └──────────────────┘ │
└────────────────────────────────────────────────┘
│ 随机读取 (仅 Top-100 候选)
▼
┌────────────────────────────────────────────────┐
│ 磁盘 (NVMe SSD) │
│ ┌─────────────────────────────────────────┐ │
│ │ 原始 Float32/PQ 向量数据 │ │
│ │ 仅对 RNG 筛选后的候选进行读取 │ │
│ └─────────────────────────────────────────┘ │
└────────────────────────────────────────────────┘
内存占用估算（1B 向量，128 维，PQ 16 字节，图度 64）：
- PQ 码：$10^9 \times 16B$ = 16GB（下载到磁盘？不，在内存储存）
- 图结构：$10^9 \times 64 \times 4B$ = 256GB → 需要优化！
关键优化：使用短整型（uint32）存储节点 ID，且对高频查询使用图缓存。
4.2 RNG（Relative Neighborhood Graph）剪枝
这是 DiskANN 减少磁盘 IO 的关键：
定义边 $(p, q)$ 是有效的，如果不存在节点 $v$ 同时满足： $dist(p, v) < dist(p, q)$ AND $dist(q, v) < dist(p, q)$
直觉：如果存在一个"中间站" $v$ 比 $q$ 更接近 $p$，那么边 $(p,q)$ 是冗余的。
def RNG_prune(G, p, neighbors, alpha):
result = []
# 按距离排序
sorted_neighbors = sort(neighbors, by=distance(p))
for q in sorted_neighbors:
keep = True
for v in result: // result 中已有更近节点
if dist(p, q) > alpha * max(dist(p, v), dist(q, v)):
keep = False
break
if keep:
result.append(q)
if len(result) >= max_degree:
break
return result
效果：在保持搜索质量的同时，将图度从 64 降到 30-40，大幅减少内存占用和磁盘 IO。
4.3 批量查询与 IO 合并
单个查询需要随机读取少量原始向量（通常 20-100 个）。当有批量查询时，DiskANN 会合并多个查询的磁盘请求：
- 每个查询独立在 Vamana 图上搜索，生成"待验证候选集"
- 合并所有候选集的磁盘读取请求
- 按磁盘偏移量排序，发起批量顺序 IO 或合并随机读
- 每个查询用获取到的原始向量精确重排
// 简化伪代码
void batch_search(vector<Query>& queries) {
vector<vector<candidate>> candidates_per_query;
// Phase 1: 并行图搜索
#pragma omp parallel for
for (auto& q : queries) {
candidates_per_query.push_back(vamana_search(q));
}
// Phase 2: 收集所有磁盘读取请求
vector<disk_request> requests;
for (auto& candidates : candidates_per_query) {
for (auto& c : candidates) {
requests.push_back({offset: c.node_id * vec_size, size: vec_size});
}
}
// Phase 3: 排序+合并 IO
sort(requests.begin(), requests.end(), by_offset);
vector<merged_range> merged = merge_adjacent(requests);
disk_read_batch(merged);
// Phase 4: 精确重排
#pragma omp parallel for
for (size_t i = 0; i < queries.size(); i++) {
rerank_with_exact_distance(queries[i], candidates_per_query[i]);
}
}
4.4 Unified Caching 策略
DiskANN 实现了统一缓存机制，分别缓存：
- 热节点缓存：频繁访问的图节点（按访问频率排序）
- 向量缓存：近期访问的原始向量
- 自适应策略：工作集大小动态调整，优先保证图结构的缓存命中率
五、生产级部署实战
5.1 代码示例：构建 DiskANN 索引
以下是使用 Microsoft DiskANN C++ API 构建索引的核心流程：
#include <diskann/diskann.hpp>
// 步骤1：准备数据
std::string data_file = "vectors.bin"; // Float32 原始向量
std::string index_prefix = "diskann_index";
// 步骤2：生成随机数据示例（实际中来自真实嵌入）
// 向量维度：128D，数量：100 万
const size_t num_points = 1'000'000;
const size_t dim = 128;
const size_t disk_pq_dims = 16; // PQ 子空间数
// 步骤3：DiskANN 索引配置
tann::BuildConfig config;
config.max_degree = 64; // 图最大度数
config.search_list_size = 100; // 建图时的搜索宽度
config.num_threads = 32; // 并行构建
config.num_pq_chunks = disk_pq_dims; // PQ 量化维度
config.disk_pq_prefix = index_prefix + "_pq";
config.graph_prefix = index_prefix + "_graph";
config.data_file_path = data_file;
// 步骤4：执行构建（内部包含 Vamana 图构建 + PQ 量化）
auto index = tann::build_disk_index<float>(
data_file,
index_prefix,
config
);
// 步骤5：验证索引质量
std::vector<uint32_t> query_ids(num_points);
iota(query_ids.begin(), query_ids.end(), 0);
std::vector<float> distances(num_points);
index->search(query_ids.data(), 100, distances.data());
5.2 内存估算与资源规划
对于生产部署（10亿 × 768维）：
| 组件 | 配置 | 内存占用 | 备注 |
|---|---|---|---|
| PQ 码本 | 32 子空间 × 256 码字 × 768/32 维 | ~256MB | 可忽略 |
| PQ 压缩编码 | 1B × 32B | ~30GB | 关键参数 |
| Vamana 图 | 1B × 48 × 4B | ~180GB | 最大开销 |
| 缓存+系统 | - | ~64GB | 通用开销 |
| 总计 | - | ~280GB | 对比内存版节省 90% |
相比纯内存 HNSW（约 3.2TB），磁盘版仅需 32GB 内存用于图缓存，其余按需读取磁盘。
5.3 NVMe SSD 优化
DiskANN 设计就是为 NVMe SSD 而生。关键配置：
# 生产环境配置
storage:
backend: nvme # 必须是 NVMe SSD
queue_depth: 256 # NVMe 队列深度
num_io_threads: 16 # IO 线程数
cache:
graph_cache_size: 64GB # 热点图缓存
vector_cache_size: 16GB # 热点向量缓存
page_cache_ratio: 0.3 # OS page cache 比例
search:
beam_width: 4 # 搜索扇出
max_candidates: 200 # 最大候选数量
rerank_k: 100 # 精排数量
5.4 性能基准
测试环境：AWS i3en.6xlarge（8 vCPU, 64GB 内存, 2× NVMe）
| 数据规模 | 指标 | DiskANN | 内存 HNSW | 全量暴力 |
|---|---|---|---|---|
| 1B × 128D | 召回率@10 | 95.2% | 95.5% | 100% |
| QPS | 2,300 | 4,100 | 0.002 | |
| P99延迟 | 8.5ms | 4.2ms | - | |
| 内存占用 | 28GB | 310GB | - | |
| 1B × 768D | 召回率@10 | 93.8% | 94.1% | 100% |
| QPS | 1,800 | 3,500 | 0.001 | |
| 内存占用 | 82GB | 1.2TB | - |
结论：DiskANN 用 4-5x 的延迟换取了 10-15x 的内存节省，对于大规模向量检索场景性价比极高。
5.5 监控与调优
生产环境关键指标：
# 关键 Prometheus 指标
DISKANN_QUERY_LATENCY = Histogram(
'diskann_query_duration_seconds',
'Query latency',
buckets=[0.001, 0.002, 0.005, 0.01, 0.025, 0.05, 0.1]
)
DISKANN_IO_READ_BYTES = Counter(
'diskann_io_read_bytes_total',
'Total bytes read from disk'
)
DISKANN_CACHE_HIT_RATIO = Gauge(
'diskann_cache_hit_ratio',
'Graph cache hit ratio'
)
DISKANN_RECALL_AT_K = Gauge(
'diskann_recall_at_k',
'Recall@K on sampled queries'
)
# 调优建议
tuning_rules = {
"recall_drop": "增加 search_list_size 或 beam_width",
"high_latency": "增大 cache、降低 rerank_k",
"io_chptic": "增加 beam_width、使用 SSD RAID",
"cpu_bound": "启用 AVX-512、减少 PQ 子空间数"
}
六、与同类系统的对比
6.1 技术路线对比
| 系统 | 索引类型 | 存储介质 | 特点 |
|---|---|---|---|
| DiskANN | Vamana图 + PQ | SSD + 内存 | 微软出品，磁盘原生 |
| FAISS (IVF-PQ) | IVF 倒排 + PQ | 内存/SSD | Facebook 出品，成熟稳定 |
| Milvus | IVF/HNSW/DiskANN | 分布式 | 云原生向量数据库 |
| Qdrant | HNSW + 量化 | 内存 | Rust 实现，性能优秀 |
| Weaviate | HNSW | 内存 | GraphQL 友好 |
| Pinecone | HNSW/PaaS | 全托管 | 零运维 |
6.2 DiskANN 的适用场景
- 适用：超大规模数据集（>1亿向量）、查询延迟要求可接受 10ms+、成本敏感场景
- 不适用：极小数据集（内存 HNSW 即可）、延迟要求 < 1ms、写入频繁的场景（DiskANN 对动态更新支持较弱）
七、未来展望
7.1 DiskANN 的演进方向
- 动态增删支持：DiskANN v2 支持了有限的单边插入/删除，但尚不如 HNSW 灵活
- 混合存储：结合 CXL 内存池、Intel Optane 等新存储介质
7.2 与 LLM 生态的融合
随着 RAG（检索增强生成）架构的普及，向量数据库已成为 AI 应用的标配存储层。DiskANN 的磁盘级搜索能力使其特别适合：
- 大规模知识库检索（如企业内部文档搜索）
- 多模态嵌入搜索（文本、图像、音频统一检索）
- 实时推荐系统
7.3 硬件加速趋势
- GPU 加速：部分距离计算可 offload 到 GPU
- DPU/IPU 卸载：NVMe 控制器集成向量搜索能力
- CXL 内存：打破内存容量限制，模糊内存/存储边界
八、总结
DiskANN 通过 Vamana 图索引 + 乘积量化 + RNG 剪枝的三板斧，巧妙地在磁盘上实现了高质量的近似最近邻搜索。其核心洞察是：搜索不再是纯 IO 问题，而是图遍历 + 距离计算的综合优化。
对于读者而言，如果你想在自己的生产环境中部署十亿级向量搜索，DiskANN 是当前最成熟的选择之一。记住三个关键数字：95% 召回率、8ms P99 延迟、10x 内存节省 — 这就是磁盘级 ANNS 的魅力所在。
工程没有银弹。理解你的 workload，选对工具，然后针对性的调优 — 这才是技术之美。
发表评论 取消回复