申请试用
HOT
登录
注册
 
如何打造高性能向量检索平台(1)
0 点赞
0 收藏
0下载
AICUG人工智能社区
/
发布于
/
332
人观看

向量检索算法

精确检索。通过在整个向量空间内,遍历所有已存向量计算其与检索向量的
距离,通常是计算欧几里德距离或者点积。 ⚫ 近似检索。通过聚类、降维或者编码等方式,将原来需要在全量高维向量空
间内的搜索,转换为在小范围空间或者相对低维的向量空间内搜索的算法。

  • 基于树的搜索算法(例如k-d tree)。
  • 基于哈希的空间划分法(例如LSH)。
  • 向量量化的编码算法(例如PQ)。
  • 基于图的搜索方法(例如SPTAG)。
展开查看详情

1. AI 工程架构系列沙龙 欢迎关注AICUG人工智能技术社区 欢迎关注 58AILab 公众号 欢迎关注58技术公众号 (www.aicug.cn)

2.如何打造高性能向量检索平台 分享嘉宾:陈泽龙-58同城AI Lab后端高级开发工程师

3. 个人简介 ⚫ 工作经历 ⚫ 2019年7月~至今 58同城 AI平台部 ⚫ 2016年7月~2019年7月 中科院信工所 后端 ⚫ 教育背景 ⚫ 2013年9月~2016年7月 硕士 中国科学院大学 联系方式:chenzelong@58.com

4. 目录 ⚫ 背景 ⚫ 向量检索原理 ⚫ 向量检索平台设计 分享人:余意 ⚫ 遇到的问题及解决方法

5.应用场景 ⚫ 在推荐系统中,召回环节基于用户向量计算其最相似的N个物 品向量。 ⚫ 在问答系统中,基于问题向量匹配相似的N个问题。 ⚫ 在视频或图像检索中,通过对视频截图提取向量,然后搜索相 似图像及图像对应的视频。 分享人:余意

6. 向量检索算法 ⚫ 精确检索。通过在整个向量空间内,遍历所有已存向量计算其与检索向量的 距离,通常是计算欧几里德距离或者点积。 ⚫ 近似检索。通过聚类、降维或者编码等方式,将原来需要在全量高维向量空 间内的搜索,转换为在小范围空间或者相对低维的向量空间内搜索的算法。 ⚫ 基于树的搜索算法(例如k-d tree)。 ⚫ 基于哈希的空间划分法(例如LSH)。 分享人:余意 ⚫ 向量量化的编码算法(例如PQ)。 ⚫ 基于图的搜索方法(例如SPTAG)。

7. 向量检索需要解决的问题 ⚫ 检索速度。线上服务,最基本的要求是单次请求耗时,这也是衡量一个服 务性能好坏的基本指标,目标是至少达到业内水平,比如百万级向量单次 检索耗时低于5ms。 ⚫ 内存使用。向量检索是一个计算密集型任务,支持只在 RAM 上搜索,内 存资源的大小决定向量数据库的量级。 分享人:余意 ⚫ 准确率。特指近似检索,精确检索不存在准确率问题。在近似检索中,选 择向量量化的编码算法,牺牲了部分准确率,换取检索速度。

8. 向量检索开源项目 ⚫ Faiss。Facebook AI Research开源的稠密向量相似度搜索和聚类框架。 ⚫ SPTAG。分布式近似最近邻域搜索(ANN)库,由MicroSoft Bing团队开源。 ⚫ Milvus。一个开源的分布式向量搜索引擎,提供完整的向量数据更新,索引 分享人:余意 与查询。由ZILLIZ开源。

9. 技术选型 ⚫ 开源项目对比 ⚫ 技术选型 分享人:余意 Milvus是基于Faiss开发,且开源时间晚;SPTAG是基于近邻图的最近邻搜索 算法,全量构建耗时特别长,实时的增量需要更新整个近邻图。最终选择Faiss

10. 目录 ⚫ 背景 ⚫ 向量检索原理 ⚫ 向量检索平台设计 分享人:余意 ⚫ 遇到的问题及解决方法

11. 典型的索引类型 ⚫ IndexFlatL2。一种精确检索索引,检索时需要计算待检索向量与所有 向量的L2距离(欧几里得距离)。 ⚫ IndexIVFFlat。一种近似检索索引,增加了聚类和倒排,牺牲了部分 准确性,提高了检索速度。 ⚫ IndexIVFPQ。一种近似检索索引,增加了量化、聚类和倒排。进一步 分享人:余意 提高了检索速度,同时,通过有损压缩,大大降低了内存占用。

12. IndexIVFFlat ⚫ IndexIVFFlat 主要参数 ⚫ nlist: 倒排表的长度,对应聚类的中心点数。 ⚫ nprobe: 每次查询需要查的倒排list的个数。 ⚫ quantizer:量化器,或者说是码表,存储所有的聚类中心点。 ⚫ d:数据源向量维度。 分享人:余意 ⚫ IndexIVFFlat 索引构建 ⚫ 训练:训练过程主要是一个聚类过程, 得到nlist个聚类中心,并建立倒排表。

13. IndexIVFPQ ⚫ IndexIVFPQ 主要参数 ⚫ nlist: 倒排表的长度,对应聚类的中心点数。 ⚫ nprobe: 每次查询需要查的倒排list的个数。 ⚫ d:数据源向量维度。 ⚫ m:向量切分子向量的个数。 ⚫ 分享人:余意 nbits:每个子向量的码书需要使用nbit个比特表示,例如nbits=8,能表示 00000000~11111111总共256个码。

14. IndexIVFPQ ⚫ IndexIVFPQ 索引构建 ⚫ 初聚类:跟IndexIVFFlat的训练过程一样,进行K-means。 ⚫ 训练量化残差:分成m个子向量,对每个分段都进行聚类。 ⚫ 索引构建:计算待添加向量与nlist个聚类中心的L2距离,选择粗聚类中心,分段 计算子聚类中心。加入倒排表。 ⚫ 分享人:余意 检索:计算待检索向量与nlist个聚类中心的距离,选择最近的nprobe个粗聚类中 心,然后计算当前向量与所有子聚类中心内积(固定,例如256个,最后得到的 其实是与子聚类码的距离),取最大的topK(内积越大,相似度越高)。

15. PQ量化 ⚫ PQ(乘积量化) ⚫ 切分空间。将D维空间切分成M份 ⚫ 量化。给每个子空间单独训练一本码书。量化的过程就是计算每个短向量距离最 近的聚类中心,距离就是L2距离。 分享人:余意

16. 压缩聚类 ⚫ 压缩: 例如,一个D=128维的原始向量,它被切分成了M=8个d=16维的短向量, 同时每个短向量都对应一个量化的索引值(8bit即1字节),那么一行向量的大小 为8*8/8=8字节。没有采取PQ时,一行向量的大小为128*4=512字节。 ⚫ 聚类: 每个分段聚类,8bit代表256个聚 类中心的索引值,那么,M个分段总共代 表256的M次方个类。类似于8位256进制 的数可以表达的最大数。

17. 距离计算 分享人:余意 • 对称距离计算:直接使用两个压缩向量x,y的索引值所对应的码字q(x),q(y)之间的距离 代替之。 • 非对称距离计算:使用x,q(y)之间的距离代替x,y之间的距离,其中x是测试向量。虽 然y的个数可能有上百万个,但是q(y)的个数只有固定个。

18. 目录 ⚫ 背景 ⚫ 向量检索原理 ⚫ 向量检索平台设计 分享人:余意 ⚫ 遇到的问题及解决方法

19. 系统架构 实时检索 向量新增/更新/删除 分城市检索 Web平台 检索服务 版本 负载均衡 滚动升级 蓝绿升级 管理 资源 全量索引构建 增量索引 分布式索引 管理 (IndexIVFFlat / IndexIVFPQ / IndexFlat2) 算法库 Faiss …… 权限 管理 Docker、Nvidia-Docker2 日志 查询 Kubernetes 监控 高性能网络文件系统 存储 MySQL HDFS WRedis (WFS) 告警

20. 索引构建 全量索引构建 IndexFlatL2 / IndexIVFFlat / IndexIVFPQ 增量索引构建 ` 逻辑层 普通索引构建 分布式索引构建 Kubernetes 集群 Pod Pod1 Pod2 … Podn 分享人:余意 Pod 存储层 全量索引 子索引1 子索引2 子索引n 全量索引 增量索引

21.增量索引 增量 数据 SCF服务(WpaiFaissIndex) 增量数据库 增量索引接口 (Redis) 分享人:余意 WFS 增量服务程序 定时持久化 定时读取 索引文件 索引文件 初始化

22.在线检索 向量检索接入SCF服务 通用检索接口 实时增量添加接口 逻辑层 检索实例 在线检索POD 在线检索POD WRedis C++gRPC server C++gRPC server 向量检索 向量检索 ` 增量索引构建POD 增量索引更新 增量索引更新 增量索引构建 分享人:余意 WFS Kubernetes

23. 在线检索负载均衡 在线检索gRPC实例负载均衡实现 Kubernetes api-server 节点变化 检索异常降权 effectiveWeight >>= 1 Watch线程 检索正常升权 新增(初始化权重) effectiveWeight += weight - effectiveWeight + 1) >> 1 删除 Faiss 后端节点IP候选池 检索节点IP 判定结果 grpc-server

24.分布式索引-索引构建 WFS 索引保存 子索引文件1 子索引文件2 子索引文件3 子索引文件n 索引构建 … 索引构建程序 索引构建程序 索引构建程序 索引构建程序 读取数据 分享人:余意 数据分片1 数据分片2 数据分片3 … 数据分片n 数据切片 HDFS/WFS 原始向量数据 WFS/WOS

25.分布式索引-索引检索 SCF服务 结果合并排 接口请求处理 序 子索引1 负载均衡 子索引2 负载均衡 … 子索引n 负载均衡 Pod1 Pod2 Pod1 Pod2 Pod1 分享人:余意 Pod2 K8S集群 …… Pod3 Pod4 Pod3 Pod4 Pod3 Pod4 存储层 子索引1 子索引2 子索引n

26.蓝绿部署 用户 向量检索接入SCF服务 通用检索接口 Pod1 Pod2 Pod1 Pod2 Pod3 Pod4 Pod3 Pod4 索引 V1 索引 V2

27.蓝绿部署-流量切换 Deployment task-1-v1 Deployment task-1-v2 修改service 的selector Service Service

28. 目录 ⚫ 背景 ⚫ 向量检索原理 ⚫ 向量检索平台设计 分享人:余意 ⚫ 遇到的问题及解决方法

29. 在线检索性能优化 ⚫ OPT_NUM_THREADS调优,设置OMP_NUM_THREADS=1 ⚫ 检索QPS较不设置提升约26倍 ⚫ 实现C++版本的GRPC服务端 ⚫ 解决Python版的grpc服务CPU占用率低的问题 ⚫ QPS最大值提高约5.5倍 ⚫ 检索平均耗时降低45.5%

0 点赞
0 收藏
0下载