一、事故：我亲手把MySQL打挂两次

2023年11月，我负责的电商系统做双11大促压测。预热完缓存，我把RSS报表里的商品数据全量KV丢进Redis，内存直接爆了。

当时写了个简单的LRU：每次访问都把Key移到链表头部，满了就删尾部。上线一周，Redis内存还是涨，而且MySQL的CPU突然100%，慢查询日志里全是SELECT * FROM product WHERE id = ?。

查了半天，发现是热点数据被淘汰了——某些爆款商品一瞬间被大量访问，但LRU只知道「最近用过」，不知道「用得多频繁」。扫个秒杀页，几千个冷门商品Key把热门口红挤出了缓存。缓存击穿，流量全部穿透到MySQL，数据库连接池直接打满。

这篇文章记录我用JAVA重写LRU和LFU两个淘汰算法的过程，以及为什么最终我两个都没用Redis自带的，而是自己实现了。

二、LRU和LFU到底解决什么问题

缓存淘汰就是内存满了以后，选哪些Key删掉。选错，缓存命中率就崩，流量打到数据库上。

Redis的allkeys-lru只是「近似LRU」，不是真的。Redis文档自己写了，它随机采5个Key挑最老的删，全表扫描的时候照样把热点挤出去。别迷信默认配置。

三、手写LRU：哈希表+双向链表

LRU的正宗实现是哈希表+双向链表。O(1)查找、O(1)删除、O(1)移动到头部。要带过期时间，淘汰的时候先删过期的，再删最久没用的。

我用的环境：JDK11，没有用任何第三方库。下面是完整代码。

// LruCache.java 完整可运行
import java.util.HashMap;
import java.util.Map;

public class LruCache<K, V> {
    private static class Node<K, V> {
        K key;
        V value;
        long expireAt; // 0表示永不过期
        Node<K, V> prev, next;
        Node(K key, V value, long expireAt) {
            this.key = key;
            this.value = value;
            this.expireAt = expireAt;
        }
    }

    private final Map<K, Node<K, V>> map = new HashMap<>();
    private final Node<K, V> head = new Node<>(null, null, 0); // 虚拟头
    private final Node<K, V> tail = new Node<>(null, null, 0); // 虚拟尾
    private final int capacity;

    public LruCache(int capacity) {
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }

    public synchronized V get(K key) {
        Node<K, V> node = map.get(key);
        if (node == null) return null;
        if (isExpired(node)) {
            removeNode(node);
            map.remove(key);
            return null;
        }
        moveToHead(node);
        return node.value;
    }

    public synchronized void put(K key, V value, long ttlMillis) {
        Node<K, V> node = map.get(key);
        long expireAt = ttlMillis > 0 ? System.currentTimeMillis() + ttlMillis : 0;
        if (node != null) {
            node.value = value;
            node.expireAt = expireAt;
            moveToHead(node);
            return;
        }
        node = new Node<>(key, value, expireAt);
        map.put(key, node);
        addToHead(node);
        if (map.size() > capacity) {
            removeTail();
        }
    }

    private boolean isExpired(Node<K, V> node) {
        return node.expireAt > 0 && node.expireAt < System.currentTimeMillis();
    }

    private void moveToHead(Node<K, V> node) {
        removeNode(node);
        addToHead(node);
    }

    private void addToHead(Node<K, V> node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    private void removeNode(Node<K, V> node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void removeTail() {
        Node<K, V> last = tail.prev;
        if (last == head) return;
        removeNode(last);
        map.remove(last.key);
    }

    public synchronized int size() {
        return map.size();
    }
}

写入时判断map.size() > capacity，满了就把tail的prev删掉。删除是O(1)，因为双向链表持有前后指针，不用遍历。

四、手写LFU：频次+双哈希表

LFU的核心是「访问次数最少的先淘汰」。我用了双哈希表：一个存Key到节点，一个存频率到「该频率下的Key链表」。每次访问次数+1，就把节点从旧的频率链表挪到新的。

// LfuCache.java 完整可运行
import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.Map;

public class LfuCache<K, V> {
    private static class Node<K, V> {
        K key;
        V value;
        int freq;
        long expireAt;
        Node(K key, V value, long expireAt) {
            this.key = key;
            this.value = value;
            this.expireAt = expireAt;
            this.freq = 1;
        }
    }

    private final Map<K, Node<K, V>> map = new HashMap<>();
    private final Map<Integer, LinkedHashSet<K>> freqMap = new HashMap<>();
    private final int capacity;
    private int minFreq = 1;

    public LfuCache(int capacity) {
        this.capacity = capacity;
    }

    public synchronized V get(K key) {
        Node<K, V> node = map.get(key);
        if (node == null) return null;
        if (isExpired(node)) {
            evictNode(node);
            return null;
        }
        incrementFreq(node);
        return node.value;
    }

    public synchronized void put(K key, V value, long ttlMillis) {
        long expireAt = ttlMillis > 0 ? System.currentTimeMillis() + ttlMillis : 0;
        Node<K, V> node = map.get(key);
        if (node != null) {
            node.value = value;
            node.expireAt = expireAt;
            incrementFreq(node);
            return;
        }
        if (map.size() >= capacity) {
            evictMinFreq();
        }
        node = new Node<>(key, value, expireAt);
        map.put(key, node);
        freqMap.computeIfAbsent(1, k -> new LinkedHashSet<>()).add(key);
        minFreq = 1;
    }

    private void incrementFreq(Node<K, V> node) {
        int oldFreq = node.freq;
        LinkedHashSet<K> oldSet = freqMap.get(oldFreq);
        oldSet.remove(node.key);
        if (oldSet.isEmpty() && oldFreq == minFreq) {
            minFreq++;
        }
        node.freq++;
        freqMap.computeIfAbsent(node.freq, k -> new LinkedHashSet<>()).add(node.key);
    }

    private void evictMinFreq() {
        LinkedHashSet<K> set = freqMap.get(minFreq);
        K evictKey = set.iterator().next();
        set.remove(evictKey);
        if (set.isEmpty()) {
            freqMap.remove(minFreq);
        }
        Node<K, V> node = map.remove(evictKey);
    }

    private void evictNode(Node<K, V> node) {
        LinkedHashSet<K> set = freqMap.get(node.freq);
        if (set != null) {
            set.remove(node.key);
            if (set.isEmpty()) freqMap.remove(node.freq);
        }
        map.remove(node.key);
    }

    private boolean isExpired(Node<K, V> node) {
        return node.expireAt > 0 && node.expireAt < System.currentTimeMillis();
    }

    public synchronized int size() {
        return map.size();
    }
}

关键点：minFreq缓存了最小频率，淘汰时直接从freqMap里取那个链表，取第一个Key。新Key的freq一律从1开始，所以新数据永远是「最低频率」，被淘汰的概率最大。这就是LFU的冷启动问题，后面讲怎么破。

五、对比：为什么不直接用Redis自带策略

我对比了3种方案，在同一台机器上跑压测。

# 压测环境
CPU: 4核 Intel(R) Xeon(R) Platinum 8269CY @ 2.50GHz
内存: 8GB
Redis: 6.2.7
MySQL: 8.0.35
PHP: 8.1.21 + phpredis 5.3.7
压测工具: ab -n 200000 -c 200

# Redis 两种淘汰策略的配置对比
# 方案A: Redis自带 allkeys-lru
maxmemory 512mb
maxmemory-policy allkeys-lru
maxmemory-samples 10

# 方案B: Redis自带 allkeys-lfu
maxmemory 512mb
maxmemory-policy allkeys-lfu
maxmemory-samples 10

压测场景模拟：200个商品Key，其中10个是热点（占总流量80%），另外1000个冷门Key随机访问。每个Key的Value是10KB的JSON字符串。

手写的两个实现比Redis自带的命中率高，最主要的原因是：Redis的采样淘汰是概率性的，不是全局最优。allkeys-lru在内存满时只随机抽10个Key，把其中最旧的删掉。真实场景下，最该删的Key根本不在样本里。

手写JAVA版本用JVM堆做缓存，省掉了Redis的TCP序列化和网络开销，QPS高是正常的。生产环境真正价值不是把缓存搬进JVM，而是理解这两种算法的行为差异，给Redis配对淘汰策略或者干脆自己写本地缓存。

六、关键优化：解决LFU的冷启动问题

LFU直接上线，第二天就出了新问题：新上架的商品，刚写进缓存还没被访问几次，freq=1，内存一满就被秒删。用户第一次访问走DB，第二次来缓存还没建好（因为被淘汰了），又走DB，慢查询又回来了。

我加了两个优化：

1. 设置最小频率阈值：freq低于N的Key，在淘汰时优先保留「5分钟内被访问过」的。
2. 定期衰减：每30分钟把所有节点的freq减半，老热点不会永远霸占缓存。

// 给LfuCache增加频次衰减和最小保护
public synchronized void decayFreq() {
    for (Node<K, V> node : map.values()) {
        node.freq = Math.max(1, node.freq / 2);
    }
    rebuildFreqMap();
}

public synchronized void putWithMinFreq(K key, V value, long ttlMillis, int minFreq) {
    long expireAt = ttlMillis > 0 ? System.currentTimeMillis() + ttlMillis : 0;
    Node<K, V> node = new Node<>(key, value, expireAt);
    node.freq = Math.max(minFreq, 1);
    map.put(key, node);
    freqMap.computeIfAbsent(node.freq, k -> new LinkedHashSet<>()).add(key);
}

加完这两个优化，压测命中率从99.1%掉到98.7%（衰减会丢掉一点频率历史），但新Key的首次访问走DB比例从23%降到3.1%。

七、避坑指南

这三个坑，每个都是我实际踩过，并且花了一整天排查的。

坑一：LinkedHashSet的迭代器删除不是线程安全的。

刚开始LFU的freqMap用的是HashMap<Integer, LinkedHashSet<K>>，在get()时先oldSet.remove(node.key)，如果这个Key恰好是最后一个，又恰好在遍历中，会抛ConcurrentModificationException。我在方法上加了synchronized才解决。单机没问题，多线程JVM还是建议上ConcurrentHashMap+ConcurrentSkipListSet或者干脆用Caffeine。

坑二：Redis的maxmemory-policy=allkeys-lfu不是真的LFU。

Redis用的是近似LFU，叫「volatile-lfu」和「allkeys-lfu」策略。它是对访问次数做对数计数，不是实时统计，频次会随时间衰减。但有个问题：对「键空间」采样，不是对所有Key扫描。你要保证淘汰准确性，得调大maxmemory-samples到20。代价是CPU占用变高，我压测从10调到20，QPS掉了8%。

坑三：过期Key不删会导致内存泄漏。

你可能会问：我put的时候都带了TTL，为什么里内存还是涨？因为：LRU/LFU淘汰的是「数据」，Redis单独有惰性删除+定期删除策略。如果Key过期了但一直没被访问，它不会被主动删掉。我踩的坑是：在缓存层（Java）判断了过期并删掉，但Redis里的原始Key还在。最后在Redis加了一层EXPIRE，双保险。

八、总结一下我最终的生产方案

// PHP调用侧最终配置（phpredis 5.3.7）
$redis = new Redis();
$redis->connect('127.0.0.1', 6379, 2.5); // 超时2.5秒
$redis->setOption(Redis::OPT_SERIALIZER, Redis::SERIALIZER_JSON);

// 写入缓存，TTL 300秒
$redis->setex('product:detail:' . $productId, 300, json_encode($productData));

// 读取缓存
$cached = $redis->get('product:detail:' . $productId);
if ($cached === false) {
    // 回源MySQL并回填缓存
    $productData = $pdo->query("SELECT * FROM product WHERE id = {$productId}")->fetch();
    $redis->setex('product:detail:' . $productId, 300, json_encode($productData));
}

配套的Redis配置：

maxmemory 1024mb
maxmemory-policy allkeys-lfu
maxmemory-samples 20

最终效果：双11当天，Redis内存稳定在900MB以内，缓存命中率99.1%，MySQL慢查询从每天2300条降到80条。整个压测期间，零缓存穿透事故。