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

1028 软件学报 2026 年第 37 卷第 3 期

个向量空间, 该局部区域内的向量在空间上更为接近, 也更有可能被访问以用于距离计算和候选集扩展. 图 6(a) 展
示了该环形区域的结构示意图. 基于这一观察, 如果第 2 阶段的查询过程能够聚焦于该区域内的向量, 对其进行有
序组织并采用对应的物理存储布局, 使缓存的换入与换出操作局限于该区域所覆盖的磁盘页之间, 则每次磁盘
I/O 所加载页面中的向量将具有更高的实际访问概率, 从而显著提升缓存命中率, 减少冗余 I/O 开销. 然而, 当前主
流的基于磁盘的索引图方法 (如 DiskANN) 在搜索过程中仍采用逐点加载策略, 仅加载当前拓展顶点所在的磁盘
页, 并在获取该顶点的向量与邻居信息后立即将其从内存中淘汰, 忽略了第 2 阶段中拓展顶点在向量空间中的聚
集性特征, 未能有效利用访问路径中的空间局部性, 从而可能引发重复的磁盘 I/O 操作. 因此, 第 1 阶段的查询过
程仍可采用传统静态缓存机制, 而第 2 阶段则应对现有策略加以改进, 设计聚焦于局部区域的缓存机制, 以更高效
地支持查询路径中频繁访问的热点区域.

动态缓存区 … 新加载页 … 已存在的页
缓存未命中, 进行页面加载 缓存命中, 直接从缓存读取
d max
入口点 v 0 v 3 v 6 v 4 v 7 v 5 v 2 … 候选优先队列
v 3 d min
v 0
查询点
v 8 v 6
v 7 v 0 v 1 v 8 v 0 v 1 v 8 v 0 v 1 v 8
v 4
v 1
…
v 5 v 3 v 6 v 7 v 3 v 6 v 7
v 2
v 9
… …
v 2 v 4 v 5
拓展顶点顺序 v 0 v 3 v 6 v 4 v 7 v 5 v 2 v 9 v 8 v 1
随拓展顶点产生的缓存变化 t
(a) 第2阶段搜索向量扩展的范围 (b) 顶点拓展过程和缓存的动态更新
图 6 动态缓存示意图

4.2 查询感知的混合缓存设计
基于第 4.1 节的分析结果, 本文提出了一种静态-动态结合的混合缓存机制, 即搜索的第 1 阶段采用静态缓存
策略 (与传统的 Beam Search 一致), 用于加速起始路径的高频访问; 当搜索进入第 2 阶段后, 系统启用动态缓存机
制, 重点优化访问局部性较强的路径. 具体而言, 在第 2 阶段的搜索过程中, 对于缓存未命中的拓展顶点, GoVector
会结合该顶点在向量空间中的位置, 触发一次批量读取操作, 将其邻近区域内的多个向量一并从磁盘加载至动态
缓存中. 这种策略旨在充分利用拓展点之间的空间相似性, 使后续拓展的顶点更有可能命中缓存, 从而显著减少频
繁的随机 I/O 操作所带来的性能开销. 如图 6(b) 所示, 当系统拓展顶点 v 3 时, 由于缓存未命中, 系统根据其在向量
v 3 、 v 7 所在的缓存页加载至动态缓存区. 由于候选优先队列中的顶点具有较高
空间中的邻近性, 一次性地将 v 6 和
的拓展概率, 系统在后续拓展过程中能有效复用之前加载的缓存页. 例如, 当拓展到顶点 v 6 和 v 7 时, 其所对应的缓
存页已由此前拓展 v 3 时加载入缓存, 因而可直接命中, 避免重复的磁盘访问, 从而显著提升整体查询效率.
为了适配该动态缓存机制, GoVector 设计了一种相似性感知读取策略. 为了支持顺序批量加载, GoVector 在
索引构建阶段对向量数据进行了空间布局优化, 使得相似向量能够按类进行划分与存储, 从而在物理层面上实现
良好的局部性. 因此, 在执行读取操作时, 系统能够以顺序访问的方式定位相关页面, 比传统的随机 I/O 开销更低.
该相似性感知读取机制的关键在于, 针对每个待拓展的目标顶点, 系统动态确定其所属类及其类内位置, 并结合当
前查询上下文, 计算出最合适的顺序读取区间, 实现局部性增强的批量加载操作. 具体来说, 每次拓展目标点时, 系
统首先识别目标点所属的类 (目标类), 再结合类的大小与拓展点在其中的相对位置, 计算最优的顺序读取起止区
间, 实现更具局部性的批量加载行为. 自适应数据读取机制遵循以下 3 条原则: ① 以目标点为中心, 优先加载其所
属类中的相邻顶点; ② 在当前类无法满足读取需求时, 优先从目标类及其相邻类中补充加载顶点; ③ 保证读取范
围不发生越界.
图 7 展示了实际应用中常见的 3 种典型场景, 假设缓存页大小为 4. 在情况 1 中, 目标类的大小不小于缓存页