HarmonyOS开发者限时福利来啦!最高10w+现金激励等你拿~ 了解详情
写点什么

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

  • 2019-12-25
  • 本文字数:6185 字

    阅读完需:约 20 分钟

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

引言

ElasticSearch(简称 ES)是一个非常受欢迎的分布式全文检索系统,常用于数据分析、搜索、多维过滤等场景。蚂蚁金服从 2017 年开始向内部业务方提供 ElasticSearch 服务,我们在蚂蚁金服的金融级场景下,总结了不少经验,此次主要给大家分享我们在向量检索上的探索。

ElasticSearch 的痛点

ElasticSearch 广泛应用于蚂蚁金服内部的日志分析、多维分析、搜索等场景。当我们的 ElasticSearch 集群越来越多,用户场景越来越丰富,我们会面临越来越多的痛点:


  • 如何管理集群;

  • 如何方便用户接入和管理用户;

  • 如何支持用户不同的个性化需求;


为了解决这些痛点,我们开发了 ZSearch 通用搜索平台:


  • 基于 K8s 底座,快速创建 ZSearch 组件,快捷运维,故障机自动替换;

  • 跨机房复制,重要业务方高保;

  • 插件平台,用户自定义插件热加载;

  • SmartSearch 简化用户搜索,开箱即用;

  • Router 配合 ES 内部多租户插件,提高资源利用率;


向量检索需求

基于 ElasticSearch 的通用搜索平台 ZSearch 日趋完善,用户越来越多,场景更加丰富。


随着业务的飞速发展,对于搜索的需求也会增加,比如:搜索图片、语音、相似向量。


为了解决这个需求,我们是加入一个向量检索引擎还是扩展 ElasticSearch 的能力使其支持向量检索呢?


我们选择了后者,因为这样我们可以更方便的利用 ElasticSearch 良好的插件规范、丰富的查询函数、分布式可扩展的能力。



接下来,我来给大家介绍向量检索的基本概念和我们在这上面的实践。

向量检索基本概念

向量从表现形式上就是一个一维数组。我们需要解决的问题是使用下面的公式度量距离寻找最相似的 K 个向量。



  • 欧式距离:

  • 两点间的真实距离,值越小,说明距离越近;

  • 余弦距离:

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

  • 汉明距离:

  • 一般作用于二值化向量,二值化的意思是向量的每一列只有 0 或者 1 两种取值;

  • 汉明距离的值就两个向量每列数值的异或和,值越小说明越相似,一般用于图片识别;

  • 杰卡德相似系数:

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


因为向量检索场景的向量都是维度很高的,比如 256,512 位等,计算量很大,所以接下来介绍相应的算法去实现 topN 的相似度召回。

向量检索算法

KNN 算法

KNN 算法表示的是准确的召回 topK 的向量,这里主要有两种算法,一种是 KDTtree,一种是 Brute Force。我们首先分析了 KDTree 的算法,发现 KDTree 并不适合高维向量召回,于是我们实现的 ES 的 Brute Force 插件,并使用了一些 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 越大,复杂度越接近于线性,所以它并不适合高维向量召回。

Brute Force

顾名思义,就是暴力比对每一条向量的距离,我们使用 BinaryDocValues 实现了 ES 上的 BF 插件。更进一步,我们要加速计算,所以使用了 JAVA Vector API 。JAVA Vector API 是在 openJDK project Panama 项目中的,它使用了 SIMD 指令优化。


结论

使用 avx2 指令优化,100w 的 256 维向量,单分片比对,RT 在 260ms,是常规 BF 的 1/6。ElasticSearch 官方在 7.3 版本也发布了向量检索功能,底层也是基于 Lucene 的 BinaryDocValues,并且它还集成入了 painless 语法中,使用起来更加灵活。

ANN 算法

可以看到 KNN 的算法会随着数据的增长,时间复杂度也是线性增长。例如在推荐场景中,需要更快的响应时间,允许损失一些召回率。


ANN 的意思就是近似 K 邻近,不一定会召回全部的最近点。ANN 的算法较多,有开源的 ES ANN 插件实现的包括以下这些:


  • 基于 Hash 的 LSH;

  • 基于编码的 IVFPQ;

  • 基于图的 HNSW;


ZSearch 依据自己的业务场景也开发了 ANN 插件(适配达摩院 proxima 向量检索引擎的 HNSW 算法)。

LSH 算法

Local Sensitive Hashing 局部敏感 hash,我们可以把向量通过平面分割做 hash。例如下面图例,0 表示点在平面的左侧,1 表示点在平面的右侧,然后对向量进行多次 hash,可以看到 hash 值相同的点都比较靠近,所以在 hash 以后,我们只需要计算 hash 值类似的向量,就能较准确的召回 topK。


IVF-PQ 算法

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



图片来源:


PQ 编码压缩后,要取得好的效果,查询量还是很大,所以前面可以加一层粗过滤,如图,把向量先用 kmeans 聚类成 1024 个类中心,构成倒排索引,并且计算出每个原始向量与其中心的残差后,对这个残差数据集进行 PQ 量化。用 PQ 处理残差,而不是原始数据的原因是残差的方差能量比原始数据的方差能量要小。


这样在查询的时候,我们先找出查询出靠近查询向量的几个中心点,然后再在这些中心点中去计算 PQ 量化后的 top 向量,最后把过滤出来的向量再做一次精确计算,返回 topN 结果。



图片来源:

HNSW 算法

讲 HNSW 算法之前,我们先来讲 NSW 算法,如下图,它是一个顺序构建图流程:


  • 例如第 5 次构造 D 点的流程;

  • 构建的时候,我们约定每次加入节点只连 3 条边,防止图变大,在实际使用中,要通过自身的数据估计该参数;

  • 随机一个节点,比如 A,保存下与 A 的距离,然后沿着 A 的边遍历,E 点最近,连边。然后再重新寻找,不能与之前重复,直到添加完 3 条边;


查找流程包含在了插入流程中,一样的方式,只是不需要构建边,直接返回结果。



HNSW 算法是 NSW 算法的分层优化,借鉴了 skiplist 算法的思想,提升查询性能,开始先从稀疏的图上查找,逐渐深入到底层的图。



以上这 3 类算法都有 ElasticSearch 的插件实现(具体源码见最底下附件):


LSH 插件IVSPQ 插件HNSW 插件
概述在创建 index 时传入抽样数据,计算出 hash 函数。写入时增加 hash 函数字段。召回用 minimum_should_match 控制计算量在创建索引时传入聚类点和码本,写入数据就增加聚类点和编码字段,召回先召回编码后距离近的再精确计算召回扩展 Lucene 的 DocValues,在每次生成 segment 前,获取 DocValue 里的原始值,并调用开源 HNSW 库生成索引
优点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.全内存

ZSearch HNSW 插件

我们根据自己的场景(轻量化输出场景),选择了在 ES 上实现 HNSW 插件。因为我们用户都是新增数据,更关心 top10 的向量,所以我们使用了通过 seqNo 去 join 向量检索引擎方式,减少 CPU 的消耗和多余 DocValues 的开销。

对接 porxima 向量检索框架:

  • proxima 是阿里内部达摩院开发的一个通用向量检索引擎框架,类似与 facebook 开源的 faiss;

  • 支持多种向量检索算法;

  • 统一的方法和架构,方便使用方适配;

  • 支持异构计算,GPU;


实现 ProximaEngine

写入流程,扩展 ElasticSearch 本身的 InternalEngine,在写完 Lucene 以后,先写 Proxima 框架,Proxima 框架的数据通过 mmap 方式会直接刷到磁盘,一次请求的最后,Translog 刷入磁盘。就是一次完整的写入请求了。至于内存中的 segment,ElasticSearch 会异步到达某个条件是刷入磁盘。


Query 流程

查询的时候,通过 VectorQueryPlugin,先从 Proxima 向量检索引擎中查找 topN 的向量,获得 seqNo 和相似度,再通过构造 newSetQuery 的 FunctionScoreQuery,去 join 其他查询语句。


这里的数字型 newSetQuery 底层是通过 BKDTree 去一次遍历所得,性能还是很高效的。


Failover 流程

当然我们还要处理各种的 Failover 场景:


  • 数据从远端复制过来时:

  • 我们拦截了 ElasticSearch 的 recovery action;

  • 然后生成 Proxima 索引的快照,这个时候需要通过写锁防止数据写入,快照生成由于都是内存的,其实非常快;

  • 把 Proxima 快照复制到目的端;

  • 再进行其他 ElasticSearch 自己的恢复流程;


  • 数据从本地 translog 恢复时,我们会记录快照的 LocalCheckPoint,如果当前 CheckPoint 小于等于 LocalCheckPoint,可以直接跳过,否则我们会回查 Proxima 检索引擎,防止数据重试;

  • 目前还有一个情况,数据会有重复,就是主副分片全部挂掉时,translog 还未刷盘,数据可能已经写入 Proxima 了。

对比

sift-128-euclidean 100w 数据集:


(https://github.com/erikbern/ann-benchmarks)


HNSW 插件ZSearch-HNSW 插件
数据写入(单线程1000个 bulk 写入)1.初始写入 5min,25个 segment,最大 CPU 300%
2.合并成1个 segment 5min,最大 CPU 700%(本地最大)
构建索引 15min,因为单线程,所以最大 CPU 100%
查询1.Top 10,召回率98%
2.rt 20ms , 合并成1个 segment 后,5ms
1.Top 10,召回率98%
2.rt 6ms
优点兼容 failoverCPU 消耗少,无额外存储
缺点CPU 消耗大,查询性能跟 segment 有关主副分片全挂的情况下会有少量数据重复

总结

ES 参数配置最佳实践

  • 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 算法:召回率性能要求搞,数据量适中(千万以下),索引全存内存,内存够用;

未来规划

深度学习里的算法模型都会转化成高维向量,在召回的时候就需要用相似度公式来召回 topN,所以向量检索的场景会越来越丰富。


我们会继续探索在 ElasticSearch 上的向量召回功能,增加更多的向量检索算法适配不同的业务场景,将模型转化成向量的流程下沉到 ZSearch 插件平台,减少网络消耗。希望可以和大家共同交流,共同进步。


作者介绍


吕梁(花名:十倍),2017 年加入蚂蚁金服数据中间件,通用搜索平台 ZSearch 基础架构负责人,负责 ZSearch 组件在 K8s 上的落地及基于 ES 的高性能查询插件开发,对 ES 性能调优有着丰富的经验。


本文转载自公众号金融级分布式架构(ID:Antfin_SOFA)。


原文链接


https://mp.weixin.qq.com/s?__biz=MzUzMzU5Mjc1Nw==&mid=2247485678&idx=1&sn=6d79c6a7b3eea2dac4e8d2e93f9abd16&chksm=faa0e734cdd76e22d574acd3e7178eb3a9bf0b2fa0b7e7871b527abdad6176cb2b93f581f972&scene=27#wechat_redirect


2019-12-25 09:305598

评论

发布
暂无评论
发现更多内容

强化学习从基础到进阶-常见问题和面试必知必答[1]:强化学习概述、序列决策、动作空间定义、策略价值函数、探索与利用、Gym强化学习实验

汀丶人工智能

人工智能 深度学习 强化学习 深度强化学习 6 月 优质更文活动

即时通讯技术文集(第17期):社交软件红包技术专题 [共12篇]

JackJiang

网络编程 即时通讯 IM

【参考设计】2KW AC/DC数字电源方案

元器件秋姐

设计 电路 方案 电源 数字电源

LED透明屏和LED玻璃屏的区别

Dylan

分辨率 视频 图像 屏幕亮度 LED

TBB 开源库及并发 Hashmap 的使用

KaiwuDB

KaiwuDB TBB开源库 Hashmap使用

高性能网络 SIG 月度动态:联合 IBM 就 SMC v2.1 协议升级达成一致,ANCK 率先完成支持

OpenAnolis小助手

开源 ibm 高性能网络 anck 龙蜥sig

IT自动化运维工具用哪款?需要考虑哪些因素?

行云管家

IT运维 自动化运维 IT自动化运维

强化学习从基础到进阶-案例与实践[1]:强化学习概述、序列决策、动作空间定义、策略价值函数、探索与利用、Gym强化学习实验

汀丶人工智能

人工智能 深度学习 强化学习 深度强化学习 6 月 优质更文活动

华为云邓明昆:云原生时代,以开源赋能数字化转型

华为云开源

开源 云原生 数字化

一种实现Spring动态数据源切换的方法 | 京东云技术团队

京东科技开发者

spring aop 企业号 6 月 PK 榜 数据源切换

Java 中优雅的 RESTful API 设计:实现高效且易维护的接口

xfgg

Java RESTful API 6 月 优质更文活动

可观测性最佳实践 | 警惕!未知的风险正在摧毁你的系统

观测云

可观测性 运维监控 观测云 云原生可观测 可观测性用观测云

618夏日“折”学家活动上线!开通表盘会员解锁百变腕间风格

最新动态

观点碰撞燃爆会场|2023开放原子全球开源峰会区块链分论坛圆满落幕

开放原子开源基金会

区块链 开源 开放原子全球开源峰会 开放原子

Typora绿化版

源字节1号

开源 软件开发 前端开发 后端开发 小程序开发

Seata Saga 模式快速入门和最佳实践

阿里巴巴云原生

阿里云 云原生 seata

浅谈API安全

权说安全

API 安全

优化开发工作流的三大实用技巧,助力效率提升

龙智—DevSecOps解决方案

版本控制 版本管理

龙智携手Atlassian亮相DevOps国际峰会:释放团队潜力,以协作挑战不可能

龙智—DevSecOps解决方案

DevOps ITSM ITSM软件 工作管理

赋能中国软件,共筑开放生态|2023开放原子全球开源峰会软硬协同开源分论坛成功举办

开放原子开源基金会

开源 开放原子全球开源峰会 开放原子 软硬协同开源

基于双层缓存(DLC)机制解决热点缓存并发重建问题

xfgg

Java' 6 月 优质更文活动

GPT-4满分通过MIT本科数学考试!这套提示词火了

Openlab_cosmoplat

算法 ChatGPT

AI+电力、大模型主题人工智能师资培训班重磅招募中

飞桨PaddlePaddle

人工智能 百度 paddle

vivo 游戏黑产反作弊实践

vivo互联网技术

游戏黑产 游戏礼券

软件测试/测试开发丨Pytest结合数据驱动-CSV

测试人

程序员 软件测试 自动化测试 csv pytest

详解4种模型压缩技术、模型蒸馏算法

华为云开发者联盟

人工智能 华为云 华为云开发者联盟 企业号 6 月 PK 榜

海南正规等级保护测评单位有哪些?叫什么名字?

行云管家

等保 等级保护 海南 等保测评单位

模型当道 开源聚力|2023开放原子全球开源峰会开源大模型分论坛圆满收官

开放原子开源基金会

开源 大模型 开放原子全球开源峰会 开放原子

用简单的描述带你理解运算放大器

矜辰所致

运算放大器 6 月 优质更文活动

蚂蚁金服 ZSearch 在向量检索上的探索_软件工程_十倍_InfoQ精选文章