1.背景用户在游戏中心/应用商店浏览某些模块时，会进行一系列的滑动操作，多次请求游戏推荐业务进行游戏推荐展示，期间这次我们称之为用户会话。在一个session中，一个用户一般会进行十几次的屏幕滑动操作，每一次滑动操作都会请求一次推荐服务。因此本环节的游戏推荐需要对推荐的游戏进行去重，避免相同游戏的重复推荐影响用户。经验。精简后的业务流程如下：当用户滑动屏幕时，会触发推荐请求。此时客户端会通过游戏中心服务器透传之前页面的黑名单游戏给推荐系统，推荐系统会发送一个session对每个请求的黑名单信息进行累积存储在Redis中作为通用过滤设置好，这些黑名单的游戏在召回和计分的时候会被过滤掉。以实际业务场景为例，用户浏览某个模块的session时长一般不会超过10分钟，该模块每个页面展示的游戏数量在20个左右。假设每个用户session会执行15个刷屏操作，那么一个session需要存储300个黑名单游戏的appId（整型Id）。因此，这种业务场景不适合持久化存储，业务问题可以归结为如何使用合适的数据结构来缓存一系列整数集，以节省内存开销。2.技术选型分析接下来，我们随机选取了300个游戏appIds（[2945340,.......,2793501,3056389]）作为一个集合来分析intset、bloomfilter、RoaringBitMap对存储效果的影响。2.1intset实验结果表明，使用intset保存300个游戏集，占用空间大小为1.23KB。这是因为对于300个整型appId游戏，每个appId可以用4Byteint32来表示。按照intset的数据结构，它的开销只是encoding占用的空间+length+400个int。typedefstructintset{unit32_t编码；//编码类型unit32_tlength;//元素数量int8_tcontents[];//元素存储}intset;2.2Bloomfilterbloomfilter底层是位图，位图本身是一个数组存储整数，arr[N]=1表示数组中存储的是数字N。布隆过滤器会先使用哈希函数对数据进行计算，并将其映射到位图的相应位置。为了减少冲突（不同的数据可能有相同的哈希值），会使用多个哈希算子对同一个数据进行多次映射。在业务中，我们假设有10000个游戏在线，同时业务场景不允许误判，那么误差必须控制在10^-5，通过bloomfilter计算工具https://hur.st/布隆过滤器/？n=10000&p=1.0E-5&m=&k=可以得出需要17个哈希算子，位图空间需要达到29KB才能满足业务需求。显然如此巨大的开销并不是我们想要的结果。2.3RoaringBitMapRoaringBitMap和bloomfilter本质上都是使用位图进行存储。但是，布隆过滤器使用多个哈希函数来映射和存储存储的数据。如果两个游戏appId哈希映射得到的数据是一致的，则确定两者重复。有一定的误判率。在这种业务场景下，空间开销会非常大。RoaringBitMap直接存储和压缩元数据，准确率100%。实验结果表明，300个游戏集的RoaringBitMap开销仅为0.5KB，比直接使用intset（1.23KB）要小，是该业务场景下的首选。那么下面我们就着重分析为什么RoaringBitMap这么高效。2.3.1数据结构每个RoaringBitMap包含一个RoaringArray，它存储所有的数据。它的结构如下：short[]keys;容器[]值；分成桶（容器）并将它们作为键存储在short[]键中。最多可以存储2^16=65536个桶（容器）。存储数据时，根据数据的高16位找到容器，然后将低16位放入容器，即Container[]值。size指示当前键和值中有效数据的数量。为了便于理解，下图展示了三个容器：图片引用自：https://arxiv.org高16位为00??00H的容器存放62的前1000个倍数，高16位为00??01H的容器在[2^16,2^16+100)区间存储100个数。高16位为00??02H的容器存放了[2×2^16,3×2^16)区间内的所有偶数，共215个。当然数据结构的细节不是我们关注的重点.有兴趣的同学可以参考相关资料进行学习。下面我们来分析一下RoaringBitMap是如何帮助我们在推荐业务中节省成本的。RoaringBitMap中的容器分为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*32bit)/13bit=17.23112,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.4112,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*32bit/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的效果可能更差。但是对于游戏业务来说，游戏总数在1万以上，appId一般是自增主键。随机性很小，分布不会特别稀疏。理论上，可以很好地压缩数据。同时使用RoaringBitMap来存储Redis自身使用的bits，不受Redis自身数据结构的影响，可以节省大量的额外空间。3.小结在文章中，我们讨论了在过滤去重业务中使用Redis存储的情况下，使用intset、bloomfilter和RoaringBitMap三种数据结构保存整数集的开销。其中，传统的bloomfilter方式由于对准确性的要求和shortidmapping节省空间有限，不适合该业务场景下的数据存储，使得该结构在游戏推荐场景下增加了存储开销。虽然intset结构可以满足业务需求，但是其使用的空间复杂度并不是最优的，还有优化的空间。最终我们选择了RoaringBitMap这种结构进行存储。这是因为在游戏推荐业务保存的过滤集合中，游戏id往往是一个自增整数，排列不是很稀疏。RoaringBitMap的压缩特性非常好。节省空间开销。我们随机抽取了300个游戏ID集进行测试。根据表格可以看出，相比于intset结构使用的1.23KB空间，RoaringBitMap只使用了0.5KB，压缩率为2.4。对于Redis这样基于内存的数据库来说，使用合适的数据结构来提高存储效率的好处是巨大的：不仅可以大大节省硬件成本，还可以减少fork阻塞线程和单次调用的延迟，影响系统性能。提升非常显着，所以在这种场景下使用RoaringBitMap是非常合适的。
