为什么蚂蚁金服的 ZSearch 比 ElasticSearh 还牛?
共 6552字,需浏览 14分钟
·
2020-08-28 16:43
点击“开发者技术前线”,选择“星标?”
在看|星标|留言, 真爱
引言
ElasticSearch 的痛点
如何管理集群; 如何方便用户接入和管理用户; 如何支持用户不同的个性化需求; ...
基于 K8s 底座,快速创建 ZSearch 组件,快捷运维,故障机自动替换; 跨机房复制,重要业务方高保; 插件平台,用户自定义插件热加载; SmartSearch 简化用户搜索,开箱即用; Router 配合 ES 内部多租户插件,提高资源利用率;
向量检索需求
向量检索基本概念
欧式距离:
两点间的真实距离,值越小,说明距离越近;
余弦距离:
就是两个向量围成夹角的 cosine 值,cosine 值越大,越相似;
汉明距离:
一般作用于二值化向量,二值化的意思是向量的每一列只有0或者1两种取值; 汉明距离的值就两个向量每列数值的异或和,值越小说明越相似,一般用于图片识别;
杰卡德相似系数:
把向量作为一个集合,所以它可以不仅仅是数字代表,也可以是其他编码,比如词,该值越大说明越相似,一般用于相似语句识别;
向量检索算法
按照 x 排序,确定中间值7,其他坐标分两边; 第二层按照 y 排序,第三层按照 x 排序; 并且在构建时维护每个节点中的 x 最大最小,y 最大最小四个值;
查找最近点
到根节点距离为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条边;
在创建 index 时传入抽样数据,计算出 hash 函数。写入时增加 hash 函数字段。召回用 minimum_should_match 控制计算量 | |||
1.实现简单,性能较高 2.无需借助其他 lib 库 3.无需考虑内存 | 1.性能较高 2.召回率高 >90% 3.无需考虑内存 | 1.查询性能最高 2.召回率最高 >95% | |
1.召回率较其他两种算法较差,大概在85%左右 2.召回率受初始抽样数据影响 3.ES 的 metadata很大 | 1.需要提前使用 faiss 等工具预训练 2. ES 的 metadata很大 | 1.在构建的时候,segment 合并操作会消耗巨大的 CPU 2.多 segment 下查询性能会变差 3.全内存 |
proxima 是阿里内部达摩院开发的一个通用向量检索引擎框架,类似与 facebook 开源的 faiss; 支持多种向量检索算法; 统一的方法和架构,方便使用方适配; 支持异构计算,GPU;
数据从远端复制过来时: 我们拦截了 ElasticSearch 的 recovery action; 然后生成 Proxima 索引的快照,这个时候需要通过写锁防止数据写入,快照生成由于都是内存的,其实非常快; 把 Proxima 快照复制到目的端; 再进行其他 ElasticSearch 自己的恢复流程;
数据从本地 translog 恢复时,我们会记录快照的 LocalCheckPoint,如果当前 CheckPoint 小于等于 LocalCheckPoint,可以直接跳过,否则我们会回查 Proxima 检索引擎,防止数据重试; 目前还有一个情况,数据会有重复,就是主副分片全部挂掉时,translog 还未刷盘,数据可能已经写入 Proxima 了。
数据写入 (单线程1000个 bulk 写入) | 1.初始写入 5min,25个 segment,最大 CPU 300% 2.合并成1个 segment 5min,最大 CPU 700%(本地最大) | |
1.Top 10,召回率98% 2.rt 20ms , 合并成1个 segment 后,5ms | 1.Top 10,召回率98% 2.rt 6ms | |
总结
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
扫码加我微信进群,内推和技术交流,大佬们零距离