12KB 记住一亿人

今天有 1 亿人访问了你的网站。统计独立访客数:HashSet 要 7.2GB,HyperLogLog 只要 12KB。代价是不到 1% 的误差——下面亲手验证这句话。

挑战

统计模块分到的内存预算是 64MB。选一个网站规模,把访客灌进去,数准他们。

选你的数据结构

三种方案都能数 UV,账单完全不同。先试试直觉方案。

数据洪流台

灌数据,盯着三条内存条。撞墙了就换个数据结构再来——访客可不会等你。

目标 1 亿访客,还没开始灌。
已接待请求
0
真实 UV
0
HLL 估计
0
偏差
—
HashSet
0 B
Bitmap
0 B
HLL
12.0 KB
预算线 64MB,条形线性缩放——小到看不见,正是重点;爆表部分标红
灌一次试试:每一步的内存账单会出现在这里。
三条内存条已经在跑了。HashSet 是直觉方案——先试试它。

寄存器显微镜

这是 HLL 的全部家当:16384 个桶,每桶 6 bit,合计 12KB(画面显示 128 个抽样)。每桶只记一件事:见过的最长"硬币连击"是多长。点一个桶看看。

点击任意桶查看它的记录。

抛硬币直觉实验室

HLL 的全部聪明来自一个抛硬币事实:看到"连续正面 20 连击",说明你大概率已经抛了上百万次。亲手验一下。

已抛次数0
最长正面连击0
2^连击 反推1
手动抛,看看连击纪录怎么爬。
连抛按钮:每次都是一局全新实验,看看单局有多飘。

真值 vs 估计

蓝线是真实 UV,橙线是 HLL 用 12KB 估出来的数。两条线重合到分不开,就是这 12KB 的价值。先灌点数据再回来看。

本页模型说明

出处:Flajolet 等,HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm, 2007;Redis PFCOUNT / PFADD 文档。