Scaling HNSWs

2025-11-11

扩展 HNSW

我要暂停几周 HNSWs(分层可导航小世界) 方面的开发（现在在做另一种数据结构，很快会有消息）。到这个阶段，我为 Redis 新增的类型已经足够稳定和完整，正是时候梳理一下我在 HNSW 上学到的东西，并把它写成一篇博客。就是那种在 AI 时代之前很常见、现在或许变得有点稀少的“脑内倾倒”式分享。嗯，经过近一年对 HNSW 和向量相似度相关工作的思考与实现，是时候写点东西了。不过这不会是一篇 HNSW 的入门介绍——那样的文章已经太多了。这篇要走的是“多走一里路”的部分。如果你已经了解 HNSW，我想与你分享一些更“进阶”的发现，特别是在让它足够快、以提供“Redis 体验”方面的探索：你知道，Redis 为低延迟和高性能而设计，而 HNSW 多少有些与之相悖，因此将 HNSW 作为一种抽象数据结构暴露出来面临不少挑战。

这篇博客将分为几个小节。可以把它们看作同一本书的不同页面、同一段经历的不同章节。哦，顺便说一句，我其实已经写过一遍这篇博客，然后又弄丢了 :D [关于 MacOS 和坏习惯的漫长悲伤故事——自 90 年代停电那会儿以来，我就再没丢过这种东西]，所以这次最大的难题是回忆几天前写过的内容，并在重写的过程中，把之前不太满意的地方表达得更好一些。

关于 HNSW 现状的几句话

在深入 HNSW 的内部原理和优化之前，我想先说几句关于 HNSW 的现状。介绍 HNSW 的原始论文是一篇出色的计算机科学文献，HNSW 也是非常惊艳的数据结构，但是：我不认为它是基于距离函数以贪心方式搜索近邻向量的最终答案。论文给人的感觉像是缺少了一些“拼图”，几乎就像研究人员如果再有半年时间，本可以探索和阐述更多内容。例如，我自己就对论文做了修改，扩展它以支持条目的删除——真正的删除，而不仅仅是用墓碑标记“已删除”并延后回收：论文中完全没有涉及删除条目的内容。同样，现在也有一些工作在认真检验 HNSW 中的“H”是否真的必要，以及是否用只有一层的扁平数据结构也能取得大致相同的性能（希望以后能多谈谈这个：我的感觉是真相介于两者之间，修改层级选择函数、只保留高于某个阈值的层级可能是有意义的）。

说这些是想表达，如果你从事数据结构研究，我认为构想 HNSW 的演进和改进是一个很好的方向，而不必陷入那种认为演进仅仅是“把它搬到磁盘上”（比如 Microsoft 的相关工作）之类的思路。好了，前言就到这里，我们进入真正的底层内容吧 :)

扩展内存

Redis 是一个内存系统，而 HNSW 和向量都有一个不幸的特点：非常耗空间。原因有三：1. HNSW 有很多指针，比如 16、32 甚至更多指向邻居节点的指针（这是 HNSW 的一个可调参数）。2. HNSW 有很多层，因为它是一种类似跳表的数据结构。这加剧了第一个问题。3. HNSW 的附属数据是浮点数向量，所以在原生情况下，每个分量 4 字节，而通常一个向量会有 300 到 3000 个分量，这是常见范围。

那么，这里学到了什么？有人会压缩指针，因为很可能很多指针（在 64 位系统上为 8 字节）的高 4 字节都是相同的。这很巧妙，我还没实现，因为在 Redis 里我需要追求速度，而这是空间与时间的权衡：但也许值得，也许不值得。我会再深入研究。

不过，如果你算一下，多层带来的影响其实并没有看起来那么可怕。平均而言，每个节点的多层结构只会让情况恶化约 1.3 倍（如果层级选择函数中层级递增的概率是 0.25），因为很多节点只会在第 0 层。但即便如此，1.3 还是比 1 大，而且如果 HNSW 中的“H”真的没那么有用……[剧透一下，我发现如果所有东西都在第 0 层，搜索时间会更长，贪心搜索的主循环会从不那么理想的位置开始，最终也能到达正确的簇，但会花费更多计算时间。不过这只是初步结果。]

所以这里真正的低垂果实是：向量量化。我发现如果使用 8 位量化，你能获得近 4 倍的加速、向量体积缩小 4 倍（但整个节点不会缩小 4 倍：指针还在那里，占很大空间），而在真实世界的用例中召回率几乎不变。这就是 Redis Vector Sets 默认使用 8 位量化的原因。你可以通过 VADD 选项指定需要全精度向量或二进制量化向量——后者只取符号位——但我对同时使用全精度向量和二进制量化向量持怀疑态度。在谈论它们之前，先看看我对 8 位量化是怎么做的。

我做的是计算每个向量分量的最大绝对值（所以量化是按向量进行的），然后用有符号 8 位值来表示从 -127 到 127 的量化。这不如同时存储最小值和最大值那么好，但在计算余弦相似度时会更快，因为我可以这样做：

/* Each vector is quantized from [-max_abs, +max_abs] to [-127, 127]
 * where range = 2*max_abs. */
const float scale_product = (range_a/127) * (range_b/127);

然后我在整数域中将它们相乘（实际上代码中的主循环是展开的，并使用了多个累加器，以让现代 CPU 更忙碌）

for (; i < dim; i++) dot0 += ((int32_t)x[i]) * ((int32_t)y[i]);

最后我们可以用以下方式回到浮点距离：

float dotf = dot0 * scale_product;

查看 vectors_distance_q8() 可以了解更多信息，但我想你已经明白了：从整数量化域回到未量化的点积非常简单，只需一些平凡的操作。

所以，8 位量化非常划算，而全精度是一个*必要*的功能，因为会有人以某种方式生成向量，其中每一处细微差异都很重要（不，用学习得到的向量就不是这样……）但是，为什么要有二进制量化呢？因为我想让用户在*原始*信息本身就是二进制时，有一种简单的方式来避免空间浪费。想象你有一组用户，他们有是／否属性，你想找到相似的用户、物品之类。嗯：这就是应该使用二进制量化的地方，它同样只是 VADD 命令的一个选项。

扩展速度：多线程与局部性

哦，你知道，我得先说说我自己：只要能用单核做很多事、然后用无共享架构去利用多核，我就不太喜欢多线程系统。但 HNSW 不同。它*很慢*，而且在大多数用例中几乎总是以只读方式被访问。正因如此，我的 Vector Sets 实现是完全多线程的。不只是读，连写也是部分多线程的，你可能会好奇，在 Redis 这样的系统中，这怎么可能不搞得一团糟——尤其是键可能被后台保存进程、客户端等以不同方式访问。

好吧，先聚焦于读。只要没有人在写入数据结构，我们就可以启动线程来贪心地收集近邻向量，并将结果返回给被阻塞的客户端。然而，我的 HNSW 实现是从零开始写的，我的意思是，从用 vim 打开的空 C 文件开始，它与其他系统常用的两种实现的共享代码为 0%，所以有一些“新东西”。其中一个不同之处是，为了避免重复访问已访问的节点，我在每个节点中存储了一个叫“epoch”的整数，而不是用另一种数据结构（比如哈希表）来标记已访问节点。我认为后者相当慢。而 epoch 则是节点本地的，全局数据结构会在每次搜索时递增 epoch。所以在每次搜索的上下文中，我们可以确定能找到小于等于当前 epoch 的 epoch，而当前 epoch 可用于标记已访问节点。

但有了线程，就会有多个搜索同时发生！是的，我需要的是一组 epoch 数组：

typedef struct hnswNode {
    uint32_t level;         /* Node's maximum level */
    … many other stuff …
    uint64_t visited_epoch[HNSW_MAX_THREADS];
}

这就是你在 hnsw.h 中能看到的内容。这同样是空间与时间的权衡，而时间再次战胜了空间。

那，有线程的写入是怎么实现的呢？诀窍在于，在 HNSW 插入过程中，大量时间都花在寻找候选邻居上。所以写入被拆成读取阶段和提交阶段，只有第二阶段需要写锁，并且有一些技巧来确保如果 HNSW 在此期间发生了变化，我们在第一阶段累积的候选会在需要时被丢弃，有些节点可能已不再有效。还有另一个问题。如果用户在后台线程正在处理值的时候删除了键，会怎么样？针对这种情况，我们有一个函数，会在真正回收对象之前等待后台操作返回。有了这些技巧，在真实世界的向量负载上很容易达到每秒 5 万次操作，而且这些数字来自 redis-benchmark 本身，包含了所有开销。而扁平 HNSW 库本身的原始数字要高得多。

扩展内存：正确地回收

在讨论如何通过多实例将 HNSW 扩展到大规模用例、以及为什么 Redis Vector Sets 要把实际的数据结构直接暴露给用户之前（我相信程序员很聪明，不需要过度保护，但不仅仅是这个原因），我想回到内存再聊聊，因为关于这个方面有一个有趣的故事。

大多数 HNSW 实现在从图中删除节点时无法直接回收内存。我认为主要有两个原因：

1. 人们以特定方式误解了原始 HNSW 论文：他们认为邻居之间的链接可以*不*是双向的。而他们之所以这么想，有一个具体原因。

2. 论文完全没有说明节点的删除以及在节点消失、连接“网络”出现缺口后如何修复图。

第一个问题是（我认为）论文表述不够清晰，以及在实现 HNSW 时人们会面临一个具体问题：当插入新节点并在现有节点中搜索合适的邻居时，候选节点往往已经拥有最大数量的出链。这时该怎么办？这个问题通常通过从我们正在插入的新节点到那些出链已“满”的候选节点进行单向链接来解决。然而，当你需要删除一个节点时，你就无法解析它的所有入链，所以你无法真正回收内存。你用一个标志把它标记为已删除，之后有时会重建图来“垃圾回收”陈旧节点，有时则只是让内存泄漏。

所以，首先，Redis 中的实现以不同的方式处理，强制链接是双向的。如果 A 链接到 B，B 就链接到 A。但是，考虑到 A 可能很忙，该怎么做呢？嗯，这会进入复杂的领域，但做法是使用启发式方法，从现有节点中丢弃与其连接良好的其他邻居的链接，并且如果我们的节点即使对目标节点来说也是更好的候选，就进行替换；如果不是这样，也有其他方法来强制新节点至少拥有最少数量的链接，始终尽量满足图的小世界特性。

这样，当 Redis 从 Vector Set 中删除一个节点时，它总是有办法移除所有指向它的指针。然而，对于剩下那些现在缺少一条链接的节点该怎么办？我会为它们创建一个距离矩阵，尝试将旧节点的邻居彼此连接起来，尽量最小化平均距离。基本上，对于我们矩阵中的每一对 i、j 节点，我们会计算连接它们有多好（它们的向量有多相似）以及连接它们会对*剩余*可能的配对造成多坏的影响（因为如果我们连接某两个特定节点，可能会有元素找不到好的配对）。构建这个分数矩阵后，我们会进行贪心配对步骤。

这效果非常好，以至于你可以构建一个包含数百万元素的大型 HNSW，之后删除其中 95% 的元素，剩余的图仍然具有良好的召回率，没有孤立节点等等。

这就是我所说的 HNSW 仍有空间供新论文继续研究的含义。

将 HNSW 扩展到多进程

当我开始做 Redis Vector Sets 时，在 Redis 领域已经有了一个向量相似度实现，具体是作为 RediSearch 的一种索引类型，而这也是大多数人对 HNSW 的看法：一种对现有数据的索引形式。

然而，我想为 Redis 提供一种以完全不同方式暴露的全新 HNSW 实现。猜猜是怎么做的？当然是作为一种数据结构。这说明了我的头脑在这么多年后是多么“Redis 式”，或者也许从一开始就是 Redis 式的，而 Redis 是按我的头脑来塑造的——因为我立刻就构想出如何设计一种能直接向用户暴露 HNSW 的 Redis 数据结构，并且我很困惑为什么 Redis 中对向量的处理不是那样做的。

与此同时，当我把设计文档交给 Redis 的同事时，我不能说他们立刻就觉得这是显而易见的事。我的推理是：向量就像 Redis 有序集合中的分数，只不过它们不是具有全序的标量分数。然而你可以 VADD、VREM 元素，然后可以调用 VSIM 而不是 ZRANGE 来获得*相似*的元素。这不仅在 API 上说得通，而且我认为 HNSW 具有很强的可组合性，并不局限于特定用例（不特定于文本嵌入、图像嵌入，甚至不一定是*学习得到的*嵌入）。你可以这样做：

VADD my_vector_set VALUES [… components …] my_element_string

所以无论你的分量里是什么，Redis 都不在乎，当你调用 VSIM 时它会报告相似的元素。

但这也意味着，如果你在不同实例／键中分散存储了关于同一用例的不同向量，你可以对所有实例用相同的查询向量请求 VSIM，并加上 WITHSCORES 选项（它会返回余弦距离），然后在客户端合并结果，你就神奇地将数亿向量扩展到了多个实例中，将数据集拆分了 N 份[关于这种用例，一个有趣的地方是，如果你的客户端库足够智能，你可以使用多路复用并行查询 N 个实例]。

关于以这种原始方式暴露 HNSW，另一个非常值得注意的地方是，你可以非常轻松地扩展写入。只需将你的元素哈希后对 N 取模，然后定位到对应的 Redis 键／实例。多个实例可以同时吸收（虽慢但按 HNSW 标准仍算快的）写入，并行化这个本就非常缓慢的过程。

这种暴露 HNSW 的方式在*向下*扩展时也非常显著：有时你想为每个用户／物品／产品／你正在处理的任何对象都维护一个 HNSW。如果你的 HNSW 是构建在某种东西之上的索引，这很难建模，但如果你的 HNSW 是数据结构，那就很简单了。你只需为每个物品维护一个 Vector Set 键，里面只有少量元素。当然，就像任何其他 Redis 键一样，你可以为键设置过期时间，让它稍后自动被移除。

所有这些都可以凝练成一条我认为在我们行业中应该更常见的规则：许多程序员都很聪明，如果你不是创建一个他们无法触及的魔法系统，而是向他们展示数据结构、展示权衡，他们就能构建更多东西，并以特定方式为自己的用例建模。而你的系统也会更简单。

扩展加载时间

如果我不使用多线程，我的 HNSW 库在单个线程下能以每秒 5000 个元素的速度将 word2vec（每个向量 300 个分量）添加到 HNSW 中，并且能以每秒 9 万次查询的速度查询最终的 HNSW。如你所见，两者差距很大。

这意味着，如果我们以最简单的方式将 HNSW 从 Redis 转储文件加载回内存——即在磁盘上存储“元素,向量”然后尝试在内存中重建 HNSW——加载包含数百万元素的 HNSW 会花费很长时间。而这个时间也会影响复制。不太好。但是，只有当我们以最平凡的方式把元素从磁盘添加到内存时，这才是真的。这里还有另一个教训。当你使用 HNSW 时，你需要按原样序列化节点和邻居，这样你就可以在内存中重建一切，只需分配内存并将邻居 ID 转换为指针。这带来了 100 倍的加速。

但你真的以为故事到这里就结束了吗？嘿嘿。最近 Redis 拥有更强的安全特性，即使 RDB 文件被攻击者破坏，也会避免做坏事。所以我需要确保无论序列化数据结构中出现什么错误和损坏，HNSW 在加载后都是有效的。这涉及许多技巧，但我想在这里自由地贴出我写的一段注释，因为我觉得其中关于双向检查的部分特别酷：

/* Second pass: fix pointers of all the neighbors links.
 * As we scan and fix the links, we also compute the accumulator
 * register "reciprocal", that is used in order to guarantee that all
 * the links are reciprocal.
 *
 * This is how it works, we hash (using a strong hash function) the
 * following key for each link that we see from A to B (or vice versa):
 *
 *      hash(salt || A || B || link-level)
 *
 * We always sort A and B, so the same link from A to B and from B to A
 * will hash the same. Then we xor the result into the 128 bit accumulator.
 * If each link has its own backlink, the accumulator is guaranteed to
 * be zero at the end.
 *
 * Collisions are extremely unlikely to happen, and an external attacker
 * can't easily control the hash function output, since the salt is
 * unknown, and also there would be to control the pointers.
 *
 * This algorithm is O(1) for each node so it is basically free for
 * us, as we scan the list of nodes, and runs on constant and very
 * small memory. */

扩展用例：JSON 过滤器

我记得第一个可用的 Vector Sets 实现感觉上已经完成的那一天。一切都按预期工作，这是一个开始进行细化和增加额外功能的起点。

然而在过去几周和几个月里，我在内部收到反馈说大多数用例需要某种混合搜索：你想查询与给定查询向量相近的向量（比如与某物最相似的电影），但也需要某种过滤（比如只限 2000 到 2010 年间上映的）。我的感觉是，你需要按不同参数查询的频率并没有产品人员认为的那么高，而且在很多时候，通过为这个具体例子中每一年使用不同的向量集键，可以更高效地获得结果（这又是将 HNSW 作为数据结构而非某种索引来表达其可组合性的另一个例子）。

不过我一直在想 HNSW 贪心搜索的主循环，它大概是这样的：

// Simplified HNSW greedy search algorithm. Don’t trust it too much.
while(candidates.len() > 0) {
    c = candidates.pop_nearest(query);
    worst_distance = results.get_worst_dist(query);
    if (distance(query,c) > worst_distance) break;
    foreach (neighbor from c) {
        if (neighbor.already_visited()) continue;
        neighbor.mark_as_visited();
        if (results.has_space() OR neighbor.distance(query) < worst_distance) {
            candidates.add(neighbor);
            results.add(neighbor);
        }
    }
}
return results;

所以我开始尝试为每个节点添加一组 JSON 元数据的想法。如果一旦有了像 {“year”: 1999} 这样的东西，这是否就足以在执行贪心搜索时进行过滤？当然，搜索需要是有界的，但这里有一个关键洞见：我首先想要的是与查询向量*相近*的元素，所以如果满足 JSON 属性条件的节点不多，我其实不需要探索整个图。我会让用户指定工作量，而且无论如何，非常远但满足过滤条件的结果是没有用的。

所以这又是我的 HNSW 与众不同的另一个地方：它支持通过类似于你在编程语言 if 语句中可写的表达式来过滤。而 Vector Set 中的元素可以关联 JSON 块来表达它们的属性。然后你可以这样做：

VSIM movies VALUES … your vector components here… FILTER '.year >= 1980 and .year < 1990'

关于内存使用的几句话

HNSW 在理论上的致命问题是——它们通常是从内存中提供服务的。实际上，你可以在磁盘上实现 HNSW，即使从磁盘访问延迟的角度来看有更好的数据结构。然而，在 Redis 和 Vector Sets 的具体场景中，想法是提供一种非常快速、易于使用的东西：内存数据结构的灵活性有助于实现这一点。所以问题归结为：内存使用真的那么糟糕吗？

将 300 万条 Word2Vec 条目以默认的 int8 量化加载到 Redis 中需要 3GB 内存，每个条目 1KB。许多用例只有几千万条目，甚至更少。而你从 HNSW 获得的回报，如果实现得好且在内存中，是非常好的性能，这在本身就按定义很慢的数据结构和工作负载中至关重要。在我的 MacBook 上，用 redis-benchmark 对持有 word2vec 数据集的键执行 VSIM，我能得到每秒 4.8 万次操作。我的感觉是，对于许多用例来说，内存中 HNSW 的内存使用是非常可接受的。即使在你想将大部分向量放在磁盘上的用例中，即便要付出更慢性能的代价，你的热集也可能应该从内存中提供。

这也是我认为投身 HNSW 研究是个好主意的原因之一：我认为它们在短期内不会被大多数用例的其他结构所取代。我们更有可能继续根据用例和数据大小，拥有分别适用于内存和磁盘的不同理想数据结构。此外，我最近即使只是浏览 Hacker News 首页，也看到有人用几百万条数据在与比必要更慢或更复杂的系统搏斗。HNSW 并以正确的方式谨慎地暴露它们，可以避免所有这些麻烦。

结论

我喜欢 HNSW，实现它们是一件非常愉快的事。我认为向量非常适合 Redis，即使在一个没有 AI 的世界里（例如，几个月前我用它们来为 Hacker News 用户做指纹识别，复现了过去发表在 HN 上的一项工作）。HNSW 对于许多用例来说实在是太酷、太强大了，而有了 AI 和学习得到的嵌入，所有这些都扩展到无数的潜在用例。然而，像 Redis 中的大多数功能一样，我预计人们要过很长时间才会意识到它们是有用且强大的，以及该如何使用它们（不，这不仅仅是 RAG 的问题）。Streams 也是如此：经过这么多年，终于迎来了大规模采用。

如果你对 HNSW 及其实现更感兴趣，我认为代码是相当易读的，并且有大量注释：

https://github.com/redis/redis/blob/unstable/modules/vector-sets/hnsw.c

如果你想了解更多关于 Redis Vector Sets 的信息，请随意阅读我亲自写的 README 文件。这里也有官方 Redis 文档，但我建议你从这里开始：

https://github.com/redis/redis/tree/unstable/modules/vector-sets

感谢你阅读这么长的博客文章！祝你有愉快的一天。

参考文献。本文是关于 HNSW 中“H”有多有用的论文 -> https://arxiv.org/abs/2412.01940