Paper reading 第一期｜SIGMOD 2021：Milvus 向量数据库系统解读

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