摘要： 在下文中，我将尝试通过 Faiss 源码中各种类构造的设计来梳理 Faiss 中的各种概念以及它们之间的关系。
本文分享自华为云社区《Faiss 源码分析（一）: 类构造剖析》，原文作者：HW007。
Faiss 是由 Facebook AI Research 研发的为浓密向量提供高效类似度搜寻和聚类的框架。通过其官网给出的老手指南，咱们能够疾速地体验 Faiss 的基本功能。然而，置信大多数人看完官网的老手指南后，对 Faiss 很多的概念还是有点含糊、无奈清晰的明确这些概念之间的边界。比如说在 Faiss 中，Quantizer 是个什么概念、其与 Index 之间的分割是什么；还有各种 Index 之间的关系又是什么等等。为此，在下文中，我将尝试通过 Faiss 源码中各种类构造的设计来梳理 Faiss 中的各种概念以及它们之间的关系。
首先奉上 Faiss 源码的类图全家福如下，具体的 EA 类图文件见附件：
图一：Faiss 的类图全家福
首先，咱们来看一下 Faiss 最次要的性能：类似度搜寻。如下图所示，以图片搜寻为例，所谓类似度搜寻，便是在给定的一堆图片（下图中左上角的图集）中，寻找出我指定的指标（下图中左下角的巴士图片）最像的 K 张图片，也简称为 KNN（K 近邻）问题。
接下来咱们看一下为了解决 KNN 问题，在工程上咱们至多须要做哪些事件。显然，有两件事是必须要做的，第一，咱们要把下面例子中的那个图库存储起来；第二，当用户指定一种图片后，咱们须要晓得怎么从存储的图库中找到最近类似的 K 张图片。由此，咱们确定了 Faiss 在其利用场景中至多应该具备的两个性能：增加性能和搜寻性能。
对于相熟数据库的同学来说，应该能在这里嗅到点“CRUD”的滋味。确实，当咱们对“图集”有增加存储这样的动作后，批改和删除等性能也便接踵而来了。由此 Faiss 实质上就是一个向量数据库。对于数据库来说，时空优化是两个永恒的主题，即在存储上如何以更少的空间来存储更多的信息，在搜寻上如何以更快的速度来搜寻出更精确的信息。如何缩小搜寻所需的工夫？在数据库中很最常见的操作便是加各种索引，把各种减速搜索算法的性能或空间换工夫的策略都封装成各种各样的索引，以满足各种不同的援用场景。
由此，咱们便不难理解为什么 Faiss 中为什么会有那么多的 Index 了，因为 Index 这个概念自身就与减速搜寻是绑在一起的。由此也能够看出在 Faiss 中，如何又快又准地找到类似向量是第一要务。下图中给出的是 Faiss 中最重要的两个基类：Index 和 IndexBinary。
在上图中，用红色的箭头标出了这两个基类中最重要的三个函数，其中 add() 和 search() 函数便对应了我上文中所提到的 Faiss 至多应该实现的两个基本功能：存储和搜寻。在此顺带提一下，与传统的数据库相比，Faiss 的 Index 还蕴含了数据存储的性能，如果你一开始就从字面上依照传统数据库中索引的概念来了解地话，就会感觉有点怪怪的。接下来，咱们重点聊聊 Index 中的 train() 函数，咱们都晓得天上是不会白白掉馅饼的，对于 Faiss 来说，不论其为了缩小存储空间还是减速搜寻，都须要提前做好一些筹备工作，这便是 train() 函数发挥作用的时候了。
以缩小存储为例子，咱们都晓得在图片解决中通过 PCA 能够将图片从高维空间（p 维）转换到低维空间（q 维, 其中 p > q），其具体操作便是是将高维空间中的图片向量（np）乘以一个转换矩阵（pq），失去一个低维空间中的向量（nq）。为了使得在整个降维的过程中信息失落起码，咱们须要看待转换图片进行剖析计算失去相应的转换矩阵（pq）。也就是说这个降维中乘以的转换矩阵是与待转换图片非亲非故的。
回到咱们的 Faiss 中来，假如我冀望应用 PCA 预处理来缩小 Index 中的存储空间，那在整个解决流程中，除了输出搜寻图库外，我必须多输出一个转换矩阵，然而这个转换矩阵是与图库非亲非故的，是能够由图库数据计算出来的。如果把这个转换矩阵看成一个参数的话，咱们能够发现，在 Faiss 的一些预处理中，咱们会引入一些参数，这些参数又无奈一开始由人工来指定，只能通过喂样本来训练进去，所以 Index 中须要有这样的一个 train() 函数来为这种参数的训练提供输出训练样本的接口。由此，咱们也能够发现，这些喂给 train() 函数的样本数据最好与之后要增加存储的图集以及搜寻指标统一比拟好，比如说，你先给 Index 喂一个猪脸数据集训练出 PCA 中的转换矩阵，再给这个 Index 增加人脸数据集，最初再在这个索引上做人脸识别，这样必定比不上一开始就喂人脸数据集失去 PCA 转换矩阵的成果好。
由上，咱们曾经能够从 train()、add() 和 search() 三大函数大略地理解到 Faiss 中的 Index 是个什么货色了，接下来咱们看一下 Faiss 中有哪些不同的 Index。从图一中的类图中能够看到，在 Faiss 中，大多数类根本都继承或应用了 Index 接口，他们要么对 Index 接口中定义的 train、add 和 search 函数进行了本人个性化的实现（如图一中被淡橙色标注的类），要么就是对曾经实现的三大函数的类进行包装，提供一些三大函数之外的流程上的加工解决（如图一中被淡蓝色标注的类）。
从图一中咱们能够看到这些被淡蓝色标注的偏包装的 Index 子类，他们与 Index 基类之间既有“is a”又有“hold a”关系，在类构造上呈现这种关系的时候，设计者要么是在设计一个树或链表的节点，要么是在设计一个包装类。显然在 Faiss 中更偏差于后者。一方面，淡蓝色的 Index 子类借助其所“hold”的 Index 来提供根本的 train、add 和 search 性能，使其本身合乎 Index 接口的定义规范，成为一种 Index，为之后的层层嵌套包装提供反对。另一方面，他又对其所“hold”的 Index 类进行了一些通用的性能扩大。如下图的 IndexPreTransform 类所示，Faiss 将看待存储图集的预处理，如归一化、PCA 降维等性能形象成一个 VectorTransform 接口，让 IndexPreTransform 应用它来为其所“hold”的 Index 增加预处理性能，这种预处理性能是与其所“hold”的是什么 Index 没有任何关系，因而我更偏差于将这种性能归结为 Index 之外的流程上的包装性能。如 IndexPreTransform 类提供了数据预处理性能、IndexIDMap 类提供了自定义 ID 性能、IndexShards 类为 Index 的并行计算提供了相干的反对等。
接下来咱们来看一下图一中被淡橙色标注的 Index 子类，如 IndexLSH、IndexPQ、IndexIVFPQ 等，从名字中咱们能够大略理解到这些类都是基于一些不同的算法实现的不同索引，他们的 train、add 和 search 办法各有差别。但在整体上还是能找到一些其余构造上的共性。在上文中，咱们晓得 Index 具备存储的性能，这些被淡橙色标注的 Index 子类在数据存储形式上根本能够划分为两大类，一类是对立存到一个容器中，如在 IndexLSH、IndexPQ 等中咱们都能够看到一个命名为 codes 的 vector 容器。另一类是分桶贮存到多个容器中，这次要为索引后续的非准确分桶部分搜寻提供反对，为此，Faiss 顺便形象出 InvertedLists 接口，须要反对分桶部分搜寻的 Index 子类均会有 hold 一个实现了 InvertedLists 接口（淡紫色标注）的实例来存储其数据。如下图所示，Faiss 为 InvertedLists 接口提供了数组、链表和磁盘文件等三种不同的实现。
在图一中还有两个被标记为淡绿色的类 ProductQuantizer 和 ScalarQuantizer 值得大家关注下，在结构上，这两个类均没有派生的子类，并且所有其余的类与他们的关系均为“hold a”关系，很纯正的工具类。从其命名中的 Quantizer（量化器）后缀可知，这两个工具类的作用是将“间断或浓密”的数据进行“离散或稠密化”，简略来说就是进行聚类的操作，就像咱们把 18 岁以下的称为少年，18~50 岁的称为中年一样，咱们把具体年龄量化成年龄段的过程就是一个聚类的过程。从图一中还能够看到，带有 Quantizer 后缀的类还有四个：MultiIndexQuantizer、MultiIndexQuantizer2、IndexScalarQuantizer 和 Level1Quantizer。其中前三个均是通过对 ProductQuantizer 或 ScalarQuantizer 的包装来实现 Quantizer 的性能，没什么稀奇的中央，但最初一个 Level1Quantizer 类居然是包装了两个 Index 类，而且其中一个 Index 类的属性名还是 quantizer，如下图所示。
难道 Index 也是一种 Quantizer？确实，对于 Index 来说，咱们更相熟的是其将数据集存储起来，再寻找某个数据在该数据集中的 K 个最近邻点的性能。但如果 Index 中存储的是数据分类后各个类的中心点呢，那么对于某个数据，咱们便能够在该 Index 上通过 KNN 来求得其 K（此时 K =1）个最近邻点，这些求进去的中心点所代表的类便是该数据在聚类中该归属的类。由此咱们能够看到 Index 是可用来聚类，将数据量化成类的中心点的。因而，Index 能够被包装成一个 Quantizer 也便难能可贵了。其实 Index 的这种聚类性能在 Faiss 的设计中是很常见的，除了下面所说的用来做 Quantizer 外，还能够用来辅助实现 K -means 算法，这也是为什么 Level1Quantizer 类中除 quantizer 外还存在一个名为 clustering_index 的 Index 类型属性的起因。通过下面的剖析，咱们还能够晓得，在 Faiss 的 Quantizer 类中，或明或暗都应该有个中央来存储用来辅助量化的“centroids”，即类中心点，它们在大多数场景中都是通过数据训练进去的（如对数据进行 K -means 聚类），在多数场景中也能够间接人为设定。
让咱们最初来关注下 IndexIVF 类（上图中被圈进去的淡紫色类）。兴许在上文介绍淡紫色的 InvertedLists 类簇时，有人会有疑难，InvertedLists 类及其派生子类在 Faiss 中次要为 Index 提供非准确的分桶部分搜寻性能，这种性能与 Index 的品种毫无关系，按上文对 Index 派生的子类的分类规范来看，IndexIVF 类应该是一个偏包装的 Index 子类，应该被标注为淡蓝色才对。确实，如上图所示，尽管 IndexIVF 类没有间接“hold a”Index 类，但其通过继承 Level1Quantizer 类间接“hold a”Index 类，的确也是一个偏包装的 Index 派生子类。图一的色彩标注只是为了突出领有 IVF 性能的 Index 类，通过色彩来辅助各个性能类簇在视觉上的区分度而已，不用深究。
通过上文，咱们能够发现，Faiss 的整个类结构设计是十分清晰简洁的，其首先将 KNN 问题的解决过程切分成 train、add 和 search 三个步骤并形象出 Index 基类。接着从这些基类派生出各种偏性能实现或者偏流程包装的 Index 子类。此外还为 Index 提供了两种的存储形式：集中和分桶（IVF）。最初还提供了 SQ 和 PQ 两种量化编码工具以及将这些编码工具或其余的 Index 包装成 Quantizer 的类。
点击关注，第一工夫理解华为云陈腐技术~