轻松理解RoaringBitmap原理及应用

背景历史

RoaringBitmap是Daniel Lemire¹于2011年发明的一种数据结构，用于压缩大规模非负整数集合，它在存储空间和时间效率上都比传统的位图(Bitmap)²和哈希表(Hash Table)³更加优越。当时，Daniel Lemire主要是为了解决大规模数据场景下整数集合存储、聚合以及查询等问题而发明了RoaringBitmap⁴。

RoaringBitmap的诞生背景在于大数据时代，数据规模日益庞大，传统的数据结构已经难以胜任大数据处理的任务。RoaringBitmap的创新之处在于：它采用了一种分层次的存储结构，将整数集合拆分为多个小块，每个小块之间存在一定的间隙，用Bitmap存储非空小块，用简洁存储方式存储空小块，这样就可以极大地压缩整数集合的存储空间，同时在进行集合运算时也能够高效地处理。

RoaringBitmap的发明在当时引起了极大关注，成为当时最颇具潜力的数据结构之一。如今，RoaringBitmap已经被广泛应用于各种大数据场景中，成为处理大规模整数集合的重要工具之一。

原理与实现

主要思想

1. 我们将 32-bit 的范围 ([0, n)) 划分为 2^16 个桶，每一个桶有一个 Container 来存放一个数值的低16位；
2. 在存储和查询数值的时候，我们将一个数值 k 划分为高 16 位(k % 2^16)和低 16 位(k mod 2^16)，取高 16 位找到对应的桶，然后在低 16 位存放在相应的 Container 中；
3. 容器的话， RBM 使用两种容器结构： Array Container 和 Bitmap Container。Array Container 存放稀疏的数据，Bitmap Container 存放稠密的数据。即，若一个 Container 里面的 Integer 数量小于 4096，就用 Short 类型的有序数组来存储值。若大于 4096，就用 Bitmap 来存储值。

Array Container

Array Container 是 Roaring Bitmap 初始化默认的 Container。Array Container 适合存放稀疏的数据，其内部数据结构是一个有序的 Short 数组。数组初始容量为 4，数组最大容量为 4096，所以 Array Container 是动态变化的，当容量不够时，需要扩容，并且当超过最大容量 4096 时，就会转换为 Bitmap Container。由于数组是有序的，存储和查询时都可以通过二分查找快速定位其在数组中的位置。

后面会讲解为什么超过最大容量 4096 时变更 Container 类型。

下面我们具体看一下数据如何被存储的，例如，0x00020032（十进制131122）放入一个 RBM 的过程如下图所示：

0x00020032 的前 16 位是 0002，找到对应的桶 0x0002。在桶对应的 Container 中存储低 16 位，因为 Container 元素个数不足 4096，因此是一个 Array Container。低 16 位为 0032（十进制为50）, 在 Array Container 中二分查找找到相应的位置插入即可（如上图50的位置）。

相较于原始的 Bitmap 需要占用 16K (131122/8/1024) 内存来存储这个数，而这种存储实际只占用了4B（桶中占 2 B，Container中占 2 B，不考虑数组的初始容量）。

Bitmap Container

第二种 Container 是 Bitmap Container。它的数据结构是一个 Long 数组，数组容量恒定为 1024，和上文的 Array Container 不同，Array Container 是一个动态扩容的数组。Bitmap Container 不用像 Array Container 那样需要二分查找定位位置，而是可以直接通过下标直接寻址。

由于每个 Bitmap Container 需要处理低 16 位数据，也就是需要使用 Bitmap 来存储需要 8192 B（2^16/8）, 而一个 Long 值占 8 个 B，所以数组大小为 1024。因此一个 Bitmap Container 固定占用内存 8 KB。

下面我们具体看一下数据如何被存储的，例如，0xFFFF3ACB（十进制4294916811）放入一个 RBM 的过程如下图所示：

0xFFFF3ACB 的前 16 位是 FFFF，找到对应的桶 0xFFFF。在桶对应的 Container 中存储低 16 位，因为 Container 中元素个数已经超过 4096，因此是一个 Bitmap Container。低 16 位为 3ACB（十进制为15051）, 因此在 Bitmap Container 中通过下标直接寻址找到相应的位置，将其置为 1 即可（如上图15051的位置）。

可以看到元素个数达到 4096 之前，Array Container 占用的空间比 Bitmap Container 的少，当 Array Container 中元素到 4096 个时，正好等于 Bitmap Container 所占用的 8 KB。当元素个数超过了 4096 时，Array Container 所占用的空间还是继续线性增长，而 Bitmap Container 的内存空间并不会增长，始终还是占用 8 KB，与数据量无关。所以当 Array Container 超过最大容量 4096 会转换为 Bitmap Container。

使用场景

什么时候使用BitMap

集合是软件中最基本的抽象概念之一。实现集合的方式有很多种，其中包括散列集、树等。在数据库和搜索引擎等应用中，集合通常是构建索引的重要组成部分。例如，我们需要维护一组满足某些属性的文档或行（通过数字标识符表示）。除了支持添加或删除元素的基本操作外，我们还需要快速计算交集、并集、差集等高级操作。

当我们需要实现一组整数时，使用位图（也称为位集或位向量）是一种非常好的策略。在适当的情况下，比如在 bitset 方法适用时，它可以比其他可能的集合实现（比如哈希集）快数倍，同时需求更少的内存。

然而，即使是压缩的 bitset，也并不总是适用的。例如，如果您有 1000 个看似随机的整数，那么一个简单的数组可能是最好的表现。这种情况被称为稀疏场景。

什么时候使用RoaringBitmap

• 数据量，在未经压缩的 BitSet 会占用大量内存。举例来说，如果您使用 BitSet，并将位置 1,000,000 的位设置为 true，那么您的数据量刚好超过 100KB。即使您忽略内存占用问题，这种做法也是一种浪费。
• 计算量，如果您需要计算这个 BitSet 和另一个在位置 1,000,001 有一个位为真的 BitSet 之间的交集，那么需要遍历所有这些零，这种情况下会非常浪费资源。另外，稀疏场景也是不应使用压缩位图的情况之一。

业务场景

数据过滤

数据过滤是大多数互联网业务需求中必备的部分。RoaringBitmap 可以帮助业务系统快速地对数据进行筛选、过滤、去重等处理。例如，可以使用 RoaringBitmap 实现大数据的记录去重、广告唯一用户数计算、广告点击监控等操作，从而提高数据处理效率。

集合运算

RoaringBitmap 提供了常见的集合操作方法，例如取交集、并集、补集等操作，因此在集合运算中也有着广泛的应用。在互联网业务中，常常需要对用户进行分类、分段、分组等操作，这些操作都可用 RoaringBitmap 进行高效的实现。

日志分析

在大型互联网公司的各种业务系统中，需要对访问日志进行分析和统计。RoaringBitmap 提供了高效的位操作，对于大规模的日志数据的处理可以大大提高性能和效率。例如，在分析用户访问日志中，RoaringBitmap 可以快速实现 IP 地址归属地、请求量统计、访问终端类型检测等操作。