缓存算法 #01：LRU（最近最少使用）

LRU（Least Recently Used）是最经典的缓存淘汰算法：当缓存满时，驱逐最长时间未被访问的条目。本文从数据结构设计出发，推导出 O(1) 的实现，并深入分析 LRU 在工程中的边界情况与局限性。

相关文章：LFU（最少使用频率） · ARC（自适应替换缓存） · W-TinyLFU 与 Caffeine · MySQL Buffer Pool 与 midpoint LRU

目录

问题定义

设计一个固定容量 capacity 的缓存，支持：

get(key)        → 返回 value（若存在），否则返回 -1
put(key, value) → 插入或更新 key-value；
                  若容量已满，先驱逐最近最少使用的条目

两个核心约束：

1. get 和 put 都必须是 O(1)
2. 每次 get 或 put 访问一个 key，该 key 变为"最近使用"

数据结构设计

为什么单用数组或链表不够

方案1：数组（按访问时间排序）
  get(key)：遍历找 key，O(N)  ← 不满足 O(1)

方案2：HashMap
  get(key)：O(1) ✅
  但无法高效找到"最久未用"的 key（需要额外排序）

方案3：HashMap + 双向链表 ← 正确答案
  HashMap：key → 链表节点（O(1) 定位）
  双向链表：维护访问顺序（最近用的在头部，最久未用的在尾部）
  节点删除：O(1)（有前驱和后继指针，无需遍历）

数据结构

// 双向链表节点
Node {
    key:  int
    val:  int
    prev: Node   // 指向前一个节点
    next: Node   // 指向后一个节点
}

// LRU 缓存
LRUCache {
    capacity: int
    size:     int                  // 当前存储的条目数
    map:      HashMap<int, Node>   // key → 节点指针（O(1) 查找）
    head:     Node                 // 哨兵头节点（最近使用端）
    tail:     Node                 // 哨兵尾节点（最久未用端）
}

// 初始化：head <-> tail（空链表，head 和 tail 互指）
init(capacity):
    self.capacity = capacity
    self.size     = 0
    self.map      = {}
    head.next = tail
    tail.prev = head

哨兵节点的作用：避免在头尾操作时判断空链表，简化代码。

完整伪代码

辅助操作

// 将节点插入到链表头部（最近使用端）
addToHead(node):
    node.prev = head
    node.next = head.next
    head.next.prev = node   // 原第一个节点的 prev 指向 node
    head.next = node        // head 的 next 指向 node

// 从链表中删除节点（O(1)，利用双向指针）
removeNode(node):
    node.prev.next = node.next
    node.next.prev = node.prev
    // node.prev 和 node.next 保留，但已从链表断开

// 移动节点到头部（= 先删除，再插入头部）
moveToHead(node):
    removeNode(node)
    addToHead(node)

// 删除尾部节点（最久未用的节点）并返回
removeTail():
    node = tail.prev        // 真正的最后一个节点（tail 是哨兵）
    removeNode(node)
    return node

get(key)

get(key):
    if key not in map:
        return -1

    node = map[key]
    moveToHead(node)        // 标记为"最近使用"
    return node.val

put(key, value)

put(key, value):
    if key in map:
        // key 已存在：更新值，移到头部
        node = map[key]
        node.val = value
        moveToHead(node)
    else:
        // key 不存在：新建节点
        node = Node(key, value)
        map[key] = node
        addToHead(node)
        size += 1

        if size > capacity:
            // 驱逐最久未用的节点（链表尾部）
            evicted = removeTail()
            del map[evicted.key]
            size -= 1

执行追踪

capacity = 3，依次执行：put(1,A) put(2,B) put(3,C) get(1) put(4,D) get(2)

初始：head ↔ tail   map={}

put(1,A)：
  map = {1:N1}
  链表：head ↔ [1,A] ↔ tail    （N1 在头部）

put(2,B)：
  map = {1:N1, 2:N2}
  链表：head ↔ [2,B] ↔ [1,A] ↔ tail

put(3,C)：
  map = {1:N1, 2:N2, 3:N3}
  链表：head ↔ [3,C] ↔ [2,B] ↔ [1,A] ↔ tail
  （缓存已满）

get(1)：
  找到 N1，moveToHead(N1)
  链表：head ↔ [1,A] ↔ [3,C] ↔ [2,B] ↔ tail
  返回 A ✅

put(4,D)：
  新建 N4，addToHead(N4)，size=4 > capacity=3
  → removeTail() 驱逐 [2,B]（最久未用）
  del map[2]
  链表：head ↔ [4,D] ↔ [1,A] ↔ [3,C] ↔ tail
  map = {1:N1, 3:N3, 4:N4}

get(2)：
  key=2 不在 map → 返回 -1  （已被驱逐）

复杂度分析

异常场景

并发访问（多线程）

问题：get 和 put 都修改链表，并发时产生竞争

Java 的解法：
  方案1：synchronized 整个方法（简单，高并发时锁竞争严重）
  方案2：分段锁（将缓存按 key hash 分桶，各桶独立加锁）
  方案3：Caffeine 使用 CAS + 写缓冲区（无锁或细粒度锁），性能最优

Go 的解法：
  用 sync.RWMutex，get 加读锁，put 加写锁
  注意：get 虽然是"读"，但会修改链表（moveToHead），必须加写锁！

缓存穿透（key 永远不存在）

问题：get("不存在的key") 每次都穿透到数据库，缓存没有防护作用

解法：
  缓存空值：put(key, NULL_SENTINEL)，TTL 设短（如 30s）
  Bloom Filter 前置拦截：先查 Bloom Filter，不存在则直接返回

容量为 1 的特殊情况

capacity = 1，put(1,A) put(2,B) get(1)：

put(1,A)：链表 [1,A]，map={1}
put(2,B)：链表 [2,B]，驱逐 [1,A]，map={2}
get(1)：  key=1 不在 map → 返回 -1

容量为 1 时，每次 put 不同 key 都会驱逐前一个，缓存命中率为 0
说明 LRU 在容量极小时退化严重

put 相同 key（更新操作）

put(1,A)，put(1,B)（相同 key，不同 value）：

第一次：创建节点 [1,A]，size=1
第二次：key 已在 map，走更新分支
         node.val = B，moveToHead(node)
         size 不变（没有新增节点）

注意：更新已有 key 时不能走"新建 + 驱逐"分支，否则 size 计数错误

LRU 的局限

问题 1：缓存污染（Cache Pollution）

场景：热点数据是 key=1~10，缓存容量=10
  → 长期稳定命中 key=1~10

突然执行一次全表扫描，顺序访问 key=1~1000：
  → key=1~1000 全部被 put 进缓存
  → key=1~10 全被驱逐（被后来的 key 挤走）

扫描结束后，再访问热点 key=1~10：全部 miss！
缓存需要重新预热 → 短暂的缓存雪崩

根本原因：LRU 只看"最近一次"访问时间，不看访问频率。一次扫描就能驱逐高频热点。

问题 2：时间局部性假设失效

LRU 隐含假设：最近用过的数据，将来大概率还会用

反例：视频流缓存
  用户顺序播放视频片段，每个片段只播一次
  最近访问的片段是"刚播完就再也不需要的"
  → LRU 缓存命中率极低（每次都是最新的，永远不复用）

更适合的算法：LIRS、ARC、W-TinyLFU

工程实现参考

Java LinkedHashMap（内置 LRU）

// accessOrder=true 表示按访问顺序排序（LRU 模式）
// removeEldestEntry 决定是否驱逐
class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;

    LRUCache(int capacity) {
        super(capacity, 0.75f, true);  // accessOrder=true
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;  // 超过容量时驱逐最老的
    }
}
// get/put 直接继承 LinkedHashMap，O(1)

Redis 的 LRU

Redis 使用近似 LRU（非精确），每个对象记录一个 24 bit 的 lru_clock（秒级时间戳）。驱逐时随机采样若干 key，选其中 lru_clock 最小的驱逐。详见 Redis LRU 近似算法。

参考资料

• LeetCode 146. LRU Cache
• Redis 对象结构：redisObject.lru
• Java LinkedHashMap 源码