缓存算法 #05：W-TinyLFU 与 Caffeine

W-TinyLFU 是 Caffeine（Java 高性能本地缓存库）的核心算法，接近最优缓存命中率，同时规避了 ARC 的专利问题。它用 Count-Min Sketch 解决 LFU 的频率老化问题，用 Window 区解决新晋热点难以进入缓存的问题。本文深入三个核心组件的算法细节。

相关文章：LRU（最近最少使用） · LFU（最少使用频率） · ARC（自适应替换缓存）

目录

设计目标与背景

纯 LFU 的两个问题

问题1：频率老化（Frequency Aging）
  某 key 历史上被访问了 10000 次，现在已无人问津
  新热点 key 只有 50 次访问
  → LFU 保留历史高频 key，驱逐新热点 → 命中率低

问题2：新晋热点难以进入（Cold Start）
  新 key 刚加入缓存，频率=1，处于最低优先级
  下一次缺页时立刻被驱逐，刚加载就淘汰
  → 新热点没有"生存期"，无法积累频率

TinyLFU 的解法：
  用 Count-Min Sketch 替代精确频率计数（解决老化）
  加入 Window 区保护新加载的 key（解决 Cold Start）

Count-Min Sketch 频率估计

Count-Min Sketch 是一种概率型数据结构，用极小空间近似统计每个 key 的访问频率。

数据结构

d 行 × w 列 的计数器矩阵（通常 d=4，w=与容量相关）
d 个相互独立的哈希函数 h1, h2, ..., hd

increment(key):
    for i in 1..d:
        col = h_i(key) % w
        sketch[i][col] += 1
        // 每行各自在不同列 +1

estimate(key):
    return min(sketch[1][h1(key)%w],
               sketch[2][h2(key)%w],
               ...,
               sketch[d][hd(key)%w])
    // 取各行的最小值（过估计误差，取最小最保守）

为什么取最小值

碰撞情况：key=A 和 key=B 共享了 sketch[1][5] 这个槽
  key=A 被访问 10 次，key=B 被访问 100 次
  → sketch[1][5] = 110（混合计数）
  → estimate(A) 从第1行得到 110（过高）
  → 但从其他行（B 没有与 A 碰撞的行）得到正确的 10
  → min(110, 10, 10, 10) = 10 ✅

最小值策略保证：estimate(key) >= 真实频率（永不低估）
                 estimate(key) 尽可能接近真实频率

Caffeine 的 4 bit 计数器优化

标准 Count-Min Sketch：每个槽用 int（32 bit）
Caffeine 优化：每个槽只用 4 bit（0~15）

理由：
  缓存大小有限（比如 1000 个槽位）
  即使某 key 访问了百万次，在有限缓存中它的相对频率才有意义
  超过 15 的计数对排序没有额外意义
  4 bit 节省 8 倍空间，使 Sketch 能全部放入 L1/L2 Cache

sketch 结构（Caffeine 实际实现）：
  long[] table，每个 long 存 16 个 4-bit 计数器
  table 大小 = capacity（与缓存容量相同）

Doorkeeper 预过滤

问题：对每一个 get 请求都调用 increment(key) 更新 Sketch
      高并发下 Sketch 更新频繁，且大量 key 只访问一次（一次性 key）
      用 4 bit 计数浪费在只访问一次的 key 上

Doorkeeper（看门人）：在 Sketch 前面加一个 Bloom Filter

规则：
  第一次访问 key：加入 Bloom Filter，不更新 Sketch（频率视为 0）
  第二次及以后访问 key：Bloom Filter 已有记录，才更新 Sketch

效果：
  只访问一次的 key 不占 Sketch 空间
  Sketch 只统计"至少访问过两次"的 key 的频率
  大幅降低 Sketch 的碰撞率，提高频率估计精度

代价：
  Doorkeeper 中 key 的频率低估 1（首次不计入 Sketch）
  admission 判断时需要补偿：estimate(key) + 1（if key in doorkeeper）

W-TinyLFU 整体结构

缓存总容量 c，分为两个区域：

┌─────────────────────────────────────────────────────────┐
│  Window Cache（约 1% 容量）  │      Main Cache（约 99%）  │
│                              │                           │
│  LRU 结构                    │  Protected LRU（80%）     │
│  新加载的 key 先进这里         │  Protected: 经过 Probation│
│                              │  确认是热点的 key         │
│  容量满时，驱逐 Window 的      │                           │
│  LRU 端 → 作为 candidate     │  Probationary LRU（20%）  │
│  进入 Main 的 Admission 判断  │  Probation: 从 Window    │
│                              │  进入 Main 的新 key        │
└──────────────────────────────┴───────────────────────────┘
                           ↑
               TinyLFU Admission Filter
               candidate.freq vs victim.freq
               谁的频率高，谁进入/留在 Main Cache

各区大小（Caffeine 默认）：
  Window    = 1% × c
  Probation = 20% × (c - Window)
  Protected = 80% × (c - Window)

完整伪代码

数据访问 get(key)

get(key):
    if key in Window:
        Window.moveToMRU(key)       // Window 内 LRU 更新
        frequency.increment(key)    // 更新 Sketch
        return Window[key].value

    if key in Main（Protected 或 Probationary）：
        if key in Probationary:
            // 从 Probation 升级到 Protected 头部
            node = Probationary.remove(key)
            if Protected 满：
                // Protected 溢出 → 降级最旧的到 Probationary 头部
                demoted = Protected.removeLRU()
                Probationary.addMRU(demoted)
            Protected.addMRU(node)
        else:
            Protected.moveToMRU(key)

        frequency.increment(key)
        return Main[key].value

    return -1  // miss

数据写入 put(key, value)

put(key, value):
    if key 已在缓存中（Window 或 Main）：
        更新 value，调用 get 逻辑移动位置
        return

    // 新 key：先放入 Window
    if Window 未满：
        Window.addMRU(Node(key, value))
    else：
        // Window 满 → 驱逐 Window 的 LRU 端
        candidate = Window.removeLRU()
        Window.addMRU(Node(key, value))

        // Admission：candidate 能否进入 Main？
        admit(candidate)

admit(candidate) — TinyLFU 准入判断

admit(candidate):
    if Main 未满：
        // Main 还有空间，直接放入 Probationary
        Probationary.addMRU(candidate)
        return

    // Main 满 → 找 victim（Probationary LRU 端）
    victim = Probationary.peekLRU()

    freq_c = frequency.estimate(candidate.key)
    freq_v = frequency.estimate(victim.key)

    if freq_c > freq_v:
        // candidate 频率更高 → 驱逐 victim，让 candidate 进入
        Probationary.removeLRU()
        Probationary.addMRU(candidate)
        // victim 从缓存彻底删除
    else:
        // victim 频率 >= candidate → candidate 被拒，直接丢弃
        // candidate 完全不进入 Main Cache
        discard(candidate)

执行追踪

capacity=10，Window=1，Main=9（Protected=7,Probation=2），演示新热点如何晋升：

初始状态：Main 中有稳定热点 K1~K9，每个频率 >> 10

step1：put(new_key=X, v)
  X 进入 Window（Window: [X]）

step2：get(X) × 3 次（X 被反复访问）
  每次访问：X 在 Window，moveToMRU，frequency[X] 累计到 3
  Window: [X]，freq[X]=3

step3：put(Y, v)（新 key 进来，Window 满了）
  candidate = Window.removeLRU() = X（Window 只有 1 个，就是 X）
  X 进入 admit 判断：
    victim = Probationary.LRU 端（假设是 K2，freq[K2]=2）
    freq[X]=3 > freq[K2]=2 → X 准入！
    Probationary: [X, ...] （X 进入 Probationary 头部）
    K2 被驱逐

step4：get(X) 继续累积到 freq[X]=8
  X 仍在 Probationary，反复被访问时：
  第一次从 Probationary 命中 → 升级到 Protected

如果 X 频率不足（step2 中只访问 1 次，freq[X]=1）：
  candidate=X，victim freq=2 > 1 → X 被拒绝，直接丢弃
  Window 里的新 key 没有积累足够频率就被驱逐 → 不浪费 Main 空间

老化机制

问题：Count-Min Sketch 的 4-bit 计数器会饱和（最大 15）
     历史高频 key 的计数一直是 15，新热点无法超越它

Caffeine 的解法：定期将所有计数器减半（aging）

触发条件：
  每当累计的 increment 次数 = c × 10（约每个槽位被更新 10 次）
  执行一次 reset()：所有计数器 >> 1（右移一位，相当于除以 2）

效果：
  旧高频 key：15 → 7 → 3 → 1（随时间衰减）
  新热点 key：1 → 2 → 4 → ...（持续上升）
  最终新热点超越旧高频 → 进入缓存

reset() 伪代码：
  reset():
      for i in range(rows):
          for j in range(cols):
              sketch[i][j] >>= 1    // 4-bit 计数器右移 1 位
      doorkeeper.clear()             // 清空 Bloom Filter，允许重新计数
      size = 0                       // 重置累计计数

Caffeine 的工程优化

异步写缓冲（Buffer + Draining）

问题：每次 get 都需要更新 Sketch 和移动链表节点，高并发时锁竞争严重

Caffeine 的解法：
  读操作（get）：更新操作不立即执行，写入一个无锁 RingBuffer
  写操作（put/evict）：同样先写 RingBuffer

  后台线程定期"drain"（清空）RingBuffer，批量执行更新

好处：
  get 的热路径几乎无锁（只写 RingBuffer，CAS 操作）
  批量执行减少锁竞争，提高吞吐

类比：MySQL 的 Change Buffer 思路——延迟合并，减少随机 I/O

W-TinyLFU vs ARC 性能对比

参考资料

• Einziger, G. & Friedman, R. (2014). TinyLFU: A Highly Efficient Cache Admission Policy
• Manes, B. (2015). Caffeine: A high performance caching library for Java. https://github.com/ben-manes/caffeine
• Caffeine Wiki: https://github.com/ben-manes/caffeine/wiki/Efficiency