Scaling HNSWs — antirez 把向量图做成 Redis 数据结构的工程笔记

是什么

《Scaling HNSWs》是 Redis 作者 antirez 写的一篇工程脑暴笔记：不是再讲一遍 HNSW 入门，而是讲「怎样把 Hierarchical Navigable Small World（分层可导航小世界图）做得够快、够省、够像 Redis」。

日常类比：HNSW 像一座多层商场导购图——你从高层快速落到大致区域，再在一层细找邻居。antirez 关心的不是商场图纸本身，而是：货架怎么压缩、导购怎么并行、拆店怎么不留死链、多店怎么分货。

它对应 Redis Vector Sets：把向量相似度当成一种一等数据结构（像 Sorted Set 的“相似版”），用 VADD / VREM / VSIM 操作，而不是只当搜索引擎上的附属索引。

为什么重要

不理解这篇笔记，下面这些事会对不上：

• 为什么 Redis 默认用 8-bit 量化（Q8）：约 4× 更快、向量约 4× 更省，真实场景 recall 几乎不掉
• 为什么 HNSW 查询要多线程，而 Redis 传统上偏单线程共享-nothing
• 为什么多数实现只能“打墓碑删除”，而 Vector Sets 能真删并回收内存
• 为什么把 HNSW 暴露成 key/数据结构，比“在别的数据上挂一个索引”更容易水平扩展

核心要点

1. 先省内存：按向量做 Q8 量化
   对每个向量取分量最大绝对值，映射到有符号 8 位（约 −127…127）。点积先在整数域算，再乘回 scale。类比：把精确价签改成“档位价签”，结账仍能对上。

2. 再提速：读多写少就并行
   查询几乎只读图；写入可拆成“后台找邻居候选 + 前台提交”。节点用 epoch 数组标记“本轮搜索是否已访问”，避免哈希表记 visited。类比：多位导购同时带客，每人在货架上盖自己的“已看戳”。

3. 真删除：强制双向边 + 邻居重连
   原文批评：很多人以为边可以单向，删除就找不到入边，只能 tombstone。antirez 强制 A↔B，删除时在旧邻居间做距离矩阵、贪心重连，甚至删掉 95% 节点后图仍连通、recall 仍可用。

4. 水平扩展：分片 + 客户端合并
   元素按 hash 进不同 key/实例；VSIM … WITHSCORES 并行查再合并。写入天然并行；读延迟接近最慢分片，而不是各分片相加。

5. 加载要序列化图，不要重建图
   若 RDB 只存“元素+向量”再插入重建，百万级会拖垮启动与复制；应把节点与邻居关系原样落盘，加载时做指针修复与互惠边校验。

实践案例

案例 1：Q8 写入与相似度查询

# 默认 Q8；也可用 NOQUANT / BIN
VADD mystream VALUES 0.1 0.2 0.3 item:a
VADD mystream VALUES 0.11 0.19 0.29 item:b
VSIM mystream VALUES 0.1 0.2 0.3 COUNT 2 WITHSCORES

逐步解释：

1. VADD 把元素和向量放进 Vector Set（内部是 HNSW 节点）
2. 默认把 float 压成 Q8，指针仍占空间，但向量体积极小
3. VSIM 在图上做 greedy 搜索，返回最相似元素与分数
4. 若业务极怕量化误差，再显式开 NOQUANT；二进制特征集可试 BIN

案例 2：多实例分片扩展

# 伪代码：按元素 id 分片，查询并行合并
shard = crc32(element) % N
VADD(f"vset:{{{shard}}}", vector, element)
# 查询：对 0..N-1 并行 VSIM，按 score 归并取 top-k

逐步解释：

1. 写入只打一个分片 → 写吞吐近似线性
2. 全量相似搜索要问所有分片，但可并行
3. 客户端按分数归并，得到全局近似 top-k

案例 3：带 JSON 属性的过滤搜索

VADD movies VALUES ... "blade" SETATTR '{"year":1998}'
VSIM movies VALUES ... FILTER '.year >= 1980 and .year < 1990'

逐步解释：

1. 每个节点可挂 JSON 元数据
2. greedy 搜索时用表达式过滤；过远且不匹配的不必穷举全图
3. 也可用“一年一个 key”的组合方式，体现数据结构可组合性

踩过的坑

1. 以为层数会让内存爆炸：多层平均大约只多 ~1.3×（层增长概率约 0.25）；真正大头常是 float 向量，先量化。
2. 删除只打 tombstone：单向边导致无法回收；要双向边 + 删除后重连。
3. RDB 按“元素+向量”重建图：加载极慢；应序列化节点与邻居，加载时指针修复（原文称可约 100×）。
4. 多线程共用一个 visited 标记：并发搜索会互相踩；用每线程 epoch 槽位。
5. 过滤条件极严还把 EF 开很小：可能过早停，召回崩——过滤要和探索预算一起调。
6. 把 Vector Set 只当成 RAG 插件：antirez 强调它是通用相似数据结构，指纹、推荐、规则向量都能用。

适用 vs 不适用场景

适用：

• 内存型、低延迟相似检索（百万～千万级，看维度与机器）
• 需要真正删除、过期 key、每用户/每商品一个小图
• 愿意用多 Redis 实例做分片，客户端合并结果
• 向量可用 Q8/BIN（学习型 embedding 通常很合适）

不适用：

• 必须全精度、且量化会伤业务指标的科学计算向量
• 数据远超内存、应以磁盘 ANN 为主力的冷存场景
• 不能接受“查所有分片再合并”的读模型，又强依赖单一全局索引语义
• 只要“给已有文档挂个向量字段”的托管搜索产品，而不想碰数据结构细节

历史小故事（可跳过）

• HNSW 论文给出分层小世界图，但几乎不谈真删除与工业线程模型。
• antirez 从零写 hnsw.c，做成 Redis Vector Sets，并公开这篇 scaling 笔记。
• 同期社区也在讨论“H 层是否必要”（文中引用 arXiv:2412.01940）；他的直觉是：全扁平会更慢，真相在中间。
• 设计争议点：同事未必一眼认同“HNSW 应是数据结构而非索引”；他用 Sorted Set 类比说服自己。

学到什么

1. 扩展 HNSW 往往先动表示与系统，而不是换算法名字——量化、线程、序列化、分片。
2. API 形状决定扩展方式：暴露成 key，分片与组合更自然。
3. 删除是图结构问题：边的方向性假设错了，内存就永远收不回来。
4. 性能数字要带场景：word2vec 量级、Q8、本机 benchmark，不能当成宇宙常数。
5. 过滤与探索预算要一起调：条件越严，越要给足搜索努力，否则“很快但什么都找不到”。

延伸阅读

• 原文：Scaling HNSWs — antirez
• Redis Vector Sets 模块说明：redis/redis vector-sets
• HNSW 实现源码入口：modules/vector-sets/hnsw.c（仓库内注释很全）
• 相关讨论：arXiv:2412.01940（HNSW 中 “H” 是否必要）
• word2vec —— 文中反复用作百万级向量负载例子
• faiss —— 另一条工业 ANN 路线，便于对照“库 vs 数据结构”

关联

• redis —— Vector Sets 落地的宿主与 API 哲学
• faiss —— IVF/HNSW 等索引库对照
• word2vec —— 文中性能与内存例子的数据来源语境
• hnsw —— 原始分层小世界图思想
• vector-search —— 近似近邻检索总览
• rag —— 常见但非唯一的向量应用

反向链接

（暂无反向链接）