申请试用
HOT
登录
注册
 
Paper reading 第一期|SIGMOD 2021:Milvus 向量数据库系统解读
4 点赞
0 收藏
5下载
Milvus.io
/
发布于
/
119
人观看

Paper reading直播是由 Milvus 社区发起的学术直播间,分享业内前沿学术论文,与大家交流人工智能与数据库交叉领域最新研究方向。

作为全球首款开源向量数据库,Milvus 在过去两年内快速发展,已经成为 LF AI&Data 基金会旗下最活跃、最具影响力、应用最广的毕业项目之一。这篇介绍Milvus 向量数据库的技术论文被 SIGMOD 2021 录用,说明 Milvus 技术与架构得到了学术界与工业界同行的共同认可。

千里之行,始于足下。Paper reading 直播的第一期,我们就从 Milvus 的技术论文开启!

本期直播,我们邀请到了 Zilliz 高级研究员易小萌,为大家解读 Milvus 团队发表在SIGMOD 2021 上的技术论文。

  • 论文链接:https://zilliz.com/whitepapers/milvus-a-purpose-built-vector-data-management-system
  • 直播预约:Zilliz视频号预约观看 ,如果对主题感兴趣,也欢迎添加小助手微信:Zilliz-tech 备注“直播”加入讨论群与讲师实时QA
  • 更多背景可查看:https://zhuanlan.zhihu.com/p/387724999
展开查看详情

1.Milvus: A Purpose-Built Vector Data Management System Jianguo Wang, Xiaomeng Yi, Rentong Guo, Hai Jin, Peng Xu, Shengjun Li, Xiangyu Wang, Xiangzhou Guo, Chengming Li, Xiaohai Xu, Kun Yu, Yuxing Yuan, Yinghao Zou, Jiquan Long, Yudong Cai, Zhenxiang Li, Zhifeng Zhang, Yihua Mo, Jun Gu, Ruiyi Jiang, Yi Wei, Charles Xie

2.Unstructured Data are Dominating Image Int, float, Text Json video Domain specific String, … audio ABCDEFG 2021.04.10 Structured data Unstructured data 2

3.Unstructured Data are Dominating Image Int, float, Text Json video Domain specific String, … audio ABCDEFG 2021.04.10 80% of global data will be unstructured by 2025. -IDC 3

4.Analysis based on vectors Data Vector Analysis in vector space 0.03, 0.12, 0.01, …. 0.01, 0.01, 0.02, …. 0.02, 0.02, 0.03, …. 0.04, 0.11, 0.05, …. … 0.11, 0.13, 0.01, …. 0.06, 0.01, 0.02, …. 0.02, 0.02, 0.03, …. 4

5.Analysis based on vectors Machine Learning Models Milvus 0.03, 0.12, 0.01, …. 0.01, 0.01, 0.02, …. 0.02, 0.02, 0.03, …. 0.04, 0.11, 0.05, …. … 0.11, 0.13, 0.01, …. 0.06, 0.01, 0.02, …. 0.02, 0.02, 0.03, …. 5

6.The open-source journey of Milvus 6.7K GitHub Stars 2018.10 2019.04 2019.06 2019.10 145 Contributors 1st The Milvus Open 1000+ Global Users Seed Idea 0.1 Source User 2021.06 2020.03 2020.10 2021.03 2021.06 1ST LF AI Joined LF AI & Commu nity Milvus &Data Gradua Milvus Data Confere nce 1.0 te Project 2.0 6

7.Common User Requirements Efforts in Milvus Efficiency: § SIMD & Cache based optimization § Large data volume § Heterogenous computing § Dynamic data management § LSM tree § Snapshot isolation § Execution plan optimization Advanced query semantic: § Vector fusion § Vector similarity search § Iterative merging algorithm § Attribute filtering § Distributed data processing § Multi-vector search § Easy-to-use interfaces 7

8.Agenda Design Overview Optimizations Advanced Query Processing System Implementation Example Applications Performance Evaluation 8

9.Design Overview Applications Query Processing Vector search Attribute filtering Multi-vector query Request Handler Cache- & SIMD-aware Heterogenous Acceleration Data insert Query MemTable Buffer pool Indexing Memory IVF_FLAT IVF_PQ … Collection A Collection B … MemTable HNSW … Flush Load Original data Index Small Small Segments … Segments Vectors Attributes Indexes Persistent Data Compaction … … Storage Large Segments Multi-storage (S3/HDFS/…) Snapshot Management 9

10.Agenda Design Overview Optimizations Advanced Query Processing System Implementation Example Applications Performance Evaluation 10

11.Cache-aware optimization: original implementation Key idea: heaps query vectors data vectors § Assign one query to a v0 thread T0 H0 q0 v1 thread per time v2 § Compare query vector thread T1 H1 q1 v3 v4 with all data vectors … … … … Issues: thread Tt-1 Ht-1 qt-1 vn … § High cache miss rate § Limited parallel when m qt+0 qt+1 is small … qm 11

12.Cache-aware optimization: design § Divide both data vectors and query vectors into blocks § Process one query vector block per time § Assign data vector blocks to threads § One heap per thread per query vector 12

13.Cache-aware optimization: design § Divide both data vectors and query vectors into blocks § Process one query vector block per time § Assign data vector blocks to threads § One heap per thread per query vector 13

14.Cache-aware optimization: design § Divide both data vectors and query vectors into blocks § Process one query vector block per time § Assign data vector blocks to threads § One heap per thread per query vector 14

15.Cache-aware optimization: design § Divide both data vectors and query vectors into blocks § Process one query vector block per time § Assign data vector blocks to threads § One heap per thread per query vector 15

16.Cache-aware optimization: performance evaluation 16

17.SIMD support Vectorized Execution § Add AVX512 instruction support § Single Instruction, Multiple Data § Automatic SIMD-instructions selection 17

18.GPU acceleration Issues: § Limited memory capacity § High data transfer cost § Underutilized PCIe bandwidth Solutions: § Bulk data transfer § Let most frequently used data resident in GPU memory § Data transfer for only computation-bound workloads 18

19.Agenda Design Overview Optimizations Advanced Query Processing System Implementation Example Applications Performance Evaluation 19

20.Attribute filtering: problem and strategies Problem: Strategies: Given a query vector qv and a constraint on attributes Ca. Find k entries among all the entries that satisfies Ca, whose vector is the most similar to qv. Vector scan after Vector index Attribute filtering attribute filtering search after after vector index attribute filtering search Examples: Searching for T-shirts similar to an image that cost less than $100. Recommend some country music to me. Attribute-based data Strategy choosing partition, only search based on related partitions estimated cost 20

21.Attribute filtering: performance evaluation 21

22.Multi-vector search: problem and solutions Problem: Both data entries v and queries q contains µ vectors. Given a vector similarity function f and a score aggregation function g, find k entries with highest score value: 𝑔(𝑓 𝑣! , 𝑞! , 𝑓 𝑣" , 𝑞" , … , 𝑓(𝑣# , 𝑞# )) Decomposable cases: vector fusion General cases: iterative merging 𝑔 𝑓 𝑣! , 𝑞! , 𝑓 𝑣" , 𝑞" , … , 𝑓 𝑣# , 𝑞# Search top- k’ result for each vector = 𝑓 ℎ 𝑣! , … , 𝑣# , ℎ′ 𝑞! , … , 𝑞# Try to find result with NRA Example: if k results can be determined if then Return results f: inner product h: concatenation, Otherwise g: weighted sum h’: weighted Increase k’ and repeat concatenation 22

23.Multi-vector search: performance evaluation 23

24.Agenda Design Overview Optimizations Advanced Query Processing System Implementation Example Applications Performance Evaluation 24

25.System Implementation Asynchronous Processing : § Write ahead logs § Background operation Read-write consistency : § LSM structure § Snapshot Isolation Distributed processing: § Compute/storage separation § Stateless computing instances 25

26.Agenda Design Overview Optimizations Advanced Query Processing System Implementation Example Applications Performance Evaluation 26

27.Example Applications Similar trademark search Floor plan search Chemical Structure Search Video search, chatbots, recommendation engine, biological multi-factor authentication… Input Output 27

28.Agenda Design Overview Optimizations Advanced Query Processing System Implementation Example Applications Performance Evaluation 28

29.Performance Evaluation Platform: § Alibaba Cloud § instance type: ecs.g6e.4xlarge Dataset: § SIFT1B: 1 billion, 128-dimension IVF indexes § Deep1B: 1 billion, 128-dimension Competitors: § Open-source: SPTAG, Vearch § Commercial: System A, B, C HNSW index 29

4 点赞
0 收藏
5下载