按照上面的估算公式，到了 10 亿级别就需要大约 100 个节点，到 100 亿级别需要的节点数为 1000 个左右，这个规模的服务在资源成本和稳定性上都面临了极大的挑战。我们在服务客户的过程中，发现相比于低延迟检索需求，大部分客户更关注成本和稳定性，因此，火山引擎云搜索团队在原先已经支持的 HNSW、IVF 等低延迟的算法引擎的基础上，引入了内存和磁盘更好平衡的 DiskANN 算法，目前已经在 200 亿单一向量库得到落地验证并取得预期效果。
DiskANN 算法的关键在于，仅将轻量级的索引结构置于内存中，而海量的原始数据以及构建好的图结构存放于磁盘，同时借助磁盘的多路读取能力，缓解内存压力的同时，高效完成近邻检索任务的三大目标：海量数据、高召回率、低时延。DiskANN 论文提到可以节约 95% 的资源，从我们落地的多个用户案例来看，非常接近这个收益值，客户仅需几十台机器就稳定高效地支撑百亿级业务需求。除了资源成本的收益之外，大规模数据应用场景下也极大提高了系统的稳定性。这是因为 DiskANN 极大减少了对内存资源的依赖，因此也具备了非常高的可扩展性，在我们的实践经验中也得到验证，从千万数据规模到十亿再到百亿，查询性能的波动非常小，具备非常高的系统可预测性。
什么是近邻检索
DiskANN 实现
为了解决上述问题，DiskANN 算法首先提出了新的图结构 Vamana，Vamana 图与 HNSW、NSG 图类似，区别在于初始图的选择、以及构图剪枝过程中引入宽松参数，在图直径和节点连通度上达到平衡，图的质量相对有所提升。其次，为了规避多次随机读写磁盘数据，DiskANN 算法结合两类算法：聚类压缩算法和图结构算法，一是通过压缩原始数据，仅将压缩后的码表信息和中心点映射信息放到内存中，而原始数据和构建好的图结构数据存放到磁盘中，只需在查询匹配到特定节点时到磁盘中读取；二是修改向量数据和图结构的排列方式，将数据点与其邻居节点并排存放，这种方式使得一次磁盘操作即可完成节点的向量数据、邻接节点等信息的读取，通过对以上两种算法的结合可以大幅提升向量召回的读取效率，降低图算法的内存，提升召回率。
构图流程
1.均匀采样数据，构建 pq 中心点信息以及压缩数据信息：
2.构建 Vamana 图，从随机图开始不断执行建边和剪枝操作，保证图的稠密度：
3.创建磁盘图结构，向量数据和邻接节点紧凑排列：
查询流程
1.给定查询向量 q，从入口点 p 出发，开始搜索 k 近邻：
2.当前遍历到的数据点，读取磁盘，以原始向量计算与查询节点的精确距离，进入结果集队列（Return Set，队列内以距离进行排序）。
3.当前节点的所有邻接节点，以 pq 数据计算与查询节点的近似距离，进入候选集队列（Candidate Set，队列内以距离进行排序）。
4.从候选集队列的头部取出 pq 距离最近的数据点。
5.重复执行 2-4 步骤，直至候选集中的数据点均被访问过，最终返回结果集。
实现效果
我们能够通过标注数据集验证可以看到使用 DiskANN 可以带来 10 倍以上的内存资源的提升，并且在召回率、性能上依旧能保持高效的检索能力。
*数据来源见文末参考论文
DiskANN 通过构建低时延、高召回率的 Vamana 图，同时辅以内存与 SSD 磁盘之间的高效协同作业，召回率和主流的 HNSW 图算法基本保持一致，内存资源占用相比于基于图的算法要大幅减少，在召回率要求高、时延查询可接受的场景下，无疑是最具性价比的海量数据向量搜索算法。
云搜索通过引入 DiskANN，以最低的成本构建海量数据检索，帮助客户在信息检索和 RAG 检索中能够大规模、高精度、低成本高效的构建检索应用。
火山引擎云搜索服务兼容 OpenSearch、Elasticsearch、OpenSearch DashBoards、Kibana 等软件及常用开源插件，支持全文搜索、向量搜索、混合搜索、时空检索等。提供结构化、非结构化文本的多条件检索、统计、报表，可以实现一键部署、弹性扩缩、简化运维，快速构建日志分析、信息检索分析等业务能力。
更多推荐实践
点击阅读原文，立即体验
如有侵权请联系:admin#unsafe.sh