假设有人问你："今天全网有多少个不同的用户搜了东西？"注意关键词——不是搜了多少次（那个加个计数器就行），而是"去重后还剩多少个独立的人"。
这个问题听起来平淡无奇，却是一个让 Google、Meta、字节这种级别的公司都得"认怂"的问题。因为最朴素的解法是：把每一个出现过的 ID 都塞进一个哈希集合（HashSet）里，最后数集合大小。听起来没错，但代价是内存随数据线性增长——十亿个用户 ID 就是几十 GB 的内存，还得在成千上万台机器之间来回搬运、去重、合并。为了得到一个"准到个位数"的数字，你要付出天文级的算力和带宽。
Breaking Taps 这支播放量超过 151 万的视频，讲的就是这个"难到连 Google 都得靠随机概率"的问题，以及它的终极答案——HyperLogLog：一个能用 12 KB 内存（不管你数到一百万还是一百亿）就把"去重计数"估得只差 0.8% 的算法。本文先还原视频的核心论证，再补上视频没展开的数学内核与工程现实。
| 项目 | 内容 |
|---|---|
| 视频标题 | A problem so hard even Google relies on Random Chance |
| 频道 | Breaking Taps |
| 时长 | 12 分 06 秒 |
| 播放量 | 约 151 万（截至 2026-06） |
| 发布时间 | 约 2024 年（页面显示 "2 years ago"） |
| 核心主题 | HyperLogLog：用极小内存做大规模基数（去重计数）估计 |
视频一上来就抛出一个反直觉点："总计数"和"去重计数"是两种完全不同量级的难题。
数总数，你只要一个整数变量，每来一个就 +1，内存恒定，不管流过多大数据。但数不重复的个数（数据库里叫 cardinality，基数），你必须"记住见过的每一个值"，否则没法判断下一个是不是新的。于是内存被绑死成 O(n)。
这就是为什么"今天有多少独立用户""有多少种不同的搜索词""某列里有多少个不重复的值"这类问题在大厂是真正的硬骨头。视频用 Google 的体量点题：在这种规模下，精确去重本身就是一种奢侈。这一节是视频的"立题"部分——它先让你承认问题难，后面所有的"随机魔法"才有意义。
视频最精彩的部分，是它如何把"计数"转译成"概率"。原理分三步：
为什么？这是整个算法的灵魂。一个均匀随机比特串，开头出现 k 个连续 0 再来个 1 的概率是 2^(-k)（几何分布）。也就是说，想看到"前面有 20 个 0"的哈希值，你平均得掷约 2^20 ≈ 100 万次骰子。所以最大的前导零数，天然就是一把以 2 为底的对数标尺：R 越大，说明你"掷"得越多，即见过的不同元素越多。
视频把这一步讲得非常具象：你不是真的去存那一亿个 ID，你只盯着"最长的一串 0 有多长"，这一个数就编码了量级。这是 Flajolet-Martin 在 1985 年论文《Probabilistic Counting Algorithms for Data Base Applications》里种下的种子。
[延伸] 视频给出了直觉，但一把标尺的方差太大——运气好，第一次就掷出一长串 0，估计就炸了；运气差，永远掷不出来，估计就瘪了。
工程师的解法叫随机平均（stochastic averaging）：把哈希值劈成两段。前面 p 个 bit 用来选桶（选寄存器），把数据流均匀地分进 m = 2^p 个桶里；剩下的 bit 用来算前导零 ρ。每个桶只记自己看到的最大 ρ。最后把 m 把标尺的结果平均起来。
这一步把内存结构固定下来了：一堆寄存器，每个存一个小整数。寄存器个数 m 是你能调的精度旋钮，m 越大越准，但内存也越大。这就是 LogLog（Durand-Flajolet, 2003）的结构。
[延伸] 这是我认为视频最难在一支短视频里讲透、但最值得展开的地方。LogLog 用的是算术平均，而算术平均会被"一个特别大的桶"主导——一个异常高的 ρ 就能把整体估计拉飞，方差很大。
2007 年，Flajolet、Fusy、Gandouet、Meunier 在论文《HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm》里换了调和平均。调和平均对异常大的值天然不敏感（因为取了倒数 2^(-M[j]) 再求和）。换上调和平均后，他们严格证明了标准误差的理论下界：
$$\text{标准误差} \approx \frac{1.04}{\sqrt{m}}$$
这就是名字里 "Hyper" 的来历——它把这个估计做到了"近最优（near-optimal）"。代入 m = 16384（2^14 个桶），每个桶存 6 bit，总共 ≈ 12 KB，标准误差 ≈ 0.81%。注意一个反直觉事实：不管真实基数是十万还是百亿，这 12 KB 和这 0.81% 都不变。内存被彻底和"数据量"解耦了。
[延伸] 中间区段用调和平均公式很好，但两个极端会失真，需要两套修正：
Google 在 2013 年的工程论文《HyperLogLog in Practice》（Heule, Nunkesser, Hall）做了进一步精修：直接上 64 位哈希，于是大基数修正可以整段删掉；又对小基数引入稀疏表示——没填满的寄存器用更紧凑的方式存，进一步省内存。这就是 Google 内部和 BigQuery 用的 HyperLogLog++。
视频后半段强调了一个被低估的特性——HLL 是可合并的（mergeable）。
两台机器各跑各的，分别得到两个 HLL 结构 H_A、H_B。要算"两边并起来的总去重数"，不用把原始 ID 传来传去，只要把两个结构的寄存器逐个取 max 合并（因为同一个桶记的是各自的最大 ρ，合并后该取较大者），就得到 H_(A∪B) 的 HLL。
这点为什么致命？因为分布式系统里，搬运原始数据是最贵的操作（网络、序列化、shuffle）。HLL 让"跨机房、跨时间的去重统计"变成只搬 12 KB 的寄存器数组。这也是 Redis 提供 PFMERGE、各大数据仓库能并行算 APPROX_COUNT_DISTINCT 的底层原因。
视频诚实地摆出了代价，这也是我认为最有"成人感"的一段：HLL 不能枚举元素、不能判断"某个值在不在里面"（那是 Bloom Filter 的活），它只回答一个问题——"大约有多少个不同值"，而且有约 0.8% 的误差。
但视频的潜台词（也是我的判断）是：对绝大多数业务问题，"1,511,506" 和 "约 153 万 ±1.2 万" 没有任何区别。老板要的是"用户量级"，不是要你为了最后那 0.8% 去多烧 100 倍的机器、还让报表晚出半小时。把精度从"精确"降到"可证明的近似"，换来几个数量级的资源节省——这是一笔极度划算的交易。HyperLogLog、Bloom Filter、Count-Min Sketch、t-digest 共同构成了概率数据结构（probabilistic data structures）这一家族，背后是同一种工程哲学。
[延伸] 给一个"已 deployed"的清单，证明这不是实验室玩具：
PFADD / PFCOUNT / PFMERGE，每个 HLL 固定 12 KB。APPROX_COUNT_DISTINCT()，底层就是 HLL++。approx_count_distinct()。uniq / uniqHLL12 / uniqCombined。APPROXIMATE COUNT (DISTINCT)）……flowchart TD
A["数据流<br/>海量元素"] --> B["哈希函数 hash(x)<br/>→ 均匀随机比特串"]
B --> C{"劈成两段"}
C -->|"前 p bit"| D["选桶/寄存器索引<br/>m = 2^p 个桶"]
C -->|"剩余 bit"| E["算前导零数 ρ"]
E --> F["寄存器只存 MAX(ρ)<br/>每个桶一个整数"]
F --> G["调和平均<br/>抗异常值（Hyper 的核心）"]
G --> H{"基数落在哪段？"}
H -->|"小基数"| I["线性计数<br/>用空桶比例修正"]
H -->|"中段"| J["直接输出估计"]
H -->|"大基数"| K["碰撞修正<br/>64位哈希可省略"]
I --> L["估计值 ± ~0.8%"]
J --> L
K --> L
F -.可合并.-> M["H_A ⊕ H_B = 逐桶取MAX<br/>= H_{A∪B}，只搬12KB"]
style B fill:#fef3c7
style G fill:#dbeafe
style F fill:#dcfce7
style M fill:#fce7f3
如果你是后端/数据工程师：碰到"去重计数"需求，第一反应应该是 HLL，而不是 SELECT COUNT(DISTINCT …)。后者在大表上会触发全量 shuffle 和巨大内存占用，前者在任何支持它的引擎里都是常数内存。Redis 里建一个 HLL 做 UV 统计，几十万 QPS 也只占 12 KB；报表里把精确 distinct 换成 APPROX_COUNT_DISTINCT，常常能从"跑不出来"变成"秒出"。
如果你做实时/流式系统：HLL 的可合并性是为你量身定的。每台机器、每个时间窗口各算各的 HLL，合并时只传寄存器数组——这把"跨节点去重"的网络成本从 O(数据量) 砍到 O(桶数)。时间维度（按小时算 HLL，再合并成天/周）也天然支持。
认知层面的升级：学会给"精确"标价。很多工程师的本能是追求绝对正确，但工程是"在约束下做权衡"。HLL 教你的是一种思维框架——当误差可以证明有界、且业务能容忍时，"近似 + 极致省资源"几乎总是比"精确 + 烧光预算"更专业。下次遇到统计类需求，先问一句："这个数字需要精确到个位吗？"
避坑提醒：HLL 在低基数（比如就几十、几百个不同值）时相对误差占比变大（虽然绝对值很小），且无法回答成员查询。如果你的场景是"判断某用户是否来过"或"元素极少要精确"，别用 HLL——前者用 Bloom Filter / 集合，后者直接精确数。
PFCOUNT / PFADD / PFMERGE 三件套，配 12 KB 的官方说明，最适合上手体验。HyperLogLog 用"哈希后数前导零"这把概率标尺，把"去重计数"的内存从 O(n) 砸成恒定的 12 KB——它教给工程师最重要的一课是：很多问题不需要更准，只需要"够准且便宜得多"。
本文由「51学通信」技术团队出品。51学通信由通信行业18年老兵爱卫生（微信ID: gprshome201101）维护，聚焦5G/6G核心网、3GPP标准解读、通信前沿技术深度分析。 出版作品有《5G核心网原理与实践》《IMS原理与实践》等4本通信专业书籍。知识星球「51学通信」提供深度技术答疑和行业洞察。
诚实披露： 视频实际时长为 12 分 06 秒（低于 15 分钟软参考线），但以 151 万播放量与高密度算法内容补足；标题/频道/播放量为实时抓取的真实数据；"延伸"标注的内容（调和平均数学、论文谱系、纠偏机制、部署清单）为我的补充，非视频原话。
下一步建议： 若需要，可继续循环 Round 13（business 分类），或对本文做 PPT 化/短视频化处理（可调用 content-to-video 或 51xtx-ppt-writer）。
[!tip] 51学通信知识星球 星主：爱卫生（微信：gprshome201101）——公众号「51学通信」创办者，19 年通信行业运维与讲师经验，著有《GPRS网络信令实例详解》《EPC原理与实践》《5G核心网原理与实践》三本纸质书（各大电商平台有售）。 星球定位：深耕 5G 核心网、IMS、NFV/AI、云原生等 ICT 领域，主打运维岗位与信令分析。 当前规模：5200 篇主题 / 990 个回答，198 元/年。 加入福利：加入星球后请加爱卫生微信，拉您进知识星球年度陪伴与答疑群——不限量回复您的各种问题，另有群内分享。 AI 加持：51学通信知识星球已作为 skill 接入 WorkBuddy，使用 deepseek-4-flash 在海量星球帖子中精准找贴、找视频、找 FAQ 和案例，做总结、找文档和 PPT 等场景全覆盖。