[Paper] 传递接力棒：高吞吐量分布式基于磁盘的向量搜索与 BatANN

Source: arXiv - 2512.09331v1

概览

本文介绍了 BatANN，一种分布式、基于磁盘的近似最近邻（ANN）引擎，能够在多台机器上搜索数十亿高维向量，同时不牺牲单节点图索引的低延迟、对数时间保证。通过“传递接力棒”——将完整的查询状态交给拥有图的下一部分的节点——BatANN 实现了近线性吞吐量扩展，同时将延迟保持在单数字毫秒范围内。

关键贡献

• 跨节点的单一全局图 – 首个开源系统能够在多台服务器上对单个 ANN 图进行分片，保持对数搜索路径长度。
• 接力棒查询模型 – 当搜索步骤到达存储在另一台机器上的邻居时，整个查询上下文会被转移，使远程节点能够在本地继续遍历，避免往返通信。
• 近线性吞吐量扩展 – 在 1 亿和 10 亿向量数据集上，使用普通 TCP 实现了比朴素的 scatter‑gather 基线高出 2.5‑6.5 倍的吞吐量。
• 基于磁盘索引的低延迟 – 即使索引位于 SSD 上且数据集远超内存，仍能保持平均延迟低于 6 ms。
• 开源发布 – 为社区提供了可直接用于构建大规模向量检索服务的生产级代码库。

方法论

1. 图构建 – 在完整数据集上构建层次化可导航小世界（HNSW）图，然后使用简单的基于哈希的分片方案将图的顶点划分到不同服务器。
2. 查询状态打包 – 查询由当前节点 ID、查询向量以及一个小的候选邻居优先队列组成。当遍历步进入由另一台服务器拥有的顶点时，整个状态包会通过 TCP 发送。
3. 远程执行 – 接收服务器在本地恢复图遍历，展开邻居、更新候选队列，并可能再次转交接力棒。初始请求之后不再需要中心协调器。
4. 终止条件 – 当候选队列稳定（即不再发现更好的邻居）时，遍历停止，最终的 top‑k 结果返回给客户端。
5. 评估 – 在配备 SSD 存储的普通服务器上进行基准测试，测量召回率（≈0.95）、吞吐量（每秒查询数）和平均延迟，覆盖不同集群规模（1‑10 节点）和数据规模（1 亿 与 10 亿 向量）。

结果与发现

• 可扩展性：吞吐量随服务器数量几乎线性增长，验证了接力棒机制的有效性。
• 网络效率：即使仅使用普通 TCP（无 RDMA 或自定义协议），仍能实现高性能，说明该方法对典型数据中心网络具有鲁棒性。
• 召回率与速度的权衡：BatANN 在保持单节点 HNSW 索引召回率的同时，在大规模数据集上实现了数量级更高的查询速率。

实际意义

• RAG 与 LLM 流水线：开发者现在可以将真正庞大的向量存储（数十亿嵌入）接入检索增强生成系统，而不会产生不可接受的延迟，从而支持更丰富的上下文窗口。
• 即服务搜索：SaaS 提供商能够为图像、音频或代码片段提供高吞吐量的相似度搜索，同时通过将大部分索引放在廉价 SSD 节点上降低硬件成本。
• 混合云部署：由于 BatANN 基于标准 TCP，可在本地集群、公有云或边缘位置部署，无需特殊网络栈。
• 开源可扩展性：团队可以 fork 代码库，以集成自定义距离度量、安全层（TLS、认证）或与现有向量数据库（如 Milvus、Vespa）结合，构建统一的技术栈。

局限性与未来工作

• 分片简易性：当前的哈希分片可能在数据分布偏斜时导致负载不均；更复杂的图感知分片器有望提升均衡性。
• 容错性：本文侧重性能，节点故障时保持查询正确性的处理仍是未来的工程工作。
• GPU 加速：所有实验均在 CPU 节点上完成，探索基于 GPU 的距离计算可能进一步提升吞吐量，特别是对计算密集型度量。
• 动态更新：向量的插入与删除目前需要重建或复杂的再平衡，增量更新机制仍是开放的研究方向。

BatANN 表明，通过巧妙的查询交接策略，分布式基于磁盘的向量搜索既可以快速又可以扩展，为开发者在 PB 级嵌入存储上构建下一代检索服务打开了大门。

作者

• Nam Anh Dang
• Ben Landrum
• Ken Birman

论文信息

• arXiv ID: 2512.09331v1
• 分类: cs.DC, cs.IR
• 发表时间: 2025 年 12 月 10 日
• PDF: Download PDF