Milvus 最佳实践之如何选择索引类型

在Milvus 0.5.3版本中，支持的索引类型包括如下几种：

FLAT

IVFFLAT

IVFSQ8

IVFSQ8H

在不同的应用场景下该如何选择一种合适的索引并非那么地显而易见，需要在资源使用量、查询效率、查询召回率等多个指标中做权衡。

本文中用到的一些符号及专用名词说明如下：

FLAT

FLAT并不是一种真正的索引，但由于它与其它的索引有一致的接口及使用方法，Milvus把它视为一种特殊的索引。FLAT的查询速度在所有的索引中是最慢的，但是当需要查询的次数较少，构建索引的时间无法被有效均摊时，它反而是最有效的查询方式。FLAT的另一个优点是，它能达到100％的查询召回率，这是所有其它索引类型所无法达到的。而且FLAT不需要数据做训练，不需要配置任何参数，也不需要占用额外的磁盘空间（其它的索引类型在保存成文件时需要占用额外的磁盘空间）。

优点：100％查询召回率

缺点：查询速度慢

Milvus可以同时查询nq条向量，并一次性返回nq条向量的topk个最近邻向量（包括向量id和距离）。

FLAT索引受Milvus配置参数search_resources控制，当search_resources中有CPU资源时，查询在CPU上进行；当search_resources中只有GPU资源时，查询在GPU上进行。

下图是在2,000,000条128维向量数据集上测得的，分别在CPU和GPU上，FLAT查询时间随nq的变化曲线 。查询时间与topk 无关，随着nq的增大而增大。

图1-1 FLAT 查询时间

用GPU能够获得更好的查询性能，但需要考虑额外的从内存到显存的数据拷贝时间。当nq小于20时，FLAT在CPU上查询得更快。

除了FLAT之外，其它的索引方法都需要对原始数据集做预处理，包括训练（Train）和聚类（Clustering）。索引类型名称前带有IVF前缀说明聚类所采用的方法是倒排索引。在默认情况下，Milvus每接收到1G的原始数据（2,000,000条128维向量的数据大小约为1G），就会启动一个新的线程对这1G数据做训练和聚类，并将生成的索引文件保存到磁盘。数据的导入和索引的构建在不同线程并发执行。

IVFFLAT

IVFFLAT是最简单的索引类型。在聚类时，向量被直接添加到各个分桶中，不做任何压缩，存储在索引中的数据与原始数据大小相同。查询速度与召回率之间的权衡由参数nprobe来控制。nprobe越大，召回率越高，但查询时间越长。IVFFLAT是除了FLAT外召回率最高的索引类型。

优点：查询召回率高

缺点：占用空间大

IVFFLAT索引受Milvus配置参数search_resources的控制，当search_resources中有CPU资源时，查询在CPU上进行；当search_resources中只有GPU资源时，查询在GPU上进行。

用公开数据集sift-1b（10亿条128维向量）建立IVFFLAT索引，并分别只用CPU或GPU做查询，在不同nprobe参数下测得的查询时间随nq变化曲线如下图：

图2-1 IVFFLAT查询时间

IVFFLAT在CPU上的查询时间与nq、nprobe正相关，而IVFFLAT在GPU上的查询时间对nq和nprobe的变化并不敏感。这是因为IVFFLAT的索引数据较大，将索引数据从CPU拷贝到GPU所用时间占了总查询时间的大部分。由图所示，除了nq＝1000且nprobe＝32的情况，IVFFLAT在CPU上的查询效率更高。

用公开数据集sift-128-euclidean（1,000,000 条128维向量）和glove-200-angular（1,183,514 条200维向量）分别建立IVFFLAT索引（nlist=16384），并测得召回率（k=10）随nprobe变化曲线如下图：

图2-2 IVFFLAT 查询召回率

当nprobe=256时，IVFFLAT在sift-128-euclidean数据集上的查询召回率（k=10）能达到0.99以上。

IVFSQ8

由于IVFFLAT未对原始的向量数据做任何压缩，IVFFLAT索引文件的大小与原始数据文件大小相当。例如sift-1b数据集原始数据文件的大小为476GB，生成的IVFFLAT索引文件大小有470GB左右，若将全部索引文件加载进内存，就需要470GB的内存资源。

当磁盘或内存、显存资源有限时，IVFSQ8是一个更好的选择。它通过对向量进行标量量化（Scalar Quantization），能把原始向量中每个FLOAT（4字节）转为UINT8（1字节），从而可以把磁盘及内存、显存资源的消耗量减少为原来的1/4~1/3。同样以sift-1b数据集为例，生成的IVFSQ8索引文件只有140GB。

优点：查询速度快，资源占用仅为IVFFLAT的1/4~1/3

缺点：查询召回率比IVFFLAT低

IVFSQ8索引也受Milvus配置参数search_resources控制，当search_resources中有CPU资源时，查询在CPU上进行；当search_resources中只有GPU资源时，查询在GPU上进行。

用公开数据集sift-1b（10亿条128维向量）建立IVFSQ8索引，并分别只用CPU或GPU做查询，在不同nprobe参数下测得的查询时间随nq变化曲线如下图：

图3-1 IVFSQ8查询时间

IVFSQ8的查询性能曲线跟IVFFLAT非常相似，但索引大小的精减带来了全面的性能提升。同样，在nq和nprobe较小时，IVFSQ8在CPU上的查询性能更高。

用公开数据集sift-128-euclidean（1,000,000 条128维向量）和glove-200-angular（1,183,514 条200维向量）分别建立IVFSQ8索引（nlist=16384），并测得召回率（k=10）随nprobe变化曲线如下图：

图3-2 IVFSQ8查询召回率

对比图2-2和图3-2，IVFSQ8对原始数据的压缩并未导致明显的查询召回率下降，对应不同的nprobe，IVFSQ8的召回率（k=10）最多只比IVFFLAT低1个百分点。

IVFSQ8H

IVFSQ8H是Milvus对IVFSQ8进行深度优化后新建的一种索引类型。IVFSQ8索引在CPU上查询时，找出距离被查询向量最近的nprobe个分桶（Coarse Quantizer）所用的时间占了总查询时间的大部分。IVFSQ8H把用于Coarse Quantizer运算的数据（大小远小于索引数据）单独拷贝到GPU运算，能大大缩短Coarse Quantizer时间。Coarse Quantizer之后，每个分桶中的查询受配置参数gpu_search_threshold控制，当nq>=gpu_search_threshold时，查询在GPU上进行；反之在CPU上进行。

优点：同IVFSQ8，且查询性能优于IVFSQ8

缺点：同IVFSQ8

IVFSQ8H需要CPU和GPU协同工作，因此在search_resources中必须同时拥有CPU资源和GPU资源。

用公开数据集sift-1b（10亿条128维向量）建立IVFSQ8H索引，在gpu_search_threshold=1001时，在不同nprobe参数下测得的查询时间随nq变化曲线如下图：

图4-1 IVFSQ8H查询时间

当nqgpu_search_threshold，分桶内的搜索转为在GPU上执行，IVFSQ8H的查询时间与IVFSQ8持平。只要选择合理的gpu_search_threshold配置，能保证IVFSQ8H的查询性能不会差于IVFSQ8。

IVFSQ8H的查询召回率与IVFSQ8完全相同。

总结

简而言之，每种索引都有自己的适用场景，如何选择合适的索引可以简单遵循如下原则：

1) 当查询数据规模小，且需要100％查询召回率时，用FLAT；

2) 当需要高性能查询，且要求召回率尽可能高时，用IVFFLAT；

3) 当需要高性能查询，且磁盘、内存、显存资源有限时，用IVFSQ8H；

4) 当需要高性能查询，且磁盘、内存资源有限，且只有CPU资源时，用IVFSQ8。

注：文中测试所用服务器配置如下：

Intel(R) Xeon(R) Platinum 8163 @ 2.50GHz, 24 cores

GeForce GTX 2080Ti x 4

768GB memory

2019 ZILLIZ