05 精确与近似的权衡：用一点点错误换几个数量级

开篇提问

先给你一道题，凭直觉猜答案：

一个网站有 10 亿条独立访客（UV），你要统计”今天的独立访客数”。用最省内存的方式，需要多少内存？

用 Set 精确存储每个用户 ID：10 亿 × 8 字节（假设用 64 位哈希值）= 8GB。而且这还只是一个指标的统计。

但如果我告诉你，用 1.5KB 内存就能做到，误差只有 2%，你会不会觉得我在骗你？

这不是魔术，这是一类算法的真实能力——概率数据结构（probabilistic data structures）。

那么问题来了，请往深里想：

为什么”允许一点点错误”能换来这么夸张的资源节省？这个交换的物理根源是什么？而且——什么时候你能接受”错 2%“，什么时候绝对不行？

子主题一：精确性的代价——信息量的下界

要理解”为什么近似能省这么多”，先要理解”为什么精确这么贵”。

这背后有个非常硬的原理，来自信息论：

要精确表示 N 个不同状态，你至少需要 log₂(N) 个比特。这是信息论下界，无法绕过。

具体到我们的例子：

要精确记录”这 10 亿个用户里哪些来过”，你需要能区分 2^(10亿) 种可能的集合状态——这需要海量比特。
实际上，精确去重需要存储每个元素的标识（或其完整哈希），所以空间至少随元素数量线性增长。

关键洞察：精确性的代价是”线性”的——你要区分的状态每多一个，就要多存一点信息。

而近似算法打破这个下界的方式非常巧妙：它不再试图区分所有状态，只试图给出一个”够用的估计”。

只要你不需要”精确知道是哪 10 亿个人”，只需要”知道大概有 10 亿”——你就把需要存储的信息量，从”10 亿个标识”压缩成了”一个数”。

信息的压缩，来自于需求的放宽。 这是这一章最核心的一句话。

子主题二：概率数据结构三剑客

我们来具体看几个经典的概率数据结构，理解它们是怎么做到”用小空间换 approximate 答案”的。

Bloom Filter（布隆过滤器）：回答”在不在”

结构：一个很长的位数组（比如 m 位）+ k 个独立的哈希函数。
插入：把元素用 k 个哈希函数算出 k 个位置，把这些位置置 1。
查询：算出 k 个位置，如果全是 1，则回答”可能存在”；只要有一个是 0，则回答”一定不存在”。
特性：不会漏报（false negative 为 0），但会误报（false positive）。
空间：每个元素大约 10 个位（在 1% 误报率下），比存完整哈希（64 位）省 6 倍以上。

它的精妙在哪？它用”允许误报”换来了”绝不漏报”和极致的空间效率。 而且这个”允许误报”的方向，恰好适配了大量真实场景——先用 Bloom Filter 挡掉”一定不存在”的请求，只对”可能存在”的去查昂贵的存储。

HyperLogLog：回答”有多少个不同的”

结构：一组寄存器（通常几千字节）。
原理（直觉版）：观察元素哈希值的二进制表示里，“前导零的最大长度”。如果看到某个元素哈希值前导零有 20 个，那大约意味着见过了 2^20 个不同元素——因为这种”极端模式”在随机哈希里很罕见，罕见程度本身就编码了基数信息。
用分桶 + 调和平均来降低单个极端值的方差。
空间：约 1.5KB 就能估算 10 亿级基数，标准误差约 2%。

它的精妙在于：它根本不存储任何元素，只存储”统计特征的摘要”。 信息被压缩到了极致——从”存 10 亿个 ID”变成”存一个能反推基数的统计量”。

Count-Min Sketch：回答”出现了几次”

结构：一个二维计数数组 + 多个哈希函数。
原理：类似 Bloom Filter 的计数版，每个哈希函数对应一行，元素映射到每行的某个位置，计数加一。查询时取所有行的最小值。
特性：可能高估，但不会低估（因为冲突只会让计数变大）。
用途：统计热点、频率估计、heavy hitters。

子主题三：为什么”不会低估”或”不会漏报”的方向性这么重要

注意到上面三个结构各自有一个”方向性保证”：

Bloom Filter：绝不漏报（可能误报）
HyperLogLog：无方向性，但误差可控在 ±2%
Count-Min Sketch：绝不低估（可能高估）

这个”方向性”不是巧合，而是概率数据结构设计的核心艺术：让错误发生在”无害的方向”上。

为什么这很重要？因为真实场景里，两种错误的代价完全不对称：

缓存穿透防护：用 Bloom Filter 挡”不存在的 key”。误报（说存在、其实不存在）只是多查一次数据库，无害；漏报（说不存在、其实存在）会导致本该命中的数据被拒绝，有害。所以 Bloom Filter 的”绝不漏报”正好适配。
限流计数：Count-Min Sketch 高估计数，意味着”稍微多限了一点”，无害；低估意味着”限流失效打爆后端”，有害。所以”绝不低估”正好适配。

这是一个极其重要的设计思想，你可以推广到整个工程领域：

当你无法消除错误时，想办法让错误只发生在代价小的那个方向上。

这比”降低错误率”更聪明——因为降低错误率往往要付出指数级的资源代价，而定向错误几乎免费。

子主题四：除了数据结构，近似还能怎么用

“用精度换资源”这个思路，远不止于概率数据结构，它在计算机领域处处可见：

采样（Sampling）：不看全量，只看一部分。监控指标采样、A/B 测试、数据库的表统计信息（PostgreSQL 的 ANALYZE 就是采样的）。 有损压缩（Lossy Compression）：JPEG、MP3、视频编码——丢弃人眼/人耳感知不到的信息，换来数量级的体积缩小。这可能是”近似思想”最成功的商业应用。 近似查询处理（AQP）：数据库对海量数据做”在线聚合”时，用抽样给出带置信区间的近似答案，而不是精确扫描全表。 机器学习本身：严格来说，所有监督学习模型都是”用可容忍的错误，换取对未知数据的泛化能力”。 近似最近邻搜索（ANN）：向量数据库里的 HNSW、IVF 等索引，牺牲一点召回率换取千倍的查询速度。

你发现共同点了吗？它们都在做同一件事：识别出”哪些信息是真正被需要的”，然后把其余的丢掉。

子主题五：什么时候绝对不能近似

讲了这么多近似的好处，必须说清楚边界。以下场景，近似是不可接受的：

场景一：涉及钱和账。 账户余额、交易金额、对账——这些必须精确。误差 2% 在 UV 统计里无所谓，在账本里是灾难。（注：即便是金融系统，也会在某些环节用近似——比如风控的统计特征——但记账环节必须精确。）

场景二：涉及安全和权限。 “这个用户有没有权限”不能回答”大概有”。安全判定必须是确定性的。

场景三：涉及正确性判定的控制流。 比如”这个事务是否冲突”、“这个锁是否可获取”——这些决定系统正确性的判断不能近似。

场景四：误差会累积的场景。 单次 2% 的误差无所谓，但如果这个近似结果被反复使用、层层叠加，误差会放大到失控。

判断的通用标准就一条：

问一句：“如果这个值错了（偏大或偏小），会发生什么？” 如果后果可接受，就能近似；如果后果不可接受，就必须精确。

而且注意：同一个系统里，不同数据可以有不同的精度要求。 好的系统会精确地划出”哪部分必须精确”（通常是很小的一部分），其余的放宽——这才是真实工程里的做法，而不是一刀切。

子主题六：Bloom Filter 深挖——误报率是从哪儿长出来的

开篇我们说 Bloom Filter “每个元素约 10 个位，误报率约 1%“。现在把这些数字背后的机制拆开。

先想一个问题：误报到底是怎么发生的？

查询一个从没插入过的元素 x，算出 k 个位置，结果这 k 个位恰好都被别人置成 1 了。这就是误报的全部成因——不是什么玄学，就是”撞车”。

那么误报率由什么决定？只有两件事：

第一，位数组有多满。 设 m 个位、n 个元素、k 个哈希函数。插入 n 个元素一共做了 kn 次置位（含重复），某个特定位始终没被碰到的概率约为 e^(-kn/m)。反过来，某一位是 1 的概率约为 1 - e^(-kn/m)。于是 k 个位置全是 1 的概率就是：

误报率 ≈ (1 - e^(-kn/m))^k

看这个式子，很直白：位数组越长（m/n 越大），越空旷，越不容易撞车。

第二，哈希函数个数 k。 这里有个反直觉的地方，值得停下来想一秒：

k 太小（比如 k=1）：只要一个位撞上就误报，门槛太低；
k 太大（比如 k=100）：每个元素要置 100 个位，位数组迅速被填满，满到什么查询都全是 1。

所以 k 不是越大越好，也不是越小越好，中间存在一个最优值。对上面的式子求极值，得到：

最优 k = (m/n) · ln2 ≈ 0.693 · (m/n)

在这个最优点上，误报率约等于 0.6185^(m/n)。代入 m/n = 10，得到约 0.8%——这就对上了”每个元素 10 个位、误报率约 1%“这个广为流传的量级，此时最优 k ≈ 7。

再给你一条好记的经验律，从 0.6185^(m/n) 直接推出来：

每给每个元素多加约 5 个位，误报率就掉一个数量级。

m/n=10 约 1%，m/n=15 约 0.1%，m/n=20 约 0.01%。注意这条曲线的形状：误报率是随空间线性投入而指数下降的。这是”精确与近似权衡”里最漂亮的一条曲线——你花的是加法，买到的是乘法。也正因为如此，追求极低误报率并不划算到荒谬：从 1% 压到 0.01% 只需要多一倍空间。

但这不是免费的：误报率越低，越逼近代价的下界。 因为 Bloom Filter 有个理论下界——要达到误报率 ε，每个元素至少需要 log₂(1/ε) / ln2 ≈ 1.44·log₂(1/ε) 个位。1% 就是约 9.6 位，0.1% 约 14.4 位。你不可能用 2 个位做到 1% 误报，这是被证明过的硬底，再聪明的工程也绕不过去。

现在到第二个问题：为什么 Bloom Filter 不能删除元素？

想一想删除意味着什么——把 k 个位置从 1 改回 0。可问题是：这些位不是 x 独占的。

一个生活化的类比：你和朋友合租一间房，门口只有一个”屋里有人”的牌子。你出门时把牌子翻成”没人”——但你的室友还在屋里睡觉。你的”删除”抹掉了别人的存在。

技术后果是什么？清零之后，某个真正在集合里的元素 y 查询时会遇到 0，于是返回”不存在”——假阴性出现了。而假阴性直接摧毁 Bloom Filter 唯一的、也是全部的承诺：“绝不漏报”。

所以标准 Bloom Filter 干脆不支持删除。这不是实现偷懒，是结构性的限制：共享位 + 不可逆的或操作 = 无法撤销。

怎么解决？Counting Bloom Filter（CBF）。

思路朴素得令人发笑：位不够用，就换成计数器。

每个位置不再是一个比特，而是一个小计数器（通常 4 位，够数到 15）；
插入：k 个位置的计数各 +1；
删除：k 个位置的计数各 -1；
查询：k 个位置的计数都 > 0，才算”可能存在”。

这样删除就安全了：只有当某个位置的计数降到 0，才说明”确实没有元素依赖这一位”。

代价是什么？

空间放大约 4 倍（每位置从 1 位变 4 位）。你用 4 倍空间买回了删除能力。
溢出风险：4 位只能数到 15，同一个位置被 16 个元素撞上就溢出。真实系统要么加大计数器，要么接受”计数饱和”（饱和后表现为”永远存在”，误差落在保守方向），要么定期重建。
删除不存在的元素会污染结构：如果你删除一个从未插入的元素，会把不该减的计数减掉，制造假阴性。CBF 要求”只能删除确实插入过的”——这个前提在很多业务里其实并不成立，是踩坑高发区。

还有更好的选择吗？有，而且现在更流行：Cuckoo Filter（布谷鸟过滤器）。

它换了个完全不同的思路：不存位，而是存元素的指纹（fingerprint，几个字节的哈希片段），用布谷鸟哈希的方式放在桶里，每个元素只有两个候选桶。

删除：找到指纹，删掉即可，完全安全；
查询：查两个桶里有没有这个指纹；
优势：支持删除、支持计数、在误报率低于约 3% 时空间效率优于 Bloom Filter、缓存局部性更好（查的是连续的两个桶，而不是 k 个随机跳跃的内存位置）。

这里有个值得记住的工程细节：Bloom Filter 的 k 次哈希是 k 次随机内存访问，在 CPU 眼里意味着 k 次大概率的 cache miss；Cuckoo Filter 只查两个桶，访问更局部。所以当位数组大到放不进内存时，Cuckoo Filter 的实际延迟往往更好。这也是”理论空间”和”真实性能”不是一回事的典型例子。

其它常见变体，一句话带过：

Scalable Bloom Filter：位数组满了就再叠一层（每层误报率按几何级数收紧），整体误报率有界，适合元素总量无法预估的场景。
Stable Bloom Filter / 滑动窗口 Bloom：给位加”老化”机制，用于”最近一段时间内是否出现过”的判重，比如流式去重。
Blocking Bloom Filter：把位数组切成块，每块放进一个 cache line，一次查询只访问一块，换取极低的 cache miss。

第三个问题：它在真实系统里到底用在哪？

（1）缓存穿透防护——最经典的用法

场景：攻击者或爬虫疯狂请求不存在的 key，缓存永远不命中，请求全部打到数据库，数据库被打挂。这就是”缓存穿透”。

Bloom Filter 怎么救场？把所有合法 key 预先放进 Bloom Filter，查询先问它：

说”不存在”→ 一定不存在 → 直接返回空，连缓存都不用查；
说”存在”→ 大概率存在 → 正常走缓存 → 缓存没命中再查库。

结果：穿透流量被完全挡在外面，数据库一根毛都碰不到。 误报的那 1% 只是多走一次缓存查询，代价几乎为零。

注意这个设计的方向性多么完美——它恰好把错误放在了无害的那一侧。

（2）数据库查询前置过滤——LSM 树的标配

这个用得比缓存穿透还广，但很多人不知道。

LevelDB / RocksDB / Cassandra / HBase 都基于 LSM 树，数据分层存放在磁盘上的 SSTable 文件里。查询一个 key 时，如果它在某一层不存在，你本该把这个文件读一遍才能确认——而读磁盘是最贵的操作。

于是：每个 SSTable 附带一个 Bloom Filter。查询时先问 Bloom Filter：“这个 key 在这个文件里吗？“——说不在，就完全跳过这个文件。

这一步把 LSM 树的读放大（read amplification）压下来一个数量级。你每查一次 RocksDB，背后都有 Bloom Filter 在替你省下几十次磁盘读。

同样的思想往外接就是：

分布式 Join：把小表的 key 做成 Bloom Filter 广播到大表所在的节点，本地先过滤掉”注定连不上”的行，再传输——省的是网络。
CDN / 反向代理分层：查询上级缓存前先用 Bloom Filter 判断”这内容我这儿存过吗”，避免无谓的回源。
Chrome 的 Safe Browsing：把恶意 URL 的前缀集合以 Bloom Filter 形式放在本地，绝大多数正常 URL 本地就能判定安全，只有”可能命中”的才发请求到服务端确认——省了网络，还顺带保护了隐私（服务端不知道你浏览了什么，只知道你访问了一小批”可疑候选”）。

留意最后这个例子：Bloom Filter 在这里同时买了两样东西——性能和隐私。当你的数据根本没离开本地，隐私问题是自动解决的。 这是”不精确”带来的意外红利。

（3）爬虫 URL 去重

一个搜索引擎爬虫要抓几十亿 URL，怎么判断”这个 URL 抓过了”？

用 Set 存：几十亿条完整 URL，几百 GB 起，还要考虑分布式同步。
用 Bloom Filter：每个 URL 约 10 位，几十亿 URL 也就几 GB，甚至可以单机放下。

误报的后果是什么？误报 = 以为抓过、实际没抓 = 少抓一个页面。 对搜索引擎来说，漏抓一个页面是无害的（反正索引本身就是不完整的近似）。而漏报（以为没抓过、实际抓过）只是重复抓一次，也是无害的。两个方向都无害，那还犹豫什么？

这也是一个通用的判断技巧：当一个场景里”两种错误都无害”时，近似几乎是免费的午餐。

子主题七：HyperLogLog 深挖——前导零为什么能编码基数

上一节 Bloom Filter 回答”在不在”，现在来看”有多少个不同的”——这是更难的问题，因为它要求的是全局统计量，而不是单元素判定。

先建立直觉：为什么哈希值的”前导零长度”能告诉我们见过多少元素？

把所有元素哈希成均匀随机的比特串（想象成无限长的硬币序列）。对每个元素，数一数它的哈希值开头有多少个连续的 0，记为 ρ。

现在抛一个硬币游戏的问题给你：

连续抛硬币，要抛到”连续 3 次都是反面”，期望需要抛多少次？

答案是 2³ = 8 次。要”连续 20 次反面”，期望是 2²⁰ ≈ 100 万次。

这就是全部秘密。

哈希值是随机比特串，“前导零长度达到 r”就等价于”连续 r 次反面”。一个随机串满足它的概率是 2

如果你观察到的最大前导零长度是 r，那你大概已经见过 2^r 个不同的元素了。

注意这个推理的精妙之处：信息不是存在”哪个元素”里，而是存在”极端事件的罕见程度”里。 你不需要记住任何一个 ID，你只需要记住”我见过的最离谱的巧合有多离谱”。

打个更狠的比方：你在一个城市随机拦人问生日。如果你拦了 20 个人就遇到一个 1 月 1 日出生的，你会觉得这个城市人不多；如果你拦了两万人才遇到第一个 1 月 1 日出生的，你会觉得这城市人很多。“稀有事件出现得有多晚”本身就是人口规模的刻度。 而 HyperLogLog 用的稀有事件，是”哈希值前导零很长”。

但这里有个致命问题：单次估计的方差大到没法用。

想一想 ρ 这个随机变量的行为。它的取值是 0, 1, 2, 3……大部分时候很小，偶尔蹦出一个大的。它的分布是重尾的：P(ρ ≥ r) = 2

后果：单次估计的相对误差是常数级的（大约 1.12 附近），完全不随数据量增大而减小。 你见了一百万个元素，估计值的误差仍然是”上下差一倍”这个水平。这样的估计器在工程中毫无价值。

怎么办？分桶 + 平均。 这是统计学里最古老也最有效的降方差手段。

分桶怎么工作？

取哈希值的前 b 位决定元素落在哪个桶（共 m = 2^b 个桶），用剩下的位计算前导零长度 ρ，每个桶只保留自己见过的最大 ρ，记为 M[j]。

插入：算出桶号 j 和剩余位的前导零 ρ，令 M[j] = max(M[j], ρ)。
每个桶相当于一个独立的”稀有事件计数器”，相当于把数据流随机分成了 m 份，每份独立估计。

于是我们只需要存 m 个数字，每个数字取值范围 0~32 左右——用 5 或 6 位就够了。

m=2048 个桶、每桶 6 位 = 12288 位 = 约 1.5KB。标准误差约 1.04/√m = 1.04/45 ≈ 2.3%。

这就对上了开篇那句”1.5KB、10 亿级基数、误差约 2%“。它不是广告词，是公式算出来的。

为什么调和平均，而不是算术平均？

这是最容易被讲错的一点，值得掰开。

如果每个桶的估计是 2

算术平均 = (1/m) · Σ 2

问题出在 2^M[j] 的分布：它是重尾的。 一个桶里只要撞上一个前导零特别长的值（比如 ρ=30），2^30 ≈ 10 亿，就能把 m=2048 个桶的算术平均整体抬高。而 ρ 的方差本来就大，这种”极端桶”出现的概率并不低。

算术平均会被离群值绑架。 这就是它高估的系统性来源。

调和平均怎么做？HLL 的估计公式是：

E = α_m · m² / (Σⱼ 2^(-M[j]))

注意分母里是 2^(-M[j])，也就是 1 / 2^M[j]。熟悉的话你会立刻认出来：这正是 2^M[j] 的调和平均的倒数形式（调和平均 H = m / Σ(1/2^M[j]) = m / Σ 2

调和平均的权重天然偏向小值：一个 2^M[j] = 10 亿的桶，取倒数后只贡献 10

一句话记住它：

算术平均问”平均每个桶看到了多罕见的事”，结果被最罕见的那个绑架；调和平均问”这些桶的罕见程度按倒数摊薄后是多少”，把离群值的喉咙掐住了。

（α_m 是一个修正常数，m=16 时约 0.673，m 很大时趋近 0.7213/(1+1.079/m)，用来修正调和平均引入的系统性偏差。你不需要记它，知道”有个常数在修正”就够了。）

有了分桶 + 调和平均，标准误差变成 1.04/√m：

桶数 m	内存（6 位/桶）	标准误差
2^11 = 2048	约 1.5KB	约 2.3%
2^14 = 16384	约 12KB	约 0.81%
2^16 = 65536	约 48KB	约 0.4%

看清楚这个关系：误差减半，需要 4 倍内存。 这是 √m 的宿命，也是所有基于采样式平均的估计器的共同宿命（和 A/B 测试的 1/√n 是同一条曲线）。

顺带一个真实数字：Redis 的 HyperLogLog 用一个 key 占约 12KB，标准误差 0.81%，不管你塞进去一百万还是十亿个元素，体积都是 12KB——空间与基数完全解耦。这是它最反直觉的地方：存 10 个元素的 HLL 和存 10 亿个元素的 HLL 一样大。

两个必须知道的工程细节

细节一：小基数时 HLL 误差很大，需要切换到 Linear Counting。

当元素很少时（比如只插入了 10 个，却有 2048 个桶），绝大多数桶的 M[j] 都是 0，调和平均的估计会严重失真。工程实现（包括 HyperLogLog++）的做法是：当估计值 E 小于约 5m/2 时，改用 Linear Counting——即根据”空桶的数量”来估计基数。空桶越多，元素越少，这个估计在小基数时反而更准。

细节二：32 位哈希在极大基数下会饱和，需要修正。

2^32 约 43 亿。当基数接近这个量级时，哈希碰撞本身开始影响估计，需要引入大范围修正项（HyperLogLog++ 的论文专门处理了这个）。

顺带说清楚 HLL 的能力边界，这点常被误解：

✅ 能合并：两个 HLL 合并只需对每个桶取 max，满足交换律和结合律。所以特别适合分布式——每台机器各算各的，最后汇总。这是它比 Set 更强的能力，Set 的合并是 O(n) 而 HLL 是 O(m)。
❌ 不能判断单个元素是否存在——它压根没存元素。
❌ 不能求交集的元素（但可以估计交集的基数，用容斥原理：|A∩B| = |A| + |B| - |A∪B|）。
❌ 不能回退、不能删除。

最后的对比：和精确 Set 差多少？

回到开篇那个 10 亿 UV 的问题：

精确 Set：10 亿 × 8 字节 ≈ 8GB（实际用哈希表还要付指针和负载因子的开销，通常 20~40GB）。
HyperLogLog（1.5KB，误差 2%）：1.5KB。

比值约 500 万倍。

而且真正的差距还不止于此。如果是分布式的、跨 100 个维度组合的 UV 统计：

精确方案：100 个 Set，要么 800GB 内存，要么做昂贵的 shuffle 去重；
HLL 方案：100 × 1.5KB = 150KB，每台机器独立算完直接合并。

这就是为什么 Redis、Druid、ClickHouse、Spark、Flink、BigQuery 全都内置了 HLL。ClickHouse 的 uniqCombined、Redis 的 PFADD/PFCOUNT、Spark 的 approx_count_distinct——你天天在用的”去重计数”，大概率已经是近似值了，只是没人告诉你。

子主题八：Count-Min Sketch 深挖——为什么要取最小值

第三个问题：“这个元素出现了多少次？”

答案：Count-Min Sketch（CM Sketch），2005 年由 Cormode 和 Muthukrishnan 提出。

先看结构，它和 Bloom Filter 是血亲：

	Bloom Filter	Count-Min Sketch
存储单元	位（0/1）	计数器（整数）
布局	一维 m 位（k 个哈希各选一个位置）	二维 d 行 × w 列，每行一个哈希
更新	置 1	+1
合并	位或	矩阵加法
查询	全 1 则”在”	取 d 行的最小值
误差方向	只误报（假阳性）	只高估
回答的问题	在不在	出现了几次

看出来了吗？Bloom Filter 其实就是 CM Sketch 的”布尔退化版”——把计数器从整数压成 1 位（加法变成”或”），就得到了 Bloom Filter。

这个对照关系值得记住，因为它揭示了一条通用的设计路径：

把某个结构的”存储单元”从布尔升级成计数，就把”存在性判定”升级成了”频率估计”。

为什么查询时要取最小值，而不是取平均或最大值？

先想清楚一行里存的是什么。设元素 x 在第 r 行的位置是 h_r(x)，那这一行的计数是：

count[r][h_r(x)] = x 的真实频次 + 所有映射到同一位置的其他元素的频次之和

也就是说：每一行的读数都是真实值的一个上界。 因为冲突只会往上加，永远不会减。

现在你有 d 个上界，怎么估真值？

取最大值：选了最松的那个上界，等于主动选了最差的估计。荒谬。
取平均：会被”某一行特别倒霉、撞上一堆高频元素”拖高。平均值没有抗离群能力。
取最小值：在 d 个上界里挑最紧的那个。

这就是名字的由来：Count-Min = 计数的最小值。

一句话：每个行读数都是”真值 + 噪声”，噪声非负；取 min 就是找噪声最小的那次试验。 这是”重复独立试验 + 取最好结果”的思路，和”抛 d 次硬币取最有利的一次”是同构的。

误差界有多强？

经典结论（Cormode & Muthukrishnan）：

取 w = ⌈e/ε⌉、d = ⌈ln(1/δ)⌉，则估计值以至少 1-δ 的概率满足： 真值 ≤ 估计值 ≤ 真值 + ε · N（N 为所有元素频次之和，即总流量）

拆开来读：

宽度 w 控制误差幅度：误差是相对于总量 N 的 ε 倍，而不是相对于元素自身频次。这意味着——低频元素的相对误差会很大，高频元素的相对误差很小。 这恰好是我们想要的：热点元素的估计很准，冷门元素根本不重要。
深度 d 控制”这个保证成立的概率”：d 每 +1，失败概率乘以 1/e。d=5 时失败概率约 0.7%。

举一个具体的量级：想要 ε = 0.1%（误差不超过总流量的千分之一）、δ = 1%（99% 概率成立）：

w = ⌈e/0.001⌉ ≈ 2718
d = ⌈ln(100)⌉ ≈ 5
总计约 13590 个计数器，4 字节一个 → 约 54KB

用 54KB 内存，给无限多种 key 做频率估计，误差不超过总流量的千分之一。想想要存”每个 key 一个计数器”需要多少内存——如果有 1 亿个 key，那是 400MB 起步，还要付哈希表的开销。差了四个数量级。

它在真实系统里干什么？

（1）热点检测 / Heavy Hitters

这是 CM Sketch 最主流的用途：从海量流水中找出”出现频率最高的那些”。

社交媒体的热搜榜单：几十亿条内容互动，找出 top-K 热门。
缓存热 key 检测：Redis 集群里找出被疯狂访问的 key，做本地缓存或打散。
DDoS / 异常流量识别：找出访问频次异常高的源 IP 或目标 URL。
数据库的频率估计：查询优化器需要知道”这个列里最频繁的值是什么”来做选择性估计，用 sketch 比扫全表便宜得多。

怎么找 top-K？CM Sketch 本身只能做点查询（“这个元素出现了几次”），要找 top-K 需要配合一个大小为 K 的最小堆：来一个元素查一次 sketch，估计值超过堆顶就替换。这个组合叫 CM Sketch + Heap，是标准的 heavy hitters 方案。

不过要诚实地说：如果只关心 top-K 而不关心任意元素的精确频次，有更好的结构——Misra-Gries（也叫 Frequent）、Space-Saving、Lossy Counting。它们用 O(K) 的空间给出 top-K 的确定性保证（Misra-Gries 保证”频次超过 N/K 的元素一定被找到”，且估计误差有严格界）。CM Sketch 的优势是能回答任意元素的频次，代价是误差与总流量挂钩。

选哪个取决于你要问什么问题。这是很实际的一个分岔口：

“任意 key 出现了几次？” → CM Sketch
“最热的 100 个是什么？” → Space-Saving / Misra-Gries

（2）限流计数

要限制”每个用户每分钟最多 100 次请求”，标准做法是为每个用户维护一个计数器。当用户数是亿级时，这个计数表本身就撑不住了。

用 CM Sketch：每个请求进来，对 user_id 做 d 次哈希，对应位置 +1；查询时取 min，超过 100 就拒绝。

为什么合适？因为高估的方向是无害的。 高估 = “多拦了一点”，偶尔误伤一个用户；低估 = “限流失效”，后端被打爆。CM Sketch 只高估不低估，正好把错误放在”多拦”这一侧。

这跟子主题三讲的”定向错误”完全对上——CM Sketch 是为限流量身定做的，不是巧合。

（3）网络流量测量

路由器和交换机要在每秒几百万个包的线上速度下统计”每个流（五元组）有多少包”。用精确哈希表？内存和查找速度都撑不住。CM Sketch 用固定的小内存 + O(d) 次哈希就能做，而且矩阵加法可以合并——多个网络设备各算各的，中心节点把矩阵加起来就是全局视图。

这个”可加性”是 sketch 家族最重要的工程性质，值得单独强调：

sketch 是一个线性变换的摘要，所以两个 sketch 相加 = 两个数据流合并后的 sketch。

HLL 的可合并（取 max）、CM Sketch 的可合并（矩阵加法）、Bloom Filter 的可合并（位或），三者都是同一件事的体现：它们都是”摘要”而不是”记录”，摘要之间能直接运算。 这直接决定了它们在 MapReduce / Flink / 分布式监控里的适用性——数据量再大，shuffle 的只是一个几 KB 的矩阵。

一个必讲的改进：Conservative Update

标准 CM Sketch 更新时给 d 行都 +1。有个几乎免费的改进，叫 Conservative Update（CM-CU）：

更新时，先算出 d 行的当前最小值 vmin，只给那些计数等于 vmin 的行 +1，其他行不动。

为什么这样做？因为查询时取的是 min，给那些”已经比最小值大”的行加 1 完全不影响查询结果，却白白增大了未来的冲突。

这是”为查询方式量身定制更新逻辑”的经典案例——既然我要取 min，那就只在必要的时候增加 min。实测能把误差降低一个数量级，代价只是更新时多一点比较。

这就是近似算法工程化的常态：理论结构给出骨架，工程技巧把常数项砍掉一半以上。

子主题九：采样——最朴素、也最容易翻车的近似

前面三种结构都是精巧的”哈希摘要”。但人类最早、最直觉的近似手段是另一回事：不看全量，只看一部分。

采样简单到不像技术，可它恰恰是翻车率最高的近似方法。为什么？因为它看起来太安全了，所以没人设防。

蓄水池采样：从未知长度的数据流中等概率抽 k 个

先抛问题：

有一个数据流，你要从中等概率抽取 k 个元素。问题是——你不知道流有多长，而且只能遍历一次。

常规做法不行：先数一遍总数 n，再按 k/n 概率抽——那要两遍遍历，流数据做不到。

蓄水池采样（Reservoir Sampling） 的解法优雅得像魔术：

维护一个大小为 k 的"蓄水池"
第 i 个元素到来时（i 从 1 开始）：
    如果 i <= k：直接放进蓄水池
    否则：
        以概率 k/i 决定是否留下它
        如果留下：随机替换蓄水池中的某一个

就这几行。凭什么它是等概率的？证明一遍，很短，值得看懂：

对第 i 个元素（i > k），它最终留在蓄水池中的概率 = “它被选中” × “之后没被替换掉”。

被选中的概率 = k/i
第 j 个元素（j > i）到来时，它以 k/j 的概率进入蓄水池，进入后以 1/k 的概率替换掉我们的目标。所以目标在第 j 轮被踢掉的概率 = (k/j)·(1/k) = 1/j
所以目标从第 i+1 轮到第 n 轮全部幸存的概率 = ∏(1 - 1/j) = (i/(i+1))·((i+1)/(i+2))·…·((n-1)/n) = i/n

乘起来：(k/i) · (i/n) = k/n。

完美等于 k/n，与 i 无关。 这个”i 恰好被约掉”的瞬间，是整个算法最漂亮的地方。

它的价值在哪？ 在”不知道总长、只能过一遍、内存固定”这三个约束同时成立的地方：

数据库查询的随机采样：流式扫描，边扫边抽，不用先 count(*)。
日志/事件的在线采样：每秒百万条，只留 1000 条做分析。
分布式蓄水池：每个分片各跑一个，合并时按各分片的数据量加权再采样一次——因为每个分片内部是等概率的，只要合并时按权重重新抽样，全局就还是等概率的。
加权版本（A-Res / A-ExpJ）：给每个元素一个权重 w，用 rand^(1/w) 作为排序键取 top-k，就得到按权重不等概率的采样。用于”重要的用户权重高”。

A/B 测试：采样 + 假设检验

A/B 测试的本质就是采样——从全部用户里抽两组，用样本的差异推断总体的差异。

它的误差规律是一条你必须刻在脑子里的曲线：

估计误差 ∝ 1/√n。置信区间宽度减半，需要 4 倍流量。

这条曲线决定了所有增长团队的工作节奏：想更快出结论，就得接受更宽的置信区间或者更大的样本。没有第三条路。

A/B 测试最容易踩的坑，几乎全是”采样偏差”的变体：

分流不随机：用哈希分桶（user_id % 100）保证稳定性和随机性是对的，但如果哈希函数与某个分组特征相关（比如按注册时间分段哈希），就会引入偏差。
新奇效应（novelty effect）：老用户对新界面的”新鲜感”会在一两周内衰减。采样时间窗口本身就是一种采样偏差。
Peeking（偷看）：中途反复看结果，“看到显著就停”会让假阳性率从 5% 膨胀到 20% 甚至更高。这本质是重复检验导致的偏差——你以为在做一次实验，其实做了二十次。
辛普森悖论：整体看 A 组胜出，但按地区/设备/新老用户拆开看，每一层都是 B 组胜出。原因是两组的样本构成不同（比如 A 组恰好抽到了更多高活跃用户）。这是”分组权重 ≠ 总体权重”导致的偏差。
多重比较：同时测 20 个指标，总有一个”显著”——这是纯随机噪声。

注意第 4 条和第 5 条，它们会在这里复现：聚合层面的误差会掩盖子群层面的真相。 这个主题我们在子主题十三还会再见一次。

监控指标采样：以及偏差陷阱

高 QPS 系统里，全量埋点上报的成本高到不可接受（存储、网络、计算都是钱）。于是采样 1%、0.1%、甚至 1/1000。

这里有三个几乎人人踩过的坑：

坑一：均匀采样会系统性丢掉”罕见但重要”的事件。

假设错误率 0.01%，采样率 1%。一个错误请求被采到的概率是 1% ——所以你每天采到的错误样本数是”真实错误数 × 1%“，这个估计是无偏的，可以乘 100 还原。

听起来没问题？问题在于：如果你还想看错误的详情页、想看”这次错误发生在哪个用户、哪条链路”——对不起，99% 的错误样本根本没被采到，你永远看不到它们。

乘回去能还原”数”，但不能还原”个体”。 这是采样和 sketch 的根本区别：sketch 保留的是全体数据的摘要，采样保留的是部分个体的原件。

坑二：采样率变化导致指标跳变。

大促时把采样率从 1% 调到 0.1%，如果你直接画”采样后的请求数”，曲线会断崖式下跌——看起来像系统崩了。

正确做法：在采样点记录采样率，上报时带上 rate，还原时按 1/rate 加权还原。 每一个采样出来的样本代表 1/rate 个真实请求。这是可观测性系统（Prometheus、OpenTelemetry、StatsD）的标准做法，但自己写埋点时很容易忘。

坑三：分位数不能简单从采样里还原。

计数类指标（QPS、总数）可以无偏还原。但 p99 延迟呢？

从 1% 的样本里取 p99，得到的是样本分布的 99 分位，它确实是总体 99 分位的一致估计——理论上 OK。但问题是方差极大：如果总流量 100 万，采 1% 是 1 万个点，你要从 1 万个点里估计第 99 百分位，只有 100 个点落在尾部上方，误差已经很明显。要是 p99.9 呢？只有 10 个点。再往下，p99.99 干脆没有样本。

正确做法是不要采样延迟，而是聚合延迟：在进程内用直方图或分位数 sketch（DDSketch、t-digest）把延迟压成一个”相对误差有界”的结构，上报这个结构而不是原始点。

注意这里出现了什么——分位数 sketch 又是”近似数据结构”。所以真实的可观测性栈是：

高频数值 → 直方图/sketch（近似但保留全体信息）高价值个体（错误、慢请求）→ 尾部采样（tail-based sampling）其余 → 均匀采样（用于计数还原）

尾部采样（tail-based sampling） 值得一提：OpenTelemetry 的做法是先缓存完整 trace，等请求结束后再决定保不保留——出错的、超时的、慢的，全部保留；正常的健康请求只保留一小部分。

这个思路的关键在于：采样的决策被推迟到了”信息完备之后”。 均匀采样是”盲采样”，尾部采样是”看完了再采样”。当你能延后决策时，偏差就消失了。

回到根本：采样偏差的根源是什么？

统计学上，采样的无偏性依赖一个前提：样本与总体同分布（或者说，每个单位被选中的概率已知且与你要度量的量无关）。

几乎所有真实的采样偏差，都来自同一个病因：

采样过程与你要度量的那个量发生了相关。

经典案例值得讲一次：1936 年美国大选，《文学文摘》（Literary Digest）寄出了 240 万份民调问卷——样本量大得惊人——预测兰登将以压倒性优势击败罗斯福。结果罗斯福赢了 46 个州。

问题不在于样本量小，而在于抽样框：名单来自电话簿和汽车登记记录。1936 年大萧条时期，有电话有汽车的是相对富裕的群体，而他们恰好倾向于共和党（兰登）。

240 万个样本，纠正不了一个系统性的抽样框偏差。 这是”样本量大 ≠ 结论准”的最著名注脚，也是我喜欢的一句总结：

增加样本量能减小方差，但减小不了偏差。偏差是设计问题，不是规模问题。

这个区分同样适用于前面所有结构：Bloom Filter 的误报是有界的、可分析的；采样的偏差是无界的、往往不可见的。所以采样的风险，其实高于 Bloom Filter——只是它伪装得更无害。

子主题十：有损压缩——把”误差的定义权”交给接收者

前面讲的是”用近似换内存/速度”。现在换一个维度：用近似换体积。这可能是近似思想商业化最成功的一次。

先想一个刺眼的问题：

一张 3MB 的 JPEG 照片，压到了 300KB。那 2.7MB 去哪了？如果信息真的丢了，为什么你看着还觉得”挺清楚”？

答案是：丢掉的那部分信息，你的眼睛从来就没接收过。

这就引出了一个根本性的区分：

信息 ≠ 感知信息。

香农 1948 年奠基信息论，给出了无损压缩的下界（熵）。但 JPEG 根本没在下界里玩——它玩的是香农 1959 年建立的率失真理论（Rate-Distortion Theory）：

给定可容忍的失真 D，最小需要多少码率 R？即 R(D) 函数。

率失真理论是有损压缩的理论地基，它的核心结论非常反直觉：当你允许一点点失真，所需码率可以断崖式下降。 曲线在 D→0 附近极其陡峭——也就是说，追求”零失真”的最后那一点代价，占了绝大部分成本。

这和本章开头那句话完全同构：精确性的代价是非线性暴涨的，放宽一点点需求，成本就崩塌式下降。

JPEG：怎么丢，才能丢得看不见？

流程走一遍，你会发现”有损”只发生在一个地方：

色彩空间转换：RGB → YCbCr（亮度 Y + 两个色差 Cb/Cr）
色度下采样：4:2:0——色度通道在两个方向上都砍半
分块 8×8，做 DCT（离散余弦变换）：把空间域转成频率域
量化：DCT 系数除以量化表，取整 ← 唯一的有损步骤
熵编码（Huffman / 算术编码）：无损

注意到没有？整个链条里只有一个环节在丢信息，其余全是数学上的等价变换或无损压缩。 这么设计不是偶然——它把”不可控的误差”隔离成了一个可以精确调节的旋钮（量化表）。

每一步背后的生理依据：

第一步：人眼对亮度分辨率远高于色彩分辨率。

视网膜上负责暗视觉的视杆细胞多、负责色觉的视锥细胞少。所以 4:2:0 下采样（色度数据量降到 1/4）你几乎看不出来。这一步直接省掉一半数据量，而且你一点感觉都没有。

类比：这就像给一份报告配彩色插画——你把插画的颜色精度降一半，读者的信息获取几乎不变，但文件小了很多。信息的价值不是均匀分布的，压缩的第一步是找出”哪部分不值钱”。

第三步：DCT 把图像变成频率。

低频系数 = 大块的平坦区域（图像的主要结构）；高频系数 = 细节和边缘的急剧变化。

第四步：量化——人眼对高频细节不敏感。

量化表的规律是：高频部分除数大、低频部分除数小。高频系数除以一个大数再取整 → 大量变成 0 → 后续熵编码几乎不占空间。

这就是为什么 JPEG 在高对比度边缘（文字、线条画）周围会出现”振铃”和块状伪影：那里恰好是人眼对失真敏感、而压缩又最狠的地方。

还有第三个武器：视觉掩蔽（masking）。 在纹理复杂的区域（比如草地、树叶），量化噪声会被纹理”掩盖”而看不见；在平坦区域（比如天空），同样的噪声就会显出块状。所以聪明的编码器会做自适应量化——在纹理区多压，在平坦区少压。

MP3：听觉掩蔽，比视觉更狠

音频的压缩比通常更高（CD 音质 1411 kbps → MP3 128 kbps，约 11:1）。凭什么？

因为听觉的”漏洞”比视觉更可利用，主要靠心理声学掩蔽：

频域掩蔽：一个响亮的声音，会让它附近频率的弱音变得听不见。这个”附近”在生理上叫临界频带（critical band）——内耳基底膜上相邻频率会互相干扰。所以编码时：算出每个频带的掩蔽阈值，低于阈值的信号根本不用编码。

时域掩蔽：一个响亮的声音出现之前几十毫秒（前掩蔽）和之后一两百毫秒（后掩蔽）内的弱音也听不见。强音前后那段，可以放心地塞入量化噪声。

所以 MP3 编码器的核心是一个”噪声预算分配”问题：在掩蔽阈值以下分配量化噪声，让噪声被音乐自己盖住。

一个绝妙的类比：这就像在摇滚演唱会现场跟人耳语——不是你的声音消失了，是它被”盖住”了。 编码器利用的正是这个”盖住”。

视频编码（H.264 / HEVC / AV1）在此基础上再加一维：

帧内预测 + 帧间预测（运动补偿）：只编码”和参考帧的差异”，而大部分像素是没变的；
运动矢量：只存”这块内容从哪儿挪到哪儿”，而不是内容本身；
再加上 DCT/量化/熵编码。

结果是：未压缩的 1080p 视频每秒约 750 Mbps，H.264 压到 4 Mbps 仍然观感良好——上百倍的压缩比。

这一节真正的洞察：误差的定义权在谁手里？

前面所有的近似结构——Bloom、HLL、CM Sketch——都有一个客观的、数学的误差定义：误报率、标准误差、ε·N。这些误差是”数据自己说了算”的。

有损压缩跨出了激进的一步：

它的误差定义，来自外部的接受者——人的感官。

JPEG 的”失真”不是数学上的像素差，而是”人眼能不能看出来”。误差的度量标准被搬出了数据本身。

这一步为什么重要？因为它意味着：同一个数据，面向不同接收者，最优的压缩是不一样的。

面向人眼 → 丢高频、丢色度（JPEG）
面向人耳 → 丢被掩蔽的频段（MP3）
面向机器分类模型呢？→ 完全是另一回事。压缩优先保留”对分类有用的特征”，人眼看不懂无所谓。这就是为神经网络的压缩 / 知识蒸馏 / 特征量化——本质上是”面向特定消费者的有损压缩”。

大模型时代的向量量化（PQ）、低秩近似（LoRA）、蒸馏，全都是这个思想的延伸：先问”谁在消费这个信息”，再决定丢什么。

反过来说，这也是有损压缩最大的风险：一旦接收者变了，你丢掉的东西可能正是他需要的。 用 128kbps MP3 存档音乐，将来做音频分析或重制时，丢掉的频段就永远回不来了。

有损压缩是不可逆的近似——这是它和 Bloom Filter 的另一个关键区别。 Bloom Filter 至少还能重建（你有原始数据就行），而压缩后的文件里，被量化的信息是真的蒸发了。

最后一个值得记住的商业结论：没有有损压缩，就没有流媒体、视频通话、移动互联网的图片经济、以及今天的短视频。整个消费互联网的物理基础，建立在”人眼和人耳有漏洞”这件生物学事实上。近似思想最赚钱的一次应用，赚的是人类感官进化的便宜。

子主题十一：近似最近邻搜索——大模型时代最热的近似

现在进入当下最火的场景：向量检索。

问题设定：你有 N 个 d 维向量（比如 10 亿条文本的 embedding，d=1024），来一个查询向量 q，要找出最相似的 k 个。

先问：精确解为什么不行？

方法一：暴力扫描。计算 q 与全部 N 个向量的距离 → O(N·d)。N=10 亿、d=1024，一次查询就是 10¹² 次浮点运算。单线程要跑好几分钟。

方法二：用空间索引，比如 KD 树、球树。在低维（2~3 维）很快，O(log N)。

但这里有个残酷的事实：维度灾难（Curse of Dimensionality）。

高维空间的几何性质和低维完全不同：

高维球体的体积几乎全部集中在表面薄壳上；
随机两点间的距离趋于相等（距离集中度：最远距离与最近距离的比值趋于 1）；
结果是：任何基于”距离下界剪枝”的树结构都剪不动了——因为所有点距离都差不多，你没法证明”这一整棵子树不可能包含最近邻”。

学术界的经典结论是：KD 树之类的空间划分结构，在维度超过大约 10 维后，性能就退化到接近暴力扫描。

注意这里发生了什么：不是”精确方法太慢”，而是”精确方法的加速机制在原理上失效了”。

这和前面 Bloom Filter 的场景不一样。Bloom Filter 是”精确方案太贵，近似方案便宜”；ANN 是”精确方案的加速技巧在高维根本不成立”。所以在高维向量检索里，近似不是一个优化选项，而是唯一的可行性路径。

好在这条路上，业务恰好能接受”漏掉几个”：

用户要的是”最相关的几条”，不是”数学上最近的 k 条”。 第 3 名和第 4 名换了位置，用户根本不知道。

这就是 ANN（Approximate Nearest Neighbor）的全部合法性来源。

方案一：IVF（倒排文件索引）——把全局搜索变成局部搜索

思路很直白：先把向量空间切成块，只搜索最可能的那几块。

用 k-means 把所有向量聚成 nlist 个簇（比如 1000 个），每个簇一个质心；
每个向量归到最近的质心，存进对应的倒排列表；
查询时，先找出与 q 最近的 nprobe 个质心（比如 10 个），只扫描这 10 个簇里的向量，其余 990 个簇一眼都不看。

本质：用聚类做空间上的”近似剪枝”——赌最近的邻居和我落在同一个或相邻的簇里。

nprobe 就是那个精度/速度旋钮：

nprobe=1：只搜 1 个簇，最快，但”最近邻恰好在簇边界外”的情况会漏掉；
nprobe=nlist：退化成暴力扫描，100% 召回；
实践中 nprobe 取 nlist 的 1%~10%，召回率能到 90%~99%。

为什么会有漏检？ 因为簇边界是”人为切出来的”，而真实最近邻可能就在边界另一侧。这就是几何上的边缘效应（boundary effect）。

方案一的升级：IVF-PQ（乘积量化）

IVF 解决了”少算距离”，但没解决”装不下”——10 亿条 1024 维 float32 = 4TB，内存放不下。

乘积量化（Product Quantization, PQ） 来解决这个问题，而且它的思想和上一节的有损压缩一脉相承：

把 d 维向量切成 m 段，每段 d/m 维（比如 1024 维切成 96 段，每段约 10 维）；
每一段独立做 k-means，得到一个小的码本（通常 256 个聚类中心，用 8 bit 编号）；
每个向量就变成 m 个字节的”编码序列”。

算一下：d=1024 的 float32 是 4096 字节；PQ 后是 96 字节。压缩约 40 倍。

更妙的是：用 PQ 编码还能直接算近似距离——预先算好查询向量与每个码本中心的距离，存成查找表，之后计算距离只需 m 次查表加法，比原始 d 次浮点乘法快一个数量级。

看到了吗？PQ 就是向量版的”有损压缩”：丢掉的是”向量分量的精确值”，保留的是”相对位置关系”。 子主题十的思想在这里完整复现。

方案二：HNSW（分层可导航小世界图）——当下的主流

如果说 IVF 是”分块剪枝”，HNSW 是”在图上走过去”。

先理解”小世界网络”：六度分隔理论说的那种图——每个节点只连少数邻居，但任意两节点间的跳数很少。

HNSW 建一个多层图：

第 0 层（底层）：包含所有节点，每个节点连 M 个最近的邻居（M 通常 16~64），是一张稠密的近邻图；
上层：节点的子集，指数衰减地稀疏（上一层节点数约为下层的 1/M），连线更长，相当于”高速公路”；
顶层只有一个入口节点。

查询过程：

从顶层入口出发，在当前层贪心地走向离 q 更近的邻居，直到没有更近的邻居（局部最优）；
下降到下一层，以上一层的落点为入口，重复贪心；
到底层后，改用 beam search：维护一个大小为 efSearch 的动态候选队列，不断扩展，保留最好的 k 个。

为什么这样快？ 上层的长边让你用极少跳数”跨”到目标区域（相当于粗粒度定位），底层再用密集短边精修（相当于细粒度搜索）。总跳数与 log N 同阶，而不是 N。

三个关键参数：

M：每个节点的连接数。M 大 → 图更稠密 → 召回率高、内存大、建图慢；
efConstruction：建图时的搜索宽度。越大 → 图质量越高 → 建图越慢；
efSearch：查询时的 beam 宽度。这是线上唯一需要调的旋钮——efSearch 从 16 调到 128，召回率从 85% 涨到 99%，QPS 相应下降。

HNSW 的代价，必须说清楚：

内存大：除了全量向量，还要存图的邻接表。10 亿条 1024 维向量，HNSW 索引可能比原始向量还大。
建图慢：插入时需要搜索并动态更新邻居连接，大规模建索引是重活。
删除麻烦：删节点要修复邻居连接，很多实现用”标记删除 + 定期重建”糊过去。

所以 IVF 和 HNSW 的选择是个真实的权衡：

	IVF / IVF-PQ	HNSW
内存	小（尤其配合 PQ）	大（图 + 全量向量）
查询速度	快，且可预测	更快（高召回下优势明显）
召回率	中等（依赖 nprobe）	高
构建	快（k-means 训练）	慢
更新/删除	相对容易	麻烦
适合	超大规模、内存受限、可批量重建	中等规模、高召回、低延迟

（还有一条路线叫 DiskANN：把图索引放在 SSD 上，单机支撑十亿级向量，用少量内存缓存热点部分。以及 LSH（局部敏感哈希）：理论优雅，但实践中图索引在召回/速度上基本胜出。）

权衡的量化有多夸张？

典型数据：在百万到亿级数据集上，召回率从 100%（暴力）降到 95%，QPS 可以从几十涨到几千——两个数量级；降到 90%，再翻几倍。

这就是”召回率的微小损失换千倍查询速度”的实际含义。 而 95% 召回意味着什么？平均每 20 个真正相关的结果，漏掉 1 个。

为什么它在大模型时代爆发？

因为 RAG（检索增强生成）把向量检索变成了基础设施：

数据规模：亿到十亿级文档块；
向量维度：768 ~ 3072（远超”维度灾难”的门槛）；
延迟要求：整个问答链路要秒级响应，检索只能占几十毫秒。

精确检索在物理上不可能。

但更关键的是下游消费者的性质变了：

检索出来的文本，最终是交给 LLM 去读的。

LLM 对”少召回一条”极度不敏感——只要最关键的那一两条在上下文里，答案几乎一样。这和传统的搜索引擎不同：搜索引擎漏掉第 3 条结果，用户可能真的就看不到那个信息了；而 RAG 漏掉第 3 条，LLM 照样能答对。

这是本章最重要的一条推论之一：

上游能近似到什么程度，取决于下游消费者对误差的鲁棒性。下游越鲁棒，上游越可以放手去近似。

反过来说，如果下游不鲁棒呢？举个反例：

法律证据检索 / 判例检索：漏掉一条关键判例可能是医疗事故或冤案；
医疗诊断辅助：漏掉一个相似病例可能误诊；
代码仓库的精确去重/版权检测：要求极高的召回。

这时候 ANN 的收益就要打折，工程上必须做**混合检索（hybrid search）**兜底：

BM25（稀疏关键词检索） + 向量检索（稠密语义检索） 双路召回 → 用 RRF（倒数排名融合）合并 → 再用 cross-encoder rerank 精排。

为什么这样能救？因为两路检索的失败模式不同（关键词检索漏掉”语义相同但用词不同”，向量检索漏掉”精确术语匹配”），失败不相关的方法融合，能显著提升整体召回上界。

这又回到子主题九讲过的道理：独立重复试验取最好结果（还记得 CM Sketch 为什么取 min 吗？同一个思想的另一面）。

子主题十二：学习型索引——用模型替代 B 树，以及”ML 做近似”的边界

现在到了近似思想最前沿、也最需要冷静的一站。

2018 年，Kraska 等人在 SIGMOD 发表《The Case for Learned Index Structures》，抛出一个炸裂的观点：

B 树本身就是一个模型。既然它是模型，那我们能不能用一个真正的机器学习模型来替代它？

先理解”索引就是模型”这个洞察。

B 树做的是：给定 key，返回”记录的存储位置”。在一个已排序的数组上，这个映射就是：

位置 ≈ N · CDF(key)

其中 CDF 是数据的累积分布函数（“有多少比例的 key 小于它”）。

B 树干了什么？它用一棵树隐式地、分段地拟合了这个 CDF——每个叶子节点覆盖一段 key 范围，页内再做局部查找。

关键洞察来了：

B 树不对数据分布做任何假设，它对任何分布都给出 O(log N) 的保证。这个”通用性”的代价，就是 log N。

而真实世界的数据分布不是最坏情况——它有规律、有偏斜、有结构。比如：

用户 ID 往往是连续自增的整数 → CDF 几乎是一条直线 → 一次线性插值就能算出位置；
时间戳分布可能集中在某几个区间 → 分段线性就能拟合得很好。

所以：

B 树的 O(log N)，本质上是”对数据分布一无所知”所交的税。如果你知道分布的形状，你就能跳过这棵树。

这个洞察和压缩的关系极其密切，值得点破：

熵编码（Huffman / 算术编码）利用的是”符号概率分布已知”，学习型索引利用的是”key 的位置分布已知”。它们都是同一件事：用分布的先验知识换掉通用性的税。

理解到这一层，你就不会觉得”用模型做索引”是玄学了——它就是用拟合代替查找。

具体怎么做？RMI（Recursive Model Index）

论文的骨架是递归模型索引：

顶层：一个模型（小型神经网络或线性模型）读入 key，输出”该用哪个下层模型”；
中间层：若干”专家”模型，各自负责一段 key 范围，进一步细分；
底层：线性模型（y = ax + b），拟合自己那段范围内的位置映射。

查询时：从顶层走到底层，几次浮点运算得到一个预测位置；由于预测有误差，在预测位置附近的一个小区间内做局部查找（比如二分）。

论文报告的效果（在只读、内存、已排序的场景下）：比 B 树快约 1.5~3 倍，空间小一个数量级甚至更多。

为什么快？两个原因：

计算代替了指针跳转：B 树的每层都是一次随机内存访问（大概率 cache miss），而模型推理是一串连续的浮点运算（可以流水线、可以 SIMD）；
空间小意味着更多地待在 cache 里。

但必须泼冷水：学习型索引的边界在哪里？这是本节的真正重点。

边界一：插入和更新是致命弱点。

模型是在”当前数据分布”上训练出来的。一旦插入新数据：

位置映射变了 → 模型预测偏移 → 误差超过预留的区间 → 局部查找退化成大范围扫描；
最坏情况下，模型彻底失效，需要重训练。

工程上的缓解手段：

预留空隙（gap）：每个 key 之间留出空位，插入时填进去；
溢出缓冲区（overflow buffer / delta index）：新写入先进缓冲区，定期批量合并并重建模型。

这本质上是在用”写入放大”换取”读取加速”——和 LSM 树的思想一致。所以学习型索引最适合的场景是：读多写少、批量重建（比如只读的分析型存储、静态字典）。B 树那 O(log N) 的稳定插入和良好的并发控制，模型短期内替代不了。

边界二：误差保证的性质变了——这是最根本的一条。

请对比：

	Bloom Filter / HLL / CM Sketch	学习型结构
误差界	有严格的概率界（可证明）	只有经验界（测出来的）
依赖假设	哈希函数的随机性（可控、可验证）	数据分布的稳定性（不可控）
输入异常时	行为不变	行为可能崩溃
验证方式	数学证明	测试 + 监控

传统数据结构的保证是”证明出来的”，学习型结构的保证是”测出来的”。

这个差别决定了它们在工程里的位置。你可以在金融系统里放心用 Bloom Filter，因为它的误报率是被数学锁死的；但你很难放心让一个模型去负责”这笔交易存在不存在”的判断。

边界三：分布漂移（distribution shift）。

线上的数据分布会变——业务增长、促销活动、用户结构变化、恶意流量。B 树对分布漂移完全免疫（它压根没假设分布）；学习型索引则会静默退化：它不会报错，只是越来越慢，直到某天突然不可接受。

“静默退化”是比”崩溃”更可怕的工程问题，因为它没有告警信号。

边界四：计算成本不一定划算。

一次模型推理（哪怕只是两层小 MLP）涉及几十到几百次乘加。如果数据能全部装进 L2/L3 cache，B 树的几次指针跳转可能比模型推理还快。

所以学习型索引要真正跑赢，往往需要：

模型足够小（能进 cache）；
用 SIMD / GPU 批量推理；
或者干脆退化为分段线性（PGM-index 的路线）。

硬件协同设计是前提，不是可选优化。

务实的落地路线：混合，而不是替代

现实中最成功的不是”纯学习型索引”，而是混合结构：

PGM-index（Ferragina & Vinciguerra, VLDB 2020） 是个很好的例子：它用分段线性函数近似 CDF（而不是神经网络），并且给出了严格的误差界和最坏情况查询复杂度保证。这是一条更务实也更可工程化的路线——用最简单的模型（分段线性），换取可证明的保证。

另一个精彩案例：Learned Bloom Filter，它把”混合”这件事讲得最透彻。

思路：用一个小模型学习”哪些 key 更可能在集合里”（模型输出一个”成员度”得分），得分高的直接判定”存在”，得分低的再查一个备用的小 Bloom Filter。

关键问题来了：这样还保证”绝不漏报”吗？

不直接保证。模型会犯错——它可能给一个真正在集合里的元素打了低分，直接判”不存在”，这就是假阴性——Bloom Filter 的核心承诺被打破了。

怎么补回来？原论文的做法是：

构建一个备用 Bloom Filter，它只包含”被模型误判为不存在”的那些元素。查询时，模型说”不存在”的，再去查这个备用过滤器。

于是：真正在集合里的元素，要么被模型判为存在，要么被备用过滤器接住——假阴性被彻底消除。

这个构造值得反复品味，它是”用 ML 做近似”的范式模板：

ML 负责利用数据分布的先验知识，压缩掉大部分工作量；传统结构负责兜底，保证正确性的下界。

模型提供效率，传统结构提供保证。二者不是替代关系，而是分工关系。

所以”用 ML 做近似”这个新范式的边界在哪？

给你一份可直接用的判断清单。

适合的场景：

数据分布稳定且有结构（不是最坏情况、不是均匀分布里的随机噪声）；
读多写少，或可以周期性批量重建；
输出的近似结果可以被廉价地校验（有 ground truth 可以核对，错了能兜住）；
单次错误的代价低；
规模足够大，使得常数优化真的值钱（小数据量下省下的时间不够覆盖复杂度成本）。

不适合的场景：

需要严格正确性保证（金融记账、权限判定、事务冲突检测）；
数据持续高频变动；
分布会漂移且没有监控；
错误的代价高，或错误不可检测（静默错误最危险）；
团队无法持续维护”模型 + 兜底”这套双层结构的复杂度。

最后给一句总结，也是这一子主题的题眼：

概率数据结构把”随机性”变成了可证明的保证；学习型结构把”数据规律”变成了可测的性能。前者是数学，后者是工程。工程可以很有效，但它需要监控、兜底和撤退方案。

子主题十三：实操——怎么评估”近似的误差”业务能不能接受

讲了这么多结构，最后回到最实际的问题：

我该不该在这个场景用近似？如果用了，怎么证明这个误差是可接受的？

给一套可操作的八步流程。这不是理论，是能直接拿去开评审会的清单。

第一步：先定义误差的度量方式——而且不要只看平均误差

最常见的错误是说”我们的误差是 1%“。这个数字几乎总是有误导性。 必须至少定义四个维度：

绝对误差 vs 相对误差：HLL 的 2% 是相对误差（10 亿的 2% 是 2000 万）；CM Sketch 的 ε·N 是相对于总量的绝对误差（对低频元素，相对误差可能高达 100%）。说误差时必须说清是相对谁。
误差的分布，而不只是均值：p50、p95、p99、max。平均值会掩盖长尾。 一个”平均误差 1%、但 1% 的 key 误差 50%“的系统，和”误差稳定在 1%“的系统完全不同。
方向性：误差是双向的，还是只偏向一侧？只偏向一侧的好处理得多（还记得子主题三吗？）。
误差随数据规模/分布的变化曲线：小数据量时如何？极大数据量时如何？数据倾斜时如何？

一句话：你要度量的是”误差的分布”，不是”一个数”。 这本身就是”对误差做近似度量”的陷阱——别用均值概括一个分布，那正是本章批判的思维。

第二步：把误差翻译成业务损失——这是最常被跳过的一步

误差只有翻译成钱、风险或用户体验，才能谈”可接受”。

举几个对比例子：

场景	误差	业务后果	可接受？
首页 UV 报表（看趋势）	±2%	趋势判断几乎不受影响	✅ 完全可以
广告结算 UV（按此收费）	+2%	多收客户 2% 的钱 → 争议、退款	❌ 结算环节必须精确
推荐系统的候选召回	漏 5% 候选	最终排序略差，用户无感	✅
风控黑名单命中	漏 1%	一次欺诈就可能造成大额损失	❌
限流计数	高估 5%	多拦 5% 的正常请求	✅ 偏向安全侧
库存扣减	高估 1%	超卖	❌

注意这个表里最重要的观察：同一个指标（UV），用在”看趋势”和”用来收钱”两种场合，结论完全相反。

所以”这个误差可接受吗”这个问题本身就问错了。正确的问题是：“在这个具体的使用场景下，这个误差可接受吗？”

第三步：找出”决策翻转点”，而不是追求误差小

这是整套流程里最有用的一条。

不要问”误差能不能小于 5%“，要问”误差多大时会改变我的决策”。

几个例子：

A/B 测试：关键的不是指标差多少，而是置信区间是否跨过 0。只要不跨过 0，无论误差多大，结论都不变。
告警系统：关键的不是指标准不准，而是误差会不会让指标跨过告警阈值。如果实际值是阈值的 3 倍或 1/3，那 ±10% 的误差完全无所谓；如果实际值常年贴在阈值附近，那 ±1% 的误差就会导致告警抖动。
报表：关键是排名会不会翻转。如果第一名和第二名差 3 倍，误差 2% 无所谓；如果他俩差 1%，误差 2% 就是灾难。

这条原则可以总结成一句话：

近似的可接受阈值不是一个绝对数字，而是”当前值离决策边界有多远”。

推论很实用：离边界远的地方大胆近似，离边界近的地方保守处理。 这是”分级精确”的工程依据——同一个系统里，不同数据用不同的精度策略，完全合理（呼应子主题五）。

第四步：离线回放——用历史数据算出真实的误差分布

做法：

取一段有代表性的历史数据（注意”有代表性”这四个字）；
用精确算法跑一遍，作为 ground truth；
用近似算法跑同样的数据；
逐条对比，输出误差的完整分布：p50、p90、p99、p99.9、max。

重点看 p99 和 max，而不是平均。

注意一个陷阱：离线回放的误差往往比线上乐观，因为历史数据是”已经发生过的、稳定的”。线上会遇到离线数据里没有的长尾和突变。所以离线结果只能作为”误差下界”来看。

第五步：按关键维度切片检验——聚合误差会掩盖子群误差

整体误差 1%，可能掩盖”某个渠道误差 30%”。

必须做的切片：

按业务维度：地区、渠道、设备、用户分层、商品类目；
按数据量：大客户 vs 长尾客户（重点看长尾——大客户数据量大，估计准；长尾客户数据量小，HLL 在小基数时误差行为完全不同，还记得 Linear Counting 吗？）；
按时间：平时 vs 大促、白天 vs 凌晨。

为什么这一条这么重要？ 因为误差通常不均匀分布：

HLL 在小基数时相对误差更大；
CM Sketch 的误差是”绝对误差 ∝ 总流量”，所以低频元素的相对误差巨大——如果你关心的是长尾，CM Sketch 可能完全不适合；
Bloom Filter 的误报对”查询量大但命中率低”的那批 key 影响最大。

这是辛普森悖论的表亲：宏观的正确掩盖了微观的错误。 在子主题九的 A/B 测试里我们见过一次，这里又见一次——它是”用聚合看世界”的通用代价。

第六步：跑压力与边界场景

必须专门测这四种：

数据量极小：n=1、n=10、n=100。很多近似结构在小 n 时行为完全不同（HLL 要切 Linear Counting，采样在小 n 时几乎无意义）。
数据量极大：是否会溢出？计数器会不会饱和？HLL 的寄存器是 5~6 位，会不会溢出？
分布突变：大促、热点事件、爬虫攻击——数据分布突然改变时，很多近似结构的误差会暴涨。（学习型索引在这里会直接崩，还记得吗？）
极端倾斜：一个 key 占 90% 的流量，其余 1000 万个 key 分剩下的 10%。这是最现实也最容易被忽略的场景。

特别提醒：倾斜是近似结构的头号杀手，因为大多数误差界都假设了某种”均匀性”（哈希把元素打散）。倾斜本身不会破坏哈希的均匀性，但会让”误差相对于元素自身频次”变得极不均匀。

第七步：线上双跑 + 误差监控

上线前用影子模式（shadow mode）：

同时跑精确路径和近似路径；
近似路径的结果返回给用户，精确路径的结果只用于对比和监控；
持续计算两者的差异，一旦误差超出阈值就告警。

关键设计：监控的是”误差本身”，不是”结果本身”。

这是很多团队的盲区。他们给 UV 指标设了告警，却没给”HLL 估计值与精确值的偏差”设告警。结果是：指标看起来一切正常，但近似结构其实已经失效了，没人知道。

具体做法：

定期（比如每天）用精确算法重算一次关键指标，与近似值对账；
给误差设 SLO（比如”p99 相对误差 < 5%“）和告警；
误差告警的优先级应该高于指标告警——因为指标异常可能是真实业务变化，而误差异常是系统坏了。

第八步：设计”逃生通道”——先想好怎么后悔

这是最实用、也最常被遗漏的一步。

近似结构的最大风险不是”不准”，而是”不可逆”。 Bloom Filter 里有哪 10 亿个元素？不知道，它存不下。HLL 里是哪 10 亿个用户？不知道。一旦业务口径变了、或者发现误差不可接受，你没法从近似结构里回溯出原始数据。

所以上线前必须回答三个问题：

原始数据保留多久？ 哪怕只是留几天的原始日志，也能让你在发现问题时重算出精确值。这是”可逆性保险”——近似结构省下的空间，应该拿出一部分来买”后悔药”。
能否一键切回精确路径？ 保留精确实现的代码路径（哪怕它慢、占内存），配一个开关。当误差超阈值时自动降级到精确路径。
误差超阈值时的业务兜底是什么？ 是”提示数据可能不准”，还是”暂停服务”，还是”用上一周期的精确值”？

一句话：先想好怎么后悔，再决定要不要做。

附：近似采用检查清单（评审会直接用）

在决定引入近似之前，逐条打勾：

☐ 我清楚误差的方向（只偏大 / 只偏小 / 双向），并且确认它在无害的一侧？
☐ 我有理论误差界，还是只有”测出来还行”？如果是后者，我接受吗？
☐ 误差是可测量的吗？我能在线上持续监控它吗？
☐ 我的下游消费者对这个误差鲁棒吗？（LLM 鲁棒，账本不鲁棒）
☐ 这个近似结果会被下游放大或累积吗（多层传递、反复使用）？
☐ 涉及钱、权限、还是决定正确性的控制流？（任一为是 → 停）
☐ 数据分布稳定吗？会不会漂移？
☐ 原始数据的保留期够我重算吗？
☐ 我有一键切回精确路径的逃生通道吗？
☐ 团队里每个人都知道这个值是不准的吗？（文档和命名要标注——比如字段名用 uv_approx 而不是 uv，这是最便宜也最有效的防护）

最后一条值得单独强调：把”这是近似值”写进命名和文档里。 无数线上事故的根源，是半年后接手的新人以为 uv 是精确值，拿它去做了对账。信息会随着代码流传，而”这个值不准”这个知识不会自动跟着走。

演进脉络

1970 年：Burton Bloom 提出 Bloom Filter（最初用于拼写检查的字典压缩）。
1980s-1990s：各种 sketch 算法在数据库和网络测量领域发展（Flajolet 等人的工作）。
2000s：Flajolet 等人提出 HyperLogLog，把基数估计的空间效率推到理论极限附近。
2010s 至今：大数据和实时计算的兴起，让概率数据结构成为标配（Redis 内置 HyperLogLog，各类数据库内置 sketch）。
前沿：学习型索引（learned index）、神经网络近似——用模型替代传统数据结构，是”近似思想”的最新形态。

本章思考题

【思考题】

为什么”允许一点错误”能换来数量级的资源节省？它的信息论根源是什么？
Bloom Filter 的”绝不漏报、可能误报”这个方向性，为什么恰好适配”缓存穿透防护”场景？如果方向反过来会怎样？
“当你无法消除错误时，让错误只发生在代价小的方向”——请再举一个这个思想的应用例子。
什么场景下绝对不能近似？请给出一个可操作的判断标准。
Bloom Filter 为什么不能支持删除元素？Counting Bloom Filter 是怎么解决的，代价是什么？Cuckoo Filter 又换了个什么思路？
Bloom Filter 的哈希函数个数 k，是不是越大越好？为什么存在一个最优 k？位数组长度和误报率之间是什么关系？
HyperLogLog 里，为什么”哈希值前导零的最大长度”能编码基数信息？为什么必须分桶、并且用调和平均而不是算术平均？
Count-Min Sketch 查询时为什么要取多行的最小值，而不是取平均或最大值？它和 Bloom Filter 在结构上是什么关系？
蓄水池采样为什么能保证”每个元素被抽中的概率恰好是 k/n”？请给出推导思路。它在什么场景下是不可替代的？
为什么说”增加样本量能减小方差，但减小不了偏差”？举一个采样偏差的真实案例，并指出它的病因。
为什么精确的最近邻检索在高维下必须让位给近似（ANN）？IVF 和 HNSW 各自”近似”在哪一步？为什么 RAG 场景下 95% 召回通常就够了？
学习型索引（Learned Index）的核心洞察是什么？它最大的工程弱点是什么？为什么 Learned Bloom Filter 必须配一个”备用 Bloom Filter”？
如果要在业务中引入一个近似算法，应该怎么评估”误差是否可接受”？请给出可操作的流程要点。

【参考答案】

信息论根源：精确表示 N 个状态至少需要 log₂N 比特，精确去重需要存储每个元素标识，空间随元素数线性增长。而近似算法放弃”精确区分所有状态”，只给出”够用的估计”，把需存储的信息从”每个元素的标识”压缩成”一个统计量”。信息被压缩是因为需求被放宽了——你不再需要知道”是哪 10 亿个人”，只需要”大概有 10 亿”。
缓存穿透防护用 Bloom Filter 挡”不存在的 key”：误报（说存在、其实不存在）只是多查一次数据库，无害；漏报（说不存在、其实存在）会让本该命中的数据被拒绝，有害。Bloom Filter 的”绝不漏报”恰好让错误落在无害方向。如果方向反过来（可能漏报），就会丢失大量合法请求、造成数据”凭空消失”，是严重 bug。
例子方向：限流用 Count-Min Sketch（只高估不低估，多限一点无害，少限会打爆后端）；有损压缩丢弃人眼/人耳”感知不到”的信息（错误发生在感知不到的方向）；监控采样允许低频指标精度下降但保证高频/异常指标不丢。共同点：识别两种错误的代价不对称，把错误定向到代价小的一侧。
绝对不能近似的场景：涉及钱和账（余额、交易、对账）、安全和权限判定、决定系统正确性的控制流（事务冲突检测、锁判定）、误差会累积放大的场景。判断标准：问一句”如果这个值错了（偏大或偏小），会发生什么”——后果可接受就能近似，不可接受就必须精确。且同一系统内可分级：关键部分精确，其余放宽。
不能删除的原因：多个元素共享同一个位，把某元素的 k 个位清 0，会连带抹掉其他元素对这一位的依赖，导致真正在集合里的元素被判为”不存在”——出现假阴性，直接摧毁”绝不漏报”这个唯一承诺。这是结构性的（共享位 + 不可逆的或操作），不是实现偷懒。 Counting Bloom Filter：把每个位换成小计数器（通常 4 位），插入 +1、删除 -1，计数降到 0 才算真正无人引用。代价：空间放大约 4 倍；计数器会溢出（4 位最多数到 15）；且只能删除”确实插入过”的元素，删不存在的元素会污染结构、制造假阴性。 Cuckoo Filter 换了思路：不存共享位，而是存元素的指纹（若干字节的哈希片段），用布谷鸟哈希放在两个候选桶里。删除时直接删自己的指纹，完全安全。额外好处：支持计数、误报率低于约 3% 时空间更省、只查两个桶所以 cache 局部性更好（Bloom 的 k 次哈希是 k 次随机内存访问）。
k 不是越大越好。误报率 ≈ (1 - e^(-kn/m))^k。k 太小：一次查询只需撞上少数几个位就误报，门槛太低；k 太大：每个元素要置 k 个位，位数组迅速被填满，满到任何查询都全是 1。两个方向都推高误报率，所以中间存在最优值。求极值得到最优 k = (m/n)·ln2 ≈ 0.693·(m/n)，此时代入得误报率 ≈ 0.6185^(m/n)。与位数组长度的关系：m/n = 10 时最优 k ≈ 7、误报率约 0.8%（这就是”每元素约 10 位、误报率约 1%“的来源）。由 0.6185^(m/n) 可得经验律：每元素多加约 5 个位，误报率降一个数量级（10 位≈1%，15 位≈0.1%，20 位≈0.01%）。空间是加法投入，误报率是指数下降。但有理论下界：达到误报率 ε 至少需要约 1.44·log₂(1/ε) 位/元素，绕不过去。
前导零能编码基数的直觉：把元素哈希成均匀随机比特串，“前导零长度达到 r”等价于”抛硬币连续抛出 r 次反面”，概率为 2^(-r)，期望需要 2^r 次试验才见到一次。所以观察到的最大前导零长度为 r，就意味着大约见过 2^r 个不同元素——信息不在”是哪个元素”里，而在”极端事件的罕见程度”里。必须分桶：单个 ρ 的估计方差是常数级（相对误差约 1.12），不随数据量下降，完全不可用。分桶（用哈希前 b 位选桶，m = 2^b 个桶，每桶只保留自己见过的最大前导零）相当于做 m 次独立试验再平均，标准误差降到 1.04/√m。必须用调和平均：每个桶的估计 2^M[j] 是重尾分布，算术平均会被偶然出现的极大桶绑架，导致系统性高估。调和平均（E = α_m·m² / Σ 2^(-M[j])，即对 2^M[j] 取调和平均）的权重天然偏向小值，把离群值的权重压到可忽略，从而消除高估。α_m 是修正常数，用于消除调和平均引入的系统性偏差。补充：小基数（E < 约 5m/2）时要切换到基于空桶数量的 Linear Counting，否则误差很大；基数接近 2^32 时需要大范围修正。
取 min 的原因：每一行的读数都等于”真实频次 + 映射到同一位置的其他元素频次之和”，因为冲突只会往上加，所以每一行都是真实值的一个上界。取最大值是选最松的上界（最差）；取平均会被某一行撞上高频元素拖高（无抗离群能力）；取 min 就是在 d 个上界里挑最紧的那个，即”重复 d 次独立试验，取噪声最小的那次”。这也是名字 Count-Min 的由来。与 Bloom Filter 的结构关系：CM Sketch 是 d 行 × w 列的计数矩阵 + d 个哈希；Bloom Filter 是位数组 + k 个哈希。Bloom Filter 就是 CM Sketch 把计数器从整数压成 1 位的布尔退化版（更新从 +1 变成”置 1”，合并从矩阵加法变成位或）。通用设计路径：把存储单元从布尔升级成计数，“存在性判定”就升级成了”频率估计”。误差界：取 w = ⌈e/ε⌉、d = ⌈ln(1/δ)⌉，则以至少 1-δ 的概率保证”真值 ≤ 估计值 ≤ 真值 + ε·N”（N 为总流量）。宽度 w 控制误差幅度（相对于总量，所以低频元素相对误差大、高频元素准，正合适做热点检测）；深度 d 控制保证成立的概率。工程改进 Conservative Update（只给当前值等于最小值的那几行 +1）能显著降低误差，因为查询取 min，给更大的行加 1 不影响结果却白白增大未来冲突。
推导思路：对第 i 个元素（i > k），它最终留在蓄水池中的概率 = 被选中概率 × 之后每轮都没被替换掉的概率。被选中概率 = k/i。第 j 轮（j > i）目标被踢掉的概率 = (k/j)·(1/k) = 1/j，所以从第 i+1 轮到第 n 轮全部幸存的概率 = ∏(1 - 1/j) = (i/(i+1))·((i+1)/(i+2))·…·((n-1)/n) = i/n。相乘得 (k/i)·(i/n) = k/n，i 被约掉，与位置无关，严格等概率。不可替代的场景：三个约束同时成立——流长度未知、只能遍历一次、内存固定。比如数据库流式扫描采样（不用先 count(*)）、在线日志采样、分布式分片采样（各分片独立跑，合并时按数据量加权重采样）。若需要不等概率，用加权版本（A-Res：以 rand^(1/w) 为排序键取 top-k）。
因为两者来源不同：方差来自”随机抽样的波动”，随样本量 n 增大以 1/√n 缩小；偏差来自”抽样设计本身的系统性缺陷”（抽样框、采样与被测变量相关、时间窗口选择），它是系统性的偏移，样本量再大也只会让估计值更精确地收敛到那个错误的值上。所以偏差是设计问题，不是规模问题。真实案例：1936 年美国总统大选，《文学文摘》发出 240 万份民调，预测兰登将压倒性击败罗斯福，结果罗斯福赢下 46 个州。病因是抽样框偏差——名单来自电话簿和汽车登记记录，而大萧条时期有电话有汽车的是相对富裕群体，恰好倾向于共和党。240 万个样本也纠正不了系统性的抽样框错误。工程中的同类病因（采样过程与要度量的量相关）：监控均匀采样会系统性丢掉罕见但关键的错误样本（乘回去能还原”数”，但还原不了”个体”）；A/B 测试里的新奇效应（时间窗口偏差）、辛普森悖论（分组权重不等于总体权重）、peeking（重复检验导致假阳性膨胀）。解法方向：分层采样、尾部采样（延后决策到信息完备后，OpenTelemetry 的做法）、按 1/rate 加权还原、预注册实验与固定样本量。
必须近似的原因：精确方案有两条路，暴力扫描是 O(N·d)（十亿 × 1024 维，单次要几分钟）；空间索引（KD 树等）在低维有效，但维度灾难使其失效——高维下随机点间距离趋于相等，“距离下界剪枝”剪不动任何子树，维度超过约 10 维就退化到接近暴力扫描。所以在高维向量检索里，近似不是优化选项，而是唯一可行路径。 IVF 近似在哪：先用 k-means 把空间切成 nlist 个簇，查询时只搜最近的 nprobe 个簇（典型取 1%~10%），把全局搜索变成局部搜索。漏检来自”簇边界效应”——真实最近邻可能在边界另一侧。IVF-PQ 再叠加乘积量化（分段 k-means + 8bit 编码），既省内存（压缩可达几十倍）又能用查表法算近似距离，这是”有损压缩”思想在向量上的复现。 HNSW 近似在哪：建多层可导航小世界图，上层是稀疏的长边”高速公路”，底层是稠密近邻图；查询时顶层贪心粗定位、逐层下降、底层用 efSearch 宽度的 beam search 精修，总跳数与 log N 同阶。它只保证”高概率走到目标附近”，不保证数学最优。 RAG 场景下 95% 召回通常够用，因为上游能近似到什么程度，取决于下游消费者对误差的鲁棒性：检索结果最终交给 LLM 阅读，只要最关键的那一两条在上下文里，少召回一条对最终答案几乎无影响。反例是法律/医疗检索（漏一条可能是事故），此时需要混合检索（BM25 + 向量 + rerank）兜底——因为两种检索的失败模式不相关，融合能抬高召回上界。
核心洞察：索引本身就是一个模型。在已排序数组上，“key → 位置”就是位置 ≈ N·CDF(key)。B 树用一棵树隐式分段拟合了这个 CDF，且不对数据分布做任何假设，因此 O(log N) 本质上是对”分布无知”所交的税。真实数据分布有结构（如自增 ID 的 CDF 几乎是直线），用模型拟合就能跳过这棵树。这与熵编码同源：都是用分布的先验知识换掉通用性的税。最大工程弱点：所有预测质量保证的性质都变了。① 插入/更新会改变位置映射，模型需重训练，只能靠预留空隙 + 溢出缓冲区缓解（本质是用写放大换读加速，和 LSM 同思路）；② 误差只有经验界没有理论界——Bloom/HLL/CM 的误差是可证明的概率界，学习型结构只有”测出来的”界；③ 分布漂移时会静默退化（不报错，只是越来越慢），比崩溃更危险；④ 模型推理的乘加成本不一定低于几次 cache 友好的指针跳转，往往需要 SIMD/GPU 才划算。 Learned Bloom Filter 必须配备用过滤器的原因：模型会犯错，可能给真正在集合里的元素打低分并直接判”不存在”，产生假阴性，从而打破 Bloom Filter “绝不漏报”的核心承诺。补法是用一个只装”被模型误判为不存在的元素”的备用 Bloom Filter 接住这部分查询。这揭示了”用 ML 做近似”的范式：模型负责利用分布先验压缩工作量，传统结构负责兜住正确性下界；模型提供效率，传统结构提供保证。 一句话：传统数据结构的保证是”证明出来的”，学习型结构的保证是”测出来的”。
可操作流程要点（八步）：① 定义误差度量——区分绝对/相对误差，给出误差的分布（p50/p95/p99/max）而非均值，明确方向性与误差随规模的变化；② 把误差翻译成业务损失（钱/风险/体验），且必须区分”看趋势”和”拿去结算”等不同用途；③ 找”决策翻转点”——不看误差绝对值，看误差多大时会改变决策（A/B 测试的置信区间是否跨 0、指标是否跨告警阈值、报表排名是否翻转），离边界远的地方大胆近似，近的地方保守；④ 离线回放，用精确算法作 ground truth，输出完整误差分布并重点看 p99/max（离线结果只能当误差下界）；⑤ 按关键维度切片（渠道、地区、用户分层、时间、长尾 vs 大客户），因为聚合误差会掩盖子群误差；⑥ 压测边界场景——极小量、极大量、分布突变（大促/攻击）、极端倾斜；⑦ 线上影子双跑，且监控误差本身而非结果本身（定期精确重算对账、给误差设 SLO 和告警，优先级高于指标告警）；⑧ 设计逃生通道——保留原始数据一段时间以便重算、一键切回精确路径的开关、误差超阈值时的业务兜底。附十项检查清单：误差方向是否在无害侧、有理论界还是仅有经验界、误差是否可在线测量、下游是否鲁棒、是否会被放大累积、是否涉及钱/权限/控制流、分布是否稳定、原始数据保留期是否够重算、是否有逃生通道、全团队是否知道这是近似值（把 uv_approx 写进命名和文档）。

徐术挺-漫思录

探索

05-精确与近似的权衡