1981年，加州大学伯克利分校的Michael Stonebraker发表了一篇标题平实却影响深远的论文——《Operating System Support for Database Management》。论文的核心论断是：通用操作系统的内存管理决策对数据库负载是次优的。操作系统以"盲目"的全局策略（通常是LRU变体）管理内存，追求跨进程的公平性，却无法利用数据库独有的语义信息。

这个问题直指数据库性能的核心：当一个执行顺序扫描的查询读取数十亿字节的数据时，操作系统会忠实地将这些页面缓存起来，可能驱逐掉更有价值的B+树索引节点。这种"缓存污染"现象催生了现代数据库自主管理内存的架构决策——几乎所有主流数据库都使用O_DIRECT或类似机制绕过操作系统的页面缓存，自己实现Buffer Pool。而Buffer Pool的核心，就是页面置换算法。

Belady最优：一个无法实现的理想

1966年，IBM的László Bélády在研究虚拟存储系统时提出了一个看似简单的问题：给定有限的内存空间和未来的页面访问序列，选择驱逐哪个页面能使缺页次数最少？

答案出人意料地优雅：驱逐未来最长时间内不会被访问的页面。这个被称为MIN算法（或Belady最优算法）的策略可以证明达到理论上的最小缺页率。

证明的核心逻辑是反证法：假设存在一个比MIN更好的算法A，那么在某个决策点，算法A驱逐了页面P，而MIN保留了P并驱逐了另一个页面Q。如果P在未来比Q更早被访问，算法A就会比MIN多产生一次缺页，与"比MIN更好"矛盾。

$$\text{Belady最优} = \arg\max_{p \in \text{cache}} \text{NextAccessTime}(p)$$

这个算法的完美之处恰恰是它的致命缺陷——它需要预知未来的访问序列。在实际系统中，我们无法知道下一个请求会访问哪个页面。Belady最优的价值在于提供了一个理论上界，让我们能够评估其他算法的性能。

有趣的是，Belady最优算法展示了一个反直觉现象，被称为Belady异常：对于某些特定的访问序列，增加缓存大小反而会增加缺页次数。这违背了直觉，但证明了FIFO算法存在理论缺陷，而LRU算法则不会出现这种异常——因为LRU是栈算法（Stack Algorithm），其缓存内容是更大缓存的子集。

LRU的困境：当"最近使用"变成诅咒

Least Recently Used（LRU）算法的核心直觉是：最近被访问的页面很可能在不久的将来再次被访问。这基于程序局部性原理，在大多数场景下效果良好。实现上，LRU维护一个双向链表，每次访问将页面移到链表头部，淘汰时选择链表尾部的页面。

然而，在数据库场景下，LRU存在两个致命缺陷：

顺序扫描灾难

考虑一个简单场景：Buffer Pool大小为100个页面，而一张表有1000个页面。当执行全表扫描时：

  1. 前100个页面填满缓存
  2. 第101个页面到来，驱逐第1个页面
  3. 第102个页面到来，驱逐第2个页面
  4. …以此类推

扫描结束后，缓存中保留的是最后访问的100个页面——它们可能永远不会再被访问，而真正有价值的热点数据已经被驱逐殆尽。更糟糕的是，如果另一个查询需要访问被驱逐的热点数据，就会触发大量的磁盘I/O。

graph LR
    subgraph LRU缓存状态变化
        A[初始: 热点数据A,B,C...] --> B[扫描开始: 页面1,2,3...]
        B --> C[扫描进行中: 热点数据被驱逐]
        C --> D[扫描结束: 缓存充满无用页面]
    end

单次访问污染

LRU仅考虑"最近是否访问"，不关心访问频率。一个被频繁访问的页面和一个仅被访问一次的页面，在LRU眼中具有同等地位——都被移到链表头部。这导致偶发性的一次性扫描可以"污染"整个缓存。

1993年，Digital Equipment Corporation的Elizabeth O’Neil等人发表了题为《The LRU-K Page Replacement Algorithm for Database Disk Buffering》的论文，提出了一个精巧的解决方案。

LRU-K：引入时间维度

LRU-K的核心洞察是：区分"瞬时热点"和"持续热点"。它记录每个页面最近K次访问的时间戳，而不是只记录最后一次访问。对于LRU-2（最常用的配置）：

$$\text{Backward K-Distance}(p) = t_{\text{current}} - t_{K}(p)$$

其中$t_K(p)$表示页面p的第K次最近访问时间。淘汰时选择Backward K-Distance最大的页面。

这个设计的精妙之处在于：只被访问一次的页面，其Backward 2-Distance是无穷大，因此成为首选淘汰对象。只有当页面被访问两次或以上时，它才有机会在缓存中停留。

论文还提出了一个重要概念——关联引用周期（Correlated Reference Period）：短时间内连续对同一页面的多次访问，应该被视为一次"逻辑访问"。这防止了一个正在进行的事务通过频繁访问某个页面而人为地提高其优先级。

LRU-K的代价是维护优先队列的$O(\log N)$复杂度，对于高吞吐量系统来说可能成为瓶颈。但它奠定了一个重要思想：用历史访问模式预测未来行为。Microsoft SQL Server的Buffer Pool就采用了LRU-2算法。

2Q：将复杂性转化为空间

1994年，威斯康星大学的Theodore Johnson和Dennis Shasha在VLDB会议上发表了《2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm》，提出了一个更加实用的设计。

2Q的核心理念是：与其维护复杂的优先队列，不如用多个简单队列的组合来近似相同效果。

完整版2Q维护三个逻辑区域：

  • Am（Main Queue）：标准的LRU队列，存放"已证明有价值"的页面
  • A1-In（First-In Resident）：FIFO队列，存放新进入缓存的页面
  • A1-Out（First-Out Ghost）：存放刚被驱逐页面的标识符（不存实际数据）

算法流程：

当访问页面P时：
  如果P在Am中 → 移动到Am头部
  如果P在A1-Out中 → 从A1-Out删除，插入Am头部（证明它值得缓存）
  如果P不在任何队列中 → 插入A1-In头部
  
当需要淘汰时：
  如果A1-In满 → 将A1-In尾部页面移到A1-Out
  如果A1-Out满 → 直接丢弃A1-Out尾部
  如果Am满 → 淘汰Am尾部

flowchart LR
    subgraph 2Q结构
        direction LR
        A1_IN["A1-In\n(FIFO)"] --> A1_OUT["A1-Out\n(Ghost)"]
        A1_OUT --> Am["Am\n(LRU)"]
    end
    
    NEW["新页面"] --> A1_IN
    A1_IN -->|"再次访问"| Am
    A1_OUT -->|"再次访问"| Am
    Am -->|"淘汰"| EVICT["驱逐"]

2Q的关键优势在于测试机制：一个页面必须先在A1-Out中"被观察到再次访问"，才能晋升到Am。这天然过滤了顺序扫描产生的单次访问页面。而且，所有操作都是$O(1)$的队列操作，没有复杂的优先级计算。

PostgreSQL的Buffer Manager深受2Q影响，尽管由于IBM对ARC算法的专利限制，PostgreSQL最终选择了自己设计的Clock Sweep变体，但"用历史验证热度"的思想一脉相承。

LIRS：重新定义"热度"

2002年，佛罗里达大学的Song Jiang和Xiaodong Zhang在SIGMOD会议上发表了《LIRS: An Efficient Low Inter-reference Recency Set Replacement Policy to Improve Buffer Cache Performance》，提出了一个更深刻的问题：用"最近访问时间"衡量页面热度是否合理？

考虑两个页面：

  • 页面A：每隔100秒访问一次，上次访问在10秒前
  • 页面B：每隔10秒访问一次，上次访问在50秒前

按LRU的逻辑，页面A更"热"（更近被访问）。但显然页面B的价值更高——它的访问频率是A的10倍。

LIRS引入了**引用间隔距离（Inter-Reference Recency, IRR）**的概念：

$$\text{IRR}(p) = t_{\text{current\_access}} - t_{\text{previous\_access}}$$

IRR小的页面意味着频繁访问，应该保留；IRR大的页面应该优先淘汰。LIRS维护两类页面：

  • LIR（Low IRR）页面：IRR小于阈值，存放在栈S中
  • HIR（High IRR）页面：IRR大于阈值，存放在队列Q中作为淘汰候选

当需要淘汰时，优先从HIR集合中选择。LIRS的精妙之处在于它不需要像LRU-K那样记录多个时间戳，只需要比较连续两次访问的间隔，就能有效区分频繁访问和偶发访问。

MySQL 8.0的InnoDB存储引擎采用的就是LIRS的变体。

ARC：自适应的终极形态

2003年，IBM Almaden研究中心的Nimrod Megiddo和Dharmendra Modha发表了《ARC: A Self-Tuning, Low Overhead Replacement Cache》，提出了一个令人印象深刻的设计——完全自适应，无需手动调参。

ARC维护四个列表：

列表 内容 作用
T1 最近访问的页面 捕获"时效性"模式
T2 频繁访问的页面 捕获"频率"模式
B1 T1的幽灵缓存 记录从T1驱逐的页面标识
B2 T2的幽灵缓存 记录从T2驱逐的页面标识

关键创新在于动态目标大小调整。ARC维护一个参数$p$，表示T1的目标大小。当发生缓存未命中：

  • 如果未命中的页面标识在B1中 → 说明之前因为T1太小而被驱逐，增加$p$
  • 如果未命中的页面标识在B2中 → 说明之前因为T2太小而被驱逐，减少$p$
$$p = p + \delta \quad \text{(B1命中)}$$

$$p = p - \delta \quad \text{(B2命中)}$$

这意味着ARC会根据工作负载的反馈，自动调整"重时效"和"重频率"之间的平衡。如果工作负载频繁访问最近的数据，ARC会扩大T1；如果工作负载有稳定的访问热点，ARC会扩大T2。

flowchart TB
    subgraph ARC结构
        T1["T1\n(Recent)"] 
        T2["T2\n(Frequent)"]
        B1["B1\n(Ghost T1)"]
        B2["B2\n(Ghost T2)"]
    end
    
    ACCESS["页面访问"] --> T1
    ACCESS --> T2
    T1 -->|"驱逐"| B1
    T2 -->|"驱逐"| B2
    B1 -->|"再次访问\n增大p"| T2
    B2 -->|"再次访问\n减小p"| T2

ARC的"经验主义普适性"（Empirical Universality）使其在多种工作负载下都能表现出色。它被ZFS文件系统和多个存储阵列产品采用。遗憾的是，IBM对ARC申请了专利，这迫使PostgreSQL等开源项目转向其他方案。后来Bansal和Modha开发了CAR（Clock with Adaptive Replacement），实现了类似的自适应能力且无专利限制。

CLOCK-Sweep：硬件友好的LRU近似

在并发环境下，传统的LRU链表面临严重的锁竞争问题——每次页面访问都需要更新链表，这需要获取全局锁。PostgreSQL采用了CLOCK-Sweep算法来解决这个问题。

CLOCK-Sweep的核心思想是用计数器代替严格的访问顺序。每个缓冲区描述符包含一个usage_count字段（通常范围0-5）：

  1. 当页面被访问时，原子地增加usage_count（不超过上限）
  2. 当需要淘汰页面时，“时钟指针"扫描缓冲池
  3. 遇到usage_count > 0的页面，递减计数器并继续扫描
  4. 遇到usage_count = 0且未被钉住的页面，选中淘汰

这实际上是对LRU的松弛近似：访问频率高的页面有更高的计数器值，需要更多轮扫描才能被淘汰。由于只需原子操作而非全局锁，CLOCK-Sweep在高并发场景下表现优异。

PostgreSQL还引入了**环形缓冲区（Ring Buffer）**机制来处理批量操作。对于顺序扫描、VACUUM等操作，PostgreSQL会分配一个小的临时环形（如256KB），这些页面在处理完后立即重用，不会进入主Buffer Pool，从而避免污染热点数据。

/* PostgreSQL源码中的usage_count递增逻辑 */
if (buf->usage_count < BM_MAX_USAGE_COUNT)
    buf->usage_count++;

InnoDB的工程智慧：中点插入策略

MySQL InnoDB的Buffer Pool实现了一个优雅的变体——Midpoint Insertion Strategy。

传统LRU的新页面总是插入链表头部，而InnoDB将新页面插入链表的中点。Buffer Pool的LRU链表被分为两个子列表：

  • Young区域（约5/8）：存放频繁访问的热点页面
  • Old区域（约3/8）：存放新进入或低频访问的页面

参数innodb_old_blocks_pct控制Old区域的比例，默认37（约3/8）。参数innodb_old_blocks_time控制页面从Old区域晋升到Young区域前必须在Old区域停留的最短时间（默认1000毫秒）。

flowchart LR
    subgraph InnoDB LRU链表
        direction LR
        YOUNG["Young区域\n(5/8 热点数据)"] 
        OLD["Old区域\n(3/8 新数据)"]
    end
    
    NEW["新页面"] -->|"中点插入"| OLD
    OLD -->|"再次访问"| YOUNG
    OLD -->|"淘汰"| EVICT["驱逐"]

这个设计的精妙之处在于：

对于顺序扫描：页面进入Old区域后，如果不再被访问，会在相对较短的时间内被淘汰（Old区域只有3/8的大小）。扫描过程中，Young区域的热点数据受到保护。

对于真正的热点：如果页面在Old区域停留期间被再次访问，它会晋升到Young区域的头部，获得更长的缓存时间。

这种设计在不增加复杂度的前提下，有效解决了顺序扫描污染缓存的问题。这也是为什么在生产环境中，合理的innodb_old_blocks_time设置对于混合负载（OLTP + 报表）至关重要。

算法对比：没有银弹，只有权衡

算法 核心指标 时间复杂度 抗扫描 自适应 代表应用
LRU 最近访问时间 O(1) 否 否 早期系统
LRU-K 第K次访问时间 O(log N) 是 否 SQL Server
2Q 队列成员关系 O(1) 是 否 PostgreSQL（影响）
LIRS 引用间隔距离 O(1) 是 否 MySQL InnoDB
ARC 自适应目标 O(1) 是 是 ZFS
CLOCK-Sweep 使用计数器 O(1) 部分 否 PostgreSQL

没有完美的算法。LRU-K的精度来自优先队列的代价；2Q的空间开销来自多队列；ARC的自适应来自额外的幽灵缓存；CLOCK-Sweep的简单来自对LRU的松弛。选择取决于工作负载特征、硬件资源和实现复杂度。

现代演进：机器学习与多层内存

2024-2025年的研究开始探索机器学习驱动的Buffer管理。CMU的LeCaR（Learning Cache Replacement）采用在线学习，在LRU和LFU两个"专家"之间动态选择；Google的Hawkeye尝试从历史轨迹中学习Belady最优策略的特征。

另一个重要方向是多层内存架构的Buffer管理。随着CXL（Compute Express Link）技术的成熟，服务器可能拥有DRAM（50ns延迟）、CXL内存（200ns延迟）和SSD（μs级延迟）三层存储。页面置换算法需要从"留在缓存还是驱逐"的二元决策，升级为"放在哪一层"的多层决策。

2024年，一篇发表在arXiv的综述论文《Evolution of Buffer Management in Database Systems》系统梳理了这个领域四十年的演进，从LRU-K、2Q到机器学习增强策略和内存分解架构，揭示了核心设计模式的延续：用历史预测未来，用空间换取时间，用复杂性换取精度。

结语

六十年来，Buffer Pool的页面置换算法从Belady的理论最优出发，经历了LRU的工程实践、LRU-K的时间维度扩展、2Q的空间换精度、LIRS的模式识别、ARC的自适应平衡，最终形成了今天各大数据库百花齐放的局面。

理解这些算法的本质，有助于在调优数据库时做出正确决策。当你看到innodb_old_blocks_time参数时，要知道它控制的是新页面在"试用期"的最短停留时间；当你观察到PostgreSQL的顺序扫描没有污染缓存时，要知道那是Ring Buffer和Clock Sweep协同工作的结果；当你需要为混合负载选择Buffer Pool策略时，要理解不同算法对时效性和频率性的权衡。

页面置换算法的故事远未结束。随着新型存储介质和机器学习技术的发展，这个领域仍在演进。但无论如何变化，核心原则不变：在有限的空间里，做出最有价值的保留决策。

参考资料

  1. Stonebraker, M. (1981). “Operating System Support for Database Management”. Communications of the ACM, 24(7), 412-418.
  2. Belady, L. A. (1966). “A Study of Replacement Algorithms for a Virtual-Storage Computer”. IBM Systems Journal, 5(2), 78-101.
  3. O’Neil, E. J., O’Neil, P. E., & Weikum, G. (1993). “The LRU-K Page Replacement Algorithm for Database Disk Buffering”. SIGMOD 1993.
  4. Johnson, T., & Shasha, D. (1994). “2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm”. VLDB 1994.
  5. Jiang, S., & Zhang, X. (2002). “LIRS: An Efficient Low Inter-reference Recency Set Replacement Policy to Improve Buffer Cache Performance”. SIGMOD 2002.
  6. Megiddo, N., & Modha, D. S. (2003). “ARC: A Self-Tuning, Low Overhead Replacement Cache”. FAST 2003.
  7. CMU 15-445/645 Database Systems Course Materials. Buffer Pool Management.
  8. PostgreSQL Documentation. Buffer Manager Implementation.
  9. MySQL Reference Manual. InnoDB Buffer Pool.
  10. Evolution of Buffer Management in Database Systems. arXiv:2512.22995, 2025.