第2章：缓存淘汰策略设计 —— LRU、LFU、FIFO、TTL、随机淘汰的适用场景与实现代价对比

缓存淘汰策略是本地缓存架构的“守门员”——当内存达到上限时，策略决定哪些数据被驱逐以腾出空间。选错策略将导致命中率骤降、延迟飙升甚至雪崩。本章从架构边界、分层职责、数据流、实现代价、风险点五个维度，对比五种常见淘汰策略，并给出可落地的选型决策树与验收标准。

2.1 架构边界与分层职责

淘汰策略位于缓存中间件的内部决策层，不属于应用业务层。在典型的分层架构中：

• 接入层：接收请求，决定走缓存还是数据库。
• 缓存操作层：执行 get/set/delete，调用淘汰策略。
• 淘汰策略引擎：根据算法选择驱逐对象，更新索引数据结构。
• 存储层：内存数据块（如 Go 的 map、Java 的 ConcurrentHashMap）。

淘汰策略对上层透明，但其时间成本、内存开销直接影响缓存吞吐与延迟。合理的设计应隔离策略实现，允许运行时切换（如 Caffeine 中通过 Builder 指定）。

2.2 五种策略的适用场景与实现代价对比

策略	核心思想	适用场景	实现代价	内存开销	时间复杂度
LRU	最近最少使用	一般业务缓存、访问模式有明显的“时间局部性”	中：需维护双向链表 + 哈希表	每个 entry 多两个指针	O(1)
LFU	最不经常使用	热点数据集中、访问频率差异大的场景（如 CDN、推荐系统）	高：需维护最小堆或频率链表 + 哈希表 + 频率计数器	每个 entry 频率计数 & 指针	O(log n) 或 O(1)（改造后）
FIFO	先进先出	数据生命周期固定、无需关注访问频率的场景（如日志缓冲区）	低：简单队列 + 哈希表	队列指针，无额外频次计数	O(1)
TTL	过期时间淘汰	时效性数据（如 session、验证码）、主动清除陈旧数据	低：仅需定时扫描或惰性删除，不依赖访问模式	每个 entry 存过期时间戳	O(n) 扫描（定时）/ O(1) 惰性
随机淘汰	随机选择淘汰对象	低优先级缓存、对命中率不敏感、内存压力极小场景（如爬虫去重）	极低：仅需随机数 + 哈希表	几乎无额外	O(1)

2.3 数据流与控制流：淘汰触发时机

无论哪种策略，淘汰触发入口都是 put 或 get 后的容量检查。典型数据流如下：

1. 应用调用 cache.get(key)，命中则更新策略元数据（LRU 移到链表头，LFU 增加频率等）；未命中尝试访问数据库并回填。
2. 回填后检查 size > maxSize，若超限则调用淘汰策略引擎的 evict() 方法。
3. 策略引擎根据当前数据结构选出待驱逐 entry，删除并释放内存。
4. TTL 策略另由后台线程定期扫描过期 key，或者通过惰性删除（get 时检查）。

控制流中需要关注锁粒度：并发场景下，淘汰操作若持有长锁将严重降低吞吐。工业实现（如 Guava Cache、Caffeine）采用分段锁或无锁链表（如 ConcurrentLinkedHashMap）减少竞争。

2.4 选型决策树

以下 SVG 决策树帮助架构师根据缓存特性快速选择淘汰策略：

2.5 风险点与常见误区

• LRU 被突发请求污染：一次批量查询可能将大量冷数据推入链表头部，导致热点被驱逐。解决方案：分段 LRU（如 Caffeine 的 W-TinyLFU）或结合 TTL。
• LFU 计数器溢出与内存膨胀：纯 LFU 需大量频率计数器，且长期不用的对象可能永远不被淘汰（需引入衰减窗口）。工业方案使用最小堆 + 定频评分。
• FIFO 命中率低：适合“先进一定先出”的业务（如日志队列），但不适合通用缓存。
• TTL 扫描开销：大量 key 精确定时扫描会引发 CPU 尖刺；更优方案是惰性删除 + 周期性随机采样（类似 Redis 的过期策略）。
• 随机淘汰不可预测：极低开销但命中率极差，仅用于测试或极低负载场景。

2.6 落地步骤与配置示例

选择策略后，在主流缓存中间件中配置通常如下：

# Caffeine 配置示例 (Java)
Caffeine.newBuilder()
    .maximumSize(10_000)
    .expireAfterWrite(10, TimeUnit.MINUTES)  // 等效 TTL
    .evictionListener((key, value, cause) -> log.warn("Evicted {} cause {}", key, cause))
    .build();

// 指定淘汰策略：
Caffeine.newBuilder()
    .maximumSize(10_000)
    .evictionPolicy(new LruPolicy())   // 默认 LRU
    .build();

// 使用 Window TinyLFU（Caffeine 默认，合并 LRU+LFU 优点）

# Redis 配置示例 (Redis 6+)
maxmemory 100mb
maxmemory-policy allkeys-lru    # 可选：allkeys-lfu / volatile-ttl / volatile-random

2.7 验收标准

在集成测试或生产预部署前，使用以下指标验证缓存淘汰策略是否达标：

指标	合格阈值	工具/方法
缓存命中率	≥ 90%（读取密集型场景）	JMX / Micrometer / Prometheus
P99 GET 延迟	≤ 5ms（内存访问）	请求埋点，排除网络
淘汰频率	每秒淘汰 < 5% 最大容量	淘汰日志 / eviction count 统计
内存波动	占用量稳定在 maxSize ±5%	内存监控（top / heap dump）