上一篇文章《向量检索研究系列:本地向量检索(上)》介绍了如何加快向量相似度计算,但是一般的向量检索流程还包括对计算结果进行排序,以及有必要的话,在计算相似度之前可以对向量库中的向量进行过滤筛选(可选流程)。
本地向量检索在过滤和排序这两个方面也有进一步优化的空间,本文将介绍一下过滤方案和排序方案,个人知识有限,有想到更好的方案,希望可以一起交流改进。
本地向量计算是先把向量加载内存再计算,经过SIMD优化,计算速度快了,但是否还能进一步减少待计算相似度的向量集呢?
举个例子,一个用户向量本来要和向量集所有1000个向量进行相似度计算,是否可以在内存中通过对向量进行属性过滤,让用户向量只需要和向量集中500个向量进行相似度计算,这样可以加快总体的向量检索速度。
把广告通过模型转成向量后,向量应该关联广告的一些基本信息,广告检索条件是基于这些广告属性的,检索的时候可以根据检索条件在向量关联的广告信息中进行向量的筛选过滤。
广告信息和检索条件:
基于内存进行向量过滤暂时有想到如下三种方案:
方案一:内存对象
方案二:内存Bitmap
方案三:内存倒排索引
对这三种方案的QPS和资源占用情况进行了测试,测试结果如下图:
100万数据量以下方案三倒排索引的综合性能较优。
线上倒排索引需要考虑向量存储,实现方案分为离线刷入数据到Redis和在线从Redis读取数据到内存两个阶段。
在离线刷入数据到Redis阶段,有两种刷入方案:
方案一:如下图左侧所示,使用单个Hash存储,Hash的Key和Field存储条件,Value存储向量列表,同时对这些向量列表进行zip和base64压缩,浮点数的压缩率不高,仅2倍的压缩率。因为有些广告会在多个条件中出现,因此向量也会在多个Filed中出现,所以会存在向量冗余。
方案二:如下图右侧所示,使用一个Hash存储索引条件和广告ID列表,用多个单独的Key/value存储广告ID和对应的向量。若在Redis把这些单独的向量Key用一个Hash进行存储,则会出现大Key,请求这些大Key会导致某些节点压力过高,响应速度变慢,而使用单独的Key存储可以分散请求压力,提高后台服务请求Redis速度。
后台服务从Redis读取向量数据到内存,若10万个广告,使用方案二,存储向量需要内存270M,存储倒排索引3M。如果线上4个版本的向量进行AB实验,则内存总占用约1G。
Redis中多个单独的Key和Value读到内存后被存储在一个两层的Map中。
综合刷入数据和读取数据两个阶段,两种方案的优缺点如下:
方案一
方案二
因此方案二的Redis存储方式更有利于线上服务存储和更新广告向量。
向量过滤和相似度计算完之后,对结果取TopK的排序是否耗时?能否优化?
把Golang官方的排序算法(快排+堆排序+插入排序)时间和SIMD相似度计算时间进行对比,如下图:
可见,排序运算时间 > 内积运算时间,Golang默认的排序算法不满足需求。
向量是浮点数数组,内积计算的结果是浮点数,浮点数结果排序方案对比:
基数排序常用于整数排序,基于浮点数的基数排序也是本小节的重点,其改造核心思想如下:
浮点数基数排序的大致流程如下,可参考下图数字表标识顺序:
上面提到需要对浮点数的二进制进行分段,到底分多少段比较合适呢?
根据算法流程,得出时间复杂度公式:O(d*(n+2^(32/d))+n),其中d为浮点数分段个数,n为待排序数据量,括号中三个时间的相加,分别代表着分桶、确定元素相对位置、将原数组元素按顺序放到新数组中。32表示是32位的浮点数。
浮点数分段数 | 时间复杂度 | 待排序数量的合适取值范围 |
---|---|---|
1 | 2n+2^32 | n > 2,147,418,112 |
2 | 4n+2^17 | 32512 < n <= 2,147,418,112 |
4 | 8n+2^10 | 124 < n <= 32512 |
8 | 16n+2^7 | 4 < n <= 124 |
16 | 32n+2^6 | 1 =< n <= 4 |
32 | 64n+2^6 | 0 |
注意:这仅是理论上的估算值,对分段趋势的一个大概判断。同时也在代码层面对分2段、4段、8段进行了测试,其排序时间对比如下图:
可以看出,数据量越大,分段数越少排序越快,这和表格中的分段趋势估算一致。在5万数据量以下,分4段的效果最好,大于5万时,分2段的效果较好。
数据量非常大的时候是否能并行排序?
并行浮点数基数排序思想:
对于上面提到的几种排序算法进行了测试,同样也和SIMD内积运算时间进行对比,其测试结果如下:
上图中各排序方案性能:并行浮点数基数排序 > 浮点数基数排序 > Golang官方排序 > 堆排序
浮点数基数排序是Golang官方排序的4~5倍,并行浮点数基数排序是Golang官方排序的1~11倍。并行浮点数基数排序在数据量比较小的时候反而性能没有浮点数基数排序好,因为并行也存在性能损耗。
此时可以看出浮点数基数排序时间已经比SIMD相似度计算时间要短,已经满足我们的业务需求。
前面提到的排序都是对全量的数据进行排序,然后对结果取TopK,如果只对部分数据进行排序拿到TopK结果,不关心其它数据顺序,因此可以考虑对现有排序算法进行局部排序改造。
局部排序改造思想
方案一:冒泡排序
方案二:快速排序.
方案三:堆排序
对这几种局部排序在不同的数据量下取TopK(k=1000)进行了测试,结果如下:
算法\数据量 | 2000 | 1万 | 2万 | 5万 | 10万 | 100万 |
---|---|---|---|---|---|---|
冒泡排序TopK | 2.3μs | 12μs | 114μs | 205.087ms | 321.765ms | 2530ms |
快速排序TopK | 1403μs | 8505μs | 17135μs | 43.705ms | 88.822ms | 883ms |
堆排序TopK | 59μs | 246μs | 335μs | 0.436ms | 0.551ms | 1.364ms |
从表格中可以得出以下结论:
根据当前的业务数据量和数据增长趋势,选择堆排序的局部排序算法比较合适。
具体的业务数据不便展示,可以提供一些优化效果的对比数据。
(1)优化后通过模型召回广告的P99分位时延降低了一半。
(2)优化后本地向量检索P99时延降低50倍,平均时延降低180倍。
(3)优化后本地向量检索时延分布,99.2的检索时延都在1ms以内。
(1)优化后SIMD向量计算P99时延降低62倍,向量检索平均时延降低3倍。
实践过程中的经验不仅能优化当前业务,也能沉淀成可复制的方法论,应用到更广的业务场景,为更多的业务赋能。
经本地向量检索和计算优化后,召回和粗排服务的时延都有大幅度下降,随着QPS和广告数的增长,线上服务仍能轻松处理请求,可支撑更大规模的业务发展。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。