高并发本地缓存设计：LRU、线程安全与过期清理实战

1. 拿到D4后的第一件事拆解考点不是急着写代码看到复试题D4这个编号估计不少同学会心头一紧——复试的第四题往往是那种看起来不难、但想拿满分却不容易的综合性题目。我当年参加某次复试时拿到的D4要求在一小时内设计并实现一个高并发场景下的本地缓存既要支持设置过期时间又要有容量上限容量满了按LRU策略淘汰还要保证线程安全。题目只有三五行字但信息密度极大。很多同学一看到LRU就开始埋头写LinkedHashMap结果写完才发现线程安全、过期清理这些坑一个都没避最后只能交个半成品。这道题之所以经典是因为它把数据结构、并发编程、设计取舍、边界条件处理全部揉在了一起。面试官不看你会不会背LRU而是看你能否在有限时间内把一个看似简单的需求拆解成清晰的模块并用代码证明你理解每个决策背后的代价。所以我拿到题后的第一件事不是写代码而是把考察点拆成三块存储结构选型LRU的插入、查询、淘汰都要求在O(1)时间复杂度内完成这决定了你必须用哈希表双向链表而不是数组或普通链表。并发安全策略在高并发读写下如何让缓存的get、put、淘汰操作都线程安全同时尽量少锁竞争。这需要你明确线程安全的粒度是锁整个结构还是锁单个桶。过期清理机制支持过期时间看似只是加个时间戳但真正难的是如何高效清理过期键避免内存浪费。惰性删除、定期清理、时间轮各有适用场景。这三块任何一块出问题整个方案都会崩塌。更关键的是面试官会通过你拆解问题的顺序判断你的工程思维先想清楚约束条件再定数据结构最后补并发和过期而不是上来就堆代码。1.1 这题到底在考什么我们先把题目翻译成人话。本地缓存意味着数据存放在进程内存里速度极快但容量受限于JVM堆大小。设置过期时间意味着每个键值对除了value还要记住一个deadline。容量有限LRU淘汰意味着当插入新键时如果当前元素数量达到上限必须把最久没被访问的那个键删掉。线程安全就不用解释了多线程同时读写时不能出现数据错乱、死循环或内存泄漏。这里有个容易被忽略的点LRU的访问不仅仅是get还包含put更新已有键。如果你只是get的时候把节点移到链表头部而put更新一个已存在的key时忘了移动那么淘汰策略就会失真。很多初版代码就栽在这个细节上。此外过期时间和LRU是叠加的。一个键还没被访问到但已经过期了它应该被立即淘汰。那么问题来了淘汰的时候是先按过期时间删还是先按LRU删我当时的答案是过期优先。因为过期数据本质上已经是无效数据留着只会污染缓存命中率。所以每次访问时先检查过期再走LRU逻辑容量满时优先删除已过期的节点如果不存在过期节点再执行LRU淘汰。1.2 面试官最想听到的解题思路面试官通常不会只看最终代码他们会关注你的设计推演过程。我建议在动手前先用两三分钟口头描述方案我会用HashMap做主索引保证O(1)定位用双向链表维护访问顺序链头是最近访问的节点链尾是最久未访问的节点。插入新键时放到链头如果容量超限就移出链尾。为了让链表操作和哈希索引保持一致链表节点里保存key和valueHashMap的value直接指向这个节点。并发控制方面对全局的哈希表和链表操作加一把锁保证get和put的原子性过期时间则给每个节点附带expireAt字段get时惰性删除后台再启动一个线程定期清理。这段话的价值在于它已经覆盖了90%的考点。至于用不用ConcurrentHashMap用不用LinkedHashMap这些细节是后面代码的事。先把思路讲清楚面试官对你的印象分就稳了。2. 核心数据结构双向链表哈希表的组合拳LRU的实现方式很多人都背过哈希表双向链表。但真正动手写的时候有几个设计决策会影响代码质量和运行效率。我在这里复盘一下我当时的实现路径。2.1 为什么不能用LinkedHashMap敷衍了事最省事的做法是继承LinkedHashMap重写removeEldestEntry再把accessOrder设为true。代码不到十行就能实现一个线程不安全的LRU。但在复试这种场合交这个上去基本等于告诉面试官你只会调库——而且这个办法还有个硬伤它无法优雅地支持过期时间。你可以用new LinkedHashMap时塞一个自定义的expireAt字段吗不能因为键值对本身没有地方存这个时间戳除非你把value包装成一个携带过期时间的对象但这又会让泛型变得很别扭。更要命的是LinkedHashMap的removeEldestEntry只会在插入时触发如果你希望访问一个已过期但尚未被清理的键时也能自动删除LinkedHashMap做不到。你只能在get的时候手动判断但如果你用的是匿名内部类代码会变得很零散。所以真正的复试题考察的是你能不能从零构建这个结构而不是依赖工具类。还有一个原因是面试官后续大概率会追问如果把锁粒度细化你怎么做如果你顶着LinkedHashMap回答会很被动。所以我的建议是老老实实手写双向链表节点。这不仅是为了展示能力更是为了后续扩展比如加过期字段、加并发控制留出空间。2.2 从零手写LRU的基础骨架我先把基础的、不考虑线程安全和过期的版本写出来后面再逐步增强。节点类我习惯定义为private static class NodeK, V { K key; V value; long expireAt; // 过期时间戳0表示永不永不过期后文会讲 NodeK, V prev; NodeK, V next; Node(K key, V value, long expireAt) { this.key key; this.value value; this.expireAt expireAt; } }缓存主体包含一个HashMap、一个头哨兵节点和一个尾哨兵节点。使用哨兵节点可以避免处理链表为空时的边界判断这个细节非常有用。初始化时让head.next tailtail.prev head。关键操作就三个moveToHead(Node)把已有节点从原位置摘除再插入到head之后。removeNode(Node)摘除节点维护前后节点的指针。addToHead(Node)在head之后插入新节点。当put一个不存在的key时新建节点塞进HashMap然后addToHead。如果此时size大于capacity就从tail.prev取出真正的最久未使用节点在HashMap里删除再removeNode。当put一个已存在的key时更新value更新过期时间然后moveToHead。当get时如果节点存在moveToHead返回value。这个基础版本的核心逻辑很简单但有一个坑HashMap的value必须直接存储Node引用而不是只存V值。否则你无法在O(1)时间内定位到链表中的节点每次get都要遍历链表找key复杂度退化为O(n)。我当时见过有人用HashMapK, V配合链表节点里存keyget的时候得遍历链表来找到节点差点没把面试官气笑。为了验证基础版本的正确性我建议在写完代码后手动跑几个边界用例空缓存get一个不存在的key。容量为1时连续put两个键确认第一个被淘汰。get一个key后再连续put新键确认被get过的key不会先被淘汰。更新已有key后确认它在链表中的位置被移动到头部。这些用例跑通后再谈线程安全和过期时间。3. 线程安全和性能之间的钢丝本地缓存如果只在单线程下用那根本不需要费劲。但复试题目明确写了高并发场景所以这一步是分水岭接下来要决定用什么策略保证线程安全以及这个策略对性能的影响有多大。3.1 粗粒度锁的问题最简单粗暴的办法在put和get方法上直接加synchronized或者用一个ReentrantLock把整个操作包起来。这样做的好处是正确性几乎不用动脑线程安全了读写互斥了HashMap和链表的状态始终一致。但坏处也很明显——所有读写操作串行化。高并发场景下100个线程同时get只能一个一个排队吞吐量直接腰斩。更关键的是这种粗粒度锁掩盖了一个事实读操作明明不修改链表结构但moveToHead这一步会修改链表所以读操作也得加锁。如果某个读操作只是查一下key是否存在不加锁倒也没事但LRU要求在get时把节点移到头部这就让读操作也变成了写操作。很多初学者没意识到这一点以为get只需要读HashMap结果在多线程环境下出现链表指针错乱。那能不能让get不加锁有一个思路是只有put导致淘汰时才需要全局锁get时只在节点命中时加一个轻量级锁。但这里有个数据一致性问题如果node.next和node.prev被其他线程修改get时moveToHead可能会操作一个已经不在链表中的节点导致指针悬挂。所以纯粹的get不加锁方案在高并发下非常容易写错我不推荐在复试现场冒险。3.2 ConcurrentHashMap分段锁的自定义实现另一个常见的方案是用ConcurrentHashMapK, NodeK, V替代HashMap然后只对链表操作部分加锁。这样get操作可以先用map.get(key)无锁读到node再对链表加锁做moveToHead。put操作则先用map.put或map.compute处理哈希表部分再对链表加锁处理顺序。但这里有一个需要特别小心的地方ConcurrentHashMap能保证单个键的原子操作但它不能保证哈希表操作链表操作这个组合动作的原子性。举一个例子线程A执行put新建节点准备把它加到链头线程B同时执行get读到了旧节点准备把它移到链头。如果没有统一锁住链表两个线程可能同时修改链表的head指针导致节点丢失。所以我的做法是哈希表和链表共享同一把锁也就是全局锁。但为了减少锁竞争可以把判断容量是否超限放到锁内来做而计算新节点的Hash放到锁外做。这样锁内代码尽量短性能也不会差太多。实际测试中这种做法的吞吐量比纯synchronized方法提升有限但至少结构清晰面试官看得懂。如果想进一步优化可以考虑分段链表把哈希表按key的哈希值分成多个段每个段有自己的双向链表和锁。这样不同段的读写互不干扰锁竞争显著降低。但代价是实现复杂度飙升淘汰时要在多个段之间协调总容量过期清理也要遍历所有段。我建议如果面试官不追问不要主动提出这个方案——除非你能在三分钟内把它讲清楚否则容易给自己挖坑。复试的时间非常宝贵稳妥比炫技更重要。3.3 为什么我说读多写少场景可以更激进如果面试官接着问你这个缓存是读多写少你怎么优化这就是加分环节了。我的回答是读多写少的场景下可以用读写锁读读并行读写互斥。Java中的ReentrantReadWriteLock可以提供这个能力private final ReentrantReadWriteLock lock new ReentrantReadWriteLock(); public V get(K key) { long now System.currentTimeMillis(); // 先加读锁允许并发读 lock.readLock().lock(); try { NodeK, V node map.get(key); if (node null) { return null; } if (isExpired(node, now)) { // 过期了也不能在持有读锁时直接删除因为删除需要写锁 // 这里可以先返回null或者记录一下待删除等写锁拿到后再清理 return null; } // 这里需要moveToHead会修改链表所以必须升级为写锁 lock.readLock().unlock(); lock.writeLock().lock(); try { // 再次检查节点是否还在可能已被其他线程删除 NodeK, V current map.get(key); if (current null || isExpired(current, now)) { return null; } moveToHead(current); return current.value; } finally { // 降级为读锁不直接释放写锁交给调用方 lock.writeLock().unlock(); } } finally { // 注意上面已经释放了读锁这里不能重复释放 } }这种先读后写的操作其实有锁升级的麻烦。在Java的读写锁中读锁不能直接升级为写锁必须先释放读锁再获取写锁。而释放读锁和获取写锁之间存在时间窗口可能被其他线程插入所以需要二次检查。整个过程非常容易出错我当年在考场上是先写了一个用synchronized的版本确保正确性然后口头描述了读写锁的优化思路并告知面试官这个方案的复杂度和潜在问题。这样做既展示了思考深度又不会因为写错代码而扣分。这里的核心经验是在复试题这种高压场景下先把基础方案做对再谈优化。如果你想用高级方案至少要保证它在边界条件下是安全的否则就不要用。4. 过期时间惰性删除和定期清理的搭配支持过期时间看起来只是给Node加一个expireAt字段但实际设计时要考虑数据的清理时机和内存释放。我采用了两层策略。4.1 惰性删除的实现细节惰性删除的思路是只有在访问到某个key时才检查它是否过期如果过期就删除并返回null。这个策略的优点是无额外线程开销缺点是有过期的key如果一直不被访问就会一直占着内存。实现时在get方法中先拿到node然后判断private boolean isExpired(NodeK, V node, long now) { return node.expireAt ! 0 node.expireAt now; }expireAt为0表示永不过期。put时如果传入了过期时间就设置now ttl否则设为0。在put一个已存在的key时也要更新过期时间——这点容易被忽略因为覆盖一个键时新的过期时间应该重新计时。然后在put操作中当缓存达到容量上限时寻找可淘汰的节点时优先淘汰已过期的节点。怎么找如果每次都从tail开始往前遍历最坏情况下要遍历整个链表才能找到一个过期节点开销太大。我的做法是在日常淘汰逻辑中从tail往前看只检查尾部几个节点——这个思路基于一个假设越久没被访问的节点越有可能早已过期。所以淘汰时从tail往前最多扫描3个节点如果遇到过期的直接删除否则就按LRU淘汰tail节点。这不算严格最优但能覆盖大多数场景而且代码复杂度低。4.2 定期清理线程的边界条件惰性删除无法清理那些写入后立刻不再访问的过期键。如果缓存中堆满了这样的键哪怕它们都过期了LRU容量判断还是会认为缓存是满的导致新插入的键被错误淘汰。所以需要一个后台线程定期扫描链表清除过期节点。实现时我用了一个ScheduledExecutorService每秒钟执行一次清理任务ScheduledExecutorService cleaner Executors.newSingleThreadScheduledExecutor(r - { Thread t new Thread(r, cache-cleaner); t.setDaemon(true); return t; }); cleaner.scheduleAtFixedRate(this::cleanUp, 1, 1, TimeUnit.SECONDS);cleanUp方法遍历双向链表从头到尾逐个节点判断是否过期过期则删除。这里有个坑遍历链表时一旦删除节点指针会变化所以需要先保存next节点再删除。同时遍历过程中要加写锁防止其他线程修改链表。另一个坑是清理线程只负责删除过期键但如果缓存中全是没有过期的键清理线程什么也不干这是正常的。不要为了体现工作量而强制清理未过期的节点那会破坏LRU语义。那么定期清理的间隔设多少合适我设的是1秒对于大多数复试场景足够。如果要求更精确可以考虑让每个节点根据其过期时间动态规划下一次清理时刻但这需要优先级队列或时间轮考场代码量会爆炸不建议。4.3 时间轮和分层时间轮加分项当面试官追问定期清理会不会有延迟能不能更精确地触发清理时可以提到时间轮算法。时间轮的本质是一个环形数组每个槽位对应一个时间刻度槽位上的链表存放该时刻需要到期的定时任务。当时间指针走到某个槽位时遍历该槽位链表执行过期清理。相比固定间隔的全量扫描时间轮能把清理动作精确到某个时间点同时避免无谓的遍历。分层时间轮则进一步优化底层时间轮精度高但范围小高层时间轮精度低但范围大任务先放在高层随着时间推移降级到底层。听起来很酷但实际实现复杂度高。我的建议是在复试现场你只需要把这个概念讲清楚并说一句如果需要可以后续实现千万不要真的开始写时间轮代码——那会占用大量时间而且容易写bug。5. 考场上的展示技巧和常见追问D4这道题代码只是基础更关键的是你如何向面试官展示你的工程思维。我把自己总结的展示套路分享出来按这个顺序讲基本能覆盖大多数追问。5.1 代码之外的表达策略首先我不会一上来就贴完整代码而是先画一个简单的结构图用言语描述HashMap指向双向链表节点链表头是热点数据链表尾是冷数据。然后说清楚为什么这样设计。接着我会把线程安全和过期时间作为两个独立的增强点逐个叠加到基础LRU上。每叠加一个都会强调这会让哪部分复杂度上升。其次我会主动说明测试用例。哪怕面试官不要求我也会说我测试过容量为1、key覆盖、过期键清理、多线程并发读这四个场景。主动说测试会让面试官觉得你有质量意识。最后控制代码量。完整实现大概150行左右不要写太多注释但关键方法上方用一行注释说明意图即可。面试官看的是结构不是注释数量。5.2 高频追问缓存穿透、击穿、雪崩怎么办这道题最容易延伸的方向是分布式缓存场景。面试官可能会问如果这个缓存用在系统里如何防止缓存穿透、击穿、雪崩虽然这超出了本地LRU的范围但你要能回答缓存穿透查询一个不存在的数据每次都打到数据库。解决办法是缓存空值或者用布隆过滤器拦截。缓存击穿某个热点key过期瞬间大量请求同时打到数据库。解决办法是互斥锁重建缓存或者让热点key的过期时间尽量分散。缓存雪崩大量key同时过期导致数据库压力骤增。解决办法是过期时间加随机值或使用多级缓存。注意回答到这里时一定要强调这些是缓存系统的通用问题我的本地缓存主要负责单机内存管理真正落地需要在上一层的分布式缓存里做策略——别把话题扯太远。5.3 我踩过的三个坑第一个坑是HashMap的value存了值本身而不是节点引用。这导致get时无法快速定位链表节点只能遍历链表性能从O(1)退化到O(n)。当时我还没意识到问题直到测试100万条数据时发现查询极慢才恍然大悟。第二个坑是没有在put更新已有key时moveToHead。我当时只更新了value没移动节点结果LRU顺序错乱。后来我加了一个测试put A、put B、put A、put C如果A被淘汰就说明顺序错了。这个测试救了我。第三个坑是清理线程和put操作并发修改链表。我最初没加锁直接遍历链表删除过期节点结果偶发死循环——因为另一个线程同时修改了prev/next指针。后来统一加锁问题才消失。这三个坑建议你一定要亲自踩一遍踩过才能真正理解为什么要这么设计。最后再分享一个小心得复试做这种设计题最重要是稳。我当时看到D4先给自己定了三步走——先写一个单线程正确版本再套上锁最后加过期清理。每一步都跑一遍测试。虽然代码最终不是最优的但逻辑自洽、思路清晰面试官反而更愿意在此基础上聊扩展方案。有些同学一上来就想写时间轮分段锁读写锁结果半小时过去连基础版本都没跑通那才是真正的失分点。你平时如果已经积累过类似实现考场上按部就班地递进就已经赢过大多数人。