白癜风医院地址 http://baidianfeng.39.net/a_zhiliao/130522/4177939.html
点击“开发者技术前线”，选择“星标??”
让一部分开发者看到未来
作者介绍吕梁（花名：十倍），年加入蚂蚁金服数据中间件，通用搜索平台ZSearch基础架构负责人，负责ZSearch组件在K8s上的落地及基于ES的高性能查询插件开发，对ES性能调优有着丰富的经验。图为ZSearch基础架构负责人十倍ElasticDevDay现场分享引言
ElasticSearch（简称ES）是一个非常受欢迎的分布式全文检索系统，常用于数据分析、搜索、多维过滤等场景。蚂蚁金服从年开始向内部业务方提供ElasticSearch服务，我们在蚂蚁金服的金融级场景下，总结了不少经验，此次主要给大家分享我们在向量检索上的探索。ElasticSearch的痛点
ElasticSearch广泛应用于蚂蚁金服内部的日志分析、多维分析、搜索等场景。当我们的ElasticSearch集群越来越多，用户场景越来越丰富，我们会面临越来越多的痛点：如何管理集群；如何方便用户接入和管理用户；如何支持用户不同的个性化需求；...为了解决这些痛点，我们开发了ZSearch通用搜索平台：基于K8s底座，快速创建ZSearch组件，快捷运维，故障机自动替换；跨机房复制，重要业务方高保；插件平台，用户自定义插件热加载；SmartSearch简化用户搜索，开箱即用；Router配合ES内部多租户插件，提高资源利用率；向量检索需求
基于ElasticSearch的通用搜索平台ZSearch日趋完善，用户越来越多，场景更加丰富。随着业务的飞速发展，对于搜索的需求也会增加，比如：搜索图片、语音、相似向量。为了解决这个需求，我们是加入一个向量检索引擎还是扩展ElasticSearch的能力使其支持向量检索呢？我们选择了后者，因为这样我们可以更方便的利用ElasticSearch良好的插件规范、丰富的查询函数、分布式可扩展的能力。接下来，我来给大家介绍向量检索的基本概念和我们在这上面的实践。向量检索基本概念
向量从表现形式上就是一个一维数组。我们需要解决的问题是使用下面的公式度量距离寻找最相似的K个向量。欧式距离：两点间的真实距离，值越小，说明距离越近；余弦距离：就是两个向量围成夹角的cosine值，cosine值越大，越相似；汉明距离：一般作用于二值化向量，二值化的意思是向量的每一列只有0或者1两种取值；汉明距离的值就两个向量每列数值的异或和，值越小说明越相似，一般用于图片识别；杰卡德相似系数：把向量作为一个集合，所以它可以不仅仅是数字代表，也可以是其他编码，比如词，该值越大说明越相似，一般用于相似语句识别；因为向量检索场景的向量都是维度很高的，比如，位等，计算量很大，所以接下来介绍相应的算法去实现topN的相似度召回。向量检索算法
KNN算法KNN算法表示的是准确的召回topK的向量，这里主要有两种算法，一种是KDTtree，一种是BruteForce。我们首先分析了KDTree的算法，发现KDTree并不适合高维向量召回，于是我们实现的ES的BruteForce插件，并使用了一些Java技巧进行加速运算。KDTree算法简单来讲，就是把数据按照平面分割，并构造二叉树代表这种分割，在检索的时候，可以通过剪枝减少搜索次数。构建树以二维平面点(x,y)的集合(2,3)，(5,4)，(9,6)，(4,7)，(8,1)，(7,2)为例：按照x排序，确定中间值7，其他坐标分两边；第二层按照y排序，第三层按照x排序；并且在构建时维护每个节点中的x最大最小，y最大最小四个值；查找最近点
搜索(3,5)的最近邻：到根节点距离为5；遍历到右节点(9,6)，发现整棵右子树的x轴，最小值是8，所以所有右子树的节点到查询节点的距离一定都大于8-3=5，于是所有右子树的节点都不需要遍历；同理，在左子树，跟(5，4)节点比较，(7,2)被排除；遍历完(2,3),(4,7)，最近点(5,4)返回；结论Lucene中实现了BKDTree，可以理解为分块的KDTree，并且从源码中可以看到MAX_DIMS=8，因为KDTree的查询复杂度为O(kn^((k-1)/k))，k表示维度，n表示数据量。说明k越大，复杂度越接近于线性，所以它并不适合高维向量召回。BruteForce顾名思义，就是暴力比对每一条向量的距离，我们使用BinaryDocValues实现了ES上的BF插件。更进一步，我们要加速计算，所以使用了JAVAVectorAPI。JAVAVectorAPI是在openJDKprojectPanama项目中的，它使用了SIMD指令优化。结论使用avx2指令优化，w的维向量，单分片比对，RT在ms，是常规BF的1/6。ElasticSearch官方在7.3版本也发布了向量检索功能，底层也是基于Lucene的BinaryDocValues，并且它还集成入了painless语法中，使用起来更加灵活。ANN算法可以看到KNN的算法会随着数据的增长，时间复杂度也是线性增长。例如在推荐场景中，需要更快的响应时间，允许损失一些召回率。ANN的意思就是近似K邻近，不一定会召回全部的最近点。ANN的算法较多，有开源的ESANN插件实现的包括以下这些：基于Hash的LSH；基于编码的IVFPQ；基于图的HNSW；ZSearch依据自己的业务场景也开发了ANN插件（适配达摩院proxima向量检索引擎的HNSW算法）。LSH算法LocalSensitiveHashing局部敏感hash，我们可以把向量通过平面分割做hash。例如下面图例，0表示点在平面的左侧，1表示点在平面的右侧，然后对向量进行多次hash，可以看到hash值相同的点都比较靠近，所以在hash以后，我们只需要计算hash值类似的向量，就能较准确的召回topK。IVF-PQ算法PQ是一种编码，例如图中的维向量，先把向量分成4份，对每一份数据做kmeans聚类，每份聚类出个聚类中心，这样，原始向量就可以使用聚类中心的编号重新编码，可以看出，现在表示一个向量，只需要用4个字节就行。然后当然要记录下聚类中心的向量，它被称之为码本。
图片来源：