【译】在 Milvus 向量数据库中进行相似性搜索的原因是什么？

原文链接：https://dzone.com/articles/what-powers-similarity-search-in-milvus-vector-dat
作者：Yudong Cai

作为核心向量执行引擎，Knowhere 之于 Milvus 就像引擎之于跑车。这篇文章介绍了 Knowhere 是什么，它与 Faiss 有何不同，以及 Knowhere 的代码是如何结构化的。

Knowhere 的概念
狭义地讲，Knowhere 是访问系统上层服务和系统下层 Faiss、Hnswlib 和 Annoy 等向量相似度搜索库的操作接口。此外，Knowhere 还负责异构计算。更具体地说，Knowhere 控制哪些硬件（例如 CPU 或 GPU）来执行索引构建和搜索请求。这就是 Knowhere 得名的原因——知道在哪里执行操作。未来版本将支持更多类型的硬件，包括 DPU 和 TPU。

从更广泛的意义上说，Knowhere 还整合了 Faiss 等其他第三方索引库。因此，作为一个整体，Knowhere 被公认为 Milvus 矢量数据库中的核心矢量计算引擎。

从Knowhere的概念可以看出，它只处理数据计算任务，而分片、负载均衡、容灾等任务超出了Knowhere的工作范围。

从 Milvus 2.0.1 开始，Knowhere（广义上的）独立于 Milvus 项目。

了解 Milvus 架构

Milvus 中的计算主要涉及向量和标量运算。 Knowhere 只处理 Milvus 中对向量的操作。上图展示了 Milvus 中的 Knowhere 架构。

最底层是系统硬件。第三方索引库位于硬件之上。然后 Knowhere 通过 CGO 与顶部的索引节点和查询节点进行交互。

本文讨论了更广泛意义上的 Knowhere，如架构插图中的蓝色框架内所示。

Knowhere 与 Faiss

Knowhere 不仅进一步扩展了 Faiss 的功能，还优化了性能。更具体地说，Knowhere 具有以下优点。

1. 支持BitsetView

最初，在 Milvus 中引入 bitset 是为了“软删除”。软删除的向量仍然存在于数据库中，但不会在向量相似性搜索或查询期间计算。位集中的每个位对应一个索引向量。如果一个向量在bitset中被标记为“1”，则表示该向量被软删除，在向量搜索过程中不会涉及。

bitset 参数被添加到 Knowhere 中所有公开的 Faiss 索引查询 API，包括 CPU 和 GPU 索引。

2. 支持索引二进制向量的更多相似性指标

除了 Hamming，Knowhere 还支持 Jaccard、Tanimoto、Superstructure 和 Substructure。 Jaccard 和 Tanimoto 可用于衡量两个样本集之间的相似性，而上层结构和子结构可用于衡量化学结构的相似性。

3.支持AVX512指令集

Faiss 本身支持多种指令集，包括 AArch64、SSE4.2 和 AVX2。 Knowhere 进一步扩展了支持的指令集，增加了 AVX512，相比 AVX2 可以将索引构建和查询的性能提升 20% 到 30%。

4. 自动 SIMD 指令选择

Knowhere 目的是在具有不同 SIMD 指令（例如 SIMD SSE、AVX、AVX2 和 AVX512）的各种 CPU 处理器（本地和云平台）上良好运行。因此，挑战在于，给定一个软件二进制文件（即 Milvus），如何让它在任何 CPU 处理器上自动调用合适的 SIMD 指令？ Faiss 不支持自动 SIMD 指令选择，用户需要在编译时手动指定 SIMD 标志（例如“-msse4”）。然而，Knowhere 是通过重构 Faiss 的代码库而构建的。依赖 SIMD 加速的常见功能（例如，相似性计算）被排除在外。然后对于每个函数，实现了四个版本（即 SSE、AVX、AVX2、AVX512）并将每个版本放入单独的源文件中。然后使用相应的 SIMD 标志进一步单独编译源文件。因此，在运行时，Knowhere 可以根据当前 CPU 标志自动选择最适合的 SIMD 指令，然后使用hook链接正确的函数指针。

5.其他性能优化
阅读 Milvus：专门构建的矢量数据管理系统，了解有关 Knowhere 性能优化的更多信息。

了解 Knowhere 代码
如第一节所述，Knowhere 只处理向量搜索操作。因此，Knowhere 只处理实体的向量场（目前仅支持集合中实体的一个向量场）。索引构建和向量相似性搜索也针对片段中的向量场。

索引
索引是一种独立于原始向量数据的数据结构。索引需要四个步骤：创建索引、插入数据、训练数据和构建索引。

对于某些 AI 应用程序，数据集训练是矢量搜索的一个单独过程。在这种类型的应用程序中，来自数据集的数据首先经过训练，然后插入到像 Milvus 这样的向量数据库中进行相似性搜索。 sift1M 和 sift1B 等开放数据集为训练和测试提供数据。但是，在 Knowhere 中，用于训练和搜索的数据混合在一起。也就是说，Knowhere 训练一个段中的所有数据，然后插入所有训练好的数据并为它们建立索引。

Knowhere 代码结构
DataObj 是 Knowhere 中所有数据结构的基类。 Size() 是 DataObj 中唯一的虚拟方法。 Index 类继承自 DataObj，具有名为“size_”的字段。 Index 类还有两个虚方法——Serialize() 和 Load()。从 Index 派生的 VecIndex 类是所有向量索引的虚拟基类。 VecIndex 提供的方法包括 rain()、Query()、GetStatistics() 和 ClearStatistics()。

上图右侧列出了其他索引类型。

• Faiss 索引有两个子类：FaissBaseIndex 用于浮点向量上的所有索引,FaissBaseBinaryIndex 用于二进制向量上的所有索引。
• GPUIndex 是所有 Faiss GPU 索引的基类。
• OffsetBaseIndex 是所有自研索引的基类。只有向量 ID 存储在索引文件中。因此，128 维向量的索引文件大小可以减少 2 个数量级。我们建议在使用此类索引进行向量相似性搜索时也考虑原始向量。

从技术上讲，IDMAP 不是索引，而是用于暴力搜索。当向量插入向量数据库时，不需要数据训练和索引构建。搜索将直接在插入的矢量数据上进行。

但是，为了代码的一致性，IDMAP 也继承自 VecIndex 类及其所有虚拟接口。 IDMAP 的用法与其他索引相同。

IVF（倒置文件）索引是最常用的。 IVF 类派生自 VecIndex 和 FaissBaseIndex，并进一步扩展到 IVFSQ 和 IVFPQ。 GPUIVF 源自 GPUIndex 和 IVF。然后GPUIVF进一步扩展到GPUIVFSQ和GPUIVFPQ。

IVFSQHybrid是自研混合索引类，在GPU上通过粗量化执行。并在 CPU 上执行桶中的搜索。这种类型的索引可以通过利用GPU的计算能力来减少CPU和GPU之间内存拷贝的发生。 IVFSQHybrid 具有与 GPUIVFSQ 相同的召回率，但具有更好的性能。

二进制索引的基类结构相对简单。 BinaryIDMAP 和 BinaryIVF 派生自 FaissBaseBinaryIndex 和 VecIndex。

目前，除了 Faiss 之外，仅支持两种第三方索引：基于树的索引 Annoy 和基于图的索引 HNSW。这两个常用且经常使用的第三方索引均源自 VecIndex。

向 Knowhere 添加索引
如果要在 Knowhere 中添加新的索引，可以先参考已有的索引：

• 要添加基于量化的索引，请参阅 IVF_FLAT。
• 要添加基于图形的索引，请参阅 HNSW。
• 要添加基于树的索引，请参阅 Annoy。

参考现有索引后，您可以按照以下步骤将新索引添加到 Knowhere。

• 在 IndexEnum 中添加新索引的名称。数据类型是字符串。
• 在 ConfAdapter.cpp 文件中对新索引添加数据验证检查。验证检查主要是验证数据训练和查询的参数。
• 为新索引创建一个新文件。新索引的基类应包括 VecIndex 和 VecIndex 必要的虚拟接口。
• 在 VecIndexFactory::CreateVecIndex() 中为新索引添加索引构建逻辑。
• 在 unittest 目录下添加单元测试。