Milvus：一个专用向量数据管理系统

原文: Milvus: A Purpose-Built Vector Data Management System 会议: SIGMOD ‘21, 2021年6月20–25日，中国（线上）作者: 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 机构: Zilliz & 普渡大学 DOI: https://doi.org/10.1145/3448016.3457550 开源: https://github.com/milvus-io/milvus

摘要

近年来，在数据科学和AI应用中，管理高维向量数据的需求日益迫切。这一趋势由两个因素推动：非结构化数据的激增，以及机器学习（ML）模型通常将非结构化数据转化为特征向量进行数据分析（如产品推荐）。现有的向量数据管理系统和算法存在两个局限：（1）处理大规模和动态向量数据时存在严重的性能问题；（2）提供的功能有限，无法满足多样化应用的需求。

本文介绍了 Milvus，一个专用数据管理系统，用于高效管理大规模向量数据。Milvus 支持易用的应用接口（包括SDK和RESTful API）；针对包含现代CPU和GPU的异构计算平台进行了优化；支持超越简单向量相似性搜索的高级查询处理；通过快速更新处理动态数据，同时保证高效的查询处理；在多个节点间分布数据以实现可扩展性和可用性。

我们首先描述了 Milvus 的设计和实现，然后展示了 Milvus 支持的实际应用场景。具体来说，我们在 Milvus 之上构建了10个应用（包括图像/视频搜索、化学结构分析、COVID-19数据集搜索、个性化推荐、生物多因子认证、智能问答等）。最后，我们对 Milvus 进行了广泛的实验评估，与两个开源系统（Vearch 和 Microsoft SPTAG）及三个商业系统进行比较。实验表明，Milvus 比竞争对手快最多两个数量级，同时提供更多功能。Milvus 目前已被全球数百家组织部署使用，并被 LF AI & Data Foundation 认可为孵化阶段项目。

关键词: 向量数据库；高维相似性搜索；异构计算；数据科学；机器学习

1 引言

在 Zilliz，我们经历了来自各类客户日益增长的需求：在许多数据科学和AI应用中管理大规模高维向量数据（维度从几十到上千）。这主要源于两个趋势。第一个趋势是非结构化数据（如图像、视频、文本、医疗数据和住房数据）由于智能手机、IoT设备和社交媒体应用的普及而爆发式增长。根据IDC的数据，到2025年80%的数据将是非结构化的。第二个趋势是机器学习的快速发展，可以有效将非结构化数据转化为学习到的特征向量进行数据分析。特别是，推荐系统中一种最近流行的方法叫做向量嵌入（vector embedding），将一个项目转化为特征向量（如 item2vec、word2vec、doc2vec、graph2vec），通过查找相似向量来提供推荐。例如，YouTube 将视频嵌入为向量；Airbnb 用向量对房屋建模；生物科学家用向量描述药物化合物的分子结构信息。此外，图像和文本也自然地由向量表示。

这些应用对设计可扩展的向量数据管理系统提出了独特的需求和挑战，包括：

需要支持大规模向量数据上的快速查询处理和动态数据（如插入和删除）的高效处理。 例如，YouTube 每分钟上传500小时的用户生成视频，同时提供实时推荐。
需要提供超越简单向量相似性搜索的高级查询处理，如属性过滤和多向量查询处理。属性过滤是仅搜索满足给定过滤条件的向量，在电子商务应用中很有用（例如找到与给定图像向量相似且价格低于100美元的T恤）。多向量查询处理针对每个对象由多个向量描述的场景（如在许多计算机视觉应用中，用面部向量和姿态向量来描述一个人）。

现有工作的局限

我们将现有工作分为两类：算法和系统。

算法层面：向量相似性搜索的算法工作（如 LSH、树形、图基和量化方法）及其开源实现库（如 Facebook Faiss 和 Microsoft SPTAG）存在以下局限：

它们是算法和库，而非一个完整的向量数据管理系统。它们不能很好地处理大量数据，因为假设所有数据和索引都存储在主存中，且不能跨越多台机器。
通常假设数据一旦进入系统就是静态的，无法在保证快速实时搜索的同时轻松处理动态数据。
不支持高级查询处理。
未针对包含CPU和GPU的异构计算架构进行优化。

系统层面：向量相似性搜索的系统工作（如 Alibaba AnalyticDB-V 和 Alibaba PASE）采用”一刀切”的方法，通过在关系数据库中添加”向量列”来扩展支持向量数据。然而，这些系统并非专门为管理向量数据而设计，未将向量视为一等公民：

传统的数据库组件（如优化器和存储引擎）阻碍了对向量的精细优化，例如查询优化器错过了最佳利用CPU和GPU处理向量数据的重要机会。
不支持高级查询处理（如多向量查询）。

另一个相关系统是 Vearch，专为向量搜索设计。但 Vearch 在大规模数据上效率不高。实验表明，Milvus 比 Vearch 快 6.4× 到 47.0×。此外，Vearch 不支持多向量查询处理。

Milvus 的定位

本文介绍的 Milvus 是一个专用数据管理系统，遵循”一尺码不适合所有人”的设计理念，专门为高维向量设计，与将关系数据库扩展为支持向量的方法形成对比。Milvus 具有以下特点：

提供多种应用接口（Python/Java/Go/C++ SDK 和 RESTful API）
针对包含现代CPU和GPU的异构计算架构高度优化
支持多种查询类型：向量相似性搜索（多种相似性函数）、属性过滤和多向量查询处理
提供不同类型的索引（量化索引和图索引），并开发了可扩展接口以轻松纳入新索引
通过基于LSM的结构管理动态向量数据，同时提供快照隔离的一致实时搜索
是一个分布式数据管理系统，跨多个节点部署以实现可扩展性和可用性

产品影响: Milvus 被全球数百家组织和机构在图像处理、计算机视觉、自然语言处理、语音识别、推荐系统和药物发现等领域采用。更重要的是，Milvus 于2020年1月被 LF AI & Data Foundation 接纳为孵化阶段项目。

论文贡献:

系统设计和实现（第2节和第5节）：Milvus 的整体设计和实现，一个专用向量数据管理系统。
异构计算（第3节）：针对包含现代CPU和GPU的异构硬件平台优化 Milvus。CPU方面提出缓存感知和SIMD感知优化；GPU方面设计了新的混合索引和新的调度策略。
高级查询处理（第4节）：支持属性过滤和多向量查询处理。设计了基于分区的属性过滤算法和两种多向量查询算法（向量融合和迭代合并）。
新应用（第6节）：在 Milvus 上构建了10个应用来展示其广泛适用性。

2 系统设计

2.1 查询处理

图1展示了 Milvus 的架构，包含三个主要组件：查询引擎、GPU引擎和存储引擎。查询引擎支持向量数据上的高效查询处理，通过减少缓存未命中和利用SIMD指令为现代CPU优化。GPU引擎是协处理引擎，通过大规模并行性加速性能，还支持多个GPU设备。存储引擎实现数据持久性，并采用基于LSM的结构进行动态数据管理，在各种文件系统（包括本地文件系统、Amazon S3和HDFS）上运行，内存中有缓冲池。

实体（Entity）

为了最好地捕捉多样化的数据科学和AI应用，Milvus 支持对向量数据和非向量数据进行查询处理。我们将术语实体定义如下：Milvus 中的每个实体由一个或多个向量描述，以及可选的一些数值属性（非向量数据）。例如，在图像搜索应用中，数值属性可以表示一个人的年龄和身高，此外还有可能的多个机器学习特征向量（如描述正面、侧面或姿态）。在当前版本的 Milvus 中，仅支持数值属性。未来计划支持带有倒排列表或位图索引的分类属性。

查询类型

Milvus 支持三种基本查询类型：

向量查询: 传统的向量相似性搜索，每个实体由单个向量描述。系统返回 k 个最相似的向量，k 是用户输入参数。
属性过滤: 每个实体由单个向量和一些属性指定。系统返回满足属性约束的 k 个最相似向量。例如，在推荐系统中，用户希望找到与给定查询图像相似且价格低于100美元的衣服。
多向量查询: 每个实体存储为多个向量。查询根据多个向量之间的聚合函数（如加权和）返回 top-k 相似实体。

相似性函数

Milvus 提供常用的相似性度量，包括欧几里得距离、内积、余弦相似度、汉明距离和杰卡德距离，允许应用以最有效的方式探索向量相似性。

应用接口

Milvus 提供易用的SDK接口，可直接在Python、Java、Go和C++等语言编写的应用中调用。还支持用于Web应用的RESTful API。

2.2 索引

索引对 Milvus 的查询处理至关重要。但一个具有挑战性的问题是决定支持哪些索引，因为向量相似性搜索已经开发了大量索引。最新基准测试表明，没有在所有场景中都胜出的方案，每种索引在性能、精度和空间开销方面都有权衡。

Milvus 主要支持两类索引：

量化索引: 包括 IVF_FLAT、IVF_SQ8 和 IVF_PQ
图索引: 包括 HNSW 和 RNSG

（Milvus 还支持树形索引，如 ANNOY。）

设计决策基于最新文献综述、工业系统（如 Alibaba PASE、Alibaba AnalyticDB-V、Jingdong Vearch）、开源库（如 Facebook Faiss）和客户输入。排除了基于LSH的方法，因为它们在十亿规模数据上的精度低于量化方法。

考虑到每年都有新索引出现，Milvus 的设计可以轻松纳入新索引，开发者只需实现几个预定义接口即可添加新索引。

2.3 动态数据管理

Milvus 通过采用 LSM-tree 的思想支持高效的插入和删除。新插入的实体首先存储在内存中作为 MemTable。当累积大小达到阈值或每隔一秒时，MemTable 变为不可变，然后刷盘成为一个新的段（segment）。较小的段被合并为较大的段以实现快速顺序访问。Milvus 实现了分层合并策略（也用于 Apache Lucene），旨在合并大约相等大小的段，直到达到可配置的大小限制（如1GB）。删除以相同的异地（out-of-place）方式支持，过时的向量在段合并期间被移除。更新通过删除和插入来支持。

默认情况下，Milvus 仅为大段（如 > 1GB）构建索引，但用户可以手动为任何大小的段构建索引。索引和数据都存储在同一段中。因此，段是搜索、调度和缓冲的基本单位。

Milvus 提供快照隔离，确保读写共享一致视图且互不干扰。快照隔离的详细信息在第5.2节。

2.4 存储管理

如第2.1节所述，每个实体表示为一个或多个向量及可选的一些属性。因此，每个实体可以被视为实体表中的一行。为了便于查询处理，Milvus 以列式方式物理存储实体表。

向量存储

对于单向量实体，Milvus 连续存储所有向量，不显式存储行ID。这样，所有向量按行ID排序。给定行ID，Milvus 可以直接访问对应的向量，因为每个向量长度相同。

对于多向量实体，Milvus 以列式方式存储不同实体的向量。例如，假设数据库中有三个实体 A、B、C，每个实体有两个向量 v1 和 v2，那么不同实体的所有 v1 存储在一起，所有 v2 存储在一起。即存储格式为 {A.v1, B.v1, C.v1, A.v2, B.v2, C.v2}。

属性存储

属性按列存储。每个属性列存储为 ⟨key, value⟩ 对数组，其中 key 是属性值，value 是行ID，按 key 排序。此外，我们按照 Snowflake 的方式构建跳指针（即最小/最大值），作为磁盘上数据页的索引。这允许在该列中进行高效的点查询和范围查询（如价格小于100美元）。

缓冲池

Milvus 假设大部分（如果不是全部）数据和索引常驻内存以获得高性能。否则，它依赖于基于LRU的缓冲管理器。缓存单位是段，即第2.3节中解释的基本搜索单位。

多存储

为了灵活性和可靠性，Milvus 支持多种文件系统，包括本地文件系统、Amazon S3 和 HDFS，用于底层数据存储。这也便于在云中部署 Milvus。

2.5 异构计算

Milvus 针对包含CPU和GPU的异构计算平台进行了高度优化。第3节详细说明。

2.6 分布式系统

Milvus 可以作为跨多个节点部署的分布式系统运行。它采用了现代分布式系统和云系统的设计实践，如存储计算分离、共享存储、读写分离和单写多读。第5.3节详细说明。

3 异构计算

本节介绍 Milvus 针对 CPU 和 GPU 异构计算平台的优化，以实现高性能。

如第2.2节所述，Milvus 主要支持量化索引（IVF_FLAT、IVF_SQ8、IVF_PQ）和图索引（HNSW、RNSG）。本节使用量化索引来说明优化，因为与图索引相比，它们消耗更少的内存、构建索引更快，同时实现不错的查询性能。注意，许多优化（如SIMD和GPU优化）也适用于图索引。

3.1 背景

在深入优化之前，我们先解释向量量化和量化索引。

向量量化的主要思想是应用量化器 z 将向量 v 映射到从码本 C 中选择的码字 z(v)。K-means 聚类算法通常用于构建码本 C，其中每个码字是质心，z(v) 是与 v 最近的质心。

量化索引（如 IVF_FLAT、IVF_SQ8、IVF_PQ）使用两个量化器：粗量化器和精细量化器。粗量化器应用 K-means 算法（如 K=16384）将向量聚类到 K 个桶中。精细量化器编码每个桶内的向量。不同索引使用不同的精细量化器：

IVF_FLAT: 使用原始向量表示
IVF_SQ8: 使用标量量化器将4字节浮点值压缩为1字节整数
IVF_PQ: 使用乘积量化，将每个向量分割为多个子向量，对每个子空间应用 K-means

量化索引上的查询处理（查询 q）分两步：

根据 q 与每个桶质心的距离，找到最近的 nprobe 个桶。参数 nprobe 控制精度和性能之间的权衡。
在每个 nprobe 相关桶内基于不同的精细量化器进行搜索。

3.2 CPU导向优化

3.2.1 缓存感知优化

量化索引上查询处理的根本问题是：给定 m 个查询 {q₁, q₂, …, qₘ} 和 n 个数据向量 {v₁, v₂, …, vₙ}，如何快速找到每个查询 qᵢ 的 top-k 相似向量？实践中，用户可以提交批量查询，因此 m ≥ 1。

Facebook Faiss 的原始实现：Faiss 使用 OpenMP 多线程并行处理查询。每个线程一次处理一个查询。线程在当前任务完成后释放（处理下一个查询）。每个任务将 qᵢ 与所有 n 个数据向量比较，维护一个 k 大小的堆存储结果。

Faiss 的上述方案有两个性能问题：

产生大量 CPU 缓存未命中，因为对于每个查询，整个数据需要流经 CPU 缓存且无法为下一个查询重用。因此，每个线程访问 m/t 次整个数据，其中 t 是线程总数。
当批量大小 m 较小时，无法充分利用多核并行性。

Milvus 的优化：Milvus 提出了两个想法来解决这些问题：

尽可能重用已访问的数据向量以最小化 CPU 缓存未命中。具体来说，优化减少 L3 缓存未命中，因为访问内存的代价高，且 L3 缓存大小（通常几十MB）远大于 L1/L2 缓存，留有更多优化空间。
使用细粒度并行性，将线程分配给数据向量而非查询向量，以最好地利用多核并行性，因为数据大小 n 通常远大于查询大小 m。

图3展示了整体设计。具体来说，设 t 为线程数，则每个线程 Tᵢ 被分配 b = n/t 个数据向量：{v_{(i-1)*b}, v_{(i-1)b+1}, …, v_{ib-1}}。Milvus 将 m 个查询划分为大小为 s 的查询块，使得每个查询块（及其关联的堆）始终能放入 L3 CPU 缓存。s 的计算公式为：

$s = \frac{L 3 缓存大小}{d \times sizeof(float) + t \times k \times ( sizeof(int64) + sizeof(float) )}$

其中 d 是维度，t 是线程数，k 是 top-k。

Milvus 一次计算每个查询块的 top-k 结果。每当每个线程将其分配的数据向量加载到 L3 缓存时，它们将与缓存中的整个查询块（s 个查询）进行比较。为了最小化同步开销，Milvus 为每个查询的每个线程分配一个堆。

这样，每个线程只访问 m/(s*t) 次整个数据，比 Faiss 的原始实现少 s 倍。实验表明，这提高了 1.5× 到 2.7× 的性能。

3.2.2 SIMD感知优化

现代 CPU 支持越来越宽的 SIMD 指令。Faiss 实现了 SIMD 感知算法来加速向量相似性搜索。Milvus 做了两个工程优化：

支持 AVX512：Faiss 不支持 AVX512（现在主流 CPU 已可用）。Milvus 扩展了相似性计算函数，使用 AVX512 指令（如 _mm512_add_ps、_mm512_mul_ps、_mm512_extractf32x8_ps）。Milvus 现在支持 SSE、AVX、AVX2 和 AVX512。
自动 SIMD 指令选择：Milvus 设计为在具有不同 SIMD 指令的各种 CPU 处理器上良好运行。挑战在于，给定单个软件二进制文件，如何使其在任何 CPU 处理器上自动调用合适的 SIMD 指令？Faiss 不支持这一点，用户需要在编译时手动指定 SIMD 标志。Milvus 重构了 Faiss 的代码库：提取依赖 SIMD 加速的公共函数，为每个函数实现四个版本（SSE、AVX、AVX2、AVX512），每个版本放在单独的源文件中，用相应的 SIMD 标志单独编译。运行时，Milvus 根据当前 CPU 标志自动选择合适的 SIMD 指令，通过 hooking 链接正确的函数指针。

3.3 GPU导向优化

GPU 以大规模并行性著称，Faiss 支持 GPU 进行向量数据查询处理。Milvus 在两个方面增强了 Faiss：

支持更大的 k 值

Faiss 的原始实现不支持 k > 1024 的 top-k 查询处理（受共享内存限制）。但许多应用（如视频监控和推荐系统）可能需要更大的 k 进行进一步验证或重排序。

Milvus 克服了这一限制，支持 k 最高达 16384。当 k > 1024 时，Milvus 以多轮方式执行查询来累积生成最终结果：

第一轮：与 Faiss 相同，获取 top-1024 结果
第二轮及之后：先检查上一轮最后一个结果的距离 dₗ（目前最大的距离），记录距离等于 dₗ 的向量ID，过滤掉距离小于 dₗ 或ID已记录的向量，从剩余数据中获取下一批1024个结果
新结果与之前轮次的部分结果合并
持续到收集到足够数量的结果

支持多GPU设备

Faiss 支持多个 GPU 设备，但需要在编译时声明所有 GPU 设备。这意味着如果代码在使用 c 个 GPU 的服务器上编译，则软件二进制文件只能在至少有 c 个 GPU 的服务器上运行。

Milvus 通过允许用户在运行时（而非编译时）选择任意数量的 GPU 设备来克服这一限制。底层机制是引入基于段的调度，将基于段的搜索任务分配给可用的 GPU 设备。每个段只能由单个 GPU 设备服务。这特别适合云环境中动态资源管理的场景，GPU 设备可以弹性添加或移除。

3.4 GPU与CPU协同设计

在这种模式下，GPU 内存不足以存储整个数据。Faiss 通过使用低占用压缩索引（IVF_SQ8）并按需从 CPU 内存向 GPU 内存移动数据来缓解问题。但存在两个局限：

PCIe 带宽未被充分利用：实验表明，测量的 I/O 带宽仅为 1~2 GB/s，而 PCIe 3.0 (16x) 支持高达 15.75 GB/s。
考虑到数据传输，在 GPU 上执行查询并不总是比 CPU 更有利。

Milvus 开发了名为 SQ8H 的新索引（‘H’ 代表 hybrid）来应对上述限制：

解决第一个局限：Faiss 按桶复制数据（从CPU到GPU），由于每个桶可能很小，导致 PCIe 带宽利用率低。自然的想法是同时复制多个桶。但多桶复制的缺点是处理删除，Faiss 使用简单的就地更新方法，因为每个桶是单独复制和存储的。幸运的是，Milvus 采用高效的基于LSM的异地方法处理删除和更新，因此可以尽可能复制多个桶来提高 I/O 利用率。

解决第二个局限：观察到 GPU 仅在查询批量大小足够大时才优于 CPU（考虑昂贵的数据移动）。更多查询使工作负载更计算密集，因为它们搜索相同的数据。因此：

如果批量大小大于阈值（如1000），Milvus 完全在 GPU 上执行所有查询，必要时加载桶（GPU内存不足时）
否则，以混合方式执行：步骤1（找 nprobe 个相关桶）在 GPU 上执行，步骤2（扫描每个相关桶）在 CPU 上执行。因为步骤1的计算-I/O比远高于步骤2——所有查询与相同的 K 个质心比较来找最近的桶，且 K 个质心足够小可以常驻 GPU 内存；而步骤2的数据访问更分散。

SQ8H 算法：

输入: nq 为批量大小
1: if nq ≥ threshold then
2:     在 GPU 上完全运行所有查询（动态加载多个桶到 GPU 内存）
3: else
4:     在 GPU 上执行 SQ8 的步骤1：找 nprobe 个桶
5:     在 CPU 上执行 SQ8 的步骤2：扫描每个相关桶
6: end if

4 高级查询处理

4.1 属性过滤

如第2.1节所述，属性过滤是一种混合查询类型，涉及向量数据和非向量数据。它仅搜索满足属性约束的向量，对许多应用至关重要（如找到大小在特定范围内的相似房屋）。

假设每个实体与单个向量和单个属性关联（扩展到多个属性是直接的）。每个查询涉及两个条件 Cₐ 和 Cᵥ，其中 Cₐ 指定属性约束，Cᵥ 是返回 top-k 相似向量的常规向量查询约束。Cₐ 表示为 a >= p₁ && a ⇐ p₂ 的形式。

Milvus 实现了多种策略，并提出了一种基于分区的方法（策略E），比策略D（最先进方案）快最多 13.7×。

策略A：属性优先-向量全扫描

仅使用属性约束 Cₐ 通过索引搜索获取相关实体。之后对结果集中的所有实体进行全扫描，与查询向量比较产生最终 top-k 结果。简单但适用于 Cₐ 高度选择性的情况。有趣的是，此策略产生精确结果。

策略B：属性优先-向量搜索

与策略A的区别在于，获取相关实体后生成结果实体ID的位图。然后基于 Cᵥ 进行正常向量查询处理，每遇到一个向量就检查位图。只有通过位图测试的向量才纳入最终 top-k 结果。适用于 Cₐ 或 Cᵥ 中等选择性的情况。

策略C：向量优先-属性全扫描

仅使用向量约束 Cᵥ 通过向量索引获取相关实体。然后对结果实体全扫描验证是否满足属性约束 Cₐ。为确保有 k 个最终结果，在向量查询处理中搜索 θ·k (θ > 1) 个结果。适用于向量约束 Cᵥ 高度选择性的情况。

策略D：基于代价

估计策略A、B、C的代价，选择代价最小的。从文献和实验看，基于代价的策略几乎在所有情况下都适用。

策略E：基于分区（Milvus的新方法）

主要思想是基于频繁搜索的属性对数据集进行分区，对每个分区应用基于代价的方法（策略D）。具体来说：

在哈希表中维护每个搜索属性的频率
给定属性过滤查询，仅搜索属性范围与查询范围重叠的分区
更重要的是，如果特定分区的范围被查询范围覆盖，则该策略不需要检查属性约束 (Cₐ)，只关注该分区中的向量查询处理 (Cᵥ)，因为该分区中的所有向量都满足属性约束

示例：假设有许多涉及属性”price”的查询，策略E将数据集分为五个分区：P0 [1~~100]、P1 [101~~200]、P2 [201~~300]、P3 [301~~400]、P4 [401~~500]。如果查询的属性约束 Cₐ 是 [50~~250]，则只需要搜索 P0、P1 和 P2（因为它们的范围与查询范围重叠）。搜索 P1 时不需要检查属性约束，因为其范围完全被查询范围覆盖。

分区数 ρ 的选择：

ρ 太小：每个分区包含太多向量，难以剪枝不相关分区
ρ 太大：每个分区的向量太少，向量索引退化为线性搜索
推荐每个分区约包含100万个向量。例如，十亿规模数据集约1000个分区
目前分区是离线创建的，未来计划使用机器学习和统计方法动态分区

4.2 多向量查询

在许多应用中，每个实体由多个向量描述以提高准确性。例如，智能视频监控应用使用不同向量描述摄像头捕捉到的人的正面、侧面和姿态。食谱搜索应用使用多个向量表示每份食谱的文本描述和关联图像。

形式化地，每个实体包含 μ 个向量 v₀, v₁, …, v_{μ-1}。多向量查询根据每个单独向量 vᵢ 的相似性函数 f（如内积）上的聚合评分函数 g 找到 top-k 实体。假设聚合函数 g 是单调的（即 g 对每个 f(X.vᵢ, Y.vᵢ) 非递减）。实践中常用的聚合函数都是单调的（如加权和、平均/中位数、最小/最大值）。

朴素方案：对每个查询向量 q.vᵢ 在 Dᵢ 上发起单独的 top-k 查询产生候选集，进一步计算获得最终 top-k 结果。但这种方法会遗漏许多真实结果，导致极低的召回率（如0.1）。

Milvus 开发了两种新方法：向量融合和迭代合并。

向量融合（Vector Fusion）

假设相似性函数是内积（之后解释如何扩展到其他相似性函数）：

存储时：将每个实体 e 的 μ 个向量存储为拼接向量 v = [e.v₀, e.v₁, …, e.v_{μ-1}]
查询时：将聚合函数 g 应用于查询 q 的 μ 个向量，产生聚合查询向量。例如，如果聚合函数是加权和，权重为 wᵢ，则聚合查询向量为 [w₀×q.v₀, w₁×q.v₁, …, w_{μ-1}×q.v_{μ-1}]
然后用聚合查询向量在数据集中的拼接向量上搜索获得最终结果

正确性证明是直接的，因为内积的相似性函数是可分解的（decomposable）。

向量融合方法简单高效，因为只需调用一次向量查询处理。但它需要可分解的相似性函数（如内积）。当底层数据归一化时，许多相似性函数（如余弦相似度和欧几里得距离）可以等价转换为内积。

迭代合并（Iterative Merging）

如果底层数据未归一化且相似性函数不可分解（如欧几里得距离），则向量融合方法不适用。迭代合并算法构建在 Fagin 的著名 NRA 算法之上。

初始尝试的问题：直接使用 NRA 算法效率低下，因为 NRA 频繁调用 getNext() 获取 q.vᵢ 的下一个结果。但现有向量索引技术不支持高效的 getNext()，获取下一个结果需要完整搜索。NRA 的另一个缺点是维护堆的开销显著。

迭代合并的两个优化：

不依赖 getNext()，而是调用 VectorQuery(q.vᵢ, Dᵢ, k’)，使用自适应的 k’ 获取 top-k’ 查询结果。无需像 NRA 那样为每次访问调用向量查询处理，也消除了 NRA 中昂贵的堆维护开销。
引入最大访问步数的上限，因为 Milvus 中的查询结果是近似的。

算法：

1: k' ← k
2: while k' < threshold do
3:     foreach i do
4:         Rᵢ ← VectorQuery(q.vᵢ, Dᵢ, k')  // 对每个 q.vᵢ 在 Dᵢ 上运行 top-k' 查询
5:     if k results are fully determined with NRA on all Rᵢ then
6:         return top-k results
7:     else
8:         k' ← k' × 2
9: return top-k results from ∪ᵢ Rᵢ

如果至少有 k 个结果可以被完全确定（即 NRA 可以安全停止），则算法终止。否则将 k’ 加倍并迭代，直到 k’ 达到预定义阈值。

与向量融合方法相比，迭代合并方法对数据和相似性函数没有假设，适用范围更广。但当相似性函数可分解时，性能不如向量融合。

5 系统实现

5.1 异步处理

Milvus 设计为通过异步处理最小化前台处理以提高吞吐量。当 Milvus 接收大量写请求时，首先将操作物化（类似于数据库日志）到磁盘，然后向用户确认。后台线程消费这些操作。因此，用户可能不会立即看到插入的数据。为防止这种情况，Milvus 提供 flush() API，阻塞所有传入请求直到系统完成处理所有待处理操作。此外，Milvus 异步构建索引。

5.2 快照隔离

Milvus 提供快照隔离以确保读写看到一致视图。每个查询仅处理查询开始时的快照。后续对系统的更新创建新快照，不干扰正在进行的查询。

Milvus 按照 LSM 风格管理动态数据。所有新数据首先插入内存，然后刷盘为不可变段。每个段有多个版本，每当该段中的数据或索引发生变化（如刷盘、合并或构建索引）时生成新版本。任何时刻所有最新段形成一个快照。每个段可以被一个或多个快照引用。

示例：系统启动时没有段。假设在 t₁ 有一些插入刷盘形成段1。之后在 t₂ 生成段2。现在系统中有两个快照：快照1指向段1，快照2指向段1和段2。段1被两个快照引用。t₂ 之前的所有查询在快照1上工作，t₂ 之后的所有查询在快照2上工作。后台线程垃圾回收未被引用的过时段。

注意，快照隔离应用于 LSM 结构中的内部数据重组。这样，所有（内部）读操作不会被写操作阻塞。

5.3 分布式系统

Milvus 是一个分布式系统，支持跨多个节点的数据管理，以实现可扩展性和可用性。

图5展示了整体架构，包含三层：

存储层：基于 Amazon S3（与 Snowflake 相同），因为 S3 高度可用
计算层：处理用户请求（如数据插入和查询），具有本地内存和SSD缓存数据以最小化对 S3 的频繁访问
协调层：维护系统元数据（如分片和负载均衡信息），三个实例通过 Zookeeper 管理实现高可用

计算层是无状态的以实现弹性。它包括单个写入实例和多个读取实例，因为 Milvus 是读密集型的，目前单个写入器足以满足客户需求。写入实例处理数据插入、删除和更新。读取实例处理用户查询。数据在读取实例之间使用一致性哈希进行分片。分片信息存储在协调层。没有跨分片事务，因为同一请求中没有混合的读写操作。该设计实现了近乎线性的可扩展性。

所有计算实例由 Kubernetes (K8s) 管理。当实例崩溃时，K8s 自动重启新实例替换旧实例。如果写入实例崩溃，Milvus 依靠 WAL（预写日志）保证原子性。由于实例是无状态的，崩溃不影响数据一致性。K8s 还可以在现有实例过载时弹性添加更多读取实例。

最小化计算和存储之间的网络开销，Milvus 采用两个优化：

计算层仅发送日志（而非实际数据）到存储层（与 Aurora 类似）。Milvus 用后台线程异步处理日志以提高性能。
每个计算实例有大量缓冲内存和SSD以减少对共享存储的访问。

6 应用

Milvus 上构建了10个应用，包括图像搜索、视频搜索、化学结构分析、COVID-19数据集搜索、个性化推荐、生物多因子认证、智能问答、图文检索、跨模态行人搜索和食谱-食物搜索。本节介绍其中两个。

6.1 图像搜索

图像搜索是向量搜索的知名应用，每张图像使用深度学习模型（如 VGG 和 ResNet）自然转换为向量。

两家科技公司——企查查和贝壳找房——目前使用 Milvus 进行大规模图像搜索。企查查是中国领先的企业信息存储和搜索网站（超过1亿家公司），Milvus 支持企查查查找相似商标。贝壳找房是中国最大的在线房地产交易平台之一，Milvus 支持贝壳找房查找相似的房屋和公寓（如户型图）。

6.2 化学结构分析

化学结构分析是一个依赖向量搜索的新兴应用。最近的研究表明，理解化学物质结构的一种新高效范式是将其编码为高维向量，使用向量相似性搜索（如 Tanimoto 距离）来查找相似结构。

Milvus 现在被 药明康德（Apptech/WuXi AppTec） 采用，这是一家开发新药和医疗器械的大型制药公司。Milvus 将化学结构分析的时间从数小时显著缩短到不到一分钟。

7 实验

7.1 实验设置

实验平台：在阿里云上进行所有实验，使用不同类型的计算实例（最多12个节点）。默认使用 CPU 实例 ecs.g6e.4xlarge（Xeon Platinum 8269 Cascade 2.5GHz，16 vCPU，35.75MB L3缓存，AVX512，64GB内存，NAS弹性存储）。GPU 实例为 ecs.gn6ic-16g1.4xlarge（NVIDIA Tesla T4，64KB私有内存，512KB本地内存，16GB全局内存，PCIe 3.0 16x接口）。

数据集：使用两个公共数据集——SIFT1B（10亿128维SIFT向量，512GB）和 Deep1B（10亿96维图像向量，384GB）。

竞争对手：JINGDONG Vearch (v3.2.0)、Microsoft SPTAG，以及三个商业系统（匿名为 System A、B、C）。

评估指标：召回率（recall）和吞吐量（10,000个随机查询）。

7.2 与先前系统的比较

使用每个数据集的前1000万个向量进行评估。

IVF 索引上的结果：

Milvus（即使CPU版本）在保持相似召回率的同时，显著优于现有系统最多两个数量级
Milvus 比 Vearch 快 6.4× 到 27.0×
比 System B 快 153.7×（System B 在4个节点上运行）
比 System C 快 4.7× 到 11.5×（System C 在2个节点上运行）
比 SPTAG 快 1.3× 到 2.1×（SPTAG 不能达到很高的召回率如0.99，且SPTAG内存占用是Milvus的14倍）
GPU版本的 Milvus 更快

HNSW 索引上的结果：

Milvus 比 Vearch 快 15.1× 到 60.4×
比 System A 快 7.3× 到 73.9×
比 System C 快 8.0× 到 17.1×

性能优势来源：

引入细粒度并行性，支持查询间和查询内并行性以最好地利用多核CPU
开发缓存感知和SIMD感知优化，减少CPU缓存未命中，利用宽SIMD指令
优化GPU和CPU之间的混合执行

7.3 可扩展性

使用 SIFT1B 数据集上的 IVF_FLAT 索引评估可扩展性。

数据规模可扩展性：在单节点 ecs.re6.26xlarge（104 vCPU，1.5TB内存）上，随着数据增加，吞吐量成比例下降。

分布式可扩展性：数据在节点间分片。随着节点数增加，吞吐量线性增加，实现近乎线性的可扩展性。

7.4 优化评估

缓存感知设计：在两种不同 L3 缓存大小的 CPU 上测试（12MB 和 35.75MB）。批量大小1000，数据规模从1000到1000万向量。缓存感知设计实现了高达 2.7×（12MB缓存）和 1.5×（35.75MB缓存）的性能提升。

SIMD感知优化：比较 AVX2 和 AVX512 在 Xeon CPU 上的性能。AVX512 大约比 AVX2 快 1.5×。

混合算法 SQ8H：在 SIFT1B 上评估（数据无法放入GPU内存）。SQ8H 在所有情况下都快于纯 CPU 和纯 GPU 上运行 SQ8。因为 SQ8H 仅将质心存储在 GPU 内存中执行第一步，让 CPU 执行第二步，所以不需要动态传输数据段到 GPU 内存。

7.5 属性过滤评估

查询选择性定义为不满足属性约束 Cₐ 的实体百分比。选择性越高意味着更少的实体能通过 Cₐ。

使用 SIFT1B 的前1亿向量，为每个向量附加一个0到10000的随机属性值。

策略比较：

策略A：性能随选择性增加而提高
策略B：对选择性不敏感（瓶颈是向量相似性搜索）
策略C：比策略B慢（需要检查 θ 倍的向量）
策略D：优于A、B、C（基于代价选择最佳）
策略E（基于分区）：显著优于策略D，最多快 13.7×

与其他系统比较：Milvus 比 System A、B、C 和 Vearch 快 48.5× 到 41299.5×。

7.6 多向量查询处理评估

使用 Recipe1M 数据集（超过100万个烹饪食谱和食物图像），每个实体由两个向量描述：文本向量和图像向量。使用欧几里得距离和内积作为相似性度量。

欧几里得距离：

NRA-50 快但召回率仅0.1
NRA-2048 召回率略有提高（最高0.5），但性能低
迭代合并（k’=4096）比 NRA-2048 快 15×，召回率相似

内积：

向量融合比迭代合并快 3.4× 到 5.8×，因为只需发起一次 top-k 向量相似性搜索

8 相关工作

向量相似性搜索（又称高维最近邻搜索）是一个广泛研究的主题，包括近似搜索和精确搜索。本文聚焦于近似搜索以实现高性能。

近似搜索的先前工作可大致分为四类：LSH-based、树形、图基和量化。但这些工作都是关于索引的，而 Milvus 是一个完整的向量数据管理系统，包括索引、查询引擎、GPU引擎、存储引擎和分布式系统。Milvus 的可扩展索引框架可以轻松纳入这些索引及任何新索引。

工业级向量数据管理系统（如 Alibaba PASE 和 Alibaba AnalyticDB-V）并未特别针对向量优化，方法是扩展关系数据库支持向量，性能严重下降。专用向量系统如 Vearch 不适合十亿规模数据，且显著慢于 Milvus。

GPU向量搜索引擎：[72] 优化了 HNSW 对 GPU 的支持，但假设数据足够小可以放入 GPU 内存。Faiss 也支持 GPU，但在数据无法放入 GPU 内存时按需加载整个数据段，导致低性能。Milvus 开发了新的混合索引 SQ8H，结合了 GPU 和 CPU 的最佳优势，无需动态加载数据。

专业化数据引擎趋势：本文与”一尺码不适合所有人”的专业化数据引擎趋势相关，如专业化图引擎、IoT引擎、时间序列数据库和科学数据库。Milvus 是管理向量数据的专业化数据引擎。

9 结论

在本文中，我们分享了过去几年在 Zilliz 构建 Milvus 的经验。Milvus 已被数百家公司采用，目前是 LF AI & Data Foundation 的孵化阶段项目。

展望未来，我们计划利用 FPGA 加速 Milvus。我们已在 FPGA 上实现了 IVF_PQ 索引，初步结果令人鼓舞。另一个有趣但具有挑战性的方向是将 Milvus 架构为云原生数据管理系统，我们目前正在致力于此。

致谢

Milvus 是一个涉及 Zilliz 许多工程师的多年项目。特别感谢 Shiyu Chen、Qing Li、Yunmei Li、Chenglong Li、Zizhao Chen、Yan Wang 和 Yunying Zhang 的贡献。感谢 Haimeng Cai 和 Chris Warnock 的论文校对。最后，感谢 Walid G. Aref 和匿名审稿人的宝贵反馈。

参考文献

[1] Annoy: Approximate Nearest Neighbors Oh Yeah. 2020. [2] ElasticSearch: Open Source, Distributed, RESTful Search Engine. 2020. [3] Facebook Faiss. 2020. [4] Vearch: A Distributed System for Embedding-based Retrieval. 2020. [5] Akbarinia et al. Best Position Algorithms for Top-k Queries. VLDB 2007. [6] André et al. Cache locality is not enough: High-Performance Nearest Neighbor Search with Product Quantization Fast Scan. PVLDB 2015. [7] Aumüller et al. ANNBenchmarks. CoRR 2018. [8] Babenko & Lempitsky. Efficient Indexing of Billion-Scale Datasets of Deep Descriptors. CVPR 2016. [9] Bajusz et al. Why Is Tanimoto Index An Appropriate Choice For Fingerprint-Based Similarity Calculations? J. Cheminformatics 2015. [10] Baltrusaitis et al. Multimodal Machine Learning: A Survey and Taxonomy. TPAMI 2019. [11] Barkan & Koenigstein. ITEM2VEC. MLSP 2016. [12] Chakrabarti et al. Interval-based Pruning for Top-k Processing over Compressed Lists. ICDE 2011. [13] Chen et al. The Rise of Deep Learning in Drug Discovery. Drug Discovery Today 2018. [14] Chen et al. SPTAG: A Library for Fast Approximate Nearest Neighbor Search. 2018. [15] Covington et al. Deep Neural Networks for YouTube Recommendations. RecSys 2016. [16] Dageville et al. The Snowflake Elastic Data Warehouse. SIGMOD 2016. [17] Dasgupta & Freund. Random Projection Trees and Low Dimensional Manifolds. STOC 2008. [18] Deutsch et al. Aggregation Support for Modern Graph Analytics in TigerGraph. SIGMOD 2020. [19] Fagin et al. Optimal Aggregation Algorithms for Middleware. PODS 2001. [20] Fu et al. Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph. PVLDB 2019. [21] Garcia-Arellano et al. Db2 Event Store: A Purpose-Built IoT Database Engine. PVLDB 2020. [22] Ge et al. Optimized Product Quantization. TPAMI 2014. [23] Gionis et al. Similarity Search in High Dimensions via Hashing. VLDB 1999. [24] Gong et al. iDEC: Indexable Distance Estimating Codes. PVLDB 2020. [25] Grbovic & Cheng. Real-time Personalization using Embeddings for Search Ranking at Airbnb. KDD 2018. [26] Grohe. Word2vec, Node2vec, Graph2vec, X2vec. PODS 2020. [27] Guo et al. Accelerating Large-Scale Inference with Anisotropic Vector Quantization. ICML 2020. [28] He et al. Deep Residual Learning for Image Recognition. CVPR 2016. [29] Hsu & Taksa. Comparing Rank and Score Combination Methods for Data Fusion in Information Retrieval. IR 2005. [30] Huang et al. FiBiNET. RecSys 2019. [31] Ilyas et al. A Survey of Top-k Query Processing Techniques. CSUR 2008. [32] Jafari et al. mmLSH. CoRR 2020. [33] Jégou et al. Product Quantization for Nearest Neighbor Search. TPAMI 2011. [34] Jégou et al. Searching in One Billion Vectors. ICASSP 2011. [35] Johnson et al. Billion-scale similarity search with GPUs. IEEE Trans. Big Data 2019. [36] King. 80 Percent of Your Data Will Be Unstructured in Five Years. 2019. [37] Le & Mikolov. Distributed Representations of Sentences and Documents. ICML 2014. [38] Li et al. FEXIPRO: Fast and Exact Inner Product Retrieval in Recommender Systems. SIGMOD 2017. [39] Li et al. The Design and Implementation of a Real Time Visual Search System on JD E-Commerce Platform. Middleware 2018. [40] Li et al. I/O Efficient Approximate Nearest Neighbour Search based on Learned Functions. ICDE 2020. [41] Li et al. Approximate Nearest Neighbor Search on High Dimensional Data. TKDE 2020. [42] Li et al. Index-Based, High-Dimensional, Cosine Threshold Querying. ICDT 2019. [43] Lin & Zhao. A Comparative Study on Hierarchical Navigable Small World Graphs. CoRR 2019. [44] Liu et al. I-LSH: I/O Efficient c-Approximate Nearest Neighbor Search. ICDE 2019. [45] Lu & Kudo. R2LSH. ICDE 2020. [46] Lu et al. VHP: Approximate Nearest Neighbor Search via Virtual Hypersphere Partitioning. PVLDB 2020. [47] Luo & Carey. LSM-based Storage Techniques: A Survey. VLDB Journal 2020. [48] Lv et al. Intelligent Probing for Locality Sensitive Hashing. PVLDB 2017. [49] Malkov & Yashunin. Efficient and Robust Approximate Nearest Neighbor Search Using HNSW. TPAMI 2020. [50] Marín et al. Recipe1M. CoRR 2018. [51] Mater & Coote. Deep Learning in Chemistry. JCIM 2019. [52] Mikolov et al. Efficient Estimation of Word Representations in Vector Space. ICLR 2013. [53] Mikolov et al. Distributed Representations of Words and Phrases and their Compositionality. NeurIPS 2013. [54] Muja & Lowe. Scalable Nearest Neighbor Algorithms for High Dimensional Data. TPAMI 2014. [55] Pelkonen et al. Gorilla: A Fast, Scalable, in-Memory Time Series Database. PVLDB 2015. [56] Salvador et al. Learning Cross-modal Embeddings for Cooking Recipes and Food Images. CVPR 2017. [57] Silpa-Anan & Hartley. Optimised KD-trees for Fast Image Descriptor Matching. CVPR 2008. [58] Simonyan & Zisserman. Very Deep Convolutional Networks for Large-Scale Image Recognition. ICLR 2015. [59] Stonebraker et al. The Future of Scientific Data Bases. ICDE 2012. [60] Stonebraker & Çetintemel. “One Size Fits All”: An Idea Whose Time Has Come and Gone. ICDE 2005. [61] Subramanya et al. Rand-NSG: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node. NeurIPS 2019. [62] Tziavelis et al. Optimal Join Algorithms Meet Top-k. SIGMOD 2020. [63] Verbitski et al. Amazon Aurora: Design Considerations for High Throughput Cloud-Native Relational Databases. SIGMOD 2017. [64] Wang et al. An Experimental Study of Bitmap Compression vs. Inverted List Compression. SIGMOD 2017. [65] Wei et al. AnalyticDB-V: A Hybrid Analytical Engine Towards Query Fusion for Structured and Unstructured Data. PVLDB 2020. [66] Willett. The Calculation of Molecular Structural Similarity. Molecular Informatics 2014. [67] Wojcicki. YouTube at 15: My Personal Journey and the Road Ahead. 2020. [68] Yang et al. PASE: PostgreSQL Ultra-High-Dimensional Approximate Nearest Neighbor Search Extension. SIGMOD 2020. [69] Ying et al. Graph Convolutional Neural Networks for Web-Scale Recommender Systems. KDD 2018. [70] Zhang et al. Query Specific Rank Fusion for Image Retrieval. TPAMI 2015. [71] Zhang & Yu. Person Re-Identification by Multi-Camera Networks for IoT in Smart Cities. IEEE Access 2018. [72] Zhao et al. SONG: Approximate Nearest Neighbor Search on GPU. ICDE 2020. [73] Zheng et al. PM-LSH: A Fast and Accurate LSH Framework for High-Dimensional Approximate NN Search. PVLDB 2020.

风车车知识库

探索

Milvus-SIGMOD21-向量数据管理系统

目录