《大规模分布式计算深入解析》4.3 Vamana/DiskANN:磁盘图遍历、图剪枝与鲁棒性

Vamana RobustPrune按几何与α剪枝;DiskANN查询用内存压缩表示和SSD节点读取,候选宽度、IO并行度与缓存分开。

Vamana负责什么

Vamana构建可导航图,RobustPrune在候选中先选离中心最近的点,再删除被该邻居充分覆盖的候选,最多保留R个邻居。alpha控制几何约束,不能用“保留数组前R−1项再塞一个指定父节点”替代。

本卷以欧氏距离定义规则alpha·d(selected,candidate)≤d(center,candidate)。代码用平方距,因此比较alpha²·d²而非alpha·d²。候选ID必须来自点集,禁止注入不存在的keepId。

几何算例

中心p=(0,0),候选a=(1,0)、b=(0.7,0.9)、c=(0.4,2)、d=(2.2,0),alpha1。a先留下;b更接近a而被剪;c距a约2.09、大于距p约2.04,留下;d被a覆盖。结果为a/c。R只是上限,不保证一定填满。

完整Vamana还有搜索候选、图更新和构建轮次。本卷实现RobustPrune与小型图例,不把一个几何函数称为完整Vamana构建器。

DiskANN为什么不等于mmap BFS

经典DiskANN在内存持有压缩码用于候选评分,SSD持有节点的原向量、邻接等内容;缓存减少部分读,beam搜索让一批候选的IO有并行机会。最终对已读取的原向量有更精确的距离与结果处理。

搜索列表长度控制候选质量/工作量,IO beam宽度控制一轮读取并发,不是图出度R。访问20个节点也不能直接推导20次设备IO,缓存、节点布局、sector/page和请求合并都会影响结果。

失败与文件一致性

节点读取失败、索引文件损坏、超时、压缩码与图版本不匹配都需要明确处理。不能默默少读一部分后仍宣称完整TopK。本卷实际映射测试会拒绝错误文件头,但没有实现SSD异步调度、缓存策略、完整索引文件或故障恢复。

架构与流程

flowchart LR
    Q["查询向量 q"] --> LUT["内存:PQ查询距离表"]
    PQ["内存:库向量压缩码"] --> SCORE["候选近似评分"]
    LUT --> SCORE
    SCORE --> FRONT["搜索前沿:优先候选 / visited / beam宽度"]
    FRONT --> CACHE{"候选节点数据在缓存?"}
    CACHE -->|"是"| NODE["原向量与邻接表"]
    CACHE -->|"否"| READ["提交有限并行的SSD读取"]
    READ --> SSD["磁盘节点布局:向量、邻接、元数据"]
    SSD -->|"读取完成"| NODE
    NODE --> EXPAND["扩展邻居;更新候选近似分数"]
    EXPAND --> SCORE
    NODE --> EXACT["已读取原向量精确距离"]
    EXACT --> RESULT["最终候选排序与结果"]
    FAIL["读失败 / 超时 / 损坏"] -.-> POLICY["按实现拒绝、重试或失败返回"]
    READ -.-> FAIL

实现与验证边界

几何剪枝原例与非法ID拒绝有真实断言;映射读取另在4.1验证。DiskANN分层图是原论文机制解释,没有部署DiskANN或测SSD吞吐,不把BFS当磁盘ANN实测。

下载卷十三实验包 。Java 8入口为 lab.RunAll;本节对应 diskann.DiskannSuite。按README分别运行模型与原生入口,失败必须返回非零。模型通过不代表完整产品实现。

一手资料

卷十三目录 · 系列导读

继续阅读

探索更多技术文章

浏览归档,发现更多关于系统设计、工具链和工程实践的内容。

全部文章 返回首页

「books」更多文章

  1. 《大规模分布式计算深入解析·向量数据库与 AI 检索内核》 · 目录与学习路径(45 篇)
  2. 《大规模分布式计算深入解析》15.3 自研向量引擎:可执行骨架与工程缺口
  3. 《大规模分布式计算深入解析》14.1 Milvus:组件架构、段管理与检索链路