算法与数据结构 / 缓存淘汰 · 从 Bélády 上界到 SIEVE / W-TinyLFU：准入判定与频率草图 待审核 4 / 7
Count-Min sketch · 减半老化 · window 加 SLRU

W-TinyLFU：准入判定与频率草图

到目前为止的策略共享一个隐含前提：被访问到的 key 一律先装进缓存，区别只在于此后淘汰谁。这个前提在一次性对象占多数的流量上代价很大——每一个只会被访问一次的 key 都要先挤掉一个可能还有用的老 key，然后自己再被挤掉。

TinyLFU 把问题换了一个：这个 key 凭什么进来。

1 · 准入判定

定义 1.1（准入判定） miss 发生时，先定出若不准入则将被淘汰的那个 key，称为 victim；再比较新来者 candidate 与 victim 的历史访问频率估计。仅当 candidate 的估计严格大于 victim 的估计时才准入，否则新来者被直接丢弃，缓存内容不变。

这条规则要求一件此前的策略都做不到的事：知道那些不在缓存里的 key 被访问过多少次。LFU 的计数表只覆盖缓存内的 key，一个 key 被淘汰后计数就归零，否则计数表会随 key 空间无限增长。

要给全体 key 保留频率，只能放弃精确。

2 · 用两千字节记住所有 key 的频率

TinyLFU 用 Count-Min sketch 存频率：深度 4 的计数器矩阵，每行宽度是 2 的幂，第 jj 行用一个独立的散列把 key 映到本行的一个格子。increment 时四行各加一，estimate 时取四格的最小值。

计数器只有 4 位，上限 15。这个位宽不是省内存的将就，而是与准入判定的语义匹配：判定只需要比较两个 key 谁更热，不需要知道具体多少次。

散列碰撞只会让计数偏高，不会偏低：两个 key 撞在同一格时，那一格记的是两者之和。取四行的最小值把高估压到很小：实测容量 200 对应宽度 1024、共 4096 个 4 位计数器（2048 字节），灌进 1999 次访问、涉及 645 个不同 key 后，621 个 key 的估计与真值完全一致，24 个偏高，最大偏高 2。

图 2-1 · Count-Min sketch 的四行探测。高亮格是某个 key 的四个落点，取最小值即为估计。下方是全体 key 的估计误差分布。可切换查询 key，并推进灌入次数触发减半。

3 · 减半：让计数器忘掉旧账

淘汰策略是在猜未来 §4 里 LFU 的病根是计数只增不减。TinyLFU 的处方极简单：累计 increment 次数达到 sampleSize 时，把整张表所有计数器右移一位。

减半是一次全表操作，但它均摊到 sampleSize 次访问上；实现里 sampleSize 取容量的十倍，容量 200 就是每 2000 次访问减半一次。实测 20000 次访问的 Zipf workload 上共触发 19 次减半。

减半保留了相对大小：一个估计 12 的 key 与一个估计 3 的 key，减半后是 6 与 1，谁更热的结论不变。而绝对值的缩小让新 key 有机会追上，它只需要攒到 7 次就能超过那个曾经 12 次的老 key。老化被实现成一次移位，而不是一个衰减系数。

4 · window 与 SLRU 的分工

纯 TinyLFU 有一个明显的破绽：一个刚刚变热的 key，估计频率还是 0，永远进不来。W-TinyLFU 的 W 就是为它加的。

缓存被切成两段：

  • window LRU，占容量的 1%，新 key 无条件先进这一段
  • 主体 SLRU，占 99%，内部再分 probation 与 protected 两段，protected 占主体的 80%

新 key 先在 window 里活一小段时间。若它在这段时间里被再次访问，sketch 的计数已经涨上来了；等它从 window 的末端被挤出时，再以 candidate 的身份接受准入判定。突发的新热点因此有一个不需要通过准入就能被命中的缓冲区。

主体的 SLRU 分段则解决另一个问题：进了主体的 key 也分两等，只被访问过一次的待在 probation，再被访问一次就升进 protected；淘汰只从 probation 的末端取。

实测这两个比例的敏感度差别很大。window 占比从 1% 提到 40%，Zipf 上命中率从 68.5% 降到 66.5%，纯循环扫描上从 38.6% 崩到 23.4%。window 越大，未经准入就能占住的容量越多。protected 占比反过来，从 20% 提到 95%，Zipf 上命中率从 66.9% 升到 69.4%。Caffeine 后来把 window 大小也做成了自适应的，用爬山法在线搜索。

图 4-1 · window 与 protected 两个比例对命中率的影响。两条曲线分别扫描一个比例、固定另一个。可切换 workload。

5 · 准入判定值多少

关掉准入判定（其余结构不变）再跑一遍，差额就是它的贡献：

workload 带准入 关掉准入 差额 候选拒绝率
Zipf 68.5% 67.4% +1.13 82.4%
热集叠加扫描 40.1% 38.8% +1.29 90.5%
突发热点 88.7% 88.8% −0.13 44.5%
纯循环扫描 38.6% 0.0% +38.61 98.4%

前两行的一两个百分点是常规收益。第三行是负的：热点整批迁移时，准入判定会把刚变热的新 key 拦在门外，帮了倒忙。第四行才是它的极端形态。

再看一个专门构造的 workload：150 个热 key 反复访问，另有一半流量每次都是一个全新的 key（20000 次访问里出现了 10075 个不同 key，容量 200）。

策略 命中率 末态缓存里的热 key
Bélády 49.6% —
W-TinyLFU 49.2% 150 / 150
关掉准入 48.5% 150 / 150
LFU 48.6% —
LRU 27.6% 79 / 150
FIFO 23.4% —

W-TinyLFU 把 150 个热 key 一个不少地留在了缓存里，LRU 只剩 79 个。但有一处值得说明白：关掉准入判定后，热 key 同样是 150 个不少，命中率只低 0.7 个百分点。也就是说在这条 workload 上，护住热 key 的主要是 SLRU 的 protected 段，不是准入判定；准入判定的贡献要到一次性对象占到七成以上才显著（占比 0.9 时是 6.7% 对 5.0%）。原先以为这个实验能干净地隔离出准入的作用，实测下来它隔离不出来，得靠上面那张 workload 表。

图 5-1 · 一次性对象占比从 0.2 到 0.9 时三种配置的命中率与热 key 存活数。可调热集大小与容量，观察准入判定何时才成为主要贡献者。

6 · 严格大于带来的冻结

上表第四行值得单独解释。纯循环扫描下 W-TinyLFU 拿到 38.6%，是唯一没被扫描打成零的策略，达成率 99.0%。

原因不在于它聪明。循环扫描里每个 key 的访问频率完全相同，sketch 给出的估计也就完全相同；准入判定用的是严格大于，估计相等时候选被拒。于是主体 SLRU 里最先装满的那 198 个 key 再也换不出去，缓存被冻住了。而冻住恰好就是这条 workload 的最优策略——Bélády 的做法也是锁死 199 个 key 不动。

这个巧合在别的 workload 上就不是好事了：估计相等时永远拒绝新来者，意味着一个真正的新热点要等到 sketch 减半把老 key 的估计压下去才进得来。Caffeine 的实现为此在低频段加了随机化：候选与 victim 的估计都不高时，按概率决定放不放行。本页的实现没有加这一步，所以第四行那个 38.6% 比 Caffeine 的真实行为更极端。

7 · 参考文献

  1. Einziger, G., Friedman, R., & Manes, B. (2017). TinyLFU: a highly efficient cache admission policy. ACM Transactions on Storage, 13(4), Article 35.
  2. Cormode, G., & Muthukrishnan, S. (2005). An improved data stream summary: the count-min sketch and its applications. Journal of Algorithms, 55(1), 58–75.
  3. Karedla, R., Love, J. S., & Wherry, B. G. (1994). Caching strategies to improve disk system performance. Computer, 27(3), 38–46.
  4. Manes, B. (2016–). Caffeine: a high performance caching library for Java. GitHub 项目 wiki 的 Efficiency 与 Design 两节。