W-TinyLFU

定义

W-TinyLFU(Window TinyLFU)是在 TinyLFU 基础上发展出的缓存管理算法,由 Gil Einziger、Roy Friedman 与 Ben Manes 等人提出,核心思想是用极小的内存近似统计访问频率,并以「准入控制」决定新条目是否值得进入缓存。

原理

算法用 Count-Min Sketch 风格的计数草图记录键的近似频率,并周期性将计数减半以实现时间衰减。缓存空间分为小的窗口区(LRU,吸收突发流量)和主区(分段 LRU);当窗口区淘汰的候选者想进入主区时,需与主区的受害者比较频率,频率更高者才被保留。

优缺点

优点是以 O(1) 时间和极低的元数据开销取得接近最优的命中率,兼顾新热点与长期热点;缺点是实现复杂,频率草图存在哈希冲突带来的误差。

应用

最著名的实现是 Java 高性能本地缓存库 Caffeine,此外多种数据库与存储系统的缓存层也采纳了该算法。