Last updated: Monday 07 September 2026 @ 20:44:27

The Clustering Strikes Back: Building Cost-Effective and High-Performance ANNS at Scale with Helmsman

Frontmatter

aigc: true

这篇论文的核心不是提出一种全新的 ANN 索引，而是提出一个很明确的系统观点：

在现代高带宽 NVMe SSD 上，继续把“图索引”搬到 SSD 上可能走错了方向；对于大 top-k 的工业负载，传统上被认为吞吐不足的 clustering-based ANNS，反而更适合 SSD。

论文据此构建了 HELMSMAN：以 SPANN 一类的聚类索引为基础，通过 SPDK 用户态 I/O + Learned Pruning + GPU/分布式构建，试图用一台 all-flash 机器取代大量 DRAM HNSW 机器。

1. 先把论文放到 ANNS 技术谱系里

你可以先这样理解现在几条路线：

路线	典型工作	数据主要在哪里	核心搜索模式
内存图	HNSW	DRAM	图遍历
SSD 图	DiskANN / Starling / PipeANN	DRAM + SSD	图遍历 + SSD fetch
聚类	IVF / SPANN	centroid 在 DRAM，posting list 在 SSD	找 cluster → 批量读取
本文	HELMSMAN	DRAM + 多块 NVMe	SPANN-like clustering + 极致 SSD 优化

所以这篇论文真正挑战的是过去一个很常见的认知：

图索引随机访问少，所以图索引更适合 SSD。

HELMSMAN 说：

不一定。

因为现代 SSD 的问题已经从：

“带宽太低”

逐渐转变为：

“带宽其实非常高，但你能不能把它喂满？”

论文给出的例子是：

12-channel DDR5：约 456 GB/s；
12 × Gen5 SSD：约 144 GB/s；
已经达到 DRAM 带宽约 32%；
SSD 单位容量价格却只有 DRAM 的约 1/40。

这就改变了 ANNS 的设计权衡。

2. 为什么他们要放弃 HNSW？

小红书原来在线业务大量使用 in-DRAM HNSW。

原因很简单：

Search：约 10 ms SLA；
Recommendation / Ads：约 5 ms SLA；
QPS 达数十万到数百万；
top-k 还非常大，经常是 100～3000。

问题在于数据规模已经很夸张：

单 search 就可能有约 20B vectors；
全部 ANNS infrastructure 已经达到 PB 级 DRAM。

而论文观察到一个有意思的问题：

HNSW 集群并不是因为吞吐需要那么多 DRAM，而是因为必须把整个 index 放进内存。

实际只用了大约 32–43% 的最大吞吐能力。

剩下的大量机器，本质上是：

为了容量，而不是为了算力。

于是他们就想：

能不能把绝大多数 vectors/index 放到便宜 SSD？

3. 为什么 DiskANN / Starling / PipeANN 不行？

这是理解整篇论文最关键的一段。

他们测试了：

DiskANN
Starling
PipeANN

结果图 4 显示：

DiskANN / Starling latency 很难进入 5–10 ms SLA；
PipeANN 延迟好一些；
但吞吐和 HNSW 仍差 10–25×。

论文认为根因不是：

SSD 带宽不够。

而是：

graph traversal 本身具有串行 dependency。

例如：

读 node A
   ↓
知道下一步去 B
   ↓
读 node B
   ↓
知道下一步去 C
   ↓
读 node C

也就是：

I/Oi+1

依赖

I/Oi

的结果。

因此即使你有：

SSD bandwidth = 144 GB/s

也不意味着你能把 144 GB/s 真正用起来。

4. 这里和 PipeANN 的关系特别重要

从技术思想上看，PipeANN 和 HELMSMAN 的分歧非常鲜明。

PipeANN 的思路

PipeANN 基本接受：

graph traversal 是 dependency-chain。

然后尝试：

把不同阶段 pipeline 起来，把 SSD latency 藏起来。

也就是：

graph search
   ↓
SSD I/O
   ↓
distance computation

通过 pipeline overlap。

HELMSMAN 的思路

HELMSMAN 更激进：

既然 dependency-chain 是图算法本身造成的，那为什么还要坚持 disk graph？

直接换成 clustering：

query
 ↓
一次找到 nprobe 个 clusters
 ↓
 ┌──────┬──────┬──────┬──────┐
 ↓      ↓      ↓      ↓
 C1     C2     C3     C4
 ↓      ↓      ↓      ↓
SSD    SSD    SSD    SSD

这些 I/O：

基本彼此 independent。

所以可以一口气批量发出去。

论文图 5 把这个称作：

Batched and Dependency-Free I/O

这实际上是全文最核心的系统 insight。

5. 为什么以前 clustering 不行，现在又行了？

HELMSMAN 标题叫：

The Clustering Strikes Back

就是这个意思。

SPANN 这样的设计本来就存在：

                DRAM
                 │
          centroid graph
                 │
query ──→ nearest centroids
                 │
       nprobe clusters
          ↓ ↓ ↓ ↓ ↓
        SSD posting lists
                 │
       distance calculation
                 │
              top-k

过去认为它的问题是：

一次 query 要扫描很多 vector，所以 I/O 太多。

但 HELMSMAN 认为现代 NVMe 改变了这个条件：

现在 SSD bandwidth 足够大，扫描多不一定是致命问题。

真正关键变成：

这些 I/O 是否可以并行发出去。

于是论文 Figure 6 有一个非常重要的实验：

随着 SSD：

1→2→4→8→12

SPANN throughput 基本近似线性增长。

12 块 SSD：

≈12×

说明它已经逐渐变成一个：

bandwidth-scalable workload

而不是 latency-bound workload。

6. 但原生 SPANN 还有三个问题

所以 HELMSMAN 并不是“直接拿 SPANN”。

论文找到三个 bottleneck：

问题 1：I/O 软件栈太慢

SPANN：

Application
 ↓
syscall
 ↓
Filesystem
 ↓
Block layer
 ↓
Device Mapper
 ↓
NVMe driver
 ↓
SSD

在论文测试中，传统 Linux I/O 软件栈：

最多占整个 I/O path 约 58%。

甚至比真正访问 SSD 的时间还高。

问题 2：nprobe 选得不好

SPANN 使用类似：

Dist(q,cj)≤(1+ϵ)Dist(q,c1)

这种 fixed pruning。

问题在于：

easy query：
实际需要 100 clusters
却读了 300

hard query：
实际需要 500
却只读了 300

前者浪费 throughput，后者降低 recall。

问题 3：建索引太慢

SPANN 的 clustering：

hierarchical k-means
balancing
boundary replication
centroid graph

主要依赖 CPU。

到了 10B 规模可能需要：

数十小时甚至几天。

而小红书的 embedding model 会频繁更新：

recommendation：一天可能重建成千上万次 index；
search：希望 daily rebuild。

所以这不够快。

7. HELMSMAN = 三个核心模块

因此整篇论文其实非常容易记：

HELMSMAN=SPDK+LLSP+GPU/ElasticBuild

也就是 Figure 8 的整体架构。

8. 第一项技术：ANNS-oriented Storage Stack

这是我认为论文里最“systems”的部分。

他们直接使用：

SPDK

绕过 Linux kernel。

变成：

Search Thread
     │
     ↓
NVMe Submission Queue
     │
     ↓
SSD hardware
     │
     ↓
NVMe Completion Queue

应用直接：

submit NVMe command；
poll completion。

数据怎么放？

他们把数据分两类。

Metadata

比如：

index name
centroid graph
pruning model
cluster → SSD/LBA mapping

比较小。

正常放 filesystem。

Posting Lists

这是热点路径：

直接写 raw NVMe logical blocks。

例如：

SSD 0
cluster 0 → LBA 100~102
cluster 3 → LBA 103~105

SSD 1
cluster 1 → LBA 100~102
cluster 5 → LBA 103~105

每个 cluster：

连续布局；
不跨 SSD；
一次 I/O 读完。

Figure 10 就是在画这个结构。

9. 为什么这种布局特别适合 SPANN？

因为 SPANN 本身有一个很方便的性质：

cluster 会被 balance 到大致固定大小。

例如论文举 SIFT：

cluster size ≈ 12 KB

所以：

每个 I/O ≈ fixed-size

这对 NVMe 非常友好：

地址容易算；
allocator 简单；
每个 cluster 一条 command；
batch submission 很方便。

他们甚至自己做了：

64 MB chunk-based allocator。

10. 一个很细但很重要的优化：Doorbell batching

正常情况下：

command 1 → doorbell
command 2 → doorbell
command 3 → doorbell
...

HELMSMAN：

enqueue cmd1
enqueue cmd2
enqueue cmd3
...
        ↓
    knock once

也就是 Figure 10 中：

Batched Enqueue → Single Knock

这样减少 PCIe MMIO / doorbell 开销。

这是典型的 storage-system 优化，而不是 ANN 算法优化。

11. 第二项技术：Leveling-Learned Search Pruning

这部分名字比较复杂，实际上思想非常直观。

它要解决：

每条 query 到底应该读多少 clusters？

也就是预测：

nprobe

12. 为什么不能直接用 Early Termination？

已经有不少工作：

LAET
Quake
Auncel

可以：

scan cluster
↓
看看结果够不够
↓
不够
↓
scan next

但 HELMSMAN 明确说：

这对 SSD clustering 是不好的。

因为会重新引入 dependency：

I/O
 ↓
compute
 ↓
decision
 ↓
I/O
 ↓
compute
 ↓
decision

于是又破坏了：

batched dependency-free I/O。

这个设计约束很关键。

HELMSMAN 要做到：

I/O 发出去之前就决定好到底读哪些 cluster。

13. LLSP 实际上是两级预测

Figure 11 非常值得看。

第一层：Router model

输入：

(query, top−k)

预测一个粗粒度 level。

例如：

L0 = 64
L1 = 128
L2 = 192
L3 = 256
...
L15 = 1024

假设预测：

L3

意味着：

nprobe≤256

14. 第二层：Pruning Model

系统先找到 top-256 centroids。

然后构造特征：

query vector
top-k

d0
d1/d0
d2/d0
...
d255/d0

也就是 centroid-distance distribution。

然后对应的：

L3 pruning model

进一步预测：

nprobe = 193

最终：

一次性 batch read 193 个 clusters。

所以：

query
 ↓
Router
 ↓
256 upper bound
 ↓
centroid search
 ↓
distance-distribution features
 ↓
pruning model
 ↓
193 clusters
 ↓
一次性批量 I/O

15. 为什么还要两级，而不是直接预测 nprobe？

这里虽然论文没有把它形式化成理论，但设计逻辑比较清楚。

Router 解决的是：

query 大概有多难。

Pruner 解决：

在这个 difficulty range 内，具体应该读多少。

这样：

模型更容易训练；
每个 level 范围有限；
feature dimension 也更受控制。

他们用的是：

GBDT / LightGBM-style model。

而不是神经网络。

原因也很现实：

inference：约 10–30 µs；
model：数百 KB；
training：百万样本约分钟级。

所以非常适合在线 path。

16. LLSP 是怎么训练的？

这里值得稍微认真理解。

他们并没有真的 brute-force 计算 ground truth。

而是先：

nprobe=4096

跑一次大范围搜索，把它当近似 reference。

然后对每个 query：

Router label

找：

最小的 level，使得 recall ≥ target recall。

例如：

target = 90%。

于是 label：

L3 = 256

Pruner label

再从 256 开始往下降：

256 → 91.2%
240 → 91.1%
220 → 90.7%
200 → 90.2%
193 → 90.0%
192 → 89.9%

于是：

label=193

模型学习的实际上就是：

满足 recall 约束的 minimum nprobe。

这是一种比较干净的 supervised formulation。

17. 第三项技术：GPU + Elastic Index Construction

HELMSMAN 的 offline build 也分三阶段。

Stage 1：GPU coarse clustering

使用 GPU 做 k-means。

论文当前实现基于：

Faiss。

但他们没有完全在 GPU 上完成所有 clustering。

原因是对于很小的 cluster：

GPU kernel + CPU↔GPU transfer 的 overhead 反而不划算。

所以只是 coarse clustering。

18. Stage 2：CPU fine clustering + padding

完成：

cluster balancing；
further split；
boundary duplication；
RNG checking。

这里分两种情况。

小规模

例如：

N<0.1B

直接使用 GPU server 的 local CPU。

这样避免：

network transfer；
distributed scheduling。

超大规模

比如 search 的 10B：

使用在线 CPU 集群在 off-peak 时段的闲置 CPU。

也就是所谓：

elastic CPU workers

例如晚上机器比较闲：

online serving CPU
        +
idle CPU cores
        ↓
index construction

如果在线流量突然来了：

offline build 会被 preempt。

所以在线 SLA 优先。

19. Stage 3：Final merge

最后多核 CPU server：

merge posting lists；
构建 centroid graph；
训练 pruning model；
写 metadata；
生成最终 deployable index。

因此完整 pipeline 是：

Raw Vectors
    │
    ▼
GPU coarse K-means
    │
    ▼
CPU fine split / balance
    │
    ▼
boundary padding
    │
    ▼
merge
    │
    ├─ posting lists
    ├─ centroid graph
    ├─ metadata
    └─ pruning models

20. 最重要的性能结果

论文报告的 headline 是：

相比现有 DRAM-SSD ANNS，HELMSMAN throughput 提升 2–16×。

并且在满足 latency SLA 时：

可以达到 in-DRAM HNSW 最高约 85% throughput。

不过这个 85% 要看具体场景。

21. 和 HNSW 的比较尤其值得注意

Figure 17。

对于较小 dataset：

20M ～ 0.5B

HNSW 可以放进同一台 96-core machine。

HELMSMAN 大约达到：

25%−70%

HNSW throughput。

所以：

HELMSMAN 本身并没有比 DRAM HNSW 快。

这个要非常明确。

但是到：

10B

HNSW 需要：

10 shards
320 CPU cores
2.5 TB DRAM

而 HELMSMAN：

1 machine
96 cores
160–330 GB DRAM
SSD

却可以达到：

47%−85%

distributed HNSW throughput。

这时候 economics 就完全不一样了。

22. SSD 利用率是论文非常关键的 evidence

Figure 18。

其他系统 SSD bandwidth utilization 大约：

graph systems    < 20%
SPANN            ~55%
HELMSMAN Gen4    ~85%
HELMSMAN Gen5    ~70%

而升级：

Gen4 → Gen5

之后：

DiskANN / Starling / PipeANN：只有 10–30% improvement；
SPANN：约 40%；
HELMSMAN：55–87%。

这实际上验证了他们最核心的论点：

HELMSMAN 已经更接近真正的 bandwidth-bound system。

23. Learned pruning 到底有没有用？

有，但没有 storage stack 那么革命性。

Figure 19：

相比完全不 pruning：

1.1−1.6×

throughput improvement。

相比 SPANN fixed pruning：

大约再提升 5–25%。

更有意思的是 recall stability。

固定 pruning 时：

超过 40% queries 可能没有达到目标 90% recall。

LLSP：

超过 80% queries 达到 target recall。

也就是说它优化的不只是平均 recall，而是：

per-query recall distribution。

24. Index build 性能

原始 CPU：

0.1B

需要：

约 9–12 小时。

4 × NVIDIA L20：

降到 1 小时以内。

10B：

借助大约：

1024→104

CPU cores 的 elastic scaling：

整体约 4–7 小时。

这个数字对他们 daily rebuild 的 production model 非常重要。

25. Cost 才是这篇论文最终真正想证明的东西

看 RedSrch10B。

HNSW

DRAM: 2.5 TB
Throughput: 23 KQPS
cost efficiency: 1.2 QPS/$

HELMSMAN

DRAM: 0.16 TB
SSD: 3.2 TB
Throughput: 19 KQPS
cost efficiency: 10 QPS/$

也就是：

8.3×

cost efficiency。

DRAM：

减少约 90%。

26. 更夸张的是 production deployment

论文声称当前已经：

大约 40 台 all-flash machines

承载了原来需要：

35,000 CPU cores
约 0.35 PB DRAM

的 online workload。

未来希望大规模替换原来的 in-DRAM deployment。

这也是这篇工作价值比较高的地方：

它不是只在 SIFT 上展示 benchmark，而是有真实 production deployment。

27. 这篇论文最值得你记住的技术观点

我会把全文浓缩成下面这个变化：

旧时代

SSD：

low latency? no
high bandwidth? no

所以目标：

尽量少做 I/O。

因此 graph ANNS 有优势。

现代 Gen5 SSD

SSD：

latency 仍然远差于 DRAM
但是 bandwidth 已经很高

于是新的目标变成：

不要串行地做少量 I/O，而要并行地做大量 I/O。

这恰好是：

Graph
serialized
dependent I/O

和

Clustering
batched
independent I/O

的根本区别。

所以 HELMSMAN 的真正 thesis 可以写成：

Modern SSD ANNS should optimize for bandwidth, not merely minimize I/O count

这比它具体用了 SPDK 或 GBDT 更值得记。

28. 我怎么看它的“创新量”

这篇论文不是一种新的 ANN algorithm。

如果只看算法：

clustering：SPANN 已有；
centroid graph：已有；
boundary replication：已有；
GBDT：已有；
GPU K-means：已有；
SPDK：已有。

它真正的贡献是：

重新判断硬件趋势，然后把这些已有组件按照新的 bottleneck 组合成一个 production system。

所以它是一篇很典型的 systems paper：

workload characterization
        ↓
发现旧 assumption 已失效
        ↓
重新选择 algorithmic primitive
        ↓
找 bottleneck
        ↓
storage / ML / GPU co-design
        ↓
production validation

29. 但论文也主动暴露了几个局限

这一节其实很值得读。

① SSD hotspot

某些 query 会集中访问相同 clusters。

即使 SSD 总 bandwidth 没满，也可能出现：

NAND die-level conflict。

他们最后通过：

给热门 cluster list 做少量 replica

把 throughput ceiling 提高了：

1.5−2×

这说明“dependency-free”不等于完全没有 storage contention。

② Memory bandwidth 又成了瓶颈

12 × Gen5：

≈140GB/s

但只能实际利用约 70%。

为什么？

因为 DRAM bandwidth 还要同时服务：

SSD → DRAM
DRAM → CPU
centroid search
distance calculation

最终 12-channel DDR5 的有效 300–350 GB/s 先满了。

所以他们测试 20 块 Gen5 SSD 时：

再加 SSD 已经没什么意义。

这其实暗示了下一代设计可能会转向：

SSD → GPU / cache direct path

论文也明确提到了这一方向。

③ Dynamic update 仍然没有解决

HELMSMAN 本质仍是：

rebuild-based system

目前更新方案：

main SSD index
        +
small in-memory HNSW/IVF delta index
        +
tombstone bitmap

query 同时搜索二者然后 merge。

所以如果你研究 dynamic ANNS：

这篇并没有真正解决 update。

论文自己也承认这是 future work。

30. 如果你只想记住一张图，就记 Figure 8

可以把整个系统记成：

                HELMSMAN
                   │
        ┌──────────┴──────────┐
        │                     │
      Online                Offline
        │                     │
        │               GPU coarse KMeans
        │                     │
Router model             Elastic CPU
        │                balance / padding
centroid graph                │
        │                 final merge
Pruning model                 │
        │               pruning training
        │
batch cluster IDs
        │
        ▼
      SPDK
        │
 ┌──────┼───────┐
SSD0   SSD1 ... SSD11
        │
        ▼
distance calculation
        │
        ▼
      top-k

这基本就是整篇论文。

最后给你一个一句话版本

HELMSMAN 不是在 SSD 上把 HNSW 做得更快，而是认为现代 SSD 已经使 ANNS 的最佳算法形态发生变化：与其费尽心思隐藏 graph traversal 的串行 SSD latency，不如回到 clustering，让大量 posting-list I/O 天然并行，再利用 SPDK 把 SSD bandwidth 真正吃满。

我认为接下来阅读这篇论文时，最值得进一步深挖的是 Figure 4→6 这段论证：它决定了“为什么 clustering suddenly wins”，也是整篇论文是否站得住脚的根基。之后再看 LLSP 和 GPU build，就会容易很多。

Keyboard shortcuts

Pages