高效压缩位图在推荐系统中的应用

一、背景

用户在浏览游戏中心/应用商店的某些模块内容时，会进行一系列滑屏操作并多次请求游戏推荐业务来进行游戏推荐展示，这段时间我们称之为一个用户session。

一个session内用户一般会进行十几次滑屏操作，每次滑屏操作都会请求推荐业务，所以在这个session内游戏推荐需要对推荐过的游戏进行去重，避免出现重复推荐同一款游戏影响用户体验。

精简后的业务流程如下所示：用户进行滑屏操作时会触发一次推荐请求，此时客户端会将上一页的黑名单游戏通过游戏中心服务端透传给推荐系统，推荐系统将一个session内每次请求的黑名单信息都累加存储到Redis中作为一个总的过滤集合，在召回打分时就会过滤掉这些黑名单游戏。

以实际业务场景为例，用户浏览某模块的session时长一般不会超过10分钟，模块每页显示的游戏为20个左右，假设每个用户session内会进行15次的滑屏操作，那么一个session就需要存储300 个黑名单游戏的appId（整数型Id）。因此该业务场景就不适合持久化存储，业务问题就可以归结为如何使用一个合适的数据结构来缓存一系列整数集合以达到节省内存开销的目的。

二、技术选型分析

接下来我们随机选取300个游戏的appId（[2945340, ……. , 2793501,3056389]）作为集合来分别实验分析intset，bloom filter，RoaringBitMap对存储效果的影响。

2.1 intset

实验结果表明用 intset保存300个游戏集合，得到占用的空间大小为1.23KB。这是因为对于300个整数型appId游戏，每个appId用4Byte的int32就能表示。根据intset的数据结构，其开销仅为encoding + length + 400 个int所占的空间。

typedef struct intset{
    unit32_t encoding;          // 编码类型
    unit32_t length;            // 元素个数
    int8_t contents[];          // 元素存储
} intset;

2.2 bloom filter

布隆过滤器底层使用的是bitmap，bitmap本身就是一个数组可以存储整形数字，arr[N] = 1 表示数组里存储了N这个数字。

bloom filter会先用hash函数对数据进行计算，映射到bitmap相应的位置，为减少碰撞（不同的数据可能会有相同的hash值），会使用多个hash算子对同一份数据进行多次映射。在业务中我们假设线上有一万个游戏，同时业务场景不允许出现误判，那么误差就必须控制在10^-5，通过bloom filter的计算工具https://hur.st/bloomfilter/?n=10000&p=1.0E-5&m=&k=得出，需要17个hash算子，且bitmap空间要达到29KB才能满足业务需求，显然这样巨大的开销并不是我们想要的结果。

2.3 RoaringBitMap

RoaringBitMap和bloom filter本质上都是使用bitmap进行存储。但bloom filter 使用的是多个hash函数对存储数据进行映射存储，如果两个游戏appId经过hash映射后得出的数据一致，则判定两者重复，这中间有一定的误判率，所以为满足在该业务场景其空间开销会非常的大。而RoaringBitMap是直接将元数据进行存储压缩，其准确率是100%的。

实验结果表明：RoaringBitMap对300个游戏集合的开销仅为0.5KB，比直接用intset（1.23KB）还小，是该业务场景下的首选。所以下文我们来着重分析下RoaringBitMap为什么为如此高效。

2.3.1 数据结构

每个RoaringBitMap中都包含一个RoaringArray，存储了全部的数据，其结构如下:

short[] keys;
Container[] values;
int sizer;

它的思路是将32位无符号整数按照高16位分桶（container），并做为key存储到short[] keys中，最多能存储2^16 = 65536 个桶（container）。存储数据时按照数据的高16位找到container，再将低16位放入container中，也就是Container[] values。size则表示了当前keys和values中有效数据的数量。为了方便理解，下图展示了三个container：

图片引用自： https://arxiv.org

• 高16位为0000H的container，存储有前1000个62的倍数。
• 高16位为0001H的container，存储有[2^16, 2^16+100)区间内的100个数。
• 高16位为0002H的container，存储有[2×2^16, 3×2^16)区间内的所有偶数，共215个。

当然该数据结构的细节不是我们关注的重点，有兴趣的同学可以去查阅相关资料学习。现在我们来分析一下在推荐业务中RoaringBitMap是如何帮助我们节省开销的。RoaringBitMap中的container分为ArrayContainer，BitmapContainer 和 RunContainer 但其压缩方式主要分为两种，姑且就称为可变长度压缩和固定长度压缩, 这两种方式在不同的场景下有不同的应用。

2.3.2 压缩方式与思考

假设两串数字集合 [112,113,114,115,116,117,118 ], [112, 115, 116, 117, 120, 121]使用可变长度压缩可以记录为：

• 112,1,1,1,1,1,1 使用的字节大小为 7bit + 6bit = 13bit, 压缩率为 (7 * 32 bit) / 13 bit = 17.23
• 112,3,1,1,3,1 使用的字节大小为 7bit + 2bit + 1bit + 1bit + 2bit + 1bit = 14bit, 压缩率为（6 * 32bit）/ 14 = 13.7

使用固定长度压缩可以记录为：

• 112, 6，使用的字节大小为 7bit + 3bit = 10bit , 压缩率为（7 * 32bit）/ 10bit = 22.4
• 112, 115, 3, 120,2 使用的字节大小为 7bit + 7bit + 2bit + 7bit + 2bit = 25bit，压缩率为（6 * 32bit）/ 25 = 7.68

显然稀疏排列对于两种压缩方式都有影响，可变长度压缩适合于稀疏分布的数字集合，固定长度压缩合于连续分布的数字集合。但在过于稀疏的情况下，即使是可变长度压缩方式也不好使。

假设集合存储范围是Interger.MaxValue，现在要存储数字集合是[ 2^3 – 1 , 2^9 – 1 , 2^15 -1 , 2^25 – 1 , 2^25 , 2^30 -1 ]这6个数。使用可变长压缩方式表示为： 2^3 -1 , 2^9 – 2^3 , 2^15 – 2^9 , 2^25 – 2^15 , 1 , 2^30 – 2^ 15 使用字节大小 3bit + 9bit +15bit + 25bit + 1bit + 30bit = 83bit, 压缩率为 6 * 32 bit / 83 = 2.3。

这个压缩率和固定长度压缩方式无异，均为极限情况下对低位整数进行压缩，无法利用偏移量压缩来提高压缩效率。

2.3.3 业务分析

更为极端的情下对于数据集合[ 2^25 – 1 , 2^26 – 1 , 2^27 – 1 , 2^28 – 1 , 2^29 – 1 , 2^30 – 1 ], RoaringBitMap压缩后只能做到 25 + 26 + 27 + 28 + 29 + 30 = 165bit, 压缩率为 6 * 32 / 165 = 1.16 就更别说加上组件数据结构，位数对齐，结构体消耗，指针大小等开销了。在特别稀疏的情况下，用RoaringBitMap效果可能还更差。

但对于游戏业务来说游戏总量就10000多款，其标识appId一般都是自增主键，随机性很小，分布不会特别稀疏，理论上是可以对数据有个很好的压缩。同时使用RoaringBitMap存储Redis本身采用的bit，不太受Redis本身数据结构的影响，能省下不少额外的空间。

三、总结

在文章中我们探讨了在过滤去重的业务中，使用Redis存储的情况下，利用intset，bloom filter 和 RoaringBitMap这三种数据结构保存整数型集合的开销。

其中传统的bloom filter 方式由于对准确率的要求以及短id映射空间节省有限的不足，使得该结构在游戏推荐场景中反而增加了存储开销，不适合在该业务场景下存储数据。而intset结构虽然能满足业务需求，但其使用的空间复杂度并不是最优的，还有优化的空间。

最终我们选择了RoaringBitMap这个结构进行存储，这是因为游戏推荐业务保存的过滤集合中，游戏id在大趋势上是自增整数型的，且排列不是十分稀疏，利用RoaringBitMap的压缩特性能很好的节省空间开销。我们随机抽选300个游戏的id集合进行测试，结合表格可以看到，相比于intset结构使用的1.23KB空间，RoaringBitMap仅使用0.5KB的大小，压缩率为2.4。

对于Redis这种基于内存的数据库来说，使用适当的数据结构提升存储效率其收益是巨大的：不仅大大节约了硬件成本，同时减少了fork阻塞线程与单次调用的时延，对系统性能的提升是十分显著的，因此在该场景下使用RoaringBitMap是十分合适的。