摘要：在下文中，我将尝试通过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的类。

点击关注，第一工夫理解华为云陈腐技术~