SelectDB中HyperLogLog去重 - ApsaraDB for SelectDB

本文介紹提供的HyperLogLog（簡稱 HLL）功能，協助您進行資料去重，加速查詢。

概述

在實際的業務情境中，隨著業務資料量的不斷增加，資料去重的壓力也隨之增大。當資料規模達到一定程度時，採用精準去重的成本也隨之增加。在業務可接受的情況下，通過近似演算法來快速去重，降低計算壓力，是一種非常有效方式。

針對這種情境，SelectDB提供了近似去重演算法HyperLogLog（簡稱 HLL）。HLL的特點是具有非常優異的空間複雜度O(log(logn))和時間複雜度O(n)，並且計算結果的誤差可控制在1%~2%左右（誤差與資料集大小以及所採用的雜湊函數有關）。

HyperLogLog原理

近似去重演算法HyperLogLog是LogLog演算法的升級版，作用是能夠提供不精確的去重計數，其數學基礎為伯努利實驗。

數學基礎

在伯努利實驗中，假設硬幣擁有正反兩面，一次拋硬幣中最終出現正反面的機率都是50%。若將“一直拋硬幣，直到它出現正面為止”記錄為一次完整的實驗，那麼對於n次伯努利實驗，就意味著出現了n次的正面。

假設每次伯努利實驗所經歷了的拋擲次數為k，第一次伯努利實驗的次數設為k1，第n次對應的是kn，以此類推。那麼在這之中，對於這n次伯努利實驗，必然會有一個最大的拋擲次數k，意味著拋了k次才出現正面，稱這個次數為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足夠大的時候，估算的誤差率會相對減少，但仍然不夠小。

SelectDB HLL函數

HLL是基於HyperLogLog演算法的工程實現，用於儲存HyperLogLog計算過程的中間結果，它只能作為表的Value列類型、通過彙總來不斷的減少資料量，以此來實現加快查詢的目的。基於它得到的是一個估算結果，誤差大概在1%左右。HLL列是通過其它列或者匯入資料裡面的資料產生的，匯入的時候通過hll_hash函數來指定資料中哪一列用於產生HLL列。它常用於替代count distinct，與ROLLUP結合在業務上用於快速計算獨立訪客UV（Unique Visitor）等。

HLL函數有以下幾個。

HLL_UNION_AGG(hll)
此函數為彙總函式，用於計算滿足條件的所有資料的基數估算。
HLL_CARDINALITY(hll)
此函數用於計算單條HLL列的基數估算。
HLL_HASH(column_name)
產生HLL列類型，用於Insert或匯入資料時，匯入的使用請參見使用樣本。

使用樣本

建立一張含有HLL列的表
```
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"
);
```
重要
使用HLL需要注意以下問題。
- 使用HLL去重的時候，需要在建表語句中將目標列類型設定成HLL，彙總函式設定成HLL_UNION。
- HLL類型的列不能作為Key列使用。
- 不需要指定長度及預設值，長度根據資料彙總程度在系統內控制。

匯入資料

樣本資料如下（test_hll.csv）。

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

使用不同的匯入方式如下。

使用Stream Load匯入，樣本如下。

# 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
}

使用Broker Load匯入，樣本如下。

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)
    )
 );

查詢資料

HLL列不允許直接查詢原始值，只能通過HLL的彙總函式進行查詢。

求總的PV，樣本如下。

SELECT HLL_UNION_AGG(pv) FROM test_hll;
+---------------------+
| hll_union_agg(`pv`) |
+---------------------+
|                   4 |
+---------------------+
1 row in set (0.00 sec)

等價於使用(DISTINCT pv)查詢。

SELECT COUNT(DISTINCT pv) FROM test_hll;
+----------------------+
| count(DISTINCT `pv`) |
+----------------------+
|                    4 |
+----------------------+
1 row in set (0.01 sec)

求每一天的PV，樣本如下。

SELECT HLL_UNION_AGG(pv) FROM test_hll GROUP BY dt;
+---------------------+
| hll_union_agg(`pv`) |
+---------------------+
|                   4 |
|                   4 |
+---------------------+
2 rows in set (0.01 sec)