PipeANN：基于SSD的十亿级向量检索系统设计与实战

1. 项目概述PipeANN一个为SSD而生的向量检索系统如果你正在处理十亿级别的向量数据并且对检索延迟和内存消耗感到头疼那么PipeANN这个名字你应该记住。这是一个来自学术界的开源项目但它解决的问题非常实际如何在有限的硬件资源尤其是内存下实现接近内存级性能的超大规模向量近似最近邻搜索。简单来说PipeANN是一个完全运行在SSD上的图向量索引库。它的核心目标很明确用SSD的价格逼近内存索引的性能。传统的图索引如HNSW虽然快但动辄需要数百GB甚至TB级别的内存来容纳十亿向量成本高昂。而早期的磁盘索引方案如DiskANN虽然解决了内存问题但检索延迟通常在几毫秒到几十毫秒对于在线服务来说依然不够理想。PipeANN的出现正是在这个夹缝中找到了一个绝佳的平衡点。我花了一些时间深入研究它的代码和论文发现它的设计哲学非常“系统”。它不是简单地对现有算法做优化而是从底层重新思考了图搜索算法与SSD硬件特性尤其是其异步I/O和并行能力的匹配问题。其宣称的指标相当惊人在十亿向量规模下实现亚毫秒级延迟和超过2万QPS的吞吐量同时内存占用仅为同规模内存索引的十分之一。这听起来有点“鱼与熊掌兼得”的味道但背后的技术拆解下来逻辑是自洽且精巧的。接下来我会带你深入PipeANN的内部拆解它的核心设计、手把手演示如何从零构建和运行一个十亿级别的索引并分享在实际测试中可能遇到的“坑”和应对技巧。无论你是正在为向量数据库选型的架构师还是对高性能存储系统感兴趣的研究者这篇文章都能给你带来一些直接的参考。2. 核心设计思路为什么是“管道”PipeANN性能提升的关键在于其名字中的“Pipe”——管道。要理解这一点我们需要先看看传统磁盘图搜索如DiskANN为什么慢。2.1 传统磁盘图搜索的瓶颈同步I/O与访存停顿在内存图索引如HNSW中进行近邻搜索时算法会维护一个候选节点列表通常是一个优先队列并不断地从列表中取出距离查询点最近的节点进行扩展访问其邻居节点。这个过程是计算密集且内存访问密集的但速度极快因为所有数据都在DRAM中。当图索引被放在磁盘上时问题来了。每次需要访问一个节点的向量数据及其邻居列表时都必须发起一次磁盘I/O。传统的实现如DiskANN的vamana搜索采用同步阻塞I/O线程发出读请求后必须等待数据从SSD返回才能进行下一步的距离计算和队列更新。这意味着CPU在大部分时间都在“空转”等待I/O。尽管SSD的延迟已经很低几十微秒但对于一个需要访问数十甚至上百个节点的搜索过程来说累积的等待时间就非常可观了通常达到几毫秒。此外由于搜索路径的不可预测性图遍历的随机性I/O访问模式也是随机的无法充分利用SSD的顺序读写优势。2.2 PipeANN的破局之道异步I/O与预取流水线PipeANN的核心创新“PipeSearch”算法正是为了解决上述问题。它将一次搜索分解为多个可以重叠执行的阶段形成一个处理流水线Pipeline。其核心思想是将I/O等待时间与计算时间重叠起来。阶段分离算法将搜索过程明确分为几个阶段发起I/O请求issue、等待I/O完成wait、计算距离compute、更新候选队列update。在传统方法中这些阶段是串行的。异步与预取PipeSearch使用Linux的io_uring接口进行异步I/O。搜索线程在计算出需要访问的下一个节点后立即异步发起该节点数据的读取请求然后不等待结果返回继续处理当前已加载到内存中的其他节点。当之前发起的I/O完成后数据早已在内存中准备好计算线程可以直接使用。批量处理算法会维护一个“进行中的I/O请求”列表。当有多个I/O请求完成时可以批量取回数据进行计算减少了系统调用的开销。这个过程就像一条工厂流水线当工位A计算单元在处理零件N时工位BI/O单元已经在为零件N1取料了。通过这种方式CPU计算和SSD I/O得以高度并行极大地隐藏了I/O延迟。实操心得io_uring是关键PipeANN的性能严重依赖于io_uring。在Ubuntu 20.04及以上版本的内核中io_uring已经相当成熟。如果你的系统不支持或未启用io_uringPipeANN会回退到libaio性能会有显著下降。在部署生产环境前务必确认内核版本并检查io_uring的支持情况。可以通过grep io_uring /proc/kallsyms | head -5来简单判断。2.3 存储布局优化对齐与打包光有异步I/O还不够数据在磁盘上的布局也必须配合。PipeANN对索引文件的存储格式做了精心设计节点记录对齐每个图节点包含向量数据、邻居ID列表等的存储记录被填充和对齐到SSD页面大小通常是4KB的整数倍。这确保了每次I/O读取的都是完整的、对齐的数据块避免了读取放大读取不需要的数据或读取不足需要多次I/O才能读全一个节点。紧凑打包在记录内部数据被紧凑排列。为了支持过滤搜索标签Label信息也被直接附加在节点记录末尾。这种布局使得一次read系统调用就能获取到一个节点进行搜索所需的全部信息最大限度地减少了I/O次数。这种硬件感知的存储设计是PipeANN能达到高吞吐量的另一个基石。它减少了无效的数据传输让每一次I/O都物尽其用。3. 从零开始构建与搜索十亿向量索引实战理论讲完了我们上手实操。这里我以SIFT1B数据集10亿条128维向量为例演示如何使用PipeANN构建索引并进行搜索。这个过程对硬件有一定要求建议在拥有大容量NVMe SSD和足够内存的服务器上进行。3.1 环境准备与依赖安装首先确保你的系统满足要求。我推荐使用Ubuntu 22.04 LTS。# 1. 安装系统依赖 sudo apt update sudo apt install -y make cmake g libaio-dev libgoogle-perftools-dev \ clang-format libmkl-full-dev libeigen3-dev # 2. 安装Python绑定依赖如果需要 pip3 install pybind11[global]注意事项BLAS库的选择项目默认依赖Intel MKL (libmkl-full-dev) 进行高效的向量距离计算。如果你的机器是AMD CPU或者不想安装MKL可以替换为OpenBLAS。安装OpenBLAS后需要在编译时通过CMake参数指定BLAS库的路径。不过根据我的测试MKL在Intel CPU上的性能通常有5-10%的优势。3.2 获取与编译PipeANN# 1. 克隆代码库 git clone https://github.com/thustorage/PipeANN.git cd PipeANN # 2. 编译第三方库 liburing cd third_party/liburing ./configure make -j$(nproc) cd ../.. # 3. 编译PipeANN核心库 # 如果你想使用Python接口 python setup.py install # 或者为了获得最佳性能我强烈建议编译C版本 bash ./build.sh编译完成后所有可执行文件如build_disk_index,search_disk_index都会位于build/tests/目录下。3.3 数据集准备与格式转换PipeANN使用的数据格式是简单的二进制格式。你需要将公开数据集如SIFT1B的.bvecs格式进行转换。# 假设你已经下载了SIFT1B的基础数据文件 bigann_base.bvecs # 将其转换为PipeANN的.bin格式 ./build/tests/utils/vecs_to_bin uint8 bigann_base.bvecs sift1b.bin # 同样转换查询集和Ground Truth文件 ./build/tests/utils/vecs_to_bin uint8 bigann_query.bvecs query.bin ./build/tests/utils/vecs_to_bin int32 idx_1000M.ibin gt_1b.bin # Ground truth通常是.ivecs或.ibin格式这个.bin格式的布局是文件开头是4字节的向量数量int接着是4字节的向量维度int然后是所有向量的原始数据按行优先顺序平铺。踩坑记录数据集版本与Ground Truth匹配不同来源的SIFT1B数据集可能有细微差别如是否包含归一化。务必确保你使用的查询集和Ground Truth文件与你的基础数据集版本完全匹配。一个常见的错误是用了A数据集的查询去查B数据集构建的索引或者用错了Ground Truth导致测出的召回率毫无意义。建议从Big-ANN-Benchmarks官网提供的统一链接下载全套数据。3.4 构建十亿级磁盘索引这是最耗时的一步。对于SIFT1B我们需要约500GB的临时内存和近1TB的SSD空间。# 在拥有大容量内存和SSD的机器上执行 # 参数解释 # uint8: 数据类型SIFT是uint8 # sift1b.bin: 输入数据文件 # sift1b_index: 索引文件前缀最终会生成 sift1b_index_disk.index 等 # 128: R参数最大出度 # 200: L参数构建时的候选池大小 # 32: PQ_bytes乘积量化字节数影响精度和索引大小 # 500: M_GB构建过程最大内存使用单位GB # 112: 使用的线程数 # l2: 距离度量L2距离 # pq: 邻居列表编码类型乘积量化支持更新 ./build/tests/build_disk_index uint8 sift1b.bin sift1b_index 128 200 32 500 112 l2 pq这个过程可能会运行数小时到一整天具体取决于你的CPU和SSD速度。控制台会输出进度信息。关键的参数是R、L和PQ_bytesR (Max out-degree): 控制图的连通性。越大图越稠密搜索路径更短但索引文件也更大I/O量增加。对于十亿数据128是一个经验值。L (Candidate list size): 构建图时每一步考虑的候选节点数。越大构建的图质量越高但构建时间越长。PQ_bytes: 这是PipeANN节省空间的秘诀。它将原始的128维uint8向量压缩到32字节。这会引入误差但通过精心设计的检索算法依然能保证高召回率。如果发现召回率不足可以尝试增加到48或64。3.5 构建内存入口图可选但推荐为了加速搜索PipeANN支持构建一个小的、常驻内存的“入口图”。这个图是原始大图的一个采样子图用于快速找到搜索的起始点。# 首先从数据集中随机采样1%的点 ./build/tests/utils/gen_random_slice uint8 sift1b.bin sift1b_index_SAMPLE_RATE_0.01 0.01 # 这会生成两个文件sift1b_index_SAMPLE_RATE_0.01_data.bin 和 sift1b_index_SAMPLE_RATE_0.01_ids.bin # 然后基于这1%的采样点构建内存图 ./build/tests/build_memory_index uint8 sift1b_index_SAMPLE_RATE_0.01_data.bin \ sift1b_index_SAMPLE_RATE_0.01_ids.bin sift1b_index_mem.index 32 64 1.2 $(nproc) l2这个内存索引很小对于十亿数据大约几百MB但能显著减少搜索时需要访问的磁盘节点数从而降低延迟。3.6 执行搜索测试现在我们可以用查询集来测试索引的性能了。# 参数解释 # uint8: 数据类型 # sift1b_index: 索引前缀 # 1: 搜索线程数单线程测延迟 # 32: Beam width搜索宽度影响搜索质量 # query.bin: 查询集文件 # gt_1b.bin: Ground truth文件 # 10: 返回的最近邻数量Top-K # l2: 距离度量 # pq: 邻居列表编码类型 # 2: 搜索模式2代表PipeANN的PipeSearch算法 # 10: 内存索引的搜索列表大小L_mem如果为0则不使用内存索引 # 10 20 30 40: 要测试的磁盘搜索列表大小L_disk序列 ./build/tests/search_disk_index uint8 sift1b_index 1 32 query.bin gt_1b.bin 10 l2 pq 2 10 10 20 30 40运行后你会看到类似下面的输出表格L I/O Width QPS Mean Lat P99 Lat Mean Hops Mean IOs Recall10 10 32 1952.03 490.99 3346.00 0.00 22.28 67.11 20 32 1717.53 547.84 1093.00 0.00 31.11 84.53 30 32 1538.67 608.31 1231.00 0.00 41.02 91.04 40 32 1420.46 655.24 1270.00 0.00 52.50 94.23解读结果L: 磁盘搜索列表大小。越大搜索越精细召回率越高但延迟也增加。QPS: 每秒查询数。单线程下能达到近2000 QPS性能可观。Mean Lat: 平均延迟微秒。L40时约为0.66毫秒达到了亚毫秒级的目标。P99 Lat: 99分位延迟。这比平均延迟更重要它反映了长尾延迟。L40时约为1.27毫秒表现稳定。Recall10: 召回率。L40时达到94.23%对于十亿规模来说是非常好的结果。Mean IOs: 平均每次查询的I/O次数。这是PipeANN效率的直观体现L40时仅需约52次I/O。你可以调整L的值在延迟和召回率之间做权衡。对于大多数应用L在30-50之间能取得很好的平衡。4. 高级特性解析动态更新与过滤搜索PipeANN不仅仅是一个静态索引它还支持动态更新增删和复杂的过滤搜索这在实际系统中至关重要。4.1 向量更新OdinANN的直接插入算法传统的磁盘图索引如DiskANN更新成本极高通常需要重建整个图或大片区域。PipeANN集成了其姊妹篇OdinANN的算法支持高效的直接插入和删除。核心思想当新向量插入时算法会为其在图中找到一个合适的局部位置进行连接并最小化对已有图结构的扰动。它通过一个巧妙的“代理节点”机制和局部图重建来实现确保插入操作不会导致整体搜索性能的剧烈波动论文中显示波动仅在1.07倍左右。启用更新功能在编译时你需要确保CMakeLists.txt中没有定义-DREAD_ONLY_TESTS和-DNO_MAPPING标志。然后使用对应的测试程序。# 1. 为数据生成标签文件建立向量ID到内部标签的映射 ./build/tests/utils/gen_tags uint8 data_200M.bin my_index_prefix # 2. 运行插入-搜索混合负载测试 # 此测试会模拟一边插入新向量一边进行搜索查询的场景 ./build/tests/test_insert_search uint8 data_200M.bin 128 1000000 100 10 32 2 \ my_index_prefix query.bin /path/to/ground_truth_dir 0 10 4 32 10 20 30 40 50重要警告崩溃一致性PipeANN的更新操作不是崩溃一致的。这意味着如果在插入或删除过程中系统崩溃索引文件可能会损坏。生产环境使用更新功能时必须考虑这一点。论文中提到可以通过定期执行final_merge操作来创建一个持久化的、一致的索引快照。在关键业务中更稳妥的做法是在一个临时副本上执行更新完成后原子性地替换线上索引。4.2 过滤搜索支持任意元数据过滤在许多实际场景中我们不仅需要找相似的向量还需要满足某些元数据条件例如“寻找与这张图片相似且发布时间在2023年之后、来自欧洲用户的图片”。PipeANN通过Label和Selector抽象优雅地支持了这一点。工作原理标签附着在构建索引时每个向量可以关联一个或多个标签例如分类ID、数值范围、位图等。这些标签数据被直接存储在磁盘上该向量节点的记录末尾。选择器定义定义一个Selector选择器它的核心是一个is_member(query_label, target_label, target_id)函数。对于每个在搜索路径上访问到的节点都会调用此函数判断其标签是否满足查询条件。搜索时过滤在标准的图搜索过程中只有通过Selector检查的节点才会被放入候选队列并进行距离计算。不满足条件的节点会被直接跳过。使用示例假设我们有一个图片数据集每个图片有多个分类标签如“猫”、“户外”、“夜景”我们想搜索“猫”的相似图片。# 1. 构建带标签的索引 # 假设 labels.spmat 是一个稀疏矩阵格式的标签文件 ./build/tests/build_disk_index uint8 image_vectors.bin image_index 96 128 32 256 112 l2 pq spmat labels.spmat # 2. 执行过滤搜索 # 假设 query_labels.spmat 包含了每个查询对应的标签例如每个查询只想找“猫” # subset 选择器表示目标节点的标签必须是查询标签的子集 ./build/tests/search_disk_index_filtered uint8 image_index 16 32 query.bin gt.bin 10 l2 pq \ subset query_labels.spmat 0 0 20 50 100 200这个功能非常强大它将向量检索与结构化过滤在索引层深度融合避免了先检索再过滤带来的性能损失和精度下降。5. 性能调优与故障排查指南在实际部署中你可能会遇到性能未达预期或各种运行时错误。以下是我总结的一些关键调优点和排查步骤。5.1 性能调优参数表参数类别参数名影响调优建议索引构建R(Max out-degree)图密度影响搜索路径长度和索引大小。十亿级128百万级64-96。越大召回越高但IO增多。L(Build candidate list)图构建质量影响最终索引的搜索精度。通常设为R的1.5-2倍。十亿级200。PQ_bytes向量压缩率影响索引大小和精度。默认32。召回率不足时增至48或64。内存紧张时可减至16。搜索性能L_disk(Search list size)搜索精细度平衡延迟与召回。最重要的参数。从20开始测试逐步增加直到召回率满足要求。通常30-50是甜点区。beam_width搜索宽度影响搜索的贪婪程度。默认32即可。在复杂图或高召回要求下可增至64。search_mode搜索算法。务必使用模式2 (PipeSearch)以获得最佳性能。系统资源线程数 (threads)并行度。构建时可用满核心数。搜索时QPS随线程数线性增长但延迟可能略增。根据业务需求高吞吐/低延迟调整。I/O引擎底层I/O接口。首选io_uring。确保内核5.1并在编译时正确链接liburing。硬件相关SSD性能直接影响IOPS和延迟。使用高性能NVMe SSD如Intel P5800X, Samsung PM9A3。避免使用SATA SSD或HDD。内存容量影响构建和缓存。构建十亿索引需~500GB。纯搜索需~40GB。确保有足够空闲内存避免Swap。5.2 常见问题与解决方案问题1构建索引时因内存不足被杀死OOM Killer。现象build_disk_index进程突然消失dmesg显示Out of memory: Killed process ...。原因参数M_GB设置过大超过了系统可用物理内存。解决使用free -h确认可用内存。将M_GB设置为略小于可用内存的值例如留出10-20GB给系统。如果数据集极大考虑使用PiPNN构建算法build_pipnn_index它对内存峰值的要求可能不同。问题2搜索召回率Recall远低于论文报告值。现象在相同L参数下自己测试的召回率比论文中低很多。排查步骤检查数据一致性确认查询集、Ground Truth与基础数据集完全匹配。这是最常见的原因。检查距离度量确认构建索引 (build_disk_index) 和搜索 (search_disk_index) 时使用的metric参数一致都是l2或都是ip。调整PQ_bytes如果向量本身信息密度高如DEEP的96维浮点数32字节压缩可能损失过多信息。尝试将PQ_bytes增加到48或64重新构建索引。增加L_disk这是最直接的提升召回率的方法但会增加延迟。逐步提高L_disk如40, 60, 80观察召回率变化曲线。检查索引构建质量确保构建时的R和L参数足够大。对于十亿数据R128, L200是推荐的起点。问题3搜索延迟Latency过高达不到亚毫秒级。现象平均延迟在几毫秒甚至更高。排查步骤确认使用io_uring运行搜索程序时观察初始日志。如果看到Using libaio for I/O说明io_uring未启用。重新检查编译环境和系统内核。检查SSD状态使用fio或ioping测试SSD的4KB随机读延迟。如果延迟高于100微秒可能是SSD性能瓶颈或负载过高。降低L_disk这是降低延迟最有效的方法但会牺牲召回率。需要在业务可接受的召回率下限内寻找最小的L_disk。检查系统负载使用iostat -x 1查看%util和await。如果SSD利用率持续接近100%说明存在其他I/O密集型任务干扰。使用内存入口图确保在搜索命令中设置了mem_L参数如10这能有效减少初始搜索阶段的磁盘I/O。问题4编译错误找不到liburing或MKL。解决对于liburing确保已成功编译third_party/liburing并且其头文件liburing.h和库文件liburing.a或.so在标准搜索路径或CMake指定的路径中。对于MKL如果不想安装庞大的Intel MKL可以修改CMakeLists.txt将find_package(MKL)注释掉并链接OpenBLAS。需要提前安装libopenblas-dev。问题5更新操作后索引文件损坏或无法加载。原因如前所述更新操作非崩溃一致。解决定期快照在业务低峰期调用索引的save方法Python接口或使用工具创建一致性快照。写时复制在独立的数据副本上进行更新操作。完成一批更新后将旧索引原子性地替换为新索引。这需要额外的存储空间和更复杂的版本管理。日志与恢复对于关键系统可以考虑在应用层记录更新操作日志。如果索引损坏可以从上一个完好快照开始重放日志进行恢复。PipeANN本身不提供此机制需要自行实现。经过以上步骤的调优和排查你应该能让PipeANN在你的硬件和数据上发挥出接近其论文宣称的性能。这个系统的优势在于它提供了一套从构建、搜索到更新的完整工具链并且代码结构清晰便于深入研究和定制化开发。对于需要处理超大规模向量数据同时又对成本和延迟有严格要求的团队来说PipeANN无疑是一个值得投入精力研究和使用的强大工具。