以阿里云OpenSearch为例谈向量检索技术选型

向量检索应用场景

向量可以对物理世界的人/物/场景所产生各种非结构化数据（如语音、图片、视频，语言文字、行为等）进行抽象，如同数学空间中的坐标，标识着各个实体和实体关系。非结构化数据变成向量的过程称为向量化(Embedding)。向量检索就是对非结构化数据生成的向量进行检索，寻找相同或相似的向量，从而找到相同或相似的非结构化数据。

非结构化数据（语音、图像、视频）检索

向量检索的第一应用场景就是对语音、图像、视频这些非结构化数据的检索。以图片搜索为例，每一幅图片可以被抽象成向量特征，然后将所有特征构建成向量索引，查询的时候，将查询（图片）也表示为一个相同维度的向量，然后用这个向量在之前构建的向量索引中查找出最相似的结果，这样就完成了一次以图搜图。

大模型知识记忆

向量其实很早就已经文本检索中用到了。高德地图中搜索“浙一医院”，“浙一医院”的标准地址是“浙江大学医学院附属第一医院”，只使用关键词“浙一”和“医院”，是找不到相关结果的。如果使用向量把地址用高维特征来表达，那么“浙一医院”和“浙江大学医学院附属第一医院”的相似度会非常高，这样就可以被检索出来。向量用于文本检索的需求真正开始爆发式增长是在大模型出现后，大模型可以使用Prompt来引导答案生成，这些用来做Prompt的信息向量化后存储到向量数据库，在查询的时候，先从向量数据库查找到相似的信息，再将这些信息作为Prompt输入大模型生成答案，这也是现在最常用的检索增强大模型方案，向量检索在里面扮演了知识记忆和筛选的重要角色，是大模型应用不可缺少的一个关键链路。

搜索、推荐、广告

搜索、推荐、广告业务中，常见的需求是找到相似的同款商品和推荐给用户感兴趣的商品，这种需求绝大多数都是采用商品协同和用户协同的策略来完成的。搜索推荐系统使用了向量， 通过Item-Item (i2i)、User-Item (u2i)、User-User-Item (u2u2i)、User2Item2Item (u2i2i) 等向量召回的方式实现快速检索。算法工程师通过对商品的相似和相关关系，以及被浏览和被购买的用户行为的抽象，将它们表征成高维向量特征并存储在向量引擎中。这样，当我们需要找一个商品的相似商品（i2i）时，就可以从向量引擎中检索出来。

开放搜索OpenSearch向量检索版是阿里云自主研发的大规模分布式搜索引擎，内置功能完备、性能优异的向量检索能力，其核心能力广泛应用于阿里巴巴和蚂蚁集团内众多业务，如淘宝搜索和推荐、蚂蚁人脸支付、优酷视频搜索、阿里妈妈广告检索等。查询延迟毫秒级，稳定性高，支持百万QPS高时效性写入，单应用实例千亿+级别数据，海量数据检索场景优势明显。OpenSearch近期发布了新版向量检索产品，这是一次全新的升级，产品从原来的PaaS形态演化成了Servless形态，易用性显著改善。核心引擎换成了新研发的引擎VectorStore，性能大幅提升。同时也推出了更丰富的产品规格。

常见向量检索方法

向量检索主要是求解KNN、RNN问题，KNN（K-Nearest Neighbor）是查找离查询点最近的 K 个点，而 RNN (Radius Nearest Neighbor) 查找查询点某半径范围内的所有点或 N 个点。KNN的其中一种实现方式就是Brute Force。在数据量很大的情况下，准确求解 KNN、RNN问题的计算成本很高，因此大数据量检索通常使用ANN（Approximate Nearest Neighbor）来进行检索。

Brute Force方法

Brute Force是一种暴力匹配的算法，它会穷举遍历所有的向量特征，找出离查询点最近的K个向量。Brute Force方法是100%准确的，适用于小数据规模的情况，或者对准确率100%要求的场景。OpenSearch中的Linear方法，Milvus中的FLAT方法都是Brute Force方法。

ANN方法

ANN（Approximate Nearest Neighbor）搜索指的是如下的任务：在给定空间（如d维欧式空间）中的一个点集S以及查询向量q后，寻找S中离q最近的k个点。在 ANN 搜索中，一般不需要精确地找到最近的k个最近邻，而是允许存在一些误差。假设找到的结果集合R，实际的最近邻集合为N，那么 ANN 搜索中召回率指的就是

可见，召回率越高，结果就越精确。当Recall=1时，算法就精确地找到了全部最近邻；当Recall=0时，算法则没有找到任何最近邻。实际计算中一般有 。召回率刻画了 ANN 搜索的精度，而检索的速度则由吞吐或延迟来衡量，延迟指的是给定S后对某个q进行一次 ANN 搜索的耗时，而吞吐则指的是给定S后在单位时间内可以处理多少次 ANN 搜索，一般使用每秒检索数 (Queries Per Second, QPS) 来衡量。在 ANN 搜索中，我们希望能以尽可能少的时间和硬件资源，构建尽可能小的索引，同时在检索时能以尽可能少的硬件资源达到尽可能高的精度和速度。

业内有不少ANN检索算法。常用的算法有基于树的算法，比如KD-Tree（K-Dimensional Tree）、Annoy（Approximate Nearest Neighbors Oh Yeah）。基于聚类的方法，比如层次聚类（Hierarchical Clustering）。基于量化的方法，比如乘积量化，PQ(Product Quantization)。基于哈希的方法，比如局部敏感哈希，LSH（Locality-Sensitive Hashing）。还有最常用的基于图的算法，比如HNSW (Hierarchical Navigable Small World)。在具体实现方案中，多种方法可以组合使用，达到最优的检索效果和效率。

基于树的方法

基于树的方法主要思想是对K维空间进行多次划分，检索时只需对少数子空间进行检索，加快检索速度。优点是实现简单，缺点是不适合高维向量场景。主要有KD树和Annoy两种算法。KD树是K-Dimension Tree的缩写，就是把整个空间划分为多个部分，然后在特定空间内进行搜索。Annoy（Approximate Nearest Neighbors Oh Yeah）也是对空间进行多次划分，并把划分后的子空间以树型结构存储，根节点放进优先队列，查询时对每一个树都进行搜索，合并候选集并排序返回。Annoy的一个优点是索引非常小，占用内存少。

基于聚类的方法

层次聚类（Hierarchical Clustering，HC）是典型的基于聚类的方法，使用多层聚类实现高效近邻检索的方法，通过对多层聚类中心点的对比，快速逼近目标向量，提高检索效率。 以两层聚类为例，构建索引的时候会先比较最近的一级中心点，然后再和一级中心点下所有的二级中心点进行比较，最终向量会加入到该一级中心点下距离最近的二级中心点的向量列表中。检索时，HC采用 BBF（Best Bin First）搜索策略，借助对若干一级中心点的比较，找到离查询点最近的若干个二级中心点，缩小范围，然后线性考察这些二级中心点下的向量和查询向量的距离，完成最近 K 个近邻的选取。HC 检索方法的效果很大程度上依赖于聚类的准确性。

基于量化的方法

基于量化的方法主要思想是将高精度的数值或向量，通过损失一定的精度，用近似的形式进行存储和计算，加快检索速度。优点是减少计算次数，加快检索速度，缺点是有一定的精度损失。基于量化的方法主要有SQ（Scalar Quantization）和PQ（Product Quantization），SQ是将每一个维度量化成指定位数的一个数，比如将32位的INT量化成8位的INT，通过损失一定的精度，缩减存储和计算成本，该方法较为简单。PQ 是 Product Quantization 的简称，即乘积量化。PQ 将特征空间分解为多个低维子空间的笛卡尔乘积，然后单独地对每一个子空间进行量化。在训练阶段，每一个子空间经过聚类后得到 K个中心点，所有这些中心点组成一个新的ID向量。 PQ可以大幅减少向量的计算和存储成本。

基于哈希的方法

基于哈希的方法是利用相似度很高的数据以较高的概率映射成同一个Hash值，相似度很低的数据以极低的概率映射成同一个Hash值，将高维数据降维到低维数据，提高检索效率。优点是能高效处理海量高维数据的最近邻问题，缺点是有数据失真。基于哈希的方法最常见的是LSH（Locality-Sensitive Hashing）。

基于图的方法

基于图的方法最常用的是HNSW (Hierarchical Navigable Small World)，几乎所有的向量检索产品都实现了 HNSW，OpenSearch的图算法也是基于HNSW实现的，并在HNSW基础上进行了优化。 HNSW 是一种分层小世界图的检索方法，上层小世界图可以看成是下层图的缩放。多层图的方式目的是为了减少搜索时距离计算和比较的次数，类似于跳表查找。检索时，从最高一层（即最稀疏的一层）开始，每一层得到的检索结果再作为下一层的输入，如此，不断迭代到最后一层。最后得到查询点的 K 个近邻。HNSW 本身基于另一种图索引 NSW (Navigable Small World)，同时借用了跳表的思想，将图分层来加速检索，从而能在较高召回率的同时保持较高的性能。不同于大部分其他图索引，在 HNSW 中存在m张图，而非只有一张图。这m张图从低到高形成了层次结构，如下图所示。从最低层（第0层）到最高层（第m-1层），层越高，其中的节点越少；层越低，其中的节点越多，并且高层的节点总会出现在低层中，而第0层则包含了索引中所有的节点。在检索时，算法首先从第m-1层开始，选取一个起始点开始游走，开始查找层中距离查询向量q最近的节点。接下来，以找到的最近节点作为新的起始点，在第m-2层查找距离q最近的节点。如此直到在第0层中完成查找。由于高层的节点稀疏，节点间的距离远，游走时能很快地达到q附近。而低层中包含更多的节点，具有较完整的邻接关系，通过在低层的游走又能精确地找到q的 top k的结果。因此 HNSW 得以在召回率和吞吐上均达到良好的性能。

在层内检索时，HNSW 是通过贪心法进行游走来完成检索的。算法不断选取距离q最近的节点作为下一跳进行游走，直到无法找到更近的节点，如下图所示。此时，算法会进行回溯，找到之前距离q次近，但是没有游走过的节点继续检索。直到最后无法找到可以游走的路径为止。此时，游走过程中找到的离q最近的k个点就是检索的结果。

HNSW 层内检索示意图（来源：NGT wiki，https://github.com/yahoojapan/NGT/wiki）

有了上述的检索算法，索引构建就很容易了。构建时，HSNW 算法会逐个将节点加入索引中来完成构建。每次将新节点加入索引时，HNSW 都会对新节点在当前索引上进行一次查找。只要将找到的最近邻当作新节点的领居，就成功在索引中插入了新节点。

异构计算

异构计算是一种结合不同指令集和体系架构进行计算优化的方式，例如CPU+FPGA、CPU+GPU。在高性能计算领域是一种不错的优化方法，应用也越来越普及。OpenSearch向量检索充分利用了异构计算，利用GPU+CPU进行加速，可以使用消费级显卡数倍提升检索性能。

向量检索性能优化

OpenSearch做了大量向量检索性能优化，以下我们介绍一些近期的优化工作。

HNSW算法分析

HNSW 在许多数据集上都能取得良好的效果，然而算法仍然还有改进的空间。下面我们从图结构和检索两个方面来分析 HNSW 的不足。

图结构

从图结构来看，我们可以通过修改 efconstruction 参数来检验图结构对索引检索性能的影响。下图展示了在 gist 数据集上，efconstruction 参数分别取 500 和 750 时，HNSW 算法的 recall-qps 曲线。

efconstruction 对 recall 和 qps 的影响

对于图本身的结构而言，我们可以测量节点出度和入度的分布来考察图结构的变化。下图展示了在 gist 数据集上，efconstruction 分别取 500 和 750 时，图的入度和出度分布。

可以看到，efconstruction 为 750 时索引的检索性能要好于取 500 时的性能。同时取 750 时会导致节点的平均入度更高，出度更为分散。直观上，对于每个节点，如果它的入度越多，就越容易在游走中被找到；如果它的出度越多，则更容易找到其他的节点，但计算邻居距离时的耗时就越大。因此可以猜测大量节点入度过低是性能偏低的主要原因之一。自然，我们可以像上述实验一样之间调整 efconstruction 的大小来控制图的结构，从而达到更好的检索性能。然而提高 efconstruction 会导致索引构建时间快速膨胀，这在很多场景下是不可接受的。因此我们需要更有效的方法来控制图的结构。

检索过程

包括HNSW算法在内的大部分knn算法的性能开销都集中在距离计算操作(distance comparison operations  aka DCOs)上,  DCO操作的计算复杂度是O(D)的,其中D是向量维度。而AKNN算法中的大部分距离比较操作都可以抽象为f(query,object,r)->bool的形式，其中query为查询向量，object是当前的比较对象，r是一距离范数的阈值，函数的返回值表示当前query和oject的距离是否大于r，注意到这个过程中其实并不需要计算query和object的精确距离作为返回值，我们只需要知道dis(query,object)和r的大小关系。如果把查询流程中的耗时做细分，把DCOs计算结果为小于阈值r的计算成为postitive DCO, 否则为negative DCO，那么如下图所示其实大部分cpu时间都花费在了计算negative DCO上。

另一方面，从 HNSW 算法的检索过程来看，很大一部分游走实际上是不必要的。大部分的q均能快速找到实际的最近邻N，只有少部分极端情况需要很长的游走。下表展示了在不同数据集上的检索中，最后一次更新结果集R时的距离计算次数占整个游走过程距离计算次数的比例。由于在此之后的游走并不会更新R，因此可以认为只有这之前的距离计算是有效的，我们称一比值为有效距离计算占比。

表 1. 不同数据集与查询参数下 HNSW 的召回率与有效距离计算占比

从表 1 可以看到，在各种数据集的场景下，HNSW 的检索都存在不必要的计算，部分场景的有效计算甚至不到总计算量的 20%。倘若可以在检索时进行判断，提前终止游走，就可以节省这部分距离计算，从而在不影响召回率的情况下提升 qps。

从上面的讨论可以看出，要对 HNSW 性能进行优化，可以从图的构建和检索两个方面入手。

• 构建阶段的优化：优化图结构，使图的出度入度更加合理，更利于 ANN 搜索；
• 检索阶段的优化：减少距离计算操作的开销，以及预测检索游走时所需的总步数，当到达预期步数时可以提前终止检索，以减少计算开销。

自适应终止算法

我们考虑不使用机器学习方法，而是采用传统的统计学方法对检索操作进行建模，以求能在较小的开销下对检索轮数进行较好的估计，达到优化 qps 的目的。如前文所述，在 HNSW 中，检索实际上是通过在图中进行贪心游走实现的，因此当前节点和q的距离会不断变化。下图展示了 gist 数据集的一次 top 10 查询中，在第 0 层内游走时，q与结果集R中的前 9 近的节点 (灰色) 、第 10 近的节点(top_k_dist，绿色) 以及当前游走节点 (cur_dist，蓝色) 之间的距离。图中还展示了当前游走节点距离进行平滑处理后的结果 (smoothed_dist，橙色)。

HNSW 检索过程中各距离的变化情况

如图所示，在这一次 ANN 搜索的游走中，第 37 步左右就已经得到了最终的查询结果。如果可以提前预知这一点，直接在第 37 步终止，就可以节省大量的计算。这与上文的分析是一致的。直观上看，cur_dist 的下降意味着发现了距离q更近的节点，以此进一步查找更有可能找到实际的最近邻；而cur_dist 的上升则意味着没有发现这样的节点，只能进行回溯从次近的节点进行搜索。图中可以看到，cur_dist 的变化大体呈现为“U 形”的变化趋势。由于初始的游走中会发现大量距离q更近的节点，在游走过程中 cur_dist 首先下降 (0-10 步) 。在此之后，搜索中发现新的近邻节点的概率更小，因此游走开始远离q，cur_dist 开始上升 (10 步后) 。基于这一观察，要判断搜索是否应该终止，应当首先判断游走是否已经进入第二阶段，开始远离q。

我们将 cur_dist>top_k_dist 作为游走进入第二阶段的判据。当然，进入了第二阶段并不足以终止检索，算法实际上应当在最后一次更新R后才停止。也就是说，假如算法预测在剩余的检索步骤中R将不再更新，算法就应当终止了。用检索中的距离来描述这一点，就是在剩余的游走中cur_dist>top_k_dist始终成立。在第二阶段的检索过程中，top_k_dist 一般比较稳定，但 cur_dist 波动较大，不容易估计。我们可以将每一轮游走的 cur_dist 视为一个随机变量。这样整个游走就可以看作一个随机过程。如果把每一次找到新的近邻节点视为一次事件，那么每一次事件就对应了一次 cur_dist 的下降。这样，没找到新近邻时的回溯就对应了 cur_dist 的一段上升区间。假设事件之间是无记忆的，那么时间发生的次数就可以通过泊松过程来进行建模。利用泊松过程的性质以及实验测试，我们发现事件间的时间间隔以及每次事件 cur_dist 的下降值都是大体服从指数分布的。只要利用这一概率分布，就可以计算剩余游走中更新R的概率。下图给出了建模方法的一个图示。

仅仅知道随机变量服从指数分布是不够的，我们还需要估计具体的分布参数。这可以通过最大似然估计实现。首先，指数分布的概率密度函数f(x)与累计分布函数F(x)如下所示：

那么对于指数分布的n个样本 ，就可以得到相应的似然函数

对 求导可以得到

因此利用样本均值的倒数就可以估计指数分布的参数 。

现在我们来计算剩余游走中R的更新概率。首先，注意到 ef 参数很大程度上决定了检索中的总步数，以此为依据即可在游走过程中估计剩余游走的最大步数，下面记为t。而利用泊松过程，则可得到在长度为t的时间段中发生i次事件的概率为

记 ，从上面的分析中可以看到，如果在接下来的t步中 都始终大于0，R将不再更新，搜索就可以终止了。记 cur_dist 下降值随机变量为X，泊松过程的参数为 ，那么R不再更新的概率为

对于指数分布，有 。记 cur_dist 下降值指数分布的参数为 ，就有

利用p即可在每一步都对R的更新概率进行预测，当R以很高的概率不再更新，检索就可以终止了。

自适应距离比较算法

随机矩阵投影是一种通用常见的对高维向量进行降维的手段，根据Johnson–Lindenstrauss lemma一个D维向量在经过一个高斯随机矩阵映射被投影到一个更小的d维空间后，依然能以一定概率保持它的欧几里德范数，这意味如果向量x y在原空间的距离信息会在一定程度上被保留在新空间上。所以我们可以先对两个高维向量query object进行随机矩阵映射降维后在对其计算距离dis'(query',object')，这样可以大大减少DCO的计算量。

JL引理给了我们一个通过投影后低维空间的距离范数来估算原空间距离范数的方法，并且给出了严格的error bound。传统的随机矩阵投影技术要求事前确定被映射到的目标向量的维度d，这对于实际应用来说具有先验知识需求，而且d一旦确定下来就不会再改变，这种固定维度的投影无法适应不同对象的特点，导致效率不高。

我们使用了ADSampling技术，ADSampling在以下两个方面具有创新性：

1. 灵活的投影：ADSampling在查询阶段将不同的对象投影到具有不同维度的向量中。这种灵活性可以实现更高效的DCOs。

2. 自适应维度采样：ADSampling根据查询阶段对对象的DCO动态决定要采样的维度数量。这种自适应方法避免了在索引阶段预设维度数量的挑战和知识需求。

假设我们有两个随机正交矩阵P和P'且 。

那么直接计算Px和 计算P'x再取前d维得到的向量是同分布的，因为:

。

这样就可以在索引构建阶段确定好随机矩阵P'，对插入的每个点都进行投影，在查询阶段对查询query进行相同的投影，这么做后查询query和data其实还是D维，但是在DCO的过程中，只需要截取query和data的前d维进行计算，这样就可以增量式的增加d的维度并增量式更新dis'，而不需要每次更新d就重复计算。

针对每次比较f(query,object,r)->bool，可以采用统计学中假设检验的方法来判断当前的d取值是否适合，如果不适合，就继续增大d直到d等于D。

假设检验具体步骤:

1. 虚无假设H0 : 当前真实距离dis(query,object)<=r。
2. 对立假设H1: dis(query,object)>r。
3. 取显著值p为 , 其中c0是常量，而𝜖0是一个调出来的经验值。
4. 假设H0成立，这样根据Johnson–Lindenstrauss lemma 事件 𝑑𝑖𝑠′ > (1 + 𝜖0/ 𝑑) · 𝑟 的概率一定小于显著值p。
5. 我们检测 事件 𝑑𝑖𝑠′ > (1 + 𝜖0/ 𝑑) · 𝑟 是否发生，如果发生那么H0不成立，及对立假设dis(query,object)>r成立，反之亦然。

可以看出随着d的增大近似距离dis'会逐渐更加精确，那么对于dis(query,object)>r的object会更容易被假设检验识别出来，而且真实距离dis越大的object越容易在更小的d维度就被假设检验识别出来（占大多数的negative DCO），从而大大节省计算量。

实验结果

利用 ANN Benchmark 工具，我们针对优化后的HNSW实现与优化前的实现在gist、sift 以及拍立淘数据集上进行了测试。实验中，检索在单线程下进行，索引构建以及检索均采用一致的基础参数（efconstruction = 500, M = 100），同时每组实验中均调整检索参数 ef，以考察两者在不同召回率下的最优 qps。下图展示了最终的实验结果，其中 baseline 和 optimized 分别展示了优化前和优化后 HNSW 算法的 recall-qps 曲线。

分析上图数据可得：

• 在 gist 数据集上，召回率由 99.53% 变为 99.51% 时，qps 由 125.11 上升为 240.61，提升 92.3%；
• 在 sift 数据集上，召回率为 99.88% 时，qps 由 670.40 上升为 814.80，提升 21.5%；
• 在拍立淘数据集上，召回率由 99.20% 变为 99.19% 时，qps 由 80.42 上升为 139.72，提升 73.7%。

可以看到，优化后的 HNSW 算法取得了显著的性能增长，在不同数据集下均可达到至少 20% 的 qps 提升，部分场景甚至可以达到将近优化前两倍的吞吐。

典型向量检索产品功能对比

以一些典型的向量检索产品为例，我们进行功能对比分析：

向量检索性能对比

OpenSearch vs. Milvus vs. ElasticSearch

异构计算性能对比（OpenSearch vs. Milvus）

对比总结

OpenSearch定位大规模数据实时检索，数据规模较大时相比其他产品有明显优势，海量数据检索首选OpenSearch。OpenSearch内置文本、图片向量化，无需在外部使用其他工具进行文本和图片的向量化，一站式检索需求首选OpenSearch。OpenSearch支持索引版本热切换，在数据字段发生变更，重建索引后，可以做到线上用户无感知的切换到新的索引版本，索引结构有变更需求首选OpenSearch。OpenSearch的QC算法支持GPU加速，可以数倍提升性能并优于其他产品（同等条件下性能加速是Milvus的3~5倍），在对性能要求极高的场景首选OpenSearch。OpenSearch支持数据源同步数据，有数据源客户首选OpenSearch，数据导入方便快捷。场景要求必须使用开源软件，可以选择Elasticsearch或者Milvus，海外用户可以选择Pinecone。