在 AnalyticDB for PostgreSQL 中使用HyperLogLog 實作毫秒級 UV / PV 統計

在網際網路産品的日常營運中, 經常需要統計網頁的 PV / UV 通路量，或者産品的 日活/月活 使用者量. 本文介紹了在 分析型資料庫PostgreSQL版

中如何使用HyperLogLog擴充來完成PV/UV 或者 日活/月活使用者量的統計. 該方法能在誤差不超過千分之二的前提下将統計時間降低300倍以上.

HyperLogLog 是一種算法, 可以用來估算資料集的基數. 基數是指一個集合中不同值的數目, 等同于

COUNT(DISTINCT field)

傳回值. 對于超大資料集來說, 精确的基數統計往往需要消耗大量的記憶體與時間, 并且消耗的記憶體與時間會随着資料集基數的增加而成比例增加. 而 HyperLogLog 能夠在常數級的記憶體與時間下, 以極低的誤差來擷取資料集基數的近似統計. 在分析型資料庫PostgreSQL版中, HyperLogLog 的誤差與記憶體消耗量受如下參數控制:

• log2m, 該參數控制着 HyperLogLog 對資料集基數估算的誤差為:

  1.04 / math.sqrt(2 ** log2m)

  . 該參數同時也控制着 HyperLogLog 記憶體消耗量.
• regwidth, 該參數與 log2m 一起決定了 HyperLogLog 記憶體消耗量最多為

  (2 ** log2m) * regwidth / 8

  位元組. 同時該函數也決定了 HyperLogLog 所能估算資料集基數的最大值.

本文在示範時, log2m 參數取值為 17, regwidth 參數取值為 7. 此時 HyperLogLog 對資料集基數估算的誤差為千分之二. 在示範開啟前, 執行指令, 建立 HyperLogLog 插件:

CREATE EXTENSION hll;           

如下我們建立表 user_login_log, 存放着使用者登入資訊. 每次使用者登入時, 都會往該表中插入一條記錄存放相關登入資訊. 這裡隻建立了示範所必需的若幹字段.

CREATE TABLE user_login_log
(
    user_id int, -- 使用者 ID, 唯一地辨別一名使用者.
    login_time timestamp without time zone,  -- 本次登入時間.
    login_ip varchar,  -- 本次登入 IP 資訊.
    login_src smallint  -- 本次登入來源: 網頁/APP...
)
DISTRIBUTED BY(user_id);           

再建立表 user_login_log_hll, 以天為粒度, 存放着該天内 user_id 資料集對應 HyperLogLog 資訊.

CREATE TABLE user_login_log_hll
(
    login_date date PRIMARY KEY,
    user_id_hll hll
)
DISTRIBUTED BY(login_date);           

之後在每次使用者登入時, 通過如下 SQL 來更新 user_login_log 表資訊:

-- 字段根據實際情況填充. 
INSERT INTO user_login_log 
VALUES('user_id', 'login_time', ...);            

對 user_login_log_hll 的更新一般有兩種模式: T + 1 更新, 實時更新.

1. 在 T + 1 更新模式中, 一般是在第 T + 1 天的淩晨時間段運作如下 SQL 為第 T 天更新資料資訊:

INSERT INTO user_login_log_hll
SELECT CURRENT_DATE - interval '1 day',
       hll_add_agg(hll_hash_integer(user_id), 17, 7)
FROM user_login_log
WHERE login_time >= (CURRENT_DATE - interval '1 day')::TIMESTAMP WITHOUT TIME ZONE
  AND login_time < CURRENT_DATE::TIMESTAMP WITHOUT TIME ZONE;           

1. 在實時更新模式中, 需要根據業務規劃預先填充 user_login_log_hll, 如下 SQL:

-- 前後 30 年.
INSERT INTO user_login_log_hll 
SELECT current_date + i, hll_empty(17,7) 
FROM generate_series(-30 * 365, 30 * 365) t(i);           

之後再每次使用者登入時, 通過 SQL 來更新 user_login_log_hll. 為了降低使用者側感覺到的時延, 對 user_login_log_hll 的更新可以以異步的方式進行.

-- 這裡 user_id, login_time 取自于使用者登入資訊. 
UPDATE user_login_log_hll 
SET user_id_hll = hll_add(user_id_hll, hll_hash_integer(user_id)) 
WHERE login_date = login_time::date;           

最後通過如下 SQL 可以在千分級誤差内快速地估算出某天/某月的日活/月活使用者數:

-- 最近一周日活估計量:
SELECT login_date, hll_cardinality(user_id_hll) as uv 
FROM user_login_log_hll 
ORDER BY login_date DESC 
LIMIT 7;           

與利用

COUNT(DISTINCT user_id)

方式得到的精确日活對比:

-- 最近三月月活估計量:
SELECT 
    extract(year from login_date) AS year, 
    extract(month from login_date) AS month, 
    hll_cardinality(hll_union_agg(user_id_hll)) AS uv 
FROM user_login_log_hll 
GROUP BY year, month 
ORDER BY year, month DESC 
LIMIT 3;           

COUNT(DISTINCT user_id)

方式得到的精确月活對比:

在 ADB PG中使用HLL　的詳細說明，可以參見　

https://help.aliyun.com/document_detail/64023.html