06. DiskANN — 十亿向量 SSD 索引(向量索引侧基础参考)

元数据

论文标题:DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node
出处:NeurIPS 2019(Microsoft Research)
后续:FreshDiskANN(2021,流式更新)、Filtered DiskANN(SIGMOD 2024,带过滤)
关键词:billion-scale ANN、graph-based、SSD-resident

一句话精髓

把图索引(类似 HNSW)的”邻居表”放在 SSD,只在 RAM 里保留极小的导航结构,实现单机十亿向量召回——证明了”向量索引完全可以驻留 SSD”。

解决的问题

向量近似最近邻(ANN)主流是图索引(HNSW、NSG),但图本身随向量数线性增长——10 亿向量的图占几百 GB,根本塞不进 RAM。已有磁盘方案要么召回率低,要么延迟爆炸。

关键 idea

设计	内容
Vamana 图算法	一种比 HNSW 更适合磁盘访问的单层图,搜索路径短
量化导航表 in RAM	全量向量做 PQ(Product Quantization)放 RAM,用于快速过滤候选
完整向量 + 邻居表 in SSD	真正的精确比较和图遍历从 SSD 拉
批量异步 IO	一次 search 的多次 SSD 读用 io_uring/libaio 并发
构建侧	用 RAM 构建子图 + 合并,避免一次性把全图放 RAM

关键架构图

RAM:
  ┌─────────────────────────────────────┐
  │ PQ-compressed vectors(全量,~10× 压缩)│
  │ Entry points(图入口)                │
  └─────────────────────────────────────┘
       │ 用 PQ 距离粗筛候选
       ▼
SSD:
  ┌─────────────────────────────────────┐
  │ Full vectors(fp32/fp16)             │
  │ Adjacency list(邻居表)              │
  └─────────────────────────────────────┘
       │ 异步并发读真实邻居
       ▼
   精确距离 → 更新候选堆 → 收敛返回 top-k

关键数据(论文公开)

单机十亿规模,95%+ 召回 @ 5 ms 量级延迟(在当时 NVMe + 内存配置下)
RAM 占用从”数百 GB”降到 几十 GB 量级
Recall vs latency 曲线在 SSD 方案里长期是 SOTA

局限

更新友好性差:原版只支持批量重建,FreshDiskANN 才补了流式更新
单查询延迟对 SSD random read 敏感,P99 抖动比纯内存大
没考虑带过滤(filter) 的查询(后续 Filtered DiskANN 才补)
多模态/异构数据没原生支持(只有向量)

对本项目的启示

🌟 向量索引层级化的标杆——证明了”向量库不必塞 RAM”。本项目要把这套思路扩展:

三级化:DiskANN 是 RAM-SSD 二级,我们要做 HBM-DRAM-SSD 三级——HBM 放最热的几百万向量(GPU 可加速),DRAM 放 PQ-compressed,SSD 放完整
与 KV / 多模态共享存储池:DiskANN 假设它独占 SSD,但生产环境向量库要和 KV cache、原始图像 blob 共住——调度器要平衡几路 IO
LLM 检索路径融合:Agent 长记忆 = 向量召回 + KV 复用,两件事的存储应该同源(参考 AlayaDB 笔记 07)
过滤 + 长记忆:Filtered DiskANN 已经做了”带 metadata 过滤的 ANN”,我们要做”按 user_id / 时间窗”的 Agent 级过滤
流式更新:FreshDiskANN 思想是对的,但 Agent 长记忆的更新频率可能比它假设的还高,需要重新考虑

横向对比

系统	主索引位置	更新支持	过滤	规模
HNSW(in-mem)	RAM	弱	后处理	千万级
DiskANN	SSD	仅批量	无	十亿
FreshDiskANN	SSD	流式	无	十亿
SPANN(NeurIPS’21)	cluster + SSD	中等	部分	十亿
AlayaDB(2025)	多级 + LLM-aware	流式	LLM 集成	TBD
本项目目标	HBM/DRAM/SSD 三级 + Agent 语义过滤	流式	多维度	TB 级

待精读

DiskANN 的 IO pattern(每次 search 读 SSD 多少次?块大小?)
Filtered DiskANN 怎么实现 attribute filter
FreshDiskANN 的更新放大系数

06. DiskANN — 磁盘友好的向量近似最近邻

搜索