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

图合并

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

我们专注于将一个较小的图

该策略是找到一个小图中顶点的子集 

我们使用下文将讨论的一个过程（第1行）来计算集合

显然，为了使这个过程有效，每个

我们尝试了使用固定值的

请注意，

一个简单的计数论证表明，如果我们仔细选择

这里，

这意味着：

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

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

计算连接集

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

在这里，

我们为每个顶点

• 是否过时（stale）

• 它的增益

• 在

  中相邻顶点的计数，记作 

• 一个在 [0, 1] 范围内的随机数，用于打破平局。

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

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

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

1. 由于它的所有邻居在

   中有了额外的邻居，它们的增益可能会发生变化（第14行）。

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

我们以懒惰的方式重新计算增益，因此只有在我们要将一个顶点插入到

请注意，我们只需要跟踪我们已添加到

结果

我们在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