在互联网产品的日常运营中, 经常需要统计网页的 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 更新, 实时更新.
- 在 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;- 在实时更新模式中, 需要根据业务规划预先填充 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
