Elasticsearch：加快 HNSW 图的合并速度-低调大师

Elasticsearch：加快 HNSW 图的合并速度

2025-04-27 148

作者：来自 Elastic Thomas Veasey 及 Mayya Sharipova

过去，我们曾讨论过搜索多个 HNSW 图时所面临的一些挑战，以及我们是如何缓解这些问题的。当时，我们也提到了一些计划中的改进措施。本文正是这项工作的成果汇总。

你可能会问，为什么要使用多个图？这是 Lucene 中架构选择的一个副作用：不可变段（immutable segments）。正如大多数架构决策一样，它既有优点也有缺点。例如，我们最近正式发布了无服务器版本的 Elasticsearch。在这个背景下，我们从不可变段中获得了非常显著的优势，包括高效的索引复制、索引计算与查询计算的解耦，以及它们各自的自动扩展能力。对于向量量化，段合并让我们有机会更新参数，以更好地适应数据特性。在这个方向上，我们认为通过测量数据特性并重新评估索引选择，还可以带来其他优势。

本文将探讨我们为显著减少构建多个 HNSW 图的开销，特别是为了降低图合并成本所做的工作。

背景

为了保持可管理的段（segment）数量，Lucene 会定期检查是否需要合并段。这基本上是检查当前段数量是否超过了一个由基础段大小和合并策略决定的目标段数。如果超过了这个限制，Lucene 就会将若干段合并，直到约束条件不再被违反。这个过程在其他文档中已有详细描述。

Lucene 倾向于合并相似大小的段，因为这样可以实现写放大的对数增长。对于向量索引来说，写放大指的是同一个向量被插入图的次数。Lucene 通常尝试将大约 10 个段合并成一组。因此，向量大约会被插入图 1 + 9/10 × log₁₀(n/n₀) 次，其中 n 是索引中的总向量数量，n₀ 是每个基础段的预期向量数量。由于这种对数增长，即便在非常大的索引中，写放大仍能保持在个位数。然而，合并图所花费的总时间与写放大呈线性关系。

在合并 HNSW 图时，我们已经采用了一个小的优化：保留最大段的图，并将其他段的向量插入这个图。这就是上述公式中 9/10 系数的原因。接下来我们将展示，如何通过利用所有参与合并的图中的信息，显著提高这一过程的效率。

图合并

之前，我们保留了最大的图，并插入了其他图中的向量，忽略了包含它们的图。我们在下面利用的关键见解是，每个我们丢弃的图包含了它所包含的向量的相似性信息。我们希望利用这些信息来加速插入至少一部分向量。

我们专注于将一个较小的图插入到一个较大的图的问题，因为这是一个原子操作，我们可以用它来构建任何合并策略。

该策略是找到一个小图中顶点的子集 $J \subset V_s$ 来插入到大图中。然后，我们利用这些顶点在小图中的连接性来加速插入剩余的顶点 $V_s \setminus J$ 。以下我们用和分别表示小图和大图中顶点的邻居。该过程的示意如下。

我们使用下文将讨论的一个过程（第1行）来计算集合。然后，使用标准的 HNSW 插入过程（第2行）将中的每个顶点插入到大图中。对于尚未插入的每个顶点，我们会找到其已插入的邻居及这些邻居在大图中的邻居（第 4 和第 5 行）。接着，使用以这个集合为种子的 FAST-SEARCH-LAYER 过程（第 6 行），从 HNSW 论文中的 SELECT-NEIGHBORS-HEURISTIC 中找到候选集合（第 7 行）。实际上，我们是在替换 INSERT 方法（论文中的算法1）中的 SEARCH-LAYER 过程，其他部分保持不变。最后，将刚插入的顶点加入集合 J（第8行）。

显然，为了使这个过程有效，每个 $V_s \setminus J$ 中的顶点必须至少有一个邻居在 J 中。实际上，我们要求对于每个 $u \in V_s \setminus J$ ，都有 $|J \cap N_s(u)| \geq k_u$ ，其中，即最大层连接数。我们观察到，在实际的 HNSW 图中，顶点度数的分布差异很大。下图展示了 Lucene HNSW 图底层中顶点度数的典型累计密度函数。

我们尝试了使用固定值的和将其设为顶点度数的函数这两种方法。第二种选择带来了更大的加速，并对召回率的影响较小，因此我们选择了以下公式：

请注意，是顶点在小图中的度数。设定下限为 2 意味着我们将插入所有度数小于 2 的顶点。

一个简单的计数论证表明，如果我们仔细选择，我们只需要直接将约 $\frac{1}{5}|V_s|$ 的顶点插入到大图中。具体而言，我们对图的边进行着色，如果我们将它的一个端点插入到中。然后我们知道，为了确保 $V_s \setminus J$ 中的每个顶点都有至少个邻居在 J 中，我们需要着色至少 $\sum_{u \in V_s \setminus J} k_u$ 条边。此外，我们预期：

这里，是小图中顶点的平均度数。对于每个顶点 $u \in J$ ，我们最多会着色条边。因此，我们预期着色的总边数最多为 $|J| \, E_U[|N_s(U)|]$ 。我们希望通过仔细选择，能够着色接近这个数量的边。因此，为了覆盖所有的顶点， $\left| J \right|$ 需要满足：

这意味着：

提供 SEARCH-LAYER 支配了运行时间，这表明我们可以在合并时间上实现最多 5 倍的加速。考虑到写入放大效应的对数增长，这意味着即使对于非常大的索引，我们的构建时间通常也仅仅是构建一个图时的两倍。

这种策略的风险在于我们可能会损害图的质量。最初，我们尝试了一个无操作的 FAST-SEARCH-LAYER。我们发现这会导致图质量下降，特别是在合并到单个段时，召回率作为延迟的函数会降低。然后我们探索了使用有限图搜索的各种替代方案。最终，最有效的选择是最简单的。使用 SEARCH-LAYER，但设置一个较低的 ef_construction。通过这种参数设置，我们能够在保持优良图质量的同时，减少约一半的合并时间。

计算连接集

找到一个好的连接集可以表述为一个图覆盖问题。贪心启发式算法是一种简单有效的启发式方法，用于逼近最优的图覆盖。我们采用的方法是使用贪心启发式算法，一次选择一个顶点将其加入到中，使用以下定义的每个候选顶点的增益：

在这里，表示向量在中的邻居数量， $1_{\{\cdot\}}$ 是指示函数。增益包括我们加入到中的顶点的邻居数量变化，即 $\max(k_v - c(v), 0)$ ，因为通过加入一个覆盖较少的顶点，我们可以获得更多的增益。增益计算在下图中对于中央橙色节点进行了说明。

我们为每个顶点维护以下状态：

是否过时（stale）
它的增益 $\text{Gain}(v)$
在中相邻顶点的计数，记作
一个在 [0, 1] 范围内的随机数，用于打破平局。

计算加入集合的伪代码如下。

我们首先在第 1-5 行初始化状态。

在主循环的每次迭代中，我们首先提取最大增益的顶点（第 8 行），并在存在平局时随机打破平局。在做任何修改之前，我们需要检查该顶点的增益是否过时。特别地，每次我们将一个顶点添加到中时，会影响其他顶点的增益：

由于它的所有邻居在中有了额外的邻居，它们的增益可能会发生变化（第14行）。
如果它的任何邻居现在已经完全覆盖，那么它们所有邻居的增益都可能发生变化（第14-16行）。

我们以懒惰的方式重新计算增益，因此只有在我们要将一个顶点插入到中时，才会重新计算该顶点的增益（第18-20行）。

请注意，我们只需要跟踪我们已添加到中的顶点的总增益，以决定何时退出。此外，尽管 $\text{Gain}_{\text{tot}} < \text{Gain}_{\text{exit}}$ ，至少会有一个顶点具有非零增益，因此我们始终会取得进展。

结果

我们在4个数据集上进行了实验，涵盖了我们支持的三种距离度量（欧几里得、余弦和内积），并采用了两种类型的量化方法：1）int8 —— 每个维度使用1字节的整数；2）BBQ —— 每个维度使用一个比特。

实验 1：int8 量化

从基准到候选方案（提出的改进）的平均加速比为：

索引时间加速：1.28×
强制合并加速：1.72×

这对应于以下运行时间的划分：

为了完整性，以下是各项时间数据：

quora-E5-small; 522931 文档；384 维度；余弦度量
基准：索引时间：112.41s，强制合并：113.81s
候选：索引时间：81.55s，强制合并：70.87s
cohere-wikipedia-v2; 100万文档；768 维度；余弦度量
基准：索引时间：158.1s，强制合并：425.20s
候选：索引时间：122.95s，强制合并：239.28s
gist; 960 维度，100万文档；欧几里得度量
基准：索引时间：141.82s，强制合并：536.07s
候选：索引时间：119.26s，强制合并：279.05s
cohere-wikipedia-v3; 100万文档；1024 维度；内积度量
基准：索引时间：211.86s，强制合并：654.97s
候选：索引时间：168.22s，强制合并：414.12s

下面是与基准进行对比的召回率与延迟图，比较了候选方案（虚线）与基准在两种检索深度下的表现：recall@10 和 recall@100 ，分别针对具有多个分段的索引（即索引所有向量后默认合并策略的最终结果）以及强制合并为单个分段的索引。曲线越高且越靠左表示性能越好，这意味着在较低的延迟下获得更高的召回率。

从下面的图表可以看出，在多个分段索引上，候选方案在 Cohere v3 数据集上的表现更好，对于其他所有数据集，曲线稍差但几乎可比。当合并为单个分段后，所有数据集的召回曲线几乎相同。

实验 2：BBQ 量化

从基准到候选方案的平均加速比为：

索引时间加速：1.33×
强制合并加速：1.34×

以下是具体的细分：

为完整性考虑，以下是时间数据：

quora-E5-small; 522931 个文档; 384 维度; 余弦度量
基准：索引时间：70.71秒，强制合并：59.38秒
候选方案：索引时间：58.25秒，强制合并：40.15秒
cohere-wikipedia-v2; 100 万个文档; 768 维度; 余弦度量
基准：索引时间：203.08秒，强制合并：107.27秒
候选方案：索引时间：142.27秒，强制合并：85.68秒
gist; 960 维度，100 万个文档; 欧氏度量
基准：索引时间：110.35秒，强制合并：323.66秒
候选方案：索引时间：105.52秒，强制合并：202.20秒
cohere-wikipedia-v3; 100 万个文档; 1024 维度; 内积度量
基准：索引时间：313.43秒，强制合并：165.98秒
候选方案：索引时间：190.63秒，强制合并：159.95秒

从多个段索引的图表可以看到，候选方案在几乎所有数据集上表现更好，除了 cohere v2 数据集，基准略优。对于单个段索引，所有数据集的召回曲线几乎相同。

总的来说，我们的实验涵盖了不同的数据集特征、索引设置和检索场景。实验结果表明，我们能够在保持强大的图质量和搜索性能的同时，实现显著的索引和合并加速，这些结果在各种测试场景中表现一致。

结论

本文讨论的算法将在即将发布的 Lucene 10.2 版本中提供，并将在基于该版本的 Elasticsearch 发布中可用。用户将在这些新版本中受益于改进的合并性能和缩短的索引构建时间。这个变化是我们不断努力使 Lucene 和 Elasticsearch 成为一个快速高效的向量搜索数据库的一部分。

自己亲自体验向量搜索，通过这款自定进度的搜索 AI 实践学习。你可以开始免费的云试用或立即在本地机器上尝试 Elastic。

原文：Speeding up merging of HNSW graphs - Elasticsearch Labs

微信关注我们

原文链接：https://my.oschina.net/u/3343882/blog/18252773

转载内容版权归作者及来源网站所有！

低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。

Kubernetes v1.33 发布，哪些新特性值得你特别关注？

4月23日，K8s v1.33 正式发布，标志着 K8s 迈入了其第二个十年。本次版本发布涵盖了64项增强功能，其中18项已升格为稳定版（Stable），20项进入Beta阶段，24项为Alpha版本，2项被弃用或撤回。这些更新体现了K8s社区在稳定性、可扩展性和安全性方面的持续努力。 K8s v1.33 的主题是"Octarine：魔法的色彩"，灵感来自特里·普拉切特的《碟形世界》系列。此版本重点介绍了K8s 在整个生态系统中实现的开源魔法。如果您熟悉碟形世界，您可能会认出一条小沼泽龙栖息在看不见的大学塔顶，凝视着安科-莫波克市上方的 K8s 月亮，背景中有 64 颗星星。 K8s v1.33 亮点功能 1. Sidecar 容器升级为稳定版 Sidecar 容器模式已成为云原生应用架构中的重要组成部分，广泛应用于日志收集、服务网格和监控等场景。在 v1.33 中，Sidecar 容器正式升格为稳定版，增强了其在 Pod 生命周期管理中的可靠性和一致性。K8s 确保 Sidecar 容器在主应用容器之前启动，并在主容器退出后自动终止，同时支持健康检查和OOM评分调整。 2. Met...

2025-04-25

507

【栏目介绍：“玩转OurBMC”是OurBMC社区开创的知识分享类栏目，主要聚焦于社区和BMC全栈技术相关基础知识的分享，全方位涵盖了从理论原理到实践操作的知识传递。OurBMC社区将通过“玩转OurBMC”栏目，帮助开发者们深入了解到社区文化、理念及特色，增进开发者对BMC全栈技术的理解。欢迎各位关注“玩转OurBMC”栏目，共同探索OurBMC社区的精彩世界。同时，我们诚挚地邀请各位开发者向“玩转OurBMC”栏目投稿，共同学习进步，将栏目打造成为汇聚智慧、激发创意的知识园地。】 iKVM（Integrated Keyboard, Video and Mouse）作为 BMC 的核心功能之一，通过集成硬件和软件，实现对服务器全程全时的远程控制。即在服务器的上电后的任意阶段，如BIOS启动、内核加载、操作系统运行或崩溃等时刻，都能通过 BMC 的iKVM功能，被远端的管理员监控管理。因此，相比于其他的远程控制技术，iKVM 作为服务器的带外远程技术，具有表1 所示不依赖服务器的 BIOS 固件、操作系统、应用程序，能在硬件层面实现全程全时的远程管理目标。表1远程控制技术的特点...

2025-04-27

218

资源下载

更多资源

Mario

马里奥是站在游戏界顶峰的超人气多面角色。马里奥靠吃蘑菇成长，特征是大鼻子、头戴帽子、身穿背带裤，还留着胡子。与他的双胞胎兄弟路易基一起，长年担任任天堂的招牌角色。

Oracle

Oracle Database，又名Oracle RDBMS，或简称Oracle。是甲骨文公司的一款关系数据库管理系统。它是在数据库领域一直处于领先地位的产品。可以说Oracle数据库系统是目前世界上流行的关系数据库管理系统，系统可移植性好、使用方便、功能强，适用于各类大、中、小、微机环境。它是一种高效率、可靠性好的、适应高吞吐量的数据库方案。

Apache Tomcat

Tomcat是Apache 软件基金会（Apache Software Foundation）的Jakarta 项目中的一个核心项目，由Apache、Sun 和其他一些公司及个人共同开发而成。因为Tomcat 技术先进、性能稳定，而且免费，因而深受Java 爱好者的喜爱并得到了部分软件开发商的认可，成为目前比较流行的Web 应用服务器。

Eclipse

Eclipse 是一个开放源代码的、基于Java的可扩展开发平台。就其本身而言，它只是一个框架和一组服务，用于通过插件组件构建开发环境。幸运的是，Eclipse 附带了一个标准的插件集，包括Java开发工具（Java Development Kit，JDK）。