作者：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是非常适合的。