关于dorisdb:StarRocks-BitmapHLL去重即原理

作为 OLAP 数据库，StarRocks 诞生之初的外围应用场景就是统计报表，防止不了有统计去重的需要。

以如来的业务需要举例，在统计命中某个标签的人数时，显然是须要基于用户 ID 去重的。

海量数据的去重，是不能应用传统的 count distinct 形式的，例如下图 2 个 BE 节点上的数据，就须要进行屡次运算。

StarRocks 提供两种高效的去重办法：

• BitMap：对应 BITMAP_UNION
• HyperLogLog：对应 HLL_UNION

还记得聚合表中：BITMAP_UNION、HLL_UNION 两个函数吗，对应的就是这里的去重形式。

1. Bitmap 去重

1.1. 原理

Bitmap 去重可能 精确计算 一个数据集中不反复元素的数量，相比传统的 Count Distinct，能够节俭存储空间、减速计算。

例如，给定一个数组 A，其取值范畴为 [0, n)，可采纳 (n+7)/8 的字节长度的 bitmap 对该数组去重。

行将所有 bit 初始化为 0，而后以数组 A 中元素的取值作为 bit 的下标，并将 bit 置为 1，那么 bitmap 中 1 的个数即为数组 A 中不同元素 (Count Distinct) 的数量。

劣势次要体现在以下两点：

（1）节俭存储空间

通过用 Bitmap 的一个 Bit 位示意对应下标是否存在，能节俭大量存储空间。例如，对 INT32 类型的数据去重，如应用一般的 bitmap，其所需的存储空间只占 COUNT(DISTINCT expr) 的 1/32。

StarRocks 采纳一种设计的非常精美的 bitmap，叫做 Roaring Bitmap，相较 Bitmap 会进一步缩小内存占用。

（2）减速计算

Bitmap 去重应用的是位运算，所以计算速度相较 COUNT(DISTINCT expr) 更快，而且 bitmap 去重在 StarRocks MPP 执行引擎中还能够并行减速解决，进步计算速度。

1.2. 举例

1、建表

创立一张聚合表 page_uv。其中 visit_users 列示意拜访用户的 ID，为聚合列，列类型为 BITMAP，应用聚合函数 BITMAP_UNION 来聚合数据。

CREATE TABLE `page_uv` (
  `page_id` INT NOT NULL COMMENT '页面 id',
  `visit_date` datetime NOT NULL COMMENT '拜访工夫',
  `visit_users` BITMAP BITMAP_UNION NOT NULL COMMENT '拜访用户 id'
) ENGINE=OLAP
AGGREGATE KEY(`page_id`, `visit_date`)
DISTRIBUTED BY HASH(`page_id`)
PROPERTIES (
  "replication_num" = "3",
  "storage_format" = "DEFAULT"
);

2、向表中导入数据。

采纳 INSERT INTO 语句导入：

INSERT INTO page_uv VALUES
(1, '2020-06-23 01:30:30', to_bitmap(13)),
(1, '2020-06-23 01:30:30', to_bitmap(23)),
(1, '2020-06-23 01:30:30', to_bitmap(33)),
(1, '2020-06-23 02:30:30', to_bitmap(13)),
(2, '2020-06-23 01:30:30', to_bitmap(23));

数据导入后:

• 在 page_id = 1，visit_date = ‘2020-06-23 01:30:30’ 数据行，visit_users 字段蕴含 3 个 bitmap 元素（13，23，33）；
• 在 page_id = 1，visit_date = ‘2020-06-23 02:30:30’ 的数据行，visit_users 字段蕴含 1 个 bitmap 元素（13）；
• 在 page_id = 2，visit_date = ‘2020-06-23 01:30:30’ 的数据行，visit_users 字段蕴含 1 个 bitmap 元素（23）。

统计去重的人数能够用 bitmap_union_count，也能够还用 count distinct，StarRocks 会将其主动转换为 bitmap_union_count 函数：

select bitmap_union_count(visit_users) from page_uv group by page_id

1.3. 阐明

Bitmap index 和 Bitmap 去重二者尽管都应用 Bitmap 技术，但引入起因和解决的问题齐全不同。前者用于低基数的枚举型列的等值条件过滤，后者则用于计算一组数据行的指标列的不反复元素的个数。

StarRocks 的 bitmap 去重是基于 Roaring Bitmap 实现的，roaring bitmap 只能对 TINYINT，SMALLINT，INT 和 BIGINT 类型的数据去重。如想要应用 Roaring Bitmap 对其余类型的数据去重，则须要构建全局字典，将其余类型数据（如字符串类型）通过全局字典映射成为整数类型。

Bitmap 是一种数据类型，尽管 BITMAP_UNION 函数是聚合表中的函数，但不是只有聚合表能力创立 Bitmap 类型指标列。甚至表中某列的数据类型是 int，然而在查问时能够通过 to_bitmap 函数，将其转换为 Bitmap 类型再进行位运算。间接存储 Bitmap 类型列，是为了缩小存储空间、查问更快。

从 StarRocks 2.3 版本开始，所有类型的表均反对设置指标列为 BITMAP 类型，然而所有类型的表不反对设置排序键为 BITMAP 类型。

因为 Bitmap 是准确去重，存的是理论值，因而能够通过 bitmap_to_string 函数，将 Bitmap 类型数据转换为逗号分隔（当有多个元素时）的字符串，查看原始 int 值。

2. HyperLogLog

2.1. 概念

HLL（HyperLogLog）是一种 近似去重 算法，当数据量达到肯定水平，Bitmap 准确去重也会比较慢，在对去重精度要求不高的场景下，能够抉择应用 HLL 加重计算压力。HLL 算法的误差可管制在 1% 至 10% 左右，数据量越大，误差越小。

应用 HLL 去重，须要在建表语句中，将指标指标列的类型设置为 HLL，聚合函数设置为 HLL_UNION。
这里要留神，只有 聚合表 反对 HLL 类型列。

2.2. 举例

1、建表

创立聚合表，存储 union_id、member_id HLL 类型：

CREATE TABLE xxx_hll (
    ts DATETIME NOT NULL COMMENT "工夫",
    scene VARCHAR(128) COMMENT "场景编码",
    ab VARCHAR(40) COMMENT "ab 分流内容",
    union_id_hll HLL HLL_UNION COMMENT "unionId 近似去重",
    member_id_hll HLL HLL_UNION COMMENT "memberId 近似去重"
)
AGGREGATE KEY(ts, scene,ab)
PARTITION BY RANGE(ts)(PARTITION p20240114 VALUES LESS THAN ("2024-01-15"))
DISTRIBUTED BY HASH(ts,scene,ab) BUCKETS 8
PROPERTIES(...);

2、StarRocks 通过 Stream Load 导入 columns 为：

ts,scene,ab,union_id,member_id,union_id_hll=hll_hash(union_id),member_id_hll=hll_hash(member_id)

3、查问去重的 union_id、member_id 数量 SQL 为：

SELECT hll_union_agg(union_id_hll),hll_union_agg(member_id_hll) from buddha_user_hit_scene_ab_hll

和 Bitmap 相似，此时应用 count distinct 成果一样，StarRocks 会将其主动转换为 hll_union_agg

2.3. HLL 原理

2.3.1. 伯努利试验

HLL 算法的数学根底是伯努利试验，这里用最直白的形式带大家了解这个算法过程。

伯努利试验 是在同样的条件下反复地、各次之间互相独立地进行的一种试验，试验就两种后果。

最常见的伯努利试验就是抛硬币，只有正、反两面后果，而且每次抛硬币的后果可能性都是二分之一。

当初试验规定设定为：每轮试验抛硬币，如果呈现背面就持续抛，如果呈现侧面就完结本轮试验，咱们记录本轮试验一共抛了几次。

能够计算概率：

• 试验抛了 1 次的概率是：1/2，第 1 次抛就是侧面，概率是 1 /2。
• 试验抛了 2 次的概率是：1/4，即第 1 次抛是背面，第 2 次是侧面，概率是 1/2 * 1/2。
• 试验抛了 3 次的概率是：1/8，即第 1 次抛是背面，第 2 次是背面，第 3 次是侧面，概率是 1/2 1/2 1/2。
• … …
• 试验抛了 n 次的概率是：1/2^n。

意味着要进行 2^n 轮试验，才可能呈现一轮抛了 n 次才呈现侧面的试验。

如果你通知我，你进行了有数轮试验，这些试验中单轮抛了最多的次数，是 100 次。我大略能够揣测出你进行了 2^100 轮试验。

极大似然预计中，试验的基数越大，后果误差越小。这里的基数就是进行多少轮试验，HLL 是一种基数估算算法。只须要记录目前所有试验中单论抛了最多的次数，就能够估算试验基数是多少。即理论数据库中能够只存储数值 n，能够预估统计数量 2^n。

2.3.2. HLL 算法的实现

后面解说如何通过伯努利试验的思维预估宏大的数量，那么 HyperLogLog 算法具体是如何实现这个思维的呢？

还记得在写入 hll 类型数据时，都通过 hll_hash 转换一下：union_id_hll=hll_hash(union_id)

这也是一种 hash 算法，每写入一条数据，就将 union_id 通过 hash 转换成二进制，假如二进制如下：

hash(record) = 011… 00101101110

二进制中只有 0 和 1，咱们能够定义 1 是抛硬币的侧面，0 是背面。只有 hash 算法足够均匀，就能保障二进制中每一位呈现 0、1 的概率都是 1 /2。

上述二进制值，从低位开始，记录第一个呈现 1 的位数（抛了侧面），这里就是第 2 位。数据库中 hll 字段就存储值 2 就能够了。

因为是聚合表，当每次有排序键雷同的数据写入表中时，记录第一个呈现 1 的位数，如果比以后 hll 类型字段的值大就替换，否则就抛弃。

然而以前学概率时老师常说，小概率事件却常常产生！如果说运气好，第一轮试验就抛了十几次，那后续几百轮的误差都会很大，HyperLogLog 算法有什么优化形式吗？求和谐平均数

2.3.3. 求和谐平均数

和谐平均数公式为：

和谐平均数 和 平均数 有啥区别吗？举个例子就分明了：

比方我的工资 1 千块，我共事的工资 10 万元一个月，求咱们公司平均工资。

• 平均数 = (1000+100000)/2 = 50500 (元)
• 和谐平均数 = 2/(1/1000 + 1/100000) ≈ 1980 (元)

显著和谐平均数更正当。因为和谐平均数的后果会偏向于汇合中比拟小的数。

在 HyperLogLog 算法中，hll 数据结构会分成多个桶，二进制数据会将第一个呈现 1 的位数最大值存到随机一个桶内，而后基于各个桶内统计的值求和谐平均数。

Redis 中同样有 HyperLogLog 构造，它会将存储的数据 hash 成 64 位二进制，取其中 14 位决定数据落入哪个桶内（2^14，能够有 16384 个桶），剩下 50 位存储数据，即伯努利试验最多有 50 轮，单个 hll 数据结构能够预估的最大值是 2^50，有 1 千多万亿。

50 的二进制是 110010，最多须要 6 个 bit 寄存。16384 个桶，每个桶存 6 个 bit，则一共不到 12kb，就能预估 1 千多万亿数据。