1. 从一次缓存抖动说起LRU算法到底解决什么问题LRU算法这三个字绝大多数人是先在面试题里见到的然后才在真实系统里踩到它的坑。我第一次认真对待它不是因为刷题而是因为一个线上接口的响应时间从 20ms 飙到 900ms排查了半天发现是本地缓存的命中率从 92% 掉到了 41%而罪魁祸首就是淘汰策略写得太随意。那次之后我才明白缓存这个东西存进去容易决定该扔掉谁才是真正的技术活。LRU 的全称是 Least Recently Used翻译过来叫最近最少使用但这个名字其实有点误导人。它真正表达的规则是如果一个数据最近被访问过那么它将来被访问的概率也更高反过来最久没被碰过的那个就先淘汰它。这个假设听起来简单却是过去几十年里被验证得最充分的一条经验规律之一从操作系统的页面置换到 CPU 缓存的替换再到 Redis、Guava、Caffeine 这些中间件和库到处都有它的身影。这篇文章适合三类人看。第一类是正在准备面试的同学LRU 几乎是手写题的常客但面试官想看的不是你能不能背出代码而是你懂不懂为什么这么设计第二类是写了几年业务代码的工程师你大概率用过LinkedHashMap或者某个缓存库但可能没想过它们在并发和容量上的取舍第三类是做系统设计的人你需要知道严格 LRU 在真实场景里为什么经常被魔改以及魔改的方向是什么。我把内容分成五块先讲清楚 LRU 要解决的本质问题再拆解它为什么必须用哈希表加双向链表这套组合然后给出可以直接抄的完整实现接着聊真实系统里那些不那么 LRU的变体最后是我这些年攒下来的排查经验和避坑清单。整个过程我会尽量把为什么讲透因为参数和代码都能查唯独判断力查不到。2. LRU算法的核心原理为什么必须是哈希表加双向链表2.1 先想清楚如果没有淘汰策略会怎样缓存本质上是拿空间换时间。你把热数据放在内存里下次要用直接取省掉了磁盘 IO 或者远程调用。但内存是有限的不可能无限往里塞数据所以当缓存满了、又来了新数据的时候就必须做一个决定是拒绝新数据还是腾出位置给它。如果选择腾位置那问题就变成了腾谁的位置。最粗暴的做法是随机淘汰也叫 Random Replacement。它的优点是实现简单、开销极小在访问模式完全随机、数据热度均匀的场景下表现其实不差CPU 的某些缓存层次就用过类似思路。但绝大多数业务场景的数据访问是严重倾斜的可能 20% 的键承担了 80% 的访问量。这种分布下随机淘汰会经常把热门数据误伤掉命中率崩塌。另一种极端是 FIFO先进先出谁先来谁先走。它的逻辑是活得久就该退休但缓存里最不该淘汰的恰恰往往是那些活得很久、一直被反复访问的老数据比如配置项、字典表、热门商品的库存信息。FIFO 会把这些常青树无情踢掉命中率同样难看。还有 LFULeast Frequently Used按访问次数淘汰谁被访问得少谁走。它在热度分布稳定的场景下命中率很高但有两个软肋一是新来的数据天然吃亏可能刚进来就被淘汰这叫缓存污染二是计数需要维护和衰减老热点过气之后计数还高高挂着占着位置不走这叫历史包袱。LRU 的定位就在这几者之间。它不统计长期频率只看最近这个时间窗口既能让突然爆火的新数据快速上位又不会像 FIFO 那样把常青树误杀。工程上它是一个平衡得非常好的选择这也是它成为默认淘汰策略的原因。2.2 用单链表实现 LRU问题出在哪理解了规则接下来是数据结构。最直觉的实现是一条链表表头放最近访问的表尾放最久没用的。每次访问一个节点就把它从当前位置摘下来挂到表头。淘汰时直接删表尾。这个思路逻辑上完全正确但性能上有硬伤。查找一个节点是否在链表里需要从头遍历时间复杂度是 O(n)。缓存的核心价值就是快如果每次get都要扫一遍链表缓存反而成了性能瓶颈这就本末倒置了。有人会说那我用数组加下标映射呢数组的问题是移动元素代价高。在头部插入一个元素后面所有元素都要往后挪同样是 O(n)。用单链表插入删除是 O(1)但你得先找到那个节点又回到 O(n) 了。这就是经典的两难定位快的数据结构数组、哈希表改顺序慢改顺序快的数据结构链表定位慢。2.3 哈希表加双向链表各取所长破局的办法是把两种结构拼起来让它们各干各擅长的事。哈希表负责定位键到节点的映射get一个键时 O(1) 就能拿到节点指针不需要遍历。双向链表负责维护顺序最近访问的挂头部最久未用的沉在尾部淘汰时 O(1) 摘掉尾节点。关键在于为什么必须是双向链表。你想想get的流程拿到节点后要把它移到头部这意味着要先把它从原来的位置删掉。删除一个节点需要知道它的前驱单链表只能从头遍历找前驱又变成 O(n)。双向链表每个节点都存着prev指针删除就是改两个指针的事O(1) 搞定。所以这套组合的最终复杂度是getO(1)putO(1)淘汰 O(1)。这就是 LRU 的精髓也是面试官真正想听到的答案。很多人能写出代码但被问到为什么不用单链表就卡壳了差别就在这里。2.4 哨兵节点这个细节值得单独拎出来讲写双向链表最容易翻车的地方是边界处理。头部插入、尾部删除当链表为空或者只有一个节点时head、tail的指针指向会变得很绕null判断满天飞代码里全是if一不留神就出现空指针。工程上有个非常通用的技巧加两个虚拟的哨兵节点一个假头dummyHead一个假尾dummyTail它们不存真实数据只是为了让链表永远非空。这样一来任何真实节点都有前驱和后继插入和删除的逻辑完全统一一行null检查都不用写。代价是多了两个节点对象的内存几乎可以忽略。收益是代码量减少三分之一而且几乎不可能出边界 bug。我在实际项目里写任何链表结构都习惯这么干这是个一劳永逸的习惯。3. 手写一个能上生产的LRU完整实现与逐行拆解3.1 节点设计与整体骨架先定义节点。每个节点需要存三样东西键、值、前后指针。class Node { int key; int value; Node prev; Node next; Node(int key, int value) { this.key key; this.value value; } }有个细节很多人会漏节点里必须存 key。为什么因为在淘汰尾节点的时候你需要拿到它的 key 去哈希表里把对应的映射删掉。如果节点只存 value你就不知道要删哈希表里的哪个条目缓存和链表就会不同步出现链表里没了的键哈希表还能查到这种脏数据。这个坑我在真实代码 review 里见过不止一次。LRU 的主类需要维护四个东西哈希表、头哨兵、尾哨兵、当前容量和最大容量。class LRUCache { private final MapInteger, Node map; private final Node head; // 哨兵头 private final Node tail; // 哨兵尾 private final int capacity; private int size; public LRUCache(int capacity) { this.capacity capacity; this.size 0; this.map new HashMap(); this.head new Node(0, 0); this.tail new Node(0, 0); head.next tail; tail.prev head; } }构造函数里最容易被忽略的是head.next tail和tail.prev head这两行。没有它们空链表状态下head.next是null第一次插入就会空指针。这两行保证了链表在任何时刻都是首尾相连的闭环结构。3.2 三个私有方法撑起全部逻辑真正干活的其实只有三个方法把节点加到头部、把节点从链表摘除、把节点移到头部。private void addToHead(Node node) { node.prev head; node.next head.next; head.next.prev node; head.next node; } private void removeNode(Node node) { node.prev.next node.next; node.next.prev node.prev; } private void moveToHead(Node node) { removeNode(node); addToHead(node); }这里指针的操作顺序有讲究。addToHead里必须先处理node.next和head.next.prev最后再改head.next顺序反了就会把原本head.next的引用覆盖掉导致后面的节点丢失。我的习惯是画个四步草图新节点的两个指针、原头节点的后继指针、头节点的后继指针按这个顺序写基本不会错。removeNode之所以能这么简洁正是因为有了哨兵节点。如果node是真实头节点它的prev就是哨兵head直接改指针没问题如果它是真实尾节点next就是哨兵tail同样没问题。要是没有哨兵这里就得加一堆if (node head)的判断。3.3 get 和 put把复杂度锁死在 O(1)public int get(int key) { Node node map.get(key); if (node null) { return -1; } moveToHead(node); return node.value; } public void put(int key, int value) { Node node map.get(key); if (node ! null) { node.value value; moveToHead(node); return; } if (size capacity) { Node last tail.prev; removeNode(last); map.remove(last.key); size--; } Node newNode new Node(key, value); map.put(key, newNode); addToHead(newNode); size; }get的逻辑很直白查得到就把它提到头部表示刚用过查不到返回 -1。这一步提升操作就是 LRU 的灵魂它让访问顺序实时更新。put分两种情况。键已存在那就更新值并提到头部注意容量不变这时候不需要淘汰。键不存在先看是否满了满了就淘汰尾节点——tail.prev就是最久未用的那个。淘汰时一定要先map.remove(last.key)再把它从链表删掉两边的数据必须同步。注意淘汰的清理顺序建议先删哈希表再删链表或者至少保证两步都执行。曾经见过有人只在链表里删了节点、忘了删 map结果内存越跑越大最后 OOM排查了两个小时才发现是这行漏了。3.4 容量到底设多大一个可以算的公式代码写完了另一个更实际的问题是容量设多少。设太小命中率上不去缓存形同虚设设太大内存吃紧还可能有 GC 压力。这里其实有个能粗略估算的公式所需缓存条目数 ≈ 峰值 QPS × 平均访问延迟秒× 安全系数举个例子某个查询接口峰值 QPS 是 5000每次查询平均耗时 20ms也就是 0.02 秒。那么在这 0.02 秒里会有 5000 × 0.02 100 个请求同时在途。也就是说只要缓存能覆盖住这 100 条数据就足以应付瞬时并发。考虑到数据分布、过期时间和突发流量安全系数一般取 3 到 5那容量大概 300 到 500 条就比较合适。再结合单条数据的大小换算成内存。假设每条记录平均 2KB500 条就是 1MB 左右这个量级非常轻。很多团队一上来就设十万条结果内存占了几百 MB命中率却只比五千条高几个百分点性价比极低。我的经验是先用小容量跑一段时间看监控里的命中率曲线再逐步往上加。命中率从 60% 提到 85% 可能只需要很小的容量但从 95% 提到 97% 可能要翻好几倍的内存边际收益递减非常明显。容量档位内存占用典型命中率适用场景100 条以内几百 KB60%~75%配置项、字典表等超热数据500~2000 条1~5 MB85%~93%单机接口缓存1 万条以上20 MB 起93%~97%需要配合过期和分片策略4. 从单机到分布式真实系统里的LRU变体4.1 严格的 LRU 为什么在大规模场景下会被放弃单机、小容量下严格 LRU 表现很好。但到了 Redis 这种动辄几 GB 内存、几千万键的场景严格 LRU 有两个绕不过去的问题。第一是内存开销。要实现严格 LRU每个键都得维护前后指针或者至少维护一个精确的访问时间戳。几千万个键光这些额外字段就得吃掉可观的额外内存。Redis 官方文档里就提到过严格 LRU 需要为每个对象额外维护链表结构成本不划算。第二是淘汰时的性能。严格淘汰需要精确定位最久未用的那个键如果每次淘汰都做精确排序或维护全局链表开销不小。于是 Redis 选择了近似 LRU。它给每个键记录一个 24 位的最后访问时间戳淘汰的时候不会去精确找最老的而是随机采样一批键默认采样 5 个从中挑出最久没用的那个淘汰。采样数可以通过maxmemory-samples调整采样越多越接近严格 LRU但 CPU 开销也越高。这个思路很值得学习在精度和成本之间找一个可接受的平衡点而不是死磕理论最优。实测下来采样 5 个键的近似 LRU命中率已经和严格 LRU 非常接近了但实现的复杂度低了一个数量级。4.2 MySQL Buffer Pool 里的改良 LRUMySQL 的 InnoDB 缓冲池也用 LRU 管理数据页但它的做法更有意思。如果直接上标准 LRU会有个致命问题全表扫描或者预读操作会把大量一次性使用的页塞进缓存把真正热的数据挤出去这叫缓冲池污染。InnoDB 的解法是把 LRU 链表切成两段新生代young占 5/8老生代old占 3/8。新读进来的页不是直接放到链表头部而是先插到老生代的头部。只有当这个页在老生代里待够一定时间后再次被访问它才有资格晋升到新生代。这个待够时间由innodb_old_blocks_time控制默认 1000 毫秒。这一招很巧妙。全表扫描读进来的页通常用完就不再访问了它们在老生代里很快就会被淘汰不会污染热数据。而真正被反复访问的页撑过 1 秒后晋升新生代得到保护。这其实已经不是纯 LRU 了而是 LRU 加了一层准入判断。我在做缓存设计时经常借鉴这个思路别让所有新数据都无条件享受最高优先级给它们一个考察期。4.3 LRU-K、2Q、LFU什么时候该换算法严格 LRU 有个众所周知的弱点叫缓存污染一次批量操作或者一个爬虫扫了一遍全站所有冷数据都被塞进来把热数据冲得干干净净。为了对付这个问题学术界和工业界搞出了不少变体。LRU-K记录每个数据最近 K 次访问的时间用第 K 次访问的时间来排序淘汰。K 越大越能过滤掉一次性访问但实现复杂度和内存开销也上去了。常见的是 LRU-2。2QTwo Queues用两个队列一个 FIFO 队列做准入考察一个 LRU 队列存真正热门的数据。新数据先进 FIFO被再次访问才进 LRU。结构简单效果不错。LFU按访问频率淘汰。适合热度分布长期稳定的场景但需要处理计数衰减否则老热点会一直霸占位置。W-TinyLFU这是 Caffeine 缓存采用的核心算法用 Count-Min Sketch 做频率统计配合窗口 LRU兼顾了频率和新鲜度被公认为当前综合表现最好的淘汰策略之一。选哪个核心看你的数据访问模式。如果热点变化快、有明显的新鲜内容LRU 系更合适如果热点稳定、就是那批数据反复被读LFU 系命中率更高。拿不准的时候先用 LRU然后根据监控里的命中率和淘汰分布再决定要不要升级。4.4 操作系统页面置换LRU 的理论与近似实现LRU 最早的大规模应用其实是操作系统的虚拟内存管理。物理内存有限进程访问的页面远多于物理页框操作系统必须决定把哪个页面换出到磁盘。LRU 在理论上是最优近似之一真正最优的是 Belady 算法但它需要预知未来无法实现。问题是硬件层面根本无法高效实现严格 LRU。每次内存访问都要更新链表或者时间戳代价太高。于是实际系统都用近似方案。经典的是时钟算法Clock给每个页一个引用位页面被访问时硬件自动置 1。淘汰时像时钟指针一样扫描遇到引用位是 1 的就清成 0 并跳过遇到 0 的就淘汰。这个方法把精确的时间顺序换成了粗略的最近是否被访问过开销小得多效果却不差。从严格 LRU 到近似 LRU从单链表到时钟算法你会发现整个计算机系统都在做同一件事用一点点精度损失换回巨大的性能收益。理解了这个思路你对缓存设计的理解就上了一个台阶。5. 常见问题与排查实录5.1 命中率突然下跌我的排查顺序命中率是缓存健康度的第一指标。它掉下来的时候别急着调大容量先按这个顺序查。第一步看流量模式是否变了。是不是有大促、爬虫、定时任务在跑我之前遇到过一次命中率跳水查了半天代码最后发现是运营配了一个全量刷新的定时任务每 10 分钟把所有缓存清一次等于把缓存当摆设。这种问题看监控的流量曲线一眼就能发现。第二步看淘汰频率。如果 QPS 没变但淘汰数暴涨说明容量不够了或者大量数据集中过期。把所有键设同一个过期时间是个经典错误会导致缓存雪崩它们在某一刻同时失效然后全部打到数据库。解决办法是给过期时间加个随机抖动比如基础时间加 0 到 10% 的随机值。第三步看键的设计。如果键里带了时间戳、用户 ID、随机数那你其实是在源源不断地写入新键缓存命中率永远上不去。我见过把毫秒时间戳拼进 key 的代码等于每次都 miss这个必须得改。现象可能原因排查动作命中率缓慢下降热点数据被挤走检查淘汰数、容量配置命中率断崖式下跌批量失效、全量刷新查定时任务、过期时间设置命中率一直很低key 设计不合理抽样看 key 的构成内存持续增长淘汰没生效、map 没同步删检查淘汰逻辑和 GC 日志5.2 并发场景下那些年我踩过的坑单线程的 LRU 好写一旦上了并发坑就多了。第一个坑是线程安全。HashMap在并发下扩容会出问题轻则数据错乱重则死循环把 CPU 打满。多线程环境一定要用ConcurrentHashMap但要注意ConcurrentHashMap只保证单次操作原子get 加 moveToHead 这两步合起来并不原子。两个线程同时操作同一个节点指针很容易乱掉。第二个坑是锁的粒度。最省事的做法是给整个缓存加一把大锁用synchronized或者ReentrantLock。简单可靠但高并发下会成为瓶颈。想优化就得做分段锁把缓存拆成 N 个独立的小 LRU按 key 的哈希取模决定进哪个段。这样锁竞争降低到原来的 N 分之一代价是容量统计和整体淘汰顺序不再全局精确。这就是典型的工程折中。第三个坑是淘汰和更新的竞态。一个线程正在淘汰尾节点另一个线程刚好在get这个键如果顺序不对可能读到已经被删的节点或者把一个已删除的节点重新挂回链表。解决办法是淘汰和插入操作放在同一个临界区里别拆开。// 分段锁的简化思路 private final LRUCache[] segments; private static final int SEGMENT_COUNT 16; private LRUCache segmentFor(int key) { int hash (key ^ (key 16)) 0x7fffffff; return segments[hash % SEGMENT_COUNT]; } public int get(int key) { return segmentFor(key).get(key); }实际项目里如果不想自己写直接用 Guava 的CacheBuilder或者 Caffeine。它们的并发处理、过期策略、统计信息都做得非常完善自己手写反而容易出问题。手写 LRU 的价值在于理解原理生产环境优先用成熟的库。提示Caffeine 默认用的是 W-TinyLFU在高并发、大容量场景下命中率普遍优于手写 LRU而且有完备的命中率统计方便你做监控。选型时值得优先考虑。5.3 高频追问速查表面试和代码 review 里关于 LRU 有几个反复出现的问题我把答案整理成表方便你快速过一遍。问题核心答案为什么复杂度是 O(1)哈希表 O(1) 定位双向链表 O(1) 改指针为什么不用单链表删除节点需要前驱单链表找前驱是 O(n)为什么节点要存 key淘汰时要同步删除哈希表映射哨兵节点有什么用消除边界判断统一插入删除逻辑LRU 和 LFU 区别LRU 看最近访问时间LFU 看访问频次严格 LRU 的问题内存开销大、易被批量操作污染、难以全局实现怎么防止缓存雪崩过期时间加随机抖动怎么防止缓存穿透空值缓存、布隆过滤器并发怎么写大锁简单、分段锁性能好、优先用成熟库关于缓存穿透稍微展开说一句。它指的是查询一个数据库里也不存在的键缓存永远 miss每次都打到数据库。LRU 本身不解决这个问题但连在一起想很有必要。常见做法是查不到也缓存一个空值并设短过期时间或者在缓存前面加一层布隆过滤器先判断键可能存在再往下走。再说一个我个人的观察LRU 的代码谁都能背但真到了线上决定成败的从来不是算法本身而是容量估算、过期策略、并发处理和监控指标这几件事。我见过算法写得完美但容量设成 10 的缓存也见过用的就是近似 LRU 但命中率常年 95% 以上的系统差别全在工程细节上。最后分享一个小技巧如果你要评估自己的 LRU 到底好不好用别只看命中率一个指标。把命中数、未命中数、淘汰数、平均访问耗时四个数据画在同一张时序图上你会非常清楚地看到淘汰行为和数据热度的关系。有几次我就是靠这张图发现淘汰数在每天上午 9 点准时出现尖峰追下去原来是早高峰的用户登录行为触发了大量一次性写入后来给这些数据单独设了短过期时间问题就解决了。算法是死的数据是活的多看监控比多改代码有用得多。