LRU 相信最近，布隆过滤器只确定“没有”
一句话总结
缓存是在押“马上还会再用的东西”，LRU 押的是“刚用过的马上还会再用”。布隆过滤器则相反，它只承诺“一定没有”，换来的是用极少的比特就能携带一个集合。必须知道它们各自相信什么，用起来数字才会符合预期。
为什么需要它
在慢速存储前面放上快速存储的那一刻，就会产生两个问题。空间不够时丢掉什么？以及，本来就不存在的东西，还有必要一路跑到慢的那一边去找吗？
第一个问题的教科书答案是 LRU（least recently used）。functools.lru_cache 文档写道，LRU 缓存在“最近的调用最能预测即将到来的调用”时效果最好，并以每天都在变化的新闻服务器上的热门文章为例。反过来说，在这个假设被打破的访问中——遍历一遍全部键的批处理或回填——LRU 会把再也不会来的键当成“最近”来供着，结果反而把真正常用的键赶了出去。Cache replacement policies 词条把这称为 cache pollution（缓存污染）。
第二个问题就是布隆过滤器的用武之地。确认是否已注册、过滤已经见过的 URL、用不存在的键来敲打的机器人请求，这类答案大多是“不存在”的查询，即使把否定结果也放进缓存，键空间一大就会很快被挤出去。Broder 和 Mitzenmacher 的综述 Network Applications of Bloom Filters: A Survey（Internet Mathematics 第 1 卷第 4 期）把这总结为“布隆过滤器原则”——如果要用列表或集合，空间又很紧张，并且能够降低假阳性的影响，就请考虑布隆过滤器。
工作原理
让 LRU 达到 O(1)。 需要的操作有三个：按键查找、标记为“刚用过”、丢弃最久没用的。哈希表负责第一个，双向链表以常数时间完成另外两个（把节点摘下来接到最后，并摘掉最前面的那个）。在 Python 中，OrderedDict 已经具备这个组合。文档写道，OrderedDict 的设计使它擅长重新排序操作，适合用来构建各种 LRU 缓存，并提供 move_to_end(key)（键不存在时抛出 KeyError）和 popitem(last=False)（按 FIFO 顺序取出）。
| 操作 | LRU | FIFO |
|---|---|---|
| get 命中 | 移到最后（最近） | 保持不动 |
| 对已有的键 put | 更新值 + 移到最后 | 只更新值 |
| 溢出时 | 移除最前面的（最久没用的） | 移除最前面的（最先进来的） |
表中的第一行几乎就是两种策略之间的全部差别。因此在 get 中漏掉最近性更新的 LRU，就成了名字叫 LRU 的 FIFO，命中数会悄悄减少。如果用列表（list）来管理顺序，remove 是 O(n)，容量越大就越慢，而在小规模测试里看不出来。
现实中的缓存也并不是精确的 LRU。Redis 的 eviction 文档说明，Redis 采用的是一种近似做法：随机挑几个键，淘汰其中最久没用的，因为真正的 LRU 要占用更多内存（采样数为 maxmemory-samples）。
布隆过滤器。 由一个 m 位的数组和 k 个哈希构成。插入时把 k 个位置置为 1；查询时如果 k 个位置全是 1 就是“可能有”，只要有一个是 0 就是“一定没有”。已置位的比特不会被清除，所以对已插入的键不会出现假阴性。按综述第 2.1 节的计算，插入 n 个之后的假阳性率约为 (1 − e^(−kn/m))^k，当 m 和 n 确定后，k = (m/n)·ln 2 时最小。第 2.2 节把目标假阳性率 p 所需的比特数写为 m ≈ n·log2(1/p) / ln 2。举个例子，n = 1,000、p = 1% 时，m 约为 9,586 比特（略多于 1.2KB），k 为 7。
也不必另外求出 k 个独立的哈希。Kirsch 和 Mitzenmacher 的 Less Hashing, Same Performance（2008）证明，用两个哈希 h1、h2 构造 g_i(x) = h1(x) + i·h2(x)，渐近的假阳性率也不会变差。本实验从 hashlib 的 sha256 摘要（32 字节）中取出 h1 和 h2。不使用内置的 hash()，是因为按 PYTHONHASHSEED 文档，字符串哈希的种子默认是随机的，别的进程做出的过滤器就无法按同样的规则读取。
测量假阳性率时，分母是针对确实不存在的键的查询次数。如果除以全部查询，数值会按存在的键的比例变小，过滤器就会显得比实际更好。
在现场相遇的样子
ClickHouse 的 skip index 中的 bloom_filter 接收一个允许的假阳性率作为参数（默认 0.025），文档说，假阳性只不过是多读几个不必要的块，并不是大问题。“ClickHouse — 从内部理解列式分析数据库”课程会用真实的 granule 数量展示这一场景。过期与 eviction 策略的选择以及 cache-aside 由“Redis 与缓存”课程讲，同样的局部性逻辑在 CPU 缓存层级中如何体现，则由“计算机组成”课程讲。本模块是亲手做出垫在这些之下的数据结构，并用数字来确认。
下一项实验要做什么
用偏斜的访问记录，按容量分别测出 LRU 和 FIFO 的命中数，并统计一次性扫描会把多少热点键挤出去。接着用公式选出 m 和 k，按规定好的哈希规则构建布隆过滤器并测出假阳性率，然后计算：把过滤器放在 LRU 前面，数据库查询能少几次。