HNSW图：如何提升Elasticsearch性能

Hierarchical Navigable Small World（HNSW）向量搜索的原理在Elasticsearch 8.0中首次引入。但图是如何构建的呢？图的构建对搜索质量有什么影响？这些参数具体有什么作用？

图的搜索

首先，简单回顾一下HNSW图是如何工作的。HNSW图是一种分层的数据结构，遵循以下规则：

• 所有向量都存在于底层（第0层）；每个向量在该层由一个图节点表示。
• 随着层级的上升，向量出现在每层的概率按对数规律减少，因此每层的向量比其下层要少。
• 每个出现在某层的向量会在该层由一个节点表示。所有同一个向量的节点与该向量相关联。
• 如果一个向量出现在某层，它也会出现在所有下层，直至第0层。
• 每层的每个节点都会引用同层一定数量的其他节点，通常是最近的节点（根据向量相似性确定，见下文）。
• 引用是单向的，因此如果节点A引用节点B，节点B不一定引用节点A。

Lucene索引的每个段都有自己独立的HNSW图，仅包含该段中的向量。多个段会独立进行搜索。

无论向量的维数是多少，HNSW图都能正常工作，因为它基于两个向量的相似性进行操作。这通常是余弦相似性或点积（具体示例见这里），具体取决于索引的配置。相似性比较两个n维向量，产生一个数字，指示这些向量的接近程度。创建HNSW图时使用的是这些相似性数值，而不是向量本身。

HNSW图的搜索，通过以下阶段来找到与查询向量最近的k个向量：

1. 搜索从入口节点开始。所有搜索使用同一个节点作为入口节点，该节点是构建过程中添加到图中最顶层的第一个向量。
2. 从入口节点开始遍历最顶层的节点，寻找该层中与查询向量最接近的向量。
3. 找到最接近的向量后，使用该向量作为起点，在下一层搜索更近的向量。
4. 重复这一过程，直到在最低层找到一个入口节点，该层包含所有向量。
5. 搜索最低层入口节点的邻居，递归遍历节点到节点的邻居链接，直到找到最接近的k个向量。

这一切都很好。但图是如何构建的呢？层数由什么决定？为什么召回率不是完美的？

图的构建

图的召回性能完全取决于其构建方式。图构建由两个参数控制：

• M：一个层上的向量节点与邻居的最大连接数（Lucene和Elasticsearch默认值为16）
• ef_construction，也称为beamWidth：kNN搜索的k参数，用于在构建过程中向图中添加新向量时寻找层邻居（Lucene默认值为100）

这些参数对图的构建有很大影响。添加新向量到图中的步骤如下：

1. 确定向量将被添加到的层数。这是基于M值随机化的。向量总是存在于第0层（底层）；向量在更高层出现的概率随着层级升高对数减少，与M成比例。对于默认值16，图通常有3-5层。重要的是，这与图的现有结构无关——任何特定向量存在的最高层完全是随机的。
2. 如果这是图中的第一个节点，或新顶层的第一个节点，它将被设置为图的入口点（无论其在向量空间中的实际位置）
3. 对向量所在的每层进行HNSW搜索，以找到该层中与新向量最近的节点。每层使用的k值是ef_construction参数。
4. 对于每层，创建最多M个与该层最近节点的连接（如果在第0层，则是M*2）。还要创建从现有节点到新节点的反向连接，双向连接考虑多样性（见下文）。

因为每层的向量比其下层要少，但最大链接数相同，因此更高层的向量具有比低层更长范围的链接，有助于从搜索开始时的初始入口点快速遍历向量空间。有关如何加速HNSW进行kNN搜索的更多信息，请参见示例。

多样性

关键问题是——如何选择连接到新节点的节点？简单地说，你会选择M个最近的节点。但如果在同一层有几个向量彼此靠近，这可能导致问题。这些向量可能形成一个团体，与其他节点很少连接。一旦图遍历进入该团体，可能难以脱离，导致次优结果。

为了解决这个问题，创建算法仅向比任何其他邻居节点更接近新节点的节点添加新连接。举个例子：

节点N正在被添加到图中。新连接将从N到A和B创建，因为它们是最近的节点，但不会连接到C，因为C比N更靠近B。随后也会从N的新连接邻居节点返回到N的来连接。这些连接也考虑多样性，相对于现有节点，如果某个节点的连接数已达到上限，则移除现有连接以保持多样性。这些确保节点连接到多样化的其他节点，最大化从图中其他地方的可达性，并最小化完全连接的团体的形成。

但这确实有一个缺点——因为每个节点不一定直接连接到其周围的所有节点，因此搜索该节点的链接邻居不会返回完整结果。这是近似kNN搜索可能遗漏一些节点的原因之一，而这些节点在穷尽搜索中会被返回，从而降低与穷尽搜索相比的搜索召回率。（具体示例见这里）。

图的参数

总结来说，构建HNSW图的两个参数是M（节点最大连接数）和ef_construction（在添加新向量时搜索邻居的节点数）。

• 增加M可以通过增加连接邻居和层数来提高搜索准确性，但也会增加图的磁盘和内存使用、插入延迟以及搜索延迟。
• 增加ef_construction会更全面地搜索以找到每个新向量的邻居，但会增加插入延迟。

HNSW图常见问题解答：

以下是理解M和ef_construction图构建参数的关键点：