DiskANN 精读：为什么它能把十亿级 ANN 放到单机 SSD 上，还保持高召回与低延迟

一句话总结

DiskANN 的核心贡献不是“又造了一种新的 ANN 索引”这么简单，而是把图索引的高召回能力和SSD 的大容量真正拼在了一起：

用一个更适合磁盘访问的图（Vamana）做导航，把压缩向量放在内存里做粗距离判断，把全精度向量和邻接表一起放在 SSD 上做低成本精排，从而在单机、有限内存条件下支撑十亿级 ANN。

如果只记住一句最通俗的话，那就是：

DiskANN 想解决的问题是：内存放不下全部向量，但我又不想放弃 HNSW 这种图索引带来的高 recall。

论文信息

标题：DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node
会议：NeurIPS 2019
作者：Suhas Jayaram Subramanya, Devvrit, Rohan Kadekodi, Ravishankar Krishnaswamy, Harsha Vardhan Simhadri
论文 PDF：https://proceedings.neurips.cc/paper_files/paper/2019/file/09853c7fb1d3f8ee67a61b6bf4a7f8e6-Paper.pdf
微软研究页：https://www.microsoft.com/en-us/research/publication/diskann-fast-accurate-billion-point-nearest-neighbor-search-on-a-single-node/
代码仓库：https://github.com/microsoft/DiskANN

这篇论文到底在解决什么问题

假设你现在有：

十亿个向量
每个向量一百多维
希望 query 延迟是几毫秒
recall 还得很高
机器又不是巨型内存服务器，只是一台比较像样的工作站

那么你马上会撞到一个现实问题：

问题 1：纯内存图索引太贵

HNSW / NSG 这类图方法在高 recall 下很强，但：

图本身要占内存
原始向量也要占内存
数据一到十亿规模，内存成本立刻爆炸

问题 2：纯压缩索引 recall 不够高

像 IVF-PQ / OADC 这类方法非常节省内存，但如果只靠压缩码来算距离：

距离估计会有误差
recall 很难打到特别高
特别是在 Top-1 / Top-10 这种要求高质量的时候

问题 3：SSD 很大，但随机读有延迟

SSD 容量便宜得多，但 ANN 检索不是只看容量：

如果查询过程要做太多轮随机读
latency 会变高
吞吐也会掉

所以 DiskANN 想解决的根本矛盾是：

如何在“内存不够放全量高质量图索引”的现实约束下，仍然保住高 recall 和低延迟？

先给数学小白的核心直觉

我先不用论文语言，直接讲直觉。

你可以把它想象成“地图 + 导航 + 仓库取货”

假设有一座非常大的城市：

城里每栋楼就是一个向量点
你要快速找到“最像 query 的那几栋楼”

如果所有道路信息和所有楼的详细资料都放在你的脑子里（内存里），那很好办；但现实是：

你的脑子不够大
只能记一部分“摘要信息”
详细资料得去仓库（SSD）临时拿

DiskANN 的策略就是：

第一步：脑子里只放“便宜的粗信息”

每个点的压缩向量（PQ code）放内存
这样你可以很快大致判断“哪些点看起来值得追”

第二步：仓库里放“完整资料 + 路网”

SSD 上存每个点的完整向量
还存它的邻居列表

第三步：走图，但每一步都尽量少读盘

不要一次只读一个点再等 SSD 回来
而是一次并行读一小批候选点（beam search）

第四步：把经常访问的关键点缓存起来

特别是从入口开始前几跳很常访问的点
放到内存里，减少磁盘 IO

所以你可以先把 DiskANN 理解成：

一个“图索引 + PQ 粗判 + SSD 全精度精排 + 缓存 + 并行 IO”的组合系统。

注意：这比 HNSW 更“系统设计”，而不只是单个算法。

第一部分：DiskANN 论文里真正新的东西是什么？

很多人第一次看 DiskANN，会误以为“它只是把 HNSW 放磁盘”。其实不对。

DiskANN 真正的新东西有两层：

1. 一个新的图构建算法：Vamana

论文不只是讲 SSD，还先提出了一个图：

Vamana

它是 DiskANN 的核心图结构。

2. 一个完整的 SSD-resident ANN 系统设计

DiskANN 的系统层设计包括：

图放 SSD
压缩向量放 DRAM
beam search 做并行读
缓存热点节点
用“顺便拿到”的全精度向量做隐式 rerank

所以要真正懂 DiskANN，必须分开理解：

A. Vamana：图怎么建

B. DiskANN：图怎么放 SSD 上并高效搜

第二部分：先讲 Vamana —— DiskANN 的底层图到底是什么

为什么作者不直接拿 HNSW？

论文的一个核心观察是：

SSD 场景下，真正关键的不只是 recall，还要尽量减少搜索路径上的跳数（hops）。

原因很简单：

每跳都可能触发一次或一批磁盘随机读
跳数多，延迟就高

作者发现：

HNSW 很强
NSG 也很强
但它们生成的图，不一定最适合 SSD
特别是在“跳数”和“图直径”上还有优化空间

于是他们提出了 Vamana。

Vamana 的目标是什么

Vamana 想要一张图，同时满足：

搜索仍然容易收敛到近邻
图直径更小
有更多长程边，减少 hop 数
图又不能太稠，否则存储和访问成本太高

一句话：

Vamana 想找的是“度数受控，但直径更小”的图。

GreedySearch 是什么

Vamana 和很多图 ANN 一样，搜索核心仍然是一个 best-first / greedy 风格遍历。

论文里的 GreedySearch(s, x_q, k, L) 可以理解成：

从起点 s 开始
维护一个候选列表 L
每次扩展当前最像 query 的点
不断把更好的点加入候选
最后返回最接近 query 的 k 个点

它和 HNSW 底层那个候选扩展搜索是同一家族思路。

Relative Neighborhood / Sparse Neighborhood Graph 这部分到底在说什么

论文在这里想表达的是：

如果图的边选得“足够好”，那么 query 在图上就很容易一路朝正确方向前进。

所谓好边，并不只是“最近邻边”，而是：

既能保局部邻近关系
又不要太冗余
还要尽量有利于导航

这和 HNSW 的 neighbor heuristic 有点亲缘关系，但 DiskANN 在这里走了自己的图构建路线。

第三部分：RobustPrune —— Vamana 里最关键的图稀疏化步骤

论文给了一个关键子过程：

RobustPrune(p, V, α, R)

别被名字吓到，直觉上它做的是：

从一大堆候选邻居里，挑出一组“既有代表性、又不冗余、还能控制度数”的邻居。

参数是什么意思

`R`

每个点最多保留多少条出边
相当于度数上限

`α`

这是 Vamana 最关键的参数之一
它决定：你希望图上每一步“向目标靠近”的幅度有多激进

这和 HNSW / NSG 很不一样。论文明确说：

HNSW 和 NSG 本质上相当于隐式用 α = 1
Vamana 引入了可调的 α > 1

为什么 `α > 1` 很重要

先直观理解。

如果只要求：

下一步比现在稍微近一点就行

那搜索路径可能会：

一点一点挪
hop 数偏多
对 SSD 场景不友好

如果要求更强：

下一步得“显著更近”

那你就更希望图上保留一些更有跨越能力的边。

这正是 Vamana 想要的：

不是只保证能走近，而是希望每步都更“有进展”。

RobustPrune 的通俗理解

假设点 p 有一堆候选邻居 V。它不会简单选最近的 R 个，而是：

先从最靠近 p 的候选开始
选进来一个之后
把那些“被这个已选邻居遮住”的点删掉
继续选下一批

这很像：

招队友时，不想要一群功能重复的人
而想要一组互补的人

这样得到的边：

更分散
更有导航价值
也更有机会形成长程捷径

第四部分：Vamana 是怎么建图的

第一步：不是空图，而是随机 R-regular 图初始化

这点和 HNSW 很不一样。

HNSW 往往从空图开始逐点插入。 Vamana 先做：

一个随机的、每点大约有 R 条出边的初始图

作者说他们观察到：

从随机图开始，比从空图开始，最后图质量更好

直觉上可以理解为：

一开始就有全局连通骨架
后续迭代更容易从局部修到全局

第二步：选一个 medoid 作为起点

Vamana 选整个数据集的 medoid 作为搜索入口。

medoid 是什么

可以简单理解成：

一个“最中心”的代表点
比均值向量更像真实数据点版本的中心

它的作用是：

给 GreedySearch 一个稳定起点
比随机起点更可控

第三步：随机顺序遍历每个点

对每个点 p：

从 medoid 出发搜索 p
得到搜索过程中访问过的一批点
用这些访问过的点作为候选邻居集合
用 RobustPrune 给 p 选邻居
再补反向边
若别的点度数超上限，再对它们也 prune 一次

第四步：做两遍

论文里一个很有意思的设计是：

Vamana 不是一遍过
而是做两遍

第一遍：`α = 1`

更像保守地先修出一张可用图

第二遍：`α = 用户指定值（比如 > 1）`

进一步引入更有跳跃性的长边

作者观察到：

两遍比一遍图更好
如果第一遍就用较大的 α，构建会更慢

这一套的本质

Vamana 不是直接构造“理想图”，而是：

通过“搜索自己 + 用访问路径反哺图结构”不断把图修好。

这和 HNSW 通过插入阶段搜索得到局部邻居，再连边的思想有相通之处。

第五部分：Vamana 和 HNSW / NSG 的真正差别

这是论文里特别值得看的一节。

相同点

三者都属于图 ANN：

逐点构图
搜索过程给构图提供候选
再做邻居筛选

关键不同点 1：`α`

HNSW / NSG 基本没有显式可调的 α
Vamana 明确用 α > 1

这直接影响：

图的直径
hop 数
长边保留能力

关键不同点 2：候选集合不同

论文指出：

HNSW 更偏向从搜索结果集里拿候选
Vamana / NSG 更倾向用整个访问过的顶点集合

直觉上：

用整个访问路径，会更容易捕捉长程边
不会只盯着局部近邻

关键不同点 3：初始化不同

HNSW：空图 + 分层插入
NSG：需要一个近似 kNN 图起步，构建成本更重
Vamana：随机图起步，更轻一些

关键不同点 4：Vamana 的目标更偏 SSD 友好

HNSW 的目标重点是：

高 recall、高性能内存图索引

Vamana 的目标更偏：

少 hop
更适合磁盘访问

所以不能把 Vamana 简单看成“换个名字的 HNSW”。

第六部分：现在才轮到真正的 DiskANN 系统设计

到这里，我们已经有了图：

Vamana graph

接下来 DiskANN 要回答两个现实问题：

问题 A：十亿点图怎么建？

问题 B：十亿点向量放不进内存，查询时怎么比距离？

这两个问题，才是 DiskANN 最真正的系统核心。

第七部分：问题 A —— 十亿点图怎么建？

直接全量内存建图的问题

如果要在十亿点上直接全量构图：

内存会极高
单机根本扛不住

论文的解决办法：重叠分片 + 合并图

这是 DiskANN 非常漂亮的一步。

第一步：先做 k-means 分片

把数据切成 k 个簇。比如论文里举例：

k = 40

第二步：每个点不只去一个簇，而是去多个最近簇

例如：

每个点分配到最近的 ℓ = 2 个中心

这就形成了：

重叠分片（overlapping clusters）

为什么要重叠？

如果每个点只属于一个 shard，那么 query 可能要：

去很多 shard 查
否则容易错过边界附近近邻

而重叠分片让系统有机会做到：

各 shard 内部图先各自建好
再把图边合并
最终形成一张更完整的全局图

作者的核心直觉是：

与其在查询时把请求路由到很多 shard，不如在构建时让点进入多个相邻 shard，从而把跨 shard 的联通性提前做进图里。

这是很系统味的想法。

第三步：每个 shard 分别建较小的 Vamana 图

因为每个 shard 规模缩小了：

能在内存里建图

第四步：把这些图的边集做并集

把多个局部图 merge 成一个整体图。

结果是什么

你不再需要：

一个能装下一次性全图构建的超大内存节点

而是能在：

64GB 级别内存机器上
慢一些但可行地建出十亿级索引

这一步的重要性

这意味着 DiskANN 不只是“查得快”，还真正解决了：

怎么在现实机器上把这么大的索引建出来。

第八部分：问题 B —— 向量放不进内存，查询时怎么比距离？

这是 DiskANN 最精彩的系统设计部分之一。

最朴素的想法

查询时如果要比较点和 query 的距离，最准确的办法是：

读这个点的全精度向量
算真实距离

但如果每访问一个候选点都去 SSD 读一次原始向量：

会慢得离谱

DiskANN 的答案：内存里放压缩向量

论文采用：

Product Quantization (PQ)

做法

所有数据点都压成短码
这些 PQ code 放在 DRAM 里
查询时先用 PQ 近似距离来做候选判断

所以：

大部分“应该继续扩哪个点”的决策
不需要读 SSD
先用内存里的压缩向量做粗判断

这一步特别关键，因为它把“候选选择”从磁盘 IO 变成了：

内存查表 + 近似距离计算

但这还不够：PQ 有误差

压缩向量是有损的。这意味着：

用 PQ 算出来最近的点
不一定真的是最接近的点

如果只靠 PQ：

recall 会掉

所以 DiskANN 还需要全精度修正。

第九部分：DiskANN 在 SSD 上到底存什么

论文设计是：

内存里存

所有点的 PQ 压缩向量
一部分热点缓存点
运行时搜索状态

SSD 上存

对于每个点 i：

它的全精度向量
它的邻居列表

而且它们是放在一起的。

为什么要放一起

因为这样一来：

你读一个点的邻居时
顺便就把这个点的原始向量也拿到了

这对后面的“隐式 rerank”极其重要。

为什么还要做定长布局 / 对齐布局

论文还提到：

节点度数上限固定是 R
如果某点邻居数不足，也要 padding

这样每个节点对应的磁盘块布局就是规则的。

好处是：

计算偏移量简单
不需要再额外存 offset 表
更适合 SSD 读

这是一种非常工程化的存储布局优化。

第十部分：为什么普通图搜索不适合 SSD，DiskANN 为什么引入 Beam Search

先看朴素图搜索

如果你完全照着普通图 ANN 搜索：

扩一个点
去 SSD 读它的邻居
等回来
再扩下一个点
再等

那会发生什么？

SSD 能力根本吃不满
单次 IO 等待成为瓶颈
latency 非常不好

SSD 的现实特性

SSD 虽然随机读很强，但：

真正高吞吐需要并发请求
只发单个请求，浪费设备能力
但并发又不能太大，否则 queue 太满，latency 反而恶化

所以需要一个平衡点。

DiskANN 的做法：Beam Search

论文把自己的搜索叫：

BeamSearch

它和普通 greedy search 的区别

不是每次只扩一个点，而是：

一次扩展一个“前沿”中的一小批点
并行发起多次 SSD 读

beam width 记为：

`W` 的含义

W = 1：接近普通 greedy
W > 1：每轮并行读多个候选点

为什么这很关键

因为 DiskANN 的目标不是单纯减少“总访问点数”，而是还要：

让访问方式更符合 SSD 的吞吐-延迟平衡点。

论文说他们发现：

W = 2, 4, 8 这种较小 beam width 往往比较合理
太小吃不满 SSD
太大又浪费带宽/算力，还拉高延迟

这说明 DiskANN 的搜索已经不是“纯算法遍历”，而是：

算法 + 存储设备行为建模

第十一部分：缓存为什么这么重要

DiskANN 还有一招很重要：

缓存经常访问的点

直觉

从入口点开始，很多 query 的早期搜索路径会重合。特别是：

离入口几跳内的那些点
经常反复访问

如果每次都读盘，非常浪费。

论文做法

可以缓存：

已知高频热点点
或者简单缓存从起点开始若干 hop 内的节点

为什么不无限缓存？

因为图是指数扩张的。距离入口 C 跳内的点数可能增长得很快。所以：

C = 3 或 4 这种小深度就差不多了
再往外，内存会涨得很厉害

这招的本质

用少量 DRAM 把大量 query 的共同前缀路径截断掉。

这和很多系统里的热点缓存思想非常一致。

第十二部分：DiskANN 最巧的一招之一 —— 隐式 rerank

我觉得这是整篇论文里最漂亮、最“工程感”的点之一。

问题

内存里只有 PQ 压缩向量。 PQ 距离不够准。如果最后结果完全按 PQ 距离排，recall 会掉。

一个直接的补救办法

在搜索完成后：

把候选点原始向量都从 SSD 拉出来
再做一次真实距离重排

这听起来对，但有问题：

如果一次性拉几十上百个候选点
会产生很多随机读
延迟和吞吐都会受影响

DiskANN 的做法

论文说：

每次从 SSD 读某个点的邻居时
该点的全精度向量本来就和邻居一起放在同一个磁盘块里
所以拿邻居时，顺便就拿到了这个点的全精度向量

于是随着搜索进行：

被访问的点的全精度向量会被“顺便”拿到
不需要额外随机读

最后返回结果时：

就可以用这些已经拿到的全精度向量做更准的排序

为什么叫 implicit reranking

因为它不是单独做一轮“重读候选再精排”，而是：

在正常扩图过程中
顺手积累了可用于精排的原始向量

所以是“隐式”的。

这招为什么厉害

因为它把“更准的精排”几乎做成了：

零额外随机读成本

这是很高级的系统优化思路。

第十三部分：DiskANN 为什么说自己兼得了图方法和压缩方法的好处

论文最后的定位其实很清楚：

图方法的优点

recall 高
导航能力强

压缩方法的优点

内存占用低
规模扩展强

DiskANN 想做的事

把二者结合：

图负责找路
PQ 负责让内存里保留“足够多的粗信息”
SSD 负责提供容量
全精度向量负责兜住最终精度

所以它不是单押某一条路线，而是：

图 + 压缩 + SSD + 缓存 + rerank 的组合拳。

第十四部分：论文实验到底证明了什么

1. Vamana 做内存图索引时就已经很强

论文比较了：

HNSW
NSG
Vamana

结论大意是：

Vamana 在 recall-latency 上能匹配甚至超过 HNSW / NSG
在某些数据上建图时间还更好

也就是说：

Vamana 不是“为了 SSD 强行妥协出来的图”
它本身就是一张很能打的图

2. Vamana 的 hop 数更少

这对 SSD 非常关键。论文明确指出：

在达到目标 recall 时
Vamana 所需 hop 数通常比 HNSW / NSG 少 2~3 倍

这等价于：

更少轮磁盘访问
更低延迟潜力

3. DiskANN 在十亿级数据上做到了很强的平衡

论文里最亮眼的结果之一是：

在 SIFT1B 上
单机 64GB RAM + 廉价 SSD
做到 95%+ 的 1-recall@1
平均延迟几毫秒
QPS 也很高

这在当时是非常强的结果。

4. 和压缩索引对比时，高 recall 优势明显

论文比较了 DiskANN 与：

FAISS
IVF-OADC+G+P

结论大意是：

在相近内存 footprint 下
DiskANN 的 recall 明显更高
特别是 Top-1 高 recall 场景，优势很突出

为什么压缩索引会吃亏

因为纯压缩方法依赖：

有损近似距离

而 DiskANN 用的是：

图导航 + PQ 粗筛 + 全精度隐式 rerank

所以最终精度更容易上去。

第十五部分：DiskANN 和 HNSW 的关系，到底该怎么理解

很多人容易把它们看成竞争关系，其实更准确的说法是：

DiskANN 是在“图索引很强”这个前提上，进一步把图索引扩展到单机大规模存储系统。

HNSW 更像什么

内存图 ANN 的代表作
重点是高 recall、低延迟、分层导航

DiskANN 更像什么

图 ANN 的系统化延伸
重点是 SSD 可扩展性
还要考虑 IO、缓存、布局、压缩、重排

一个很实用的判断

如果库能装进内存

很多时候先看：

HNSW

如果库装不进内存，且还要高 recall

那就要认真看：

DiskANN

所以二者更多是：

同一路线的不同 operating regime

第十六部分：DiskANN 和 IVF-PQ 的差别怎么理解

IVF-PQ 的思路

先分桶（IVF）
再在桶里用 PQ 编码比距离
本质上靠“分区 + 压缩”缩小搜索范围

DiskANN 的思路

靠图导航找到该去哪里
借助 PQ 做内存粗判
SSD 上有全精度向量兜底

区别可以这么记

IVF-PQ 更像：

先把城市切成区，只去几个区查

DiskANN 更像：

你沿着一张设计很好的高速路网，一步步驶向目标区域

哪个更好？

没有绝对。但通常：

超高 recall：DiskANN / 图路线更占优
极致内存效率、批量场景：IVF-PQ 很强
实际系统里两者都非常重要

第十七部分：我认为这篇论文最厉害的地方

如果让我挑最重要的 4 个点：

1. 它不是只提了个新图，而是完整把 ANN 做成了存储系统

这让它和很多“只在内存里卷曲线”的方法非常不同。

2. 它看重 hop，而不是只看 recall

这是非常系统思维的切入点。

对内存 ANN，访问点数很重要
对 SSD ANN，访问轮数（hop）尤其重要

3. 它把 PQ 用在了“粗判”而不是“唯一距离来源”

这是它比纯压缩路线更稳的关键。

4. 它把全精度 rerank 做成了“顺手拿到”的副产物

这非常优雅。

第十八部分：这篇论文的局限和后续问题

经典归经典，它也不是没有代价。

1. 系统复杂度更高

相比 HNSW：

DiskANN 涉及图、PQ、SSD、缓存、beam、分片合并
整体工程复杂度高很多

2. 构建链路并不轻

虽然 64GB 单机可建 merged index 很厉害，但：

分片
建局部图
合并
调优都不是白送的

3. 删除 / 更新 / freshness 不是这篇主论文重点

后来才有：

Fresh-DiskANN
Filtered-DiskANN 等后续工作

4. SSD 友好不代表所有 workload 都最佳

如果：

数据其实能轻松进内存
追求极低单 query latency 那 HNSW 这种纯内存图有时会更直接

第十九部分：给数学小白的最终复述

如果爹只想记住最核心的一版，可以记这段：

DiskANN 是一种面向超大规模向量检索的 ANN 系统。它先用一个新图 Vamana 把数据点连成一张更适合低 hop 导航的图，再把压缩向量放在内存里用于快速粗距离判断，把全精度向量和邻居列表放在 SSD 上。查询时，它不是一次只读一个点，而是用 beam search 并行读一小批点，并且把经常访问的点缓存到内存里。最巧的是，当它读取某个点的邻居时，会顺便拿到这个点的全精度向量，于是最后可以几乎零额外 IO 成本地做更准确的 rerank。正因为这样，DiskANN 才能在单机、有限内存条件下，把十亿级 ANN 做到高 recall 和低延迟。

第二十部分：如果我是工程师，我该抓住哪些最关键的点

1. DiskANN 的第一关键词不是“磁盘”，而是“hop 优化”

它不是简单把索引搬到 SSD，而是围绕 SSD 重新设计搜索路径。

2. Vamana 是 DiskANN 的地基

不懂 Vamana，就很难真正懂 DiskANN。

3. PQ 在 DiskANN 里不是主角，但非常关键

它不是负责最终精度，而是负责：

让内存保留足够多的粗信息
减少 SSD 读前的距离判断成本

4. 隐式 rerank 是系统亮点

如果没有它，DiskANN 很难同时兼顾：

高 recall
低额外 IO

5. DiskANN 是“系统组合拳”而不是单一技巧

它成功不是靠某一个公式，而是几个设计拼在一起：

Vamana
beam search
PQ 内存粗判
SSD 布局
热点缓存
顺手拿全精度向量 rerank

第二十一部分：与前面 HNSW 精读的关系

如果说前面的 HNSW 精读讲的是：

如何把图索引做到非常强的内存 ANN

那么 DiskANN 精读讲的就是：

如何在保留图索引高质量检索能力的前提下，把它扩展到单机 SSD 时代。

一个偏“内存图算法”，一个偏“图索引系统化落地”。

风车车知识库

探索

diskann-deep-dive-beginner

目录