结合源码理解Caffine的缓存淘汰策略

W-TinyLFU 结合了 LRU（Least Recently Used）+ LFU（Least Frequently Used）+ TinyLFU 频率过滤器，核心是 Count-Min Sketch（CMS）+ 概率性淘汰。我们结合 Caffeine 源码 来分析其实现。

1. Caffine源码结构

BoundedLocalCache<K,V>: Caffine的缓存主类，实现了W-TinyLFU逻辑
Sketch<K>:实现了TinyLFU频率统计（基于Count-Min Sketch）
WindowTinyLfu<K, V>：管理 Window Cache + Main Cache，负责数据插入和淘汰。
Node<K, V>：缓存中的数据节点，每个 Node 记录了访问时间、频率等信息。

2. Count-Min Sketch介绍

Caffeine 使用 Count-Min Sketch（CMS）来统计访问频率，代码核心在 Sketch.java，但可能直接看代码有点难以理解，那么让我们先介绍一下Count-Min Sketch的核心逻辑：

Count-Min Sketch是一种概率性数据结构，用于高效统计数据流中元素的频率，并且占用极小的内存。它特别适用于大规模数据流（如日志分析、网络流量监控、缓存策略等）。其核心思想是采用多个哈希函数和一个二维计数矩阵，用来记录数据的出现频率。其步骤如下：

使用多个哈希函数将数据映射到多个位置。
每次更新数据，在所有对应的哈希位置上加 1。
查询某个数据的频率时，取所有哈希映射位置的最小值。

由于使用了哈希函数，CMS 可能会发生哈希碰撞，但由于取的是多个哈希值中的最小值，它能够有效减少误差，这就是采用多个哈希函数的原因。

CMS会维护一个w×d的二维计数矩阵 count[d][w]：

w（列数）：每个哈希函数对应的存储空间，用于控制误差范围
d（行数）：哈希函数的数量，用于控制误差精度
hash1(x), hash2(x), ..., hashd(x)：一组独立的哈希函数，每个函数将 x 映射到 [0, w-1] 之间的某个索引。

当插入数据时，对于每个数据x，首先计算d个哈希值hash1(x), hash2(x), ..., hashd(x)。接下来，对于每个哈希值对应的count[i][hashi(x)] 位置上 +1。

当查询数据时，对于每个数据x，也首先计算 d 个哈希值 hash1(x), hash2(x), ..., hashd(x)。在 count[i][hashi(x)] 位置取最小值作为估计频率：

f(x)=min(count[0][hash1(x)],count[1][hash2(x)],...,count[d][hashd(x)])

Count-Min Sketch 不会低估数据的真实频率，但可能会高估，因为哈希冲突会导致计数增加。可以看出，w越大，哈希冲突的概率越低。相比于哈希表，CMS只需要O(wd)的存储空间，适合大规模数据。其不会因为数据量增加而膨胀，且其时间复杂度为O(d)，比维护全量计数表更快。

Count-Min Sketch 在Caffine（W-TinyLFU）中进行使用，通过其记录数据的访问频率。当数据被访问时，CMS记录数据频率。而当缓存满时，淘汰频率最低的数据，而不仅仅是根据LRU进行淘汰，这里需要解释一下Caffine的淘汰策略,Caffine主要通过Window Cache + Main Cache 结合CMS进行淘汰，当缓存满时，Caffine采用以下流程：

首先尝试淘汰 Window Cache（短期数据），如果 Window Cache 还有空间，直接插入新数据。否则淘汰最老的数据（FIFO）
如果新数据进入了 Main Cache，则进行概率性淘汰。对于新数据newKey获取访问频率newFreq = sketch.frequency(newKey)，并从Main Cache中随机选出一个Main Cache的victimKey，获取 victimFreq = sketch.frequency(victimKey)
如果 newFreq > victimFreq，淘汰 victimKey，新数据替换进入 Main Cache。否则，丢弃新数据，victimKey 继续留在缓存中。

可以看出，对于处于Main Cache的长期缓存数据，其是基于概率进行淘汰的，也就是即使存在频率更低的数据，也并不一定就会将其替换，但从概率上讲，频率高的，长期的缓存数据会逐渐将出现频率较低的数据替换掉。

3. TinyLFU频率统计：Sketch<K>

下面先对CMS的核心代码进行解读：

final class Sketch<K> {
  final int[][] table; // Count-Min Sketch 的二维数组
  final int width, depth;
  final Random random;
  
  Sketch(int width, int depth) {
    this.width = width;
    this.depth = depth;
    this.random = new Random();
    this.table = new int[depth][width];
  }
  
  void increment(K key) {
    int hash = key.hashCode();
    for (int i = 0; i < depth; i++) {
      int index = (hash + i) & (width - 1);
      table[i][index]++; // 统计 key 访问频率
    }
  }
  
  int frequency(K key) {
    int hash = key.hashCode();
    int min = Integer.MAX_VALUE;
    for (int i = 0; i < depth; i++) {
      int index = (hash + i) & (width - 1);
      min = Math.min(min, table[i][index]); // 取所有哈希函数计算的最小值
    }
    return min;
  }
}

Sketch类创建了计数矩阵count[w][d]，提供了CMS计数的方法，以及获取某key频率的方法。

table[i][index]++：更新 Count-Min Sketch，记录 key 的访问频率。
frequency(K key)：查询 key 的最小访问频率（防止哈希冲突影响）。

淘汰策略由类WindowTinyLfu<K,V>实现：

final class WindowTinyLfu<K, V> {
  final Sketch<K> sketch; // TinyLFU 访问频率统计
  final BoundedLocalCache<K, V> cache;
  
  WindowTinyLfu(BoundedLocalCache<K, V> cache) {
    this.cache = cache;
    this.sketch = new Sketch<>(width, depth);
  }
  
  void record(K key) {
    sketch.increment(key); // 记录 key 的访问频率
  }
  
  boolean shouldReplace(K newKey, K victimKey) {
    int newFreq = sketch.frequency(newKey);
    int victimFreq = sketch.frequency(victimKey);
    return newFreq > victimFreq; // 采用概率比较，决定是否替换
  }
}

record(K key)：每次访问 key 时，增加 Count-Min Sketch 计数。
shouldReplace(K newKey, K victimKey)：当缓存满了，新数据 和 随机选中的 victim 进行频率比较：

newFreq > victimFreq → 淘汰 victim，让 newKey 进入缓存。
否则，newKey 直接丢弃，victim 继续留在缓存中

淘汰流程由BoundedLocalCache.evictEntry()方法控制：

void evictEntry() {
  Node<K, V> victim = selectVictim(); //随机选取一个victimKey
  if (victim != null && windowTinyLfu.shouldReplace(newKey, victim.key)) {
    cache.removeNode(victim); //删除旧key
    cache.put(newKey, newValue); //添加新key
  }
}