Page 66 - 《软件学报》2026年第3期

周依杰 等: GoVector: I/O-高效的高维向量近邻查询缓存策略 1029

v 5 为中心, 系统可直接从同一类中加载相邻的 、 、 、 v 4 这 4 个顶点, 完成一次有效缓存填充;
容量, 因此以 v 2 v 5 v 9
在情况 2 中, 由于目标类 (类 3) 较小, 无法独立填满缓存页, 系统将以类 2 为中心, 同时补充加载类 2 中与目标点
相邻的顶点 ( v 4 ); 在情况 3 中, 若直接按照上述原则读取会导致磁盘读取范围的左边界超出索引文件, 因此系统会
执行边界检测与调整机制, 以避免读取异常, 确保读取行为的正确性.

类 1 类 2 类 3 v i 目标点 缓存页

v 0 v 1 v 8 v 2 v 5 v 9 v 4 v 3 v 6 v 7 v 0 v 1 v 8 v 2 v 5 v 9 v 4 v 3 v 6 v 7 v 0 v 1 v 8 v 2 v 5 v 9 v 4 v 3 v 6 v 7
情况 1: 目标类大小≥4 情况 2: 目标类大小<4 情况 3: 边界问题
图 7 相似性感知读取机制示意图

在静态缓存机制的基础上, GoVector 首次引入了查询感知的动态缓存区. 但由于在向量搜索的过程中, 动态
缓存区的数据量会随着搜索路径的扩展不断增长, 当其达到设定的容量上限时, 系统需执行缓存替换操作. 为此,
本文借鉴操作系统中虚拟内存管理的思想, 实现了 3 种替换策略: 先进先出 (first-in-first-out, FIFO)、随机替换
(Random) 以及最不经常使用 (least frequently used, LFU) 策略. 通过对 3 种策略的对比评估, 最终选择 LFU 作为动
态缓存的默认替换策略.
我们针对搜索的两阶段提出了不同的缓存方式, 因此, 如何准确识别两个阶段的转折点成为实现高效搜索的
关键. 本文借鉴了 PANNS [21] 中提到的识别方法, 即当候选队列中排名前 k 的顶点均已被访问时, 判定搜索进入
第 2 阶段. 然而, 在实际应用中, 该识别策略存在明显的滞后性, 即转折点往往在真实转折发生后经过多轮拓展才
被检测到. 如图 3 所示, 在 SIFT 和 GIST 数据集中, 距离查询点最近的向量分别出现在第 16 轮和第 8 轮, 即第 1、
2 阶段的真实转折点, 而 PANNS 识别的转折点分别出现在第 27 轮和第 16 轮. 为了克服转折点检测滞后这一问

题, 本文在此基础上引入了一个判断参数 θ (0< θ <1), 即当候选队列中排名前 θ ·k 的顶点均已被访问时, 判定搜索
进入第 2 阶段. θ 通过如下方法确定: 从数据集中随机抽取 1% 的查询向量样本, 记录每个查询在完整搜索过程中
′
的真实转折轮数 k (即首次访问 Top-k 最近邻所需的轮数), 并结合 PANNS 方法计算其估计转折轮数 k . 最终以
θ = k/k 的方式获得各查询的转折判断参数, 用于动态识别搜索阶段, 从而实现阶段切换的控制. 这种方法能够更
′
早感知搜索阶段的变化, 显著缓解转折点识别的滞后问题. 在图 3 的实验中, 相较于 PANNS, GoVector 在 SIFT 和
GIST 数据集中识别到的转折点分别提前 9 轮和 5 轮, 验证了该方法的有效性.
动态缓存机制对 ANNS 查询性能的优化效果, 不仅依赖于缓存策略的设计, 还与底层存储布局的局部性特征
密切相关. 若相似向量能够聚集于同一磁盘页中, 则顺序读取过程中加载的向量更有可能被访问, 从而进一步提升
缓存的命中率. 因此, 优化存储布局以提升 I/O 的访问局部性, 成为缓存机制之外的另一关键问题. 为此, 第 5 节将
重点探讨基于向量相似性的索引图重排序方法.
5 基于向量相似性的索引图重排序

5.1 I/O 效率问题分析
在大规模向量检索任务中, 磁盘 I/O 成本往往成为限制系统性能的关键瓶颈, 其另一原因在于单次 I/O 的有
效利用率偏低. 由于磁盘以页为基本读写单位, 系统在访问某个顶点的特征或邻居信息时, 必须整体加载该顶点所
在页的全部内容. 若该页面中仅有少数顶点实际参与查询过程, 其余数据则为无效读取, 造成带宽浪费. 为了继续
搜索其他相关向量, 系统不得不频繁加载新的磁盘页, 从而引发额外的磁盘 I/O 开销. 已有研究指出 [16] , 在 DiskANN
系统中, 每次读取的数据页中约有 94% 的顶点未被访问, 查询过程有超过 92.5% 的时间用于磁盘 I/O. 该问题在
ANNS 查询的第 2 阶段尤为突出, 此阶段虽已定位到部分与查询向量接近的初始候选, 但为了进一步优化结果, 还
需在其邻近的向量空间中进行更深入的拓展. 若能将当前拓展顶点与其近邻的其他向量集中存储于同一磁盘页
内, 则系统一次 I/O 操作就能加载多个有可能被命中的向量, 有效提升单次 I/O 的利用率, 减少冗余磁盘访问. 然
而, 目前主流的数据布局策略仍主要基于图结构连接关系组织页面, 如 Starling 系统采用 BNF (block neighbor