缓存淘汰算法

一、设计思路

缓存设计不是简单选择一个“淘汰算法”。完整方案至少包含：

1. 容量约束：按条目数、字节数还是自定义权重限制。
2. 准入策略：发生 Miss 后，新数据是否值得进入缓存。
3. 淘汰策略：空间不足时，应该移除谁。
4. 过期策略：数据超过 TTL／TTI 后如何失效。
5. 加载与刷新：缓存未命中、即将过期时如何读取源数据。
6. 并发控制：如何避免击穿、重复加载和锁竞争。
7. 一致性：缓存与数据库之间允许多长时间不一致。
8. 可观测性：命中率、淘汰率、加载耗时和内存开销如何监控。

本文不把算法按“新旧”简单排序。一个算法是否优秀，取决于：

访问分布 × 缓存容量 × 对象大小 × 并发模型 × 回源成本 × 实现预算

2. 基本概念

2.1 Hit、Miss 与命中率

Hit：请求的数据在缓存中。
Miss：请求的数据不在缓存中，需要访问更慢的后端。

对象命中率 = Hit 次数 / 总请求次数
对象缺失率 = Miss 次数 / 总请求次数

对象大小差异很大时，还需要关注字节缺失率：

字节缺失率 = Miss 对象的总字节数 / 请求对象的总字节数

只优化对象命中率，可能留下少量超大对象，反而增加回源流量。因此 CDN、对象存储和磁盘缓存通常同时考虑：

• 对象缺失率；
• 字节缺失率；
• CPU 开销；
• 元数据开销；
• 并发扩展能力。

2.2 淘汰、过期、失效和准入不是一回事

概念	触发原因	解决的问题
淘汰 Eviction	容量不足	腾出空间
过期 Expiration	TTL／TTI 到期	控制数据新鲜度
主动失效 Invalidation	数据源发生变化	缓存一致性
准入 Admission	新对象准备进入	避免低价值对象污染缓存
刷新 Refresh	数据仍可用但需要更新	降低过期瞬间的延迟尖峰

传统 LRU/LFU 主要回答“淘汰谁”；TinyLFU 重点回答“新对象值不值得进入”。

2.3 Bélády 最优算法

理论上的最优策略是淘汰“距离下一次访问最远”的对象，也称 MIN／OPT。

它需要知道未来访问序列，线上无法实现，但可以作为离线模拟的上界，用于判断某个策略距离理论最优还有多远。

2.4 缓存问题的形式化

设请求轨迹为：

R = r1, r2, ..., rt

每个请求 ri 至少包含：

key、timestamp、objectSize、missCost、ttl、operationType

时刻 t 的缓存状态记为 Ct，容量约束为：

按对象数：|Ct| <= K

按字节数：Σ size(x) <= B，x ∈ Ct

请求到来时：

• 如果 ri.key ∈ Ct，产生 Hit，可更新算法元数据；
• 如果不在，产生 Miss，并支付回源、磁盘或计算成本；
• 如果决定准入新对象且容量不足，淘汰策略必须选择 Victim。

最简单的目标是最小化 Miss 数量：

min Σ miss(ri)

真实系统通常是多目标问题：

min α × 对象缺失成本
  + β × 回源字节
  + γ × CPU 开销
  + δ × 元数据内存
  + ε × 写放大／锁竞争

不同论文可能优化不同目标，不能只比较“命中率”就断言一个算法全面更好。

2.5 时间局部性与空间局部性

时间局部性：一个对象刚被访问后，短期内再次访问的概率较高。LRU 主要利用这一点。

空间局部性：访问一个地址后，邻近地址可能很快被访问。它在 CPU Cache、页面缓存和顺序预取中更重要，在普通 Key-Value Cache 中不一定直接成立。

频率局部性：部分对象在一个观察窗口内被重复访问。LFU、TinyLFU 等利用这一特征。

研究缓存前，应先问：

工作负载究竟表现为“最近访问更重要”，
还是“累计频率更重要”，
还是存在顺序扫描、周期循环、阶段性热点和一击即逝对象？

2.6 复用时间、复用距离与栈距离

对同一个 Key 的两次连续访问：

• 复用时间 Reuse Time：两次访问之间经过的时间；
• 复用距离 Reuse Distance：两次访问之间访问过多少个不同对象；
• 栈距离 Stack Distance：在 LRU 栈模型中，该对象再次访问时距离栈顶的位置。

对于全相联、等大小对象和 LRU，复用距离可直接判断给定容量是否命中：

reuseDistance < cacheCapacity  =>  Hit

这使得一条轨迹可以推导多个容量下的 LRU Miss Ratio Curve，而不必为每个容量重新运行完整模拟。

2.7 工作集与阶段变化

工作集是在某个时间窗口内活跃的数据集合。真实系统的工作集往往随时间变化：

• 白天和夜间热点不同；
• 新闻、直播、促销产生短时热点；
• 扫描任务短时间访问大量冷数据；
• 软件发布或模型版本切换使旧热点突然失效。

因此，纯累计 LFU 容易被历史绑架；任何频率算法都需要窗口、衰减或重置机制。

2.8 栈算法与 Bélády 异常

如果容量为 K 时的缓存内容始终是容量 K+1 缓存内容的子集，这类算法具有包含性质。LRU 是典型栈算法，因此增加容量不会使同一轨迹的 Miss 数增加。

FIFO 不具备这一性质，所以页面置换中可能出现 Bélády 异常。这个现象的深层意义不是“FIFO 一定差”，而是提醒我们：

容量增加是否单调改善，需要由算法性质证明，不能只凭直觉。

---

3. FIFO：先进先出

3.1 思想

FIFO 按进入缓存的先后顺序淘汰：最早进入的对象最先离开。

队头：最早进入，优先淘汰
队尾：最新进入

访问一个已经存在的对象，不改变它在队列中的位置。

3.2 数据结构

HashMap：O(1) 查找 Key
ArrayDeque：维护插入顺序

3.3 Java 实现

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

public class FIFOCache<K, V> {

    private final int capacity;
    private final Map<K, V> data;
    private final Deque<K> order;

    public FIFOCache(int capacity) {
        if (capacity <= 0) {
            throw new IllegalArgumentException("capacity must be positive");
        }

        this.capacity = capacity;
        this.data = new HashMap<>((int) (capacity / 0.75f) + 1);
        this.order = new ArrayDeque<>(capacity);
    }

    public V get(K key) {
        // FIFO 的访问不会改变顺序
        Objects.requireNonNull(key, "key");
        return data.get(key);
    }

    public void put(K key, V value) {
        Objects.requireNonNull(key, "key");
        Objects.requireNonNull(value, "value");

        if (data.containsKey(key)) {
            // 更新已有值，但保留原进入顺序
            data.put(key, value);
            return;
        }

        if (data.size() == capacity) {
            K oldestKey = order.removeFirst();
            data.remove(oldestKey);
        }

        data.put(key, value);
        order.addLast(key);
    }

    public V remove(K key) {
        Objects.requireNonNull(key, "key");
        V removed = data.remove(key);
        if (removed != null) {
            // ArrayDeque 按值删除是 O(n)
            order.remove(key);
        }
        return removed;
    }

    public int size() {
        return data.size();
    }
}

这份实现的 get/put 为均摊 O(1)，但任意 Key 的 remove 因为需要从队列中查找，最坏为 O(n)。如果删除也是高频操作，可以用带节点索引的双向链表。

3.4 优点

• 逻辑简单；
• 插入和淘汰开销低；
• Cache Hit 不需要调整全局顺序，并发扩展性较好；
• 顺序写入对磁盘／闪存缓存较友好。

3.5 缺点

• 不考虑访问频率和最近访问时间；
• 可能淘汰仍然很热门、但进入时间较早的数据；
• 对不同访问模式的适应能力弱；
• 传统页面置换场景中可能出现 Bélády 异常：增加页面数后缺页率反而升高。

3.6 需要纠正的常见说法

“FIFO 现在已经不再使用”并不准确。

基础 FIFO 的命中率可能不理想，但它因为简单、无 Hit 顺序更新、容易扩展，仍然是现代算法的重要构件。2023 年的 S3-FIFO 和 2024 年的 SIEVE 都重新证明了 FIFO 风格结构在大规模缓存中的价值。

---

4. LRU：最近最久未使用

4.1 思想

LRU 假设最近访问过的数据，近期更可能再次访问。当缓存满时，淘汰最长时间没有访问的对象。

链表头：最久未使用，优先淘汰
链表尾：刚被访问，最近使用

get 和 put 都会改变访问顺序。

4.2 LinkedHashMap 实现

import java.util.LinkedHashMap;
import java.util.Map;

public class LRUCache<K, V> extends LinkedHashMap<K, V> {

    private final int maxSize;

    public LRUCache(int maxSize) {
        // true：访问顺序；false：插入顺序
        super((int) (maxSize / 0.75f) + 1, 0.75f, true);

        if (maxSize <= 0) {
            throw new IllegalArgumentException("maxSize must be positive");
        }

        this.maxSize = maxSize;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > maxSize;
    }
}

示例：

LRUCache<String, Integer> cache = new LRUCache<>(3);

cache.put("A", 1);
cache.put("B", 2);
cache.put("C", 3);

cache.get("A");     // A 移动到最近使用端
cache.put("D", 4); // 淘汰 B

System.out.println(cache);
// 顺序类似：{C=3, A=1, D=4}

4.3 从基本数据结构推导 LRU

为了观察 LRU 的核心不变量，可以直接使用：

HashMap<K, Node<K,V>> + 双向链表 + 头尾哨兵

核心操作：

private void moveToTail(Node<K, V> node) {
    detach(node);
    appendToTail(node);
}

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

private void appendToTail(Node<K, V> node) {
    Node<K, V> previous = tail.prev;

    previous.next = node;
    node.prev = previous;
    node.next = tail;
    tail.prev = node;
}

注意：detach() 只改变链表关系，不能删除 HashMap 映射，也不能清空 Value。只有真正淘汰时才同时执行：

detach(lruNode);
cache.remove(lruNode.key);

4.4 优点

• get/put/evict 都可以做到 O(1)；
• 适合具有明显时间局部性的访问；
• 实现成熟，容易理解和调试。

4.5 缺点

• 全量扫描会把一次性数据放到链表尾部，挤掉真正热点；
• 每次 Hit 都要修改双向链表，并发场景可能产生锁竞争；
• 不区分“访问一次”和“访问一万次但刚好稍久未访问”；
• 每个条目需要额外维护前后指针。

---

5. LFU：最不经常使用

5.1 思想

LFU 记录对象的访问频率，缓存满时淘汰频率最低的对象；频率相同时通常再使用 LRU 或 FIFO 作为二级规则。

5.2 为什么“小顶堆 + HashMap”不是唯一答案

小顶堆可以找到最低频对象，但存在两个问题：

• 每次访问后频率发生变化，需要调整堆，复杂度为 O(log n)；
• 需要额外保存节点在堆中的位置，否则更新更麻烦。

为了把频率更新和最小频率淘汰都降到均摊 O(1)，可以使用：

keyToNode：Key -> 节点
frequencyToKeys：频率 -> 同频率 Key 的 LinkedHashSet
minFrequency：当前最小频率

5.3 Java O(1) 实现

import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.Map;

public class LFUCache<K, V> {

    private final int capacity;
    private int minFrequency;

    private final Map<K, Node<K, V>> nodes = new HashMap<>();
    private final Map<Integer, LinkedHashSet<K>> frequencyBuckets =
            new HashMap<>();

    public LFUCache(int capacity) {
        if (capacity <= 0) {
            throw new IllegalArgumentException("capacity must be positive");
        }
        this.capacity = capacity;
    }

    public V get(K key) {
        Node<K, V> node = nodes.get(key);
        if (node == null) {
            return null;
        }

        increaseFrequency(node);
        return node.value;
    }

    public void put(K key, V value) {
        Node<K, V> existing = nodes.get(key);
        if (existing != null) {
            existing.value = value;
            increaseFrequency(existing);
            return;
        }

        if (nodes.size() == capacity) {
            evictOne();
        }

        Node<K, V> node = new Node<>(key, value, 1);
        nodes.put(key, node);
        frequencyBuckets
                .computeIfAbsent(1, ignored -> new LinkedHashSet<>())
                .add(key);
        minFrequency = 1;
    }

    private void increaseFrequency(Node<K, V> node) {
        int oldFrequency = node.frequency;
        LinkedHashSet<K> oldBucket = frequencyBuckets.get(oldFrequency);

        oldBucket.remove(node.key);

        if (oldBucket.isEmpty()) {
            frequencyBuckets.remove(oldFrequency);
            if (minFrequency == oldFrequency) {
                minFrequency++;
            }
        }

        node.frequency++;
        frequencyBuckets
                .computeIfAbsent(
                        node.frequency,
                        ignored -> new LinkedHashSet<>())
                .add(node.key);
    }

    private void evictOne() {
        LinkedHashSet<K> bucket = frequencyBuckets.get(minFrequency);
        K victimKey = bucket.iterator().next();

        bucket.remove(victimKey);
        if (bucket.isEmpty()) {
            frequencyBuckets.remove(minFrequency);
        }

        nodes.remove(victimKey);
    }

    private static class Node<K, V> {
        private final K key;
        private V value;
        private int frequency;

        private Node(K key, V value, int frequency) {
            this.key = key;
            this.value = value;
            this.frequency = frequency;
        }
    }
}

LinkedHashSet 在相同频率内部保留进入顺序，因此可以淘汰同频率中最久未使用的 Key。

5.4 优点

• 能长期保留真正高频对象；
• 对热点集合稳定、访问频率差异明显的工作负载有效；
• 合理的数据结构可让核心操作达到均摊 O(1)。

5.5 缺点

• 历史热点可能长期霸占缓存；
• 新热点需要积累频率才能竞争过旧热点；
• 频率计数可能无限增长；
• 元数据和实现复杂度高于 LRU。

5.6 工程改进

• 定期衰减频率，例如除以 2；
• 只统计最近一个时间窗口；
• 频率使用饱和计数器，达到上限后不再增加；
• 同频率内部结合 LRU；
• 使用 Count-Min Sketch 做近似统计，减少空间开销。

---

6. CLOCK 与 Second-Chance

6.1 思想

CLOCK 是对 LRU 的近似。每个对象维护一个访问位 referenceBit，再维护一个循环指针：

1. Hit 时只把访问位置为 1，不移动节点；
2. 需要淘汰时，从指针位置开始扫描；
3. 如果访问位是 1，将其清零并跳过，给予“第二次机会”；
4. 如果访问位是 0，直接淘汰；
5. 指针继续循环前进。

6.2 特点

• Hit 路径只写一个 Bit，通常比精确 LRU 更容易并发扩展；
• 不需要每次访问都修改双向链表顺序；
• 淘汰可能需要扫描多个对象，单次最坏不是严格 O(1)；
• 常用于操作系统页面置换、缓冲区和高并发缓存。

---

7. 经典改进算法

7.1 LRU-K

LRU-K 记录对象最近 K 次访问时间，根据第 K 次最近访问判断价值。

LRU-1：传统 LRU
LRU-2：至少经历两次访问后，才更可能被视为稳定热点

优点是能区分一次性扫描和重复访问；代价是需要保存更多历史信息。

7.2 SLRU：分段 LRU

SLRU 通常分成两个区域：

Probation：试用区，新对象进入这里
Protected：保护区，再次命中后晋升

保护区满时，把其中最旧对象降级回试用区。它避免一次访问的新对象直接挤掉成熟热点。

7.3 2Q

2Q 使用多个队列区分：

• 第一次访问的新对象；
• 被重复访问的热点对象；
• 已经淘汰但仍保存 Key 元数据的 Ghost 队列。

如果一个刚被淘汰的 Key 很快再次出现，说明它有较高复用价值，应进入热点队列。2Q 比纯 LRU 更抗扫描，但需要更多队列与元数据。

7.4 ARC：自适应替换缓存

ARC 同时跟踪“最近性”和“频率性”：

• 近期只访问过一次的对象；
• 至少访问过两次的对象；
• 两类对象对应的 Ghost 历史。

它根据 Ghost 命中情况动态调整两个主区域的大小，从而适应偏最近性或偏频率性的工作负载。

优点是自适应能力强；缺点是实现和元数据开销更高。

7.5 LIRS

LIRS 依据对象两次访问之间的间隔判断复用价值，而不只看最近一次访问时间。

它对循环扫描、弱局部性负载可能优于 LRU，但状态管理和实现复杂度较高，更适合专门存储系统而不是普通业务代码手写。

---

8. TinyLFU 与 W-TinyLFU

8.1 TinyLFU 的关键变化：准入控制

传统策略在 Miss 后通常直接把新对象放入缓存，再淘汰旧对象。TinyLFU 会比较：

新对象候选者的估算频率
        vs
缓存中淘汰候选者的估算频率

只有新对象更值得保留时，才允许它进入主缓存。

TinyLFU 使用类似 Count-Min Sketch 的紧凑结构估算频率，并通过定期衰减让历史热点逐渐失去优势。

8.2 W-TinyLFU 的结构

请求
  |
  v
Window LRU：接住突发的新对象
  |
  | Window 淘汰候选
  v
TinyLFU 准入比较
  |
  v
Main Cache：通常使用 SLRU 保护稳定热点

小型 Window 解决“新热点还没有频率历史”的问题；主区域保留长期热点；TinyLFU 阻止一次性对象污染主缓存。

8.3 Caffeine 的实践

Caffeine 官方设计使用 Window TinyLFU：小型准入窗口、主缓存区域以及频率草图共同兼顾最近性与频率性。其设计还会根据访问模式动态调整窗口与主区域的比例。

Cache<String, Object> cache = Caffeine.newBuilder()
        .maximumSize(10_000)
        .expireAfterAccess(Duration.ofMinutes(10))
        .recordStats()
        .build();

如果对象大小差异明显，应考虑权重限制：

Cache<String, byte[]> cache = Caffeine.newBuilder()
        .maximumWeight(100 * 1024 * 1024L)
        .weigher((String key, byte[] value) -> value.length)
        .build();

在 Java 业务系统中，Caffeine 通常比自行维护一个并发 LRU 更可靠，因为它还处理了并发访问、过期维护、统计、异步加载等工程问题。

---

9. S3-FIFO：三段静态 FIFO

9.1 背景

大量真实缓存轨迹中存在很多“一击即逝”对象：进入缓存后不会再次被访问。如果使用 LRU，这些对象仍会进入最近使用端，可能污染缓存，并且每次 Hit 都要维护链表顺序。

S3-FIFO 在 2023 年提出，核心由三个 FIFO 队列组成：

S：Small，小型队列，快速筛掉一次性对象
M：Main，主队列，保存重复使用对象
G：Ghost，只保存已淘汰对象的标识，不保存 Value

9.2 核心思想

• 新对象先进入小队列；
• 被重复访问的对象更有机会进入主队列；
• Ghost 命中说明对象被过早淘汰，可提高其准入优先级；
• Hit 时主要更新少量访问状态，不需要像精确 LRU 一样立即移动节点；
• 使用快速降级和延迟晋升降低一次性对象污染及锁竞争。

9.3 适用场景

• CDN、块缓存、对象缓存；
• 一击即逝对象很多；
• 多线程吞吐和锁竞争非常重要；
• 闪存缓存，希望尽量顺序写入。

S3-FIFO 的官方材料报告了其在大量真实轨迹上的优势，但任何百分比都依赖轨迹、缓存大小和指标，不能直接等价为某个业务一定提升同样幅度。

---

10. SIEVE：惰性晋升与快速淘汰

10.1 数据结构

SIEVE 可以理解为：

单个 FIFO 风格队列
+ 每个对象一个 visited Bit
+ 一个沿队列移动的淘汰指针

10.2 工作过程

Hit：
    visited = 1
    不立即移动节点

Evict：
    从淘汰指针开始扫描
    如果 visited == 1：
        visited = 0
        跳过，给它一次保留机会
    如果 visited == 0：
        淘汰该对象

这是一种“惰性晋升”：Hit 路径不维护全局顺序，把是否保留的判断推迟到淘汰时。

10.3 为什么适合高并发

• Cache Hit 不需要移动双向链表节点；
• 大量读请求不必争用全局 LRU 锁；
• 元数据少，实现相对简单；
• 对 Web Cache 工作负载具有较强的扫描抵抗能力。

SIEVE 在 NSDI 2024 发布。论文强调它在 Web Cache 轨迹上的命中效率和并发扩展性，但它仍然不是所有负载的绝对最优策略。

---

11. 2025—2026 学习型缓存研究

11.1 3L-Cache（FAST 2025）

学习型策略尝试预测对象未来的复用价值，接近无法在线实现的 Bélády 最优决策。但逐对象训练和预测会带来明显 CPU 开销。

3L-Cache 的主要方向是：

• 过滤不必要的训练历史；
• 动态调整训练频率；
• 通过双向采样优先寻找不热门对象；
• 自动调节参数；
• 同时关注对象缺失率、字节缺失率和计算开销。

论文实验显示它显著降低了部分既有学习策略的 CPU 开销，但其成本仍高于 LRU。因此更适合作为研究与专业缓存系统方案，而不是普通 Java 服务的默认本地缓存。

11.2 LAH 与 S4-FIFO（OSDI 2026）

Learning-Augmented Heuristics（LAH）的思路不是让模型逐个决定淘汰谁，而是：

数据平面：继续使用简单、快速、可解释的启发式策略
控制平面：低频、异步地学习缓存级参数

S4-FIFO 是基于这一框架的 Smart S3-FIFO，通过模型学习 S3-FIFO 的缓存级参数。

这种设计的价值在于：

• 热路径仍然简单；
• 学习开销不压在每次访问上；
• 模型负责调参，而不是替代全部缓存逻辑；
• 比逐对象黑盒决策更容易解释和回退。

截至 2026 年，它代表缓存算法研究的新方向。工程采用时仍需评估模型分布漂移、训练数据、降级路径和实现成熟度。

---

12. Redis 的实际淘汰策略

Redis 的淘汰由 maxmemory 和 maxmemory-policy 控制。

maxmemory 4gb
maxmemory-policy allkeys-lru

当前官方文档列出的主要策略包括：

具体策略是否可用取决于 Redis 版本、发行版和部署形态；例如较新的 LRM 策略不能直接假设旧版 Redis 已支持，落地前应核对目标实例的官方文档和配置能力。

策略	含义
noeviction	不淘汰，新增写入返回错误
allkeys-lru	从全部 Key 中淘汰近似 LRU
allkeys-lfu	从全部 Key 中淘汰近似 LFU
allkeys-lrm	从全部 Key 中淘汰最近最少修改对象
allkeys-random	从全部 Key 随机淘汰
volatile-lru	只在设置 TTL 的 Key 中执行 LRU
volatile-lfu	只在设置 TTL 的 Key 中执行 LFU
volatile-lrm	只在设置 TTL 的 Key 中执行 LRM
volatile-random	只在设置 TTL 的 Key 中随机淘汰
volatile-ttl	优先淘汰剩余 TTL 最短的 Key

12.1 Redis 不是精确 LRU

Redis 为减少全局链表和每 Key 元数据开销，采用采样方式近似选择 LRU／LFU 淘汰对象。采样数量可以影响准确性和 CPU 消耗。

因此：

• Redis 的 allkeys-lru 不等于 Java LinkedHashMap 的精确 LRU；
• 增大采样数量可能更接近精确策略，但会增加 CPU 工作；
• 选择策略前应观察 keyspace_hits、keyspace_misses、evicted_keys 等指标；
• volatile-* 在没有符合条件的 TTL Key 时无法按预期腾出空间；
• 混合缓存数据和不可丢数据时，最好拆分实例或内存池，而不是只依赖 volatile-*。

12.2 选型建议

• 明显二八热点、最近性强：allkeys-lru；
• 稳定热点、需要保留长期高频 Key：allkeys-lfu；
• 数据的新鲜度由业务 TTL 精确表达：可考虑 volatile-ttl；
• Redis 既承担缓存又承担不可丢状态：优先拆实例；
• 不能接受任何自动淘汰：noeviction，同时做好容量告警和写失败处理。

---

13. 算法对比

算法	主要依据	Hit 是否改顺序	抗扫描	元数据	并发扩展	典型问题
FIFO	进入时间	否	弱	低	强	可能淘汰热点
LRU	最近访问时间	是	弱	中	中／弱	扫描污染、Hit 锁竞争
LFU	访问频率	是	较强	高	中	历史热点不易退出
CLOCK	访问 Bit	否	中	低	强	淘汰时可能扫描
SLRU	最近性＋重复访问	是	较强	中	中	分区比例需要选择
2Q	首次／重复访问	部分	强	中／高	中	多队列和 Ghost 元数据
ARC	最近性＋频率自适应	是	强	高	中	实现复杂
W-TinyLFU	最近性＋频率准入	是／近似	强	中	强	Sketch 为近似统计
S3-FIFO	三段 FIFO＋复用信息	否／惰性	强	中	强	实现比基础 FIFO 复杂
SIEVE	FIFO＋访问 Bit＋指针	否／惰性	强	低	强	效果依赖访问轨迹
3L-Cache	对象级学习	取决于实现	强	高	取决于实现	训练／预测开销
S4-FIFO	启发式＋学习调参	数据平面简单	强	中／高	强	新方案、成熟度待评估

复杂度表中的 O(1) 通常是均摊复杂度；并发实现还需考虑锁、CAS、缓冲区和维护任务。

14. 如何选择

场景一：普通 Java 服务本地缓存

推荐：Caffeine。

理由：

• W-TinyLFU 命中率通常优于基础 LRU；
• 支持按数量或权重限制；
• 支持访问后过期、写入后过期和异步加载；
• 并发和维护逻辑成熟。

场景二：从零实现算法实验

为了理解数据结构与状态转移，可以分别实现：

• FIFO：HashMap + Queue；
• LRU：HashMap + 双向链表；
• LFU：Key -> Node + Frequency -> LinkedHashSet + minFrequency。

实验报告必须明确：

• get/put 复杂度；
• 容量为 0／1 的边界；
• 更新已有 Key 是否改变顺序／频率；
• 同频率如何淘汰；
• 多线程是否安全。

场景三：Redis 纯缓存

先根据数据访问模式选择 allkeys-lru 或 allkeys-lfu，再用真实指标验证。不要只凭算法名称判断。

场景四：CDN／大对象缓存

除了对象命中率，还要关注字节缺失率、对象大小、写放大和磁盘顺序性。S3-FIFO、SIEVE、GDSF 类大小感知策略可能比基础 LRU 更合适。

场景五：扫描流量明显

基础 LRU 容易被扫描污染，可以考虑：

• SLRU／2Q；
• W-TinyLFU；
• S3-FIFO；
• SIEVE。

场景六：访问模式持续变化

• 基础 LFU 需要频率衰减；
• ARC／自适应 W-TinyLFU 可以动态平衡最近性与频率性；
• 学习型策略需要可靠的回退策略和在线监控。

---

15. 生产级缓存还需要解决什么

算法只决定“留下谁”，生产缓存还要回答“为什么缓存、放在哪里、怎样读写、允许多旧、缓存坏了怎么办”。实战时不要先选 LRU 或 LFU，先把业务约束写清楚。

15.1 先判断这个数据是否适合缓存

一个对象值得缓存，通常同时满足：重复读取明显、源数据读取较慢或成本较高、允许短时间陈旧、对象大小可控。设计前至少记录：

问题	影响
读写比例是多少	读多写少更容易获得稳定收益
同一个 Key 会不会重复访问	一次性数据即使命中率高也可能不值得缓存
数据允许旧多久	决定 TTL、刷新和一致性方案
Miss 的代价是什么	数据库查询、远程调用和模型推理的价值不同
对象有多大	决定按条目还是按字节限制
缓存不可用时源站能否承受	决定限流、降级和旧值兜底

下面几类数据要谨慎：只访问一次的大对象、必须强一致的余额与库存结果、每次读取都依赖用户权限的敏感数据、源数据本来就很快且缓存维护成本更高的数据。

先设一个可以验证的目标，例如：

把商品详情接口 P99 从 180 ms 降到 60 ms
把数据库读取 QPS 从 8000 降到 2500 以下
允许价格信息最多陈旧 5 秒
缓存故障时数据库 QPS 不超过保护阈值

没有目标，命中率再高也无法判断缓存是否真正有效。

15.2 架构选型与容量规划

本地缓存、Redis 与两级缓存怎么选。

方案	适合场景	优点	主要代价
Caffeine 本地缓存	单实例数据、配置、字典、短生命周期热点	延迟低、无网络调用	每个实例一份数据，失效广播复杂
Redis 分布式缓存	多实例共享、容量较大、需要统一失效	数据集中、跨实例共享	网络延迟、序列化、集群故障
Caffeine + Redis	极热数据、跨机房或高 QPS 读取	L1 抗流量，L2 共享数据	两层一致性、容量和监控更复杂

两级缓存的常见读路径是：

请求 -> L1 Caffeine -> L2 Redis -> 数据库

写入或失效时顺序相反：先改变数据源，再让 L2 和所有 L1 失效。L1 的 TTL 应比 L2 更短，并且必须有广播失效或版本检查，否则不同实例会长时间持有不同旧值。

不要因为“多一级更快”就默认使用两级缓存。若 Redis 已经满足延迟和吞吐目标，额外的 L1 会增加故障组合与排查成本。

容量规划不能只写 maximumSize。

缓存占用不只是 Value：

总内存 ≈ Key + Value + 对象头 + 引用 + 哈希表 + 淘汰元数据 + 临时加载对象

容量规划步骤：

1. 从堆或容器内存中预留业务对象、线程栈、直接内存和 GC 空间；
2. 用序列化大小、对象采样或内存分析工具估算条目重量；
3. 按字节或业务权重设置硬上限；
4. 给加载中的临时对象和流量突增留余量；
5. 用压测观察 GC、淘汰速度和源站 QPS，而不是只看条目数。

对象大小差异明显时，Caffeine 可以按权重限制：

LoadingCache<String, Product> productCache = Caffeine.newBuilder()
        .maximumWeight(256L * 1024 * 1024)
        .weigher((String key, Product value) -> value.estimatedBytes())
        .expireAfterWrite(Duration.ofMinutes(30))
        .refreshAfterWrite(Duration.ofMinutes(5))
        .executor(refreshExecutor)
        .recordStats()
        .build(productRepository::findRequired);

这里有几个容易误解的点：

• maximumWeight 控制的是业务定义的重量，不等于 JVM 精确堆占用；
• 权重在创建或更新条目时计算，Value 内部变化后不会自动重算；
• refreshAfterWrite 只是让对象具备刷新资格，后续访问才会触发刷新；
• 刷新期间可以继续返回旧值，刷新失败也要监控，不能把错误静默当成功；
• 刷新线程池必须独立限流，避免慢源站拖垮公共线程池。

15.3 读路径：Cache-Aside 与请求合并

最常用的是 Cache-Aside：

读取缓存
  命中 -> 返回
  未命中 -> 读取数据源 -> 写入缓存 -> 返回

单 JVM 使用 Caffeine 时，优先使用原子加载，而不是手写“先 get、再 put”：

Product product = productCache.get(productId, productRepository::findRequired);

它可以合并同一进程内同一个 Key 的并发加载。多实例共同访问 Redis 时，本地原子加载不能阻止其他实例同时回源，需要额外的 SingleFlight、每 Key 短锁或异步刷新。

一个完整的 Miss 路径应进行二次检查：

V get(K key) {
    V cached = cache.getIfPresent(key);
    if (cached != null) {
        return cached;
    }

    return singleFlight.execute(key, () -> {
        V secondCheck = cache.getIfPresent(key);
        if (secondCheck != null) {
            return secondCheck;
        }

        V loaded = source.load(key);
        cache.put(key, loaded);
        return loaded;
    });
}

请求合并不是无限等待：等待者必须继承请求超时；加载任务要有限流；源站失败时可以返回短时间旧值或业务降级值；加载完成后必须释放每 Key 状态，避免锁表不断增长。

对不存在的数据，可以缓存一个显式的 NullValue，并使用比正常数据更短的 TTL。不要用 Java null 同时表达“未命中”和“数据确实不存在”，否则调用方无法区分两种状态。

15.4 写路径：一致性先定义边界

缓存一般不是事实来源，数据库才是。常见写路径是：

提交数据库事务
    -> 删除缓存
    -> 删除失败则可靠重试

为什么通常删除而不是直接更新缓存：一次数据库更新可能影响多个查询视图，业务代码很容易只更新其中一个缓存；删除后由下一次读取根据数据库重建，更容易保持单一数据来源。

但“更新数据库后删除缓存”不是强一致。存在一个典型竞态：

读请求 A：缓存 Miss，读到数据库旧版本 v1
写请求 B：提交 v2，并删除缓存
读请求 A：晚一步把 v1 写回缓存

根据业务允许的不一致窗口，分层处理：

1. 允许秒级最终一致：数据库更新后删除缓存，删除失败重试，再用 TTL 兜底；
2. 要求失效事件不丢：数据库事务同时写 Outbox，异步消费者或 CDC 删除 Redis，并广播删除所有 L1；
3. 需要阻止旧值回填：缓存值携带数据版本，写入前比较版本，旧版本不能覆盖新版本；
4. 关键读必须读到刚写结果：写接口直接返回数据库结果，关键链路短时间绕过缓存，或者使用更强的串行化方案。

Outbox／CDC 解决的是“失效消息可靠送达”，仍然存在消息传播延迟。版本号解决的是“新旧覆盖顺序”，但需要数据源提供单调版本。两者不能被一句“最终一致”替代，必须写明最大延迟、补偿责任和失败告警。

15.5 TTL、刷新与三类缓存故障

TTL、刷新与旧值兜底。

TTL 要从业务新鲜度倒推，而不是统一写 30 分钟：

硬 TTL：超过后绝不再返回
软 TTL：超过后触发刷新，但允许短时间返回旧值
随机抖动：避免大量 Key 同时到期

例如：

实际 TTL = 基础 TTL + random(0, 基础 TTL × 10%)

常见策略：

• 配置与字典：事件失效为主，较长 TTL 防止漏消息；
• 商品详情：中等 TTL，加变更事件删除；
• 热点榜单：短 TTL 或定时刷新，允许返回上一版本；
• 高成本模型结果：按输入版本构造 Key，较长 TTL，并限制对象大小；
• 权限、余额、库存：只缓存可接受陈旧的派生结果，关键校验仍访问事实来源。

异步刷新要防止“刷新风暴”：限制并发、合并同 Key、设置超时、记录刷新失败，并给旧值设置最终硬过期时间。旧值兜底只能降低可用性故障，不能用于已经撤销权限或明确要求立即生效的数据。

缓存穿透、缓存击穿和缓存雪崩如何真正处理。

问题	现象	核心措施	边界
穿透	大量查询不存在的 Key	参数校验、空值缓存、Bloom Filter、限流	Bloom Filter 有误判，不能替代源站校验
击穿	单个热点失效，大量请求同时回源	SingleFlight、异步刷新、短锁、旧值兜底	单机锁不能保护多实例
雪崩	大量 Key 同时失效或缓存整体不可用	TTL 抖动、预热、限流、熔断、源站保护	多级缓存不能代替降级预案

处理顺序应从源站保护开始：

1. 为数据库和下游设置并发上限；
2. 超出上限时快速失败或返回降级结果；
3. 再使用合并、预热和 TTL 分散降低回源量；
4. 最后才讨论是否扩容缓存。

如果缓存完全不可用，所有请求直接穿透到数据库，往往比缓存故障本身更危险。因此必须能在故障演练中证明：限流器能生效、降级数据可接受、恢复后不会出现集中回填。

15.6 并发实现与 Redis 落地

不要把 ConcurrentHashMap 当成完整缓存。

ConcurrentHashMap 只能保证 Map 操作安全，不能自动保证“Map + 链表 + 频率桶 + 总重量”的复合不变量。精确 LRU 的 get() 也会移动节点，因此读请求会产生共享写入和锁竞争。

业务系统优先使用成熟实现。确实需要自行实现或研究时，至少检查：

• 同一个节点不会重复插入或摘除；
• Map 删除与淘汰结构删除保持一致；
• 更新已有 Key 时重量差额正确；
• 容量为 0、1 时状态仍正确；
• 加载异常不会遗留永久占位；
• 维护线程落后时内存不会无限超限；
• 回调中不持有全局锁调用慢服务。

高并发缓存常把热路径事件先写入缓冲区，由维护线程批量更新淘汰结构。这用“短时间近似不精确”换取更少的全局锁竞争，也是 Caffeine、SIEVE 等设计值得迁移的地方。

Redis 配置与数据治理。

Redis 用作纯缓存时，先设置明确的内存上限和淘汰策略：

maxmemory 4gb
maxmemory-policy allkeys-lru
maxmemory-samples 5

选择建议：

• 不了解负载时，allkeys-lru 是容易验证的基线；
• 稳定热点长期重复访问时，可以比较 allkeys-lfu；
• volatile-* 只在带 TTL 的 Key 中选择，若没有可淘汰 Key，行为可能退化为拒绝写入；
• 缓存数据和不可丢的持久数据尽量不要混在同一个 Redis 实例；
• 调大采样数可能更接近精确策略，但会增加 CPU，必须用 Miss 与延迟数据验证。

数据治理同样重要：

• Key 带业务命名空间和版本，例如 product:v3:detail:123；
• Value 使用稳定序列化格式，限制单 Key 大小；
• 批量读取使用 MGET、Pipeline 等方式减少网络往返，但限制单批数量；
• 热 Key 需要本地缓存、复制读或业务拆分，单纯扩容分片不一定能分散同一个 Key；
• 禁止在线使用会扫描全库的高风险命令；
• 明确 Cluster 重定向、超时、重试和连接池上限，避免无限重试放大故障。

15.7 监控、压测与上线

监控时，命中率只是结果之一。

建议从五个维度监控：

维度	指标示例	能回答的问题
效果	Hit、Miss、对象／字节缺失率	缓存是否保住了有价值的数据
源站	回源 QPS、P95/P99、错误率	缓存是否真的降低下游压力
容量	当前重量、淘汰数量、淘汰重量	容量是否过小或大对象是否污染
加载	加载耗时、失败、超时、合并等待者	Miss 路径是否成为延迟尖峰
新鲜度	版本落后、失效延迟、旧值返回次数	一致性承诺是否兑现

排查顺序不要只盯 Hit Rate：

命中率下降
  -> 是 TTL 到期增多，还是容量淘汰增多
  -> 是新流量没有复用，还是热点集合变化
  -> 回源 QPS 和延迟是否同步上升
  -> 大 Key、失败加载或失效广播是否异常

Redis 可结合 keyspace_hits、keyspace_misses、evicted_keys、expired_keys 和内存指标；Caffeine 使用 recordStats() 采集命中、加载和淘汰统计。应用层还要记录业务 Key 类型，否则只能看到整体下降，无法定位是哪类对象导致。

压测与上线要按故障过程验证。

缓存压测至少覆盖五个阶段：

1. 冷启动：缓存为空，验证源站能否承受预热流量；
2. 稳定期：观察命中率、容量、P99 和 GC；
3. 热点到期：让单个热点 Key 过期，验证请求合并；
4. 缓存故障：模拟超时、连接耗尽和部分节点不可用，验证限流与降级；
5. 恢复期：验证回填速率受控，不因集中加载再次压垮源站。

上线顺序：

只记录不返回的影子模式
  -> 小流量读取缓存
  -> 逐步扩大流量
  -> 开启写入和失效事件
  -> 故障演练
  -> 根据指标调整容量与 TTL

上线前必须准备：缓存旁路开关、限流阈值、降级值、预热脚本、清理命令、失效补偿任务和回滚方案。真正的完成标准不是“接入了 Redis”，而是缓存命中、缓存失效、缓存故障和缓存恢复四条路径都能被观测和控制。

15.8 三个可直接套用的方案模板

模板一：单体或单实例查询加速

Caffeine LoadingCache
+ maximumWeight
+ expireAfterWrite
+ refreshAfterWrite
+ recordStats

适合配置、字典和中等规模只读对象。先用 cache.get(key, loader) 合并加载，再根据对象大小和业务新鲜度设重量与时间。

模板二：多实例共享业务缓存

Cache-Aside Redis
+ 数据库提交后删除
+ Outbox 或 CDC 可靠失效
+ TTL 抖动
+ 热点请求合并
+ 数据库限流

适合商品、用户资料等多实例读取。核心不是 Redis 客户端调用，而是删除失败、旧值回填和缓存故障时谁负责兜底。

模板三：极热数据两级缓存

L1 Caffeine 短 TTL
  -> L2 Redis 较长 TTL
  -> 数据库

适合少量极热 Key。变更后通过消息同时失效 L2 与各实例 L1；消息漏发由 TTL 和定期对账兜底。只有 Redis 网络开销已经成为瓶颈时，才值得承担这层复杂度。

---

16. 统一研究框架：从思想到实验

这一章把原来的研究思想、模拟器、学习路线、复现实验和开放问题合在一起。目标不是再记一批算法名，而是学会拆解、验证和比较算法。

16.1 用七个问题拆解任何缓存算法

维度	要问的问题	典型例子
复用信号	用最近性、频率还是复用距离预测未来	LRU、LFU、LIRS
准入	Miss 对象是否一定进入	TinyLFU
淘汰反馈	淘汰后还保留什么信息	2Q、ARC、S3-FIFO 的 Ghost
元数据	精确记录还是近似统计	精确 LRU、CLOCK、Sketch
更新时间	Hit 立即移动还是淘汰时判断	LRU、SIEVE
对象价值	是否考虑大小与回源成本	GDSF、Cost-aware Cache
适应方式	固定参数、自适应还是模型学习	ARC、3L-Cache、S4-FIFO

这些设计本质上都在交换成本：

更多历史信息 -> 可能提高策略质量，但增加内存和更新开销
更精确的顺序 -> 可能减少 Miss，但增加锁竞争
更积极的刷新 -> 降低陈旧与冷 Miss，但增加源站负载

对象大小和 Miss 成本不同时，可以用下面的思路理解对象价值：

utility(x) = predictedReuse(x) × missCost(x) / size(x)

不同算法是在用不同信息近似 predictedReuse。线上算法不知道未来，不能达到 Bélády MIN；论文轨迹结果也只代表给定轨迹、容量和指标，不能跳过业务验证。

16.2 最小轨迹模拟器

学习算法最有效的实践是实现一个很小的 Simulator，而不是继续扩充概念笔记。

统一接口只需要表达一次访问的状态变化：

public interface CachePolicy<K> {
    AccessResult access(K key, int size, long timestamp);
    PolicyStats stats();
}

AccessResult 至少区分：

HIT
MISS_ADMITTED
MISS_REJECTED
MISS_ADMITTED_WITH_EVICTION
EXPIRED

轨迹从最简单的 Key 序列开始，再逐步增加：

timestamp,key,size,missCost,ttl,operation

模拟主循环保持一致：

for (Request request : trace) {
    AccessResult result = policy.access(
            request.key(), request.size(), request.timestamp());
    metrics.record(request, result);
}

至少记录对象缺失率、字节缺失率、回源成本、准入／拒绝／淘汰次数、元数据字节数和每请求状态更新次数。研究并发实现时，再记录吞吐、P99、锁等待、CAS 重试和维护积压。

正确性先用小轨迹人工推导，再用随机轨迹与低效参考实现对拍。比较策略时固定轨迹、容量、预热、TTL、随机种子和统计区间；否则结果没有可比性。

16.3 只做四个关键实验

实验一：扫描污染。 固定一组稳定热点，再周期性扫描超过缓存容量的一次性对象。比较 LRU、2Q、W-TinyLFU 与 SIEVE，观察热点被挤出数量和扫描结束后的恢复请求数。

实验二：热点切换。 长时间访问集合 A，再突然切换到集合 B。比较无衰减 LFU、衰减 LFU、ARC 与 W-TinyLFU，观察 Miss 峰值和适应时间。

实验三：大小和成本。 同时生成小对象高频、大对象低频和大对象高回源成本三类请求，分别优化对象缺失率、字节缺失率和总回源成本。这个实验能直接说明“最高命中率”不等于“最低成本”。

实验四：热路径开销。 统计每次 Hit 的共享状态写入：LRU 移动节点、CLOCK/SIEVE 写 Bit、FIFO 不改顺序；再做多线程吞吐测试，把策略收益与 CPU、锁等待放到一起比较。

同时运行 Bélády MIN 作为离线上界，并为不同容量画 Miss Ratio Curve。若算法已经接近 MIN，复杂模型的空间有限；若增加容量后收益很小，继续扩容也未必值得。

16.4 学习顺序压缩为四步

1. 实现不变量：FIFO、LRU、LFU，完成边界测试和随机对拍；
2. 理解局部性：Bélády、复用距离、CLOCK、2Q、ARC、LIRS；
3. 研究现代取舍：TinyLFU、W-TinyLFU、S3-FIFO、SIEVE，重点比较准入、Ghost 与 Hit 路径成本；
4. 最后研究学习型策略：先建立强启发式基线，再比较训练、预测、分布漂移和回退成本。

每一步都应产生可验证输出：实现、轨迹、指标和失败反例。没有复现实验时，“某算法更好”只是一条无法迁移的结论。

16.5 值得继续研究的问题

• 多目标：如何同时处理对象命中、字节、延迟、能耗与写放大；
• TTL 与淘汰：剩余寿命很短的对象是否值得继续占用容量；
• 多级缓存：对象应该保留、晋升、降级、复制还是删除；
• 多租户：全局命中率与租户公平、配额和 SLO 如何平衡；
• 分布式缓存：本地决策与全局热点、路由和副本如何协同；
• 学习策略：模型失效、分布漂移和控制面故障时如何退回静态策略；
• LLM KV／Prefix Cache：如何把前缀共享、显存、重计算成本和租户公平纳入对象价值。

深入研究一个算法，最后只需要持续回答：它假设什么、保存什么、何时更新、优化什么、牺牲什么、在哪些轨迹上失败，以及并发实现后是否仍然值得。

---

17. 论文与资料阅读顺序

基础与经典算法

1. FIFO、LRU、LFU、CLOCK 的教材章节；
2. 2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm；
3. LIRS: An Efficient Low Inter-reference Recency Set Replacement Policy；
4. ARC: A Self-Tuning, Low Overhead Replacement Cache；
5. Mattson 等人的 Stack Distance 理论及其后续高效计算研究；
6. SHARDS：MRC 近似构建，FAST 2015 Proceedings。

建议读法：先读 Abstract 和 Introduction，写出论文试图修复的基线缺陷，再读算法和评估；不要先陷入伪代码细节。

现代算法

1. TinyLFU: A Highly Efficient Cache Admission Policy；
2. Caffeine：Window TinyLFU 设计；
3. S3-FIFO：FIFO Queues are All You Need for Cache Eviction；
4. SIEVE：NSDI 2024。

建议重点比较：

Hit 路径需要更新什么？
新对象如何快速降级？
算法保存多少 Ghost／频率信息？
对象缺失率改善是否以 CPU、锁或内存为代价？

学习型策略

1. 3L-Cache：FAST 2025；
2. LAH / S4-FIFO：OSDI 2026。

建议重点比较逐对象预测与缓存级参数学习：模型介入粒度越细，潜在决策能力越强，但训练、预测、稳定性和部署成本通常也越高。

工程实现作为研究案例

• Redis 官方：Key eviction；
• Caffeine 官方 Wiki：Population；
• Caffeine 官方 Wiki：Eviction；
• Caffeine 官方 Wiki：Refresh；
• Caffeine 官方 Wiki：Efficiency。

阅读工程实现时，不只看它“用了什么算法”，还要研究算法为了并发、内存布局、维护线程和 API 语义做了哪些近似。

18. 总结：研究缓存应抓住的主线

缓存算法的演进可以概括为六条主线：

1. 预测信息：从插入顺序，到最近性、频率、复用距离，再到学习模型。
2. 时间范围：从无限历史，到滑动窗口、衰减和阶段自适应。
3. 决策拆分：从只研究 Eviction，到 Admission、Eviction、Expiration、Refresh 协同。
4. 状态成本：从精确全局顺序，到采样、Sketch、Bit 和 Ghost Metadata。
5. 执行时机：从 Hit 时立即晋升，到 Eviction 时惰性判断。
6. 目标函数：从对象命中率，到字节、延迟、CPU、锁、能耗、公平性和写放大。

真正深入研究一个算法时，至少回答：

它对工作负载做了什么假设？
它观测哪些信号，丢弃哪些信息？
它的状态转移不变量是什么？
它优化哪个指标，又牺牲了什么？
它在哪些反例上会失败？
它与 Bélády MIN 的差距来自哪里？
它的论文结果能否在不同轨迹和容量下复现？
它在并发实现后是否仍然值得？

这比记住某个算法“命中率更高”更接近缓存研究的核心。