巧用 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，可以显著提升性能。

• 程序逻辑上的优化

1. RoaingBitmap 维护了排好序的一级索引，以及有序的 ArrayContainer 当进行交集操作的时候，只需要根据一级索引中对应的值来获取需要合并的容器，而不需要合并的容器则不需要对其进行操作直接过滤掉。
   

2. 当进行合并的 ArrayContainer 中数据个数相差过大的时候采用基于二分查找的方法对 ArrayContainer 求交集，避免不必要的线性合并花费的时间开销。
   

3. RoaingBitmap 在做并集的时候同样根据一级索引只对相同的索引的容器进行合并操作，而索引不同的直接添加到新的 RoaingBitmap 上即可，不需要遍历容器。
   

4. 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 及其他场景域的压力。

同时本方案也适用其他类似的场景，比如选投平台侧的刷新，绑定选投平台的主题集下的商品刷新等。 

参考文档：

1. RoaingBitmap 官方 github 地址

2. 使用 Apache ECharts 完成优化效果图绘制

*文/Creed

关注得物技术 @得物技术公众号