LRU 与 LFU 缓存淘汰算法

#数据结构 · #LRU · #LFU · #缓存 · #淘汰策略 · #哈希链表

缓存空间有限，当缓存满时必须淘汰部分数据。LRU（最近最少使用）和 LFU（最不经常使用）是两种最经典的淘汰策略，各有适用场景。

---

缓存淘汰策略对比

策略	淘汰依据	实现复杂度	适用场景
LRU	最近最少使用	中	访问具有时间局部性
LFU	使用频率最低	高	访问频率分布不均
FIFO	最先进来	低	简单场景
TTL	超过过期时间	低	有明确时效性的数据
W-TinyLFU	综合 + 频率 + 新近度	高	Caffeine 默认策略
ARC	自适应 LRU/LFU	高	兼顾两者优点

---

一、LRU（Least Recently Used）

核心思想

每次访问把数据移到"最新"位置，淘汰时删除"最旧"的数据。

访问序列: A → B → C → A → D (容量=3)

[A]           → 插入 A
[B, A]        → 插入 B
[C, B, A]     → 插入 C
[A, C, B]     → 访问 A，移到最前
[D, A, C]     → 插入 D，淘汰 B（最旧）

数据结构：哈希表 + 双向链表

HashMap: key → Node 指针     双向链表: Head ↔ Newest ↔ ... ↔ Oldest ↔ Tail
  key1 → Node1                                                 ↓
  key2 → Node2                                         淘汰时删除 Tail.prev
  key3 → Node3

为什么用双向链表？

• O(1) 删除任意节点（需要前驱指针）
• O(1) 移到头部

实现

type LRUCache struct {
    capacity int
    cache    map[int]*Node
    head     *Node  // 哨兵：最近使用
    tail     *Node  // 哨兵：最久未使用
}

type Node struct {
    key, value int
    prev, next *Node
}

func NewLRUCache(capacity int) *LRUCache {
    lru := &LRUCache{
        capacity: capacity,
        cache:    make(map[int]*Node),
        head:     &Node{},
        tail:     &Node{},
    }
    lru.head.next = lru.tail
    lru.tail.prev = lru.head
    return lru
}

func (c *LRUCache) Get(key int) int {
    if node, ok := c.cache[key]; ok {
        c.moveToHead(node)
        return node.value
    }
    return -1
}

func (c *LRUCache) Put(key, value int) {
    if node, ok := c.cache[key]; ok {
        node.value = value
        c.moveToHead(node)
    } else {
        node := &Node{key: key, value: value}
        c.cache[key] = node
        c.addToHead(node)
        if len(c.cache) > c.capacity {
            removed := c.removeTail()
            delete(c.cache, removed.key)
        }
    }
}

// 辅助方法
func (c *LRUCache) addToHead(node *Node) {
    node.prev = c.head
    node.next = c.head.next
    c.head.next.prev = node
    c.head.next = node
}

func (c *LRUCache) removeNode(node *Node) {
    node.prev.next = node.next
    node.next.prev = node.prev
}

func (c *LRUCache) moveToHead(node *Node) {
    c.removeNode(node)
    c.addToHead(node)
}

func (c *LRUCache) removeTail() *Node {
    node := c.tail.prev
    c.removeNode(node)
    return node
}

Redis 中的 LRU

Redis 使用近似 LRU，不维护完整链表，而是：

1. 随机采样 N 个 key（默认 5 个）
2. 淘汰其中空闲时间最长的
3. maxmemory-policy allkeys-lru

Redis 3.0+ 使用近似 LRU（Eviction Pool）：
- 维护一个候选池（最多 16 个 key）
- 每次淘汰时，从池中选最久未使用的
- 空闲时间用 24 位时钟近似

---

二、LFU（Least Frequently Used）

核心思想

淘汰使用频率最低的数据；频率相同时，淘汰最久未使用的。

访问序列: A A B B A C C A D (容量=3)

Freq: A=4, B=2, C=2, D=1

[A freq=4]
[B freq=2]
[C freq=2]
[D freq=1] ← 淘汰

频率相同时(B和C)，淘汰更旧的(B)

数据结构：哈希表 + 频率桶

HashMap: key → Node
FreqMap: freq → DoublyLinkedList (该频率的所有 key)

freq=1:  [D] ↔ [C]
freq=2:  [B]
freq=3:  [A]
   ↑
minFreq （最小频率，快速定位淘汰目标）

实现

type LFUCache struct {
    capacity int
    minFreq  int                    // 当前最小频率
    keyMap   map[int]*LFUNode       // key → node
    freqMap  map[int]*FreqBucket    // freq → 双向链表
}

type LFUNode struct {
    key, value int
    freq       int
    prev, next *LFUNode
}

type FreqBucket struct {
    head, tail *LFUNode  // 哨兵节点
    size       int
}

func NewLFUCache(capacity int) *LFUCache {
    return &LFUCache{
        capacity: capacity,
        minFreq:  0,
        keyMap:   make(map[int]*LFUNode),
        freqMap:  make(map[int]*FreqBucket),
    }
}

func (c *LFUCache) Get(key int) int {
    if node, ok := c.keyMap[key]; ok {
        c.increaseFreq(node)
        return node.value
    }
    return -1
}

func (c *LFUCache) Put(key, value int) {
    if c.capacity <= 0 {
        return
    }
    if node, ok := c.keyMap[key]; ok {
        node.value = value
        c.increaseFreq(node)
    } else {
        if len(c.keyMap) >= c.capacity {
            c.removeLFU()
        }
        node := &LFUNode{key: key, value: value, freq: 1}
        c.keyMap[key] = node
        c.addToFreqBucket(node, 1)
        c.minFreq = 1
    }
}

func (c *LFUCache) increaseFreq(node *LFUNode) {
    oldFreq := node.freq
    // 从旧频率桶移除
    c.removeFromFreqBucket(node)
    // 如果旧频率桶空了且是最小频率，更新 minFreq
    if oldFreq == c.minFreq && c.freqMap[oldFreq].size == 0 {
        c.minFreq++
    }
    // 加入新频率桶
    node.freq++
    c.addToFreqBucket(node, node.freq)
}

func (c *LFUCache) removeLFU() {
    bucket := c.freqMap[c.minFreq]
    // 删除最小频率桶的最后一个（最久未使用）
    node := bucket.tail.prev
    c.removeFromFreqBucket(node)
    delete(c.keyMap, node.key)
}

func (c *LFUCache) addToFreqBucket(node *LFUNode, freq int) {
    if c.freqMap[freq] == nil {
        c.freqMap[freq] = &FreqBucket{head: &LFUNode{}, tail: &LFUNode{}}
        c.freqMap[freq].head.next = c.freqMap[freq].tail
        c.freqMap[freq].tail.prev = c.freqMap[freq].head
    }
    bucket := c.freqMap[freq]
    // 插入到头部（最近使用）
    node.next = bucket.head.next
    node.prev = bucket.head
    bucket.head.next.prev = node
    bucket.head.next = node
    bucket.size++
}

func (c *LFUCache) removeFromFreqBucket(node *LFUNode) {
    node.prev.next = node.next
    node.next.prev = node.prev
    c.freqMap[node.freq].size--
    node.prev, node.next = nil, nil
}

Redis 中的 LFU

Redis 4.0+ 支持 LFU，使用 Morris Counter 近似计数：

Redis LFU 的概率性计数：
- 每个 key 存储一个 8bit 对数计数器（0-255）
- 增加频率：counter += 1（有概率递减）
- 衰减：counter *= lfu_decay_time 因子
- 优点：极少的内存开销（8bit vs 标准 32bit 计数器）

maxmemory-policy allkeys-lfu

---

LRU vs LFU 对比

维度	LRU	LFU
淘汰对象	最久未使用的	频率最低的
适合场景	时间局部性强	频率差异大
新数据保护	好（新数据在头部）	差（新数据 freq=1 易被淘汰）
历史数据	一次访问就复活	频率低易被淘汰
实现复杂度	中	高
内存开销	O(n) 双向链表	O(n) 多频率桶
频率爆炸问题	无	需要衰减机制

---

现代缓存：W-TinyLFU（Caffeine）

Caffeine（Java 高性能缓存库）使用 Window TinyLFU 策略：

        ┌──────────┐    晋升     ┌──────────┐    晋升     ┌──────────┐
写入 →  │ Window   │ ───────→  │  Probation│ ───────→  │ Protected│
        │ LRU (1%) │          │  LFU (20%)│          │ LRU (80%) │
        └──────────┘           └──────────┘           └──────────┘
                                    │                      │
                                    └──── 竞争淘汰 ←───────┘

TinyLFU 维护一个 Count-Min Sketch 近似计数
新数据先在 Window LRU 中热身，再与主空间的 LFU 竞争

特点：综合 LRU（对新数据友好）和 LFU（对高频数据公平）的优点。

---

工程实践：缓存淘汰策略为什么经常决定系统上限

0. 一眼看懂：访问模式决定淘汰策略

flowchart LR
    A["时间局部性强"] --> B["LRU"]
    C["长期热点稳定"] --> D["LFU"]
    E["既有新流量又有扫描流量"] --> F["W-TinyLFU / 混合策略"]

流量形态	更适合	最怕什么
热点随时间快速移动	LRU	顺序扫描污染
热点长期稳定	LFU	历史频率包袱
新热点、旧热点、扫描混在一起	混合策略	设计和实现复杂度高
数据天然有失效时间	TTL + 淘汰联合	只配 TTL 不管容量抖动

1. 淘汰策略影响的不是“优雅程度”，而是命中率与回源压力

缓存设计里最容易低估的一点是：淘汰策略不只是一个数据结构题，它直接决定：

• 命中率
• 回源流量
• 下游数据库/Redis/对象存储压力
• 尾延迟和抖动

flowchart LR
    A["淘汰策略不匹配访问模式"] --> B["命中率下降"]
    B --> C["更多请求回源"]
    C --> D["下游负载升高"]
    D --> E["RT 抖动 / 雪崩风险增加"]

2. LRU 最大的问题不是老，而是容易被“顺序扫描”污染

LRU 对时间局部性很好，但对这种访问模式很脆弱：

热点数据 H 一直稳定存在
突然来一波大范围顺序扫描 S1, S2, S3 ... Sn

结果通常是：

• 扫描数据把链表前部全部刷新
• 真正热点数据被挤出缓存
• 扫描结束后，热点又要重新回源热起来

这就是经典的 cache pollution（缓存污染）。

所以只要业务存在：

• 大分页扫描
• 批量导出
• 冷数据巡检
• 宽表全量遍历

单纯 LRU 往往不够稳。

3. LFU 最大的问题不是复杂，而是“历史包袱太重”

LFU 能保护长期热点，但如果没有衰减机制，就容易出现：

• 过去热点长期霸占缓存
• 新热点很难升上来
• 流量模式变化后，缓存仍然服务旧世界

这就是为什么真实系统里的 LFU 往往都会加：

• 计数衰减
• 近似频率统计
• 窗口区预热
• 新旧数据竞争机制

4. 为什么现代缓存更偏向混合策略

像 Caffeine 的 W-TinyLFU 之所以流行，本质上是因为真实流量同时存在：

• 新近性
• 频率性
• 突发性
• 扫描性

单独用 LRU 或 LFU 都容易在某一类流量下失真，所以现代策略更常见的是：

• 一小块窗口区吸收新流量
• 主缓存按频率决策
• 近似计数而不是精确计数
• 用极小内存成本换更稳的命中率

5. 一个典型故障链

flowchart LR
    A["访问模式变化 / 大量扫描请求"] --> B["缓存污染或热点挤出"]
    B --> C["命中率下降"]
    C --> D["数据库/下游回源流量飙升"]
    D --> E["连接池变紧 / RT 上升 / 错误率增加"]

很多系统里，用户先看到的是：

• 数据库慢了
• 接口超时了
• Redis 打满了

但真正的根因可能是：缓存淘汰策略和访问模式不匹配。

6. 怎么选策略

场景	更适合
明显时间局部性、实现要简单	LRU
热点长期稳定，频率差异大	LFU
存在扫描流量、热点切换、复杂业务流量	W-TinyLFU / 混合策略
数据有明确时效性	TTL + 其他淘汰策略联合

注意现实里经常不是“二选一”，而是：

• TTL 控过期
• 淘汰策略控容量
• singleflight / preload 控击穿
• 限流和降级控雪崩

7. 评估缓存策略，不能只看平均命中率

真正应该看的还包括：

• 热点 key 命中率
• 命中率在流量切换时的恢复速度
• 回源峰值
• 淘汰抖动
• 扫描流量出现时的稳定性

也就是说，同样 95% 命中率，两个策略对系统的体感可能完全不同：

• 一个很平稳
• 一个会周期性把下游打爆

8. 排障思路

现象	优先怀疑	看什么
命中率突然下降	缓存污染 / 热点切换	cache metrics、访问分布
下游 DB 突然压力大	淘汰策略失配	miss 峰值、回源量
新热点迟迟起不来	LFU 历史频率压制	频率衰减配置
大批量任务时服务波动	LRU 被扫描打穿	批任务窗口与缓存命中关联

9. 一个实战原则

先看访问模式，再选淘汰策略；
不要先决定 LRU 还是 LFU，再去解释业务为什么适合它。

---

10. 工业实现深度对比：Redis vs Caffeine

10.1 Redis 为什么不用严格 LRU？

Redis 使用近似 LRU / LFU（maxmemory-policy），原因是：

• 严格 LRU 需要一个全局链表 + 每次访问更新节点位置 → O(1) 但锁开销大
• Redis 是单线程执行命令，全局链表维护成本会拖慢所有操作
• 近似算法的采样开销可控：每次 maxmemory 检查时随机采样 N 个 key（默认 5），淘汰其中最应该被淘汰的

Redis 近似 LRU 的工作原理:
  1. 每个 key 对象存储一个 24 位 lru 时钟（lruclock）
  2. 每次访问 key → 更新 lru 值 = 当前 lruclock
  3. 内存不够时: 随机采样 N 个 key (maxmemory-samples 5)
  4. 淘汰其中 lru 值最小的（最久未被访问）
  5. 采样数越大 → 越接近严格 LRU (maxmemory-samples 10)

Redis 近似 LFU (allkeys-lfu / volatile-lfu):
  - 用 lru 字段的高 16 位存上次访问时间，低 8 位存访问频率
  - 访问频率定时衰减 (lfu_decay_time)，解决"老死数据霸占"问题
  - 新增 key 给一个初始频率 (lfu_log_factor 控制增长曲线)

策略	Redis 实现方式	内存开销	精度
allkeys-lru	近似采样 LRU (24位 lru 时钟)	每个 key 24bits	采样 N=10 时接近严格 LRU
allkeys-lfu	近似采样 LFU (高16位时间 + 低8位频率)	同上	莫里斯计数器近似
volatile-lru	同 allkeys-lru，仅过期 key	同上	同上
volatile-ttl	采样后淘汰 TTL 最近的	0	基于已有的 expire 时间

10.2 Caffeine W-TinyLFU — 命中率最高的本地缓存

Caffeine（Java 顶级缓存库）使用 W-TinyLFU 算法（Window TinyLFU），被广泛认为是命中率最高的缓存淘汰算法：

flowchart TD
    A["新数据"] --> W["Window Cache<br/>1% 容量<br/>(LRU 策略)"]
    W --> P{"晋升竞争"}

    M["Main Cache<br/>99% 容量<br/>(SLRU: 2段)"]
    M --> S["Probation 段<br/>(候选淘汰区)"]
    S --> G["Protected 段<br/>(热点保护区)"]
    G -->|"降级"| S

    P -->|"频率 > S 队尾"| G
    P -->|"频率 ≤ S 队尾"| S

    F["TinyLFU 频率统计器<br/>Count-Min Sketch<br/>4-bit per entry"] -.-> P

    style W fill:#2196F3,color:#fff
    style G fill:#4CAF50,color:#fff
    style S fill:#FF9800,color:#fff
    style F fill:#9C27B0,color:#fff

W-TinyLFU 的三个关键设计：

设计	解决问题	效果
Window Cache	新数据需要预热，LFU 频率低时进不去	给新数据 1% 的窗口区，在 LRU 竞争中证明自己
Count-Min Sketch	精确频率计数内存太大	4-bit per entry 近似计数，空间效率高
SLRU 两段	老数据长期霸占、新数据无法晋升	Probation(候选) → Protected(保护)，有进有出
周期性重置	Sketch 计数器溢出 / 访问模式变化	定期衰减计数，让"过去的热点"能退场

10.3 Caffeine vs Guava LRU vs Redis LRU 命中率对比

场景: 模拟 YouTube 视频播放量分布（Zipfian 分布），缓存容量 = 总数据量 10%

命中率:
  Caffeine W-TinyLFU:  ~52%
  Redis 近似 LFU:      ~48%
  Guava ConcurrentLRU: ~42%
  严格 LRU:            ~40%

差距来源:
  - 严格 LRU 被"顺序扫描"污染最严重 (10% 命中率差距)
  - LFU 保护热点更稳定，但需要衰减防止老化
  - W-TinyLFU 因 Window 段的存在，对新热点的反应更快

10.4 淘汰算法在本地缓存/Redis/CDN/OS 中的纵向演化

层级	系统	淘汰算法	为什么选它
L1: CPU Cache	硬件	随机 / 伪 LRU	硬件实现成本低，ns 级决策
L2: OS 页缓存	Linux	双链表 LRU (Active/Inactive)	区分"被访问过的页"和"只读过一次的页"
L3: 本地缓存	Caffeine	W-TinyLFU	命中率最高，JVM 内存受限
L4: 分布式缓存	Redis	近似 LRU/LFU	单线程，采样开销可控
L5: CDN	Nginx proxy_cache / Varnish	LRU / 2Q	数据量大，淘汰粒度是文件级
L6: 数据库	MySQL Buffer Pool	LRU (midpoint insertion)	防止全表扫描污染 buffer pool

核心观察：越靠近 CPU，淘汰算法越简化（硬件成本约束）；越靠上层应用，算法越复杂（命中率优先）。

参考

• LeetCode 146. LRU Cache
• LeetCode 460. LFU Cache
• Redis LRU 实现说明
• Caffeine W-TinyLFU 论文