罗罗编程学习记录
本页内容 展开查看

02.10.1 LRU 与 LFU 缓存设计

所属:全栈开发面试题库 / 02 数据结构与算法 / 02.10 设计类与手写题

覆盖范围

  • 哈希表 + 双向链表的 LRU 完整 O(1) 实现
  • LFU 频次桶与最小频率维护
  • 并发安全的 LRU 改造思路
  • Redis 近似 LRU 采样策略与精确 LRU 的对照
  • 缓存淘汰策略选型与缓存穿透/雪崩/击穿

高频题速览

编号 题目 难度 频率
02.10.1-001 手写 LRU 缓存(哈希 + 双向链表) 基础 ★★★★★
02.10.1-002 LFU 缓存 O(1) 实现(频次桶) 高级 ★★★★★
02.10.1-003 LRU 如何改造为线程安全版本 进阶 ★★★★
02.10.1-004 Redis 近似 LRU 与精确 LRU 的差异 进阶 ★★★★
02.10.1-005 FIFO / LRU / LFU / ARC 怎么选 进阶 ★★★★
02.10.1-006 LFU 中最小频率为什么不会错删 高级 ★★★
02.10.1-007 缓存穿透、雪崩、击穿与淘汰策略的关系 基础 ★★★★★
02.10.1-008 LRU 热点数据抖动问题如何缓解 高级 ★★★

02.10.1-001 手写 LRU 缓存(哈希 + 双向链表)

频率 ★★★★★ | 难度 基础

一句话结论

哈希表存 key 到节点的映射,双向链表按访问时间排最近(头)到最久(尾);get 命中把节点移到头,put 命中更新移头、未命中插头并在超容量时删尾,两处同步;均摊 O(1)。

概念解释

  • 节点必须同时存 key 和 value,淘汰尾节点时要拿 key 去哈希表删映射。
  • 用哑头哑尾消除空指针判断,所有插入删除都按中间节点处理。
  • 哈希负责 O(1) 按键定位,链表负责 O(1) 维护访问顺序,二者互补。

原理流程

  1. 初始化:head.next = tail,tail.prev = head,map = {}。
  2. get:map 命中则 remove 节点 + addToHead,返回 value;未命中返回 -1。
  3. put:map 命中则更新 value + moveToHead;未命中新建节点 addToHead 并 map.put;随后若 size > cap,删 tail.prev 并 map.remove。

代码 / 示例

class LRUCache {
    static class Node {
        int key, val; Node prev, next;
        Node(int k, int v) { key = k; val = v; }
    }
    private final int cap;
    private final Map<Integer, Node> map = new HashMap<>();
    private final Node head = new Node(0, 0), tail = new Node(0, 0);

    LRUCache(int cap) {
        this.cap = cap;
        head.next = tail; tail.prev = head;
    }
    public int get(int key) {
        Node n = map.get(key);
        if (n == null) return -1;
        moveToHead(n);
        return n.val;
    }
    public void put(int key, int value) {
        Node n = map.get(key);
        if (n != null) { n.val = value; moveToHead(n); return; }
        Node fresh = new Node(key, value);
        map.put(key, fresh); addToHead(fresh);
        if (map.size() > cap) {
            Node old = tail.prev;
            remove(old);
            map.remove(old.key);
        }
    }
    private void addToHead(Node n) {
        n.prev = head; n.next = head.next;
        head.next.prev = n; head.next = n;
    }
    private void remove(Node n) {
        n.prev.next = n.next; n.next.prev = n.prev;
    }
    private void moveToHead(Node n) { remove(n); addToHead(n); }
}

常见误区

  • 误区:节点只存 val;正解:淘汰时要拿 key 删哈希,节点必须存 key。
  • 误区:put 同键会插入第二个节点;正解:先查 map,命中走更新分支,不新增节点。
  • 误区:淘汰时只删链表不删哈希;正解:两处同步删除,否则内存泄漏。

追问 / 延伸

  • Q:为什么不用单链表? A:单链表删已知节点需遍历找前驱,O(n)。
  • Q:容量为 0 怎么处理? A:题目一般保证 cap >= 1;若 cap=0,put 后立即淘汰。

02.10.1-002 LFU 缓存 O(1) 实现(频次桶)

频率 ★★★★★ | 难度 高级

一句话结论

维护三张表:key -> Node、freq -> 双向链表(同频率节点,按时间排)、minFreq;每次访问把节点从旧频率桶摘除、挂到 freq+1 桶,淘汰时从 minFreq 桶尾摘;所有操作 O(1)。

概念解释

  • 每个节点记录 key、value、freq。
  • 频率桶用双向链表,桶内按时间排序(新插头、旧留尾),同频率内再按 LRU 淘汰。
  • minFreq 维护当前最小频率;新增节点 freq=1 时重置 minFreq=1;某桶删空时若它是 minFreq 则 minFreq++。

原理流程

  1. get:查 key,节点 freq++;从旧桶摘除(空桶且是 minFreq 则 minFreq++),挂到新 freq 桶头。
  2. put 命中:同 get,但额外更新 value。
  3. put 未命中:新建节点 freq=1,挂到 freq=1 桶头,minFreq=1;超容量时删 minFreq 桶尾,同步删 key 表。

代码 / 示例

class LFUCache {
    static class Node {
        int key, val, freq = 1; Node prev, next;
        Node(int k, int v) { key = k; val = v; }
    }
    private final int cap;
    private int minFreq;
    private final Map<Integer, Node> keyMap = new HashMap<>();
    private final Map<Integer, LinkedHashSet<Node>> freqMap = new HashMap<>();

    LFUCache(int cap) { this.cap = cap; }

    public int get(int key) {
        Node n = keyMap.get(key);
        if (n == null) return -1;
        bump(n);
        return n.val;
    }
    public void put(int key, int value) {
        if (cap == 0) return;
        Node n = keyMap.get(key);
        if (n != null) { n.val = value; bump(n); return; }
        if (keyMap.size() == cap) {
            LinkedHashSet<Node> minSet = freqMap.get(minFreq);
            Node victim = minSet.iterator().next(); // 桶尾最久
            minSet.remove(victim);
            keyMap.remove(victim.key);
        }
        Node fresh = new Node(key, value);
        keyMap.put(key, fresh);
        freqMap.computeIfAbsent(1, k -> new LinkedHashSet<>()).add(fresh);
        minFreq = 1;
    }
    private void bump(Node n) {
        int f = n.freq;
        LinkedHashSet<Node> old = freqMap.get(f);
        old.remove(n);
        if (old.isEmpty() && f == minFreq) minFreq = f + 1;
        n.freq++;
        freqMap.computeIfAbsent(n.freq, k -> new LinkedHashSet<>()).add(n);
    }
}

常见误区

  • 误区:用一个 PriorityQueue 按 freq 排;正解:每次访问 freq 变化都要堆调整,O(log n),不满足 O(1)。
  • 误区:minFreq 删空时忘记 ++;正解:旧桶空且是 minFreq 时要推进 minFreq,否则下次淘汰找不到桶。
  • 误区:桶内用普通 HashSet;正解:需要保留插入顺序(同频率按 LRU),用 LinkedHashSet。

追问 / 延伸

  • Q:minFreq 会不会永远停在 1? A:只要 freq=1 桶被删空且有新节点 freq=2,minFreq 就推进。
  • Q:空间复杂度? A:O(cap),节点与桶都是容量级别。

02.10.1-003 LRU 如何改造为线程安全版本

频率 ★★★★ | 难度 进阶

一句话结论

朴素版用一把 ReentrantLock 包住 get/put 即可线程安全但并发度低;进阶用 ConcurrentHashMap 存节点 + 分段锁或读写锁维护链表;生产环境直接用 Caffeine 或 LinkedHashMap 的同步包装。

概念解释

  • 粒度:全局锁简单但 get 也串行;读写锁让读并发,但 get 命中要移头(写操作),不能纯读。
  • Collections.synchronizedMap(new LinkedHashMap(...)) 是最简单的同步包装,但所有方法同一把锁。
  • Caffeine 基于 W-TinyLFU 思想,结合了 LRU 与 LFU,且有高并发实现,生产环境首选。

原理流程

  1. 全局锁版:所有公开方法 synchronized 或 lock.lock()。
  2. ConcurrentHashMap 版:map 线程安全,但链表操作仍需锁;可用 ConcurrentLinkedDeque 但失去 O(1) 摘除已知节点能力。
  3. 分段锁版:按 key 哈希分片,每片一把锁,降低争用。

代码 / 示例

class ThreadSafeLRU {
    private final Object lock = new Object();
    private final Map<Integer, Integer> map = new java.util.LinkedHashMap<>(16, 0.75f, true) {
        @Override
        protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
            return size() > cap;
        }
    };
    private final int cap;
    ThreadSafeLRU(int cap) { this.cap = cap; }
    public int get(int k) { synchronized (lock) { Integer v = map.get(k); return v == null ? -1 : v; } }
    public void put(int k, int v) { synchronized (lock) { map.put(k, v); } }
}

常见误区

  • 误区:ConcurrentHashMap 就能让 LRU 线程安全;正解:map 线程安全不代表链表顺序操作线程安全,get/put 中的链表修改仍需同步。
  • 误区:读写锁适合 LRU;正解:get 命中会 moveToHead(写链表),读也升级为写,读写锁收益有限。

追问 / 延伸

  • Q:Caffeine 为什么快? A:基于 W-TinyLFU 命中率高,且用 CAS + 缓冲队列减少锁竞争,具体实现细节以官方文档为准。
  • Q:分布式 LRU 怎么做? A:本地缓存 + 远程缓存(Redis)二级,本地 LRU 限容,远程集中存储。

02.10.1-004 Redis 近似 LRU 与精确 LRU 的差异

频率 ★★★★ | 难度 进阶

一句话结论

Redis 为了节省内存不维护真实双向链表,而是每个对象带一个 24 位时钟,淘汰时随机采样 N 个 key 淘汰最久的;样本越大越接近精确 LRU,默认样本数可配置。

概念解释

  • 精确 LRU 需要双向链表,每个 key 额外存 prev/next 指针,内存开销大。
  • 近似 LRU:每个对象记录 lru 字段(时间戳秒级或毫秒级截断),淘汰时从候选集里挑 lru 最小的。
  • Redis 默认 maxmemory-samples=5,即每次随机抽 5 个淘汰 1 个;样本越大越精确但 CPU 越高。

原理流程

  1. 访问 key 时更新对象 lru 字段为当前时间。
  2. 内存超限时,按淘汰策略(allkeys-lru / volatile-lru)随机采样 N 个 key。
  3. 在采样集合中挑 lru 最小的淘汰,重复直到低于阈值。

代码 / 示例

精确 LRU:每次淘汰 O(1) 删尾,需双向链表
近似 LRU:采样 N 个,O(N) 挑最久,无链表开销
N=5   :CPU 低,命中率比精确 LRU 略低
N=100 :接近精确 LRU,CPU 更高

常见误区

  • 误区:Redis LRU 是精确 LRU;正解:是随机采样的近似 LRU,样本越大越准。
  • 误区:采样越少越好;正解:样本少会导致冷数据长期滞留,命中率下降。

追问 / 延伸

  • Q:Redis 还有哪些淘汰策略? A:noeviction、allkeys-lru、volatile-lru、allkeys-lfu、volatile-lfu、allkeys-random、volatile-ttl 等,具体以 Redis 版本为准。
  • Q:LFU 模式怎么实现? A:对象 lru 字段拆成计数与时间衰减,具体以 Redis 官方实现为准。

02.10.1-005 FIFO / LRU / LFU / ARC 怎么选

频率 ★★★★ | 难度 进阶

一句话结论

FIFO 最简单但忽略访问频率;LRU 按时间淘汰,适合热点局部性明显的场景;LFU 按频率淘汰,适合长期热点但怕冷数据残留;ARC 自适应两者,在 LRU/LFU 间动态平衡分区。

概念解释

  • FIFO:先进先出,不区分访问频率,实现最简单(队列即可)。
  • LRU:最近最少使用,抗批量访问抖动能力一般。
  • LFU:最不经常使用,频率计数,热点数据长期留存,但历史高频数据会污染。
  • ARC:自适应替换缓存,维护 L1(近期)和 L2(频繁)两个分区,动态调整大小。

原理流程

  1. 访问模式均匀随机:四者命中率差不多,选 FIFO。
  2. 访问有时间局部性(最近访问的还会访问):LRU 最优。
  3. 访问有频率局部性(热点长期访问):LFU 最优。
  4. 访问模式在两种间切换不确定:ARC 自适应。

代码 / 图示

策略     时间开销   频率开销   内存开销   抗抖动
FIFO     O(1)      不看       O(n)       差
LRU      O(1)      不看       O(n)       中
LFU      O(1)      维护       O(n)       好但冷数据滞留
ARC      O(1)      维护       O(2n)      自适应

常见误区

  • 误区:LFU 一定比 LRU 好;正解:LFU 对突发批量访问不敏感(频率增长慢),但冷数据一旦被高频访问过就长期滞留。
  • 误区:ARC 就是 LRU+LFU;正解:ARC 是自适应分区,不是简单叠加。

追问 / 延伸

  • Q:Java 里用什么? A:LinkedHashMap 可实现 LRU;Caffeine 用 W-TinyLFU,命中率接近 ARC。
  • Q:缓存容量很大选什么? A:容量大时 LRU 通常够用,容量小且访问模式不均时考虑 LFU/ARC。

02.10.1-006 LFU 中最小频率为什么不会错删

频率 ★★★ | 难度 高级

一句话结论

minFreq 只在两个时机变化:新插入节点(freq=1)时设为 1;某频率桶删空且该桶等于 minFreq 时推进到 f+1;由于所有被访问节点 freq 都递增,minFreq 永远指向当前最久未被访问的频率。

概念解释

  • 新节点 freq=1,所以 minFreq 一定 <= 1 时重置为 1。
  • bump 节点时,旧桶非空则 minFreq 不变;旧桶空且是 minFreq 才推进。
  • 淘汰只从 minFreq 桶尾摘,因为同频率内桶尾是最久未访问的。

原理流程

  1. 假设 minFreq=2,此时没有任何 freq=1 的节点存在。
  2. 访问某 freq=2 节点,它 bump 到 freq=3,若 freq=2 桶变空,则 minFreq=3。
  3. 新插入节点 freq=1,minFreq 立即重置为 1。

代码 / 图示

节点 freq 变化:1 -> 2 -> 3 -> ...
minFreq 始终是当前存在的最小 freq
新插入:minFreq = 1
旧桶删空且是 minFreq:minFreq++

常见误区

  • 误区:每次 bump 都重新扫描所有桶找 min;正解:增量维护 minFreq,O(1)。
  • 误区:淘汰时从全局 freq 最小且时间最久摘;正解:同频率桶内本身按时间排,桶尾即最久。

追问 / 延伸

  • Q:minFreq 会不会超过实际最大 freq? A:不会,因为只有某桶删空才推进,且推进到 f+1 时该桶必然存在(刚 bump 过来的节点)。
  • Q:频率计数需要衰减吗? A:基础 LFU 不衰减,长期运行会导致历史高频数据污染;生产版有衰减机制。

02.10.1-007 缓存穿透、雪崩、击穿与淘汰策略的关系

频率 ★★★★★ | 难度 基础

一句话结论

穿透是查不存在的 key(缓存层拦不住,打到 DB);雪崩是大量 key 同时过期(DB 瞬时压力);击穿是单个热点 key 过期瞬间大量请求打到 DB;淘汰策略本身不解决这三个问题,但过期时间设计和空值缓存可缓解。

概念解释

  • 缓存穿透:key 不存在,每次都查 DB,需布隆过滤器或缓存空值。
  • 缓存雪崩:大量 key 同时 TTL 到期,需过期时间加随机抖动。
  • 缓存击穿:热点 key 到期,需互斥锁或逻辑过期。
  • 淘汰策略(LRU/LFU)解决的是容量满时淘汰谁,不解决过期问题。

原理流程

  1. 穿透:在缓存前加布隆过滤器,不存在的 key 直接拒绝。
  2. 雪崩:TTL 加随机偏移(如 base ± 30s),避免同时失效。
  3. 击穿:热点 key 用互斥锁重建,或逻辑过期(异步更新)。

代码 / 图示

穿透:布隆过滤器 + 缓存空值(短 TTL)
雪崩:TTL 加随机抖动
击穿:互斥锁 setnx + 热点 key 不过期
淘汰:容量满时 LRU/LFU 选谁出

常见误区

  • 误区:用 LRU 就能防穿透;正解:LRU 只在容量满时淘汰,不存在的 key 根本不会被缓存(或被缓存为空值)。
  • 误区:淘汰策略和过期策略是一回事;正解:淘汰是容量触发,过期是 TTL 触发,两者独立。

追问 / 延伸

  • Q:空值缓存 TTL 设多长? A:一般 30s~5min,太短频繁回源,太长影响真实数据更新。
  • Q:布隆过滤器误判率? A:误判率随位数组大小和哈希函数数变化,不存在误判为存在,存在不会误判为不存在。

02.10.1-008 LRU 热点数据抖动问题如何缓解

频率 ★★★ | 难度 高级

一句话结论

LRU 对突发批量访问敏感:一次批量扫描会把热点挤到尾部;缓解方案是 LRU-K(记录最近 K 次访问)、2Q(双队列)、或直接换 LFU/W-TinyLFU。

概念解释

  • LRU-K:记录每个 key 最近 K 次访问时间,只有当 K 次访问都发生在近期才认为是热点。
  • 2Q:用两个队列,新进 key 先进 A1(FIFO),二次访问才进 Am(LRU),过滤一次性访问。
  • W-TinyLFU:用频率计数器 + 窗口段,新数据先进窗口,达到频率门槛才进主缓存。

原理流程

  1. 批量扫描一次性访问大量 key,LRU 把它们都放头部,真热点被挤到尾部淘汰。
  2. LRU-2 只看最近 2 次访问间隔,一次性访问不进入主 LRU。
  3. W-TinyLFU 用 Count-Min Sketch 估计频率,频率高的才进主缓存。

代码 / 图示

问题:批量冷数据访问 -> 真热点被挤出去
LRU-2:最近2次访问都近 -> 热点
2Q:先 FIFO,二次访问才进 LRU
W-TinyLFU:频率计数 + 窗口

常见误区

  • 误区:LRU 抗抖动;正解:LRU 只看最近一次,批量冷访问会污染。
  • 误区:增大容量就能解决;正解:容量再大,批量扫描也会占满缓冲区。

追问 / 延伸

  • Q:Java 生产用什么? A:Caffeine 的 W-TinyLFU,命中率在大多数场景优于传统 LRU。
  • Q:LRU-K 的 K 怎么选? A:K=2 是常见选择,K 越大对短期突发越不敏感但反应越慢。

待整理清单

  • [ ] Caffeine W-TinyLFU 详细实现原理
  • [ ] 分布式缓存一致性哈希与 LRU 结合
  • [ ] LFU 频率衰减机制