Bitmap在数仓中的应用

一、配景

在数据堆栈的一样平常工作中，我们常常必要面对海量数据的存储和高效查扣标题。尤其是，当业务对性能的要求越来越高、数据量连续增长时，传统的处理惩罚方式每每显得鸠拙而低效。而这时间，Bitmap（位图）作为一种“看似简单却威力强大”的数据结构，渐渐显现出它的代价。简单来说，Bitmap 就像是一种用“0”和“1”记载信息的小工具。它通过位的情势将数据高效地压缩存储，同时支持快速的聚集运算，比如并集、交集、补集等。这些特性使得 Bitmap 在高基数去重、举动统计、快速筛选等场景中表现得尤为精彩。比如，给定一个数千万级别的用户群，使用 Bitmap 技能可以在几毫秒内完成某些复杂的查询操纵，这在传统方法中大概必要数十秒乃至更长时间。
Bitmap 在数据堆栈中的应用非常广泛。无论是资助优化指标盘算，还是提升查询性能，它都可以大概为开发者办理许多头疼的标题。比方，在广告投放场景下，我们必要实时统计某一人群的曝光次数；在用户运营中，我们大概必要高效筛选出符合特定标签的用户群。这些看似复杂的任务，通过 Bitmap，每每能以优雅的方式轻松办理。
这篇文章渴望以实际案例为切入点，团结 Bitmap 的原理，聊一聊它在数据堆栈中的应用场景和实现方式，资助各人更好地明确和使用这一实用工具。
二、Bitmap 原理

2.1 根本构成

Bitmap 是一个连续的位数组，数组的每个位置对应一个无符号整数。比方必要存储 1、2、4、5 元素，只必要将这个数组的第 1、2、4、5 位设置为 1 别的位保持为 0 即可，即为011011
2.2 核心操纵

2.2.1 交

通过按位与盘算两个位图的交集，比方 bitmap1 和 bitmap2 的位图分别是 1010 和 0110，它们的交集为 0010
2.2.2 并

通过按位或盘算两个位图的并集，比方 bitmap1 和 bitmap2 的位图分别是 1010 和 0110，它们的并集为 1110
2.2.3 补

通过按位取反盘算某个位图的补集，比方 bitmap 的位图是 1010，它的补集位 0101
2.2.4 差

通过按位与非盘算两个位图的差集，比方 bitmap1 和 bitmap2 的位图分别是 1010 和 0110，它们的差集为 1000（bitmap & ~bitmap2）
2.2.5 基数

按位盘算位图中值位 1 的数量，比方 bitmap 的位图是 1010，它的基数为 2
2.3 应用场景

位图由于其独特的数据结构在大规模数据统计场景有着内存占用低、盘算服从高的特点。比方存储 100 万个连续无符号正整数(uint)，直接存储约莫必要 4MB(100 万 x 4byte)，而使用位图只必要100 万位即可，而每位只必要 1bit(8bit = 1byte)约莫只需 122KB；同时其按位盘算是盘算机中服从最高的盘算方式之一。
位图的根本操纵在生产中应用也是极其广泛的，比方：在用户举动分析中

• 交：同时满意多个条件的用户聚集，对应 sql 中的 and
  
• 并：满意恣意条件的用户聚集，对应 sql 中的 or
  
• 补/差：满意条件 A 不满意条件 B 的用户聚集，对应 sql 中的 and not 组合
  
• 基数：交并补差操纵之后统计满意条件的用户个数，对应 sql 中的 count(distinct)
  

Tip: 从聚集的角度来看，补和差的逻辑是一样的。只不外补的逻辑是 AB 两个聚集是存在子集的关系，若 AB 不满意父子集关系就是差运算。本质都是从一个聚集中扣出别的一个聚集中的元素
三、Bitmap 的痛点及其优化

2.3 的例子中特地夸大了连续，由于从 Bitmap 根本数据结构可以看出，位图的长度只和最大的元素有关与元素个数无关。如果必要存储一个极其离散的数据集，比方[1,1000000] 位图在必要开发 100 万个 bit 空间，但实际只存储两条数据，这时间使用位图依然必要 122KB 的空间，但直接存储只必要 2 x 4byte = 8byte 这是其痛点之一。
第二个痛点是只能存储无符号整数，生产中的数据是五花八门的连最常用的字符串都不能处理惩罚是会影响它的使用范围的。为此本章节紧张是来讨论怎样办理或缓解这两个痛点
3.1 RoaringBitmap

RoaringBitmap 在 bitmap 的根本上通太过块和压缩来表现希罕或稠密数据的整数聚集且每块根据稠密性选择差别的压缩方式，其官网地点如下：https://roaringbitmap.org/
RoaringBitmap 的核心是将一个 32 位的无符号整数分为高 16 位和低 16 位两部门，此中高 16 位作为索引，每个索引对应一个 container 用来存储低 16 位的数据；同时 RoaringBitmap 还会根据数据规模以及稠密程度提供三种 container 实现

• ArrayContainer
  
• BitmapContainer
  
• RunContainer
  下面通过源码简单的过一下 RoaringBitmap 的实现逻辑
  

3.1.2 索引逻辑

RoaringBitmap 的底层实现类是 RoaringArray 下面是这个类的核心属性

1. static final int INITIAL_CAPACITY = 4;  // keys 的初始长度
2.   
3. char[] keys = null;  // 存储高 16 位的索引值
4.   
5. Container[] values = null; // 存储低 16 位的数据

复制代码

下面是核心的 add 方法

1. public void add(final int x) {  
2.   final char hb = Util.highbits(x);  // 获取高 16 位索引值
3.   final int i = highLowContainer.getIndex(hb);  // 通过索引获取容器的索引值
4.   if (i >= 0) {  // 容器已经存在
5.     highLowContainer.setContainerAtIndex(i,  
6.         highLowContainer.getContainerAtIndex(i).add(Util.lowbits(x)));  
7.   } else {  // 容器不存在
8.     final ArrayContainer newac = new ArrayContainer();  
9.     highLowContainer.insertNewKeyValueAt(-i - 1, hb, newac.add(Util.lowbits(x)));  
10.   }}

复制代码

上面的代码可以看出Container 的默认实现是 ArrayContainer
同时索引的处理惩罚逻辑可以这么明确，从 0 到 32 位无符号整数的最大值(42亿左右)按 65536 将元素分别成 65536 份分别存储到 container 中
3.1.3 容器逻辑

ArrayContainer

ArrayContainer 的核心逻辑是通过一个 char 数组按序存储低 16 位的实际值，下面是两个核心参数

1. private static final int DEFAULT_INIT_SIZE = 4;  // 初始容量
2.   
3. static final int DEFAULT_MAX_SIZE = 4096;// 最大容量

复制代码

以是肯定陪同着数组的扩容，对于 DEFAULT_MAX_SIZE 则是当数据规模到达肯定程度时存储原始数据将不再有上风必要转换到 BitmapContainer 实现

1. public Container add(final char x) {
2.     if (cardinality == 0 || (cardinality > 0 && (x) > (content[cardinality - 1]))) {
3.       if (cardinality >= DEFAULT_MAX_SIZE) {
4.         return toBitmapContainer().add(x); // 数据量超过阈值，转换为 bitmapcontainer
5.       }
6.       if (cardinality >= this.content.length) {
7.         increaseCapacity(); // 扩容逻辑
8.       }
9.       content[cardinality++] = x; // 保存低 16 位原始数据
10.     } else {
11.           // 通过二分法查找带插入的位置
12.       int loc = Util.unsignedBinarySearch(content, 0, cardinality, x);
13.       if (loc < 0) {
14.         // Transform the ArrayContainer to a BitmapContainer
15.         // when cardinality = DEFAULT_MAX_SIZE
16.         if (cardinality >= DEFAULT_MAX_SIZE) {
17.           return toBitmapContainer().add(x);
18.         }
19.         if (cardinality >= this.content.length) {
20.           increaseCapacity();
21.         }
22.         // insertion : shift the elements > x by one position to
23.         // the right
24.         // and put x in it's appropriate place
25.         System.arraycopy(content, -loc - 1, content, -loc, cardinality + loc + 1);
26.         content[-loc - 1] = x;
27.         ++cardinality;
28.       }
29.     }
30.     return this;
31. }

复制代码

BitmapContainer

当数据量高出 4096 时再存储原始数据不管是内存还是盘算服从都不占上风，因此将其转换为 Bitmap 存储。必要留意的是 RoaringBitmap 的 Bitmap 相对于位图实现是极其奥妙的。
下面是核心属性以及构造方法

1. public static final int MAX_CAPACITY = 1 << 16; // 最大容量 65536
3. final long[] bitmap;
5. public BitmapContainer() {  
6.   this.cardinality = 0;  
7.   this.bitmap = new long[MAX_CAPACITY / 64];  // 数组长度 1024
8. }

复制代码

MAX_CAPACITY 分析一个 Container 必要存储 65536 个元素（这是低 16 位决定的），但是 BitmapContainer 却使用了 1024 长度的 long 数组来存储，总内存占用固定位 1024 x 8byte = 8KB，下面是最为精彩的添加元素操纵

1. public Container add(final char i) {  
2.   final long previous = bitmap[i >>> 6];  // 除 64 找到该值对应的数组位置并获取数据
3.   long newval = previous | (1L << i);  // 1L << i 生成只有第 i 位为 1 其余都是 0 的值并与原值做或
4.   bitmap[i >>> 6] = newval;  // 替换原值
5.   // 更新基数
6.   if (USE_BRANCHLESS) {  
7.     cardinality += (int)((previous ^ newval) >>> i);  
8.   } else if (previous != newval) {  
9.     ++cardinality;  
10.   }  return this;  
11. }

复制代码

至于为什么接纳 long 来存储同时筹划这么复杂的插入逻辑，可以从下面几点思索

• 当代 CPU 的指令集对 64 位（long）数据的处理惩罚服从更高
  
• 使用 long 举行按位操纵（如 &、|、~）时，只需一次指令即可处理惩罚 64 位，而使用 byte 必要处理惩罚 8 次
  
• 使用 long[] 时，每个元素固定存储 64 位，通过简单的位运算可以直接访问特定位
  固然使用 long 数组在内存使用上不是最优解，但是 BitmapContainer 是在 ArrayContainer 根本上转换过来的，自己已经是一种麋集场景，因此使用 long 在盘算性能上会有较大的上风，这点额外的内存开销是可以担当的
  

RunContainer

RunContainer 是一种特别的容器范例，被筹划在用于高效的连续数据存储，使用一个有序数组，存储数值范围的出发点和止境，紧张的目标是在数据高度连续时，镌汰内存占用和进步操纵服从。
比方：[1, 2, 3, 4, 5, 10, 11, 12] 可以优化为 [(1, 5), (10, 12)]
但是由于数据的离散程度 RoaringBitmap 无法直接控制，因此 BitmapContainer 向 RunContainer 的厘革是手动的，在 BitmapContainer 中提供 runOptimize 方法交由使用者自己调用

1. public Container runOptimize() {  
2.   int numRuns = numberOfRunsLowerBound(MAXRUNS); // decent choice  
3.   
4.   int sizeAsRunContainerLowerBound = RunContainer.serializedSizeInBytes(numRuns);  
5.   
6.   if (sizeAsRunContainerLowerBound >= getArraySizeInBytes()) {  
7.     return this;  
8.   }  // else numRuns is a relatively tight bound that needs to be exact  
9.   // in some cases (or if we need to make the runContainer the right  // size)  numRuns += numberOfRunsAdjustment();  
10.   int sizeAsRunContainer = RunContainer.serializedSizeInBytes(numRuns);  
11.   
12.   if (getArraySizeInBytes() > sizeAsRunContainer) {  
13.     return new RunContainer(this, numRuns);  
14.   } else {  
15.     return this;  
16.   }
17. }

复制代码

3.2 Roaring64Bitmap 和 Roaring64NavigableMap

RoaringBitmap 的筹划是存储 32 位无符号整数，但是对于大型网站、APP 等其用户 id 规模肯定是高出 RoaringBitmap 的筹划范围，因今生产中更多的是使用 Roaring64Bitmap 或 Roaring64NavigableMap 实现，从类名就可以看出来可存储 64 位无符号整数。固然存储的数据范围差别且实现细节也略有差别，但团体头脑都是将数据分为高位和低位，高位作为索引低位存储到 container 中，因此三者的区别紧张是对高位索引的处理惩罚机制上
Roaring64Bitmap 和 Roaring64NavigableMap 区别如下：

• Roaring64Bitmap 将高 48 位作为索引并存储到  Art 中（The Adaptive Radix Tree），低 16 位存储到 Container 中，Container 的实现与 RoaringBitmap 同等
  
• Roaring64NavigableMap 将高 32 位作为索引并存储到 NavigableMap 中，具体的实现是 TreeMap 底层是红黑树，低 32 位存储到 Container 中。有自己的实现，感爱好可以看一下 BitmapDataProvider 的实现类（也是三种）
  

3.3 拓展恣意数据范例

不管是 Bitmap 的哪种实现都只能处理惩罚无符号整数，对于字符串的处理惩罚可以从下面两种方向去思量拓展
3.3.1 hash

通过 hash 将字符串转换成无符号整数，但必要思量 hash 函数的离散型大概得到的聚集数据过于离散使用 bitmap 不愿定是最佳实践。
3.3.2 row_number

通过 dense_rank() over() 全窗口开窗天生连续序号。这种方案可以处理惩罚恣意范例的数据同时还可以处理惩罚原聚集数据过于离散的环境；但是全窗口开窗在超大数据会集服从极低乃至无法完成盘算，同时必要额外的 join 操纵更换掉原聚集数据，这种场景是否必要继续使用 bitmap 有待商讨。
四、生产中的 Bitmap

4.1 集成 Spark/Hive

生产中的 bitmap 通常是使用 UDF 集成到 Spark/Hive 中(下面统称 UDF)。保举使用 Doris 提供的 bitmap 实现，相对来说比力权势巨子 https://doris.apache.org/zh-CN/docs/ecosystem/hive-bitmap-udf
Tip: doris 的 hive bitmap 在 fe 下面终极天生 jar 相对来说也比力大，可以自己重新起一个专门的 udf 项目对照写一下
4.2 实战

编写一段 shell 脚本用于天生随机的 userid

1. #!/bin/bash
3. # 输入参数
4. MAX_ROWS=$1          # 最大行数
5. MAX_USERID=$2        # 最大 userid
6. MAX_PARALLEL=$3      # 最大并行度
8. # 校验参数
9. if [[ -z "$MAX_ROWS" || -z "$MAX_USERID" || -z "$MAX_PARALLEL" ]]; then
10.   echo "Usage: $0 <max_rows> <max_userid> <max_parallel>"
11.   exit 1
12. fi
14. # 临时目录
15. OUTPUT_DIR="./output"
16. MERGED_FILE="./merged_result.txt"
17. mkdir -p "$OUTPUT_DIR"
19. # 计算每个子任务分配的行数
20. ROWS_PER_TASK=$((MAX_ROWS / MAX_PARALLEL))
21. REMAINING_ROWS=$((MAX_ROWS % MAX_PARALLEL)) # 分配多余的行到最后一个任务
23. # 打印任务分配情况
24. echo "总行数: $MAX_ROWS"
25. echo "最大用户 ID: $MAX_USERID"
26. echo "最大并行任务数: $MAX_PARALLEL"
27. echo "每个任务行数: $ROWS_PER_TASK"
28. echo "多余行数: $REMAINING_ROWS"
30. # 任务计数器
31. TASK_COMPLETED=0
33. # 生成随机行的函数
34. generate_random_users() {
35.   local task_id=$1
36.   local rows=$2
37.   local output_file=$3
39.   echo "任务 $task_id: 开始生成 $rows 行数据到 $output_file..."
40.   for ((i=1; i<=rows; i++)); do
41.     echo $((RANDOM % MAX_USERID)) >> "$output_file"
42.   done
43.   echo "任务 $task_id: 生成完成！"
44. }
46. # 启动子任务
47. for ((i=1; i<=MAX_PARALLEL; i++)); do
48.   OUTPUT_FILE="$OUTPUT_DIR/task_${i}.txt"
49.   ROWS_TO_GENERATE=$ROWS_PER_TASK
51.   # 最后一个任务需要分配多余的行
52.   if [[ $i -eq $MAX_PARALLEL ]]; then
53.     ROWS_TO_GENERATE=$((ROWS_PER_TASK + REMAINING_ROWS))
54.   fi
56.   generate_random_users "$i" "$ROWS_TO_GENERATE" "$OUTPUT_FILE" &
57. done
59. # 等待所有子任务完成
60. wait
61. TASK_COMPLETED=$MAX_PARALLEL
62. echo "所有任务完成！"
64. # 合并所有文件
65. echo "开始合并所有任务文件..."
66. cat "$OUTPUT_DIR"/*.txt > "$MERGED_FILE"
67. echo "合并完成，输出文件: $MERGED_FILE"
69. # 清理临时文件
70. rm -rf "$OUTPUT_DIR"
71. echo "临时文件已清理！"

复制代码

天生 1 亿行范围在 0 - 1 千万的 userid

1. ./generate_user_id.sh 100000000 10000000 10
2. 总行数: 100000000
3. 最大用户 ID: 10000000
4. 最大并行任务数: 10
5. 每个任务行数: 10000000
6. 多余行数: 0
7. 任务 1: 开始生成 10000000 行数据到 ./output/task_1.txt...
8. 任务 2: 开始生成 10000000 行数据到 ./output/task_2.txt...
9. 任务 3: 开始生成 10000000 行数据到 ./output/task_3.txt...
10. 任务 4: 开始生成 10000000 行数据到 ./output/task_4.txt...
11. 任务 5: 开始生成 10000000 行数据到 ./output/task_5.txt...
12. 任务 6: 开始生成 10000000 行数据到 ./output/task_6.txt...
13. 任务 7: 开始生成 10000000 行数据到 ./output/task_7.txt...
14. 任务 8: 开始生成 10000000 行数据到 ./output/task_8.txt...
15. 任务 9: 开始生成 10000000 行数据到 ./output/task_9.txt...
16. 任务 10: 开始生成 10000000 行数据到 ./output/task_10.txt...

复制代码

导入表中

1. use blog;  
2.   
3. create table user_info  
4. (  
5.     user_id bigint  
6. ) stored as parquet;  
8. create table user_info_txt  
9. (  
10.     user_id bigint  
11. ) stored as textfile;
12.   
13. load data local inpath '/Users/wjun/tmp/bitmap_data/merged_result.txt' overwrite into table user_info_txt;
15. -- 数据量扩充 5 倍
16. insert overwrite table user_info  
17. select tbl.user_id  
18. from user_info_txt t  
19.          lateral view explode(array(t.user_id, t.user_id, t.user_id, t.user_id, t.user_id)) tbl as user_id

复制代码

导入 bitmap jar 并创建 bitmap 干系的函数

1. add jars hdfs://127.0.0.1:8020/user/hive/jars/hive-bitmap-udf.jar;  
2. create temporary function to_bitmap AS 'com.hive.bitmap.udf.ToBitmapUDAF';  
3. create temporary function bitmap_union AS 'com.hive.bitmap.udf.BitmapUnionUDAF';  
4. create temporary function bitmap_count_v1 AS 'com.hive.bitmap.udf.BitmapCountUDF';  
5. create temporary function bitmap_and AS 'com.hive.bitmap.udf.BitmapAndUDF';  
6. create temporary function bitmap_or AS 'com.hive.bitmap.udf.BitmapOrUDF';  
7. create temporary function bitmap_xor AS 'com.hive.bitmap.udf.BitmapXorUDF';  
8. create temporary function bitmap_to_array AS 'com.hive.bitmap.udf.BitmapToArrayUDF';  
9. create temporary function bitmap_from_array AS 'com.hive.bitmap.udf.BitmapFromArrayUDF';  
10. create temporary function bitmap_contains AS 'com.hive.bitmap.udf.BitmapContainsUDF';

复制代码

分析：spark 3.5.1 内置了 bitmap_count 这里为了不重名使用 bitmap_count_v1
下面紧张演示 bitmap 在盘算 uv 的场景实战
正常写法：

1. select count(distinct user_id) as uv from user_info;

复制代码

进阶写法：

1. select count(1) as uv  
2. from (select user_id from user_info group by user_id);

复制代码

bitmap 写法：

1. select bitmap_count_v1(to_bitmap(user_id)) from user_info;

复制代码

纵然 user_info 的数据量已经到达 5 亿，但是由于缺少对应的维度（没有 group by）测试效果大概率还是 count(distinct user_id) 最快。还是必要各位在生产环境中去验证，当开发指标时发现 count(distinct user_id) 已经出不来效果而且导致 spark 频仍的 oom 时可以思量 bitmap 写法
讨论：理论上 count(distinct user_id) 都可以优化成嵌套 group by 写法，但是当出现一个查询列表中出现多个字段的 count distinct 嵌套 group by 大概就不是很好实现了