申请试用
HOT
登录
注册
 
账号已存在
如何打造高性能向量检索平台(1)
AICUG人工智能社区
/
发布于
/
383
人观看

向量检索算法

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

  • 基于树的搜索算法(例如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 点赞
1 收藏
0下载
确认
3秒后跳转登录页面
去登陆