RoaringBitmap原理与大数据去重
什么是RoaringBitmap？请说明其数据结构和存储优化原理。相比传统BitMap，RoaringBitmap在稀疏和稠密场景下各有哪些优势？在StarRocks/Druid/Kylin中如何应用RoaringBitmap实现精确去重和加速计算？
回答
我是大山
1. RoaringBitmap原理
RoaringBitmap将32位整数空间分为高16位和低16位：
Key（高16位） Container
↓ ↓
0x0001 → ArrayContainer(稀疏，存低16位列表)
0x0002 → BitmapContainer(稠密，位图)
0x0003 → RunContainer(连续范围，变长编码)
三种Container：
| 容器类型 | 存储方式 | 适用场景 | 内存占用 |
|---|---|---|---|
| ArrayContainer | short[] 有序数组 | 元素<4096个 | 2*N bytes |
| BitmapContainer | 8KB位图 | 元素≥4096个 | 8KB固定 |
| RunContainer | (start, len)对 | 连续大区间 | 2*RLE对 bytes |
2. 优势对比
| 场景 | 传统BitMap | RoaringBitmap |
|---|---|---|
| 稀疏（1%填充） | 8KB固定 | 240962=16KB...但优于N=1时2bytes |
| 稠密（90%填充） | 8KB固定 | BitmapContainer=8KB（相同） |
| 压缩（连续） | 8KB固定 | RunContainer可压缩到几百bytes |
| AND/OR运算 | O(n)位运算 | 智能选择Container类型优化 |
3. 大数据应用
StarRocks精确去重
-- Bitmap类型列
CREATE TABLE user_visit (
dt DATE,
user_id BITMAP BITMAP_UNION
) AGGREGATE KEY(dt);
-- 查询
SELECT dt, bitmap_count(user_id) FROM user_visit;
SELECT bitmap_count(bitmap_union(user_id)) FROM user_visit;
Druid
- 使用RoaringBitmap实现精确去重
- 支持跨维度Bitmap运算（交/并/差）
Kylin
- 预计算中Bitmap精确去重度量
- 支持IntersectCount
4. 性能对比
1亿用户ID去重：
HyperLogLog：1.2MB（误差2-3%）
RoaringBitmap：≈120MB（精确）
原始BitMap：512MB
普通HashSet：3.2GB+
5. 适用场景
- 精确UV统计（用户数≤10亿）
- 画像分析（标签交并运算）
- 漏斗分析（每一步去重）
- 广告归因（多维度明细交集）