布隆过滤器：一个很小的“肯定不在”测试，代价是几个错的“可能在”

它是干嘛的。 回答“这个东西在集合里吗”，集合大到没法全放内存，或者查真正的存储要一次磁盘读的时候用。它只是个预筛，永远不是最终答案：它只是让你大多数时候不用去问那个贵的问题。

想法。 不存东西本身，只存它留下的几个痕迹。查的时候算同样的痕迹位置：有一个痕迹缺了，这个东西就一定没加入过。痕迹全在，这个东西可能加入过，也可能是别的的东西的痕迹凑巧盖住了这几个位置。

怎么建。 一个位数组，开始全是 0，再加几个 hash 函数。hash 函数把一个 key 算成一个位置，而且是确定的：同一个 key 每次算出来的位置都一样。加入一个 key，就是用每个函数算一遍，把那几个位设为 1。位是共用的：好几个 key 都可能置同一个位。

怎么查。 用同样的函数算要查的 key，验这几个位。有一个位是 0，这个 key 一定没加入过：永远没有漏判。几个位全是 1，这个 key 可能加入过：误判可能有。

实测例子：10 个位，2 个 hash。 加入 apple：置 3 号和 7 号位。加入 banana：置 2 号和 7 号位。查 cherry：算出来是 3 号和 5 号位，5 号位是 0，所以 cherry 一定不在。查 grape：算出来是 3 号和 7 号位，全是 1，所以 grape 可能在，但实际是 apple 和 banana 的痕迹拼出来的：一次误判。

“可能在”的代价。 一次误判就是多查一次真正的存储，仅此而已。误判率可以调：数组越大越低，hash 函数越多先降后升，因为函数太多会把太多位置亮。常用工作点是一个 key 大概 10 个位，误判约 1%。数组要按它这辈子能装的最大集合来定：最优负载下大概一半的位是 1，再往上误判率就爬得很快。

它干不了什么。 不能删：一个位可能被好几个 key 共用，清零会误伤别人。counting 变种把每个位换成一个小计数器，删就有了，代价是几倍的空间。它给不出值，只能回答在不在。它也证明不了存在：“可能在”永远不是“在”。

谁在用。 LSM 存储里每张 SSTable 一个过滤器（Cassandra、RocksDB、HBase、ScyllaDB）：过滤器跟表一起存在磁盘上，查的时候读进数据库共用的那一个块缓存，在读任何数据块之前先跳过整张表。同样的形状还出现在所有“便宜的一句肯定不在能省下一次贵的检查”的地方：爬虫跳过见过的 URL，路由器和缓存跳过不存在的 key。

一个语义上的亲戚，以及它为什么很少人用。 把 hash 函数换成局部敏感 hash（相似的向量有很大概率撞到同一个桶），就得到 distance-sensitive Bloom filter，承诺“集合里肯定没有语义相近的东西”。但实践中漏判确实会出现，因为 LSH 不保证碰撞；消灭漏判的变种存储随半径指数涨，而且它需要的近远间隔很宽。所以精确的存在判断还是经典布隆的活，语义找邻居还是向量索引的活。

Transfer。 lsm-tree 的读路径就是这个过滤器挣钱的地方：它定查哪张表，二分查找定表里查哪。

Kin。 lsm-tree

给 agent 的检查清单。读完本节点，按每一条去验一个过滤器部署，验出结果要带证据。

1. 查的语义：说没有就是没有，说有就是可能有；没有任何调用方把“可能在”当成“在”。
2. 定尺寸：每个 key 几个位、用几个 hash 要写明，数组按最大集合定，误判率是测出来的不是想当然的。
3. 删除：要么设计上就没有删（不可变表），要么是 counting 变种且空间代价写明。
4. 缓存位置：过滤器跟数据一起在磁盘上，读进共用的缓存，不是每张表各一个缓存。