Caffeine 缓存算法

一、前言

Caffeine 之所以能在性能和命中率上碾压 Guava Cache 和 Ehcache，核心在于它采用了一种名为 W-TinyLFU 的算法

为了透彻理解 W-TinyLFU，此处将按照算法演进的逻辑，将其拆解为四个部分来讲：

1. LRU (基础)：传统 LRU 算法说明与痛点
2. LFU (基础)：解决 LRU 算法的扫描流量问题
3. TinyLFU (频率统计)：在 LFU 算法的基础上解决内存占用与过气热点问题
4. W-TinyLFU (架构融合)：在 TinyLFU 算法基础上进一步解决突发热点问题

二、正文

1. LRU 算法及其困

1.1. LRU 算法说明

LRU (Least Recently Used，最近最少使用) 是大多数缓存的默认算法：

• 逻辑：如果一个数据最近被访问过，那么它将来被访问的几率很高
• 实现：维护一个链表，将新数据放在头部，老数据在尾部，当缓存满了就淘汰尾部的数据

1.2. LRU 算法缺陷

LRU 算法无法抵抗“扫描流量” 假设当前存在一个使用LRU算法的100条容量大小的缓存：

1. 缓存中已经存储 100 条热点数据（经常被访问的数据）
2. 突然进行全表扫描（如遍历数据库），一次性读取了 1000 条冷数据（访问频次很低的数据）
3. 结果：由于冷数据是最近访问的，LRU 会把 100 条热点数据驱逐，再填满 100 条冷数据（只用一次的垃圾数据）
4. 后果：缓存命中率瞬间跌至 0，数据库压力激增，这就是“缓存污染”

1.3. LRU 的替代算法：LFU、TinyLFU

为了解决 LRU 算法无法抵抗“扫描流量”的问题，需要引入 LFU （Least Frequently Used，最不常使用） 算法：

• 逻辑：根据数据的“访问次数”作为数据淘汰的依据
• 缺点：但是传统的 LFU 极其耗费内存（每个数据都要存一个计数器），且难以处理“过气热点”问题

Caffeine 提供了另一套解决方案：TinyLFU，很好的解决了内存占用问题

2. TinyLFU 算法说明

2.1. TinyLFU 简述

TinyLFU 算法并非一个完整的缓存替换算法，它类似于过滤器

TinyLFU 算法的核心思想是：仅当新数据的预计价值（频率）高于要被淘汰的老数据时，才允许新数据进入缓存

为了实现这一点，Caffeine 必须解决一个难题：如何用极小的内存记录海量数据的历史访问频率？

2.2. TinyLFU 针对内存占用的改进方案

如果为每个 CacheKey 都配一个 int 类型的计数器，那么缓存的整体内存占用过大

Caffeine 使用了 Count-Min Sketch 近似计数算法来统计近似的访问频率（类似于BitMap）：

• 原理说明：

  • 一个二维数组（实际上被 Caffeine 优化为一维 long 数组配合位运算）
  • 包含 4 个 Hash 函数，用于计算数据的位值
  • 整体原理类似于布隆过滤器，但记录频率赋值上有所不同

• 记录频率：当 Key A 被访问，通过 4 个 Hash 函数映射到数组的 4 个位置，将这 4 个位置的计数器都 +1

• 读取频率：当查询 Key A 的频率时，用同样的 Hash 函数找到 4 个位置，取其中数值最小的那个作为估计值

• 算法特点：

  • 节省内存：不需要存维护 CacheKey 与访问频次的映射数组，依靠 BitMap 就可以达成近似效果
  • 容忍误差：BitMap 特性，由于 Hash 碰撞，访问频次统计值可能会偏大，但绝不会偏小，在缓存场景下，稍微高估一点非热点数据的频率被认为可以接受

2.3. TinyLFU 针对过气热点的解决方案

LFU 算法还有个问题：一个数据以前访问频次很高（如昨天的热搜），过一段时间访问频次降低逐渐归零，但由于该数据的历史访问频率高，所以该数据不会被驱逐

Caffeine 为此引入了保鲜机制：
当统计的总次数达到一个阈值（如缓存大小的 10 倍）时，会将所有记录的频率除以 2

• 热点数据：15 -> 7（频次仍然很高，被保留）
• 过气数据：2 -> 1（甚至衰减为 0，被淘汰）

保鲜机制保证了频率统计能反映缓存数据近期的热度，而非历史总热度

3. Caffeine 的架构整合算法：W-TinyLFU

3.1. LFU、TinyLFU 算法对突发热点数据的缺陷

LFU 与 TinyLFU 算法对突发流量不友好：

• 新的数据访问频率总为1
• 新数据如果直接和缓存中频率较高的老数据对比，那么新数据永远无法进入缓存
• 新数据可能是即将爆发的热点数据

为了兼顾处理突发热点问题以及扫描流量问题，Caffeine 设计了 W-TinyLFU 结构

3.2. W-TinyLFU 算法内存结构与说明

W-TinyLFU 算法将缓存空间拆分为三个区域（分代思想，类似于JVM内存堆内存）：

3.2.1. WindowCache（窗口区）

WindowCache 缓存区域为了解决新数据因为直接与缓存中老数据做频次对比导致永远无法进入内存的问题：

• 算法类型：WindowCache区域采用 LRU 算法

• 运行原理：

  • 所有新写入的数据，首先进入 WindowCache 区域
  • 若数据只被访问一次，由于LRU算法机制，该数据会逐渐到达 WindowCache 区域末尾
  • 数据在即将被挤出时：
    • MainCache 区域存在空闲位置，该数据会被直接晋升至 MainCache 观察段头部
    • MainCache 区域已满，门卫机制会对比 MainCache 观察段此时的尾部数据和当前数据的访问频次，淘汰掉访问频次较低的数据

• 区域作用 ：给新数据一个“试用期”

3.2.2. MainCache (主存储区)

MainCache 缓存区域内部实际上是一个 Segmented LRU（分段LRU），该区域被进一步分为两段：

• Probation (观察段)：

  • 运行原理：

    观察段会保存以下缓存数据：

    • 从 WindowCache 被挤出的数据（MainCache存在冗余位置时）
    • 门卫机制优胜数据（MainCache已满时）

  • 区域作用： 存放待考察的数据

• Protected (保护段)：

  • 运行原理：

    • 从观察段晋升： 如果观察段的数据被再次访问，就会晋升到保护段
    • 降级回观察段： 保护段已满时再加入新的数据，会把末尾的数据降级回观察段

  • 区域作用： 存放真正的热点数据

3.3. 数据淘汰判定机制：门卫机制

门卫机制是 W-TinyLFU 的灵魂所在

当 WindowCache 区满了，需要把一个数据推到 MainCache 时，若 Main Cache 也满了，就需要门卫机制判定淘汰数据：

• 数据 A： 来自 WindowCache 区的新数据
• 数据 B： MainCache 观察段的淘汰候选数据

Caffeine 会查询访问频次表

• 如果 Freq(A) > Freq(B)：说明新数据更有价值，淘汰 B，接纳 A
• 如果 Freq(A) <= Freq(B)：说明旧数据更有价值，直接抛弃 A，保留 B

三、总结

1. W-TinyLFU 中的数据流转

1.1. 数据进入缓存

• 场景：调用了 cache.put("A", val)
• 动作：数据 "A" 无条件进入 WindowCache 的头部
• 意义：Caffeine 假设每一个新数据都可能是突发热点数据，先给新数据一个“窗口期”展现潜力
  • 如果 Window 区没满：A 安全暂存
  • 如果 Window 区满了：把 Window 区尾部的数据"B"挤出 WindowCache（可能进入观察段）

1.2. 数据关键流转：WindowCache -> MainCache

数据 "B" 被挤出 Window Cache 时，它必须寻找新去处（被淘汰或进入观察段）

• 场景：数据 "B" 被挤出 WindowCache 区
• 情况一：Main Cache 没满
  • 流转：B 直接进入观察段的头部
  • 结果：B 存活
• 情况二：Main Cache 已满 (触发 TinyLFU 裁决)
  • 判定： 数据 B 与观察段末尾的数据Old进行频次比较
    1. Freq(B) > Freq(Old)：
       • 结果：B 存活
       • 流转：Old 被淘汰，B 进入观察段头部
    2. Freq(B) <= Freq(Old)：
       • 结果：B 淘汰
       • 流转：B 被**直接淘汰，Old 继续留在观察段
• 意义： Caffeine 解决扫描流量的核心：低频的新数据（B）无法置换高频的老数据（Old）

1.3. 内部流转：Probation <-> Protected

缓存数据只要进入了 Main Cache，就只会在考察段或保护段间流转

1.3.1. 晋升: Probation -> Protected

• 场景：数据 "C" 目前在观察段，突然被cache.get("C")访问了一次
• 流转：
  • Caffeine 发现 "C" 在 Probation 区
  • 认为 "C" 有长期价值
  • 将 "C" 从 观察段移除，移动到保护段头部
• 意义：数据一旦进入保护段，就不易被淘汰

1.3.2. 降级: Protected -> Probation

• 场景：保护段也满了（因为不断有数据从观察段晋升进来）
• 流转：
  • 保护段将尾部数据“D”重新挤入观察段头部
• 意义：给过气数据一个缓冲机会，若 D 在观察段再次被访问，就会重新进入保护段，但如果一直未被访问，D 会慢慢滑向观察段尾部，最终面临被 WindowCache 区挤出的数据裁决的风险

2. W-TinyLFU 解决的问题

• 突发热点问题： 引入 Window 区域，数据不必比较访问频次就可以进入 WindowCache 区域
• 过气热点问题： 访问频次降级策略（详见2.3）
• 内存占用问题： 近似频率统计策略（详见2.2）
• 全表扫描问题： TinyLFU 过滤（本质上是 LFU 算法解决的问题）