# 随机反而数得准：12KB 凭什么数清十亿个不重复的值 ## 导语：一个把 Google 逼到"掷骰子"的问题 假设有人问你："今天全网有多少个**不同的**用户搜了东西？"注意关键词——不是搜了多少次（那个加个计数器就行），而是"**去重后**还剩多少个独立的人"。 这个问题听起来平淡无奇，却是一个让 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 的体量点题：在这种规模下，**精确去重本身就是一种奢侈**。这一节是视频的"立题"部分——它先让你承认问题难，后面所有的"随机魔法"才有意义。 ### 二、核心魔法：把每个元素变成一次"掷骰子" 视频最精彩的部分，是它如何把"计数"转译成"概率"。原理分三步： 1. **哈希化**：把每个元素（用户 ID、URL……）丢进一个好的哈希函数。好哈希函数的输出**在位级别上看起来像均匀随机数**——0 和 1 各半，每一位独立。 2. **数前导零**：看这个哈希值从左数，连续有几个 0 才出现第一个 1。这个位置记作 ρ（rho）。 3. **读"标尺"**：在一批数据里，记录你见过的**最大前导零数 R**。结论是——你大约见过 **2^R 个不同元素**。 为什么？这是整个算法的灵魂。一个均匀随机比特串，开头出现 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）的结构。 ### 四、"Hyper"的关键：调和平均压扁方差 [延伸] 这是我认为视频最难在一支短视频里讲透、但最值得展开的地方。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% 都不变**。内存被彻底和"数据量"解耦了。 ### 五、两头的纠偏：小基数看"空桶比例"，大基数防"哈希碰撞" [延伸] 中间区段用调和平均公式很好，但两个极端会失真，需要两套修正： - **小基数修正**：当数据很少时，很多桶根本没被填，寄存器还是 0。这时改用**线性计数（Linear Counting）**——用"空桶的比例"反推基数（概率论经典：m 个桶里投 n 个球，空桶数的期望有闭式解）。这比调和平均公式在低基数区更准。 - **大基数修正**：当基数逼近哈希空间上限（如 2^32）时，前导零的"标尺"开始撞天花板，出现可预测的偏差，需要按公式补偿。 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"的清单，证明这不是实验室玩具： - **Redis**：`PFADD` / `PFCOUNT` / `PFMERGE`，每个 HLL 固定 12 KB。 - **Google BigQuery**：`APPROX_COUNT_DISTINCT()`，底层就是 HLL++。 - **Apache Spark**：`approx_count_distinct()`。 - **ClickHouse**：`uniq` / `uniqHLL12` / `uniqCombined`。 - **Druid、Presto/Trino、Elasticsearch、Aerospike、Vertica、Amazon Redshift**（`APPROXIMATE COUNT (DISTINCT)`）…… - Google、Meta、Twitter 内部的各种 UV/独立搜索词统计。 ## 知识结构图 ```mermaid flowchart TD A["数据流
海量元素"] --> B["哈希函数 hash(x)
→ 均匀随机比特串"] B --> C{"劈成两段"} C -->|"前 p bit"| D["选桶/寄存器索引
m = 2^p 个桶"] C -->|"剩余 bit"| E["算前导零数 ρ"] E --> F["寄存器只存 MAX(ρ)
每个桶一个整数"] F --> G["调和平均
抗异常值（Hyper 的核心）"] G --> H{"基数落在哪段？"} H -->|"小基数"| I["线性计数
用空桶比例修正"] H -->|"中段"| J["直接输出估计"] H -->|"大基数"| K["碰撞修正
64位哈希可省略"] I --> L["估计值 ± ~0.8%"] J --> L K --> L F -.可合并.-> M["H_A ⊕ H_B = 逐桶取MAX
= 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 / 集合，后者直接精确数。 ## 延伸学习路径 1. **原始论文**：Flajolet et al., *HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm* (AOFA 2007)——算法的圣经，含 1.04/√m 的完整证明。 2. **Google 工程版**：Heule, Nunkesser, Hall, *HyperLogLog in Practice* (2013)——看 HLL++ 如何把理论工程化（64 位哈希、稀疏表示）。 3. **Redis 官方文档**：`PFCOUNT` / `PFADD` / `PFMERGE` 三件套，配 12 KB 的官方说明，最适合上手体验。 4. **"Engineering Quotes" 系列博客 / "Discovering HyperLogLog" (Redis Labs)**——把前导零标尺讲得最直观的科普文之一。 5. **配套阅读：概率数据结构家族**——Bloom Filter（成员查询）、Count-Min Sketch（频率估计）、t-digest（分位数估计）。看懂 HLL 后，这几个是同一哲学的"姐妹篇"。 ## 一句话总结 HyperLogLog 用"哈希后数前导零"这把概率标尺，把"去重计数"的内存从 O(n) 砸成恒定的 12 KB——它教给工程师最重要的一课是：**很多问题不需要更准，只需要"够准且便宜得多"**。 ## 参考来源 1. [A problem so hard even Google relies on Random Chance — Breaking Taps](https://www.youtube.com/watch?v=lJYufx0bfpw) — 本文分析的核心视频（约 151 万播放） 2. [HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm — Flajolet et al., 2007](https://hal.inria.fr/inria-00075477/document) — 算法原始论文 3. [HyperLogLog in Practice: Algorithmic Engineering of a State of The Art Cardinality Estimation Algorithm — Google, 2013](https://research.google/pubs/pub40671/) — Google HLL++ 工程实现 4. [Redis Documentation — HyperLogLog (PFCOUNT/PFADD/PFMERGE)](https://redis.io/docs/latest/develop/data-types/probabilistic/hyperloglog/) — 生产环境 12 KB 实现 5. [Probabilistic Counting Algorithms for Data Base Applications — Flajolet & Martin, 1985](https://www.sciencedirect.com/science/article/pii/S0022000085800418) — 整条技术线的起点 > 本文由「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 等场景全覆盖。