W-TinyLFU算法

传统淘汰算法的问题

LRU（Least Recently Used）

最近最少使用算法，淘汰最久未被访问的数据。

优点：实现简单，对热点数据友好
缺点：对突发流量敏感，可能淘汰高频数据

LFU（Least Frequently Used）

最不经常使用算法，淘汰访问频率最低的数据。

优点：对高频数据保护好
缺点：新数据难以存活，历史数据难以淘汰

W-TinyLFU 算法原理

W-TinyLFU（Window Tiny Least Frequently Used）结合了 LRU 和 LFU 的优点，是 Caffeine 的核心淘汰算法。

整体架构

三个核心组件

1. Window Cache（窗口缓存）

• 占总容量的 1%
• 使用 LRU 策略
• 新数据首先进入这里
• 给新数据一个"试用期"

2. Main Cache（主缓存）

分为两个区域：

• Protected（保护区）：占 80%，存放高频访问数据
• Probation（观察区）：占 20%，存放待观察数据

3. TinyLFU（频率过滤器）

• 使用 Count-Min Sketch 统计访问频率
• 决定数据是否能进入 Main Cache
• 定期衰减，避免历史数据霸占缓存

数据流转过程

Count-Min Sketch

TinyLFU 使用 Count-Min Sketch 数据结构来统计访问频率，它是一种概率数据结构，用极小的空间估算元素频率。

原理

特点

• 空间效率高：使用位数组，内存占用极小
• 查询快速：O(1) 时间复杂度
• 可能高估：由于哈希冲突，频率可能被高估，但不会低估
• 定期衰减：通过右移操作衰减所有计数器

代码示意

public class CountMinSketch {
    private final long[][] table;
    private final int depth;
    private final int width;
    
    public void increment(long hash) {
        for (int i = 0; i < depth; i++) {
            int index = indexOf(hash, i);
            table[i][index]++;
        }
    }
    
    public long frequency(long hash) {
        long min = Long.MAX_VALUE;
        for (int i = 0; i < depth; i++) {
            int index = indexOf(hash, i);
            min = Math.min(min, table[i][index]);
        }
        return min;
    }
    
    // 衰减：所有计数器右移一位
    public void reset() {
        for (int i = 0; i < depth; i++) {
            for (int j = 0; j < width; j++) {
                table[i][j] >>>= 1;
            }
        }
    }
}

准入策略

当 Window Cache 中的数据要进入 Main Cache 时，TinyLFU 会进行准入判断：

// 伪代码
boolean admit(candidate, victim) {
    int candidateFreq = frequencySketch.frequency(candidate);
    int victimFreq = frequencySketch.frequency(victim);
    
    // 候选者频率必须大于受害者才能准入
    if (candidateFreq > victimFreq) {
        return true;
    }
    
    // 频率相同时，随机决定（避免饥饿）
    if (candidateFreq == victimFreq) {
        return random.nextBoolean();
    }
    
    return false;
}

自适应调整

Caffeine 会根据访问模式自动调整 Window Cache 和 Main Cache 的比例：

• 如果新数据命中率高，增大 Window Cache
• 如果旧数据命中率高，减小 Window Cache

与其他算法对比

命中率对比

访问模式	LRU	LFU	W-TinyLFU
热点数据	高	高	高
突发流量	低	高	高
扫描攻击	低	中	高
新数据友好	高	低	中

空间复杂度

算法	空间复杂度
LRU	O(n)
LFU	O(n)
W-TinyLFU	O(n) + O(1) 频率统计

实际效果

根据 Caffeine 官方基准测试，W-TinyLFU 在各种工作负载下都有优秀表现：

# 数据库访问模式
LRU:        71.2% 命中率
LFU:        75.8% 命中率
W-TinyLFU:  79.4% 命中率

# Web 访问模式
LRU:        64.3% 命中率
LFU:        68.1% 命中率
W-TinyLFU:  74.2% 命中率

# 搜索引擎模式
LRU:        58.7% 命中率
LFU:        62.4% 命中率
W-TinyLFU:  69.8% 命中率

小结

W-TinyLFU 算法通过 Window Cache 给新数据试用期，通过 TinyLFU 过滤低频数据，通过 SLRU 保护高频数据，在各种访问模式下都能保持较高的命中率。这是 Caffeine 性能优于 Guava Cache 的核心原因。

面试题预览

常见面试题

1. W-TinyLFU 算法的原理是什么？
2. Count-Min Sketch 是什么？有什么特点？
3. 为什么 W-TinyLFU 比 LRU 命中率更高？