聚类方法的回归：用 Helmsman 构建低成本、高性能的大规模近似最近邻搜索系统（OSDI 2026）

原题：The Clustering Strikes Back: Building Cost-Effective and High-Performance ANNS at Scale with Helmsman (Operational Systems)

一句话总结：面对大 top-k 检索中图遍历的串行 SSD 访问，Helmsman 将聚类索引的无依赖批量读取与 SPDK 存储栈、搜索前学习剪枝及 GPU/CPU 分工构建结合；在百亿向量实验中，单台 96 核服务器以 160–330 GB DRAM 达到十分片内存 HNSW 吞吐的约 47%–85%，并满足相同平均延迟 SLA。

问题与动机

小红书的搜索、推荐和广告把近似最近邻搜索（ANNS）用作多阶段排序的候选生成器。搜索与广告请求的 top-k 可达 100–3,000，推荐可达 1,000，因为后续还要过滤和重排；这些业务要求约 5–10 ms 的平均检索延迟。仅用小 top-k、高召回率基准衡量索引，不能代表这里的部署目标（§2、§6.2）。

原有 HNSW 部署将向量和图全部放进 DRAM。容量需求使其采购的内存远超支撑实际吞吐所需：生产业务仅需要内存部署最大吞吐的约 32%–43%，其余资源主要用于容纳索引（图 3）。SSD 能降低容量成本，但 DiskANN、Starling 和 PipeANN 的遍历存在前后依赖，大 top-k 拉长搜索路径，难以利用多盘带宽。

SPANN 的聚类索引把质心图留在 DRAM，将簇内向量列表放在 SSD；找到候选簇后可以一次发出多个独立读取。论文围绕这种访问模式解决三项部署障碍：内核 I/O 开销、固定剪枝带来的扫描浪费，以及 CPU 单机构建无法跟上嵌入模型更新速度。目标是以较低资源成本满足业务吞吐和延迟，而非在每个数据集上超过内存 HNSW。

关键观察 / 隐含假设

观察 1：大 top-k 使串行访问延迟比读取总量更具决定性。 在 SIFT100M、90% 召回率、12 块 Gen5 SSD 上，PipeANN 即便改善单查询并行度，满足延迟 SLA 时吞吐仍比 HNSW 低 10–25 倍；SPANN 随 SSD 数量增加则接近线性扩展（图 4、图 6）。
- 依赖假设：业务确实需要较大候选池，且设备有足够并行带宽承受更多批量读取。
- 可能失效场景：盘数少、成本主要来自读取带宽，或查询集中于小 top-k 时，图索引减少访问量的价值可能上升。
观察 2：现有聚类索引受软件栈和扫描范围双重限制。 SPANN 仅使用约 26%–59% 的阵列带宽，固定距离阈值对不同查询既可能过量扫描，也可能漏掉达到目标召回所需的簇（图 7）。
- 依赖假设：查询向量、top-k 和质心距离能预测所需扫描量，而且近期日志与随后流量足够接近。
- 可能失效场景：热点迁移、新查询或嵌入模型切换会使学习模型低估范围；已有召回实验不构成逐请求保证。
观察 3：GPU 的聚类收益取决于任务粒度。 大规模距离计算适合 GPU，但少于约十万条 128 维向量的小任务可能被主机与设备间搬运开销主导（图 13）。
- 依赖假设：构建流程能分成 GPU 粗聚类与 CPU 细分任务，且大索引可借用低峰期空闲 CPU。
- 可能失效场景：缺乏夜间空闲资源、在线流量持续抢占或分布式存储拥塞时，构建时限会变长。
假设 4：允许以资源节省换取一定吞吐下降和周期重建。 搜索阶段主要追求足够大的候选集合，常用约 90% 召回率；这不是高精度检索的普遍要求。该假设有生产经验支撑，但论文未给出下游排序质量或收入指标的对照实验。

核心方法

面向固定簇读取的用户态存储

Helmsman 保留 SPANN 的质心图与簇列表组织，使用 SPDK 绕过内核 I/O 栈。每个簇占据一块 SSD 上连续的逻辑块，一次 NVMe 命令即可读取；不同簇分布在阵列各盘。元数据、质心索引和剪枝模型仍以普通文件保存，在线常驻 DRAM（图 8、图 10）。

搜索线程批量提交 NVMe 命令并轮询完成队列，每盘每批只通知一次设备，避免逐命令敲门铃。簇经大小约束和边界向量补充后采用固定读取尺寸，例如 SIFT 中的 12 KB。存储分配器据此用固定大小块区管理空间，例如 64 MB 块区，再在其中分配簇列表。这种专用布局减少文件系统和通用分配器开销，但要求系统自行管理原始设备、空间回收与映射。

在读取前预测搜索范围

分级学习式搜索剪枝（LLSP）使用梯度提升决策树，分两次预测。路由模型从查询向量和 top-k 选择扫描范围档位，例如 nprobe=256；系统在质心图中找到相应数量的候选质心后，再将质心距离、相对距离比例等特征交给该档位的剪枝模型，缩小最终读取范围（图 11）。

两次预测都不依赖 SSD 上向量的中间搜索结果，因此最后仍能批量提交读取。相比 Quake 等逐簇检查停止条件的思路，这牺牲了搜索途中的反馈，保住了 I/O 并行性。训练从近期日志采样，使用大扫描范围、无剪枝搜索，例如 nprobe=4096，生成近似监督标签。该标签并非穷举得到的精确最近邻；路由结果也只是模型预测的上界，不是数学上的召回安全边界（§4.3）。

异构、可抢占的索引构建

GPU 先生成粗粒度质心；CPU 再完成小簇的细分、平衡与边界向量复制。常见的亿级以内数据集直接使用 GPU 服务器的本地 CPU，避免额外调度和网络开销。百亿级搜索索引则将细分任务分派给弹性 CPU 池，最后由多核服务器合并簇、构建质心图并训练剪枝模型（图 12）。

在线业务始终优先。资源冲突时构建任务被终止并重试，重试超过阈值后换节点，并暂时将不稳定节点移出资源池。分布式文件系统保存原始数据、中间结果和最终索引；论文没有将这些外部资源视为免费的独立计算能力，实际构建时限仍依赖可借用规模。

设计取舍

更多 SSD 空间换取可并行读取：边界向量复制及固定簇布局降低漏召回和不均衡风险；实验将复制因子设为 4，质心约占总规模的 8%，以匹配 DRAM 与 SSD 容量比例。
预测而非逐步反馈：LLSP 可一次发出读取，但错误预测可能损害召回；系统没有提供对每个查询都成立的召回下界。
专用设备管理换取软件开销下降：用户态直接访问适合批量读，轮询的空载 CPU 成本、设备共享隔离和故障恢复则需要额外工程支撑。
周期重建换取在线主索引简单性：部署使用 SSD 主索引、内存增量索引和删除位图；查询合并两路结果并过滤删除项。它支持新鲜数据，但不消除内存占用和重建成本（§6.2）。

实验与结果

实验采用 SIFT 及五类生产数据，维度为 64–1,024，规模为 400 万至 100 亿向量，距离函数统一为 L2。SIFT10B 由 SIFT1B 复制十次得到。混合存储实验机配置为 96 核 AMD EPYC 9654、12×96 GB DDR5 和 12×1.92 TB Gen5 SSD；构建加速使用另一套 CPU/GPU 资源（表 2、§5.1）。

查询性能：SIFT100M、90% 召回率、top-k 从 10 增至 3,000 时，Helmsman 平均延迟保持在 10 ms 内，P99.9 低于 20 ms。作者汇总相对混合存储基线吞吐为 2–16 倍；不能把该范围理解成每个数据集都达到最高倍数（图 14、§5）。
对比内存 HNSW：在 2,000 万至 5 亿规模下，Helmsman 吞吐约为同一 96 核节点 HNSW 的 25%–70%；百亿级实验则以单机 160–330 GB DRAM 达到十台合计 320 核、2.5 TB DRAM 的 HNSW 部署吞吐的约 47%–85%，满足平均延迟 SLA（图 17）。
存储带宽：RedSrch0.5B 上，Helmsman 使用约 85% Gen4、70% Gen5 阵列带宽，图索引低于 20%。从 Gen4 升至 Gen5，在 64/128 维负载上吞吐增约 55%，1,024 维负载增约 87%（图 18）。
剪枝消融：相对不剪枝，LLSP 吞吐为 1.1–1.6 倍；相对固定剪枝提高 5%–25%。同为约 90% 平均召回时，超过 80% 查询达到目标召回，固定策略则有超过 40% 查询不达标。生产数据按连续日志前 10 万条训练、后 1 万条测试，主要验证短时间窗口内泛化（图 19、图 20、§5.4）。
构建速度：亿级索引在 192 核 CPU 上需约 9–12 小时，加入 4 块 NVIDIA L20 后缩短至一小时内。百亿级任务将弹性 CPU 从 1,024 核增至约一万核，端到端耗时从超过 16 小时降至约 4–7 小时，具体随数据集变化（图 21）。
成本与部署：RedSrch10B 的表 5 给出 HNSW 23 KQPS、2.5 TB DRAM，与 Helmsman 19 KQPS、0.16 TB DRAM 加 3.2 TB SSD 的对比；按存储采购价计算为 1.2 对 10 QPS/美元，约 8.3 倍。§6.1 报告约 40 台全闪存服务器已接替此前约 35,000 核、0.35 PB DRAM 承担的业务；这是已迁移业务的部署报告，不代表平台全量迁移完成。

论断—证据表

论断	证据	评测边界	置信度
大 top-k 的聚类读取能更好利用多盘 SSD	图 4、图 6、图 14：图遍历受串行路径限制，聚类索引随盘数扩展	SIFT100M、90% 召回、最多 12 块 Gen5；不能推广到所有索引和设备	强
用户态存储支持带宽扩展	图 9、图 18：Gen4/Gen5 利用率约 85%/70%	I/O 微基准加端到端测量；主存带宽仍限制最终利用率	强
搜索前剪枝改善效率与召回分布	图 19、图 20：比固定策略吞吐高 5%–25%，超过 80% 查询达到目标召回	近期日志训练测试；无逐查询保证和长期漂移测量	中
异构构建能支持小时级重建	图 21：亿级少于一小时，百亿级约 4–7 小时	4 块 L20 的单机实验与约一万弹性 CPU 核的大规模实验，资源口径不同	强
降低存储成本而仍满足 SLA	图 17、表 5、§6.1：百亿索引约 8.3 倍存储成本效率，已有生产迁移	存储价格不含完整服务器、能耗、网络与运维成本	中

批判性分析

论证链条

从大 top-k 引出的长串行路径，到聚类批量读取，再到用户态栈与搜索前剪枝，设计都回应了测量中的障碍。与 HNSW 的对比也明确保留了吞吐差距：内存系统有容量导致的过度配置，才允许用较低峰值性能换取整体节省。论文支持的是这一业务条件下的替代方案，而非聚类在任何检索场景都优于图索引。

假设压力测试

LLSP 的训练标签本身近似，且路由模型会先限制可见的质心范围。若新流量需要更大范围，后续剪枝没有利用 SSD 搜索结果纠错的步骤。短窗口实验展示了更好的召回分布，但仍有查询不达标；应进一步测试冷启动查询、时间漂移及嵌入模型切换后的召回下分位数。

SSD 热点已经是作者报告的失效实例：部分推荐索引在带宽不足 20% 时无法继续扩展，原因是突发查询访问相同逻辑块，引起芯片级冲突。复制热点簇列表后吞吐提高 1.5–2 倍（§6.2）。因此，容量、总带宽和全局 CPU 利用率不足以解释服务上限。

实验可信度

论文同时包含公开数据、多个维度的生产数据、不同 top-k、P99.9、硬件代际和剪枝消融，覆盖了主要工程主张。但 SIFT10B 的十倍复制主要检验容量与构建扩展，不能单独证明十倍独立数据的分布难度。混合图索引、聚类索引与内存 HNSW 的内存预算及分片结构不同，适合比较部署方案，不能解释为等资源算法排名。剪枝有直接消融，存储栈内部布局、批量门铃与分配器各自贡献则未被完整拆开。

成本数字存在原文算术不一致。 表 4 的 HNSW 与 Helmsman 分别为 51、250 QPS/美元，按表内数值约为 4.9 倍；§5.6 写作 5.4 倍。本文采用可复算的约 4.9 倍，不将差异当作新实验结果。表 4、表 5 的效率分母主要是 DRAM 和 SSD 采购价，不能直接作为完整总拥有成本。表 6 另以云实例归一化价格讨论构建，但仍未覆盖整个平台的年度运维支出。

系统性缺陷

§6.2 说明 12 块 Gen5 SSD 的约 140 GB/s 外部带宽只能利用约 70%，因为约 300–350 GB/s 有效主存带宽还要承受 SSD 写入 DRAM、CPU 重读和质心搜索。增加到 20 块盘的收益有限，说明继续扩展已转为内存数据搬运问题。

论文未系统评估原始设备故障恢复、索引与模型发布的原子性、多租户资源隔离，以及构建频繁被抢占时的完成时间分布。内存增量索引随重建延迟增长后，会如何影响尾延迟和内存预算，也没有单独给出压力实验。这些缺口不否定现有部署结果，但限制了迁移到不同运维条件的可预测性。

局限与后续工作

召回保障：按小时、天和模型版本切分测试集，记录每个 top-k 桶的召回低分位数与 SLA 违规率；比较范围预测校准、保守回退和二次读取的代价。
带宽扩展：测量每查询 SSD 字节数、DRAM 读写量、CPU 停顿和 P99.9，定位 12 盘到 20 盘收益下降的来源；再验证 I/O 直达缓存或 GPU 数据通路能否减少重复搬运。
在线更新：在约 25–30 KQPS 检索与 25–30 KOPS 更新并存时，测量增量索引增长、删除过滤成本和重建完成时间，而不仅报告静态主索引性能。
资源与成本边界：控制弹性 CPU 可用比例和抢占率，报告构建时间分位数；计入 GPU、CPU、网络、SSD 磨损、冗余副本与恢复资源后，重算每百万次查询的成本。

Awesome System Papers Wiki

探索

paper-osdi26-huang-yuchen