Elasticsearch 向量搜索插件调研和测试
in Note with 0 comment
Elasticsearch 向量搜索插件调研和测试
in Note with 0 comment

背景

这里是一篇调研和性能测试报告,我们发现业界有在使用elasticsearch+向量搜索插件的方式去做一些特征搜索,这个方向是比较成熟的,目前在使用这种方式的有阿里和百度等等,同时发现有些开源插件也能满足我们的需求,如elastiknn。阿里云和百度的插件是闭源的,要使用他们的服务才给使用。官方也有对向量搜索的支持,也试用过,但是不够理想,故先测试使用 elastiknn。

所有的压测都是在同一台机下进行。压测的 Elasticsearch 是单节点,配置 16G 的 JVM ,版本是 7.14.1,elastiknn 插件版本是 7.14.1.2,不进行任何 elasticsearch 节点级的调优工作,使用默认配置。

下面是三种算法的插件优缺点对比:
2021-11-10T08:03:17.png

相关链接:

一些辅助理解的链接:

业务选型

我们主要业务场景是存储一些向量特征,并对这些特征进行相似性搜索,现在的线上的业务使用的相似性搜索算法是余弦距离算法,特征集有大有小,刚好插件能满足需求,下面是基于业务情况和插件自身的特性进行选型,并会基于这些选型进行性能测试。

mapping 配置

LSH

第一种:elastiknn_dense_float_vector + lsh + cosine

这种是使用了局部敏感哈希(Locality Sensitive Hashing,LSH)算法,是近似最近邻搜索算法中最流行的一种,它有坚实的理论依据并且在高维数据空间中表现优异。需要注意的是,LSH 是ANN中的一类方法,这里插件本身用到的具体 hash 算法是随机映射算法(Random Projection algorithm),该算法是为cosine distance between vectors 而设计的。

LSH的基本思想是:将原始数据空间中的两个相邻数据点通过相同的映射或投影变换(projection)后,这两个数据点在新的数据空间中仍然相邻的概率很大,而不相邻的数据点被映射到同一个桶的概率很小。也就是说,如果我们对原始数据进行一些hash映射后,我们希望原先相邻的两个数据能够被hash到相同的桶内,具有相同的桶号。对原始数据集合中所有的数据都进行hash映射后,我们就得到了一个hash table,这些原始数据集被分散到了hash table的桶内,每个桶会落入一些原始数据,属于同一个桶内的数据就有很大可能是相邻的,当然也存在不相邻的数据被hash到了同一个桶内。因此,如果我们能够找到这样一些hash functions,使得经过它们的哈希映射变换后,原始空间中相邻的数据落入相同的桶内的话,那么我们在该数据集合中进行近邻查找就变得容易了,我们只需要将查询数据进行哈希映射得到其桶号,然后取出该桶号对应桶内的所有数据,再进行线性匹配即可查找到与查询数据相邻的数据。换句话说,我们通过hash function映射变换操作,将原始数据集合分成了多个子集合,而每个子集合中的数据间是相邻的且该子集合中的元素个数较小,因此将一个在超大集合内查找相邻元素的问题转化为了在一个很小的集合内查找相邻元素的问题,显然计算量下降了很多。

基于 LSH 的搜索策略在 elasticsearch 里大致执行如下:

1、使用 index mapping 指定的参数对输入的 vector 进行 hash;
2、使用 hash 出来的值去构造对应的 query 语句并运行起来,去找到其他已经入库的并进行了相同参数的 hash 的 vector,查询方法是使用 Lucene 的 TermInSetQuery 的方法,这里是用 hash 查 hash,然后通过查到的 hash 反查拿到 vector;
3、查询获得一批跟输入的 hash 的最为接近的 vector,并对这批 vector 进行相似性计算,并以分数的顺序的形式返回。

{
    "feature":{
        "path_match":"feature",
        "mapping":{
            "store":true,
            "type":"elastiknn_dense_float_vector",
            "elastiknn":{
                "dims":256,
                "model":"lsh",
                "similarity":"cosine",
                "L":99,
                "k":1
            }
        }
    }
}

EXACT

第二种:elastiknn_dense_float_vector + exact + cosine

没啥好说的,就是暴力计算所有向量。

{
    "feature":{
        "path_match":"feature",
        "mapping":{
            "store":true,
            "type":"elastiknn_dense_float_vector",
            "elastiknn":{
                "dims":256
            }
        }
    }
}

补充说明

数据采集

主要使用 elasticdump 进行数据采集,目标是让线上的 es 的存有特征的 index 倒到一个测试部署的 es 里,这里选择了 body_features 这个库,特征维度是 256。

elasticdump --input=http://172.26.1.66:9200/body_features --output=http://192.168.1.232:9200/body_features_knn

数据样例有两种情况

数据样例的采集,都会通过这个工具来实现,工具的执行方式是串行,每次写100个

压测样例

两种 mapping,4 种数据样例,一共 8 种压测样例。
压测方式有6种,分别是:

创建 index

2021-11-10T07:56:12.png

我们看到 lsh 会比 exact 的数据体积大些,但也仅仅只是多一丢一丢, 可以忽略不计。
还有,490100 比 500000 差9900条,这里假设数据量为 50w,虽然不够严谨,但是足够作为例子。

开始压测

压测的方法,是使用同一组 feature 请求进行搜索,这里不用担心数据是否会被缓存从而影响计算;压测工具是 autocannon。

features_exact_1w

10并发+持续10秒
2021-11-10T08:44:50.png

100并发+持续10秒
2021-11-10T08:45:03.png

1000并发+持续10秒
2021-11-10T08:45:11.png

10并发+持续30秒
2021-11-10T08:45:18.png

100并发+持续30秒
2021-11-10T08:45:23.png

1000并发+持续30秒
2021-11-10T08:45:30.png

features_lsh_1w

10并发+持续10秒
2021-11-10T08:45:37.png

100并发+持续10秒
2021-11-10T08:45:43.png

1000并发+持续10秒
2021-11-10T08:45:50.png

10并发+持续30秒
2021-11-10T08:45:57.png

100并发+持续30秒
2021-11-10T08:46:04.png

1000并发+持续30秒
2021-11-10T08:46:10.png

features_exact_10w

10并发+持续10秒
2021-11-10T08:46:17.png

100并发+持续10秒
2021-11-10T08:46:23.png

10并发+持续30秒
2021-11-10T08:47:04.png

100并发+持续30秒
2021-11-10T08:47:10.png

features_lsh_10w

10并发+持续10秒
2021-11-10T08:47:34.png

100并发+持续10秒
2021-11-10T08:47:39.png

10并发+持续30秒
2021-11-10T08:47:45.png

100并发+持续30秒
2021-11-10T08:47:50.png

features_exact_50w

10并发+持续10秒
2021-11-10T08:49:30.png

100并发+持续10秒
2021-11-10T08:49:35.png

features_lsh_50w

10并发+持续10秒
2021-11-10T08:49:41.png

100并发+持续10秒
2021-11-10T08:49:47.png

结论

需要重申一次,我们的特征数据是256维,lsh 是近似的,exact 是精确的,几乎没有做什么优化,使用默认配置。

从整体上看

1、并发越高,耗时越高,并发越低,耗时越少;
2、lsh 和 exact 在 1w 量级,平均耗时相差不大,在5~10ms内,但是在 10w 50w 量级下,lsh 比 exact 快 40~50%,耗时差距更明显,其中10w量级,耗时在50~100ms内;
3、高并发并不会带来更多的处理量。单位时间下处理一样数量的请求,低并发的处理量可能会比高并发的高,这里其实还会涉及到 es 本身的线程池的调优,有可能通过调优实现高并发;
4、10秒和30秒的区别,没看到有价值的地方,只需要看10秒的统计即可。

从局部上看

1、 我们先来看 body_features_exact_1w 下的 10并发+持续10秒, 100并发+持续10秒,1000并发+持续10秒的三组报告,分别得到 10k 12k 13k requests,说明在 10并发+持续10秒 这个输入指标下,继续增大并发并不会得到更多更明显的处理量,说明我们后续的开发应该使用小步快跑(低并发)的方式去开发,用同样的角度去看 lsh 的,一样得到相同的结论;
2、在1w量级和10并发+持续10秒 ,无论 lsh 和 exact 处理耗时都能做到很低,平均值分别是5ms和10ms,这个耗时是包含了网络io的耗时,在一些少特征数的业务场景下,这个耗时都是非常理想的;
3、在10w量级,lsh 平均耗时61,exact 平均耗时102,lsh 处理量几乎是 exact 的 2 倍,特征集在10w量级用lsh 更好;
4、body_features_lsh_50w 和 10并发+持续10秒 ,在50w量级,平均耗时282ms, p97 也有342,在没有做节点级的调优下, 纯cpu计算的场景,这个耗时其实是相当理想的。

建议

1、特征向量数在0~5w内,使用 lsh 或者 exact 都可以,取决于业务要求,如果没要求则建议 lsh,因为 lsh 还是会比 exact 快点的,天下武功唯快不破;
2、特征向量数大于5w,则建议使用 lsh,能带来更明显的小耗时。

疑虑

1、lsh 会不会导致漏数据?经过查资料 lsh 召回率只有85%,没有 hnsw 95% 高,如果是大数据量的特征集,选择 hnsw 更好;
2、如果要做100w+的特征集,该方法还是不是个好方法?我觉得还是,因为很多优化工作是没有展开的,相信做好优化,耗时等指标会符合要求。

Responses