当前位置：首页 > article >正文

Elasticsearch：加快 HNSW 图的合并速度

article 2026/1/29 11:31:58

作者：来自 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 系数的原因。接下来我们将展示，如何通过利用所有参与合并的图中的信息，显著提高这一过程的效率。

图合并

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

我们专注于将一个较小的图 $G_s = (V_s, E_s)$ 插入到一个较大的图 $G_l = (V_l, E_l)$ 的问题，因为这是一个原子操作，我们可以用它来构建任何合并策略。

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

我们使用下文将讨论的一个过程（第1行）来计算集合 $J$ 。然后，使用标准的 HNSW 插入过程（第2行）将 $J$ 中的每个顶点插入到大图中。对于尚未插入的每个顶点，我们会找到其已插入的邻居及这些邻居在大图中的邻居（第 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$ ，其中 $k_u < M$ ，即最大层连接数。我们观察到，在实际的 HNSW 图中，顶点度数的分布差异很大。下图展示了 Lucene HNSW 图底层中顶点度数的典型累计密度函数。

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

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

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

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

这意味着：

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

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

计算连接集

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

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

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

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

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

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

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

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

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

请注意，我们只需要跟踪我们已添加到 $J$ 中的顶点的总增益，以决定何时退出。此外，尽管 $\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

Elasticsearch：加快 HNSW 图的合并速度

作者：来自 Elastic Thomas Veasey 及 Mayya Sharipova 过去，我们曾讨论过搜索多个 HNSW 图时所面临的一些挑战，以及我们是如何缓解这些问题的。当时，我们也提到了一些计划中的改进措施。本文正是这项工作的成果汇总。你可能会问…...

编程日记 2026/1/26 3:51:37

图片中文字无法正确显示的解决方案

图片中文字无法正确显示的解决方案问题描述在 Linux 系统中生成图片时，图片中的文字（如中文）未能正确显示，可能表现为乱码或空白。这通常是由于系统缺少对应的字体文件（如宋体/SimSun），或者…...

编程日记 2026/1/26 16:45:05

数据结构：通俗解释AOE 网中事件的最早发生时间和最迟发生时间

1. 事件的最早发生时间在 AOE 网（Activity On Edge Network，边表示活动的网络）中，事件的最早发生时间指从源点（起点）到该事件结点的最长路径长度（即所需时间）。它决定了所有以该事…...

编程日记 2025/7/12 18:28:19

C# 看门狗策略实现

using System; using System.Threading;public class Watchdog {private Timer _timer;private volatile bool _isTaskAlive;private readonly object _lock new object();private const int CheckInterval 5000; // 5秒检测一次private const int TimeoutThreshold 10000; …...

编程日记 2025/9/13 22:55:02

在 openEuler 24.03 (LTS) 操作系统上添加 ollama 作为系统服务的步骤

以下是在 openEuler 操作系统上添加 ollama 作为系统服务的步骤： 创建 systemd 服务文件 sudo vi /etc/systemd/system/ollama.service将以下内容写入服务文件（按需修改参数）： [Unit] DescriptionOllama Service Afternetwork.…...

编程日记 2026/1/28 11:30:23

Elasticsearch中的基本全文搜索和过滤

Elasticsearch中的基本全文搜索和过滤知识点参考: https://www.elastic.co/guide/en/elasticsearch/reference/current/full-text-filter-tutorial.html#full-text-filter-tutorial-range-query 1. 索引设计与映射多字段类型（Multi-Fields） &#xff…...

编程日记 2026/1/19 16:44:57

基于VSCode的Qt开发‘#include ui_test.h’报错没有该文件

笔者在基于VSCode进行Qt开发时，test.ui文件是在Qt软件中绘制的，导致本项目无法使用这个ui文件，报错如标题。事实上，本工程中也确实没有生成这个头文件。出现这个错误的原因是ui文件没有被编译为c头文件。要生成 ui_test.h 文件&…...

编程日记 2025/9/1 6:42:19

Python常用排序算法

1. 冒泡排序冒泡排序是一种简单的排序算法，它重复地遍历要排序的列表，比较相邻的元素，如果他们的顺序错误就交换他们。 def bubble_sort(arr):# 遍历所有数组元素for i in range(len(arr)):# 最后i个元素是已经排序好的for j in range(0, …...

编程日记 2025/9/1 0:52:13

ISP--Demosaicking

文章目录前言算法解释简单的线性插值代码实现色差法和色比法基于方向加权的方法RB缺失的G通道的插值RB缺失的BR的插值G缺失的BR的插值代码实现基于边缘检测的方法计算缺失的G计算缺失的RB值/计算缺失的G值前言人眼之所以有能感受到自然界的颜色，是因为人眼的感…...

编程日记 2026/1/27 0:07:49

国标GB28181协议EasyCVR视频融合平台：5G时代远程监控赋能通信基站安全管理

一、背景介绍随着移动通信行业的迅速发展，无人值守的通信基站建设规模不断扩大。这些基站大多建于偏远地区，周边人迹罕至、交通不便，给日常的维护带来了极大挑战。其中，位于空旷地带的基站设备，如空调、蓄电池等&…...

编程日记 2026/1/26 11:44:31

vue watch 和 watchEffect的区别和用法

在 Vue.js 里，watch 和 watchEffect 都用于响应式地追踪数据变化并执行相应操作，不过它们在使用方式、应用场景等方面存在差异。 1. watch watch 是 Vue 提供的一个选项，用于监听特定数据的变化。当监听的数据发生变化时，会触发…...

编程日记 2025/6/23 16:55:05

SQL 不走索引的常见情况

在 SQL 查询中，即使表上有索引，某些情况下数据库优化器也可能决定不使用索引。以下是常见的不走索引的情况： 1. 使用否定操作符 NOT IN ! 或 <> NOT EXISTS NOT LIKE 2. 对索引列使用函数或运算 -- 不走索引 SELECT * FROM user…...

编程日记 2025/9/1 10:06:44

git配置 gitcode -- windows 系统

版本 $ git --version git version 2.49.0.windows.1检查现有的 SSH 密钥打开git-bash终端，执行以下命令查看是否已经生成过 SSH 密钥： ls -al ~/.ssh如果看到类似 id_rsa 和 id_rsa.pub（或者其他命名的密钥对）文件&#xff0…...

编程日记 2025/9/1 5:46:32

基于Kubeadm实现K8S集群扩缩容指南

一、集群缩容操作流程 1.1 缩容核心步骤驱逐节点上的Pod 执行kubectl drain命令驱逐节点上的Pod，并忽略DaemonSet管理的Pod： kubectl drain <节点名> --ignore-daemonsets # 示例：驱逐worker233节点 kubectl drain worker233 --ignor…...

编程日记 2025/9/1 17:01:56

模拟-与-现实协同训练：基于视觉机器人操控的简单方法

25年3月来自 UT Austin、Nvidia、UC Berkeley 和纽约大学的论文“Sim-and-Real Co-Training: A Simple Recipe for Vision-Based Robotic Manipulation”。大型现实世界机器人数据集在训练通才机器人模型方面拥有巨大潜力，但扩展现实世界人类数据收集既耗时又耗资…...

编程日记 2026/1/27 8:09:05

WRS-PHM电机智能安康系统：为浙江某橡胶厂构筑坚实的生产防线

以行业工况为背景一、顾客工厂的背景浙江某橡胶厂以电机为中心生产设备必须连续平稳运行。但由于缺乏有效的故障预警体系，电机故障就像潜伏着的“不定时炸弹”,不但不时地造成生产流程的中断，也使对生产进行管理异常艰难，对持续安全生产提…...

编程日记 2026/1/27 7:04:18

将 CrewAI 与 Elasticsearch 结合使用

作者：来自 Elastic Jeffrey Rengifo 学习如何使用 CrewAI 为你的代理团队创建一个 Elasticsearch 代理，并执行市场调研任务。 CrewAI 是一个用于编排代理的框架，它通过角色扮演的方式让多个代理协同完成复杂任务。如果你想了解更多关于代理…...

编程日记 2026/1/27 2:34:58

wait 和notify ，notifyAll，sleep

wait 使线程进入阻塞状态，释放CPU，以及锁 sleep 使线程进入睡眠状态，sleep方法不会释放CPU资源和锁资源，而是让出CPU的使用权。操作系统会将CPU分配给其他就绪线程，但当前线程依然存在，不会释放其占用的…...

编程日记 2025/9/2 12:54:50

ECMAScript 6 新特性（二）

ECMAScript 6 新特性（二） ECMAScript 6 新特性（一） ECMAScript 6 新特性（二）（本文） ECMAScript 7~10 新特性 1. 生成器生成器函数是 ES6 提供的一种解决异步编程方案，一…...

编程日记 2025/11/8 14:33:58

SpringBoot接口覆盖上一次调用的实现方案

调用springboot接口时，如何实现覆盖上一次调用 Spring Boot 接口覆盖上一次调用的实现方案以下是多种实现覆盖上一次接口调用的方案，适用于不同场景。方案一：同步锁控制（单机环境） 适用场景‌：单实例…...

编程日记 2025/12/26 11:55:47

Spring 的 IoC 和 DI 详解：从零开始理解与实践

Spring 的 IoC和 DI 详解：从零开始理解与实践一、IoC（控制反转） 1、什么是 IoC？ IoC 是一种设计思想，它的核心是将对象的创建和管理权从开发者手中转移到外部容器（如 Spring 容器）。通过这种…...

编程日记 2026/1/28 23:17:07

Python Cookbook-5.12 检查序列的成员

任务你需要对一个列表执行很频繁的成员资格检査。而in操作符的 O(n)时间复杂度对性能的影响很大，你也不能将序列转化为一个字典或者集合，因为你还需要保留原序列的元素顺序。解决方案假设需要给列表添加一个在该列表中不存在的元素。一个可行的方法…...

编程日记 2025/9/19 16:52:44

签名过期怎么办？

1无论是证书到期还是被封停，只需要找到签名服务商，重新签名就可以了，但签名经常性过期会造成app用户流失，所以我们在选择签名时需要注意，在资金充足的情况下，优先选择独立、稳定签名，接下来我们…...

编程日记 2025/9/1 22:10:41

ZYNQ笔记（四）：AXI GPIO

版本：Vivado2020.2（Vitis） 任务：使用 AXI GPIO IP 核实现按键 KEY 控制 LED 亮灭（两个都在PL端） 一、介绍 AXI GPIO (Advanced eXtensible Interface General Purpose Input/Output) 是 Xilinx 提供的一个可…...

编程日记 2026/1/28 5:06:15

实操（环境变量）Linux

环境变量概念我们用语言写的文件编好后变成了程序，./ 运行的时候他就会变成一个进程被操作系统调度并运行，运行完毕进程相关资源被释放，因为它是一个bash的子进程，所以它退出之后进入僵尸状态，bash回收他的退出结果&…...

编程日记 2026/1/28 16:17:22

【补题】P9423 [蓝桥杯 2023 国 B] 数三角

题意：小明在二维坐标系中放置了 n 个点，他想在其中选出一个包含三个点的子集，这三个点能组成三角形。然而这样的方案太多了，他决定只选择那些可以组成等腰三角形的方案。请帮他计算出一共有多少种选法可以组成等腰三角形&#xff…...

编程日记 2025/9/1 23:05:29

Word / WPS 页面顶部标题段前间距失效 / 不起作用 / 不显示，标题紧贴页眉问题及解决

问题描述： 在 Word 或者 WPS 里面，如果不是新的一节，而是位于新的一页首行时，不管怎么设置段前间距，始终是失效的，实际段前间距一直是零。解决方案： 查询了很多方案均无法解决问题&#xff…...

编程日记 2026/1/28 0:00:39

Mysql自动增长数据的操作（修改增长最大值）

在MySQL中，如果你想要修改一个表的自增长（auto-increment）属性的起始值，可以使用ALTER TABLE语句。这对于初始化新环境或修复损坏的自增长计数器特别有用。下面是如何操作的一些步骤： 查看当前自增长值首先&#xff…...

编程日记 2025/9/1 15:07:53

Linux自行实现的一个Shell(15)

文章目录前言一、头文件和全局变量头文件全局变量二、辅助函数获取用户名获取主机名获取当前工作目录获取最后一级目录名生成命令行提示符打印命令行提示符三、命令处理获取用户输入解析命令行执行外部命令四、内建命令添加环境变量检查和执行内建命令五、初始化初始化环境…...

编程日记 2026/1/28 4:25:59

在 Q3D 中提取汇流条电感

汇流条排简介和设计注意事项汇流条排是用于配电的金属导体，在许多应用中与传统布线相比具有设计优势。在设计母线排时，必须考虑几个重要的因素： 低电感：高频开关内容会导致无功损耗，从而降低效率电容：管…...

编程日记 2026/1/28 3:14:27

背景

图合并

计算连接集

结果

实验 1：int8 量化

实验 2：BBQ 量化

结论

相关文章：