LRU-K 算法

玻尔百科

核心要点

简单的 LRU 缓存会驱逐最近最少使用的页面，这使其极易因缓存污染而导致性能下降。
LRU-K 算法通过考虑最后 K 次访问的历史记录，而不仅仅是最近一次访问，从而对 LRU 进行了改进。
通过跟踪访问历史，LRU-K 能够区分有价值的“热”工作集和来自大规模扫描的瞬时数据，从而保护关键页面。
这种抗扫描能力使 LRU-K 成为一种更稳健、更有效的缓存策略，适用于数据库、操作系统和云服务等实际应用。

引言

在计算机科学领域，效率至关重要。缓存——即将频繁访问的数据存储在一个小而快的内存层中的做法——是高性能系统的基石。一种简单且广为人知的缓存策略是“最近最少使用”（LRU）算法，它会丢弃最长时间未被访问的数据。虽然这种纯粹基于近因性的方法在许多场景下都很有效，但它存在一个致命缺陷：无法区分持续重要的数据和仅属于近期大规模一次性操作的数据。这种脆弱性会导致“缓存污染”，即有价值的数据被瞬时数据冲刷掉，从而降低系统性能。

本文将深入探讨一个更复杂的解决方案：LRU-K 算法。通过引入对过去访问的记忆，LRU-K 提供了一种更智能的方法来判断哪些数据是真正有价值的。

第一章 原理与机制 将剖析 LRU 策略的根本弱点，并引入 LRU-K 的历史视角，解释跟踪第 K 次最近访问如何提供强大的抗缓存污染能力。
第二章 应用与跨学科联系 将探讨这一概念在各个领域的实际影响，从数据库和操作系统的核心功能到现代云基础设施、游戏，乃至物联网系统中的概率建模。

通过这次探索，我们将揭示对访问模式的更深理解如何促成更稳健、更高效的系统设计。

原理与机制

想象一个工作坊。你的工作台上只有少量空间放置工具。你会把哪些工具留在工作台上，又会把哪些放回工具箱？如果你和大多数人一样，你可能会把刚用过的工具放在手边。这个直觉很简单：如果你刚用过螺丝刀，你可能很快会再需要它。这就是计算机科学中一个绝妙简单且出奇有效的思想的精髓：最近最少使用（LRU）缓存策略。

在计算机中，“工作台”是一小块称为缓存的快速内存，“工具”是称为页面的数据块。缓存只能容纳总数据的一小部分，因此系统需要一个规则来决定保留什么和驱逐什么。LRU 的规则是：当缓存已满且需要调入一个新页面时，踢出那个最长时间未被动用过的页面。它优先考虑近因性（recency）。

对于许多任务来说，这非常有效。如果一个程序处理的一小组页面都能轻松地装入缓存，它会访问这些页面，将它们调入缓存，然后每一次后续访问都将是闪电般的“命中”。程序循环使用它最喜欢的 $k$ 个页面，缓存有 $k$ 个页面的空间，命中率接近 100%——这是时间局部性（temporal locality）的完美场景。LRU 似乎是完美而理性的选择。

近因性的“阿喀琉斯之踵”

但是，当我们的近因性直觉将我们引入歧途时会发生什么？如果“最近”不等于“重要”呢？在这里，LRU 优雅的简单性开始暴露出一个深层缺陷。

考虑一个程序，它不是处理一组恰好能放进缓存的页面，而是有条不紊地循环访问一个比缓存略大的页面列表。假设缓存可以容纳 $k=10$ 个页面，但程序正在循环访问页面 $P_1, P_2, \dots, P_{11}$ 。它请求 $P_1$ 到 $P_{10}$ ，填满了缓存。现在它需要 $P_{11}$ 。根据 LRU 规则，系统必须驱逐最近最少使用的页面，那当然是 $P_1$ 。于是， $P_1$ 被踢出以便为 $P_{11}$ 腾出空间。程序接下来请求的页面是什么呢？在它的循环中，又回到了 $P_1$ 。但我们刚把它驱逐了！所以，这是一次“未命中”（miss）。为了把 $P_1$ 重新调入，我们必须驱逐新的 LRU 页面，也就是 $P_2$ 。下一个请求是 $P_2$ ，又是一次未命中。

这种灾难性的模式会无限持续下去。每一次请求都是针对刚刚被扔掉的那个页面。旨在加速的缓存，却处于持续的颠簸（thrashing）状态，命中率惨淡地降为零。该算法正以最愚蠢的方式运行，不是因为它坏了，而是因为它在严格遵守其唯一的简单规则。

这看似一个人为的例子，但它指向了一个更常见、更隐蔽的问题：缓存污染。让我们想象一个更现实的场景。你正在编辑一小组“热”文件——比如说，三个文件 $\{A, B, C\}$ ——它们代表你的核心工作集。你频繁访问它们，LRU 也很乐意地将它们保留在缓存中。然后，你执行一个大型的一次性任务，比如在一百个其他文档 $\{D_1, D_2, \dots, D_{100}\}$ 中搜索一个词。这是一种顺序扫描。

对于 LRU 来说，这些扫描页面是最新、最近使用的项。它尽职地加载 $D_1$ ，然后是 $D_2$ ，以此类推。如果缓存很小，它很快就会开始驱逐较旧的页面来腾出空间。而哪些页面是最旧的呢？正是你宝贵的热点集合！首先 $A$ 被驱逐，然后是 $B$ ，再然后是 $C$ ，它们被一连串只使用一次就再也不会用到的“垃圾”页面所取代。扫描结束后，你回去编辑文件 $A$ 。但它已经不在缓存里了。一次未命中。然后是 $B$ ，又一次未命中。然后是 $C$ ，第三次未命中。这一次性扫描完全污染了缓存，而本应智能的 LRU 算法对这次突发的、最近发生但最终并不重要的活动产生了“过拟合”。

这就是纯粹近因性的根本失败之处：它没有记忆。它无法区分一个长期受欢迎的页面和一个恰好是瞬时爆发活动一部分的页面。

更深层次的智慧：历史的力量

我们如何赋予缓存记忆？我们如何教它区分短暂的趋势和持久的重要性？答案是更深入地审视过去。这就是 LRU-K 算法背后的卓越洞见。

LRU-K 不再只关注唯一的最近访问时间（这正是 LRU，或称 LRU-1，所做的），而是着眼于最后 $K$ 次访问的历史。一个页面的“近因性”不是它最后一次被使用的时间，而是它倒数第 K 次被使用的时间。让我们来看看最简单且通常最有效的版本 LRU-2 是如何工作的。

在 LRU-2 中，我们根据页面的访问历史区别对待它们。

只被访问过一次的页面被视为处于观察期。
被访问过两次或以上的页面证明了其价值，被视为受保护的。

驱逐规则被改变了。当缓存已满时，算法在考虑动用受保护页面之前，总是会选择驱逐一个处于观察期的页面。

让我们用 LRU-2 来重演我们的缓存污染场景。

工作集预热： 你访问你的热点文件 $\{A, B, C\}$ ，然后再次访问它们。它们现在各自都至少有两次引用记录，因此被提升到受保护集合。
扫描开始： 搜索开始，请求页面 $D_1, D_2, \dots$ 。这些页面被加载到缓存中。但由于每个页面只被访问一次，它们都进入了观察期集合。
驱逐时刻： 随着扫描继续，缓存被填满。假设缓存中存有 $\{A, B, C, D_1\}$ ，现在需要加载 $D_2$ 。LRU-2 算法必须选择一个牺牲品。它看到三个受保护的页面（ $A$ , $B$ , $C$ ）和一个观察期页面（ $D_1$ ）。规则很明确：驱逐一个观察期页面。于是， $D_1$ 被踢出，为 $D_2$ 腾出空间。
结果： 随着扫描的进行，扫描页面（ $D_2, D_3, D_4, \dots$ ）被调入，但它们只会驱逐其他的扫描页面。它们在缓存的“观察期”槽位中循环，而受保护的热点工作集 $\{A, B, C\}$ 则安然无恙。当扫描结束，你回到你的工作时， $A$ 、 $B$ 和 $C$ 仍然在那里等着你。所有那些额外的未命中都被避免了。

仅仅通过查看倒数第二次的引用，该算法就获得了一种初级但强大的记忆形式。它现在能够区分长期的兴趣和一时兴起。这就是为什么 LRU-K 及其变体通常被称为抗扫描（scan-resistant）。这个原理非常强大，其性能不仅超越了简单的 LRU，也超越了像 CLOCK 算法这样的 LRU 近似算法，后者也从根本上受制于近因性，同样容易受到大规模扫描的污染。

算法的本质：没有银弹

当然，LRU-K 并非灵丹妙药。它是一个更精密复杂的算法。它需要为每个页面跟踪更多信息（其最后 K 次访问的时间戳），这增加了开销。

此外，它的威力不是无限的。如果污染缓存的扫描相对于缓存大小来说过于庞大，它最终仍然可能冲刷掉“受保护”的页面。如果你的缓存只能容纳 10 个页面，而你对 10,000 个独立页面进行扫描，那么再聪明的驱逐策略也无法保住你原有的工作集。任何缓存算法的有效性都是程序访问模式与可用物理资源之间的一场微妙博弈。

现实世界的系统还会增加更多层次。例如，系统可能会试图变得更聪明，预取（prefetch）它认为你很快会需要的数据，这个过程称为预读（read-ahead）。这些预取的数据也需要缓存空间，系统必须管理它们的驱逐优先级，这为缓存难题增加了另一个维度。

然而，在这些约束之内，从 LRU 的简单直觉到 LRU-K 的历史视角的演进过程，完美地诠释了科学方法。我们从一个简单、优雅的模型开始，测试它并找到其临界点。然后，我们寻求一个更深刻、更稳健的原则——在这个案例中，就是认识到页面的历史比其短暂的过去更能预测其未来价值。其美妙之处不在于找到一个完美的最终答案，而在于不断完善我们的理解，从而产生不仅更正确，而且更具深刻洞见的思想。

应用与跨学科联系

在掌握了区分像 LRU 这样简单的基于近因性的策略和像 LRU-K 这样更细致、具有历史感知能力的策略的原理之后，我们现在可以踏上一段旅程，去看看这些思想在何处焕发生机。页面和指针的抽象舞蹈不仅仅是学术演练；它是驱动我们数字世界的无形引擎，塑造着从用户界面的响应速度到全球互联网架构的方方面面。缓存的逻辑证明了科学与工程中的一个优美原则：通过智能地管理少量宝贵的快速资源，我们可以创造出拥有无限资源的幻觉。

机器的心脏：数据库与操作系统

让我们从机器的深处，即这些算法的诞生地——操作系统和数据库领域开始。想象一个简单的 LRU 缓存管理器，它就像一位善意但健忘的图书管理员。这位管理员只记录每本书最后被谁接触过。现在，想象一个大型数据库查询执行“全表扫描”——这就像一个研究员快速地从书架上取下几十本书，仅仅为了瞥一眼每本书的索引，然后就放回去。对于我们这位简单的 LRU 图书管理员来说，这些被短暂接触的书籍突然显得异常受欢迎。为了腾出空间，管理员尽职地丢弃了那些在过去几分钟内未被触碰、但经久不衰、频繁阅读的参考书。缓存被无用的一次性物品“污染”，下一个需要真正热门参考书的人发现书不见了，只能缓慢地去档案室查找。

这正是 LRU-K 展现其智慧的场景。LRU-K 是一位经验更丰富的图书管理员，它不仅记录最后一次访问，还记录倒数第二次、倒数第三次访问等。它能够区分一个随时间被反复引用的真正“热”项和一个仅仅是一次性扫描一部分的“冷”项。当扫描发生时，LRU-K 看到这些新项目没有使用历史，并正确地将它们优先设置为驱逐对象，从而保护了宝贵的、已建立的工作集。

数据库将此更进一步。当一个事务正在进行时——比如更新用户的账户余额——其底层的数据页必须被锁定在内存中。无论它们在替换算法看来有多“冷”，都不能被驱逐。这个被称为“钉住”（pinning）的概念，与像 LRU-K 这样的策略紧密配合，以确保性能和正确性，保证关键数据不会在操作中途被换出。

同样的情景也发生在管理你电脑应用程序的操作系统中。考虑一个交互式 UI 进程。你可能正在疯狂打字，然后停下来思考几分钟。对于一个只考虑最近访问的简单 LRU 策略来说，你应用程序所属的页面在这段空闲期间很快就会显得“陈旧”。如果一个后台任务启动，操作系统可能会换出你应用程序的页面。当你终于有了绝妙的点子并重新开始打字时，你会遇到令人沮丧的延迟，因为系统正手忙脚乱地重新加载它刚刚丢弃的一切。然而，一个类似 LRU-K 的策略会记得你应用程序的页面在暂停之前被频繁使用。它正确地将它们识别为有价值工作集的一部分，并保护它们免受瞬态后台任务的影响，从而带来更流畅、响应更快的用户体验。当我们考虑到像 CLOCK 算法这样对硬件友好的近似算法时，这种权衡变得更加引人入胜。CLOCK 算法使用一个单一的引用位。虽然 CLOCK 可以有效地保护一个页面不被驱逐“指针”的一次扫描所淘汰，但它缺乏长期记忆来区分一个真正热门的页面（有多次近期访问）和一个仅仅被触碰过一次的页面。LRU-K 更深厚的历史记录使其能够做出更稳健、更长期的决策。

塑造我们的数字体验：从游戏到云

这些算法的影响远远超出了机器的核心，延伸到我们日常交互的应用程序中。想象一下，你是一款角色扮演游戏中的冒险者，你的物品袋只能装三件物品。你用了一瓶生命药水，然后是你的剑，再然后是一把钥匙。现在，你需要捡起一件宝物，你的背包（使用简单的 LRU 策略）决定自动丢弃“最近最少使用”的物品：生命药水。这非常令人沮丧！作为玩家，你知道生命药水是你装备中的重要部分，远比一次性使用的钥匙重要。LRU-K 提供了一个更符合直觉的解决方案。通过记住你过去频繁使用生命药水，它会正确地将钥匙识别为瞬时物品，并选择丢弃它，这让游戏感觉更智能，更符合玩家的意图。

同样的“用户挫败感”原则在现代云计算中有一个直接的对应物：财务成本。考虑一个临时的无服务器函数，它被启动以执行任务，然后关闭。为了快速响应，它需要某些软件库处于“热”状态——也就是说，已经加载到内存中。如果所需的库不是热的，函数就会遭受“冷启动”，产生显著的延迟惩罚。通过维护一个基于 LRU 的小型库缓存，系统可以避免许多这样的冷启动。以节省的延迟秒数来衡量的总收益，与缓存命中次数成正比。通过分析访问轨迹，我们可以精确地看到像 LRU-K 这样的算法，如何通过更好地预测哪些库会再次被需要，直接转化为更快的服务和更低的运营成本。

运动中的世界：动态系统建模

到目前为止，我们考虑的都是特定的、确定性的事件序列。但现实世界是混乱且充满概率性的。这些思想能帮助我们在不确定性下预测和设计系统吗？答案是肯定的，这正是缓存理论与随机过程领域美妙结合之处。

想一想社交媒体的信息流。用户的注意力并非随机；它表现出“近因偏见”，意味着他们最有可能与最新的帖子互动。我们可以用一个简单的概率定律来模拟这种行为，例如，一个几何分布，其中重访第 $j$ 个最近项的概率为 $p(j) = p_r(1-p_r)^{j-1}$ 。在这个模型下，对于一个大小为 $k$ 的 LRU 缓存（根据定义，它保存着 $k$ 个最近的项），缓存命中的概率是用户重访一个排名 $j \le k$ 的项的概率。这个求和是一个简单的几何级数，得出一个非常优雅的结果：

$P_{\text{hit}} = 1 - (1-p_r)^{k}$

突然间，我们有了一个强大的预测工具。平台设计者现在可以定量地回答这个问题：“如果我们将用户的缓存大小加倍，他们的命中率会提高多少？”它弥合了系统参数（ $k$ ）和用户行为（ $p_r$ ）之间的差距。

这种概率方法同样适用于机器对机器的系统。在微服务架构中，对不同端点的请求可能遵循独立的泊松过程。对于一个大小为 $k=1$ 的简单缓存，它只保存最后请求的端点，如果当前请求与前一个请求是同一个端点，则发生命中。如果请求端点 $A$ 或 $B$ 的概率分别是 $p_a$ 和 $p_b$ ，那么命中概率就是 $p_a^2 + p_b^2$ ，即两个相同的独立事件连续发生的概率。

也许最生动的概率应用是在物联网（IoT）中。想象一个传感器网关缓存来自气象传感器的最后 $k$ 个读数。新读数以速率 $\mu$ 到达，将较旧的读数从 LRU 缓存中挤出。与此同时，查询以速率 $\nu$ 独立到达，以检索一个特定的“基线”读数。如果基线读数在查询到达之前被驱逐，则查询失败。这就构成了一场新读数到达与下一次查询到达之间的“竞赛”。要使基线被驱逐，必须在单个查询到达之前有 $k$ 个新读数到达。这种情况发生的概率原来是另一个极其简单的表达式：

$P_{\text{eviction}} = \left(\frac{\mu}{\mu+\nu}\right)^{k}$

这个公式优雅地捕捉了这场竞赛的本质。如果数据到达速率 $\mu$ 远高于查询速率 $\nu$ ，驱逐就很可能发生。如果缓存更深（ $k$ 更大），驱逐的概率会呈指数级下降。

宏伟设计：作为架构模式的缓存

最后，让我们放大到系统设计的最高层面。缓存的逻辑不仅仅是一种算法；它是一种在各种尺度上都出现的通用架构模式。考虑一下将这篇文章带给你的内容分发网络（CDN）。它形成了一个多层缓存：一个位于你所在城市附近服务器中的小型、快速的“边缘”缓存，一个更大的“区域”缓存，以及内容最初存储的缓慢的“源”服务器。

这种全局层次结构完美地类比了单台计算机内部的存储层次结构：边缘缓存就像 CPU 的 L1 缓存或 RAM，区域缓存就像固态硬盘（SSD），而源服务器则像是缓慢的硬盘驱动器（HDD）。其根本目标是相同的：将“热”内容保存在最快、最近的存储层中。

在这里，缓存策略的选择具有深远的架构意义。如果“热”对象的总集合（ $K$ ）大于区域缓存（ $C_2$ ），但小于边缘缓存和区域缓存的总和（ $K \le C_1 + C_2$ ），那么最佳策略是独占式缓存。在这种设计中，一个对象要么存在于边缘缓存，要么存在于区域缓存，但不能同时存在于两者中。这最大化了系统可以容纳的唯一对象的总数。当区域缓存（SSD）中的一个对象被访问时，它被“提升”到边缘缓存（RAM）。当边缘缓存已满时，它将其最近最少使用的项“降级”到区域缓存。这种动态移动确保了最频繁访问的内容迁移到最快的层级，同时充分利用系统的组合容量，以最小化从源服务器（HDD）进行的缓慢抓取。这就是局部性原理在全球范围内的宏大体现。

从处理器的核心到互联网的边缘，近因性和频率这些简单的思想为构建快速、高效、智能的系统提供了一个强大而统一的框架。通过理解如何在“刚刚使用”和“最常使用”之间取得平衡，我们能够设计出感觉无缝且瞬时的体验。