使用faiss最重要的就是选择index，虽然官方提供了很多index，但在实际工作中要权衡使用。本文主要考虑：

  1. 可以是批量操作id
  2. id可以自定义
  3. 内存、可否使用GPU(faiss CPU线程安全，GPU线程不安全)
  4. 速度
  5. 准确性（放在最后考虑是因为faiss足够强，准确性不会太差）

最终选择的索引是 IndexIVFFlat

0 本文目标

搭建一个查询faiss的服务

  1. 当接受一个查询向量，没有在faiss cache中找到相似度高的向量，则将该向量加入cache，并增加自定义id。
  2. faiss cache中向量在长时间没有被检索，视为过期，移除该向量。
  3. 移除向量是个高消耗操作，需要批量操作。

1 理论基础补充

需要先阅读：faiss详解文章 https://www.yuque.com/shareit/yijiao/th56cr#4MNWO

1.1 index高阶操作

这部分只有几个索引可以使用：支持IndexFlat, IndexIVFFlat (需要与make_direct_map结合), IndexIVFPQ, IndexPreTransform这几类索引类型。

数据准备：

  1. import numpy as np 
  2. import faiss
  4. #生成数据
  5. d = 10
  6. n_data = 500
  7. data = np.random.rand(n_data, d).astype('float32')

1.1.1 从索引重建向量(从index中提取向量）

给定id，可以使用reconstruct或者reconstruct_n方法从index中回复出原始向量。

  1. index = faiss.IndexFlatL2(d)
  2. index.add(data)
  3. re_data = index.reconstruct(0)  # 指定需要恢复的向量的id,每次只能恢复一个向量
  4. print(re_data)
  5. re_data_n = index.reconstruct_n(0, 10) # 从第0个向量开始，连续取10个
  6. print(re_data_n.shape)
  8. [0.1341046  0.33378014 0.98919195 0.21173532 0.2883128  0.11518779
  9.  0.5738503  0.62650466 0.02399825 0.16701537 0.21001063 0.8286967
  10.  0.10198797 0.6235889  0.61777    0.62631434]
  11. (10, 16)

缺点：reconstruct_n()只能连续取向量，不方便。

1.1.2 从索引中删除元素（从index中移除向量）

  1. index = faiss.IndexFlatL2(d)
  2. index.add(data)
  3. print(index.ntotal)
  4. index.remove_ids(np.arange(5)) # 需要移除的向量的id
  5. print(index.ntotal)  #移除了5个向量，还剩495个
  7. index.remove_ids(np.array([1,5,9,6,5])) # 需要移除的向量的id
  8. print(index.ntotal)  #移除了5个向量，还剩490个

优点：remove_ids()可以移除指定id列表。结合 1.1.1，意味着后续只能记录向量过期时间，移除过期向量，而不是提取未过期向量。
恰好IndexIVFFlat可以使用index索引，满足需求第一个条件

1.2 为向量添加唯一ID

  1. 对于支持 add_with_ids() 方法的index
  1. ids = list[] ...
  2. ids = numpy.array(ids).astype('int')    # 转换成int型一维数组
  3. index.add_with_ids(data,ids)
  1. 对于不支持 add_with_ids() 的 index 借助 IndexIDMap，如IndexFlatL2
    1. ids = list[] ...
    2. ids = numpy.array(ids).astype('int')    # 同上
    3. index = ...
    4. index2 = faiss.IndexIDMap(index)
    5. index2.add_with_ids(data, ids)
    6. D, I = index2.search(data[:50], k)      # 注意这里对索引的add 和 search
    7.                                      # 都需要调用index2 来进行操作
    8.                                      # 来获取向量正确的id

注：
IndexIVF子类总是存储向量ID，IndexIVF天生就提供了add_with_ids，所以 IndexIVFFlat 可以直接使用add_with_ids，满足第二个条件。

1.3 内存、GPU问题

请记住，所有的Faiss索引都将向量存储在RAM中。以下内容认为，如果不需要准确的结果，RAM是限制因素，并且在内存约束条件下，我们将把精确度和速度进行折衷。以下形式为索引工厂函数形式。

  • 如果不： “HNSWx”

如果你有很多RAM或数据集很小，HNSW是最好的选择，它是一个非常快速和准确的指标。4 <= x<= 64是每个矢量的链接数量，越高越准确，但使用更多的RAM。速度 - 精度权衡是通过efSearch参数设置的。内存使用量为每个矢量（d 4 + x 2 * 4）个字节。
HNSW只支持顺序添加（不addwith_ids），所以在这里再次，IDMap如果需要前缀。HNSW不需要培训，也不支持从索引中移除向量。
_GPU支持：不支持

  • 如果有的话 “…,Flat”

“…”意味着必须预先执行数据集的聚类（请参阅下文）。聚类后，”Flat”只将矢量组织成桶，所以它不压缩它们，存储大小与原始数据集相同。速度和精度之间的权衡是通过nprobe参数设置的。
在GPU上支持：是（但是请参阅下文，也必须支持聚类方法）

  • 如果相当重要的话 “PCARx,…,SQ8”

如果存储整个向量太昂贵，则执行两个操作：

  • 一个PCA的维度x来减少维度
  • 每个矢量分量的标量量化为1个字节。
    因此总存储量是x每个向量的字节数。
    GPU支持：不支持


  • 如果非常重要的话 “OPQx_y,…,PQx”

PQx使用输出x字节码的产品量化器压缩矢量。x通常<= 64，对于较大的代码，SQ通常是准确和快速的。OPQ是向量的线性转换，使它们更容易压缩。y是这样一个维度：

  • y是x（必需）的倍数
  • y <= d，其中d是输入向量的维数（最好）
  • y <= 4 * x（优选）
    GPU支持：是（注意：OPQ转换是用软件完成的，但它不是性能关键）

很幸运，我的内存不是问题，同时拥有GPU，IndexIVFFlat 满足了第三个条件

1.4 提高速度

为了加快搜索速度，我们可以按照一定规则或者顺序将数据集分段。 我们可以在 d 维空间中定义 Voronoi 单元，并且每个数据库向量都会落在其中一个单元。 在搜索时，查询向量 x， 可以经过计算，算出它会落在哪个单元格中。 然后我们只需要在这个单元格以及与它相邻的一些单元格中，进行与查询向量 x 的比较工作就可以了。

（这里可以类比 HashMap 的实现原理。训练就是生成 hashmap 的过程，查询就是 getByKey 的过程）。

上述工作已经通过 IndexIVFFlat 实现了。 这种类型的索引需要一个训练阶段。因此 IndexIVFFlat 同时需要另外一个 Index： quantizer， 来给 Voronoi 单元格分配向量。 每个单元格由质心（centroid）定义。 找某个向量落在哪个 Voronoi 单元格的任务，就是一个在质心集合中找这个向量最近邻居的任务。 这是另一个索引的任务，通常是 IndexFlatL2。

这里搜索方法有两个参数：nlist（单元格数量），nprobe （一次搜索可以访问的单元格数量，默认为1）。 搜索时间大致随着 nprobe 的值加上一些由于量化产生的常数，进行线性增长。示例：

  1. import numpy as np
  2. import faiss
  3. d = 64                           # dimension
  4. nb = 100000                      # database size
  5. nq = 10000                       # nb of queries
  6. np.random.seed(1234)             # make reproducible
  7. xb = np.random.random((nb, d)).astype('float32')
  8. xb[:, 0] += np.arange(nb) / 1000.
  9. xq = np.random.random((nq, d)).astype('float32')
  10. xq[:, 0] += np.arange(nq) / 1000.
  12. nlist = 100
  13. k = 4
  14. quantizer = faiss.IndexFlatL2(d)  # 另外一个 Index
  15. index = faiss.IndexIVFFlat(quantizer, d, nlist, faiss.METRIC_L2)
  16.        # 这里我们指定了 METRIC_L2, 默认它执行 inner-product 搜索。
  17. assert not index.is_trained
  18. index.train(xb)
  19. assert index.is_trained
  21. index.add(xb)                  # add may be a bit slower as well
  22. D, I = index.search(xq, k)     # actual search
  23. print(I[-5:])                  # neighbors of the 5 last queries
  24. index.nprobe = 10              # default nprobe is 1, try a few more
  25. D, I = index.search(xq, k)
  26. print(I[-5:])                  # neighbors of the 5 last queries
  28. [[ 9900  9309  9810 10048]
  29.  [11055 10895 10812 11321]
  30.  [11353 10164  9787 10719]
  31.  [10571 10664 10632 10203]
  32.  [ 9628  9554  9582 10304]]
  33. [[ 9900 10500  9309  9831]
  34.  [11055 10895 10812 11321]
  35.  [11353 11103 10164  9787]
  36.  [10571 10664 10632  9638]
  37.  [ 9628  9554 10036  9582]]

1.5 减少代码量：索引工厂函数

直接参考 faiss详解 https://www.yuque.com/shareit/yijiao/th56cr#4MNWO

faiss提供了一个index_factory的方法，可以直译为：索引工厂函数。这个索引工厂函数是用来干嘛的呢？

faiss库在构建索引时，为了进一步提高计算效率或减少内存压力，会综合运用更多的算法。比如上面已经用了倒排索引+PQ编码，还可以预先用PCA对向量进行降维。如此一来，在写代码的时候，我们就需要分三步：
首先进行PCA降维（数据预处理），然后倒排（聚类），最后PQ编码（编码）。

为了省事，干脆直接用一个字符串，把数据预处理、聚类、编码的方法和参数拼接在一起，放入索引工厂函数中，一行代码就生成了复合索引。

下面就用索引工厂函数来构建索引：

  • 数据预处理：OPQ16_64，意思是用OPQ把向量降为64维，分为16类。
  • 聚类：IMI2×8，这个没看懂，官网说是构建了65536个倒排索引。
  • 编码：PQ16，意思是把向量压缩到16字节。原先是 128*4=512字节，这压缩了32倍。
  1. index_fac = faiss.index_factory(d,"OPQ16_64,IMI2x8,PQ16") 
  2. start = time.time()
  3. index_fac.train(data)
  4. index_fac.add(data)
  5. end = time.time()
  6. print("\nTime usage for train: {} seconds.\n".format(round((end - start),4)))
  7. start = time.time()
  8. dis, ind = index_fac.search(data[:10], 10)  # 真实查询
  9. end = time.time()
  10. print(ind)
  11. print("\nTime usage for search: {} seconds.\n".format(round((end - start),4)))

理论充分，改写实现：

  1. import numpy as np
  2. import faiss
  3. d = 64                           # dimension
  4. nb = 100000                      # database size
  5. nq = 10000                       # nb of queries
  6. np.random.seed(1234)             # make reproducible
  7. xb = np.random.random((nb, d)).astype('float32')
  8. xb[:, 0] += np.arange(nb) / 1000.
  9. xq = np.random.random((nq, d)).astype('float32')
  10. xq[:, 0] += np.arange(nq) / 1000.
  12. nlist = 100
  13. k = 4
  15. index = faiss.index_factory(d, f"IVF{4*d+8},Flat")
  16. assert not index.is_trained
  17. index.train(xb)
  18. assert index.is_trained
  20. index.add(xb)                  # add may be a bit slower as well
  21. D, I = index.search(xq, k)     # actual search
  22. print(I[-5:])                  # neighbors of the 5 last queries
  23. index.nprobe = 10              # default nprobe is 1, try a few more
  24. D, I = index.search(xq, k)
  25. print(I[-5:])                  # neighbors of the 5 last queries

1.6 减少内存

IndexFlatL2 和 IndexIVFFlat 都会存储所有的向量。 为了扩展到非常大的数据集，Faiss提供了一些变体，它们根据产品量化器（product quantizer）压缩存储的矢量并进行有损压缩。

矢量仍然存储在Voronoi单元中，但是它们的大小减小到可配置的字节数m（d必须是m的倍数）。

压缩基于Product Quantizer， 其可以被视为额外的量化水平，其应用于要编码的矢量的子矢量。

在这种情况下，由于矢量未精确存储，因此搜索方法返回的距离也是近似值。
使用IndexIVFPQ （也可以看 faiss详解的案例）

  1. nlist = 100
  2. m = 8                             # number of bytes per vector
  3. k = 4
  4. quantizer = faiss.IndexFlatL2(d)  # this remains the same
  5. index = faiss.IndexIVFPQ(quantizer, d, nlist, m, 8)
  6.                                     # 8 specifies that each sub-vector is encoded as 8 bits
  7. index.train(xb)
  8. index.add(xb)
  9. D, I = index.search(xb[:5], k) # sanity check
  10. print(I)
  11. print(D)
  12. index.nprobe = 10              # make comparable with experiment above
  13. D, I = index.search(xq, k)     # search
  14. print(I[-5:])

1.7 保存索引

可以使用如下方法将索引保存为文件：
faiss.write_index(index, “large.index”)
然后需要使用时，使用以下方法读取文件建立索引：
index = faiss.read_index(“large.index”)

实战

补充完基础理论，可以开始包装faiss了。主要解决实时增删向量，识别舆情方向。

等待完善…

参考文章

https://blog.csdn.net/u013066730/article/details/106298939
https://www.jianshu.com/p/d35198c5bc23
https://www.yuque.com/shareit/yijiao/th56cr#4MNWO