HLL 近似去重

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

HLL 的特点是具有非常优异的空间复杂度 O(mloglogn) , 时间复杂度为 O(n), 并且计算结果的误差可控制在 1%—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 足够大的时候,估算的误差率会相对减少,但仍然不够小。

Doris HLL 函数

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

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

来指定数据中哪一列用于生成 hll 列,它常用于替代 count distinct,通过结合 rollup 在业务上用于快速计算 uv 等

HLL_UNION_AGG(hll)

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

HLL_CARDINALITY(hll)

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

HLL_HASH(column_name)

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

如何使用 Doris HLL

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

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

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

创建一张含有 hll 列的表

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

导入数据

  1. Stream load 导入

    1. curl --location-trusted -u root: -H "label:label_test_hll_load" \
    2. -H "column_separator:," \
    3. -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):

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

    导入结果如下

    1. # 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
    2. {
    3. "TxnId": 693,
    4. "Label": "label_test_hll_load",
    5. "TwoPhaseCommit": "false",
    6. "Status": "Success",
    7. "Message": "OK",
    8. "NumberTotalRows": 8,
    9. "NumberLoadedRows": 8,
    10. "NumberFilteredRows": 0,
    11. "NumberUnselectedRows": 0,
    12. "LoadBytes": 320,
    13. "LoadTimeMs": 23,
    14. "BeginTxnTimeMs": 0,
    15. "StreamLoadPutTimeMs": 1,
    16. "ReadDataTimeMs": 0,
    17. "WriteDataTimeMs": 9,
    18. "CommitAndPublishTimeMs": 11
    19. }
  2. Broker Load

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

查询数据

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

  1. 求总的 PV

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

    等价于:

    1. mysql> SELECT COUNT(DISTINCT pv) FROM test_hll;
    2. +----------------------+
    3. | count(DISTINCT `pv`) |
    4. +----------------------+
    5. | 4 |
    6. +----------------------+
    7. 1 row in set (0.01 sec)
  2. 求每一天的 PV

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