在 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