双十一亿级用户日活统计：HyperLogLog

一、需求

统计 UV（独立访客）： - 1 亿用户。 - 每天去重计数。 - 内存不能太大。

二、为什么不用 Set

SADD uv:20241111 user1 user2 ...
SCARD uv:20241111

1 亿用户，每个用户 ID 8 字节，一天就 800MB，一个月 24GB。太贵。

三、HyperLogLog

Redis 的 HyperLogLog 用概率算法，固定 12KB 内存，能统计 2^64 个元素的基数，误差 0.81%。

PFADD uv:20241111 user1 user2 ...
PFCOUNT uv:20241111

四、原理

思想

随机哈希后，二进制开头连续 0 的个数 k。观察到 k 越大，说明样本越多。

样本 1: 0010... → k=2
样本 2: 1000... → k=0
样本 3: 0001... → k=3
最大 k=3 → 估计基数 ≈ 2^3 = 8

分桶

分 16384 个桶，每个桶记自己的最大 k，最后调和平均。

五、合并

多日/多渠道合并：

PFMERGE uv:week uv:mon1 uv:mon2 ...

六、误差

标准误差 0.81%。对于"日活 UV"这种量级，完全够用。

七、适用场景

• UV 统计。
• 页面访问量去重。
• 不需要精确值的场景。

八、不适用

• 需要精确去重。
• 需要返回具体用户列表（用 Set/Bitmap）。

九、Bitmap 对比

Bitmap 也能做 UV： - 用户 ID 映射到位。 - 一个用户 1 bit。 - 1 亿用户 = 12.5MB。

比 HyperLogLog 大，但精确。HyperLogLog 12KB，近似。

	Set	Bitmap	HyperLogLog
内存	大	中	极小
精度	精确	精确	0.81% 误差
合并	麻烦	OR	PFMERGE

双十一

1 亿 DAU，HyperLogLog 一天 12KB，一个月 360KB，几乎免费。