第3章：动态 ANN 工程谱系 —— SPFresh / Quake / OdinANN 横向对比

第 2 章末尾提到静态 ANN 有四条假设在 Agent 时代全部失效。但工业界不是 2026 年才意识到这件事——从 2021 年的 FreshDiskANN 开始，每年都有团队在攻动态 ANN 这块硬骨头：流式插入、删除、概念漂移、并发更新、recall 漂移……这些问题各家用了完全不同的工程手段，没有谁是”对的”，但理解它们各自的取舍是理解 Stage 5 的前提。本章把这五年最重要的 8 个系统按”它解决的痛点 → 它的核心技巧 → 它留下的开放问题”格式横向对比，再用最后一节讲清楚一个被反复提到但很少有人讲透的现象：“剪枝悖论”——为什么标记删除会让 recall 反而上升，而图却已经烂了。读完这章你会有一份动态 ANN 选型矩阵，并能讲清楚为什么这条线”还远没收敛”。

📑 目录

• 1. 动态 ANN 的三大核心难题
• 2. 五年演进时间轴
• 3. FreshDiskANN：out-of-place 缓冲范式
• 4. SPFresh：in-place + LIRE 局部重平衡
• 5. OdinANN：direct insert 在 billion-scale 上的工程化
• 6. PipeANN：BFS-SSD 对齐 + 并发更新
• 7. Quake：自适应分裂簇
• 8. LSM-VEC：LSM-tree 化磁盘 ANN
• 9. MN-RU：HNSW 删除优化
• 10. 动态 ANN 系统对比矩阵
• 11. 剪枝悖论与 Recall 悬崖
• 自我检验清单
• 参考资料

---

1. 动态 ANN 的三大核心难题

读后续每个系统前，先把”动态 ANN 难在哪”讲清楚。所有 8 个系统都是在三个核心难题之间做权衡：

难题 1：图退化（Graph Degradation）

新插入节点只能做局部搜索找邻居（不可能拿到全局 ground truth）。多次插入后：

• 边的质量下降（Stretch Factor 增大）
• 部分节点变得不可达（Unreachable Ratio 增大）

这不是工程 bug，是理论限制——HNSW 的 greedy insert 只能给出 M 个 局部最优 邻居。

难题 2：删除一致性

删除一个节点有两种做法，都有副作用：

做法	优点	缺点
标记删除（tombstone）	立刻可见，O(1)	图结构变形、剪枝悖论
物理删除 + 重连邻居	图保持紧致	慢，需要扫该节点的所有邻居

工业系统几乎都用标记删除，但没人定期 compaction → 时间长了图变成”破洞奶酪”。

难题 3：动态触发重建

最朴素的策略：监控 Recall，掉到阈值就全量重建。但这会引发两个问题：

• 重建很贵：百万级 HNSW 重建 3-5 分钟，百亿级要小时
• Recall 是滞后指标：等它掉下来已经太晚（参见本章第 11 节”recall 悬崖”）

🌟 结论：动态 ANN 的工程难题本质是”在三种损失之间动态权衡”——读延迟（图质量）、写延迟（重建代价）、可观测性（什么时候该重建）。本章 8 个系统每一个都在三角某个角上做得更好，但没有谁同时把三个都做满。

---

2. 五年演进时间轴

2021 ─── FreshDiskANN (NeurIPS)
   │     Out-of-place buffer + 周期合并
   │     "把动态变成批量"，最朴素也最稳健
   │
2023 ─── SPFresh (SOSP)
   │     In-place 增量更新 + LIRE 局部 rebalance
   │     "不重建，只修补受影响的局部"
   │     ↑↑↑ 第一次让"流式 ANN"在工业系统站稳脚跟
   │
2024 ─── MN-RU (arXiv)
   │     HNSW 删除优化，抑制不可达点增长
   │     "动态 ANN 第一次直面 unreachability"
   │
2025 ─── Quake (OSDI) ⭐
   │     自适应分裂大簇 + 索引内分裂决策
   │     "把 IVF 的固定簇变成动态结构"
   │
2025 ─── PipeANN (OSDI)
   │     BFS 与 SSD 局部性对齐，搜索更新并发
   │     "把硬件假设搬进图算法"
   │
2025 ─── LSM-VEC (arXiv)
   │     LSM-tree 式分层 + compaction，把动态 ANN 完全磁盘化
   │
2025 ─── UBIS (BigData)
   │     可更新平衡索引，锁设计 + 分裂优化
   │
2026 ─── OdinANN (FAST) ⭐
   │     Direct insert，billion-scale 稳定吞吐
   │     "不要 buffer，直接插，靠 careful 设计扛住"

⭐ 关键判断：这条演进线还远没收敛——2025 年的 Quake / PipeANN / OdinANN 是三种完全不同的工程哲学（自适应分裂 vs 硬件对齐 vs 直插），没有”统一胜者”。

---

3. FreshDiskANN：out-of-place 缓冲范式

3.1 痛点

DiskANN（2019）是静态的——所有向量一次性写入 SSD，构建好的 Vamana 图也是固定的。怎么支持新向量插入？

3.2 核心技巧：out-of-place buffer

FreshDiskANN（Singh et al., NeurIPS 2021）的方案极其朴素但有效：

┌─────────────────────────────────────────┐
│                                         │
│  Long-term Index (SSD)                  │
│  ┌─────────────────────────────────┐    │
│  │  原始的 DiskANN Vamana 图        │    │
│  │  10 亿向量，只读                  │    │
│  └─────────────────────────────────┘    │
│                                         │
│  Streaming Buffer (DRAM)                │
│  ┌─────────────────────────────────┐    │
│  │  新插入的向量 + 增量 HNSW 图      │    │
│  │  几百万到一千万向量              │    │
│  └─────────────────────────────────┘    │
│                                         │
│  查询：两边都搜，结果归并               │
│                                         │
└─────────────────────────────────────────┘

定期：当 buffer 满了，触发 merge：
    1. 把 buffer 里的向量插入 long-term index
    2. 清空 buffer，等待下一批

🍎 直觉比喻：FreshDiskANN 像信用卡账单——白天刷卡（buffer）随时累积，每月结账（merge）一次性把所有交易归入主账户。

3.3 关键参数与权衡

参数	典型值	调参权衡
buffer 大小	10M-50M 向量	太小：merge 频繁，太大：查询延迟（每次要搜 buffer）
merge 触发条件	buffer 达 80% 或周期	影响”新数据可见度”和”merge 暂停”的平衡
merge 模式	全量重建 vs 增量插入	FreshDiskANN 用增量，但仍需停服

3.4 留下的开放问题

• ❌ merge 期间服务质量下降：merge 是 CPU/IO 密集操作，期间 QPS 显著下降
• ❌ 删除支持差：只能标记删除，物理回收要靠 merge
• ❌ buffer 设计太朴素：不能区分热冷数据

🌟 结论：FreshDiskANN 是”动态 ANN 的稻草人”——简单可用，但留了大量工程优化空间。所有后续工作都在攻它的某个开放问题。

---

4. SPFresh：in-place + LIRE 局部重平衡

4.1 痛点

FreshDiskANN 的 buffer 方案有一个致命问题：buffer 里的向量和主索引不在同一个图上，跨图搜索的召回天然有损。SPFresh 想做”直接在主索引上插入，不用 buffer”。

4.2 核心技巧：LIRE (Lightweight Incremental Re-balancing)

SPFresh（Xu et al., SOSP 2023）基于 SPANN（聚类 + SSD 范式），主要贡献是 LIRE 局部重平衡协议：

插入新向量 v：
1. 找最近的聚类中心 c → v 加入 c 的倒排列表
2. 检查 c 的列表大小：
   - 如果 < 1.5x 平均：什么都不做（happy path）
   - 如果 > 1.5x 平均：触发 LIRE
3. LIRE：
   - 在 c 的附近找一个相邻聚类 c'
   - 用 k-means(2) 把 c 的成员重新分成 c 和 c''
   - 更新倒排列表，但 ** 邻居的邻居不动 **

🧠 关键洞察：LIRE 把”全局 k-means”退化成”局部 k-means(2)“——只重新分配触发分裂的那个簇里的向量，不影响其他簇。代价从 O(N) 降到 O(簇大小)。

4.3 工程数据（SPFresh 论文）

指标	FreshDiskANN	SPFresh	改进
单次更新延迟	~100 ms	~10 ms	10x
每日 1% 更新率所需资源	50% CPU + 50% DRAM	10% CPU + 1% DRAM	5-50x
召回稳定性	周期性下降（merge 前）	平稳	显著

4.4 留下的开放问题

• ⚠️ LIRE 假设”局部”够用：在分布漂移大的工作负载下，局部重平衡不够
• ⚠️ 图退化未直接处理：LIRE 平衡簇大小，但 HNSW 图退化仍然存在
• ⚠️ 无健康监控：什么时候该触发全量重建？经验阈值

🌟 结论：SPFresh 是**“in-place 增量更新”范式的奠基**。所有后续 in-place 工作（Quake、OdinANN）都站在它肩上。

---

5. OdinANN：direct insert 在 billion-scale 上的工程化

5.1 痛点

SPFresh 用 LIRE 解决簇分裂，但 更新依然要先写到 buffer 再 merge 进主索引。OdinANN（FAST 2026）问了一个更激进的问题：为什么不直接插入主索引？

5.2 核心技巧：直接插入 + careful 数据布局

OdinANN 的核心是把”动态插入”做到与静态插入一样原地：

传统流程：
  insert v → write to buffer → ... wait ... → batch merge → main index

OdinANN 流程：
  insert v → directly write to main index → done

听起来简单，难点在 不破坏主索引的查询性能。OdinANN 用了三个技巧：

1. 预留 gap：建索引时每个邻居列表留 1.5x 容量，新插入不需要 realloc
2. Lock-free 并发：插入和搜索用 RCU（Read-Copy-Update）模式
3. Lazy reorder：邻居列表周期性按访问频率重排，不阻塞查询

5.3 工程数据

• 在 SPACEV-1B（10 亿向量）上：插入吞吐 50K op/s，查询延迟波动 < 5%
• 与 SPFresh 比：查询延迟降低 2-3x（因为没有跨索引归并）

5.4 留下的开放问题

• ❌ 预留 gap 占额外内存 —— 1.5x 倍数空间浪费
• ❌ 不支持高效删除 —— 仍然依赖标记删除
• ❌ 在分布漂移下未验证

🌟 结论：OdinANN 是 2026 年最新的工业派路线——在”等批量”和”立刻插入”之间，选择了后者，靠工程把代价吃下来。

---

6. PipeANN：BFS-SSD 对齐 + 并发更新

6.1 痛点

DiskANN 系列的搜索都是 BFS（广度优先），但 BFS 的访问模式和 SSD 的 IO 模式（连续 4KB 大块读）严重不匹配——每次跳到不连续的图节点，IO 利用率极低。

6.2 核心技巧：把 BFS 阶段化 + 与 IO 对齐

PipeANN（OSDI 2025）的核心创新：

传统 DiskANN：
  搜索一步 → 读 SSD 一次 → 搜索下一步 → 读 SSD 一次 → ...
  IO 利用率约 10-20%

PipeANN：
  把 BFS 分成 stage，每 stage 内提前 prefetch 下一 stage 的节点：
  stage 1: 探索 a, b, c → 同时 prefetch d, e, f
  stage 2: 探索 d, e, f → 同时 prefetch g, h, i
  IO 利用率 > 80%

加上并发更新——搜索和插入用不同的锁粒度（节点级而非图级），互不阻塞。

6.3 工程数据

• SPACEV-1B：1ms 端到端搜索延迟（vs DiskANN 的 5-10 ms）
• 混合搜索 + 插入 workload：搜索延迟波动 仅 1.07x（vs DiskANN 的 3-5x）

6.4 留下的开放问题

• ⚠️ prefetch 决策启发式 —— 没有理论指导哪些节点该预取
• ⚠️ 删除仍依赖标记

🌟 结论：PipeANN 把”算法 vs 硬件”的张力从”互相妥协”变成”协同设计”，是 2025 年硬件对齐方向的标杆。

---

7. Quake：自适应分裂簇

7.1 痛点

IVF 和 SPFresh 都假设 簇数 nlist 是固定的。但 agent workload 下：

• 某些簇被频繁更新 → 越来越大 → 精搜慢
• 某些簇几乎没人访问 → 浪费索引空间

7.2 核心技巧：在线分裂大簇

Quake（Mohoney et al., OSDI 2025）让 nlist 变成动态变量：

触发条件：
1. 某簇大小 > 平均 × α（α = 2.0 是经典值）
2. 该簇近 N 秒查询命中率 > β

满足条件 → 在线把簇 c 分裂成 c1, c2：
- 用 k-means(2) 找到分裂超平面
- 更新倒排列表
- 通知粗搜层（IVF 中心）

合并条件（对偶）：
1. 两个簇都很小且相邻
2. 合并不增加平均搜索代价 → 合并

🧠 关键洞察：Quake 把 IVF 从”静态聚类”变成了”自适应空间划分”——本质上模拟了 B-tree 的页分裂逻辑。

7.3 工程数据

• 在 agent-style workload（局部性强）下，搜索延迟降低 40-60%
• 索引空间几乎不变（分裂和合并平衡）

7.4 留下的开放问题

• ⚠️ 分裂判定依赖经验阈值 —— α 和 β 没有理论指导
• ⚠️ 只对 IVF 系有效 —— 图索引（HNSW）没法直接套用
• ⚠️ 多 agent 共享时分裂决策冲突 —— 不同 agent 的访问模式可能矛盾

🌟 结论：Quake 是”索引内自适应”范式的代表。它的思想可以推广到 HNSW——参见第 5 章 Pancake 的 FSM 模式建模。

---

8. LSM-VEC：LSM-tree 化磁盘 ANN

8.1 痛点

DiskANN 系列把图写盘了，但图本身的结构在磁盘上不能变。对动态插入只能用 buffer + merge。LSM-VEC 借鉴 LSM-tree 的设计：多层、每层只读、定期 compaction。

8.2 核心技巧

Level 0 (DRAM): 最新的向量 + 小图        ←  随时插入
Level 1 (SSD): 中等大小图                ←  Level 0 满了就合并下来
Level 2 (SSD): 大图（compaction 结果）   ←  最稳定，最大
Level 3 (HDD/对象存储): 冷数据           ←  访问极少

查询：从 Level 0 到 Level 3 依次搜，合并结果

Compaction（后台）：
- Level 0 → Level 1：定期或满阈值
- Level 1 → Level 2：达到大小比例时
- ...

🍎 直觉对应：LSM-VEC 像图书馆的”新书架 / 流通书架 / 库存书架”分层——新书放容易拿的架子，旧书归档到深处。

8.3 工程数据

• 内存占用 比 DiskANN 减少 66%
• 写吞吐比 SPFresh 高 2-3x（多层并发写）
• 但查询延迟略增（多层归并开销）

🌟 结论：LSM-VEC 是把”数据库系统设计哲学”成功移植到 ANN 的代表。适合”写多读少”或”成本极敏感”场景。

---

9. MN-RU：HNSW 删除优化

9.1 痛点

HNSW 的标记删除会产生不可达点（unreachable points）——某些点的所有邻居都被删除了，搜索路径再也走不到它。MN-RU（Mutual-Neighbor Reachability Update）是 2024 年第一个经验性观察并修复这个问题的工作。

9.2 核心技巧

删除节点 v 时：
1. 找 v 的所有邻居 N(v)
2. 对每个 u ∈ N(v)，检查 u 失去 v 后是否仍可达
3. 如果失去 v 让 u 变成不可达：
   - 从 N(v) 之外找一个替代邻居 u'
   - 添加边 u ← → u'
   - 这样保持图的"互相可达性"

9.3 工程数据

• 删除 50% 数据后 unreachable ratio 从 30%+ 降到 < 5%
• 召回保持稳定（vs 朴素标记删除会先升后崩）

🌟 结论：MN-RU 是第一篇正式承认”HNSW 在动态删除下结构会烂”的论文。但它只解决了部分问题——本章第 11 节会讲清楚为什么 “解决了不可达点” 仍然不够。

---

10. 动态 ANN 系统对比矩阵

系统	基础架构	核心技巧	优势场景	弱点
FreshDiskANN (2021)	DiskANN + buffer	周期 merge	简单稳健	merge 期间退化
SPFresh (2023)	SPANN + LIRE	局部 k-means(2)	工业级 in-place 标杆	无健康监控
MN-RU (2024)	HNSW + 互可达	删除时补连	删除场景召回稳定	只解决删除
Quake (2025)	IVF + 自适应分裂	在线 split/merge 簇	局部性强的 workload	仅对 IVF 系有效
PipeANN (2025)	DiskANN + 硬件对齐	BFS-IO 阶段化 + 并发	SSD 友好、低延迟	启发式 prefetch
LSM-VEC (2025)	LSM-tree 图	多层 compaction	写多读少 + 成本敏感	查询延迟略高
OdinANN (2026)	HNSW direct insert	RCU + lazy reorder	billion-scale 稳定流式	1.5x 内存开销

选型决策树

你的工作负载？
├── 偶尔批量更新（每天几千次） ──→ FreshDiskANN（最简单）
│
├── 持续小批量更新 ──────────→ SPFresh（in-place 标杆）
│                              或 OdinANN（最新，性能更好）
│
├── 局部性强（某些点频繁访问） → Quake（自适应簇）
│
├── 强删除需求 ──────────────→ 任意 + MN-RU（删除时配合）
│
├── 内存极受限 ──────────────→ LSM-VEC（多层磁盘）
│
└── 极低延迟 SSD ────────────→ PipeANN（硬件对齐）

🌟 关键判断：没有”通用最优”——动态 ANN 选型必须基于具体 workload。Agent Memory 的 workload 在第 4 章详细分析。

---

11. 剪枝悖论与 Recall 悬崖

这一节讲两个所有动态 ANN 都会遇到、但很少有人讲透的现象。理解这两个现象是从工程师到研究者的分水岭。

11.1 剪枝悖论（The Pruning Paradox）

现象：在 HNSW 上做标记删除，删除 50% 数据后，Recall@10 不降反升——从 0.985 升到 0.997。但同时，不可达比率（UR）从 0 飙升到 52%。

为什么 Recall 上升？ 因为标记删除让搜索时跳过已删除节点，相当于”剪枝”了搜索路径，反而更干净。

为什么这是个问题？ 因为 UR 在累积——图结构已经严重退化。一旦达到拐点（典型 60-70% 删除），recall 会瞬间崩溃。

Recall@10
   ▲
1.0│       ╭───────────╮              ╲
   │      ╱             ╲              ╲ ← 拐点（不可预测）
   │     ╱               ╲              ╲
0.95│   ╱                 ╲              ╲╲
   │                                       ╲╲
0.5│                                          ╲╲
   │                                            ╲╲
   └─────────────────────────────────────────────➤
      0%     20%     40%     60%     80%   删除比例

Unreachable Ratio
   ▲
0.5│                                       ╱╱
   │                                    ╱╱
   │                                 ╱╱
0.3│                              ╱╱
   │                          ╱╱
   │                       ╱╱
   │                    ╱╱
0.0└──────────────────╱─────────────────────➤
      0%     20%     40%     60%     80%   删除比例

🧠 关键洞察：Recall 是滞后指标，UR 是领先指标。系统监控 Recall 永远晚一步，必须监控 UR 才能在崩溃前介入。

11.2 Recall 悬崖（Recall Cliff）

现象：在持续聚类插入（concept drift）下，Recall 前 90% 操作维持 0.99，最后 10% 操作灾难性下降到 0.26。

为什么不是渐进下降？ 因为 HNSW 图有一定”鲁棒性”——少量退化能被 ef_search 的冗余消化。一旦冗余耗尽，搜索路径全面失效，崩溃是非线性的。

Recall@10
   ▲
1.0│ ━━━━━━━━━━━━━━━━━━━━━━━╮
0.9│                          │
0.8│                          │
   │                          │
0.5│                          │
   │                          ╲
0.3│                            ╲
0.2│                              ━━━━━
   └─────────────────────────────────────➤
     0     250K     500K   操作数

   ↑                          ↑
   稳定区                    悬崖

🧠 关键洞察：等 Recall 报警时已经在悬崖底了——必须有比 Recall 更早的信号。

11.3 这两个现象的意义

给工程师：不要单纯监控 Recall，也要监控 UR / SF（Stretch Factor）等”图健康指标”。

给研究者：这是 Agent Memory ANN 系统层论文的核心 motivation——如果 Recall 是欺骗性的，那现有所有”自适应重建策略”（包括 Quake 的分裂判定、SPFresh 的 LIRE 阈值）都建立在沙堆上。

⭐ 这两个现象是后续 Pancake 三章和第 9 章研究方法论的支撑性观察。Pancake 在第 5 章会用一种完全不同的 “FSM 模式建模” 来绕开它。

---

✅ 自我检验清单

• 三大核心难题：能说出动态 ANN 的三个核心难题（图退化、删除一致性、动态触发重建），并举例说明每一个的具体表现
• 8 个系统的核心技巧：每个系统能用一句话讲清核心创新
• SPFresh LIRE：能解释 LIRE 为什么是”局部 k-means(2)“，相比全局 k-means 的代价节省多少
• OdinANN direct insert：能说出它怎么做到”不要 buffer 也能稳定”的三个工程技巧
• Quake 自适应分裂：能解释簇的分裂判定条件，并讨论它在多 agent 场景下的潜在冲突
• 剪枝悖论：能讲清楚”为什么 50% 删除后 Recall 上升但 UR 上升到 52%”
• Recall 悬崖：能解释为什么 Recall 是非线性下降（不是渐进下降）
• 选型：给定一个具体的 workload（每天 1% 更新、10 亿规模、内存受限），能给出合理的动态 ANN 选型

---

📚 参考资料

概念入门

• Faiss “Dynamic indexes” 讨论：Faiss issues —— 工业上 dynamic ANN 的真实痛点合集
• Milvus “Dynamic vector index” 文档：milvus.io —— 工业系统怎么处理流式数据
• The Pruning Paradox 博客实验：建议自己用 hnswlib 跑一遍——10 行代码就能复现（参见本系列模块二十二第 9 章实战）

关键论文（按时间序）

2021-2023 起步阶段：

• FreshDiskANN: A Fast and Accurate Graph-Based ANN Index for Streaming Similarity Search（Singh et al., NeurIPS 2021）：arXiv 2105.09613
• SPFresh: Incremental In-Place Update for Billion-Scale Vector Search（Xu et al., SOSP 2023）：ACM DL —— in-place 范式奠基

2024 删除与可达性：

• Enhancing HNSW Index for Real-Time Updates: Addressing Unreachable Points and Performance Degradation (MN-RU)（2024）：arXiv 2407.07871

2025 多路线分化：

• Quake: Adaptive Indexing for Vector Search（Mohoney et al., OSDI 2025）：USENIX PDF
• PipeANN: Achieving Low-Latency Graph-Based Vector Search via Aligning BFS with SSD（Guo et al., OSDI 2025）：USENIX PDF
• LSM-VEC: A Large-Scale Disk-Based System for Dynamic Vector Search（2025）：arXiv 2505.17152
• UBIS: Updatable Balanced Index for Stable Streaming Similarity Search（BigData 2025）

2026 工业派最新：

• OdinANN: Direct Insert for Consistently Stable Performance in Billion-Scale Graph-Based ANNS（FAST 2026）：Tsinghua PDF ⭐

Surveys

• A Survey on Vector Database Management Systems（Pan et al., 2024）：arXiv 2310.14021 —— 含动态 ANN 综述章节
• Storage-Based Approximate Nearest Neighbor Search Survey（IISWC 2025）：atlarge-research.com PDF —— 磁盘级动态 ANN 视角

行业讨论

• Microsoft DiskANN GitHub：github.com/microsoft/DiskANN —— 含 FreshDiskANN 实现
• Pinecone “Vector Database Reliability” 系列：pinecone.io/learn —— 工业系统的 SLA 视角
• Quake 项目主页：可通过 OSDI 2025 论文获取

本系列其它章节

• 上一章：第2章 静态 ANN 技术回顾 —— 静态 ANN 四条假设的失效
• 下一章：第4章 Agent Memory 系统总览 —— 应用层框架 Mem-GPT / A-MEM / MIRIX / MemOS
• 相关模块：模块十九 Agent Memory 实证审计与负结果方法论 —— 剪枝悖论的实证审计方法论