LRU 缓存

定义

LRU 缓存是一种按照数据最近一次被访问的时间来决定淘汰对象的缓存管理方式。它给每个缓存项记录最近访问的时间信息，当缓存已满而必须载入新数据时，选择距离当前时刻最久没有被访问的那一项移出缓存^[1]。

这一策略的出发点是对最优置换算法的一种近似。理论上最少缺页的做法是淘汰未来最长时间内不会被用到的数据，但系统无法预知未来的访问序列，只能借助「最近的过去」推断「最近的将来」。LRU 用历史访问顺序作为未来访问的近似判断，因而只能算接近理想，而不能保证最优^[1]。

原理

LRU 的基础是程序访存的局部性原理。时间局部性指某项数据一旦被访问，近期很可能再次被访问；空间局部性指与刚被访问地址相邻的数据也容易在不久后被使用^[4]。LRU 主要利用时间局部性，把最近被访问的数据留在缓存中，把长久未用的数据淘汰出去^[5]。

在软件缓存中，实现 LRU 的常见方式是同时使用哈希表与双向链表。哈希表负责在常数时间内定位数据，双向链表负责维护访问先后顺序：刚被访问的节点移到靠近头部的一端，最久未访问的节点位于另一端，缓存满时删除该端节点^[6]。这样查找、插入和删除的时间复杂度都能保持在 $O(1)$，只使用单链表则查找需要 $O(n)$^[7]。

在操作系统页面置换场景中，精确实现 LRU 需要为每个页面维护时间戳并在每次访存时更新。一种做法是给页表项增加「最后使用时间」字段，置换时扫描找出数值最小者，但这也带来每次访存和每次置换的额外开销^[8]。另一种做法是用栈保存页号，被访问的页移到栈顶，栈底就是最近最久未使用的页^[1]。

flowchart LR

A[访问数据] --> B{在缓存中?}

B -- 是 --> C[移到最近使用端]

B -- 否 --> D{缓存已满?}

D -- 否 --> E[插入最近使用端]

D -- 是 --> F[淘汰最久未使用端]

F --> E

发展历程

LRU 的思想形成于 20 世纪 60 年代末到 70 年代初，伴随操作系统虚拟内存管理对页面的调度需求而出现^[9]。早期的实现方案之一借助访问位工作：把数据块组织成循环链表并附访问位，被访问时置 1，需要置换时挑选访问位为 0 的块，也就是时钟算法的雏形^[9]。

1966 年，贝拉迪(Laszlo A. Belady) 提出了理论上的最优替换算法，即淘汰未来最久才被使用页面的做法，为衡量 LRU 等实际算法提供了性能上限。此后围绕 LRU 的改进不断出现，包括 1994 年的 2Q、2001 年的 MQ 与 LRFU、2003 年的 ARC、2010 年的 RRIP，以及 2016 年的 Hawkeye 等。针对硬件实现成本，还发展出简化版的伪 LRU（PLRU），用较少的比特近似记录访问顺序。

应用

操作系统是 LRU 最早的应用场所，用于虚拟内存的页面置换。多数现代操作系统采用 LRU 的近似变体，因为精确版本的开销过高^[8]。在处理器中，LRU 是组相联高速缓存常用的替换策略，真正的精确实现只在小规模组内可行，4 至 8 路的组通常改用伪 LRU 方案^[10]。

在数据库与网络缓存领域，LRU 也被广泛采用。MySQL 的缓冲池使用 LRU 管理内存中的数据页^[11]；Redis 从 4.0 版本起提供多种内存淘汰策略，其中若干基于 LRU 或 LFU 思想^[11]。浏览器缓存管理、内容分发网络等场景同样会用到这一策略^[12]。

以 Redis 为例，它采用的是一种近似 LRU：不为所有键维护全局链表，而是给每个键的对象结构附加记录最近访问时间的字段，淘汰时随机抽样若干个键，从中挑出空闲时间最长者删除，采样数量可由参数调整^[6]。这样做节省内存并减少每次访问的链表操作，代价是结果与全局最久未使用存在误差^[11]。

局限

LRU 只参考访问的时间顺序，不考虑访问次数，因此在某些访问模式下会淘汰实际仍属热点的数据。若数据 A、B、C 中 C 最近被访问但总次数最少，而 B 被访问最频繁，LRU 仍可能把 B 视为较「冷」的数据^[11]。

顺序扫描或大循环访问会严重削弱 LRU 的效果。当缓存可容纳 N 项而程序循环遍历 N+1 项的数据时，每次访问都可能造成未命中，LRU 的性能会退化^[13]。有分析指出，LRU 在循环访问这类常见模式下表现不佳，因此出现了许多针对循环模式进行检测并切换策略的改进方案^[13]。

精确实现的成本是另一项约束。为了在每次访存时维护访问顺序信息，需要额外的硬件或软件开销，多数系统难以承受，只能退而采用时钟算法、老化算法等近似方案，而这些近似方案对访问时间的分辨率低于理想 LRU。使用随机采样实现的近似 LRU 还可能留下缓存污染问题，即只被访问过一两次的数据长期占据缓存空间^[6]。

参见

• 先进先出算法 —— 按进入缓存的先后顺序淘汰数据，与 LRU 的淘汰依据不同

• LFU 算法 —— 依据访问频率而非最近访问时间淘汰数据

• 局部性原理 —— LRU 得以奏效的计算机访存规律基础

• 页面置换算法 —— LRU 在操作系统虚拟内存中的具体应用形式

• ARC 算法 —— 结合 LRU 与 LFU 并自适应调整的缓存替换策略

• 缓存 —— LRU 所服务的存储层次结构