Roaring Bitmap——稀疏场景下的Bitmap最优解

Bitmap（位图）是“用二进制位表示元素存在性”的高效结构，但遇到稀疏数据（比如ID是雪花ID、UUID这类不连续值）时，普通Bitmap会浪费99%的空间（比如ID是100000，但要从位0存到100000）。

而Roaring Bitmap就是为解决“稀疏Bitmap空间浪费”而生的优化方案——它通过“分段+压缩”，把稀疏Bitmap的空间利用率提升了10~100倍，同时保持高效的集合运算（交、并、差）。

一、什么是Roaring Bitmap？

Roaring Bitmap（简称RB）是一种优化型Bitmap，核心思想是：

把整数ID分成“高16位”和“低16位”，高16位作为“容器编号”，低16位存在对应容器中；不同容器根据数据密度，用不同的压缩方式存储。

它的目标是：在稀疏场景下省空间，在密集场景下不损失效率。

二、核心原理：“分段+多容器”的压缩逻辑

Roaring Bitmap把32位整数（用户ID常用类型）分成两部分：

高16位：表示“容器组”（共2^16=65536个容器）；
低16位：表示“容器内的元素”（每个容器最多存2^16=65536个元素）。

对每个容器，RB会根据“元素数量”自动选择3种存储方式（按需切换，空间最优）：

1. ArrayContainer（数组容器）——元素少（≤4096个）

当容器内元素数量≤4096时，用有序短整型数组存储低16位值。

举例：容器内只有3个元素（低16位是100、200、300），直接存成[100,200,300]；
优势：空间占用=元素数×2字节（比如3个元素占6字节），比Bitmap（65536位=8KB）省很多。

2. BitmapContainer（位图容器）——元素多（>4096个）

当容器内元素数量>4096时，直接用普通Bitmap存储低16位值。

举例：容器内有5000个元素，用8KB的Bitmap（2^16位=65536位=8KB）存储；
优势：元素多的时候，Bitmap的空间效率比数组高（5000个元素用数组存要10KB，Bitmap只要8KB）。

3. RunContainer（行程编码容器）——元素连续（可选）

当容器内元素是连续区间时（比如100-2000），用“起始值+长度”的行程编码存储。

举例：元素是100-2000，存成(100, 1901)（100是起始，1901是长度）；
优势：连续元素的空间占用极省（不管多长，只存2个整数）。

三、Roaring Bitmap的核心优势

对比普通Bitmap和其他压缩Bitmap（比如EWAH Bitmap），RB的优势很明显：

1. 空间效率极高（尤其是稀疏场景）

普通Bitmap：不管元素多稀疏，都要占“最大ID对应的位数”空间；
Roaring Bitmap：只存“有元素的容器”，且容器按需用数组/位图/行程编码，稀疏场景下空间是普通Bitmap的1/10~1/100。

2. 集合运算速度快

交、并、差等运算直接在“容器级别”做：

相同容器组的元素直接运算；
不同容器组的元素自动归并；
数组/位图容器的运算都做了优化（比如数组用二分查找，位图用位运算）。

3. 兼容性好

支持32位/64位整数，能无缝替换普通Bitmap（很多库都提供了Bitmap的接口封装）。

四、Roaring Bitmap的典型应用场景

正因为“省空间+运算快”，RB在这些场景里是首选：

海量用户去重统计：比如DAU/WAU/MAU（配合ClickHouse等数仓）；
权限控制：用RB存储“用户拥有的权限ID”，快速判断权限交集；
日志去重：存储“已处理的日志ID”，避免重复消费；
推荐系统：存储“用户看过的商品ID”，快速计算用户兴趣交集。

五、实战：Roaring Bitmap的基本用法（以Java库为例）

常用的Roaring Bitmap库是org.roaringbitmap:RoaringBitmap，核心操作很简单：

1. 初始化与添加元素

import org.roaringbitmap.RoaringBitmap;

public class RBDemo {
    public static void main(String[] args) {
        // 初始化RoaringBitmap
        RoaringBitmap rb = new RoaringBitmap();
        
        // 添加元素（用户ID）
        rb.add(1001L);
        rb.add(1002L);
        rb.add(1003L);
    }
}

2. 统计基数（去重数）

// 统计元素个数（对应DAU）
long count = rb.getCardinality();
System.out.println("去重数：" + count); // 输出3

3. 集合运算（比如合并两日DAU）

// 次日的RoaringBitmap
RoaringBitmap rb2 = new RoaringBitmap();
rb2.add(1001L);
rb2.add(1004L);

// 并集（两日总去重用户）
RoaringBitmap union = RoaringBitmap.or(rb, rb2);
System.out.println("总去重数：" + union.getCardinality()); // 输出4（1001、1002、1003、1004）

六、关键细节：使用Roaring Bitmap的注意事项

ID尽量用整数类型：RB只支持整数（32/64位），非整数ID（比如UUID）要先转成整数（比如用哈希函数）；
避免频繁增删（部分库不支持删除）：部分RB实现是“只增”的，删除操作可能效率低；
注意容器切换的开销：当容器内元素数量跨越“4096”阈值时，会触发数组→位图的切换，频繁切换会有性能损耗。

总结

Roaring Bitmap是**“稀疏场景下Bitmap的最优替代方案”**——它用“分段+多容器压缩”解决了普通Bitmap的空间浪费问题，同时保持了高效的集合运算，是海量数据去重、统计场景的“利器”。

注意：本文归作者所有，未经作者允许，不得转载

Roaring Bitmap