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

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

候选区域. 在动态缓存区, 系统自适应地缓存当前查询过程中访问到的顶点所在的页面及其在磁盘中邻近的页面,
用于支持 Top-k 相似向量的扩展访问. 在磁盘层面, GoVector 首先基于向量相似性对查询点邻近区域内的向量进
行聚类, 并据此对原始索引图中的向量进行重排序. 重排序后的向量再依据分区存储至磁盘, 以提升数据访问的局
部性, 减少跨页加载频次.
图 4 展示了该搜索流程的主要步骤. ① 从候选向量队列中选取当前距离最近且尚未访问的顶点进行拓展.
② 根据拓展点的 ID 向混合缓存模块发起数据读取请求. ③ 混合缓存模块判断该顶点是否已驻留于缓存中, 若命
中则返回其向量和邻居信息, 否则向读取模块发起磁盘访问请求. ④ 读取模块根据当前所处的搜索阶段来选择不
同的磁盘加载策略, 若当前处于搜索的第 1 阶段, 则直接读取拓展顶点所在的磁盘页, 反之则采用相似性感知读取
机制, 同时加载拓展点及其相似向量所在的多个页. ⑤ 将读取到的顶点向量和邻居信息加载至内存, 若当前阶段
为第 2 阶段, 还需将相关页面写入动态缓存. ⑥ 计算拓展点与查询向量之间的真实距离, 并依据 PQ 距离将其邻居
加入候选向量队列中.
4 静态-动态混合缓存机制

4.1 现有缓存策略局限性分析
传统的 Beam Search 搜索算法通常采用静态缓存机制, 即在系统初始化阶段, 根据预设的缓存容量, 预加载入
口顶点及其若干跳邻居, 并在整个搜索过程中保持缓存内容不变. 该机制在搜索的初始阶段具有较高的缓存命中
率, 因为每轮查询均从入口顶点出发, 路径前几跳的顶点被频繁访问, 因而能够有效提升命中率. 然而, 静态缓存机
制无法感知查询路径的实际拓展行为, 导致其命中范围往往局限于搜索路径的初始几跳. 随着搜索的深入, 命中率
迅速下降, 导致后续阶段的访存效率大幅降低. 我们基于 DiskANN 在 SIFT 与 GIST 两个数据集上进行了实验测
试, 结果如图 5 所示. 随着查询拓展轮数的增加, 静态缓存的命中率呈现明显的幂律衰减趋势. 结合第 1.3 节中的
两阶段搜索划分标准, 我们将找到精确最近邻的轮次定义为两个阶段的转折点, 并在图 5 进行标注. 可以观察到,
当搜索进入第 2 阶段后, 静态缓存的命中率相比于第 1 阶段显著下降. 在第 1 阶段, 两个数据集的静态缓存命中率
分别为 19% 和 63%; 而在第 2 阶段, 该命中率大幅下降, 仅为 4% 和 9%. 此外, 实验结果还表明, 第 2 阶段的搜索
耗时通常占据总搜索时间的 80% 以上, 说明该阶段已成为制约整体检索效率的主要性能瓶颈.

100 100
第1阶段 80 第1阶段
累积缓存平均命中率 (%) 60 累积缓存平均命中率 (%) 60
第2阶段
第2阶段
80

40
40
20

0 20 0
0 16 50 100 0 8 50 100
拓展轮数 拓展轮数
(a) SIFT (b) GIST
图 5 DiskANN 100 轮拓展中静态缓存命中率变化曲线 (k=10)

为了更深入地理解第 2 阶段的拓展特性, 我们进一步分析了该阶段拓展的顶点与查询向量之间的距离分布.
图 3 展示的实验结果表明, 在该阶段中, 拓展的顶点 p 在向量空间中与查询向量 q 的距离集中落在一个窄幅区间
∗
d(p ,q) 表示拓展顶点与查询向量之间的距离. 根据图 3 的实验结果,
∗
内, 波动较小, 表现出显著的空间聚集性. 设
d min < d(p ,q) < d max . 其中, d max 分别表示该阶段访问点与查询向量之间的最小与最大距离. 由此可见,
∗
可得 d min 和
第 2 阶段的查询过程实际上被限制在一个以 q 为中心、半径范围为 [d min ,d max ] 的环形区域内进行扩展. 相较于整