缓存淘汰算法深度实战：从 LRU 到 W-TinyLFU 的完整演进之路

缓存是现代计算系统性能优化的核心手段，而缓存淘汰算法直接决定了缓存的有效性。本文从基础理论出发，深入剖析八种经典淘汰算法的原理、实现与工程实践，覆盖操作系统、数据库、分布式系统到 Web 应用的全场景应用。

一、为什么缓存淘汰如此重要

在计算系统中，缓存无处不在：CPU L1/L2/L3 缓存、操作系统页缓存、数据库 Buffer Pool、Redis/Memcached 分布式缓存、CDN 边缘缓存、浏览器本地缓存。它们的共同特点是存储空间有限，当缓存满时必须决定丢弃哪些数据——这就是缓存淘汰算法的核心问题。

一个优秀的淘汰算法能够：

• 最大化缓存命中率：减少昂贵的后端访问
• 最小化淘汰开销：算法本身的运行成本要低
• 适应访问模式变化：工作负载随时间演化
• 保证内存上限可控：不因元数据膨胀而失控

二、算法分类与评估指标

衡量淘汰算法的核心指标包括：

• Hit Ratio：缓存命中次数 / 总访问次数，最直观的指标
• Miss Ratio：补数，即 1 - Hit Ratio
• Byte Hit Ratio：按字节加权的命中率（对象大小不一时更有意义）
• 实现复杂度：时间复杂度、空间复杂度、并发安全成本
• 工作集适应性：扫描抵抗能力、时变负载适应能力

三、经典淘汰算法深度解析

3.1 FIFO（先进先出）

FIFO 是最简单的淘汰策略，维护一个队列，淘汰最早进入缓存的元素。

class FIFOCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = {}
        self.queue = collections.deque()
    
    def get(self, key):
        return self.cache.get(key, -1)
    
    def put(self, key, value):
        if key not in self.cache:
            if len(self.queue) >= self.capacity:
                evicted = self.queue.popleft()
                del self.cache[evicted]
            self.queue.append(key)
        self.cache[key] = value

时间复杂度：O(1) | 空间复杂度：O(n)

最严重的问题：Belady 异常——增大缓存容量反而可能降低命中率。此外，FIFO 不考虑访问频率，即使某个 key 被频繁访问也可能因为较早进入而被淘汰。

3.2 LRU（最近最少使用）

LRU 基于时间局部性原理：如果数据最近被访问过，那么将来被访问的概率也更高。实现上使用哈希表 + 双向链表。

public class LRUCache<K, V> {
    private final int capacity;
    private final Map<K, Node<K, V>> map;
    private final Node<K, V> head; // 哨兵头
    private final Node<K, V> tail; // 哨兵尾

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<>();
        head = new Node<>(null, null);
        tail = new Node<>(null, null);
        head.next = tail;
        tail.prev = head;
    }

    public V get(K key) {
        Node<K, V> node = map.get(key);
        if (node == null) return null;
        moveToHead(node); // 最近使用，移到头部
        return node.value;
    }

    public void put(K key, V value) {
        Node<K, V> node = map.get(key);
        if (node != null) {
            node.value = value;
            moveToHead(node);
        } else {
            if (map.size() >= capacity) {
                Node<K, V> evicted = removeTail();
                map.remove(evicted.key);
            }
            Node<K, V> newNode = new Node<>(key, value);
            addToHead(newNode);
            map.put(key, newNode);
        }
    }
}

时间复杂度：get/put 均为 O(1) | 空间复杂度：O(n)

LRU 的致命弱点：扫描抵抗能力极差。一次全表扫描就能把缓存中所有热数据全部替换为只访问一次的冷数据。MySQL Buffer Pool 早期因 LRU 扫描污染导致性能严重退化，后来演变为 midpoint insertion 方案。

3.3 LFU（最不常用）

LFU 基于频率局部性：访问次数多的键更可能被再次访问。淘汰时选择访问频率最低的键。

class LFUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.key_to_freq = {}
        self.freq_to_keys = collections.defaultdict(OrderedDict)
        self.min_freq = 0
    
    def get(self, key):
        if key not in self.key_to_freq:
            return -1
        freq = self.key_to_freq[key]
        self.freq_to_keys[freq].pop(key)
        if not self.freq_to_keys[freq] and freq == self.min_freq:
            self.min_freq += 1
        self.key_to_freq[key] = freq + 1
        self.freq_to_keys[freq + 1][key] = None
        return self.values[key]
    
    def put(self, key, value):
        if self.capacity <= 0:
            return
        if key in self.key_to_freq:
            self.values[key] = value
            self.get(key)  # 触发频率增加
            return
        if len(self.key_to_freq) >= self.capacity:
            evicted_key, _ = self.freq_to_keys[self.min_freq].popitem(last False)
            del self.key_to_freq[evicted_key]
            del self.values[evicted_key]
        self.key_to_freq[key] = 1
        self.freq_to_keys[1][key] = None
        self.values[key] = value
        self.min_freq = 1

时间复杂度：get/put 均为 O(1) | 空间复杂度：O(n)

LFU 的问题：历史频率的"惯性"——某个数据曾经很热但已冷却，却因高频率长期驻留缓存。此外，新进入的数据频率为1，即使马上会高频访问也会被立即淘汰。

3.4 2Q（Two Queue）

2Q 是 LRU 的改良版，通过两个队列解决单次扫描污染问题：

• A1（FIFO）：第一次进入的数据放这里，只给一次机会
• Am（LRU）：从 A1 被再次访问的数据升级到 Am，获得 LRU 的持久保护

// PostgreSQL Buffer Manager 使用的 2Q 变种
// Am 中的 buffer 必须被访问两次才能进入，过滤掉一次性扫描
#define HIT_THERESHOLD 3  // 某些变种使用多次命中阈值

if (buf->usage_count < HIT_THERESHOLD) {
    // 放入 A1 (once queue)
    dlist_push_head(&StrategyProtBufData[0], &buf->node);
} else {
    // 放入 Am (multi-queue / LRU)
    dlist_push_head(&StrategyAccessedList, &buf->node);
}

2Q 的实践应用：PostgreSQL 的 Buffer Manager、MySQL InnoDB 的改进 LRU（本质是 2Q 思路）。

3.5 ARC（自适应替换缓存）

ARC 能够在 LRU 和 LFU 之间动态自适应，同时追踪近期淘汰历史来指导当前决策。

核心结构——四个列表：

• T1：最近只访问过一次的数据页
• T2：最近访问过至少两次的数据页
• B1：T1 中被淘汰的幽灵记录（只保留元数据）
• B2：T2 中被淘汰的幽灵记录

class ARCCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.p = 0  # 自适应参数：偏好T1还是T2
        self.t1 = OrderedDict()  # 单次访问
        self.t2 = OrderedDict()  # 多次访问
        self.b1 = OrderedDict()  # T1幽灵
        self.b2 = OrderedDict()  # T2幽灵
    
    def replace(self, in_b2=False):
        if self.t1 and (len(self.t1) > self.p or 
                        (in_b2 and len(self.t1) == self.p) or
                        len(self.t2) == 0):
            key, _ = self.t1.popitem(last=False)
            self.b1[key] = None  # 移入ghost
        else:
            key, _ = self.t2.popitem(last=False)
            self.b2[key] = None  # 移入ghost
    
    def get(self, key):
        if key in self.t1:
            # T1命中：升级到T2
            del self.t1[key]
            self.t2[key] = 'val'
            return True
        if key in self.t2:
            # T2命中：保持在T2头部
            self.t2.move_to_end(key, last=False)
            return True
        # Miss，检查ghost
        if key in self.b1:
            # 幽灵命中B1：说明T1太小，增大p
            self.p = min(self.capacity, self.p + max(1, len(self.b2) // len(self.b1)))
            return False  # 仍需从后端加载
        if key in self.b2:
            # 幽灵命中B2：说明T2太小，减小p
            self.p = max(0, self.p - max(1, len(self.b1) // len(self.b2)))
            return False
        return False

ARC 的工程实践：IBM SAN 文件系统、PostgreSQL 社区曾经尝试引入 ARC 替代 2Q、ZFS 的 ARC（Adaptive Replacement Cache）就是基于此算法。

3.6 LIRS（低内部引用距离集）

LIRS 通过 IRD（Inter-Reference Recency，即同一数据页两次访问之间的间隔页数）来区分"热"和"冷"页面，比 LRU 更精准。

• HIR（高 IRD）：冷页面
• LIR（低 IRD）：热页面
• LIR 集合占用大部分缓存空间约 99%
• 淘汰时从 HIR 的 RESIDENT 中选择

LIRS 的优势：天然抵抗扫描污染——一次性扫描填充的 HIR 页面不会挤占 LIR 空间，且扫描数据很快被清理出缓存。Linux 内核的页面回收曾经有学者提出使用 LIRS 替代 LRU。

四、新一代利器：W-TinyLFU

4.1 设计动机

W-TinyLFU 是 Google Guava/Caffeine 缓存库使用的算法，它解决了传统算法的三个核心痛点：

1. LFU 频率衰减问题 → Count-Min Sketch 近似计数
2. 新数据冷启动问题 → Window TinyLFU 准入策略
3. LRU 扫描污染 → 频率感知的准入过滤

4.2 架构设计

// Caffeine 的 W-TinyLFU 结构示意
// 三个区域：Window LRU → Probation Observer → Protected
//          (准入区)    (试用期)              (保护区)

class BoundedLinkedHashMap {
    // Window 区 (1%): 纯 LRU，新数据入口
    AccessOrderDeque windowDeque;
    
    // Main 区 (99%): SLRU 分两个段
    //   - Probation (20%): 新晋升的数据
    //   - Protected (80%): 热数据保留区
    AccessOrderDeque probationDeque;
    AccessOrderDeque protectedDeque;

准入流程：新数据进入 Window LRU → 满时溢出到 Probation → 与候选者为频率"打架"，胜者留 Protected，败者驱逐。频率由 Count-Min Sketch 记录。

4.3 Count-Mis Sketch

class CountMinSketch:
    """概率型数据结构，用极小的空间近似记录访问频率"""
    def __init__(self, width=128, depth=4):
        self.width = width
        self.depth = depth
        self.table = [[0] * width for _ in range(depth)]
        # 使用4个不同的哈希函数
        self.hashes = [self._make_hash(i) for i in range(depth)]
    
    def increment(self, key):
        min_count = float('inf')
        for i in range(self.depth):
            idx = self.hashes[i](key) % self.width
            self.table[i][idx] += 1
            min_count = min(min_count, self.table[i][idx])
        return min_count
    
    def estimate(self, key):
        return min(
            self.table[i][self.hashes[i](key) % self.width]
            for i in range(self.depth)
        )
    
    def reset(self):
        """定期衰减所有计数，防止历史膨胀"""
        for i in range(self.depth):
            for j in range(self.width):
                self.table[i][j] //= 2

空间效率：传统 LFU 需要每个 key 存储完整计数（可能很大），Count-Min Sketch 用固定 O(width × depth) 的空间，128×4 仅需 512 个整数，无论缓存多少 key。

五、Redis 的工程实践：近似 LRU + LFU

5.1 Redis 近似 sampled LRU

Redis 没有使用精确的 LRU（因为每个对象都要加链表指针太耗内存），而是采用采样近似 LRU：

// evictionPoolLRU 中的候选池
// redis.conf 配置：maxmemory-samples 5
int freeMemoryIfNeeded(void) {
    while (mem_used + mem_tofree > server.maxmemory) {
        int j, k, keys_freed = 0;
        for (j = 0; j < server.maxmemory_samples; j++) {
            sds bestkey = NULL;
            robj *val;
            bestdbid = -1;
            // 如果 pool 未满，填充样本
            if (pool_len(eviction_pool) < EVAPCTION_POOL_SIZE) {
                while(pool_len(eviction_pool) < EVAPCTION_POOL_SIZE) {
                    // 随机选N个key放入pool
                    de = dictGetRandomKey(dict);
                    /* 计算 idle time (基于 lru clock) */
                    if (server.maxmemory_policy & MAXMEMORY_FLAG_LRU) {
                        idle = estimateObjectIdleTime(o);
                    } else { // LFU
                        idle = 255 - o->lru; // LFU: 频次越低 idle 越高
                    }
                    /* 按 idle time 插入优先队列 */
                    evictionPoolPopulate(i, key, idle, o);
                }
            }
            // 淘汰 idle time 最大的（LRU候选）
            if (bestkey) dbDelete(db, bestkey);
        }
    }
}

近似度控制：max-memory-samples 越大，越接近精确 LRU，但 CPU 开销越高。默认 5 已足够在大多数场景达到 80-90% 的精确度。

5.2 Redis LFU 模式

Redis 4.0+ 引入的 LFU 使用 24-bit 字段，分为两部分：

• 高 16 bits：分钟级 LRU 时间戳末 16 位（用于衰减）
• 低 8 bits：对数计数器（最大 255，指数增长避免小访问差距过大）

// LFU 频率递增（概率衰减式）
uint8_t LFULogIncr(uint8_t counter) {
    if (counter == 255) return 255;
    // 概率递增：counter 越大幅度增加越难
    double r = (double)rand()/RAND_MAX;
    double baseval = counter - LFU_INIT_VAL;
    if (baseval < 0) baseval = 0;
    double p = 1.0/(baseval*server.lfu_log_factor + 1);
    if (r < p) counter++;
    return counter;
}

衰减策略：每分钟所有 key 的 LFU 计数器根据上次访问的分钟数进行衰减，防止"历史热门"数据长期占用空间。

六、生产环境选型指南

场景	推荐算法	理由
CPU Cache / TLB	硬件 LRU/Pseudo-LRU	硬件实现，速度优先
数据库 Buffer Pool	改进 LRU / 2Q / ARC	抵抗全表扫描污染
Redis 通用场景	allkeys-lru	简单高效，命中率可接受
Redis 数据有长尾	allkeys-lfu	保护高频数据
Java 应用本地缓存	Caffeine (W-TinyLFU)	业界最高命中率
CDN / Web 缓存	GDSF / LRU	考虑对象大小和成本
大数据堆外缓存	ARC	自适应不同工作负载
内核页回收	LRU 双链 (active/inactive)	内核实现成熟稳定

七、总结与展望

缓存淘汰算法七十余年的发展呈现清晰的演进脉络：

• 1960s-1970s：FIFO/Clock/OPT 理论奠基
• 1980s-1990s：LRU/LFU 工程普及、2Q 解决扫描问题
• 2000s：ARC/LIRS 自适应与精确性提升
• 2010s：W-TinyLFU 融合概率数据结构与新-旧分区
• 2020s：ML-driven 淘汰（LEAR/CARTE）、工作负载感知自适应

从工程实践看，没有放之四海而皆准的"最佳"算法。选型三原则：了解你的工作负载特征（是否有扫描？频率分布如何？），测算算法元数据开销（每 key 额外内存），最后通过 benchmark 验证。Redis 的 sampled LRU 与 Caffeine 的 W-TinyLFU 是当前业界最成功的两种工程实现思路，值得深入学习。