共计 2581 个字符，预计需要花费 7 分钟才能阅读完成。
在 Milvus 社区中，与磁盘索引相干的问题成为近期用户集中询问重点。为了不便用户更深刻地理解磁盘索引，咱们将从其原理登程，由表及里地介绍如何用好磁盘索引。
Milvus 是世界上最快的向量数据库，在最新版本的 Milvus 中，基于内存的 HNSW 索引能够提供极致的性能体验。然而，Milvus 的指标是反对多种不同的场景，除了性能，咱们也谋求性价比和可扩大，因而便有了磁盘索引。
基于 DiskANN 的磁盘索引能够在仅应用 1/10 的内存耗费下，施展出 HNSW 索引 1/3-1/2 的性能能力，可能在千万级别的数据上拿到 ~10ms 的提早能力。因而，它能够帮忙用户在 QPS、Latency 不特地敏感的场景下大大降低资源的耗费。
01.
DiskANN 原理浅析
之前曾经有 Zilliz 的同学写过一篇对于 DiskANN 论文的相干文章 [1]，感兴趣的敌人能够理解一下。
回到原理介绍的局部，DiskANN 的大抵构造是在内存中保护一个 PQ，而后原始向量和邻接表以 Vamana 图的构造贮存在硬盘里。
Vamana
图的构造有很多种，最早是 2011 年有文章提出链接每个点的最邻近的 K 个点。这种策略的空间占用高，并且性能差。
起初大家优化的重点就在于如何去剪枝。2017 年，有篇文章提出了 NSG 图，策略就是如果一个新的点离指标点的距离远于离指标点的街坊，就不链接。即保障对于指标点的街坊，以它为核心，到指标点的间隔为半径的圆里边没有别的指标点的街坊。
这种策略缩小了每个点的出度，大大放慢了查问的速度。
DiskANN 基于的 Vamana 图就是由 NSG 演进而来，具体的改良就是因为 NSG 的裁边机制过于激进导致精度降落，因而引入一个参数 alpha 来管制裁边。具体就是裁边的时候判断的间隔乘上这个系数后还是过大才会裁掉。
Build
简略介绍一下 DiskANN 建索引的过程：
首先 DiskANN 会对原始数据采样找到 PQ 的 Pivots，这一步 DiskANN 默认是 256 个 clusters，会依据用户容许的在查问中应用的内存来决定 chunk 数目和大小。而后对原始数据进行 PQ 压缩。
而后 DiskANN 会基于原始数据来构建 Vamana 图，依据用户的容许的在建索引中应用的内存在决定是一次建完还是分批建而后 merge。后者会有较大的性能升高。
而后是把数据都写入磁盘，并删除两头文件。
最初会生成一个从原始数据中随机采样的样本用于 warmup。
Search
首先 DiskANN 会加载磁盘中的索引文件，把 PQ 码表放进内存，而后依据用户的参数开始建设 cache 和 warmup。
Cache 的策略有两种：
取之前的采集的样本进行 query，缓存两头路过的点。目前是用于 KNN search。
在 entrypoint 四周进行 BFS，缓存这些点，目前用于 range search。
Warmup 的形式则是对样本进行 query。
而后就是 DiskANN 的搜索算法，具体做法是：
先依据参数固定一个 search list，把 entry point 放进去。
而后从 search list 每次拿至少 beamwidth 个点，在硬盘中加载向量和街坊。
用 PQ 计算这些街坊到指标点的间隔，择优放进 Search List（相似于 Priority Queue）。
始终循环到 search list 被占满。且都拜访过。
把路径的所有点收集起来排序取 topK。
02.
DiskANN in Milvus
Build 时，IndexNode 会从 MinIO 里抓取原始数据，预处理后放入本地磁盘。而后 DiskANN 会从磁盘中读取文件并生成索引文件。最初由 IndexNode 把建好的索引文件解决后推到 MinIO 里。
Search 的时候，QueryNode 会从 MinIO 里抓取索引文件，与解决后放入本地磁盘。而后 DiskANN 会从本地磁盘中加载大量必要的信息以供查问。
03.
如何用好磁盘索引
实用场景
磁盘索引实用于对性能不是十分敏感，且内存资源无限的场景。在默认场景下，内存的占比是原始数据大小的 1/4，其中 1/8 用作 PQ 码表，1/8 用作 cache。索引的磁盘占用是原始数据的 1.5~2 倍。这些比例都能够通过参数来调节以满足不同场景的需要，后边会具体介绍。
数据类型：目前 Milvus 的 DiskANN 只反对 float 类型的数据。
间隔类型：DiskANN 能反对 L2 和 IP 间隔。
维度：因为 Milvus 根据原始数据大小划分 Segment，如果维度过小，会导致一个 Segment 里数据行数过多。
DiskANN 的索引次要由原始数据和邻接表组成，过多的行数会导致单个 Segment 索引中邻接表数量变大，从而导致整个索引大小过大。因而 Milvus 的 DiskANN 临时不反对 16 维以下的向量。因为 DiskANN 会大量拜访磁盘，而磁盘的拜访都是以一个大小是 4096 的 page 为根本单位的。因而过大维度会引起磁盘拜访增大，从而导致性能降落。Milvus 的维度下限为 32768，然而为了取得更好的性能，举荐的最大维度为 1024。
性能瓶颈
磁盘索引的 Search 性能瓶颈个别集中在磁盘 IO 上，因而好的磁盘对于性能的晋升简直是线性的。一般来说 SSD(NVMe) 的性能是 SSD(Sata) 的 4 - 5 倍，而 SSD(Sata) 的性能是个别 HDD 的 4-5 倍。
然而磁盘的性能对索引的 Build 性能影响不大。Build 的时候 DiskANN 须要在内存里建图，因而须要约单个 Segment 原始数据 1.7-2 倍左右大小的内存反对。如果内存不够，DiskANN 会分块建图再合并，会造成比拟大的 Build 性能损失。
参数调整
对于磁盘索引的相干参数调整能够参见 Milvus 官网文档 [2]。
这里还想分享一个性能上的 trick。个别图算法在数据量增大后，Latencty 的回升会很不显著。因而调整 Segment 大小能对性能产生不小的影响。在 ${MILVUS_ROOT_PATH}/configs/milvus.yaml 里，调大 dataCoord/segment/diskSegmentMaxSize (默认 2G) 会让性能更好。
参考资料
[1]DiskANN 论文相干文章：https://zhuanlan.zhihu.com/p/394393264
[2] 官网文档：https://milvus.io/docs/disk_index.md
（本文作者刘力系 Zilliz 主任工程师）
本文由 mdnice 多平台公布