深入理解 LRU：从课本上的知识到高并发缓存应用的完整闭环

前言LRU 大概是每一个计算机专业学生在操作系统课上都见过的名词。课本上的版本很简单内存不够了把最近很久没用到的那个页面换出去画一张双向链表标几个指针考试就过去了。但真正工作之后会发现这个被简化到一行字的策略几乎是整个后端缓存体系的基石——本地缓存用它、Redis 用它、MySQL 的 Buffer Pool 用它、浏览器用它、甚至写的高并发系统里热点数据放哪、淘汰谁背后都是它。课本上的 LRU 和生产环境里的 LRU差的不是一点半点。这篇文章就把这件事深入讲解一下一、为什么需要 LRU缓存的本质矛盾要理解 LRU先得理解它解决的那个问题本身。缓存的存在是因为快的存储贵、容量小慢的存储便宜、容量大这个亘古不变的矛盾。CPU 寄存器比 L1 缓存快、L1 比 L2 快、L2 比内存快、内存比 SSD 快、SSD 又比机械盘快一个数量级。我们把热点数据放在快的那一层是为了让绝大多数请求不用每次都砸到慢存储上。但快存储的容量是硬约束——内存就那么大、Redis 实例给的配额就那么多缓存一旦写满就必须回答一个问题当新数据要进来时把谁踢出去这就是缓存淘汰算法要解决的事。理想的策略是把未来再也不会被访问的数据踢出去但你没法预知未来只能用过去去推断未来。最朴素的想法是按进入顺序踢最早的这是 FIFO按最久没被碰过的踢就是 LRULeast Recently Used最近最少使用按访问次数最少的踢是 LFU。LRU 背后有一个非常强的假设叫做局部性原理如果一个数据刚刚被访问过那么它接下来被访问的概率也比较大反过来如果一个数据已经很久没被碰过那它短期内大概也不会被碰。这个假设在绝大多数真实业务里都成立这也是 LRU 能统治缓存淘汰领域几十年的根本原因。举个生活里的例子就好懂了。你的书桌就那么大缓存容量有限你每天要用的书就摊在桌面上不用的塞到书架里慢存储。当你新买了一本书、桌面已经放不下了你会本能地把那本已经三个月没翻过的塞回书架——你不会去数哪本书一共翻过几次那是 LFU也不会机械地把最早上桌的塞回去那是 FIFO。这种凭最近用过没用过做判断的直觉就是 LRU。二、LRU 的核心数据结构哈希表 双向链表LRU 要做到一件事get 和 put 都是 O(1)。这个时间复杂度要求直接决定了它的数据结构选型。先想清楚 LRU 每一次操作要做什么。当访问一个 key 的时候我们要做两件事第一找到这个 key 对应的 value第二把这个 key 标记为最近用过也就是把它挪到最近使用的那一端。当 put 一个新 key 的时候如果缓存没满就插到最近使用端如果满了就把最久没用的那一端踢掉。问题就来了——光用链表行不行链表能在 O(1) 时间把头尾增删但根据 key 找到节点这一步是 O(n)每次都要遍历。光用哈希表行不行哈希表查找是 O(1)但它是无序的你没法在 O(1) 时间知道谁是最久没用的。所以标准答案是用一个哈希表HashMap做 key 到链表节点的映射再用一个双向链表维护最近使用 → 最久未使用的顺序。哈希表负责快速找到节点双向链表负责快速调整顺序和淘汰队尾。访问一个 key 时先从哈希表拿到节点引用再把这个节点从链表原位置摘掉、塞到链表头部put 时新节点直接塞到头部、同时写进哈希表如果超过容量就把链表尾部节点摘掉、同时从哈希表删掉。两个数据结构配合所有操作都是 O(1)。为什么是双向链表而不是单链表因为当我们要把一个中间节点摘下来时单链表要 O(n) 才能找到它的前驱双向链表每个节点都直接保存 prev 指针摘除是 O(1)。为什么要带头尾哨兵因为链表的头和尾在空表、只有一个节点、满表淘汰这些边界情况下逻辑会写一堆 null 判断加两个不存数据的哨兵节点可以让所有插入删除操作统一处理少写一大堆 if。这里有一个特别容易被面试官抓的细节淘汰尾节点的时候必须把它从哈希表里也删掉。因为链表的 key 和哈希表的 key 是两套结构删了一个忘了删另一个下次 get 一个已经被淘汰的 key 就会拿到一个幽灵节点。这个细节写代码时一不留神就漏也是考察候选人是不是真的自己手写过一遍的信号。三、站在 JDK 的肩膀上LinkedHashMap 已经帮你写好了如果你真的去翻 Java 的源码会发现上面这套东西根本不用自己写——java.util.LinkedHashMap 天生就是一个 LRU 容器。它的内部维护了一个双向链表记录所有 entry 的访问顺序或者插入顺序取决于构造参数并且留了一个钩子方法 removeEldestEntry默认返回 false意思是永远不淘汰。你只要继承它、重写这个方法让它在 size 超过容量时返回 trueJDK 就会自动帮你淘汰最老的 entry这也是为什么面试时如果被问LRU 怎么实现只写一个手写版本还不够——你最好能补一句工程上 Java 直接用 LinkedHashMapaccessOrder 设为 true重写 removeEldestEntry 就行然后再点一句但它不是线程安全的多线程环境下要加锁或者用 Caffeine/Guava。能说出这一句基本就说明你不是在背题而是真的在项目里用过。四、朴素 LRU 的缺陷为什么工业界很少真的直接用它手写一个 LRU 不难但真把它用到生产环境会发现朴素 LRU 有几个绕不开的坑这也是面试深挖时的高频考点。第一个坑叫缓存污染Cache Pollution。设想这样一个场景你本来缓存里存的都是热点用户数据结果某次批量任务一次性把几十万条冷数据扫进了缓存。按照朴素 LRU 的规则这些冷数据会把整个链表占满真正的热点数据反而被挤到队尾淘汰掉了。等批量任务跑完正常流量回来缓存里全是刚才扫过的冷数据命中率断崖式下跌数据库瞬间被打穿。这就像你为了临时搬一次家把书桌上所有常用的书都塞进了书架等搬完家想找一支笔都找不到。第二个坑叫缓存抖动。如果业务数据有明显的周期性——比如早高峰是 A 类数据热、晚高峰是 B 类数据热——朴素 LRU 会在每一次热点切换时表现很差因为 A 类数据还在链表头部时 B 类已经开始访问等 B 类挤上来、A 类被淘汰过两个小时流量又切回 A 类命中率又掉一次。第三个坑是对访问频率完全不敏感。一个 key 哪怕历史上被访问过一万次只要最近一次访问是在队尾照样被淘汰反过来一个 key 哪怕这辈子就被访问过一次只要它刚被访问就稳坐头部。在访问分布明显偏斜二八定律的业务里这种只看最近一次、不看历史频次的策略其实是浪费缓存容量。针对这些缺陷工业界演化出了一大批变体。最有名的几个LRU-K不再只看最近一次而是看最近第 K 次比如 LRU-2 会记住每个 key 最近两次访问的时间只有被访问过两次以上的数据才允许进入缓存主链表单次扫描的冷数据在幽灵队列里待着进不去主缓存这就直接解决了批量冷数据污染问题2Q 算法思路类似把缓存分为 FIFO 入口队列和 LRU 主队列进过两次才晋级ARC则更激进动态在 LRU 和 LFU 之间调整权重自己根据流量特征决定偏向。这些变体不需要在面试里全背但你至少要能说出朴素 LRU 有缓存污染问题、LRU-K 是怎么解决的这就比绝大多数候选人高一个段位。五、项目里 LRU 到底用在哪从本地缓存到 Redis、MySQL空谈算法没有意义真正能写进简历、能在面试里讲出故事的是 LRU 在你项目里的落点。下面这几个场景都是后端项目里真实会遇到的。1. 本地缓存Caffeine / Guava CacheJava 后端最常用的本地缓存不是你自己写的 LRU而是Caffeine以及老一代的 Guava Cache。Caffeine 底层用的是 W-TinyLFU 算法——本质上是一个结合了 LFU 频率统计和 LRU 窗口的改进版 LRU但对外暴露的配置非常简单LoadingCacheString, UserInfo userCache Caffeine.newBuilder() .maximumSize(10_000) // 最大容量超过触发 LRU 淘汰 .expireAfterWrite(Duration.ofMinutes(10)) // 写后过期 .recordStats() // 开启命中率统计 .build(key - userMapper.selectById(key)); // 未命中时回源maximumSize 这一行就是在告诉底层这个缓存最多放 1 万条满了你自己按淘汰策略踢人。做高并发选课系统的时候我们经常把课程基本信息这种读多写少、变化不频繁的数据放在本地缓存里——第一级挡掉 80% 的重复读让请求根本不用走到 Redis。2. Redis 的淘汰策略你以为的 LRU 其实是近似 LRURedis 是后端项目里用得最多的分布式缓存它的淘汰策略里有两条和 LRU 直接相关allkeys-lru所有 key 里按 LRU 淘汰和 volatile-lru只在设了过期时间的 key 里按 LRU 淘汰。但这里有一个几乎一定会被追问的细节Redis 并不是严格实现了上面那套双向链表 LRU而是用了一个近似 LRU。为什么因为 Redis 是单线程的如果真的给每个 key 维护一条双向链表每一次访问都要改指针、每一次淘汰都要遍历CPU 会被这个维护动作吃掉一大块。Redis 的做法很取巧每个 key 只存一个 24 位的最近访问时间戳淘汰时不是从真正的队尾踢而是随机采样 N 个 key默认 5 个从这 N 个里挑最久没用的那个踢掉。采样数量越大可以通过 maxmemory-samples 配置成 10 或者 100近似 LRU 就越接近真实 LRU但 CPU 开销也越大。Redis 之所以这么做是因为在百万、千万 key 量级的实例上严格 LRU 的维护成本高到不可接受而随机采样在数学上已经能拿到非常接近真实 LRU 的命中率。3. MySQL Buffer Pool课本里的 LRU 真正的家如果说 Redis 是把 LRU 用在了 KV 缓存里那MySQL InnoDB 的 Buffer Pool就是把 LRU 用在了数据库页缓存里而且它的改进版 LRU 是教科书级别的。InnoDB 的 Buffer Pool 默认大小可能是几十 G磁盘上的数据页加载到内存里才能被访问。它的 LRU 链表被刻意拆成了两段young 区新生代约占 5/8和 old 区老生代约占 3/8。一个新读到的数据页先插入到 old 区的头部只有当这个页在 old 区停留超过一定时间innodb_old_blocks_time默认 1 秒且再次被访问才会被晋升到 young 区的头部。为什么要这么设计就是为了对付前面讲过的缓存污染。想象一下一个 DBA 跑了一次全表扫描按朴素 LRU 的逻辑这张表所有的页会瞬间把 Buffer Pool 占满把真正的热点页全部挤出去整库性能抖上好几分钟。InnoDB 把新页先丢进 old 区、并且要求停留 1 秒后还被访问才算数全表扫描这种一次性扫过的页根本没有机会晋升到 young 区扫完就被淘汰掉了对热点页几乎没影响。这就是上一节说的 LRU-2 思想在数据库里的真实落地。面试时如果你能把 Buffer Pool 这个 young/old 分区讲出来基本就把 LRU 从算法题拉高到了数据库内核的层级。结语LRU 这个东西课本上看起来就是一张画了几个箭头的链表但真往深了挖它是串起本地缓存、分布式缓存、数据库页缓存、操作系统内存置换一整条体系的主线。面试时能从怎么手写一路讲到为什么工业界不直接用朴素版本、Redis 为什么用近似 LRU、MySQL Buffer Pool 为什么要分 young 和 old、你的项目里 Caffeine 怎么配这个知识点就从一道算法题变成了你对整个缓存体系理解的展示窗口。下次再被问到 LRU别只说哈希表加双向链表——那句话只能让你过第一关后面这几层才是真正拉开差距的地方。