【向量检索研究系列】本地向量检索（下）

1 背景

上一篇文章《向量检索研究系列：本地向量检索（上）》介绍了如何加快向量相似度计算，但是一般的向量检索流程还包括对计算结果进行排序，以及有必要的话，在计算相似度之前可以对向量库中的向量进行过滤筛选（可选流程）。

本地向量检索在过滤和排序这两个方面也有进一步优化的空间，本文将介绍一下过滤方案和排序方案，个人知识有限，有想到更好的方案，希望可以一起交流改进。

2 过滤优化

本地向量计算是先把向量加载内存再计算，经过SIMD优化，计算速度快了，但是否还能进一步减少待计算相似度的向量集呢？

举个例子，一个用户向量本来要和向量集所有1000个向量进行相似度计算，是否可以在内存中通过对向量进行属性过滤，让用户向量只需要和向量集中500个向量进行相似度计算，这样可以加快总体的向量检索速度。

2.1 向量过滤

把广告通过模型转成向量后，向量应该关联广告的一些基本信息，广告检索条件是基于这些广告属性的，检索的时候可以根据检索条件在向量关联的广告信息中进行向量的筛选过滤。

广告信息和检索条件：

模型版本
冷启动或非冷启动创意
平台
模板
媒体

基于内存进行向量过滤暂时有想到如下三种方案：

方案一：内存对象

将广告信息存储为对象属性，向量也是其中一个属性，遍历广告对象，根据对象属性进行过滤。

方案二：内存Bitmap

每个广告属性的取值都生成一个Bitmap，广告ID为下标，如平台属性中为iOS平台和安卓平台各生成一个bitmap，检索条件对应着多个bitmap，对这些bitmap进行集合运算即可得到满足条件的广告。bitmap举例如下：

方案三：内存倒排索引

使用两个两层Map结构存储广告信息，第一个Map存储索引信息，一级Key :“模型版本_冷启动或非冷启动创意”，二级Key :“平台_模板_媒体”，值为广告ID列表。第二个Map存储向量信息，一级Key :“模型版本”，二级Key ：广告ID，值为广告向量。
检索时把检索条件在第一个Map中查询到满足检索条件的广告ID列表，再根据ID列表从第二个Map中取出对应向量列表。
大致结构可以参考2.2中向量存储方案图。

对这三种方案的QPS和资源占用情况进行了测试，测试结果如下图：

QPS：倒排索引 > Bitmap> 对象
CPU资源：Bitmap > 对象 > 倒排索引
时延（微秒级别，此处没有展示）：对象 > Bitmap > 倒排索引

100万数据量以下方案三倒排索引的综合性能较优。

2.2 向量存储

线上倒排索引需要考虑向量存储，实现方案分为离线刷入数据到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次数少
缺点：解析复杂、冗余向量内存占用大、不便增量更新

方案二

优点：解析简单、内存占用小、方便增量更新
缺点：查询Redis次数比方案一要多

因此方案二的Redis存储方式更有利于线上服务存储和更新广告向量。

3 排序优化

向量过滤和相似度计算完之后，对结果取TopK的排序是否耗时？能否优化？

3.1 全量排序

把Golang官方的排序算法（快排堆排序插入排序）时间和SIMD相似度计算时间进行对比，如下图：

可见，排序运算时间 > 内积运算时间，Golang默认的排序算法不满足需求。

向量是浮点数数组，内积计算的结果是浮点数，浮点数结果排序方案对比：

Go官方排序（快排堆排序插入排序）
堆排序（TopK问题常用算法）
浮点数基数排序（非比较型排序）
并行浮点数基数排序（分而治之）

基数排序常用于整数排序，基于浮点数的基数排序也是本小节的重点，其改造核心思想如下：

浮点数转二进制分段
多次分桶排序
处理负数

浮点数基数排序的大致流程如下，可参考下图数字表标识顺序：

将待排序的浮点数转成二进制，并分成多段。
将所有浮点数的第1段映射到桶里面，段的二进制位数决定了桶的大小，如8位二进制段对应的桶大小为256。
在桶里面确定浮点数的相对位置。
根据这个相对位置再进行浮点数第2段排序，重复步骤2~3。
直至所有分段都分桶完成并确定元素相对位置后已经得到浮点数的大致顺序，因为负数带符号位，最高位为1，负数会在数组的后面，需要将负数反转至数组头部即可得到最终排序好的浮点数数组。

上面提到需要对浮点数的二进制进行分段，到底分多少段比较合适呢？

根据算法流程，得出时间复杂度公式：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段的效果较好。

数据量非常大的时候是否能并行排序？

并行浮点数基数排序思想：

多协程分批排序后各取TopK
子结果汇总后再取TopK

对于上面提到的几种排序算法进行了测试，同样也和SIMD内积运算时间进行对比，其测试结果如下：

上图中各排序方案性能：并行浮点数基数排序 > 浮点数基数排序 > Golang官方排序 > 堆排序

浮点数基数排序是Golang官方排序的4~5倍，并行浮点数基数排序是Golang官方排序的1~11倍。并行浮点数基数排序在数据量比较小的时候反而性能没有浮点数基数排序好，因为并行也存在性能损耗。

此时可以看出浮点数基数排序时间已经比SIMD相似度计算时间要短，已经满足我们的业务需求。

3.2 局部排序

前面提到的排序都是对全量的数据进行排序，然后对结果取TopK，如果只对部分数据进行排序拿到TopK结果，不关心其它数据顺序，因此可以考虑对现有排序算法进行局部排序改造。

局部排序改造思想

方案一：冒泡排序

冒泡排序每次循环都会找到一个最大或最小的数值，循环TopK次就可以找到最终的TopK结果，退出算法即可。
时间复杂度：O(n*k)

方案二：快速排序.

利用二分法的思想，对于每次找到支点pivot时，判断pivot位置若大于TopK，则在pivot的左半部分继续递归，若pivot位置小于TopK，则在pivot的右半部分继续递归，直至pivot等于TopK退出递归，数组的前TopK个数就是最终的TopK结果。
时间复杂度：O(n*logn)

方案三：堆排序

取出数组的前TopK个数构建的一个小顶堆，然后遍历原数组第TopK之后所有的数，依次和堆顶进行比较，若比堆顶大，则插入堆中，进行堆调整。遍历完之后的堆即可TopK结果。
时间复杂度：O(n*logk)

对这几种局部排序在不同的数据量下取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