DiskANN 磁盘向量检索深度解析：如何在有限内存下实现十亿级向量毫秒级搜索

为什么需要磁盘向量检索

在向量搜索领域，内存容量始终是制约系统规模的瓶颈。以常见的 768 维 float32 向量为例，十亿条向量的原始数据量约为

。即便采用 PQ 量化将维度压缩至 64 字节，存储十亿条向量仍需约 60 GB 内存。对于大多数企业而言，为向量检索单独部署如此庞大的内存集群并不经济。

传统的内存向量索引方案（如 HNSW、IVF-PQ）在设计时假设所有索引数据都驻留在内存中，以此换取微秒级的查询延迟。然而当数据规模突破亿级，内存成本呈线性增长，而查询延迟却因为缓存未命中等因素开始退化。这一矛盾催生了磁盘向量检索技术的兴起。

微软研究院在 2019 年提出的 DiskANN（Disk-based Approximate Nearest Neighbor）算法，首次证明了在仅使用 64 GB 内存的前提下，对十亿级向量数据实现 5 毫秒以内的查询延迟是可行的。其核心思想是：将向量全量存储在 SSD 上，内存中仅保留压缩后的向量摘要与图结构的入口节点，通过精巧的磁盘访问策略最小化 I/O 次数。

DiskANN 核心架构解析

Vamana 图索引构建

DiskANN 的图索引基于 Vamana 算法，这是 Navarro 提出的 HNSW 的变体，但引入了一个关键改进——全局入口点搜索与两阶段构建策略。Vamana 图的构建过程如下：

第一阶段：随机初始化与粗排

• 为每个向量随机选择出度邻居，构建初始图
• 以贪心搜索方式从任意起点出发，找到距离查询最近的节点
• 记录搜索路径上经过的所有节点作为候选邻居

第二阶段：剪枝与入口点优化

• 对每个节点的候选邻居按距离排序，执行贪心剪枝：保留距离最近的邻居，同时确保被剪掉的邻居至少被保留邻居中的一个覆盖
• 参数 alpha 控制剪枝的激进程度，默认 alpha=1.2
• 选择图的全局入口点（距离所有节点平均最近的节点）

与 HNSW 的多层结构不同，Vamana 是一张扁平图，但通过精心控制出度上限（通常为 60-120），在保持搜索效率的同时大幅降低内存占用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Vamana 图构建伪代码

def build_vamana_index(data, max_degree=64, alpha=1.2, num_iters=2):

    n = len(data)

    # 初始化随机图

    graph = random_init_graph(n, max_degree)

    # 找到全局入口点（距离质心最近的点）

    centroid = np.mean(data, axis=0)

    entry_point = argmin([distance(data[i], centroid) for i in range(n)])

    

    for iteration in range(num_iters):

        for i in range(n):

            # 从入口点贪心搜索到 i 的路径

            path = greedy_search(graph, entry_point, data[i], data)

            # 收集路径上所有节点的邻居作为候选

            candidates = set()

            for node in path:

                candidates.update(graph[node])

            candidates.add(i)

            # 按距离排序后贪心剪枝

            sorted_cands = sorted(candidates, key=lambda j: distance(data[i], data[j]))

            pruned = robust_prune(data[i], sorted_cands, max_degree, alpha)

            graph[i] = pruned

    

    return graph, entry_point

PQ 压缩与磁盘布局

DiskANN 采用乘积量化（Product Quantization, PQ）将高维向量压缩为短编码，存储在内存中用于快速距离预筛。PQ 压缩过程将 D 维向量切分为 M 个子空间，每个子空间聚类为 256 个码字，因此每个向量仅需 M 字节即可表示。

磁盘上的布局策略是 DiskANN 性能的关键。每个向量在 SSD 上按如下结构顺序存储：

这种将向量数据与图结构交错存储的设计，使得一次磁盘读取可以同时获取向量的完整数据与邻居信息，最大化利用 SSD 的顺序读性能。

查询流程深度剖析

DiskANN 的查询流程分为三个阶段：PQ 预筛、磁盘验证与结果合并。其精妙之处在于通过 PQ 压缩向量在内存中快速缩小候选集，再对少量候选发起精确的磁盘读取。

阶段一：PQ 近似搜索

查询向量首先被分解为 M 个子向量，在每个子空间中查找最近的码字，构建 PQ 近似距离查找表。随后从入口点出发，在 Vamana 图上进行贪心搜索，但距离计算使用 PQ 近似而非原始向量。由于 PQ 编码全量驻留在内存中，这一阶段的延迟完全取决于 CPU 计算速度。

阶段二：磁盘精确验证

PQ 搜索返回 Top-L 个候选（L 通常为查询 Top-K 的 2-4 倍），这些候选的完整向量需要从磁盘读取以进行精确距离计算。DiskANN 采用批量 I/O 策略，将所有待读取的扇区按逻辑地址排序后一次性提交，利用 SSD 的内部并行性最大化吞吐。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# DiskANN 查询流程伪代码

def diskann_search(query, graph, entry_point, pq_tables, 

                   top_k=10, beam_width=2, l_search=200):

    # 阶段1: PQ近似搜索

    pq_dist_table = compute_pq_distance_table(query, pq_tables)

    candidates = pq_greedy_search(

        graph, entry_point, pq_dist_table, l_search

    )

    

    # 阶段2: 批量磁盘读取 + 精确距离计算

    hit_list = []

    for node_id in candidates[:l_search]:

        full_vector = disk_read(node_id)  # 从SSD读取原始向量

        exact_dist = exact_distance(query, full_vector)

        neighbors = disk_read_neighbors(node_id)

        hit_list.append((node_id, exact_dist, neighbors))

    

    # 阶段3: 在精确结果上做最终排序

    hit_list.sort(key=lambda x: x[1])

    return hit_list[:top_k]

Beam Search 与 I/O 优化

为减少磁盘 I/O 次数，DiskANN 引入了 Beam Search 策略。传统的贪心搜索每次只扩展一个最近节点，需要频繁的磁盘访问。Beam Search 同时扩展 beam_width 个候选节点，将多次随机读合并为一次批量读。当 beam_width=2 时，查询延迟约为 5ms；beam_width=4 时可降至约 3ms，但 I/O 量翻倍。

值得注意的是，DiskANN 对 SSD 的随机读性能有较强依赖。在 NVMe SSD 上，4KB 随机读延迟约为 20-50 微秒，而 SATA SSD 约为 100-200 微秒。因此 DiskANN 推荐使用 NVMe SSD 部署，且最好为索引文件预留独立的 NVMe 设备以避免与系统 I/O 竞争。

与 HNSW 及 IVF 方案的性能对比

为了直观展示 DiskANN 的优势，下表对比了三种主流方案在十亿级数据规模下的关键指标：

从表中可以看出，DiskANN 在内存占用方面具有压倒性优势，仅为 HNSW 的 1/8 左右。虽然查询延迟比纯内存方案高一个数量级，但对于大多数在线搜索场景（用户可接受的响应时间通常在 100ms 以内），5ms 的延迟完全满足需求。关键在于，DiskANN 使得在单台服务器上部署十亿级向量检索成为可能，而非必须依赖昂贵的内存集群。

生产部署实战

环境准备与编译

DiskANN 的官方实现以 C++ 开源在 GitHub 上（microsoft/DiskANN），同时也提供了 Python 绑定。以下是在 Ubuntu 22.04 上的部署步骤：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 安装依赖

sudo apt update && sudo apt install -y \

    build-essential cmake libaio-dev libopenmp-dev \

    libboost-program-options-dev



# 编译 DiskANN

git clone https://github.com/microsoft/DiskANN.git

cd DiskANN

mkdir build && cd build

cmake -DCMAKE_BUILD_TYPE=Release ..

make -j$(nproc)



# 编译完成后，主要工具位于 build/ 目录下

# - build_disk_index: 构建磁盘索引

# - search_disk_index: 执行查询

# - build_memory_index: 构建内存索引（用于对比）

索引构建与参数调优

构建 DiskANN 索引时需要关注以下核心参数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 构建 DiskANN 索引

./build/build_disk_index \

    --data_type float32 \

    --data_path /data/vectors.bin \

    --index_path_prefix /data/diskann_index \

    --R 64 \                    # 图的最大出度

    --L 200 \                   # 构建时的搜索列表大小

    --B 64 \                    # PQ 编码字节数

    --M 32 \                    # 构建时使用的内存缓冲区 (GB)

    --T 48                        # 构建线程数



# 参数说明：

# R: 出度上限，增大可提升召回率但增加索引体积

# L: 构建时的搜索深度，增大可提升图质量但增加构建时间

# B: PQ 压缩字节数，增大可提升 PQ 搜索精度但增加内存占用

# M: 内存缓冲区大小，至少为数据量的 1/4

查询服务部署

查询阶段需要配置的关键参数包括搜索列表长度和 Beam Width：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 启动查询服务

./build/search_disk_index \

    --index_path_prefix /data/diskann_index \

    --query_file /data/queries.bin \

    --K 10 \                    # 返回 Top-K 结果

    --L 400 \                   # 搜索列表大小（应为 K 的 20-40 倍）

    --beam_width 2 \            # Beam Search 宽度

    --search_io_limit 200 \     # 最大磁盘 I/O 次数

    --num_nodes_to_cache 100000   # 缓存热门节点数量



# 调优建议：

# - L 越大召回率越高，但延迟增加

# - beam_width=2 适合延迟敏感场景，beam_width=4 适合召回率敏感场景

# - num_nodes_to_cache 应根据可用内存调整，缓存 10 万节点约需 2GB

内存配置策略

对于不同规模的数据集，推荐以下内存配置方案：

增量更新与 Fresh-DiskANN

DiskANN 原始版本不支持增量更新，这是其在生产环境中的主要局限。微软在 2021 年提出了 Fresh-DiskANN 方案来解决这一问题。Fresh-DiskANN 的核心思想是维护两个索引：

• 静态索引（主索引）：基于 Vamana 构建的磁盘索引，存储大部分历史数据
• 动态索引（增量索引）：基于 HNSW 构建的内存索引，存储最近写入的数据

查询时同时搜索两个索引并合并结果。当增量索引增长到一定阈值时，将其与主索引合并，重新构建磁盘索引。这一过程类似于 LSM-Tree 的 compaction 机制。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# Fresh-DiskANN 合并策略伪代码

def merge_indices(static_index, dynamic_index, merge_threshold=1_000_000):

    if dynamic_index.size() < merge_threshold:

        return  # 未达阈值，无需合并

    

    # 从磁盘读取静态索引中的所有向量

    all_vectors = []

    for node_id in static_index.all_nodes():

        all_vectors.append(disk_read_full_vector(node_id))

    

    # 添加增量索引中的新向量

    for node_id in dynamic_index.all_nodes():

        all_vectors.append(dynamic_index.get_vector(node_id))

    

    # 重新构建 Vamana 图

    new_static = build_vamana_index(all_vectors)

    

    # 原子替换：新索引写入临时路径后 rename

    atomic_replace(static_index.path, new_static.path)

    

    # 清空增量索引

    dynamic_index.clear()

Fresh-DiskANN 的合并操作较为耗时（十亿级数据约需数小时），因此通常在低峰期执行。在合并期间，查询仍可正常进行——旧索引继续提供服务，合并完成后再原子切换。

监控与运维实践

在生产环境中运行 DiskANN，以下监控指标至关重要：

• 磁盘 I/O 延迟：NVMe SSD 的 4KB 随机读 P99 延迟应低于 100 微秒。如果延迟飙升，可能是 SSD 磨损或 I/O 竞争
• 缓存命中率：内存缓存中热门节点的命中率应保持在 80% 以上。低于此值需增加缓存节点数
• PQ 搜索候选集大小：如果 PQ 搜索返回的候选数远小于 L 参数，说明 PQ 量化质量不足，需增大 B 参数
• 查询延迟分布：关注 P99 延迟与平均延迟的比值。如果比值超过 5:1，通常是由于长尾查询的磁盘访问路径过深

对于 SSD 寿命管理，建议启用 NVMe SMART 监控，跟踪写入量（Written LBAs）与剩余寿命百分比。DiskANN 的索引构建是写密集操作，一次十亿级索引构建可能产生 5-10 TB 的写入量。建议将索引构建与查询服务部署在不同的 NVMe 设备上。

适用场景与替代方案选择

DiskANN 并非万能方案。在选择向量检索架构时，需要根据具体场景权衡：

适合 DiskANN 的场景：

• 数据规模超过 5 亿条，且内存预算有限
• 查询延迟要求在 10ms 以内（非微秒级）
• 数据更新频率较低（每天增量不超过百万级）
• 部署环境配备 NVMe SSD

不适合 DiskANN 的场景：

• 数据规模在亿级以下——HNSW 的内存需求完全可接受，且延迟更低
• 实时性要求极高（如在线广告竞价，延迟要求小于 1ms）
• 高频增量写入——Fresh-DiskANN 的合并开销可能无法接受
• 只能使用 SATA SSD 或 HDD——I/O 延迟会成为瓶颈

在替代方案方面，如果 DiskANN 不满足需求，可以考虑以下选项：

• Streaming-DiskANN：微软提出的流式更新方案，在原始 DiskANN 基础上支持更平滑的增量更新
• SPANN (Microsoft)：基于倒排文件的磁盘方案，构建速度更快但召回率略低
• Vamana + HNSW 混合：温冷数据用 DiskANN，热数据用 HNSW，通过路由层分流查询
• Qdrant / Milvus 磁盘模式：这些数据库已集成 DiskANN 的核心思想，提供更完善的运维工具链

最终的技术选型应基于实际数据集进行基准测试。DiskANN 的官方仓库提供了完整的基准测试工具链，可以在真实数据上评估不同参数组合下的延迟-召回率曲线，为决策提供数据支撑。