缓存淘汰策略深度解析：LRU、LFU、FIFO、TTL的原理与适用场景

大家好，我是你们的老朋友。今天我们来聊聊缓存淘汰策略。

说实话，很多同学觉得这玩意儿就是背背概念。LRU、LFU、FIFO，背完就完事了。但我在项目中踩过不少坑，发现选错策略的代价，比想象中大得多。

你想想看，缓存命中率从95%掉到70%，数据库瞬间被打爆。这种事故，我见过不止一次。

所以今天，咱们把四种主流策略掰开揉碎，讲清楚它们各自适合什么场景。

1. LRU：最常用的策略，但别盲目用

LRU（Least Recently Used），最近最少使用。它的核心逻辑很简单：淘汰最长时间没有被访问的数据。

实现上，一般用双向链表+哈希表。每次访问数据，就把这个节点移到链表头部。淘汰时，直接干掉链表尾部的节点。

// 伪代码示例
class LRUCache {
    // 双向链表节点
    Node head, tail;
    // 哈希表，O(1)查找
    HashMap<K, Node> map;
    
    void get(K key) {
        Node node = map.get(key);
        // 移到头部
        removeNode(node);
        addToHead(node);
        return node.value;
    }
    
    void put(K key, V value) {
        if (map.size() >= capacity) {
            // 淘汰尾部节点
            removeNode(tail.prev);
        }
        // 新节点加到头部
        addToHead(newNode);
    }
}

适用场景：

• 热点数据访问模式比较稳定
• 数据访问有局部性（比如用户最近浏览的商品）
• Redis的近似LRU实现，就是典型应用

2. LFU：适合稳定的热点场景

LFU（Least Frequently Used），最不经常使用。它淘汰的是访问频率最低的数据。

实现上，每个数据维护一个访问计数器。每次访问，计数器+1。淘汰时，找计数器最小的那个。

嗯，这里要注意：LFU有个经典问题——缓存污染。某个数据曾经很火，后来没人访问了，但它的计数器很高，一直赖着不走。

// LFU核心数据结构
class LFUCache {
    // key -> 频率
    HashMap<K, Integer> freqMap;
    // 频率 -> 双向链表
    HashMap<Integer, LinkedHashSet<K>> freqList;
    
    void get(K key) {
        int oldFreq = freqMap.get(key);
        int newFreq = oldFreq + 1;
        freqMap.put(key, newFreq);
        // 从旧频率链表移到新频率链表
        freqList.get(oldFreq).remove(key);
        freqList.get(newFreq).add(key);
    }
}

适用场景：

• 热点数据相对固定，比如CDN中的热门视频
• 数据库查询缓存，某些SQL被频繁执行
• 需要防止突发流量冲垮缓存的场景

3. FIFO：简单，但别用在核心路径

FIFO（First In First Out），先进先出。说白了就是队列，谁先来谁先走。

实现极其简单，一个队列就搞定。但问题也很明显：完全不考虑访问频率和时效性。

// FIFO实现，简单到令人发指
class FIFOCache {
    Queue<K> queue;
    
    void put(K key, V value) {
        if (queue.size() >= capacity) {
            // 队首出队
            K oldest = queue.poll();
            cache.remove(oldest);
        }
        queue.offer(key);
        cache.put(key, value);
    }
}

适用场景：

• 数据有效期明确，比如日志缓存
• 对命中率要求不高的场景
• 作为其他策略的补充（比如LRU的二级缓存）

4. TTL：时间是最好的裁判

TTL（Time To Live），生存时间。每个数据设置一个过期时间，到期自动删除。

实现上，可以用时间轮或者延迟队列。Redis的过期策略就是典型的TTL应用。

// TTL实现思路
class TTLCache {
    // 数据 + 过期时间戳
    HashMap<K, Entry> cache;
    
    V get(K key) {
        Entry entry = cache.get(key);
        if (entry == null) return null;
        // 检查是否过期
        if (System.currentTimeMillis() > entry.expireAt) {
            cache.remove(key);
            return null;
        }
        return entry.value;
    }
}

适用场景：

• 数据有时效性，比如验证码、Session
• 数据源会主动更新，比如配置中心
• 需要保证数据最终一致性的场景

5. 如何根据业务选择最优策略？

这个问题，我一般会问自己三个问题：

1. 数据有没有时效性？ 有的话，TTL是必须的。
2. 热点数据是稳定的还是突发的？ 稳定用LFU，突发用LRU。
3. 对命中率要求多高？ 高的话，别用FIFO。

下面这张图，是我总结的选择流程：

最后说一句：没有银弹。我见过很多系统，最终用的是组合策略。比如LRU+TTL，或者LFU+LRU的混合模式。

好了，这一章就到这里。记住：选策略不是选最牛的，而是选最合适的。