跳转至

6.4.2 HLL 近似去重

1 HLL 近似去重

在实际的业务场景中，随着业务数据量越来越大，对数据去重的压力也越来越大，当数据达到一定规模之后，使用精准去重的成本也越来越高，在业务可以接受的情况下，通过近似算法来实现快速去重降低计算压力是一个非常好的方式，本文主要介绍 Doris 提供的 HyperLogLog （简称 HLL ）是一种近似去重算法。

HLL 的特点是具有非常优异的空间复杂度 O(mloglogn) ，时间复杂度为 O(n) ，并且计算结果的误差可控制在 1%-2% 左右，误差与数据集大小以及所采用的哈希函数有关。

2 什么是 HyperLogLog

它是 LogLog 算法的升级版，作用是能够提供不精确的去重计数。其数学基础为伯努利试验。

假设硬币拥有正反两面，一次的上抛至落下，最终出现正反面的概率都是 50% 。一直抛硬币，直到它出现正面为止，我们记录为一次完整的试验。

那么对于多次的伯努利试验，假设这个多次为 n 次。就意味着出现了 n 次的正面。假设每次伯努利试验所经历了的抛掷次数为 k 。第一次伯努利试验，次数设为 k1 ，以此类推，第 n 次对应的是 kn 。

其中，对于这 n 次伯努利试验中，必然会有一个最大的抛掷次数 k ，例如抛了 12 次才出现正面，那么称这个为 k_max ，代表抛了最多的次数。

伯努利试验容易得出有以下结论：

  • n 次伯努利过程的投掷次数都不大于 k_max 。

  • n 次伯努利过程，至少有一次投掷次数等于 k_max

最终结合极大似然估算的方法，发现在 n 和 k_max 中存在估算关联： n = 2 ^ k_max 。当我们只记录了 k_max 时，即可估算总共有多少条数据，也就是基数。

假设试验结果如下：

  • 第 1 次试验：抛了 3 次才出现正面，此时 k=3 ， n=1

  • 第 2 次试验：抛了 2 次才出现正面，此时 k=2 ， n=2

  • 第 3 次试验：抛了 6 次才出现正面，此时 k=6 ， n=3

  • 第 n 次试验：抛了 12 次才出现正面，此时我们估算， n = 2^12

取上面例子中前三组试验，那么 k_max = 6 ，最终 n=3 ，我们放进估算公式中去，明显： 3 ≠ 2^6 。也即是说，当试验次数很小的时候，这种估算方法的误差是很大的。

这三组试验，我们称为一轮的估算。如果只是进行一轮的话，当 n 足够大的时候，估算的误差率会相对减少，但仍然不够小。

3 Doris HLL 函数

HLL 是基于 HyperLogLog 算法的工程实现，用于保存 HyperLogLog 计算过程的中间结果，它只能作为表的 Value 列类型、通过聚合来不断的减少数据量，以此

来实现加快查询的目的，基于它得到的是一个估算结果，误差大概在 1% 左右， HLL 列是通过其它列或者导入数据里面的数据生成的，导入的时候通过 hll_hash 函数

来指定数据中哪一列用于生成 HLL 列，它常用于替代 Count Distinct ，通过结合 Rollup 在业务上用于快速计算 UV 等

3.1 HLL_UNION_AGG(hll)

此函数为聚合函数，用于计算满足条件的所有数据的基数估算。

3.2 HLL_CARDINALITY(hll)

此函数用于计算单条 HLL 列的基数估算

3.3 HLL_HASH(column_name)

生成 HLL 列类型，用于 Insert 或导入的时候，导入的使用见相关说明

4 如何使用 Doris HLL

  1. 使用 HLL 去重的时候，需要在建表语句中将目标列类型设置成 HLL ，聚合函数设置成 HLL_UNION

  2. HLL 类型的列不能作为 Key 列使用

  3. 用户不需要指定长度及默认值，长度根据数据聚合程度系统内控制

4.1 创建一张含有 HLL 列的表

SQL
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
create table test_hll(
    dt date,
    id int,
    name char(10),
    province char(10),
    os char(10),
    pv hll hll_union
)
Aggregate KEY (dt,id,name,province,os)
distributed by hash(id) buckets 10
PROPERTIES(
    "replication_num" = "1",
    "in_memory"="false"
);

4.2 导入数据

  1. Stream load 导入

    Bash
    1
2
3
    curl --location-trusted -u root: -H "label:label_test_hll_load" \
    -H "column_separator:," \
    -H "columns:dt,id,name,province,os, pv=hll_hash(id)" -T test_hll.csv http://fe_IP:8030/api/demo/test_hll/_stream_load

    示例数据如下（ test_hll.csv ）：

    Text Only
    1
2
3
4
5
6
7
8
    2022-05-05,10001，测试 01，北京，windows
2022-05-05,10002，测试 01，北京，linux
2022-05-05,10003，测试 01，北京，macos
2022-05-05,10004，测试 01，河北，windows
2022-05-06,10001，测试 01，上海，windows
2022-05-06,10002，测试 01，上海，linux
2022-05-06,10003，测试 01，江苏，macos
2022-05-06,10004，测试 01，陕西，windows

    导入结果如下

    Bash
     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
    # curl --location-trusted -u root: -H "label:label_test_hll_load"     -H "column_separator:,"     -H "columns:dt,id,name,province,os, pv=hll_hash(id)" -T test_hll.csv <http://127.0.0.1:8030/api/demo/test_hll/_stream_load>

{
    "TxnId": 693,
    "Label": "label_test_hll_load",
    "TwoPhaseCommit": "false",
    "Status": "Success",
    "Message": "OK",
    "NumberTotalRows": 8,
    "NumberLoadedRows": 8,
    "NumberFilteredRows": 0,
    "NumberUnselectedRows": 0,
    "LoadBytes": 320,
    "LoadTimeMs": 23,
    "BeginTxnTimeMs": 0,
    "StreamLoadPutTimeMs": 1,
    "ReadDataTimeMs": 0,
    "WriteDataTimeMs": 9,
    "CommitAndPublishTimeMs": 11
}

  2. Broker Load

    SQL
     1
 2
 3
 4
 5
 6
 7
 8
 9
10
    LOAD LABEL demo.test_hlllabel
(
DATA INFILE("hdfs://hdfs_host:hdfs_port/user/doris_test_hll/data/input/file")
INTO TABLE `test_hll`
COLUMNS TERMINATED BY ","
(dt,id,name,province,os)
SET (
    pv = HLL_HASH(id)
)
);

5 查询数据

HLL 列不允许直接查询原始值，只能通过 HLL 的聚合函数进行查询。

  1. 求总的 PV

    SQL
    1
2
3
4
5
6
7
    mysql> select HLL_UNION_AGG(pv) from test_hll;
+---------------------+
| hll_union_agg(`pv`) |
+---------------------+
|                   4 |
+---------------------+
1 row in set (0.00 sec)

    等价于：

    SQL
    1
2
3
4
5
6
7
    mysql> SELECT COUNT(DISTINCT pv) FROM test_hll;
+----------------------+
| count(DISTINCT `pv`) |
+----------------------+
|                    4 |
+----------------------+
1 row in set (0.01 sec)

  2. 求每一天的 PV

    SQL
    1
2
3
4
5
6
7
8
    mysql> select HLL_UNION_AGG(pv) from test_hll group by dt;
+---------------------+
| hll_union_agg(`pv`) |
+---------------------+
|                   4 |
|                   4 |
+---------------------+
2 rows in set (0.01 sec)