Faiss了解

Faiss是什么

Faiss全称Facebook AI Similarity Search，是Facebook AI团队开源的相似性搜索工具，或者称为向量数据库。它是面向稠密向量高效的相似性检索以及聚类引擎,可实现在十亿级数据集上创建毫秒级的最邻近搜索（nearest neighbor search）。Faiss用C++编写，并支持Python接口。除此以外，对一些核心算法提供了GPU实现。

Faiss工作机制

Faiss的工作机制简单来说就是把我们自己的候选向量集封装成一个index数据库，并提供一个计算相似性的度量函数进行搜索，它可以加速我们检索相似向量TopK的过程，其中有些索引还支持GPU构建，可谓是强上加强。参考下图，包括构建数据、查询数据两个过程，其中Faiss训练指的是对向量进行聚类，是构建数据中的一个重要步骤。在实际应用时，使用到的三个对象：向量维度、索引类型、度量方法。在构建数据的时候需要选定向量的维度以及索引类型，进行数据训练以及存储；在查询数据的时候需要选定度量方法计算相似度。所以下面会详细介绍Faiss支持的索引类型和度量方法。

度量方法

FAISS支持几种不同的度量方法，这些度量方法用于计算向量之间的相似度或距离。以下是FAISS中常用的几种度量方法：

1. L2 距离（欧氏距离）：

- 用于计算两个向量之间的欧氏距离。

- 表示为 `faiss.METRIC_L2`。

- 适用于许多最近邻搜索问题。

2. 内积（dot product）:

- 用于计算两个向量的内积。

- 表示为 `faiss.METRIC_INNER_PRODUCT`。

- 在某些情况下，内积可以用作相似度度量，尤其是在向量经过归一化后。

3.余弦相似度:

- FAISS本身不直接支持余弦相似度作为一种内置的度量方法，但可以通过归一化向量来间接使用余弦相似度。

- 由于余弦相似度等价于归一化向量的内积，可以先将向量归一化，然后使用内积度量。

各种度量方法的定义：https://zhuanlan.zhihu.com/p/662371692?utm_id=0

构建模块/索引数据训练

Faiss构建模块即构建索引数据的过程，对一些基础算法提供了非常高效的视实现：K-means/聚类、PCA/降维、PQ编解码/量化。这也是其提供的索引类型能够快速检索的因素之一。只需要对这些有一个基本的了解便于后续学习索引类型。

1、K-means聚类：即将给定的向量进行分类汇聚，将各个类别中的中心向量返回。

2、PCA:向量降维

3、PQ编解码/量化：将数据进行编码，然后用这个编码代替数据，从而降低数据对资源的负担。

索引类型/算法

Faiss中的索引类型表示的是算法。一种索引类型即一种算法，当我们选择了一种索引类型之后，Faiss会按照算法定义好的数据结构存储向量数据。举个例子我们熟悉的es索引，它使用倒排索引的结构即单词-文档矩阵来存储数据,以便更加快速的进行全文搜索。FAISS 支持多种索引类型，这些索引类型根据不同的需求和数据集特点进行了优化。以下是一些常见的 FAISS 索引类型：

1. Flat 索引:

- `IndexFlatL2`: 使用 L2 距离（欧氏距离）的扁平索引。

- `IndexFlatIP`: 使用内积的扁平索引。

2. 量化索引:

- `IndexIVFFlat`: 倒排文件（IVF）索引，与扁平索引结合使用。

- `IndexIVFPQ`: 结合了倒排文件和乘积量化（PQ）的索引。

- `IndexIVFFaiss`: 使用 FAISS 方法优化的 IVF 索引。

- `IndexIVFHNSW`: 结合了倒排文件和分层导航小世界（HNSW）的索引。

3. 乘积量化索引:

- `IndexPQ`: 乘积量化索引，使用 PQ 进行向量压缩。

- `Index2Layer`: 两层 PQ 索引，为了更好的压缩和搜索性能。

4. 树结构索引:

- `IndexLSH`: 局部敏感哈希（LSH）索引，适用于大规模数据集。

- `IndexPQ`: 使用 PQ 进行向量压缩的索引。

5. 图索引:

- `IndexHNSWFlat`: 使用扁平索引和 HNSW 图结构的索引。

- `IndexHNSWPQ`: 结合了 PQ 量化和 HNSW 图结构的索引。

6. 复合索引:

- `IndexPreTransform`: 允许在搜索之前对向量应用一个或多个变换（如 PCA、白化等）。

- `IndexIDMap`: 允许在索引中存储额外的 ID 信息，通常与其他索引类型结合使用。

7. 其他索引:

- `IndexScalarQuantizer`: 标量量化索引，对每个向量维度使用不同的量化方法。

- `IndexBinaryFlat`: 用于二进制向量的扁平索引。

- `IndexBinaryIVF`: 用于二进制向量的倒排索引。

每种索引类型都有其特定的适用场景和性能特征。例如，扁平索引（Flat）提供精确的最近邻搜索，但不适合大规模数据集。而倒排文件（IVF）索引适合大规模数据集，但提供的是近似最近邻搜索。乘积量化（PQ）索引和图索引（如 HNSW）旨在提供更高效的搜索和更好的空间压缩。

几种常用的索引类型

暴力查询IndexFlatL2

faiss 中最简单的索引，便是没有使用任何花哨技巧（压缩、分区等）的平面索引：IndexFlatL2。当我们使用这种索引的时候，我们查询的数据会和索引中所有数据进行距离计算，获取它们之间的 L2 距离（欧几里得距离）。因为它会尽职尽责的和所有数据进行比对，所以它是所有索引类型中最慢的一种，但是也是最简单和最准确的索引类型，同时，因为类型简单，也是内存占用量最低的类型。而它采取的遍历式查找，也会被从业者打趣称之为“暴力搜索”。

优点：该方法是Faiss所有index中最准确的，召回率最高的方法，没有之一；

缺点：速度慢，占内存大。

使用情况：向量候选集很少，在50万以内，并且内存不紧张。

注：虽然都是暴力检索，faiss的暴力检索速度比一般程序猿自己写的暴力检索要快上不少，所以并不代表其无用武之地，建议有暴力检索需求的同学还是用下faiss。

构建方法：

查询优化IndexIVFFlat

上面提到的暴力检索方式的计算成本是很高的，那么当数据膨胀到很大的量级，计算的压力一定会成为检索的瓶颈，所以我们才会引入IndexIVFFlat索引类型。

这种索引模型的思路是为了通过分区的方式提高查询速度。和传统数据库一样，我们能够使用不同的手段来优化我们的“查询性能”。在向量数据库中，对于“向量检索”最简单的性能优化方案，便是对索引数据进行分区优化，将数据通过“沃罗诺伊图单元”（也被叫做泰森多边形）来进行切割（类似传统数据库分库分表）。

便于理解此索引结构，我们先来介绍什么叫泰森多边形（Voronoi）。

上图可认为把向量空间划分为多个区域，每个区域有个离散点，称为质心（centroid）。上图中X{i}即为第i个区域的质心。可把上图中点P称为查询向量，则有P与掉入其区域的质心X9距离最近，与非X9的距离较远。回到faiss IndexIVFFlat索引的话题，思路是类似的。这个索引也是把向量集划分成多个区域，然后为每个区域设定一个质心。当查询向量请求时，会用查询向量与多个质心先比较，根据距离最小的或最小的几个召回一系列cell区域。然后再用查询向量与cell区域中的向量数据进行距离计算，排序，输出即可。这个索引有两个重要参数：nlist和nprobe，前者表示向量数据集一共被划分为多少cell区域，后者表示查询时要检索的cell区域个数。

优点：IVF主要利用倒排的思想，在文档检索场景下的倒排技术是指，一个kw后面挂上很多个包含该词的doc，由于kw数量远远小于doc，因此会大大减少了检索的时间。在向量中如何使用倒排呢？可以拿出每个聚类中心下的向量ID，每个中心ID后面挂上一堆非中心向量，每次查询向量的时候找到最近的几个中心ID，分别搜索这几个中心下的非中心向量。通过减小搜索范围，提升搜索效率。

缺点：速度也还不是很快。存储很大

使用情况：相比Flat会大大增加检索的速度，建议百万级别向量可以使用。

参数：IVFx中的x是k-means聚类中心的个数

构建方法：

存储优化-IndexPQ

上面的索引类型为了追求查询效率，牺牲的是内存资源。所以还有一类场景就是海量数据、以及数据快速增长的场景中，业务所使用的服务器资源的内存完全装不下我们的向量数据。无法支撑我们采用分区索引或者平面索引这种相对精确的相似性检索，我们需要想办法大幅降低内存占用。同时，因为数据量极大，即使采用能够性能提升非常明显的分区索引，也无法满足低延时的计算结果返回。

这个时候，我们就需要采用“乘积量化（Product Quantization）”的方式，来建立 PQ 索引，帮助我们加速检索过程，同时减少内存空间占用。简单理解，乘积量化索引具备一定的压缩向量数据的功能，某种程度上，它和分区索引所采取的“加速”思想是类似的，都是减少计算量：分区索引采取的是划分大量“数据单元”，动态调整搜索范围；向量索引则更进一步，除了划分细粒度的“工作区域”外，还预先计算了不同向量数据之间的“距离”，让每一堆向量数据都是距离这堆向量数据的质心更近的数据。

假设，入库向量数据为50k个1024维embedding/向量。此索引先按维度进行切分，如上图1024维被切成8个128维。

将50k的向量数据进行聚类操作，得到256个聚类中心。

用128维的子向量与256个聚类中心点分别计算L2距离，得到8个距离长度。

检索过程：当有一个查询向量到来时，执行过程如下。

1、把查询向量由1024维切分为8个128维子向量。

2、用子向量与所属组的256个聚类中心分别计算L2距离，每组维护一个256长度的距离表。

3、对50k个向量中的每个，找到对应8个分组中各自的聚类中心，各自的距离分量，求和得完整距离。

4、然后把完整距离排序，输出即可。

优点：利用乘积量化的方法，改进了普通检索，将一个向量的维度切成x段，每段分别进行检索，每段向量的检索结果取交集后得出最后的TopK。因此速度很快，而且占用内存较小，召回率也相对较高。

缺点：召回率相较于暴力检索，下降较多。

使用情况：内存及其稀缺，并且需要较快的检索速度，不那么在意召回率

参数：PQx中的x为将向量切分的段数，因此，x需要能被向量维度整除，且x越大，切分越细致，时间复杂度越高

构建方法：

查询存储优化-IndexIVFPQ

上述介绍了PQ的过程，但是IndexIVFPQ中查询向量不需要和50k个向量逐一计算，仅仅需要和50k中子集计算即可。IndexIVFPQ即是IVF+PQ，原理也很简单。

优点：工业界大量使用此方法，各项指标都均可以接受，利用乘积量化的方法，改进了IVF的k-means，将一个向量的维度切成x段，每段分别进行k-means再检索。

缺点：集百家之长，自然也集百家之短

使用情况：一般来说，各方面没啥特殊的极端要求的话，最推荐使用该方法！

参数：IVFx，PQy，其中的x和y同上

构建方法：

局部敏感哈希IndexLSH

原理：哈希对大家再熟悉不过，向量也可以采用哈希来加速查找，我们这里说的哈希指的是局部敏感哈希（Locality Sensitive Hashing，LSH），不同于传统哈希尽量不产生碰撞，局部敏感哈希依赖碰撞来查找近邻。高维空间的两点若距离很近，那么设计一种哈希函数对这两点进行哈希计算后分桶，使得他们哈希分桶值有很大的概率是一样的，若两点之间的距离较远，则他们哈希分桶值相同的概率会很小。

优点：训练非常快，支持分批导入，index占内存很小，检索也比较快

缺点：召回率非常拉垮。

使用情况：候选向量库非常大，离线检索，内存资源比较稀缺的情况

构建方法：

图索引IndexHNSWFlat

优点：该方法为基于图检索的改进方法，检索速度极快，10亿级别秒出检索结果，而且召回率几乎可以媲美Flat，最高能达到惊人的97%。检索的时间复杂度为loglogn，几乎可以无视候选向量的量级了。并且支持分批导入，极其适合线上任务，毫秒级别体验。

缺点：构建索引极慢，占用内存极大（是Faiss中最大的，大于原向量占用的内存大小）

参数：HNSWx中的x为构建图时每个点最多连接多少个节点，x越大，构图越复杂，查询越精确，当然构建index时间也就越慢，x取4~64中的任何一个整数。

使用情况：不在乎内存，并且有充裕的时间来构建index

构建方法：

总结

Faiss的检索方式并非精确检索，而是模糊检索。既然是模糊检索，那么必定有所损失，一般使用召回率来表示模糊检索相对于精确检索的损失。在实际的工程中，候选向量的数据集，index所占内存的大小，检索所需的时间（是离线检索还是在线检索）、index构建时间、检索的召回率等都是我们选择index时常常需要考虑的地方。

在选择索引类型时，需要根据数据集的大小、向量维度、内存限制以及对搜索速度和准确性的需求来决定。通常为了获得最佳性能，可能需要对不同的索引类型进行实验和基准测试。