从 SPTAG 到 SPANN，再到 SPFresh：亿级向量检索的技术脉络与细节

09 Oct, 2025

想象一下，你需要在千亿张名片堆成的月球般高的塔中，在一眨眼的时间内找到最相关的 10 张——这正是现代搜索引擎每天面临的挑战。从 Bing 的网页搜索到推荐系统，从问答助手到多模态检索，海量高维向量的近邻搜索（ANN）已经成为 AI 应用的基础设施。

但规模是残酷的。当数据量达到亿级、十亿级时，传统的内存索引方案要么内存爆炸，要么召回率惨不忍睹。更棘手的是，生产环境的数据始终在变化——每天有数百万新文档加入、旧内容下线，索引必须实时更新，同时保持毫秒级延迟和95%+ 的召回率。

这篇文章将带你走过微软研究院在向量检索领域的三个里程碑：SPTAG（2018）用树图混合导航破解高维诅咒，SPANN（2021）用内存 - 磁盘分层架构把容量扩展到十亿级，SPFresh（2023，SOSP）用增量自平衡协议彻底解决动态更新难题。我们不仅看"是什么"，更要看为什么这样设计，以及每个优化背后的工程直觉。

1. SPTAG：树 + 图的内存导航器

GitHub: https://github.com/Microsoft/SPTAG

SPTAG（Space Partition Tree And Graph） 是微软开源的近邻检索库，也是 Bing 搜索引擎的核心技术之一。它提供两套混合索引方案：KDT（kd-tree + RNG）和 BKT（Balanced k-means tree + RNG）。核心思想是用树做快速定位，用图做精确修正——树给搜索提供"方向感"，图保证局部连通性。

1.1 kd-tree 在 ANN 里的角色

kd-tree 是最经典的空间分割结构：递归选择方差最大的维度，用中位数作为切分点，把空间一分为二，直到叶节点的向量数量低于阈值。查询时从根节点出发，自顶向下选择"更靠近查询点"的子树，同时维护一个优先队列跟踪候选点。

优点：构建快（O(n log n)），搜索时能快速收敛到目标区域。

缺点：在高维空间（> 20 维）中，维度诅咒会让"距离上界估计"变得极其保守。一个点可能在超平面的"另一侧"，但实际上是最近邻——这就是著名的跨超平面近邻漏检问题。

1.2 Balanced k-means tree (BKT) 如何改进

BKT 用均衡 k-means 聚类取代轴对齐的超平面切分：每个节点把数据分成 k 个簇（通常 k=2 或 4），同时加入平衡约束，确保每个簇的大小接近。递归这个过程，直到叶节点足够小。

为什么需要平衡？ 如果某个簇特别大，搜索时进入该簇的代价会远高于其他分支，导致查询延迟不可预测。均衡性让树的每条路径"代价相近"，在高维数据上鲁棒性更强。

实现细节：SPTAG 的 BKT 使用层次化聚类，每次聚类前会对数据采样，避免全量 k-means 的计算开销。聚类结果会存储每个簇的质心，作为导航树的"路标"。

1.3 RNG（相对邻域图）的稀疏化魔法

RNG（Relative Neighborhood Graph）是一种稀疏化的邻接图。定义非常优雅：对于任意两点 p 和 q，仅当不存在第三点 r 使得

max(d(p, r), d(q, r)) < d(p, q)

时，才在 p 和 q 之间连边。直观理解：p 和 q 的"透镜区域"（两个圆的交集）中没有更近的点 r。

实践中的构建方式：SPTAG 先用近邻传播算法构建初始的 kNN 图（每个点连接 k 个最近邻），然后用 RNG 规则做修剪——删除那些有"捷径"可达的边。这样得到的图边数更少但连通性好，既节省内存，又避免搜索时陷入"边爆炸"。

为什么需要 RNG？ 完整的 kNN 图虽然召回率高，但在十亿级数据上，每个节点保存几百条边会让内存和遍历开销不可接受。RNG 通过稀疏化，把平均度数从 100+ 降到 20-30，同时保持可达性。

1.4 SPTAG 的检索流程（伪代码解析）

# 第一步：树导航，找到种子点
seeds = tree_search(BKT/KDT, query, num_seeds=10)

# 第二步：图上迭代扩展
candidates = PriorityQueue(seeds)
visited = set()

while len(visited) < MaxCheck and candidates:
    current = candidates.pop_best()  # 取出最近的候选
    
    for neighbor in RNG[current]:
        if neighbor not in visited:
            dist = distance(query, neighbor)
            candidates.push(neighbor, dist)
            visited.add(neighbor)

# 第三步：返回 Top-k
return candidates.top_k()

关键参数调优：

num_seeds：树返回的初始种子数，越多覆盖越广但开销越大
MaxCheck：最大访问节点数，控制召回率和延迟的权衡
RNG 的度数限制：平衡内存和连通性

性能数据：在 SIFT1M 数据集上，SPTAG-BKT 可以达到 95% 召回率，查询延迟 < 1ms（单线程，Intel Xeon）。

示意图（树上收敛 + 图内细化）：

          [Root]
         /  |   \
      [C1] [C2] [C3]  ← 树导航：快速定位到 C2 区域
       |     |     |
   RNG(C1) RNG(C2) RNG(C3)  ← 图扩展：在 C2 周围精修
            ↑
         种子点

2. SPANN：质心在内存、向量在磁盘的两层架构

论文：https://arxiv.org/abs/2111.08566

当数据量突破 10 亿向量时，把整个索引放内存的代价变得不可接受（需要数 TB 的 DRAM）。SPANN 的核心洞察是：我们真正需要快速访问的不是全部向量，而是"导航元数据"。因此，SPANN 设计了一个优雅的两层结构：

内存层：存储Posting 质心的 SPTAG 索引（通常只占数据集的 1-10%）
磁盘层：存储均衡的 Posting 列表（每个 Posting 是一组向量）

查询时，先在内存中用 SPTAG 找到最近的若干质心，然后并行读取对应的 Posting 列表，在全精度向量上做精排。

2.1 为什么"Posting 均衡"至关重要

如果 Posting 长度差异巨大（比如有的 Posting 有 10 万向量，有的只有 1000），查询会遇到严重的尾延迟抖动：

命中长 Posting 时，I/O 量和计算量暴涨
命中短 Posting 时，可能漏掉真正的近邻

SPANN 用多约束均衡聚类把 |X| 个向量划分成 N 个 Posting，目标是：

最小化 Var(|P_1|, |P_2|, ..., |P_N|)
同时保证 每个 P_i 的平均大小 ≈ |X| / N

层次化加速：直接在全量数据上做均衡聚类是 O(|X| · m · N)，不可行。SPANN 采用层次分组：先把数据粗略分成 k 组，每组再细分，把复杂度降到 O(|X| · m · k · log_k N)。

实际效果：在 SPACEV1B（10 亿向量）数据集上，SPANN 能把 Posting 长度的标准差控制在 平均值的 10% 以内，P99 延迟稳定在 2-3ms。

2.2 边界向量的"闭包赋值"策略

问题场景：假设查询点 q 最近的质心是 c1，但 q 的真实近邻 x 实际上属于邻近质心 c2 的 Posting。如果只搜索 P(c1)，就会漏掉 x。

SPANN 的解决方案：在构建索引时，识别"边界向量"并复制到多个 Posting。具体规则：

对于向量 x，设其最近的 K 个质心为 c_1, c_2, ..., c_K（按距离排序）
如果满足：
    d(x, c_j) ≤ (1 + ε1) · d(x, c_1)
则将 x 同时赋给 P(c_1), P(c_2), ..., P(c_j)

什么是边界向量？ 那些与多个质心距离几乎相同的向量——它们位于簇的边界，容易被遗漏。通过复制，确保只要搜索任一近邻 Posting，这些边界向量都有机会被召回。

参数 ε1 的权衡：

ε1 = 0.1：冗余度约 5-10%，召回率提升 2-3%
ε1 = 0.2：冗余度约 15-20%，召回率提升 4-5%

2.3 用 RNG 规则减少冗余复制

边界复制会导致一个新问题：如果有多个非常接近的质心（比如 c2、c3、c4 几乎在同一方向），把 x 复制到所有这些 Posting 会造成磁盘读浪费——因为这些 Posting 的内容高度重叠。

SPANN 借用 RNG 的思想：只保留"方向差异大"的多个簇。简化判定规则：

sorted_centroids = sorted(nearest_K_centroids, by_distance_to_x)

for j in range(1, K):
    c_j = sorted_centroids[j]
    c_prev = sorted_centroids[j-1]
    
    # 跳过 c_j，如果它"被 c_prev 遮挡"
    if distance(x, c_j) > distance(c_prev, c_j):
        continue
    
    # 否则，x 应该复制到 P(c_j)
    replicate(x, c_j)

直觉：如果从 x 看，c_j 被 c_prev “挡住了”（即去 c_j 的路上会先经过 c_prev），那么搜索时经过 c_prev 就能找到 x，不需要再复制到 c_j。

2.4 查询时的动态剪枝与质心替换

动态剪枝：不是固定搜 K 个 Posting，而是根据距离阈值动态决定：

threshold = (1 + ε2) * distance(query, nearest_centroid)

for centroid in candidate_centroids:
    if distance(query, centroid) <= threshold:
        fetch_and_search(Posting[centroid])

只有"距离足够近"的 Posting 才会被拉取，减少无效 I/O。

质心代表替换：用最靠近质心的真实向量替代几何中心做导航。好处：

几何中心可能不是数据集中的真实点，计算距离需要额外开销
真实向量已经在全精度数据中，可以直接复用

性能对比（SPACEV1B 数据集）：

SPANN vs DiskANN：2× 更快，达到 90% 召回率时延迟 ~1ms（DiskANN 需 2-3ms）
内存开销：32GB（仅存质心索引），vs DiskANN 的 60-100GB

3. SPFresh：在 SPANN 之上的在线增量更新与自平衡

论文：https://arxiv.org/abs/2410.14452（SOSP 2023）

SPANN 是静态构建的——索引一旦建成，更新就很麻烦。真实场景中，数据分布会持续漂移：新闻网站每天新增数千篇文章，电商平台商品库存实时变化。如果每次更新都全局重建，会遇到两大问题：

尾延迟飙升：重建期间 CPU/内存/I/O 被抢占，查询延迟从 2ms 飙到 20ms+
资源浪费：需要额外 60GB 内存和 10+ 核心，重建耗时数小时

SPFresh 在 SPANN 之上引入 LIRE（Lightweight Incremental Rebalancing）协议，把"重建"改成小步快跑的局部自愈，并配合用户态存储（SPDK）做可预测的 I/O。

3.1 LIRE 协议：五个操作，一个不变量

五类操作：

Insert：新向量直接追加到最近的 Posting
Delete：标记删除（不立即清理，延迟 GC）
Split：当 Posting 过长时，均匀分裂成两个
Merge：当 Posting 过短时，合并到邻近 Posting
Reassign：检查近邻 Posting，重新分配违反 NPA 的向量

不变量 NPA（Nearest Partition Assignment）：每个向量应归属于最近的 Posting 质心。Split/Merge 后，只对可能违反 NPA 的近邻 Posting触发 Reassign，工作集极小。

为什么 LIRE 高效？ 关键在于局部性：

Split 只影响被分裂的 Posting 及其邻居（通常 < 10 个 Posting）
Reassign 只评估边界向量（平均每次 ~5000 个向量，实际迁移 < 80 个）
收敛性保证：有限步内恢复 NPA 性质

实验数据（100 天，1% 日更新率）：

仅 0.4% 的插入触发重平衡
平均评估 5094 个向量，实际重分配 79 个
Merge 频率约 0.1%
级联分裂最长 3 层，平均 2 层

3.2 Version Map：并发友好的轻量元数据

每个向量维护 1 字节元数据：

7 bit 版本号（0-127 循环）
1 bit 删除标记

插入/重分配：版本号 +1（模 128）
删除：置位删除标记
查询：过滤 version < global_version 或 deleted = 1 的向量

并发控制：用 CAS（Compare-And-Swap） 原子更新 Version Map，写路径是 append-only，无需全局锁。查询可以在版本视图上无锁并行。

内存开销：10 亿向量只需 1GB 的 Version Map（vs DiskANN 额外 60GB 的辅助索引）。

3.3 存储层：SPDK vs RocksDB

SPDKStorage（主推方案）：

用户态 NVMe 驱动，绕过内核，减少上下文切换
提供原子 GET/APPEND/PUT 接口
降低写放大：append-only 写入，无需 compaction
可预测延迟：把瓶颈推到 SSD IOPS 上限，P99.9 稳定在 4ms

RocksDBStorage（备选方案）：

接口一致，部署门槛更低
自定义 MergeOperator 处理版本更新
但要承担 LSM-tree 的写放大和 compaction 抖动
P99.9 延迟会有周期性尖峰（compaction 期间可达 10ms+）

选择建议：

生产环境、性能优先 → SPDK
快速原型、已有 RocksDB 基础设施 → RocksDB

3.4 为什么 DiskANN 的全局重建会导致尾延迟飙升

DiskANN 的更新策略：

维护一个辅助索引累积更新
定期触发 streamingMerge，全局重建图结构
重建期间需要遍历并重连大量节点，计算密集

问题根源：

重建与查询竞争 CPU/内存/I/O
即便用"删旧边 + 补邻居的邻居"的轻量策略，也难阻止质量随时间下降
尾延迟锯齿：重建前积累劣化 → 重建期抖动 → 重建后短暂稳定 → 循环

实验对比（1% 日更新，100 天）：

DiskANN P99.9：正常 4-5ms，重建期飙到 20ms+（即便设置 10ms 硬超时）
SPFresh P99.9：全程稳定 ~4ms，对比基线平均 2.41× 更低

对比示意图：

DiskANN： ──┐         ┌── P99.9 延迟 ──┐         ┌──
            └─[Rebuild]─┘ (20ms+)      └─[Rebuild]─┘

SPFresh： ──────────────────────────────────────────
            (平稳 4ms，局部 Split/Merge 不可见)

4. 技术演进的全景总结

从 SPTAG 到 SPANN，再到 SPFresh，这三个系统展现了亿级向量检索的完整进化路径：

技术里程碑对比

维度	SPTAG (2018)	SPANN (2021)	SPFresh (2023)
规模	千万级（内存）	十亿级（混合）	十亿级（动态）
核心结构	树 + RNG 图	内存质心 + 磁盘 Posting	SPANN + LIRE 协议
内存开销	全量向量	1-10% 质心	1-10% 质心 + 1GB 元数据
查询延迟	< 1ms	1-2ms (P50)	~4ms (P99.9)
更新能力	支持但有限	静态构建	实时增量，无重建
尾延迟稳定性	中等	中等	优秀（2.41× 优于 DiskANN）

设计哲学的传承

SPTAG 的基因：树图混合导航成为后续系统的"内存层"基础
- SPANN 用 SPTAG-BKT 索引质心
- SPFresh 沿用这套导航结构
SPANN 的突破：内存 - 磁盘分层 + 均衡分区
- 把容量推到 SSD IOPS 极限
- 均衡性保证尾延迟稳定
SPFresh 的升华：局部自愈 + 版本控制
- 用 LIRE 避免全局重建
- 用 Version Map 实现并发友好的增量更新

适用场景指南

选择 SPTAG，如果你：

数据量 < 1000 万，内存充足
需要极致的查询延迟（< 1ms）
更新频率低（每天 < 1% 变化）

选择 SPANN，如果你：

数据量 > 1 亿，内存受限
可以接受静态构建（每周/每月重建一次）
尾延迟要求不极端（P99 < 5ms 可接受）

选择 SPFresh，如果你：

数据量 > 1 亿，且持续增长
需要实时更新（秒级延迟）
尾延迟要求严格（P99.9 < 10ms）
资源紧张（希望避免重建峰值）

#Vector-Search #Database #System #ANN