挑战
统计模块分到的内存预算是 64MB。选一个网站规模,把访客灌进去,数准他们。
选你的数据结构
三种方案都能数 UV,账单完全不同。先试试直觉方案。
数据洪流台
灌数据,盯着三条内存条。撞墙了就换个数据结构再来——访客可不会等你。
目标 1 亿访客,还没开始灌。
预算线 64MB,条形线性缩放——小到看不见,正是重点;爆表部分标红
灌一次试试:每一步的内存账单会出现在这里。
三条内存条已经在跑了。HashSet 是直觉方案——先试试它。
寄存器显微镜
这是 HLL 的全部家当:16384 个桶,每桶 6 bit,合计 12KB(画面显示 128 个抽样)。每桶只记一件事:见过的最长"硬币连击"是多长。点一个桶看看。
点击任意桶查看它的记录。
抛硬币直觉实验室
HLL 的全部聪明来自一个抛硬币事实:看到"连续正面 20 连击",说明你大概率已经抛了上百万次。亲手验一下。
手动抛,看看连击纪录怎么爬。
连抛按钮:每次都是一局全新实验,看看单局有多飘。
真值 vs 估计
蓝线是真实 UV,橙线是 HLL 用 12KB 估出来的数。两条线重合到分不开,就是这 12KB 的价值。先灌点数据再回来看。
图表库加载失败(当前离线?),数据仍在上方统计区实时更新。
本页模型说明
- HashSet 按 Java HashMap 平均每条目约 72 字节计(16 字符 ID),不同语言量级相同。
- Bitmap 需要连续整数 ID;真实访客 ID 是任意字符串,给字符串发号本身要先记住发过号的 ID——发号表就是另一个 HashSet。
- HLL 参数 16384 桶 × 6bit,与 Redis 稠密编码一致,理论标准差 0.81%;本页用 32 位演示哈希,生产实现普遍用 64 位。
- 全部计算在你的浏览器里完成,没有后端。
出处:Flajolet 等,HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm, 2007;Redis PFCOUNT / PFADD 文档。