蚂蚁金服 ZSearch 在向量检索上的探索

• 如何管理集群；
• 如何方便用户接入和管理用户；
• 如何支持用户不同的个性化需求；
• ...

• 基于 K8s 底座，快速创建 ZSearch 组件，快捷运维，故障机自动替换；
• 跨机房复制，重要业务方高保；
• 插件平台，用户自定义插件热加载；
• SmartSearch 简化用户搜索，开箱即用；
• Router 配合 ES 内部多租户插件，提高资源利用率；

• 欧式距离：

• 两点间的真实距离，值越小，说明距离越近；

• 余弦距离：

• 就是两个向量围成夹角的 cosine 值，cosine 值越大，越相似；

• 汉明距离：

• 一般作用于二值化向量，二值化的意思是向量的每一列只有0或者1两种取值；
• 汉明距离的值就两个向量每列数值的异或和，值越小说明越相似，一般用于图片识别；

• 杰卡德相似系数：

• 把向量作为一个集合，所以它可以不仅仅是数字代表，也可以是其他编码，比如词，该值越大说明越相似，一般用于相似语句识别；

图片来源：https://blog.csdn.net/richard9006/article/details/90058465

• 按照 x 排序，确定中间值7，其他坐标分两边；
• 第二层按照 y 排序，第三层按照 x 排序；
• 并且在构建时维护每个节点中的 x 最大最小，y 最大最小四个值；

查找最近点

图片来源：https://blog.csdn.net/richard9006/article/details/90058465

• 到根节点距离为5；
• 遍历到右节点(9,6)，发现整棵右子树的x轴，最小值是8，所以所有右子树的节点到查询节点的距离一定都大于8-3=5，于是所有右子树的节点都不需要遍历；
• 同理，在左子树，跟(5，4)节点比较，(7,2)被排除；
• 遍历完(2,3),(4,7)，最近点(5,4) 返回；

• 基于 Hash 的 LSH；
• 基于编码的 IVFPQ；
• 基于图的 HNSW；

PQ 是一种编码，例如图中的128维向量，先把向量分成4份，对每一份数据做 kmeans 聚类，每份聚类出256个聚类中心，这样，原始向量就可以使用聚类中心的编号重新编码，可以看出，现在表示一个向量，只需要用4个字节就行。然后当然要记录下聚类中心的向量，它被称之为码本。

• 例如第5次构造 D 点的流程；
• 构建的时候，我们约定每次加入节点只连3条边，防止图变大，在实际使用中，要通过自身的数据估计该参数；
• 随机一个节点，比如 A，保存下与 A 的距离，然后沿着 A 的边遍历，E 点最近，连边。然后再重新寻找，不能与之前重复，直到添加完3条边；

• proxima 是阿里内部达摩院开发的一个通用向量检索引擎框架，类似与 facebook 开源的 faiss；
• 支持多种向量检索算法；
• 统一的方法和架构，方便使用方适配；
• 支持异构计算，GPU；

• 数据从远端复制过来时：
• 我们拦截了 ElasticSearch 的 recovery action；
• 然后生成 Proxima 索引的快照，这个时候需要通过写锁防止数据写入，快照生成由于都是内存的，其实非常快；
• 把 Proxima 快照复制到目的端；
• 再进行其他 ElasticSearch 自己的恢复流程；

• 数据从本地 translog 恢复时，我们会记录快照的 LocalCheckPoint，如果当前 CheckPoint 小于等于 LocalCheckPoint，可以直接跳过，否则我们会回查 Proxima 检索引擎，防止数据重试；
• 目前还有一个情况，数据会有重复，就是主副分片全部挂掉时，translog 还未刷盘，数据可能已经写入 Proxima 了。

• 100w 256维向量占用空间，大概是0.95GB，比较大：

• 所以更大的堆外内存分配给 pagecache；
• 例如 8C32G 的机器，JVM 设置 8GB，其他 24GB 留给系统和 pagecache；

• 设置 maxconcurrentshard_requests：
• 6.x 默认为节点数*5，如果单节点 CPU 多，可以设置更大的 shards，并且调大该参数；
• BF 算法使用支持 AVX2 的 CPU，基本上阿里云的 ECS 都支持；

• KNN 适合场景：

• 数据量小(单分片100w以下)；
• 先过滤其他条件，只剩少量数据，再向量召回的场景；
  召回率100%；

• ANN 场景：

• 数据量大(千万级以上)；
• 先向量过滤再其他过滤；
• 召回率不需要100%；
• LSH 算法：召回率性能要求不高，少量增删；
• IVFPQ 算法：召回率性能要求高，数据量大(千万级)，少量增删，需要提前构建；
• HNSW 算法：召回率性能要求搞，数据量适中(千万以下)，索引全存内存，内存够用；

• fast-cosine 插件：
  https://github.com/StaySense/fast-cosine-similarity
• LSH 插件 ：
  https://github.com/alexklibisz/elastik-nearest-neighbors
• IVFPQ 插件：
  https://github.com/rixwew/elasticsearch-approximate-nearest-neighbor
• HNSW 插件：
  https://github.com/opendistro-for-elasticsearch/k-NN
• 向量算法概述：
  https://yongyuan.name/blog/vector-ann-search.html
• HNSW 算法：
  https://blog.csdn.net/u011233351/article/details/85116719
• ANN 性能测试框架 ：
  https://github.com/erikbern/ann-benchmarks

本文归档在 sofastack.tech。