共计 3741 个字符，预计需要花费 10 分钟才能阅读完成。
作者：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… 得出，须要 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 是非常适合的。
