JCSprout 源码实战：从零手写 LRU 缓存淘汰策略（三套实现演进）

文档教程后端【免费下载链接】JCSprout‍ Java Core Sprout : basic, concurrent, algorithm项目地址https://gitcode.com/gh_mirrors/jc/JCSprout点击查看免费下载LRULeast Recently Used最近最少使用是缓存领域最核心的淘汰策略之一本指南以 JCSprout 仓库 docs/algorithm/LRU-cache.md 为主线完整讲解 LRU 的演进式实现从数组 队列 守护线程的简易版到HashMap 双向链表的标准版再到基于 LinkedHashMap 的一行式优雅实现。读完本文你将掌握 LRU 的底层数据结构原理、常见边界问题以及如何用 Java 手写一个可运行的 LRU 缓存并能在仓库源码与测试用例中验证每个结论。LRU 是什么为什么缓存需要淘汰策略LRU 是Least Recently Used的简写字面意思为最近最少使用。它通常被用作缓存的淘汰策略由于缓存内存非常宝贵必须根据某种规则剔除数据保证内存不被撑满。以常用的 Redis 为例它内置了多种数据淘汰策略LRU 正是其中一类策略描述volatile-lru从已设置过期时间的数据集中挑选最近最少使用的数据淘汰volatile-ttl从已设置过期时间的数据集中挑选将要过期的数据淘汰volatile-random从已设置过期时间的数据集中任意选择数据淘汰allkeys-lru从所有数据集中挑选最近最少使用的数据淘汰allkeys-random从所有数据集中任意选择数据进行淘汰no-eviction禁止驱逐数据可以看到volatile-lru与allkeys-lru分别作用于设置了过期时间的数据集与全量数据集其核心思想一致优先淘汰最长时间没有被访问的数据。理解了这一点就能把握 LRU 实现的核心——需要一种机制来记录数据的访问新鲜度。实现一LRUAbstractMap——简易 HashMap 队列 守护线程原文档中的第一版实现来自一道经典面试题需求是实现一个 LRU 缓存当缓存数据达到 N 之后需要淘汰掉最近最少使用的数据N 小时之内没有被访问的数据也需要淘汰掉。仓库中对应源码为 src/main/java/com/crossoverjie/actual/LRUAbstractMap.java它继承了java.util.AbstractMap属于自研的简易 Map 实现。类注释中明确了设计目标源码 第 11-26 行key 的 hashcode 生成复用 HashMap 的 hash 函数put/get 时若 key 相等为简单起见未比较 equals 与 hashcode限制大小Map 最大 size 为 1024超过后淘汰最久未访问的键值对淘汰时调用lruCallback具备超时功能键值对 1 小时内未被访问即被淘汰由单独的守护进程处理HashMap 的扩容、链表超过阈值等场景未考虑进来。完整代码较长其核心设计可拆解为四个部分。数据结构数组 拉链法冲突处理 容量队列// map 最大 size private final static int MAX_SIZE 1024; // 记录写入顺序的队列 private final static ArrayBlockingQueueNode QUEUE new ArrayBlockingQueue(MAX_SIZE); // 默认数组大小 private final static int DEFAULT_ARRAY_SIZE 1024; private Object[] arrays; // 超时时间1 小时 private final static Long EXPIRE_TIME 60 * 60 * 1000L; // 整个 Map 的大小 private volatile AtomicInteger size;数据存放采用与 HashMap 相同的数组 链表方式只是手动实现了一个简易版hash(key)后对arraySize取模得到桶下标冲突时以Node链表挂接源码 hash 方法 完全复刻了 HashMap 的(h key.hashCode()) ^ (h 16)扰动函数内部用一个ArrayBlockingQueue保存每次写入的数据队列的 FIFO 特性正好用来记录谁先来超时时间固定为 1 小时60 * 60 * 1000L毫秒。put / get / remove 的写读删流程put 流程源码 第 107-150 行计算hash % arraySize定位桶桶为空则新建Node写入数组同时QUEUE.offer()入队并sizeUp()桶非空则沿链表遍历key 已存在就直接覆盖 value不存在则头插新节点并sizeUp()。get 流程源码 第 153-188 行定位桶后沿链表查找命中时调用currentNode.setUpdateTime(System.currentTimeMillis())刷新访问时间——这一步是后续超时淘汰的依据。remove 流程源码 第 191-229 行命中后sizeDown()删除节点并从队列QUEUE.poll()移除若目标在链表中间则通过nNode.pre.next nNode.next完成断链重接。容量上限依赖 FIFO 队列实现淘汰sizeUp()是容量控制的核心源码 第 235-257 行int size this.size.incrementAndGet(); if (size MAX_SIZE) { // 找到队列头的数据 Node node QUEUE.poll(); if (node null) { throw new RuntimeException(data error); } // 移除该 key Object key node.key; remove(key); lruCallback(); }思路是当写入导致容量超过阈值 N此处为 1024时根据队列的 FIFO 特性删除队列头的数据——因为队列头的数据一定是最先放进去的。淘汰后调用lruCallback()当前实现仅打印 debug 日志 源码第 322-324 行这可以理解为一个预留的扩展点便于业务侧感知淘汰事件。超时淘汰守护线程检查队首构造时通过executeCheckTime()启动一个单线程的ThreadPoolExecutor线程工厂使用 Guava 的ThreadFactoryBuilder设置名称check-thread-%d并标记为守护线程源码 第 90-99 行拒绝策略为AbortPolicy。CheckTimeThread的循环逻辑源码 第 335-355 行while (flag) { Node node QUEUE.poll(); if (node null) { continue; } Long updateTime node.getUpdateTime(); if ((updateTime - System.currentTimeMillis()) EXPIRE_TIME) { remove(node.key); } }为什么只检查队首因为最先放进去的数据最有可能先满足超期条件——这是基于时间单调递增的合理推断把扫描范围收敛到队首代价很低。设置为守护线程的目的也很明确如果是一个用户线程它会一直运行最坏情况下可能导致程序无法正常退出守护线程则不会出现这个情况。当QUEUE.size() 0时sizeDown()会把flag置为false线程随之退出源码 第 262-269 行。致命缺陷它并不是真正的 LRU实现一虽然大体满足功能但存在一个致命问题最近最少使用没有满足删除的数据都是最先放入的数据。它实际是 FIFO先进先出淘汰而非按访问频率/新鲜度淘汰——即使某个队首数据刚被频繁访问过只要容量满了它依然会被优先淘汰。不过正如原文档指出的其中put、get流程算是一个简易的 HashMap 实现对加深 HashMap 的理解很有帮助。仓库测试 src/test/java/com/crossoverjie/actual/AbstractMapTest.java 演示了其 put/get/remove/size 的基本用法。实现二LRUMap——HashMap 双向链表真正的 LRU从实现一的教训出发要记录最近最少使用至少需要满足两点要有一个有序的集合来保证写入的顺序在使用了数据之后能够更新它的顺序。基于以上两点很容易想到一个常用的数据结构链表。操作规则如下每次写入数据时将数据放入链表头结点使用数据时将数据移动到头结点缓存数量超过阈值时移除链表尾部数据。仓库中对应实现为 src/main/java/com/crossoverjie/actual/LRUMap.java整体结构数据用HashMap存放访问顺序用双向链表维护链表有头结点header与尾结点tailer。初始化构造带头尾哨兵的双向链表public LRUMap(int cacheSize) { this.cacheSize cacheSize; // 头结点的下一个结点为空 header new Node(); header.next null; // 尾结点的上一个结点为空 tailer new Node(); tailer.tail null; // 双向链表 头结点的上结点指向尾结点 header.tail tailer; // 尾结点的下结点指向头结点 tailer.next header; }初始化时生成了两个没有真实数据的哨兵节点头、尾各一它们互相关联形成一个环形结构只是为了让链表在为空时也有可操作的对象。需要注意真实数据写入之后需要把这两个初始化节点摘除这正是addHead中nodeCount 2特殊分支存在的意义源码 第 156-160 行。put写入头结点满了先删尾public void put(K key, V value) { cacheMap.put(key, value); addNode(key, value); // 双向链表中添加结点 } private void addNode(K key, V value) { NodeK, V node new Node(key, value); // 容量满了删除最后一个 if (cacheSize nodeCount) { delTail(); } addHead(node); // 写入头结点 }delTail()会先从cacheMap中移除尾结点对应的 key再调整链表指针、nodeCount--源码 第 164-174 行。get查链表并移动到头部public V get(K key) { NodeK, V node getNode(key); moveToHead(node); // 移动到头结点 return cacheMap.get(key); }moveToHead是 LRU 语义的关键源码 第 73-100 行分三种情况处理节点本就是尾结点node.tail null更新tailer指针nodeCount--节点本就是头结点node.next null无需处理直接返回节点处于中间node.tail ! null node.next ! null将其上一节点next指向其下一节点实现摘除同时nodeCount--。最后在头部新增当前节点。这里有一个值得注意的细节需要重新new一个 Node 对象源码注释明确说明不然原本的 node 还有着下面的引用会造成内存溢出源码 第 95-97 行。值得一提的是仓库源码比原文档多了一行node.next.tail node.tail;源码 第 91 行用于同步修正被摘除节点的下一节点的前驱指针是原文档示例代码的补充完善理解时可对照源码阅读。实际效果验证仓库测试 src/test/java/com/crossoverjie/actual/LRUMapTest.java 完整覆盖了写入、读取、重复 key、容量逐级淘汰等场景下面节选原文档中的两组核心用例。写入时容量 3Test public void put() throws Exception { LRUMapString,Integer lruMap new LRUMap(3); lruMap.put(1,1); lruMap.put(2,2); lruMap.put(3,3); System.out.println(lruMap.toString()); lruMap.put(4,4); System.out.println(lruMap.toString()); lruMap.put(5,5); System.out.println(lruMap.toString()); } // 输出 1:1--2:2--3:3-- 2:2--3:3--4:4-- 3:3--4:4--5:5--使用时get 之后被访问的数据移动到链表头Test public void get() throws Exception { LRUMapString,Integer lruMap new LRUMap(3); lruMap.put(1,1); lruMap.put(2,2); lruMap.put(3,3); System.out.println(lruMap.toString()); System.out.println(); Integer integer lruMap.get(1); System.out.println(integer); System.out.println(); System.out.println(lruMap.toString()); } // 输出 1:1--2:2--3:3-- 1 2:2--3:3--1:1--输出清晰地展示了 LRU 的核心行为get(1) 之后1:1从链表头被移到链表尾最新访问位置后续若容量满最先被淘汰的将是2:2。测试中还包含重复 key 场景put3中连续 put 两次 2、put4中容量 3 时重复 put 2用于验证覆盖写入对链表顺序的影响get4则演示了容量 5 时依次 get 2/3/4/5 后再 put 6 的完整淘汰过程读者可直接运行这些测试观察输出。数据结构推演文字版对象关系图原文档配了多张对象关系图初始化、逐次写入、获取数据由于这些图是文档发布时的外部图床链接仓库内无对应图片文件这里以文字推演替代初始化时header哨兵与tailer哨兵互相指向nodeCount 0此时链表为空环写入 1 后header.next 1号节点1号节点.tail headerheader更新为 1 号节点nodeCount 1写入 2 后链序为tailer(哨兵) → 1 → 2 → header(哨兵)此时nodeCount 2触发哨兵摘除逻辑tailer直接指向 1 号节点链序变为1 → 2写入 3 后链序1 → 2 → 3容量 3 已满写入 4 时cacheSize nodeCount先delTail()淘汰 1 号节点再头插 4链序变为2 → 3 → 4get(2) 后2 号节点从链中摘除并重新头插链序变为3 → 4 → 2。理解这段推演就理解了头插新数据、访问即上移、满则删尾的完整机制。实现二的要点与不足原文档总结的实现二要点数据直接利用 HashMap 存放保证 O(1) 的读写内部使用双向链表存放数据因此有头结点header和尾结点tailer每次写入头结点、删除尾结点都依赖header/tailer如果看着比较懵建议自己实现一个链表熟悉下使用数据移动到链表头时第一步需要在双向链表中找到该节点。这里体现出链表的问题查找效率很低最差需要 O(N)getNode从tailer起线性遍历源码 第 107-119 行写入头结点时判断链表大小等于 2 需要删除初始化的头尾结点因为初始化生成的两个双向节点只是占位结构真实数据进来后需删除以便后续操作这点可以继续优化以上所有操作都是线程不安全的需要使用者自行控制并发。实现三LRULinkedMap——基于 LinkedHashMap 的优雅解法如果对 Java 集合比较熟悉会发现实现二的结构和LinkedHashMap非常类似——它内部同样维护了一个双向链表。仓库中相关原理可参考 docs/collections/LinkedHashMap.md 一文这里直接看如何借用它实现 LRU。仓库对应实现为 src/main/java/com/crossoverjie/actual/LRULinkedMap.java完整代码只有几十行public class LRULinkedMapK,V { /** 最大缓存大小 */ private int cacheSize; private LinkedHashMapK,V cacheMap; public LRULinkedMap(int cacheSize) { this.cacheSize cacheSize; cacheMap new LinkedHashMap(16, 0.75F, true) { Override protected boolean removeEldestEntry(Map.Entry eldest) { if (cacheSize 1 cacheMap.size()) { return true; } else { return false; } } }; } public void put(K key, V value) { cacheMap.put(key, value); } public V get(K key) { return cacheMap.get(key); } public CollectionMap.EntryK, V getAll() { return new ArrayListMap.EntryK, V(cacheMap.entrySet()); } }这次代码非常简洁具体的逻辑 LinkedHashMap 已经帮我们实现好了其关键在于构造 LinkedHashMap 时传入第三个参数accessOrder true这会开启访问顺序模式get操作会把被访问的节点移动到链表尾部最新位置重写removeEldestEntry方法这是 LinkedHashMap 预留的淘汰钩子。removeEldestEntry一个方法搞定淘汰LinkedHashMap.removeEldestEntry的默认实现是protected boolean removeEldestEntry(Map.EntryK,V eldest) { return false; }它默认返回false也就是不管有没有超过阈值都不会淘汰任何数据。所以我们自定义大于阈值时返回trueLinkedHashMap 就会在每次put后检查一旦满足条件就自动删除最久未使用的数据也就是链表头部、最早进入的那条记录if (cacheSize 1 cacheMap.size()) { return true; }注意这里判断条件是cacheSize 1 cacheMap.size()因为removeEldestEntry是在新元素已经插入之后被回调的此时size()比真实容量多 1所以写成cacheSize 1。实际效果验证仓库测试 src/test/java/com/crossoverjie/actual/LRULinkedMapTest.java 中的用例与原文档一致。写入时容量 3Test public void put() throws Exception { LRULinkedMapString,Integer map new LRULinkedMap(3); map.put(1,1); map.put(2,2); map.put(3,3); for (Map.EntryString, Integer e : map.getAll()) { System.out.print(e.getKey() : e.getValue() \t); } System.out.println(); map.put(4,4); for (Map.EntryString, Integer e : map.getAll()) { System.out.print(e.getKey() : e.getValue() \t); } } // 输出 1 : 1 2 : 2 3 : 3 2 : 2 3 : 3 4 : 4写入 4 时容量已满最久未使用的1 : 1被自动淘汰。使用时容量 4Test public void get() throws Exception { LRULinkedMapString,Integer map new LRULinkedMap(4); map.put(1,1); map.put(2,2); map.put(3,3); map.put(4,4); for (Map.EntryString, Integer e : map.getAll()) { System.out.print(e.getKey() : e.getValue() \t); } System.out.println(); map.get(1); for (Map.EntryString, Integer e : map.getAll()) { System.out.print(e.getKey() : e.getValue() \t); } } // 输出 1 : 1 2 : 2 3 : 3 4 : 4 2 : 2 3 : 3 4 : 4 1 : 1get(1) 之后1 被移动到访问顺序的末尾与实现二的行为完全一致但代码量大幅减少。三种实现对比与总结对比维度实现一 LRUAbstractMap实现二 LRUMap实现三 LRULinkedMap数据结构数组 链表 ArrayBlockingQueueHashMap 双向链表LinkedHashMap内部双向链表淘汰依据FIFO 队首并非真正 LRU链表尾部真正 LRU链表头部真正 LRU访问更新仅刷新 updateTime 字段节点移动到链表头accessOrder 模式下自动移到尾部超时淘汰支持守护线程扫描队首不支持不支持查找复杂度O(1) 定位桶 链表遍历getNode 最差 O(N)O(1)链表节点有 HashMap 索引线程安全否否否代码量约 350 行约 220 行约 50 行三套实现的演进脉络非常清晰实现一证明了队列 定时扫描的思路可行但暴露了它只是 FIFO 而非 LRU 的致命缺陷同时顺手演示了一个简易 HashMap 的实现实现二用双向链表真正落实了访问即上移、满则删尾的 LRU 语义代价是链表查找 O(N) 与较多的边界处理实现三借助 LinkedHashMap 的accessOrder与removeEldestEntry钩子以最少代码实现了同样语义的 LRU是工程中最实用的方案。了解了这些实现平时使用缓存时至少可以做到知其所以然。此外业界使用较多的还有 Guava 的缓存实现本仓库 pom.xml 中已引入 guava 22.0 依赖仓库内相关用法可参考 docs/frame/guava-cache.md 一文它在此基础上还支持多种过期策略可作为进一步学习的方向。所有源码与测试均可在当前仓库中直接查阅与运行三个实现类位于src/main/java/com/crossoverjie/actual/目录对应测试位于src/test/java/com/crossoverjie/actual/目录使用 Maven 项目结构参见 pom.xml本地执行mvn test -DtestLRUMapTest,LRULinkedMapTest,AbstractMapTest即可复现文中所有输出。赞分享文档教程后端【免费下载链接】JCSprout‍ Java Core Sprout : basic, concurrent, algorithm项目地址https://gitcode.com/gh_mirrors/jc/JCSprout点击查看免费下载相关推荐WatchAlert 内存缓存设计LRU缓存淘汰策略实现WatchAlert 内存缓存设计LRU缓存淘汰策略实现 缓存架构概述 在云原生监控告警引擎中缓存系统是提升数据处理性能的核心组件。WatchAlert作为后端可观测性告警云原生运维终极Obsidian美化指南18个CSS片段打造个性化知识管理空间终极Obsidian美化指南18个CSS片段打造个性化知识管理空间 还在为Obsidian的默认界面感到乏味吗想要打造既美观又高效的个性化知识管理系统aw文档知识管理深入理解GeeCache项目LRU缓存淘汰策略实现深入理解GeeCache项目LRU缓存淘汰策略实现 前言 在构建高性能应用时缓存技术是不可或缺的重要组成部分。本文将深入探讨如何从零开始实现一个基于Go语言示例工程上一篇Tmax-27B-MLX-6bit性能深度解析为什么它在Apple M芯片上如此高效下一篇Conventional-Commit-Types深度解析为什么你的团队需要Emoji提交规范 创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考