缓存淘汰算法与 Caffeine 实战：FIFO、LRU、LFU 与 W-TinyLFU

缓存的容量是有限的，当缓存满了，就必须淘汰一些旧数据来腾出空间。**缓存淘汰算法（Cache Eviction Policy）**就是决定"该淘汰谁"的策略。选错淘汰算法，缓存命中率会大幅下降，甚至比没有缓存还糟。

本文先讲三种经典淘汰算法（FIFO、LRU、LFU），再介绍现代 Java 缓存库 Caffeine 所采用的 W-TinyLFU，以及它如何把它们的优点结合起来。

一、为什么要"淘汰"

无论 Redis 还是本地缓存（如 Caffeine），内存都是稀缺资源：

缓存永远装不下所有数据，容量满了就得移除部分条目；
淘汰的目标是保住"最可能再次被访问"的数据，让缓存命中率最高；
不同的淘汰算法，就是在"预测未来访问"这件事上给出不同的判断依据。

二、三种经典淘汰算法

1. FIFO（先进先出）

原理：最先进入缓存的数据最先被移除，就像排队，先进先走。

优点：实现最简单，只需一个队列记录进入顺序；
缺点：完全不考虑数据的使用频率和重要性，经常使用的数据也可能因为"来得早"而被换出，命中率较差。

2. LRU（最近最少使用）

原理：最近最少使用的数据项被优先移除。它假设"最近被访问过的数据，很可能很快还会被访问"。

优点：能较好地反映访问的时间局部性，命中率高，是最常用的淘汰算法；
缺点：需要维护"最近使用"的状态（通常用哈希表 + 双向链表，每次访问要移动节点），需要额外的空间和计算开销。

3. LFU（最不经常使用）

原理：最不经常使用的数据项被优先移除，即访问次数最少的先淘汰。

优点：依据使用频率决策，对"稳定高频"的数据非常友好；
缺点：需要为每个条目维护使用计数，实现复杂度高；且存在"历史问题"——过去很热、现在已冷的数据长期占着计数，新晋热点难以进入缓存。

三者对比一览

算法	淘汰依据	实现复杂度	优点	缺点
FIFO	进入时间	低	简单	不关心访问频率，命中率差
LRU	最近访问时间	中	贴合时间局部性，通用性好	需要维护访问顺序，有额外开销
LFU	访问频率	高	对稳定热点友好	计数开销大，历史频率拖累新数据

三、Caffeine 介绍

Caffeine 是一个基于 Java 8 的高性能本地缓存库，可以看作 Guava Cache 的"高配升级版"，也是 Spring Boot 默认集成的本地缓存实现（替代 Guava Cache）。

它最核心的亮点，是采用了 W-TinyLFU 淘汰算法。

1. W-TinyLFU 是什么

W-TinyLFU（Window Tiny LFU）是 LFU 的工程化改进，思路是：

用**频率草图（Frequency Sketch）**近似统计每个 key 的访问频率，内存开销极小；
引入一个窗口段（Window）：新数据先进窗口，即使频率低也有机会被访问；窗口溢出的数据再按频率进入主段，从而缓解 LFU"历史频率压制新数据"的问题；
频率会随时间衰减，避免"曾经很热、现在已冷"的数据长期霸占缓存。

简单说：W-TinyLFU ≈ LFU 的频率统计 + LRU 的时间局部性 + 对突发流量的容忍，在命中率上通常优于纯 LRU / 纯 LFU。

2. Caffeine 的核心特性

高性能：接近内存访问极限的读写性能；
自动淘汰：支持基于大小、写入时间、访问时间等多种淘汰策略；
异步加载：支持 LoadingCache、AsyncLoadingCache，缓存未命中时自动加载；
统计：recordStats() 可统计命中率等指标；
事件监听：条目被淘汰/更新时可触发回调。

3. 快速上手

<dependency>
    <groupId>com.github.ben-manes.caffeine</groupId>
    <artifactId>caffeine</artifactId>
    <version>3.1.8</version>
</dependency>

基本用法（按大小淘汰 + 写入后过期）：

Cache<String, User> cache = Caffeine.newBuilder()
        .maximumSize(10_000)              // 容量上限，触发淘汰
        .expireAfterWrite(Duration.ofMinutes(5)) // 写入 5 分钟后过期
        .recordStats()                     // 开启命中率统计
        .build();

// 读：先查缓存，未命中再查库并回填
User user = cache.get(userId, id -> userService.getById(id));

配合本地缓存 + Redis 的二级缓存场景（如前面笔记服务所述），Caffeine 正是承担"本地缓存"这一层的最佳选择。

四、总结

FIFO 简单但命中率差；LRU 是通用首选；LFU 对稳定热点更准但复杂且怕"历史频率"；
Caffeine 采用 W-TinyLFU，用频率草图 + 窗口段 + 频率衰减，在极低开销下逼近"最优淘汰"，是 Java 本地缓存的现代默认选择；
选淘汰算法本质是用缓存容量换取命中率，理解了三种经典算法，再看 W-TinyLFU 就水到渠成。