Bitmap原理及Hive去重方式对比

1. 什么是 Bitmap？

Bitmap（位图）是一种用位（bit）来表示数据集合的数据结构。每个位代表一个元素是否存在，比如：

• 一个长度为N的bitmap，每一位对应一个元素的状态（0或1）。
• 例如，数字集合 {1, 3, 4}，用bitmap表示就是第1、3、4位为1，其余为0。

1.1 Bitmap的特点：

• 空间利用率高：用bit表示，存储效率高。
• 查询效率快：判断某个元素是否存在，直接定位对应bit即可。
• 支持快速集合操作：如并集、交集、差集等，直接对bit位做位运算。

1.2 位（bit）、字节（byte）、KB（千字节）

1.2.1 位（bit）

• 定义：bit是计算机中最小的数据单位，表示二进制中的一个0或1。
• 符号：通常用小写字母 b 表示。
• 作用：所有数字、字符、图像、声音等信息，最终都以0和1的形式存储和处理，bit就是这些信息的最小单位。

1.2.2 字节（byte）

• 定义：字节是计算机存储信息的基本单位，通常由8个bit组成。
• 符号：用大写字母 B 表示。
• 作用：一个字节可以表示256种不同的状态（2^8），通常用来表示一个字符（比如一个英文字母、数字或符号），中文占2-4个字符，udf-8占3个，udf-16大多占2个，生僻字占4个，GB2312 / GBK / GB18030大陆编码占4个。
• 关系：1 字节 = 8 位 (bits)

1.2.3 KB（千字节）

• 定义：KB是存储容量的单位，表示1024个字节。
• 符号：用大写字母 KB 表示。
• 注意：虽然“K”通常表示1000，但计算机存储中，1KB = 1024字节（2的10次方），这是因为计算机采用二进制计数。
• 关系：
  • 1 KB = 1024 Bytes
  • 1 Byte = 8 bits

1.2.4 总结关系

1.2.5 举个例子

• 一个英文字符（如字母“A”）通常占用1字节（8位）。
• 一个文件大小为10KB，意味着它大约有10 × 1024 = 10240字节，等于 10,240 × 8 = 81,920 位。

2. Bitmap的用途

• 去重计数（Distinct Count）：统计不重复元素个数。
• 集合操作：快速实现集合的并、交、差。
• 布隆过滤器：判断元素是否存在（可能有误判）。
• 大数据场景：处理海量数据的去重、统计。

3. Hive中如何用Bitmap去重？

Hive本身不直接支持bitmap类型，但可以通过扩展函数（UDF）或者第三方库（如bitmap-udf、RoaringBitmap等）实现。

常见做法：

• 使用bitmap UDF构建bitmap，比如 bitmap_add()，把每个元素对应的bit位置置1。
• 最后用 bitmap_count() 计算bitmap中1的个数，即去重后的数量。

示例伪代码：

SELECT
  bitmap_count(bitmap_union_agg(bitmap_add(user_id))) AS distinct_user_count
FROM
  user_logs;

• bitmap_add(user_id)：把user_id加入bitmap。
• bitmap_union_agg()：聚合多个bitmap做并集。
• bitmap_count()：统计bitmap中1的数量

4. 和 count(distinct)、size(collect_set())对比

4.1 总结

4.2执行过程及原理

4.2.1count(distinct)

执行过程：

• Map阶段：
  • 读取数据，提取目标字段值。
  • 在Map端做局部去重（减少数据量）。
• Shuffle阶段：
  • 将局部去重后的数据发送到Reducer。
• Reduce阶段：
  • Reducer对接收到的所有值做全局去重。
  • 统计不同值数量，输出结果。

原理：

• 使用哈希表或类似数据结构存储不同元素。
• 需要在内存中维护distinct值集合，内存消耗与distinct数量相关。

4.2.2 size(collect_set())

执行过程：

• Map阶段：
  • 读取数据，提取字段值。
• Shuffle阶段：
  • 将数据发送到Reducer。
• Reduce阶段：
  • 聚合所有值，使用集合结构去重，形成唯一元素集合。
• 调用size()：
  • 计算集合大小。

原理：

• collect_set()收集所有唯一元素到集合中。
• 需要将所有去重元素集中到Reducer节点，内存压力大。

4.2.3 Bitmap去重

执行过程：

• Map阶段：
  • 对每条记录，调用bitmap_add()，将元素映射到bitmap对应的bit位置，置1。
• Shuffle阶段：
  • 将bitmap数据传输到Reducer。
• Reduce阶段：
  • 对多个bitmap做位或（OR）操作，合并所有局部bitmap。
• 调用bitmap_count()：
  • 统计bitmap中置1的位数，即去重元素数量。

原理：

• 利用bitmap的位标记特性，空间效率高。
• 支持分布式合并，内存占用低。
• 只能统计数量，不能返回具体元素。
• 需要额外安装bitmap相关UDF。

5. Bitmap去重的弊端

• 只能统计数量，不能直接得到去重元素列表。
• 需要额外配置和安装bitmap相关的UDF或库，不是Hive原生功能。
• 误差问题：如果使用压缩bitmap或者近似算法（比如HyperLogLog），会有一定误差，不适合对精度要求极高的场景。
• 不适合元素非常稀疏且范围极大的场景，因为bitmap大小可能很大。

总结