作者：vivo 互联网技术-Ke Jiachen

一、背景

用户在浏览游戏中心/应用商店的某些模块内容时，会进行一系列滑屏操作并多次请求游戏推荐业务来进行游戏推荐展示，这段时间我们称之为一个用户 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 是十分合适的。