它是什么
在大规模下，精确的答案内存成本太高：统计每个不同的用户、每个 key 的频率，或”我见过这个条目吗”，所需的状态都与数据量成正比。概率型数据结构用一个小的、有界的、可预测的误差，换取不随数据增长的内存。有四种值得了解，各自回答不同的问题：
| 结构 | 它回答的问题 | 误差 | 内存 |
|---|---|---|---|
| Count-Min Sketch | ”key X 大约出现了多少次？“ | 只会高估，不会低估 | 由你想要的误差决定，而不是由 key 的数量决定 |
| Space-Saving（heavy hitters） | “哪些 key 最频繁？“ | 对被追踪的 key 有界的高估 | 固定数量的候选 key |
| HyperLogLog | ”我大约见过多少个不同的条目？“ | 一个小的标准误差，通常在 1% 以内 | 几 KB |
| Bloom filter | ”我是否肯定没见过 X？“ | 有假阳性，没有假阴性 | 约每个条目 10 bit，对应 1% 的假阳性 |
Important
核心要点： 按问题来选结构，而不是按你熟悉的工具。单独的 Count-Min Sketch 无法列出 top-K 的 key（它不存 key）；Bloom filter 不能计数；HyperLogLog 说不出看到过哪些条目。要说出你接受的误差，以及它换来的内存。
何时需要它
Top-K 趋势、独立访客、去重，以及放在数据库前面的”这个 key 存在吗”检查，都会用到它们。标准的陷阱是对 top-K 说出 Count-Min Sketch 就停下。
Note
面试信号： 说”单靠 Count-Min Sketch 不够做 top-K，因为它无法枚举它的 key；要配合一个堆，或使用 Space-Saving”，是对 top-K 这道题的资深回答。再补上内存算术，才让它具体起来。
Count-Min Sketch
直觉。 不为每个 key 开一个槽来统计频率：用一个 d 行 w 列的计数器网格，每一行一个哈希函数。增加一个 key 会在每一行里给一个格子加一。要估计一个 key，读出它在每一行中的格子，取最小值：冲突只会抬高一个格子，不会降低它，所以最小值是最紧的上界。
| col 0 | col 1 | col 2 | col 3 | col 4 | |
|---|---|---|---|---|---|
| row 0 (h₁) | 3 | 1 | 5 | 2 | 0 |
| row 1 (h₂) | 0 | 4 | 1 | 3 | 2 |
| row 2 (h₃) | 2 | 0 | 3 | 1 | 4 |
估计 #superbowl：它哈希到的三个格子分别是 5、4、4，所以估计值是 min(5, 4, 4) = 4。
误差界。 取 w = ⌈e ÷ ε⌉ 列和 d = ⌈ln(1 ÷ δ)⌉ 行，估计值以概率 1 − δ 落在真实计数的 ε × N 以内（N 是事件总数）。
算例。 取 ε = 0.001、δ = 0.01。则 w ≈ 2,718，d ≈ 5，所以这个 sketch 占 5 × 2,718 × 4 字节 ≈ 54 KB，无论有多少不同的 key。在每秒 100 万个事件持续一小时的情况下，N 是 36 亿，所以每个 key 的误差至多约 360 万。真实计数远高于这个值的 key 能被很好地分辨；低于它的则无法区分。对于计数在几千万的热门话题标签，这已经足够。大小只取决于你选的误差，与 key 的数量无关。
Space-Saving（heavy hitters）
保存一个固定大小的、包含 m 个候选 key 及其计数的映射，其中 m 大于 K（对 top-100 约为 10 K）。对每个事件：
- 如果 key 在映射里，就给它加一。
- 否则如果映射还有空位，就以计数 1 加入它。
- 否则淘汰计数最小的条目，并以
min + 1的计数插入新 key。新 key 继承被淘汰者的计数，这就是 “saving” 的由来。
在 m = 4 下对流 A A B A C D D D E 的追踪：
| 事件 | 之后的映射 | 动作 |
|---|---|---|
| A, A | A:2 | 插入，然后加一 |
| B | A:2, B:1 | 插入 |
| A | A:3, B:1 | 加一 |
| C | A:3, B:1, C:1 | 插入 |
| D | A:3, B:1, C:1, D:1 | 插入（映射已满） |
| D, D | A:3, B:1, C:1, D:3 | 加一两次 |
| E | A:3, C:1, D:3, E:2 | 最小的是 B（1）；淘汰 B；E 以 1 + 1 = 2 进入 |
A 和 D 正确地成为前两名。E 被追踪为 2，是一个高估（它的真实计数是 1），而 B 已经没了。这个淘汰规则让一个真正走红的新 key 能很快浮现出来。
为什么不直接用 Count-Min Sketch 加一个堆？ 由 sketch 喂数据的候选堆有一个延迟问题：一个新的热门 key 必须累积足够的估计计数，才能超过当前第 K 名并进入堆。如果第 100 名是 150,000，一个走红的新话题标签必须先达到这个数才会出现，可能落后现实好几分钟。Space-Saving 会立刻接纳它。另外保留一个 Count-Min Sketch，用来回答另一个问题：“key X 出现了多少次？“，针对不在被追踪列表里的 key。
HyperLogLog
统计不同条目的数量。思路：把每个条目哈希成一个比特串，并为每个桶记录见过的最长前导零序列。长的序列是稀有事件，所以看到一个，就说明哈希过很多不同的条目。在许多桶之间取平均可以降低方差。
算例。 用 16,384 个寄存器，标准的 HyperLogLog 使用约 12 KB，标准误差约 0.8%，无论它看到的是一千个还是十亿个条目。Sketch 可以合并（取每个寄存器的最大值），所以每日的 sketch 可以组合成每周的去重计数，而不需要重新处理。它说不出看到过哪些条目，也无法删除一个条目。
Bloom filter
一个 m 位的比特数组和 k 个哈希函数。添加一个条目时，设置 k 个比特。测试时，检查那 k 个比特：只要有一个是 0，这个条目就肯定不存在；如果全是 1，它就是可能存在（其他条目可能设置了这些比特）。没有假阴性，假阳性率可调，大约是 (1 − e^(−kn/m))^k。
算例。 在每个条目约 10 bit、7 个哈希函数时，假阳性率约 1%。十亿个条目大约需要 10⁹ × 10 bit ≈ 1.25 GB。放在数据库前面，一个由合法 key 构成的 Bloom filter 能廉价地拒绝那 99% 不可能的查找；LSM 存储引擎在每个文件上用一个，来跳过不可能包含该 key 的文件。它不能删除条目（计数型的变体可以，代价是更多内存），也不能计数。
如何选择
| 需求 | 选择 | 原因 |
|---|---|---|
| 某个给定 key 的频率 | Count-Min Sketch | 内存固定，只会高估 |
| 最频繁的前 K 个 key，且新鲜度重要 | Space-Saving（再配一个 sketch 来做点计数） | 能快速接纳新 key |
| 去重计数（独立访客） | HyperLogLog | 只要几 KB，可合并 |
| 在昂贵的查找之前问”这个 key 可能在集合里吗？“ | Bloom filter | 没有假阴性 |
| 精确计数、计费 | 不要用这些：用精确聚合，可以另用 sketch 做监控 | 近似不可接受 |
Caution
常见错误： 在数字会变成钱或法律主张的地方使用近似结构。这些误差有界，但是真实存在的：计费要基于精确的聚合，sketch 用于看板、异常检测和容量决策。
相关
- 演练：设计 Top K 系统 — 在事件洪流上找 heavy hitters，单靠 Count-Min Sketch 不够。
- 参考：存储引擎——B-Tree、LSM-Tree 与 Bitcask — 每个文件一个 Bloom filter，是 LSM-tree 的标准读优化。
- 参考：缓存访问与失效模式 — 放在数据库前面的 Bloom filter 能挡住缓存穿透。