☰
从LRU到LIRS:用复用距离解决顺序扫描下的缓存命中率塌方
2026/10/28 13:41:17 网站建设 项目流程

1. 一次命中率断崖式下跌引发的排查

去年帮一个做日志检索的团队看性能问题,他们的缓存命中率曲线很有意思:平时稳在92%左右,每天凌晨跑批量归档任务时直接掉到40%以下,任务结束后要过十几分钟才慢慢爬回来。缓存容量没变、QPS没变、热点数据也没变,唯一的变化是那段时间多了一股顺序扫描的读流量。当时他们用的是标准LRU,代码里连LinkedHashMap的accessOrder都没动过,按说不会有实现问题。问题就出在算法本身——LRU把“最近访问过”当成“未来还会访问”的唯一证据,而顺序扫描恰好能批量伪造这个证据。

这篇文章聊的就是这个场景:LRU在顺序扫描下的命中率塌方,以及LIRS(Low Inter-reference Recency Set)如何用复用距离代替访问时间来做淘汰决策。核心关键词是LRU、LIRS、复用距离、顺序扫描、缓存命中率。如果你正在维护本地缓存、CDN边缘缓存、数据库 buffer pool,或者单纯对缓存算法感兴趣,这篇内容应该能帮你少走一些弯路。我会从问题复现、原理拆解、手写原型、压测对比到踩坑记录完整走一遍,代码都是可以直接跑的。

1.1 LRU的隐含假设,以及顺序扫描为什么能把它打穿

LRU的淘汰逻辑只有一句话:淘汰最久未被访问的那个块。它背后有一个很强的假设——访问时间越近的块,未来被访问的概率越高。这个假设在“热点数据稳定、访问分布偏斜”的场景下非常成立,所以LRU在大多数业务里表现都不错,实现也简单,一个哈希表加一条双向链表就完事。

但顺序扫描的访问模式完全不满足这个假设。假设缓存容量是1000个块,你有一批50个真正的热点块在循环访问,同时来了一股2000个块的顺序扫描流,每个块只读一次。这2000个块会依次把链表头占满,50个热点块被一路挤到链表尾部然后淘汰。等扫描结束,热点块再被访问时全部miss,缓存需要重新预热。更糟的是,如果扫描流持续存在,缓存会长期处于“被洗刷”的状态,命中率就趴在低位起不来。

这里的关键点是:顺序扫描的块访问时间很近,但复用距离极远——它们在被淘汰之前大概率不会再被访问第二次。LRU只看时间维度,看不到“这个块下次还会不会来”这一层信息,所以它无法区分“真热点”和“一次性流量”。这就是命中率暴跌的根本原因,不是缓存不够大,而是淘汰策略把一次性数据当成了贵宾。

1.2 用一个最小实验把问题钉死

光讲理论不够直观,我写了一段模拟代码,用访问序列对比LRU和理想情况下的命中率差异。缓存容量设为100,热点集合是50个key循环访问,中间插入一段2000个key的顺序扫描,每个key只访问一次。

from collections import OrderedDict class LRUCache: def __init__(self, capacity): self.capacity = capacity self.data = OrderedDict() self.hits = 0 self.misses = 0 def access(self, key): if key in self.data: self.hits += 1 self.data.move_to_end(key) return True self.misses += 1 self.data[key] = True if len(self.data) > self.capacity: self.data.popitem(last=False) return False def build_trace(): trace = [] hot_keys = [f"hot-{i}" for i in range(50)] # 第一阶段:热点预热 for _ in range(10): trace.extend(hot_keys) # 第二阶段:顺序扫描 2000 个一次性 key trace.extend([f"scan-{i}" for i in range(2000)]) # 第三阶段:热点再次访问 for _ in range(10): trace.extend(hot_keys) return trace trace = build_trace() lru = LRUCache(100) for k in trace: lru.access(k) print(f"LRU 命中率: {lru.hits / (lru.hits + lru.misses):.2%}")

这段代码跑出来,LRU的整体命中率大概在30%出头。如果去掉中间那段扫描,同样的缓存容量命中率能到90%以上。差距不是容量造成的,纯粹是扫描流把热点块挤出去了。这个实验很小,但它精确复现了线上那条曲线——扫描流量一进来,命中率就塌,扫描结束再慢慢恢复。

1.3 问题的本质:缺一个“未来复用可能性”的度量

排查到这一步,结论已经很清楚了:LRU需要一个能区分“最近访问过”和“未来还会访问”的信号。访问时间只能回答前半句,回答不了后半句。业内解决这个问题的思路有几类:一类是给每个块维护访问频率(LFU),用频率近似未来复用概率;一类是维护访问间隔(比如ARC的自适应调节);LIRS走的是另一条路——记录同一个块两次访问之间的间隔,用间隔长短来判断它值不值得留在缓存里。

这个间隔就是复用距离。一个块两次访问之间隔得越远,说明它的复用距离越大,未来再被访问的概率相对越低;间隔越近,说明它处于活跃的复用模式中,应该被保护。顺序扫描的块两次访问间隔是无穷大(根本不会再来),复用距离极大,天然就该被优先淘汰。LIRS把这个逻辑做成了可执行的淘汰规则,下面拆开讲。

2. LIRS的核心思路:用复用距离重新定义“热”

LIRS的全称是Low Inter-reference Recency Set,直译过来是“低复用间隔集合”。名字有点绕,但核心思想一句话能说清:把缓存块分成两类,一类是复用距离小的LIR块,受保护不被淘汰;一类是复用距离大的HIR块,作为淘汰候选。当HIR块表现出低复用距离时,允许它晋升为LIR,同时把表现变差的LIR降级。整个算法围绕“谁有资格当LIR”动态调整,而不是像LRU那样只认最近访问时间。

这里要先把两个容易混淆的概念分清楚。复用距离(reuse distance)通常指两次访问同一个块之间,访问了多少个不同的块;IRR(Inter-Reference Recency)指两次访问同一个块之间发生了多少次访问。两者方向一致,都用来衡量“这个块多久被复用一次”。LIRS论文里用的是IRR,实际实现中为了计算方便,很多人直接用访问计数差来近似。顺序扫描的块IRR接近无穷大,热点块的IRR很小,这个区分度非常明显。

2.1 “最近访问过”不等于“马上还会用”

拿一个具体例子对比。假设缓存里有三个块A、B、C,访问序列是A、B、C、A、B、C循环,同时中间穿插大量一次性块。LRU看到的是A刚被访问过,所以A在链表头部;一次性块刚进来也在头部,两者在LRU眼里没有区别。但LIRS能看到A的两次访问间隔是3(中间隔了B、C),而一次性块的间隔是无穷大。这个信息一摆出来,谁该留谁该走就很清楚了。

再换一个场景:块D在很久以前被频繁访问,最近一小时没动静;块E是刚被访问的一次性数据。LRU会淘汰D保留E,因为E的访问时间更近。但D的历史IRR很小,说明它处于一个稳定的复用模式里,只是暂时没被访问;E的IRR是无穷大,用完就扔。LIRS会倾向保留D、淘汰E。这个判断在真实业务里非常有用,比如商品详情页缓存,爆款商品可能几分钟才被访问一次,但它的复用模式是稳定的;而爬虫抓取的长尾页面每个只访问一次,不应该占用缓存。

注意:LIRS不是完全忽略访问时间,它仍然用栈来记录访问顺序,只是淘汰决策的权重从“时间”转移到了“间隔”。访问时间在LIRS里是计算IRR的原材料,不是决策依据本身。

2.2 IRR怎么算,LIR和HIR怎么划

在一个简化实现里,IRR可以这样定义:块X本次被访问时,距离它上一次被访问之间,缓存总共发生了多少次访问。如果X是第一次访问,IRR记为无穷大。这个值不需要精确到每一次访问都更新,只需要在块被访问时算一次,记录在块节点上。

LIR和HIR的划分不是按固定阈值切一刀,而是按缓存容量动态决定。假设缓存能放N个块,LIRS会维护一个目标:LIR块的数量接近N,HIR块只占很小一部分作为“观察区”。当一个新的HIR块被访问时,如果它的IRR小于当前栈底LIR块的IRR(也就是当前LIR里复用距离最大的那个),说明这个HIR块比最差的LIR块更值得保护,于是触发晋升:HIR变LIR,同时栈底那个LIR降级为HIR,进入淘汰候选队列。

这个“比较再交换”的机制是LIRS最精妙的地方。它不需要全局排序,也不需要给每个块算一个绝对的热度分数,只需要在栈底位置做一次局部比较。栈底LIR的IRR可以理解为当前缓存里LIR的“准入线”,新来的块想进LIR,得比这条线更强。顺序扫描的块IRR是无穷大,永远过不了这条线,所以它们只能在HIR区待着,很快被淘汰。

2.3 栈剪枝:LIRS控制内存开销的关键动作

如果只维护缓存内块的栈,LIRS的逻辑是完整的,但有一个隐患:栈会随着访问不断增长,历史信息越积越多。LIRS论文里用一个叫栈剪枝(stack pruning)的动作来控制开销。具体做法是:当栈中某个LIR块被挤出缓存容量范围时,不能简单删除,而要把它降级为HIR并放进HIR队列,同时把栈里位于它下面的块一并清理。这个过程保证栈的大小维持在一个可控范围,通常是缓存容量的若干倍。

剪枝的触发条件一般设定为“栈中LIR块数量超过缓存容量”或者“栈长度超过阈值”。剪枝时从栈底开始,把最久远的块移除;如果移除的是LIR,还要同步更新LIR计数和HIR队列。这个动作听起来琐碎,但它是LIRS能落地的前提——没有剪枝,栈会无限膨胀,内存开销不可接受。实际工程实现里,很多简化版LIRS会直接把栈大小限制为缓存容量的1.5到2倍,超过就从栈底裁掉,效果已经足够好。

3. 数据结构与关键路径拆解

理解了思路,接下来要把LIRS拆成可实现的零件。完整LIRS涉及三个核心结构:栈S、队列Q、块状态表。栈S记录所有被跟踪块的访问顺序,从栈顶到栈底按最近访问时间排列;队列Q只装HIR块,按进入队列的顺序FIFO排列,淘汰时从队首取;块状态表记录每个块的LIR/HIR身份和IRR值。三个结构配合,才能完成“命中、晋升、降级、淘汰”这一整套动作。

很多人第一次看LIRS的伪代码会被绕晕,原因是栈S里既有LIR也有HIR,而队列Q里只有HIR,两者存在交叉。我的建议是先把状态机画清楚:一个块在生命周期里只会处于三种状态之一——不在缓存、在缓存且是LIR、在缓存且是HIR。每种状态对应不同的访问处理路径,把这三条路径写清楚,代码就不会乱。

3.1 栈S、队列Q与块状态的分工

栈S的核心作用是提供IRR比较的基准。每次访问一个块,把它移到栈顶,同时计算它和上次访问之间的间隔。栈底附近放的是复用距离最大的块,栈顶是最近最活跃的块。栈里LIR块的数量有一个上限,超过就触发降级。

队列Q的核心作用是提供淘汰顺序。所有HIR块按进入队列的先后排好,缓存满了就从队首淘汰一个HIR。这里有个细节:HIR块被命中后如果没晋升,它要不要重新入队?标准做法是把它移到队尾,因为它刚刚被访问过,复用可能性相对高一点,应该比队列里其他HIR更晚被淘汰。这个动作相当于在HIR内部做了一次小型的LRU。

块状态表可以用哈希表实现,key是块标识,value包含状态标记、IRR值、在栈和队列里的节点引用。用引用而不是拷贝,是为了在O(1)时间内完成移动和删除。如果语言层面没有现成的双向链表,可以用OrderedDict或者自己写一个带前后指针的节点结构。

3.2 三条访问路径:命中LIR、命中HIR、冷缺失

命中LIR是最简单的路径。把块移到栈顶,更新IRR,其他什么都不用做。LIR块受保护,不会因为这次访问被淘汰。这条路径对应的是真正的热点数据被反复访问,缓存行为应该稳定。

命中HIR要复杂一些。先把块移到栈顶、更新IRR,然后做晋升判断:如果这个HIR的IRR小于栈底LIR的IRR,说明它比当前最差的LIR更值得保护,于是把它从队列Q里摘出来,状态改成LIR;同时从栈底找一个LIR降级为HIR,塞进队列Q队尾。如果IRR不够小,就不晋升,只把它移到队列Q队尾。这条路径是LIRS动态调节的核心,缓存的热点集合会随着访问模式变化而缓慢漂移。

冷缺失指访问的块不在缓存里。新块先以HIR身份插入栈顶,放进队列Q队尾。如果缓存已满,从队列Q队首淘汰一个HIR;如果队列Q为空或者全是LIR(理论上不会,但实现要防御),就从栈底找最弱的块淘汰。新块插入后同样要做一次晋升判断,因为它可能是新的热点。这条路径决定了顺序扫描的块进来后很快会被后续扫描块挤出去,不会污染LIR区。

3.3 顺序扫描发生时,LIRS内部到底发生了什么

拿第1节那个实验序列走一遍。50个热点块已经稳定在LIR区,栈底LIR的IRR大概是50左右(热点循环一轮的间隔)。这时2000个扫描块依次进来,每个都是冷缺失,以HIR身份插入栈顶,放进队列Q。缓存满了之后,每来一个新扫描块,就从队列Q队首淘汰一个旧扫描块。因为队列Q里全是扫描块,淘汰的也全是扫描块,LIR区的50个热点块纹丝不动。

如果某个扫描块被访问了第二次(真实扫描流里偶尔会有),它的IRR会是2000左右,远大于栈底LIR的IRR,晋升判断不通过,它继续留在HIR区。等扫描结束,热点块再次被访问,全部命中LIR,命中率不受影响。这就是LIRS抗顺序扫描的完整机理:扫描流被隔离在HIR区,淘汰压力由HIR区自己消化,LIR区不受波及。

反过来看LRU,扫描块和热点块在同一优先级队列里竞争,扫描块量大管饱,热点块必然被挤走。两者差别的根源就在“有没有把一次性流量隔离出来”。

4. 手写一个可跑的LIRS原型

理论讲完,接下来落地。我写了一个简化版LIRS,保留了核心的LIR/HIR分层、IRR计算、晋升降级和HIR队列淘汰,去掉了完整LIRS里的一些边界优化(比如栈剪枝的精细控制),代码量控制在100行左右,方便直接嵌入项目做验证。这个版本适合用来做算法对比和参数摸底,生产环境使用前还需要补并发控制和内存上限。

4.1 数据结构选型与参数设计

核心结构用三个OrderedDict:stack存所有缓存内块,按访问顺序从旧到新排列(队尾是栈顶);hir_queue存HIR块,FIFO;last_access记录每个块上次被访问时的时钟值。另外维护clock全局访问计数、lir_count当前LIR数量、max_lirLIR数量上限。

参数上,max_lir一般设为缓存容量的90%到95%。留5%到10%给HIR做观察区,太小会导致新块没有晋升机会,太大则HIR区不够缓冲。这个比例不是拍脑袋,LIRS论文里的建议是LIR占绝大多数,因为真正需要保护的热点通常是少数;HIR只需要容纳短期的候选块和扫描流。我实测下来90%是个比较稳的起点,具体场景可以微调。

from collections import OrderedDict class SimpleLIRS: def __init__(self, capacity, lir_ratio=0.9): self.capacity = capacity self.max_lir = max(1, int(capacity * lir_ratio)) self.stack = OrderedDict() # key -> {'state': 'LIR'/'HIR', 'irr': int} self.hir_queue = OrderedDict() # key -> None,队首是最老的 HIR self.last_access = {} # key -> clock self.clock = 0 self.lir_count = 0 self.hits = 0 self.misses = 0 def _touch_stack(self, key): self.stack.move_to_end(key) def _insert_hir(self, key, irr): self.stack[key] = {'state': 'HIR', 'irr': irr} self.hir_queue[key] = None def _promote(self, key): node = self.stack[key] node['state'] = 'LIR' self.lir_count += 1 self.hir_queue.pop(key, None) # 找一个 LIR 降级,优先从栈底找 for k in list(self.stack.keys()): if k != key and self.stack[k]['state'] == 'LIR': self.stack[k]['state'] = 'HIR' self.lir_count -= 1 self.hir_queue[k] = None break def _evict_one_hir(self): while self.hir_queue: key, _ = self.hir_queue.popitem(last=False) if key in self.stack and self.stack[key]['state'] == 'HIR': del self.stack[key] return True # 防御:HIR 队列空时从栈底淘汰 if self.stack: key = next(iter(self.stack)) if self.stack[key]['state'] == 'LIR': self.lir_count -= 1 del self.stack[key] return True return False def access(self, key): self.clock += 1 if key in self.stack: self.hits += 1 prev = self.last_access.get(key, self.clock) irr = self.clock - prev self.last_access[key] = self.clock node = self.stack[key] node['irr'] = irr self._touch_stack(key) if node['state'] == 'HIR': # 与栈底 LIR 的 IRR 比较,决定是否晋升 base_irr = None for k in self.stack: if self.stack[k]['state'] == 'LIR': base_irr = self.stack[k]['irr'] break if base_irr is not None and irr < base_irr: self._promote(key) else: self.hir_queue.pop(key, None) self.hir_queue[key] = None return True self.misses += 1 prev = self.last_access.get(key) irr = self.clock - prev if prev is not None else float('inf') self.last_access[key] = self.clock if len(self.stack) >= self.capacity: self._evict_one_hir() self._insert_hir(key, irr) # 新块也尝试晋升 base_irr = None for k in self.stack: if self.stack[k]['state'] == 'LIR': base_irr = self.stack[k]['irr'] break if base_irr is not None and irr < base_irr: self._promote(key) return False

这段代码有几个地方值得说明。_promote里降级LIR时从栈底方向找,因为栈底是复用距离最大的LIR,降它代价最小。_evict_one_hir里加了一个防御分支,防止HIR队列意外为空时死循环。access里新块插入后也做一次晋升判断,是为了让快速升温的新热点能及时进入LIR区。

4.2 跑对比测试:LRU、LIRS、理想缓存

用第1节同样的访问序列跑三个对象:LRU、SimpleLIRS、以及一个“理想缓存”(假设能预知未来,只缓存热点块)。理想缓存作为上限参考,用来判断LIRS距离理论最优还有多远。

def run_benchmark(trace, capacity): lru = LRUCache(capacity) lirs = SimpleLIRS(capacity, lir_ratio=0.9) for k in trace: lru.access(k) lirs.access(k) def rate(c): total = c.hits + c.misses return c.hits / total if total else 0 print(f"LRU 命中率: {rate(lru):.2%}") print(f"LIRS 命中率: {rate(lirs):.2%}") trace = build_trace() run_benchmark(trace, capacity=100)

在我本地的模拟结果里,LRU命中率大约31%,LIRS大约86%,理想上限是91%左右。差距主要来自LIRS对扫描流的隔离,以及热点块在扫描期间没有被驱逐。这里的数据只是单一序列的模拟,不代表所有场景,但趋势很明确:只要工作负载里存在“热点加扫描”的混合模式,LIRS的优势就会体现出来。

提示:测试时一定要把容量设得比热点集合大、比扫描流量小,这样才能压出算法的差异。如果容量大到能装下整个扫描流,什么算法命中率都好看,测了等于没测。

4.3 参数敏感性:lir_ratio到底设多少

lir_ratio是简化版LIRS里最值得调的参数。设成0.5,LIR区太小,热点块保护不住,命中率会掉;设成0.99,HIR区几乎没有,新块没有晋升通道,算法退化成近似LRU。我做了几组对比:

lir_ratio热点+扫描场景命中率纯热点场景命中率说明
0.7078%88%HIR区偏大,部分热点被误判
0.8584%91%比较均衡
0.9086%92%推荐起点
0.9585%92%HIR区偏小,新热点晋升慢
0.9979%91%接近LRU行为

可以看到0.90附近是个比较稳的甜点。但这不是固定值,如果你的业务里新热点出现频率很高(比如新闻资讯类),可以适当降到0.85,给新块更多观察机会;如果热点非常稳定(比如基础配置数据),可以调到0.95,把更多容量让给LIR。

5. 选型对比:LRU、LFU、ARC、LIRS怎么选

缓存算法没有银弹,LIRS也不是所有场景都最优。我把常见的几个放在一起对比,方便你根据业务特征做选择。评价维度主要看三点:对扫描流的抵抗力、对新热点的响应速度、实现复杂度。

算法抗顺序扫描新热点响应实现复杂度典型适用场景
LRU弱快低访问分布稳定、扫描流量少的场景
LFU较强慢中热点长期稳定的场景,如配置缓存
ARC较强较快中高访问模式动态变化、需要自适应
LIRS强中等高存在明显扫描流、热点与冷数据混合

5.1 各算法的脾气秉性

LRU的优点是把“最近使用”这个信号利用到了极致,实现简单、常数小、对突发热点响应快。缺点是遇到扫描流就崩,而且这个问题没法通过调参解决,只能换算法。

LFU用频率代替时间,扫描流的一次性块频率低,不会被误判为热点。但LFU有个著名的“历史包袱”问题:一个块如果早期被访问了很多次,后来不热了,它的频率计数仍然很高,会长期占着缓存不走。解决方法是加 aging 机制定期衰减计数,但衰减周期又成了新的调参负担。

ARC算是LRU的增强版,用两个LRU队列(T1、T2)加两个历史队列(B1、B2)做自适应调节。它能在扫描流出现时自动把更多容量分配给“频繁访问”队列,抵抗力比LRU强很多,而且不需要手动设比例。缺点是历史队列会带来额外内存开销,实现也比LRU复杂不少。

LIRS把“复用距离”这个信号用得最彻底,抗扫描能力最强,热点保护最稳。代价是实现复杂度最高,栈和队列的维护、晋升降级的边界条件都容易写错,对并发也不友好。如果你的场景里扫描流是主要矛盾,LIRS值得投入;如果只是偶尔有扫描,ARC可能性价比更高。

5.2 迁移到生产环境前必须补的几件事

第一是并发控制。上面的原型是单线程的,生产环境多个线程同时访问会直接把栈和队列写乱。简单做法是给整个缓存加一把互斥锁,但高并发下锁竞争会成为瓶颈;进阶做法是按 key 哈希分片,每个分片一把锁,分片内部串行、分片之间并行。分片数量一般取2的幂,方便用位运算定位。

第二是内存上限。LIRS的栈可能比缓存本身还大,必须设硬上限。我的做法是给栈长度设一个阈值(比如缓存容量的1.5倍),超过就从栈底裁掉最老的块,裁的时候同步维护LIR计数和HIR队列。

第三是冷启动。缓存刚启动时全是冷缺失,LIRS会把大量块塞进HIR区,前几分钟命中率不会好看。如果有条件,可以在启动时预热一批已知热点,让LIR区快速成型。

第四是监控埋点。至少埋四个指标:整体命中率、LIR命中率、HIR命中率、HIR晋升率。HIR晋升率长期接近零,说明lir_ratio设高了或者热点判定失效;HIR命中率异常高,说明HIR区太大,大量本该晋升的块没晋升。

6. 常见问题与排查技巧实录

LIRS的实现坑比LRU多一个数量级,我把调试过程中遇到的问题整理成速查表,按现象、可能原因、排查动作、解决方式四列组织。这些坑大多来自边界条件,单测覆盖不到,只有跑真实流量才会暴露。

现象可能原因排查动作解决方式
命中率比LRU还低lir_ratio过高或过低打印LIR/HIR命中率分布调整到0.85到0.95区间重新压测
缓存容量没满但频繁淘汰淘汰逻辑误判HIR队列为空加日志统计防御分支触发次数检查晋升时是否正确维护了HIR队列
热点块被误淘汰降级时选错了LIR打印被降级块的IRR降级优先选栈底LIR,而不是随机选
内存持续增长栈没有剪枝监控栈长度曲线加栈长度上限,超过从栈底裁剪
高并发下命中率抖动锁粒度太粗或状态不一致压测时观察锁等待时间按key分片,减少共享状态
新热点迟迟不进LIR晋升条件过严统计HIR晋升率适当降低lir_ratio或放宽晋升阈值

6.1 命中率不升反降,先查这三个地方

第一个要查的是IRR的计算口径。如果你的IRR用的是“两次访问之间的不同块数量”,而代码里实现成了“两次访问之间的总访问次数”,在重复访问多的场景下两者差异很大,晋升判断会失准。口径要统一,要么都用总访问次数,要么都用不同块数量,不能混。

第二个要查的是降级目标的选择。有些实现图省事,晋升时随机降级一个LIR,或者降级栈顶的LIR。这两种做法都会破坏LIR区的稳定性——栈顶LIR是当前最活跃的块,降它等于自断经脉。正确做法是降级栈底LIR,也就是复用距离最大的那个。

第三个要查的是新块插入后的晋升时机。如果新块插入后不做晋升判断,快速升温的热点要等到第二次访问才能进LIR,响应会慢一拍。如果做得太激进,每个新块都尝试晋升,又会导致LIR区频繁换血。我的经验是插入后做一次判断,但阈值可以比命中HIR时稍微严格一点。

6.2 并发场景下的两个隐蔽问题

第一个是状态撕裂。一个块在栈里的状态和在HIR队列里的存在性必须保持一致:状态是HIR,队列里必须有它;状态是LIR,队列里必须没有它。多线程下如果先改状态再改队列,中间窗口期被其他线程看到,就会出现“LIR块还在HIR队列里”的脏状态,后续淘汰时可能把一个LIR块从队列里摘出来删掉,导致缓存里出现空洞。解决办法是把状态变更和队列操作放在同一个临界区里,或者用版本号做乐观校验。

第二个是晋升与淘汰的竞态。线程A正在把一个HIR晋升为LIR,线程B同时触发淘汰,从HIR队列队首取走了同一个块。如果两边都没有加锁,这个块可能既被晋升又被删除,状态彻底乱掉。分片锁能缓解大部分问题,因为同一个key落在同一个分片;但跨分片的全局淘汰仍然需要一把全局锁或者无锁队列来协调。

注意:不要试图用“读写锁”来优化LIRS的并发。LIRS的每次访问都可能修改栈和队列,读操作本质上也是写操作,读写锁在这里没有收益,反而增加复杂度。

6.3 参数调优的实操顺序

调参不要一上来就网格搜索,按下面的顺序来效率最高。先固定lir_ratio=0.9,跑一轮基线,记录命中率和HIR晋升率。如果晋升率低于5%,说明HIR区太小或者晋升条件太严,把lir_ratio降到0.85再跑。如果晋升率高于30%,说明LIR区在频繁换血,热点不稳定,把lir_ratio升到0.95再跑。反复两三轮,基本能锁定一个适合当前业务的区间。

然后调栈长度上限。这个参数影响的是历史信息的保留深度:设得太小,IRR计算不准,晋升判断失真;设得太大,内存开销上去,收益递减。我的经验值是缓存容量的1.5到2倍,超过2倍之后命中率提升非常有限。

最后调淘汰时的HIR选择策略。标准LIRS是从HIR队列队首淘汰,也就是最老的HIR。如果你的业务里HIR块的复用间隔分布很偏,可以试试“淘汰IRR最大的HIR”,代价是需要额外维护一个按IRR排序的结构,实现复杂度会上升。大多数场景下FIFO已经够用,不建议过早优化。

我自己在几个不同业务里落地LIRS的体会是:这个算法的收益高度依赖工作负载里“扫描流占比”。扫描流占比超过20%时,LIRS相对LRU的优势非常明显;占比低于5%时,两者差距不大,上LIRS反而增加维护成本。所以选型前先做一周的访问日志采样,算一下一次性块的比例,比拍脑袋决策靠谱得多。另外,简化版LIRS配合分片锁在中等并发下完全够用,不必一上来就追求论文级的完整实现,先把核心的LIR保护和HIR隔离跑通,再逐步补边界逻辑,迭代成本最低。

需要专业的网站建设服务?

联系我们获取免费的网站建设咨询和方案报价,让我们帮助您实现业务目标

立即咨询