1. 从一次缓存命中率暴跌说起LRU 到底哪里不够用做过服务端开发的人大概率都经历过这样的场景某个接口平时响应时间稳定在几毫秒某天突然开始间歇性抖动P99 延迟从 8ms 飙到 200ms 以上查了半天数据库、网络、GC 都没问题最后定位到缓存命中率从 92% 掉到了 61%。把缓存淘汰策略从 LRU 换成 LIRS 之后命中率回到 89%延迟也跟着恢复正常。这不是玄学而是访问模式本身在惩罚LRU。LRULeast Recently Used最近最少使用的核心假设是如果一个数据最近被访问过那么它未来被再次访问的概率也更高。这个假设在大多数场景下成立所以 LRU 成了最通用的缓存淘汰策略从操作系统的页缓存到 Redis 的近似 LRU再到各种本地缓存库到处都是它的身影。但问题在于大多数场景不等于所有场景有一类访问模式会让 LRU 的表现急剧退化甚至退化到接近随机淘汰的水平。这类模式就是弱局部性访问模式典型代表是顺序扫描和偶发冷数据访问。举个具体的例子假设缓存容量是 100 个条目现在有一个顺序扫描操作依次读取 200 个不重复的数据块。LRU 会把前 100 个块全部淘汰掉换成后 100 个块。如果这 200 个块里其实有 80 个是热点数据只是被顺序扫描顺带读了一遍那这 80 个热点数据就被无辜地挤出去了。等真正的业务请求再来访问这些热点数据时全部缓存未命中只能回源查数据库。这就是所谓的缓存污染Cache Pollution。LIRSLow Inter-reference Recency Set就是专门为解决这个问题而设计的。它的核心思想不是看最近有没有被访问而是看两次访问之间的间隔有多长。间隔短的叫高复用距离High Reuse间隔长的叫低复用距离Low Reuse。LIRS 优先保留那些复用距离短的数据即使它们最近没有被访问过同时允许复用距离长的数据在缓存里短暂停留但不让它们污染核心缓存区。这篇文章会从 LRU 的失效场景讲起把 LIRS 的核心机制拆开揉碎然后给出一个可运行的 Python 实现最后聊聊在实际项目中怎么选型、怎么调参、怎么避坑。不管你是做后端服务、数据库内核还是嵌入式存储只要涉及缓存淘汰这篇内容都能给你一些可以直接抄作业的思路。2. LRU 在顺序扫描下的失效链路一次完整的命中率崩塌复盘2.1 用一个小实验把问题复现出来光说理论不够直观我写了一段模拟代码用两种访问模式对比 LRU 和 LIRS 的命中率差异。先看 LRU 的实现用 Python 的 OrderedDict 就能搞定from collections import OrderedDict class LRUCache: def __init__(self, capacity): self.capacity capacity self.cache OrderedDict() self.hits 0 self.misses 0 def access(self, key): if key in self.cache: self.hits 1 self.cache.move_to_end(key) return True self.misses 1 if len(self.cache) self.capacity: self.cache.popitem(lastFalse) self.cache[key] True return False def hit_rate(self): total self.hits self.misses return self.hits / total if total else 0.0然后构造一个混合访问序列80 个热点数据编号 0-79被反复访问中间穿插一次顺序扫描编号 1000-1199缓存容量设为 100。访问序列大概是这样的import random def generate_workload(): workload [] # 热点数据反复访问 for _ in range(2000): workload.append(random.randint(0, 79)) # 中间插入一次顺序扫描 for i in range(1000, 1200): workload.append(i) # 继续访问热点数据 for _ in range(2000): workload.append(random.randint(0, 79)) return workload跑下来 LRU 的命中率大概在 78% 左右而如果去掉中间那次顺序扫描命中率能到 95% 以上。也就是说一次顺序扫描直接把命中率拉低了 17 个百分点。这个差距在真实系统里就是数据库 QPS 翻倍、响应时间翻倍的差别。2.2 为什么 LRU 会被一次性数据带偏LRU 的淘汰逻辑是最近最久未使用的先走它隐含了一个假设访问时间越近未来被访问的概率越大。这个假设在强局部性场景下没问题比如热点数据被反复访问LRU 能很好地保留它们。但顺序扫描的数据有一个特点每个数据只被访问一次之后再也不用了。这些数据在 LRU 链表里会不断往头部挤把真正的热点数据往尾部推最终挤出缓存。更麻烦的是LRU 对访问频率完全不敏感。一个数据被访问了 1000 次另一个数据只被访问了 1 次只要后者比前者更晚被访问LRU 就会优先淘汰前者。这在访问模式稳定的时候问题不大但一旦出现突发性的冷数据访问LRU 就会做出错误的淘汰决策。我用一个更极端的例子来说明缓存容量 10访问序列是1,2,3,4,5,6,7,8,9,10,11,1,2,3,4,5。前 10 次访问把缓存填满第 11 次访问淘汰 1然后访问 1 时未命中淘汰 2访问 2 时未命中……最终 1-5 全部未命中。如果缓存容量是 11这 5 次访问就全部命中。这就是 LRU 的顺序扫描退化缓存容量刚好比工作集小一点的时候命中率会断崖式下跌。2.3 命中率崩塌的完整排查链路在实际项目里遇到缓存命中率暴跌我一般按这个顺序排查先看监控曲线命中率是缓慢下降还是断崖式下跌缓慢下降通常是工作集增长断崖式下跌通常是出现了新的访问模式。再看访问日志抽样最近 10 分钟的缓存访问记录统计 key 的访问频次分布。如果出现大量只访问一次的 key基本可以确定是顺序扫描或冷数据批量导入。定位来源根据 key 的前缀或业务标识找到是哪个接口或哪个任务在批量访问。常见的有离线任务全表扫描、运营后台导出数据、新用户首次登录加载全量配置。验证假设临时把这些批量访问的 key 排除掉看命中率是否恢复。如果恢复说明就是缓存污染。选择方案要么在业务层隔离批量访问走独立缓存或直接回源要么在缓存层换淘汰策略LRU 换 LIRS 或 ARC。这个排查链路我走过好几次最坑的一次是某个离线任务每小时跑一次全量扫描每次跑完缓存命中率要花 20 分钟才能恢复。后来把离线任务的缓存单独隔离问题就解决了。但如果隔离成本太高换 LIRS 就是更优雅的方案。3. LIRS 的核心机制用复用距离替代访问时间3.1 复用距离LIRS 的度量衡LIRS 的核心概念是复用距离Reuse Distance定义是同一个数据块两次连续访问之间访问了多少个不同的数据块。举个例子访问序列是A, B, C, AA 的复用距离就是 2中间隔了 B 和 C。复用距离越短说明这个数据被访问得越频繁越应该留在缓存里。LIRS 把数据分成两类LIRLow Inter-reference Recency复用距离短的数据是缓存的核心保留对象。HIRHigh Inter-reference Recency复用距离长的数据是缓存的临时住户。LIRS 的缓存空间被划分为两部分LIR 区通常占 99% 左右和 HIR 区占 1% 左右。LIR 区的数据是铁定保留的HIR 区的数据是随时可淘汰的。当 HIR 区的数据被再次访问时如果它的复用距离足够短就会被提升为 LIR同时把 LIR 区里复用距离最长的数据降级为 HIR。这个机制的精妙之处在于顺序扫描的数据只会进入 HIR 区不会污染 LIR 区。因为顺序扫描的数据复用距离是无穷大只访问一次它们只能在 HIR 区里短暂停留很快就被淘汰。而热点数据因为复用距离短会被提升到 LIR 区得到保护。3.2 LIRS 栈怎么在有限空间里追踪复用距离理论上要精确计算复用距离需要记录每个数据块的所有历史访问记录空间开销太大。LIRS 用了一个巧妙的近似方法维护一个LIRS 栈栈里只保留最近访问的数据块栈顶是最近访问的栈底是最久未访问的。当一个数据块被访问时它在栈里的位置就反映了它的复用距离——位置越靠近栈顶复用距离越短。但 LIRS 栈不能无限大否则空间开销还是太高。实际实现里LIRS 栈的大小通常是缓存容量的数倍比如 3-5 倍只保留最近访问的数据块。栈里不在缓存中的数据块只记录它们的状态是 LIR 还是 HIR不记录实际数据。这里有一个关键细节LIRS 栈里同时包含 LIR 和 HIR 数据块但只有 LIR 数据块会被锁定在栈里。当一个 HIR 数据块从栈里被挤出时如果它还在缓存里就会被淘汰如果它已经不在缓存里就只是从栈里移除。这个机制保证了 LIR 数据块的复用距离信息不会被 HIR 数据块冲掉。3.3 LIR 与 HIR 的动态转换什么时候提升什么时候降级LIRS 的动态转换规则是整套机制里最需要理解清楚的部分。我把它拆成几个场景场景一访问一个不在缓存里的数据块如果缓存没满直接放入 HIR 区。如果缓存满了淘汰 HIR 区里最久未访问的数据块把新数据块放入 HIR 区。如果新数据块在 LIRS 栈里的位置足够靠前复用距离短把它提升为 LIR同时把 LIR 区里栈位置最靠后的数据块降级为 HIR。场景二访问一个在缓存里的 HIR 数据块如果它在 LIRS 栈里的位置足够靠前提升为 LIR同时降级一个 LIR 数据块。如果位置不够靠前保持在 HIR 区但更新它在栈里的位置。场景三访问一个在缓存里的 LIR 数据块直接命中更新它在 LIRS 栈里的位置。这套规则的核心逻辑是LIR 区的容量是固定的HIR 区的数据要竞争才能进入 LIR 区。竞争的标准就是复用距离复用距离短的数据胜出。这样就避免了 LRU 那种谁最近被访问谁就留下的盲目性。4. 手写一个可运行的 LIRS 缓存从数据结构到调参4.1 数据结构选型为什么用双向链表加字典实现 LIRS 需要几个核心数据结构LIRS 栈用双向链表实现支持 O(1) 的插入、删除、移动操作。栈里存储数据块的 key 和状态LIR/HIR。缓存区用字典实现key 到实际数据的映射。LIR 区和 HIR 区分别用两个字典或一个字典加状态标记。栈位置索引用字典记录每个 key 在 LIRS 栈里的节点引用方便 O(1) 定位。这里有一个容易踩的坑LIRS 栈里可能包含不在缓存里的数据块。因为栈的大小比缓存大有些数据块已经被淘汰出缓存了但还在栈里保留着复用距离信息。所以栈节点和缓存条目是两套独立的生命周期不能混在一起管理。4.2 核心操作的伪代码与 Python 实现先看访问操作的完整逻辑class LIRSCache: def __init__(self, capacity, stack_ratio3): self.capacity capacity self.lir_capacity max(1, int(capacity * 0.99)) self.hir_capacity capacity - self.lir_capacity self.stack_size capacity * stack_ratio self.cache {} # key - data self.key_status {} # key - LIR or HIR self.stack OrderedDict() # key - None, 栈顶在末尾 self.hits 0 self.misses 0 def _update_stack(self, key): if key in self.stack: self.stack.move_to_end(key) else: self.stack[key] None if len(self.stack) self.stack_size: self.stack.popitem(lastFalse) def _evict_hir(self): for k in list(self.stack.keys()): if self.key_status.get(k) HIR and k in self.cache: del self.cache[k] del self.key_status[k] return k return None def _demote_lir(self): for k in list(self.stack.keys()): if self.key_status.get(k) LIR: self.key_status[k] HIR return k return None def access(self, key, dataNone): if key in self.cache: self.hits 1 self._update_stack(key) if self.key_status[key] HIR: # 检查是否提升为 LIR stack_pos list(self.stack.keys()).index(key) if stack_pos len(self.stack) - self.lir_capacity: self.key_status[key] LIR self._demote_lir() return self.cache[key] self.misses 1 self._update_stack(key) if len(self.cache) self.capacity: self._evict_hir() self.cache[key] data self.key_status[key] HIR return data这段代码是简化版实际生产环境还需要处理并发、过期时间、统计指标等。但核心逻辑已经完整了访问时更新栈位置HIR 数据块根据栈位置决定是否提升缓存满时优先淘汰 HIR 数据块。4.3 参数调优LIR 比例和栈大小怎么定LIRS 有两个关键参数LIR 区比例和LIRS 栈大小。LIR 区比例默认是 99%这个值在大多数场景下都合适。如果访问模式里热点数据占比很高比如 90% 以上的访问都集中在 10% 的数据上可以适当降低 LIR 比例到 95%给 HIR 区更多空间减少提升/降级的频率。如果访问模式比较均匀热点数据占比不高可以保持 99% 甚至提高到 99.5%。LIRS 栈大小默认是缓存容量的 3 倍。栈越大复用距离的估计越准确但空间开销也越大。实测下来3 倍是一个比较平衡的值。如果内存非常紧张可以降到 2 倍命中率会下降 1-2 个百分点。如果内存充裕可以提到 5 倍命中率提升不明显但栈操作的延迟会略微增加。这里有一个经验值LIRS 栈大小不要超过缓存容量的 10 倍否则栈操作本身的开销会抵消命中率带来的收益。另外栈大小最好是缓存容量的整数倍方便做内存预分配。5. LIRS 与 LRU、ARC、LFU 的选型对比什么场景该用哪个5.1 四种策略的横向对比策略核心思想优点缺点适用场景LRU最近最少使用实现简单强局部性场景命中率高顺序扫描下退化严重访问模式稳定的热点缓存LFU最少使用频率对频率敏感抗扫描频率统计开销大新数据难进入访问频率差异大的场景ARC自适应调整 LRU 和 LFU 比例自适应综合表现好实现复杂参数多访问模式多变的通用场景LIRS复用距离抗扫描命中率高实现复杂栈开销大有顺序扫描的混合访问场景从实测数据看在纯热点访问场景下LRU 和 LIRS 的命中率差不多都在 95% 以上。但在混合了顺序扫描的场景下LRU 命中率掉到 78%LIRS 还能保持 89%ARC 大概在 86% 左右。如果顺序扫描占比更高比如 30% 的访问是扫描LRU 会掉到 60% 以下LIRS 还能维持在 82% 左右。5.2 选型决策树三步确定用哪个第一步看访问模式。如果访问模式非常稳定热点数据固定LRU 就够了没必要上 LIRS。如果访问模式里有明显的顺序扫描或冷数据批量访问优先考虑 LIRS 或 ARC。第二步看实现成本。LRU 用现成的库就行LIRS 需要自己实现或找第三方库。如果团队没有精力维护复杂的缓存逻辑ARC 是更稳妥的选择它的自适应机制能覆盖大多数场景。第三步看内存预算。LIRS 的栈需要额外内存通常是缓存容量的 3 倍。如果内存非常紧张LFU 的计数开销可能更小但 LFU 需要定期衰减频率计数否则新数据永远进不来。我个人的经验是如果缓存命中率对业务影响很大比如直接影响 QPS 和延迟而且访问模式里有扫描直接上 LIRS。如果只是普通的本地缓存LRU 足够。ARC 适合那种不确定访问模式会不会变的场景它的自适应机制能兜底。5.3 一个真实的选型翻车案例之前有个项目缓存用的是 LRU平时命中率 90% 左右。后来加了一个新功能每天凌晨跑一次全量数据同步同步过程中会顺序读取所有数据。结果每天凌晨缓存命中率掉到 50% 以下持续 30 分钟。一开始想用 LIRS 解决但评估后发现 LIRS 的栈开销太大这个服务的缓存条目有上千万栈内存扛不住。最后用的方案是缓存隔离全量同步走独立的缓存实例和在线业务的缓存物理隔离。同步完成后独立缓存直接销毁。这样在线业务的缓存完全不受影响命中率稳定在 90% 以上。这个案例说明换淘汰策略不是唯一解业务层隔离有时候成本更低。6. 落地 LIRS 时的五个坑从栈溢出到并发安全6.1 栈溢出LIRS 栈不是越大越好LIRS 栈的大小直接决定了内存开销。我见过一个实现栈大小设成了缓存容量的 10 倍结果缓存本身占 1GB栈又占了 10GB直接把服务撑爆了。栈里每个节点至少需要存储 key 和前后指针如果 key 是字符串开销更大。正确的做法是先估算缓存条目的平均 key 大小再乘以栈大小得到栈的内存开销。如果栈开销超过缓存本身的 50%就要考虑降低栈大小或者改用 ARC 这种不需要额外栈的策略。另外栈里可以只存 key 的哈希值而不是完整 key这样能省不少内存但会有哈希冲突的风险需要额外处理。6.2 并发安全读写锁的粒度怎么控制LIRS 的访问操作会修改栈和缓存区必须加锁。但锁的粒度很关键如果整个缓存一把大锁高并发下会成为瓶颈如果每个条目一把锁又会有死锁风险。我的做法是分段锁把缓存分成 N 个段每个段独立加锁。访问时根据 key 的哈希值定位到段只锁这个段。段的数量通常是 CPU 核数的 2-4 倍。这样既能保证并发性能又能避免死锁。需要注意的是LIRS 栈的更新操作可能涉及跨段的数据块比如提升 LIR 时需要降级另一个段里的 LIR这时候需要按固定顺序加锁避免死锁。6.3 命中率统计别被平均值骗了命中率是一个平均值指标它会把不同时间段的命中率平均掉。如果缓存命中率是 85%但其中 80% 的时间是 95%20% 的时间是 30%那这个 85% 就有很大的误导性。我在监控里会同时看命中率的 P50、P95、P99以及命中率的滑动窗口曲线。另外要区分全局命中率和热点数据命中率。全局命中率可能被大量冷数据访问拉低但热点数据的命中率才是业务真正关心的。我通常会把访问频次前 10% 的 key 单独统计命中率这个指标更能反映缓存的实际效果。6.4 冷启动新服务上线时怎么快速预热LIRS 在冷启动时表现不如 LRU因为它的 LIR 区需要时间才能学习到哪些是热点数据。新服务刚上线时缓存是空的所有数据都进 HIR 区命中率会很低。预热的方法有两种一是离线预热从历史访问日志里提取热点 key服务启动时批量加载二是在线预热服务启动后先放少量流量进来让 LIRS 自己学习等命中率稳定后再逐步加大流量。我一般用离线预热从过去 7 天的访问日志里提取访问频次前 20% 的 key启动时加载到缓存里。这样冷启动时间能从 30 分钟缩短到 5 分钟以内。6.5 数据一致性淘汰和更新的顺序问题LIRS 淘汰数据时如果数据正在被更新可能会出现淘汰了旧数据但新数据还没写入的空窗期。这个空窗期里其他请求访问这个 key 会缓存未命中回源查到旧数据又写回缓存导致数据不一致。解决方法是淘汰和更新加同一把锁或者用版本号机制每个缓存条目带一个版本号更新时版本号加一淘汰时检查版本号是否变化。如果变化了说明数据已经被更新不能直接淘汰。这个机制会增加一些开销但在数据一致性要求高的场景下是必要的。7. 从 LIRS 到自适应缓存后续可以怎么扩展LIRS 解决了 LRU 在顺序扫描下的退化问题但它本身也有局限LIR 区比例是固定的不能根据访问模式动态调整。如果访问模式发生变化比如热点数据突然变多固定的 LIR 比例可能不是最优的。一个自然的扩展方向是自适应 LIRS根据命中率和访问模式的变化动态调整 LIR 区比例。比如命中率下降时增大 LIR 区比例保护更多热点数据命中率稳定时减小 LIR 区比例给 HIR 区更多空间。这个思路和 ARC 的自适应机制类似但 ARC 调整的是 LRU 和 LFU 的比例自适应 LIRS 调整的是 LIR 和 HIR 的比例。另一个方向是分层 LIRS把缓存分成多层每层用不同的 LIR 比例。热数据层用高 LIR 比例冷数据层用低 LIR 比例。访问时先查热数据层未命中再查冷数据层。这样既能保护热点数据又能利用冷数据的复用距离信息。这个思路在 CPU 缓存里已经有类似的设计多级缓存搬到应用层缓存也是可行的。我在实际项目里试过自适应 LIRS实现复杂度比固定 LIRS 高不少但命中率在访问模式变化时确实更稳定。如果你们的业务访问模式经常变化可以考虑这个方向。如果访问模式比较稳定固定 LIRS 就够了没必要过度设计。最后分享一个我在调参时的小技巧先用 LRU 跑一周收集访问日志离线模拟 LIRS 的命中率。如果模拟下来 LIRS 比 LRU 高 5 个百分点以上再考虑上线 LIRS如果差距不大说明访问模式里扫描占比不高LRU 就够了。这样能避免盲目上线复杂策略带来的维护成本。