介绍Cardinal：向量搜索性能最强的引擎

在数据库中，“性能”是一个关键指标，特别是在向量数据库中。它在有限资源内有效处理大量用户请求中起着至关重要的作用。虽然在某些情况下访问延迟可能不是问题，但对于向量数据库来说，性能仍然至关重要。

依赖于近似最近邻搜索（ANNS）的向量搜索可能会为了提高性能而牺牲一定程度的准确性。反过来，提高的性能又允许更高的精度。

在一致的查询延迟下保持出色的性能，可以利用相同的资源实现更高的吞吐量，容纳更多的用户群体。

此外，提高的性能意味着支持相同使用场景所需的计算资源更少。

向量数据库本质上是计算密集型的，资源使用量的很大一部分——通常超过80%——专门用于向量距离计算。因此，负责处理向量搜索任务的向量搜索引擎成为决定向量数据库整体性能的关键因素。

Zilliz始终将提高向量数据库性能作为优先事项。开源的Milvus和完全托管的Zilliz Cloud与类似产品相比展现出卓越的性能。Milvus向量搜索引擎Knowhere在实现这一成功中发挥了重要作用，为新搜索引擎奠定了基础。

Zilliz Cloud最新版本的核心是Cardinal，这是我们构建的一个新的向量搜索引擎。这个搜索引擎已经证明了与之前的版本相比性能提高了三倍，提供的搜索性能（QPS）达到了Milvus的十倍。

我们通过开源向量数据库基准测试工具评估了最新Zilliz Cloud的性能，并将其性能与Milvus和旧引擎的Zilliz Cloud进行了比较。评估结果如下所示。

什么是Cardinal？

Cardinal是一个专有的多线程现代C++模板基础向量搜索引擎，实现了最实用和广泛使用的ANNS方法。Cardinal从头开始设计和编写，以有效利用可用的计算资源。

Cardinal能够：

- 执行暴力搜索，

- 创建和修改ANNS索引，

- 执行索引Top-K和索引范围搜索，

- 处理各种输入数据格式，包括FP32、FP16和BF16，

- 处理内存中数据或内存映射数据，

- 根据用户提供的标准在搜索期间过滤结果。

Cardinal包括：

- 实现ANN方法，允许轻松配置各种内部参数。然而，默认操作点始终调整以最大化搜索速度（QPS，每秒查询数）同时保持合理的准确性（召回率）。

- 支持ANNS方法的各种算法的高效实现。例如，提供样本过滤功能的算法。

- 用于搜索或构建期间使用的最计算密集型操作的低级专门优化内核。支持多个硬件平台。除了计算各种度量的距离内核外，Cardinal还包含融合内核和数据预处理内核。

- 支持设施，如异步操作、内存映射I/O能力、缓存、内存分配器、日志记录等。

Knowhere与Cardinal

Knowhere库是开源Milvus的内部核心，负责向量搜索。Knowhere基于行业标准的开源库的修补版本，如Faiss、DiskANN和hnswlib。

让我们提供Knowhere和Cardinal之间的比较：

两者都是生产就绪的，并提供Milvus和Zilliz Cloud所需的所有可扩展能力。

Knowhere旨在实现实验和灵活性。Cardinal的范围更狭窄，优先考虑为提高速度和性能而增强现有功能，而不是引入广泛的新功能。

由于Knowhere是开源的，并且可能部署在许多不同的环境，它运行在所有主机类型上。Cardinal为Zilliz Cloud主机环境进行了优化。

Knowhere依赖于知名的开源软件库和实现（如Faiss、DiskANN和hnswlib）。Cardinal包含非平凡的修改和优化。

Cardinal为什么这么快

Cardinal实现了各种算法相关的、工程的和低级的优化。Cardinal引入了AUTOINDEX机制，它自动选择最佳搜索策略和索引数据集。这消除了手动调整的需要，节省了开发人员的时间和努力。

让我们深入了解细节。

算法优化

这种形式的优化显著提高了搜索过程的准确性和有效性，这是一个涉及各种算法协同工作的多方面管道。这个管道中的许多算法可以被改进以提高整体性能。Cardinal中算法优化的显著候选者包括：

- 搜索算法，包括基于IVF和基于图的方法，

- 设计用于帮助搜索保持所需召回率的算法，无论过滤样本的百分比如何，

- 最佳优先搜索算法的高级迭代，

- 针对优先队列数据结构的定制算法。

可参数化的算法提供了权衡的灵活性，例如平衡性能与RAM使用。因此，Cardinal的算法优化还涉及在参数空间内选择最优操作点。

工程优化

虽然算法最初是考虑到抽象图灵机而设计的，但现实世界的实现面临着诸如网络延迟、云服务提供商对IOPS的限制以及机器RAM的限制等挑战，RAM是一种宝贵但有限的资源。

工程优化确保Cardinal的向量搜索管道保持实用，并与计算、RAM和其他资源限制保持一致。在Cardinal的开发中，我们结合了标准实践和创新技术。这种方法使得C++编译器能够生成计算最优的编译代码，同时保持干净、可基准测试和易于扩展的源代码，这有助于快速添加新功能。

以下是在Cardinal中实施的工程实践的一些示例，展示了特定的优化：

- 专门的内存分配器和内存池，

- 正确实现的多线程代码，

- 组件的层次结构，促进将元素组合成各种搜索管道，

- 针对特定、关键用例的代码定制。

低级优化

大部分搜索时间都花在称为内核的相对较小的代码片段上。最简单的例子是计算两个向量之间L2距离的内核。

Cardinal包含了许多不同目的的计算内核，每个内核都为特定的硬件平台和用例专门编写和优化。

Cardinal支持x86和ARM硬件平台，但其他平台可以轻松添加。

对于x86平台，Cardinal内核使用AVX-512的F、CD、VL、BW、DQ、VPOPCNTDQ、VBMI、VBMI2、VNNI、BF16和FP16扩展。此外，我们正在探索使用新的AMX指令集。

对于ARM平台，Cardinal内核适用于NEON和SVE指令集。

我们确保Cardinal获得计算内核的最优化代码。我们不仅仅依赖现代C++编译器来完成这项工作：

- 我们使用专门的工具，如Linux perf，来分析热点和CPU指标，

- 我们使用机器代码分析工具，如GodBolt Compiler Explorer和uiCA，确保最佳地利用硬件“资源”，如RAM/缓存访问次数、使用的CPU指令、寄存器、计算端口。

我们采用迭代方法，将设计、基准测试、分析和汇编代码分析阶段交错进行。

一个正确优化的计算内核可能会比一个简单但未优化的内核提供2倍或3倍的速度提升。这可能进一步转化为2倍的QPS值提高或在云主机机器上降低20%的内存需求。

AutoIndex：搜索策略选择

向量搜索是一个复杂的过程，涉及许多独立组件，包括量化、索引构建、搜索算法、数据结构等。每个组件都有多种可调参数。它们共同形成了向量搜索策略的广泛范围，不同的数据集和场景需要不同的搜索策略。

为了更好地挖掘性能提升的潜力，Cardinal除了在每个组件中支持多种策略外，还实现了一套基于AI的动态策略选择机制，称为AUTOINDEX。它根据给定数据集的分布、提供的查询和硬件配置，自适应地选择最合适的策略。这有助于我们在满足用户对搜索质量的需求的同时实现最佳性能。

Cardinal基准测试

我们已经采用了ANN-benchmarks来支持Cardinal在我们的测试环境中。ANN-benchmarks是评估近似最近邻搜索（ANNS）实现的标准基准测试工具，它在几个使用不同距离度量的标准数据集上运行。每个性能评估都是在限制为单线程使用的docker容器内进行的。指标基于几次评估迭代，这些迭代使用了许多单个查询请求。每个评估框架的结果都汇总到一个召回率与QPS（每秒查询数）的帕累托前沿。

所有测试都是在与基线ann-benchmarks（截至2024年1月）相同的机器上进行的，即Amazon EC2 r6i.16xlarge机器，配置如下：

- CPU：Intel(R) Xeon(R) Platinum 8375C CPU @ 2.90GHz

- CPU核心数：32

- 超线程被禁用

- 内存：512 GB

- 操作系统：Ubuntu 22.04.3 LTS，Linux内核6.2.0-1017-aws

- 未启用大页支持

- 测试使用`--parallelism=31`选项运行

- Cardinal使用clang 17.0.6编译器编译

下面呈现的基准测试结果仅针对Cardinal引擎，不包括Zilliz Cloud提供的额外非索引优化。

注意：结果包括Zilliz Cloud特定优化的测试结果在文章开头已经提供。

以下图表是通过获取ANN-benchmark GitHub页面上呈现结果的图表图像，并精确地在其上添加了一个额外的Cardinal曲线。

对于所有提供的基准测试，Cardinal展示了非常有竞争力的结果。并且还有进一步改进的空间。

下一步是什么？

未来无疑会给我们带来新的挑战。不同的需求，不同的瓶颈，更大的数据集。我们一直在努力使Cardinal变得更好。

道路已经照亮。路径已经清晰。我们只需要跟随它的力量 :)