海量数据处理利器 Roaring BitMap 原理介绍
作者：来自 vivo 互联网服务器团队- Zheng Rui
本文结合个人理解梳理了 BitMap 及 Roaring BitMap 的原理及使用，分别主要介绍了 Roaring BitMap 的存储方式及三种 container 类型及 Java 中 Roaring BitMap 相关 API 使用。
一、引言
在进行大数据开发时，我们可以使用布隆过滤器和 Redis 中的 HyperLogLog 来进行大数据的判重和数量统计，虽然这两种方法节省内存空间并且效率很高，但是也存在一些误差。如果需要 100%准确的话，我们可以使用 BitMap 来存储数据。
BitMap 位图索引数据结构被广泛地应用于数据存储和数据搜索中，但是对于存储较为分散的数据时，BitMap 会占用比较大的内存空间，因此我们更偏向于使用 Roaring BitMap 稀疏位图索引进行存储。同时，Roaring BitMap 广泛应用于数据库存储和大数据引擎中，例如 Hive，Spark，Doris，Kylin 等。
下文将分别介绍 BitMap 和 Roaring BitMap 的原理及其相关应用。
二、BitMap 原理
BitMap 的基本思想就是用 bit 位来标记某个元素对应的 value，而 key 就是这个元素。
例如，在下图中，是一个字节代表的 8 位，下标为 1,2,4,6 的 bit 位的值为 1，则该字节表示{1,2,4,6}这几个数。
在 Java 中，1 个 int 占用 4 个字节，如果用 int 来存储这四个数字的话，那么将需要 4 * 4 = 16 字节。
BitMap 可以用于快速排序，查找，及去重等操作。优点是占用内存少（相较于数组）和运算效率高，但是缺点也非常明显，无法存储重复的数据，并且在存储较为稀疏的数据时，浪费存储空间较多。
三、Roaring BitMap 原理
3.1 存储方式
为了解决 BitMap 存储较为稀疏数据时，浪费存储空间较多的问题，我们引入了稀疏位图索引 Roaring BitMap。Roaring BitMap 有较高的计算性能及压缩效率。下面简单介绍一下 Roaring BitMap 的基本原理。
Roaring BitMap 处理 int 型整数，将 32 位的 int 型整数分为高 16 位和低 16 位分别进行处理，高 16 位作为索引分片，而低 16 位用于存储实际数据。其中每个索引对应一个数据桶（bucket），那么一共可以包含 2^16 = 65536 个数据块。每个数据桶使用 container 容器来存储低 16 位的部分，每个数据桶最多存储 2^16 = 65536 个数据。
如上图所示，高 16 位作为索引查找具体的数据块，当前索引值为 0，低 16 位作为 value 进行存储。
Roaring BitMap 在进行数据存储时，会先根据高 16 位找到对应的索引 key（二分查找），低 16 位作为 key 对应的 value，先通过 key 检查对应的 container 容器，如果发现 container 不存在的话，就先创建一个 key 和对应的 container，否则直接将低 16 位存储到对应的 container 中。
Roaring BitMap 的精妙之处在于使用不同类型的 container，接下来将对其进行介绍。
3.2 container 类型
1.ArrayContainer
顾名思义，ArrayContainer 直接采用数组来存储低 16 位数据，没有采用任何数据压缩算法，适合存储比较稀疏的数据，在 Java 中，使用 short 数组来存储，并且占用的内存空间大小和数据量成线性关系。由于 short 为 2 字节，因此 n 个数据为 2n 字节。ArrayContainer 采用二分查找定位有序数组中的元素，因此时间复杂度为 O(logN)。ArrayContainer 的最大数据量为 4096, 4096 * 2b = 8kb。
2.BitMapContainer
BitMapContainer 采用 BitMap 的原理，就是一个没有经过压缩处理的普通 BitMap，适合存储比较稠密的数据，在 Java 中使用 Long 数组存储低 16 位数据，每一个 bit 位表示一个数字。由于每个 container 需要存储 2^16 = 65536 个数据，如果通过 BitMap 进行存储的话，需要使用 2^16 个 bit 进行存储，即 8kb 的数据空间。
可以从下图中看出 ArrayContainer 和 BitMapContainer 的内存空间使用关系，当数据量小于 4096 时，使用 ArrayContainer 比较合适，当数据量大于等于 4096 时，使用 BitMapContainer 更佳。
因为 BitMap 直接使用位运算，所以 BitMapContainer 的时间复杂度为 O(1)。
3.RunContainer
RunContainer 采用 Run-Length Encoding 行程长度编码进行压缩，适合存储大量连续数据。Java 中使用 short 数组进行存储。连续 bit 位程度越高的话越节省存储空间，最佳场景下（65536 个数据全为 1）只需要存储 4 字节。最差场景为所有数据都不连续，所有存储数据位置为奇数或者偶数，这种场景需要存储 128kb。由于采用二分查找算法定位元素，因此时间复杂度为 O(logN)。
行程长度编码即的原理是对连续出现的数字进行压缩，只记录初始数字和后续连续数量。
例如：[1,2,3,4,5,8,9,10]使用编码后的数据为[1,4,8,2]。
Java 里可以使用 runOptinize()方法来对比 RunContainer 和其他两个 Container 存储空间大小，如果使用 RunContainer 存储空间更佳则会进行转化。
根据上面三个 Container 类型我们可以得知如何进行选择：
Container 默认使用 ArrayContainer，当元素数量超过 4096 时，会由 ArrayContainer 转换 BitMapContainer。
当元素数量小于等于 4096 时，BitMapContainer 会逆向转换回 ArrayContainer。
正常增删元素不会使 Container 直接变成 RunContainer，而需要用户进行优化方法调用才会转换为最节省空间的 Container。
3.3 Roaring BitMap 相关源码
介绍完 Roaring BitMap 的三种 container 类型以后，让我们了解一下，Roaring BitMap 的相关源码。这里介绍一下 Java 中增加元素的源码实现。
Roaring BitMap 首先获取添加元素的高 16 位，然后再调用 getIndex 获取高 16 位对应的索引，如果索引大于 0，表示已经创建该索引对应的 container，故直接添加相应的元素低 16 位即可；否则的话，说明该索引对应的 container 还没有被创建，先创建对应的 ArrayContainer，再进行元素添加。值得一提的是，在 getIndex 方法中，使用了二分查找来获取索引值，所以时间复杂度为 O(logn)。
对于元素添加，三种 Container 提供了不同的实现方式，下面将分别介绍。
1. ArrayContainer
ArrayContainer 把添加元素分成两种场景，一种走二分查找，另外一种不走二分查找。
第一种场景：不走二分查找。
当基数为 0 或者值大于 container 中的最大值，可以直接添加，因为 content 数组是有序的，最后一个是最大值。
当基数大于等于默认最大值 4096 时，ArrayContainer 将转换为 BitMapContainer。如果基数大于 content 的数组长度的话，需要将 content 进行扩容。最后进行赋值即可。
第二种场景：走二分查找。
先通过二分查找找到对应的插入位置，如果返回 loc 大于等于 0，说明存在，直接返回即可，如果小于 0 才进行后续插入。后续操作同上，当基数大于等于默认最大值 4096 时，ArrayContainer 将转换为 BitMapContainer。如果基数大于 content 的数组长度的话，需要将 content 进行扩容。最后通过拷贝数组将元素插入到 content 数组中。
2. BitMapContainer
BitMap 数组为 BitMapContainer 的存储容器存放数据的内容，数据类型为 long，在这里我们只需要找到 x 在 BitMap 中的位置，并且把相应的 bit 位置 1 即可。x/64 就是找到对应 long 的旧值，1L<<x 就是把对应的 bit 位置为 1，再跟旧值进行或操作，就可以得到新值，再将这个新值存回到 bitmap 数组即可。<="" span="">
3. RunContainer
RunContainer 中的两个数据结构，nbrruns 表示有多少段行程，数据类型为 int，valueslength 数组表示所有的行程，数据类型为 short。
首先，使用二分查找+顺序查找在 valueslength 数组中查找元素 k 的插入位置 index。如果查找到的 index 结果大于等于 0 那就说明 k 是某个行程起始值，已经存在，直接返回。
-index-2 是为了指向前一个行程起始值的索引。
接下来是一些偏移量和索引值的判断，主要是为了确认 k 是否落在上一个行程里，或者外面，如果落在上一个行程里，则直接返回，否则需要新建一个行程或者就近与一个行程混合并且将行程长度加 1。
3.4 BitMap 和 Roaring BitMap 存储情况对比
上述代码使用了 Java 内置的 BitMap(BitSet) 和 Roaring BitMap 进行存储大小对比，输出结果如下所示。
Roaring BitMap 个数：1000000000
最好情况，BitMap 压缩大小：149KB
最坏情况，BitMap 不压缩大小：119MB
Roaring BitMap 个数：1000000000
BitMap 大小：128MB
可以发现，Roaring BitMap 的压缩性能效果非常好，同等情况下，是 BitMap 占用内存的近一千分之一。在退化成 BitMapContainer/arrayContainer 之后也仍然比使用基本的 BitMap 存储效果好一些。
四、Roaring BitMap 使用
4.1 Java 中相关 API 使用
在 Java 中，Roaring BitMap 提供了交并补差集等操作，如下代码所示，列举了 Java 中 roaing BitMap 的相关 API 使用方式。
对于序列化来说，Roaring BitMap 官方定义了一套序列化规则，用来保证不同语言实现的兼容性。
Java 中可以使用 serialize 方法进行序列化，deserialize 方法进行反序列化。
4.2 业务实际场景应用
Roaring BitMap 可以用来构建大数据标签，针对类型特征来创建对应的标签。
在我们的业务场景中，有很多需要基于人群标签进行交并补集运算的场景，下面以一个场景为例，我们需要计算每天某个设备接口 在设备标签 A 上的查询成功率，因为设备标签 A 中的设备不是所有都活跃在网的，所以我们需要将设备标签 A 与每日日活人群标签取交集，得到的交集大小才能用作成功率计算的分母，另外拿查询成功的标签人群做分子来进行计算即可，查询时长耗时为 1s。
假如没有使用标签保存集合之前，我们需要在 hive 表中查询出同时满足当天在网的活跃用户和设备 A 的用户数量，查询时长耗时在几分钟以上。两种方式相比之下，使用 Roaring BitMap 查询的效率更高。
五、总结
本文结合个人理解梳理了 BitMap 及 Roaring BitMap 的原理及使用，分别主要介绍了 Roaring BitMap 的存储方式及三种 container 类型及 Java 中 Roaring BitMap 相关 API 使用，如有不足和优化建议，也欢迎大家批评指正。
参考资料：
Chambi S , Lemire D , Kaser O , et al.
Better BitMap performance with Roaring
BitMaps[J]. Software—practice & Experience, 2016, 46(5):709-719.
版权声明: 本文为 InfoQ 作者【vivo互联网技术】的原创文章。
原文链接:【http://xie.infoq.cn/article/e77df7450b2496125510e2182】。文章转载请联系作者。
官方公众号：vivo互联网技术，ID：vivoVMIC 2020-07-10 加入
分享 vivo 互联网技术干货与沙龙活动，推荐最新行业动态与热门会议。
评论