原文链接：https://www.cs.purdue.edu/homes/csjgwang/pubs/SIGMOD21_Milvus.pdf

从向量数据库引擎的角度介绍了milvus的查询、索引以及异构加速设计；

Milvus

Intro

milvus是在Facebook的Faiss基础上构建的，Faiss是一个开源的向量相似度搜索c++库。milvus做了如下优化

  • 针对不同计算平台进行优化（CPU、GPU）

    • CPU方面做了向量查询的CPU L3cache优化和根据CPU Tag自动选择SIMD指令优化；

    • GPU方面设计了混合索引机制和多GPU调度策略；

  • 支持动态数据管理，将数据查询分散到多个节点

  • 支持标量属性过滤和多向量查询处理（相对于单向量查询）

    • 属性过滤方面设计了基于分区的过滤算法；

    • 多向量查询处理方面设计了向量融合、迭代合并两种算法；

  • 提供多语言SDK调用接口

System Design

支持的查询类型：

  • 向量查询、属性过滤、多向量查询（根据用户定义聚合函数将数据中多个向量属性的相似度进行聚合）

支持的索引方面：

  • 基于量化的索引（IVF_FLAT、IVF_SQ8、IVF_PQ）、图索引（HNSW、RNSG），并支持添加新索引机制

动态数据管理：

  • 采用LSM-tree日志合并树的思想支持高效插入和删除，新插入的数据首先存放在内存中的MemTable；

  • Memtable大小达到阈值或者每隔一秒，Memtable变为immutable并刷新到磁盘作为一个新的segment；

  • 较小的segments通过tiered merge机制被选择合并成更大的segment来加速顺序访问；

  • 删除操作通过”out-of-place”的方式执行（不直接在原始数据上修改），merge操作时移除已删除的数据；

  • 数据更新操作通过删除+插入操作完成。

  • 默认情况下milvus只为超过1GB的segment构建索引，用户也可以对任何大小的segment手动构建索引；

  • 数据和对应的索引文件存放在相同的segment中。segemt是milvus搜索、调度和缓存的基本单位；

  • milvus使用快照隔离机制保证读写操作共享一致性试图，避免读写互相影响；

数据存储管理：

  • 向量属性存储：采用列存储方式保存每条数据的向量属性；

  • 标量属性存储：每个属性列按照的列表形式进行列存储，key是属性值、value是行ID；对于磁盘上的数据构建了skip pointers索引来加速列标量属性上的点查询和范围查询；

  • Bufferpool：milvus假设所有数据和索引可放入内存，内存不足时按照segment粒度进行LRU缓存替换；

  • Multi-storage：milvus支持包括本地文件系统、Amazon S3、HDFS在内的多种底层存储方案；

分布式系统

  • 按照分布式系统中的存储计算分离、共享存储、读写分离、一写多读的设计原则进行构建

Heterogeneous Computing

背景：IVF_FLAT、IVF_SQ8、IVF_PQ等基于量化的索引机制有两个量化器：粗量化和细量化

  • 粗量化：使用K-means将向量数据聚类到K个buckets中，milvus和Faiss默认K=16384；

  • 细量化：编码每个buckets中的向量；

不同的索引机制可能使用不同的细量化策略，IVF_FLAT保存原始的向量数据；IVF_SQ8采用标量量化将一个4B浮点数据压缩成1B的整型数；IVF_PQ采用乘积量化技术将每个向量分为多个子向量，并对每个子空间进行K-Means聚类。在基于量化的索引上进行向量查询分为两个步骤：（1）比较bucket中心找到最近的n_{probe}个buckets；（2）在找到的buckets中比较每个量化后的向量；

面向CPU的优化：

  • 假设用户发起m个向量的top-k查询。Faiss采用OpenMP多线程技术并行处理m个向量查询请求，每个线程负责一个向量查询请求，将查询向量qi和所有的n个向量数据进行比较，并维护自己的k-size堆保存结果。Faiss的这种多线程策略有两个缺陷：

    • （1）每个查询都需要整个数据集流经CPU缓存，不能被下一个查询复用，因此每个线程需要访问m/t次数据集，其中t为线程数量；（2）m很小时无法充分利用多核并行性。

  • 批量查询策略：将n个数据划分给t个线程，将m个请求s一组划分成块。$s = \frac{L3_cache_size}{𝑑 × sizeof(float) + 𝑡 × 𝑘 × (sizeof(int64) + sizeof(float))}$ 保证请求块中的查询向量和top-k堆结构能够放入缓存。

    • milvus每次使用多线程计算一个查询块中每个查询的top-k结果；

    • 为减少同步开销，milvus为每个线程的每个查询都分配一个top-k堆。也就是说，对于某个向量q的查询，milvus将整个查询数据集按照线程数量划分成多个块，多线程并行计算自己所在块的top-k结果，最终将每个线程的top-k结果进行合并得到最终向量q的top-k查询结果。

    • 一个block中的s个请求共用一次数据集访问，平均每个线程的数据集访问次数变为了m/(s*t)；

  • SIMD指令自动选择：对于每个常用函数（例如相似度计算）milvus实现了SSE、AVX、AVX2、AVX512四个版本并放置在不同的源文件中，针对不容的SIMD标志可以选择不同的版本进行编译。运行时milvus根据当前CPU标志自动选择合适的SIMD指令，并使用hooking技术链接合适的函数指针。

面向GPU的优化：

  • Faiss中top-k中k最大为1024，milvus通过多轮迭代技术支持最大k为16384。milvus第一轮类似Faiss计算出top1024个结果对应的距离和ID，记第一轮的最大距离为dl，第二轮milvus在剩下的距离大于等于dl的结果中挑选下一批1024个结果，如此迭代。

  • Faiss需要提前知道GPU设备数量进行编译，milvus支持用户在运行时自定义GPU数量，milvus编译生成的库可在任意数量GPU的服务器上运行。具体来说milvus采用基于segment的查询调度机制，将查询以segment为单位在可用的GPU设备上进行调度。

GPU-CPU协同设计：

  • 在GPU内存无法加载全部数据集的情况下，Faiss使用IVF_SQ8量化索引进行数据压缩并通过PCIe总线将数据从CPU内存搬运到GPU内存中。该策略有两个缺陷：

    • Faiss采用逐个bucket搬运的方式，PCIe带宽无法被充分利用（PCIe3.0x16支持15.75GB/s最大带宽）；

    • 考虑到数据搬运延迟，在GPU中执行查询可能不是最优选择；

  • Milvus在CPU和GPU间一次传输多个bucket，提高了IO带宽（说是因为采用了基于LSM的非原位数据更新）

  • 此外，milvus考虑将大batch查询放在GPU执行，例如batch size超过1000时，Milvus将使用GPU执行所有查询并将涉及的数据buckets加载到GPU内存中。如果GPU内存无法加载所有的bucket数据，milvus将采用混合执行的方案。

    • 将查找$n_{probe}$个目标bucket的计算放在GPU中执行，在CPU中扫描每个bucket中的量化向量数据；

    • 动机：步骤1中的buckets中心体量很小，且批查询中所有查询都需要比较相同的buckets中心数据。步骤2中不同查询请求查询的量化向量较为分散；

Advanced Query Processing

属性过滤：假设每条数据包含一个标量属性和一个向量属性，分别有查询限定C_A、C_V。

  • 策略1 attribute-first-vector-full-scan：使用C_A采用标量索引进行过滤，对剩余数据采用向量全表扫描机制。当C_A高选择性时采用；

  • 策略2 attribute-first-vector-search：使用C_A过滤数据得到位图bitmap，使用C_V进行一般向量搜索，并查询搜索结果在位图中是否有效，有效结果存入top-k结果集中。当C_A、C_V都具有一定的选择性时使用；

  • 策略3 vector-first-attribute-full-scan：先向量搜索，后全表扫描标量过滤，向量搜素通常输出\theta k个结果保证最后可以查找到top-k个结果。C_V高选择性时使用。

  • 策略4 cost-based：采用AnalyticDB-V中代价估计策略评估前三个策略的执行代价，选择代价最小的策略执行查询计划，适用性很强。

  • 策略5 partition-based：按照频繁访问的属性划分数据集，将策略4应用到每个数据划分。milvus动态维护一个属性查询访问计数hash表。每个partition应该也维护了一个属性范围用于加速过滤。

    • milvus采用离线的方式对历史数据构建partition，构建完成后应用于在线查询；

    • 用户可以自定义分区数量，分区数量太大导致分区内向量数量过少，标量属性过滤趋近线性搜索。分区数量太小，分区内数据量增大，过滤无关数据效率变低。Milvus推荐每个分区内容纳1 million百万条向量。

多向量查询：vector fusion、iterative merging

System Implementation

异步处理：

  • 通过异步处理最大限度的减少前台处理。当Milvus接收到大量写请求时，会先将操作（类似于数据库logs）物化到磁盘然后响应用户。后端线程将逐步执行这些操作，因此用户可能不会立即看到插入的数据；

  • Milvus提供flush() API阻塞当前到来的所有请求，直到系统处理完目前正在等待的所有操作；

  • Milvus构建索引的操作也是异步的；

快照隔离：

  • milvus通过快照隔离读写操作互相之间的影响。每个查询都是在快照上执行。后续对系统的更新操作将创建新的快照，不会阻碍当前进行的查询；

  • milvus采用LSM-Style的方式管理动态数据。新数据首先被插入内存然后作为immutable segment刷入磁盘。每个segment都有多个版本，segment内部的数据和索引发生变化时（flushing、merging、building index）都会生成新的版本。当前时刻所有最新版本的segment组成了当前的快照。每个segment可以被多个快照引用。后端会有一个线程，将没有引用segment删除做垃圾回收。

分布式系统（更全面的介绍看最近的Manu论文）：
数据在各个读节点上按照一致性hash进行shard，分区信息保存在coordinator层。所有的计算节点通过K8s管理进行节点故障重启、节点扩展。采用单写节点，多个读节点。写节点故障时milvus依赖WAL保证写操作原子性。为了降低计算节点和存储节点之间的网络通信带宽，milvus采用两个优化：

  • 计算层发送logs而非真实数据到存储层，后端有线程会处理这些logs中的操作；

  • 每个计算实例都有足够的缓存和SSD来减少对共享存储的访问；

Manu

前言：Manu采用WAL和Binlog作为服务基础，写组件被设计成为日志发布者，其他所有的只读组件、例如分析组件和查询搜索组件被设计为日志订阅者。此外，Manu使用MVCC多版本并发控制以及一个延迟一致性模型来简化系统各个组件之间的通信和合作。上述设计思想是的Manu系统内部耦合度低，利于在云环境中的弹性扩展和版本迭代。

向量数据库应用的独有需求使得Milvus必须在原有的关系型数据库设计原则上做出改变，向量查询应用的特性：

  • 没必要支持复杂事务：低级别的ACID对于大部分的向量数据库应用来说都是足够的；

  • 性能和一致性之间的权衡很重要：传统关系型数据库在强一致性和最终一致性之间很少提供折中方案。向量数据库应用中新插入的数据对查询是否可见可以经过一段缓冲时间，这个可调节的时间提供了可调节的一致性；

  • 硬件成本感知的细粒度资源分配弹性：向量搜索和索引构建等计算密集型操作可能需要GPU和FPGA来优化，将读写分离有助于降低系统耦合。Manu在函数功能层面而不是在系统层面进行弹性和资源隔离，提供更加细粒度的硬件资源分配；

总的来说，Manu认为向量数据库应该提供可调节一致性、函数功能粒度的解耦、各组件均支持弹性扩展的能力。Manu的设计目标包括：易扩展和迭代、可调节一致性、计算资源弹性伸缩、高可用、高查询性能、低迁移成本。

Manu System

data model

  • Scheme：类似于关系数据库中表格的属性设置，如字段、主键、字段类型等等。如果用户没有指定主键，系统将为每条记录（类似于关系数据库中表内的一条数据）自动添加自增主键。此外每条记录最后隐藏一个逻辑序列号（LSN）。属性支持过滤，不支持join和聚合操作。

  • Collection：记录的集合，类似关系数据表，区别是向量数据库中的Collections之间无关联，不支持join。

  • Shard：对应插入/删除通道。记录在插入或者删除时经过主键哈希被分配到多个shard中。

  • Segment：每个shard内部的数据划分成多个Segment，Manu数据放置的基本单位。Segment有growing和sealed两种状态。growing状态的segment接受新写入的数据，sealed状态segment是只读的。当growing状态的segment大小达到512MB或者超过固定时间没有接收数据插入（例如十秒），状态将变为sealed。如果插入速率很低，系统内部产生大量较小segment，Manu会将小segments合并为大segmetn提高查询效率。

Log Backbone

数据节点订阅WAL并将基于行的WAL转换为基于列的binlogs。日志记录任何改变系统状态的操作，包括：数据定义请求（创建删除集合）、数据操作请求（插入删除向量）、系统协调信息（集合加载到内存或者释放）。集合查找请求不会被写入日志因为他们是只读操作，不会改变系统状态。Manu使用逻辑日志而非物理日志，逻辑日志只记录操作事件而非最终对物理数据页的修改，日志的订阅者可以根据自身需要按照不同方式消费日志。

以数据插入为例：代理根据记录ID使用一致性哈希将数据映射到哈希环中，每一个日志器负责处理一个或多个哈希桶。上文中每一个shard对应哈希环中的一个哈希桶和一个WAL通道。当日志器收到一个请求，首先首先验证合法性，然后通过中央时钟服务分配一个LSN隐藏字段。接着确定数据应该存放在哪个segment并将数据写入WAL。logger也会将数据ID到segmentID的映射关系写到本地LSM-tree中并定期将LSM-tree的增量部分刷盘到对象存储，因此数据entity到segment的映射关系是以RocksDB的SSTable形式保存。每个logger将自己管理的shard中数据segment映射关系对应的SSTable从对象存储中缓存到本地。

WAL基于云的消息队列实现。数据定义和系统协调信息使用自己的channel，数据操作请求被哈希到多个通道增加吞吐量。数据节点订阅WAL，并将基于行的日志转换为基于列的binlog。WAL中相同属性的值在binlog中以列的形式保存。索引节点只需从binlog中读取需要构建索引的列数据，减少了读放大。

组件之间的系统协调信息也是通过发布订阅日志实现的。当segment被写入存储时数据节点将事件写入日志，当索引构建完成时索引节点将事件写入日志。

Tunable Consistency

Manu的时间戳LSN由物理时间戳和逻辑时间戳组成。逻辑时间戳是应对同一物理时间发生多个事件的情况。物理事件戳记录请求被Manu接收的时间。为了实现延迟一致性，日志订阅者以查询节点为例，需要知道三个信息：（1）用户指定的容忍时间$t$，（2）最后一个数据更新的时间，（3）查询请求发起的时间。为了让每个日志订阅组件获取信息（2），time-ticks信息被周期性的插入每个日志通道以通知数据同步。记订阅者接收的最新time-tick为$L_s$，查询的发起时间为$L_r$，如果不满足$L_r-L_s<t$，则需要等待下一个time-tick到来。

Index Building

Manu中存在两种索引构建场景：

  • 批量索引构建：当用户为整个collection创建索引，index调度器从数据节点获取集合内所有segment的路径，并通知索引节点为每个segment构建索引。

  • 流式索引构建：用户持续性的插入新数据，索引以异步方式构建，不会阻碍搜索服务。具体来讲，当segment接收新数据并到达指定大小，其所在的数据节点将此segment变为sealed状态并作为binlog写入对象存储。此后，数据调度器通知索引调度器，索引调度器通知索引节点对此segment构建索引。索引节点从对象存储中读取索引构建需要的列并构建索引。对于数据删除，Manu使用位图记录删除的向量，并在删除数据量达到一定阈值后重新为segment构建索引。

  • 对于批式索引构建和流式索引构建，当索引构建完成后，索引节点将索引文件持久化到对象存储，并将索引文件路径发送到索引调度器。索引调度器会通知查询调度器以便查询节点可以加载向量查询需要的索引文件。Manu也会在适当的时候在多个segment之上构建联合索引。

对于向量搜索，Manu将一个集合划分成多个segments并将segments分散到多个查询节点并行查询。代理proxy通过询问查询调度器获取查询节点上的segments分布，并将查询请求发送到持有对应segment的查询节点。查询节点在本地执行两阶段查询，对于top-k查询，查询节点首先获得segment粒度的top-k结果，然后内部汇总得到query节点粒度的top-k结果。然后代理proxy将收集多个节点粒度的top-k结果进行合并，返回给应用程序。对于删除操作，查询节点使用位图记录每个segment中删除的数据并从segment粒度的top-k结果中去除已被标记删除的数据。Manu也支持批量向量查询，当之前的批查询请求结果尚未返回时，查询节点在cache中对当前批查询请求进行归类，将对相同集合，使用相同相似性函数的查询请求组织为一个批次，提高处理效率。

查询节点获取数据的渠道有三个：WAL、索引文件、binlog。对于growing segment中的数据，查询节点订阅WAL并以扫描的方式进行搜索。大segment有利于已经创建索引的数据查询，但是growing segment中的数据查询代价高。为了实现权衡，Manu将segment内部又划分为多个slices（默认包含1w个向量）。新数据被顺序插入到slice中，slice满了之后将构建轻量化索引（如IVF-FLAT）。当segment写满，构建好索引并存储到对象存储中后，索引节点被通知将索引加载到内存替换slice的临时索引。当查询节点间的segment分布因为系统节点scale、负载均衡、查询节点故障重启等发生改变后，查询节点需要访问binlog。如果查询节点故障，其负责的segment和对应的索引将被加载到其他索引节点。

Future Directions

Cloud Native and Adaptive

Manu将系统解耦为存储、协调器、工作器。存储可以使用事务型KV管理元数据，消息队列管理log、对象KV存储实际数据。协调器使用标准的一主二备方案实现高可用。对于工作器，Manu将向量搜索、日志存档、索引构建进行解耦，实现组件粒度的弹性伸缩。

Good Usability

多种SDK API+Attu可视化界面。

Time Travel

Manu允许用户指定目标物理时间并进行数据库回滚，具体通过checkpoint和log delay机制实现。Manu记录每个segment和其上的progress最新时间L，并周期性的为collection的segment map设置checkpoints，保存collection内部所有segments的路由map信息。为了回滚到位于时间T时刻的数据库，Manu读取在T之前的最新检查点，读取segment映射表中所有的segments并从segment对应的process重放每个segment的WAL日志。Manu通过检查点日志重放机制无需完整保存每个检查点的完整collection，并且没有数据变化的segment可以在多个checkpoints中共享。

Hardware Optimizations

Manu针对CPU和GPU的优化参考Milvus paper。SSD比Dram便宜100x且带宽比HDD高10x。Manu允许在配置较低的查询节点中，将有限Dram存放不下的大型向量collection存放在SSD中。Manu将向量组织成大小略小于4kb的桶（SSD读写以4kb为单位）。具体来说，Manu通过层次k-means聚类方法控制每个桶内的类族大小。这些桶在SSD中按照4kb对齐方式存储，并且每个桶对应的k-means聚类中心向量的索引保存在内存中。