巧用RoaringBitMap处理海量数据内存diff问题 ｜ 得物技术
背景
目前，在商品圈选投场景，每个标签id都会根据规则/指标绑定一定数据量的商品集，在圈选规则条件变动或者定时任务触发时会进行商品集的刷新，新增符合规则的商品，删除不符合规则的商品。
但是由于商品集下的spu数量大部分都在数十万，多的能达到上百万，如果直接将刷新前后各十万甚至百万的spu全量放到内存中互相做diff，再对diff得到的差集做增删，当同一时间刷新的标签数量过多时，内存就很容易溢出，造成整个服务宕机。
同时目前底层存储商品集的数据库为Hbase，因此在标签侧对于商品集的刷新场景目前都是采取全增全删的策略，即把刷新后的商品集先全量保存一次(利用Hbase 保存的幂等性，同一个rowkey的数据重复保存会进行覆盖，而不用在保存前做额外的数据是否存在的判断)，并更新数据的modity_time=now()，然后再从Hbase中分批scan遍历商品集，找到modity_time<now的再进行删除，以此完成一次标签的刷新任务。
往往一个商品集在刷新前后真正变化的spu量并不大，通过取数分析得知变化的不会超过商品集数量的10%。而我们目前采用的这种全增全删的策略，每次刷新后都会有大量已有数据的重复插入，不仅延长了刷新的速度，也增加底层储存的压力，同时由于选投平台里有标签的指标，标签的变动需要推送变化的spu给选投平台进行重新圈品，同时spu es 中也存有标签的数据用于后台展示，所以当前全增全删的策略，尤其是大量已有数据的重复插入，都会同步到选投平台和spu es侧，对他们造成大量的性能浪费和处理成本，改造迫在眉睫。
优化方案
前面提到，由于传统的java Set结构在数据量较大的情况，占用内存较多，导致无法将前后海量商品集的数据全部存到内存中去做运算。
那么有没有一个数据结构可以在存海量数据时还能保持较低的内存占用，支持去重，还支持交集，差集等各种运算呢?
Bitmap完美满足要求。
Bitmap是通过bit数组来存储数据的数据结构，是一串连续的二进制数组（0和1），可以通过偏移量（offset）定位元素。Bitmap通过最小的单位bit来进行0|1的设置，表示某个元素的值或者状态，时间复杂度为O(1)。
同时由于采用了Bit为单位来存储数据，因此在存储空间方面，可以大大节省。例如储存500W数据仅需5000000/8/1024/1024=0.5M内存。
因此准备使用Bitmap结构来存储刷新前后的商品集，然后分别对新老Bitmap互相求差集得到，最终对差集进行add和delete操作即可。
方案可行性分析
以标签场景为例。
标签可以绑定选投平台，标签系统会把选投平台圈选的所有商品集都打上标，此刻标签下的商品集记为oldSset(X+Y)。
选投平台刷新后，会重新圈选出一批满足选投平台指标的商品集，此时选投平台下的商品集记为newSet(Y+Z) 。
此时标签系统需要给newSet(Y+Z)打标，同时从oldSet(X+Y)删除不在本次圈选范围内的商品(X)。
标签商品集底层储存是Hbase，对于已存在数据的插入，只要rowkey(标签id+spuId)不变， Hbase就会进行覆盖，保存最新时间戳的数据，可以理解为老Y已经被新Y覆盖(老Y数据=新Y数据,只是时间戳会不一样)，所以老全增全删的方案， 删除量级是X，而不是X+Y。
如上图所示，每次刷新后，其实只需要对X进行删除和对Z进行新增。
相比于老全增全删逻辑，Bitmap diff新方案查询和删除量级不变，新增量级和对选投平台，spu es 的通知量级，都减少了Y。
同时由于Bitmap本身储存数据的方式，储存500W的spu数据集对内存的占用也才在0.5M,完成不用担心内存溢出风险。
因此采用Bitmap来储存刷新前后的全量商品数据，并在内存中做diff是一个理论可行的方案。
技术选型
既然我们选定了使用Bitmap作为新方案的储存，那么应该选取哪种Bitmap实现呢?
众所周知，Bitmap的实现有很多，例如java原生的BitSet，guava的EWAHCompressedBitmap，第三方的RoaingBitmap，redis Bitmap等等，由于redis的Bitmap主要做远程储存不适合当前内存diff场景，因此排除。
本次主要对比BitSet、EWAHCompressedBitmap、RoaingBitmap三种实现在各种数据稀疏度下的内存占用和cpu占用，以选出最满足当前场景的实现。
内存占用测试
通过往Bitmap中添加1、N+1、2N+1.....5000000数据，其中N为数据的步长(稀疏度) 来计算各个Bitmap在不同稀疏度下(N)的内存占用情况。
通过下图可以看出，除了在稀疏度为1时，EWAHCompressedBitmap内存占用最低以外，其余稀疏度下的内存占用：RoaingBitmap<EWAHCompressedBitmap<BitSet。
cpu耗时测试
往各个Bitmap中添加1、N+1、2N+1.....5000000数据，其中N为数据的步长(稀疏度)，然后与有5000000满数据的Bitmap分别求2000次差集并取2000次中的最大耗时，得到在每个稀疏度下每种Bitmap的耗时情况。
通过下图可以看出，各个稀疏度下的cpu耗时：RoaingBitmap≈EWAHCompressedBitmap<BitSet.
选型最终结论
从内存占用，cpu耗时测试，实际场景下数据稀疏度综合考虑，RoaingBitmap效果最优，因此选用RoaingBitmap作为新方案的Bitmap实现。
RoaingBitmap介绍及原理
RoaingBitmap储存原理
RoaingBitmap会将32 bit unsigned int 类型数据 划分为 2^16 个大Container（即使用数据的前16位二进制作为Container的编号），每个大Container有一个小Container 来存放一个数值的低16位。
在存储和查询数值时，将数值 k 划分为高 16 位和低 16 位，取高 16 位值找到对应的Container，然后在将低 16 位值存放在相应的 Container 中。
这样说可能比较抽象不易理解，下面我通过一个例子来说明。
比如我们要将31这个数放进RoarigBitmap中，它的16进制为：0000 001F，前16位为0000，后16为001F。所以我们先需要根据前16位的值：0，找到它对应的的Container编号为0，然后根据后16位的值：31，确定这个值应该放到Container中的哪一个位置，如下图所示。
需要注意大Container里面的各个小Container是在需要的时候才会申请开辟的，并不是一开始就全部申请的，而且大Container中小Container都是按序号有序排列在大Container里面的。
四种container介绍
为了在各种场景和稀疏度下都始终保持有良好的内存占用和性能表现，RoaingBitmap 特意设计了4种小Container，分别为ArrayContainer(数组容器)，BitmapContainer(位图容器)，Runcontainer(行程步长容器)，Sharedcontainer(共享容器)，下面我会对每个ArrayContainer的使用场景和原理进行介绍。
Arraycontiner
在创建一个新container时，如果只插入一个元素，RBM（RoaingBitmap）默认会用ArrayContainer来存储。当ArrayContainer（其中每一个元素的类型为 short 占两个字节，且里面的元素都是按从小到大的顺序排列的）的容量超过4096（这里是指4096个short 即8k）后，会自动转成BitmapContainer(这个所占空间始终都是8k)存储。4096这个阈值很聪明，低于它时ArrayContainer比较省空间，高于它时BitmapContainer比较省空间。也就是说ArrayContainer存储稀疏数据，BitmapContainer存储稠密数据，可以最大限度地避免内存浪费，如下图所示。
BitmapContainer
这个容器其实就是我们所说的位图，只不过这里位图的位数为65536个，也就是2^16个bit，计算下来起所占内存就是8kb。然后每一位用0，1表示这个数不存在或者存在，如下图所示：
Runcontainer
这是一种利用步长来压缩空间的方法
我们举个例子：比如连续的整数序列 11， 12， 13， 14， 15， 27， 28， 29 会被 压缩为两个二元组 11， 4， 27， 2 表示：11后面紧跟着4个连续递增的值，27后面跟着2个连续递增的值，那么原先16个字节的空间，现在只需要8个字节，是不是节省了很多空间呢。不过这种容器不常用，所以在使用的时候需要我们自行调用相关的转换函数来判断是不是需要将arraycontiner，或BitmapContainer转换为Runcontainer。
Sharedcontainer
这种容器它本身是不存储数据的，只是用它来指向ArrayContainer，BitmapContainer或Runcontainer，就好比指针的作用一样，这个指针可以被多个对象拥有，但是指针所指针的实质东西是被这多个对象所共享的。在我们进行RoaingBitmap之间的拷贝的时候，有时并不需要将一个container拷贝多份，那么我们就可以使用Sharedcontainer来指向实际的container，然后把Sharedcontainer赋给多个RoaingBitmap对象持有，这个RoaingBitmap对象就可以根据Sharedcontainer找到真正存储数据的container，这可以省去不必要的空间浪费。
这些container之间的关系可以用下面这幅图来表示：
其中的roaring_array是RoaingBitmap对象，而途中的Sharedcontainer则表示被多个roaring_array里面的小Container共享。
RoaingBitmap优势
内存
Bitmap比较适用于数据分布比较稠密的存储场景中，对于原始的Bitmap来说，若要存储一个uint32类型数据，这就需要2 ^ 32长度的bit数组，通过计算可以发现(2 ^ 32 / 8 bytes = 512MB)，一个普通的Bitmap需要耗费512MB的存储空间。如果我们只存储几个数据的话依然需要占用512M的话，就有些浪费空间了，因此我们可以采用对位图进行压缩的RoaingBitmap，以此减少内存和提高效率。
性能
RoaingBitmap除了比Bitmap占用内存少之外，其并集和交集操作的速度也要比Bitmap的快。原因归结为以下几点：
计算上的优化
对于RoaingBitmap本质上是将大块的Bitmap分成各个小块，其中每个小块在需要存储数据的时候才会存在。所以当进行交集或并集运算的时候，RoaingBitmap只需要去计算存在的一些块而不需要像Bitmap那样对整个大的块进行计算。如果块内非常稀疏，那么只需要对这些小整数列表进行集合的 AND、OR 运算，这样的话计算量还能继续减轻。这里既不是用空间换时间，也没有用时间换空间，而是用逻辑的复杂度同时换取了空间和时间。
同时在RoaingBitmap中32位长的数据，被分割成高 16 位和低 16 位，高 16 位表示块偏移，低16位表示块内位置，单个块可以表达 64k 的位长，也就是 8K 字节。这样可以保证单个块都可以全部放入 L1 Cache，可以显著提升性能。
程序逻辑上的优化
RoaingBitmap维护了排好序的一级索引，以及有序的ArrayContainer当进行交集操作的时候，只需要根据一级索引中对应的值来获取需要合并的容器，而不需要合并的容器则不需要对其进行操作直接过滤掉。
当进行合并的ArrayContainer中数据个数相差过大的时候采用基于二分查找的方法对ArrayContainer求交集，避免不必要的线性合并花费的时间开销。
RoaingBitmap在做并集的时候同样根据一级索引只对相同的索引的容器进行合并操作，而索引不同的直接添加到新的RoaingBitmap上即可，不需要遍历容器。
RoaingBitmap在合并容器的时候会先预测结果，生成对应的容器，避免不必要的容器转换操作
show me the code
代码逻辑其实相对简单，主要是构建新老Bitmap，互相求差集后对本次新增的spu进行新增，对本次需要删除的spu进行删除操作。
优化效果
刷新速度
统计全量标签在新老逻辑下的耗时,发现提升比例大部分都集中在40%-60%区间，去掉最高及最低值
得出最终结论为平均提升比例在52.42%
写入量级以及对其他场景影响
统计全量标签在新老逻辑下的写量级,发现提升比例大部分都集中在85%-99%区间，去掉最高及最低值
得出最终结论为平均提升比例在86.98%
总结
由于java的Set结构在大数据量下的内存占用很高，因此在圈选商品集的刷新场景无法直接在内存中用set去全量储存刷新前后的商品集并做差集运算。
因此考虑到了使用Bitmap这样一种通过bit数组来存储数据的数据结构，它采用了Bit为单位来存储数据，因此在存储空间方面，可以大大节省。
对比了业界了各种Bitmap实现，结合当前场景，最终采用了RoaingBitmap来作为最终的实现。
RoaingBitmap属于是位图的一个进化，即压缩位图，不过在RoaingBitmap中不只包含Bitmap这一种数据结构，而是包涵了多种存储的方式(contianer)，同时通过计算及逻辑上的优化，保证了在各个稀疏度下相比于传统的Bitmap都能保持较低的内存占用和对比速度。
最终上线后优化效果也是比较不错，刷新速度提升在52%左右，写入量级平均降低87%，有效的提升了刷新速度，以及对储存DB及其他场景域的压力。
同时本方案也适用其他类似的场景，比如选投平台侧的刷新，绑定选投平台的主题集下的商品刷新等。
参考文档：
RoaingBitmap 官方github地址
使用Apache ECharts完成优化效果图绘制
*文/Creed
要是觉得文章对你有帮助的话，欢迎评论转发点赞～
得物技术公众号后台 回复「沙龙」进群，不迷路！
报名方式：
云原生专场：关注 InfoQ视频号 7月9日13:50开播
数据库专场：关注51CTO技术栈视频号 7月9日 13:50开播
或者 得物Tech视频号预约：