缓存算法 #06：MySQL Buffer Pool 与 midpoint LRU

MySQL InnoDB Buffer Pool 是数据库最重要的内存结构，所有读写都必须经过它。InnoDB 在标准 LRU 基础上做了"midpoint insertion"改造，通过将新页插入链表中间位置，防止全表扫描污染热点数据页。本文深入 Buffer Pool 的页管理、LRU 变体、刷脏策略和并发控制。

相关文章：LRU（最近最少使用） · Clock 与 CLOCK-Pro · ARC（自适应替换缓存）

目录

Buffer Pool 整体结构

Buffer Pool 由若干"页帧"（page frame）组成，每帧固定 16 KB，存一个数据页。
三个核心链表管理所有页帧：

1. Free List（空闲链表）
   存放尚未使用的空页帧
   需要加载新页时，从 Free List 取一帧
   初始时所有帧都在 Free List

2. LRU List（使用链表）
   所有已加载数据页的链表，按访问顺序排列
   分为两个区域（midpoint 分界）：
     Young 区（热数据，约 5/8，链表前部）
     Old 区（冷数据，约 3/8，链表后部）
   驱逐时从 Old 区的尾部（最久未访问的冷页）驱逐

3. Flush List（脏页链表）
   所有被修改但尚未刷回磁盘的脏页
   按 LSN（Log Sequence Number，修改时间戳）排序
   Checkpoint 时从 Flush List 刷脏页到磁盘

Midpoint Insertion LRU

标准 LRU 的问题

全表扫描场景（SELECT * FROM big_table，数据量 >> Buffer Pool）：
  标准 LRU：新加载的页插入链表头部（最热端）
  → 扫描读取了大量页，每页进入 LRU 头部
  → 真正的热点页（索引页、频繁查询的页）被挤到尾部
  → 扫描结束后，热点页全被驱逐
  → 后续正常查询全部缓存未命中，需要重新从磁盘加载
  → 短暂性能雪崩

Midpoint Insertion 解法

新页不插入头部，而是插入 Young/Old 分界点（midpoint）：

Young 区（5/8）：头部 ←────────── midpoint
Old 区（3/8）：              midpoint ──────────→ 尾部

规则：
  1. 新页（缺页加载）：插入 midpoint，即 Old 区的头部
  2. Old 区的页被再次访问：
     if 在 Old 区停留时间 > innodb_old_blocks_time（默认 1000ms）：
         移动到 Young 区头部（升级为热数据）
     else:
         不移动（说明是扫描读取，短时间内重复访问，不算真正热点）
  3. Young 区的页被访问：
     if 在 Young 区停留时间 > 1/4 Young 区遍历时间：
         移动到 Young 区头部（减少链表操作次数）
     else:
         不移动（避免频繁移动开销）

关键参数：innodb_old_blocks_pct（默认 37，即 Old 区占 37%）
          innodb_old_blocks_time（默认 1000ms）

完整伪代码

// 读取页
read_page(space_id, page_no):
    page = find_in_LRU(space_id, page_no)

    if page != null:
        // 缓存命中（Buffer Pool Hit）
        on_page_hit(page)
        return page

    // 缓存未命中（Buffer Pool Miss）
    frame = get_free_frame()         // 从 Free List 取空帧
    if frame == null:
        frame = evict_page()         // Free List 空，驱逐一个 Old 区页
    load_from_disk(frame, space_id, page_no)  // 磁盘 I/O
    insert_at_midpoint(frame)        // 新页进入 Old 区头部
    return frame

on_page_hit(page) — 命中后的处理

on_page_hit(page):
    if page in Young 区:
        // Young 区命中：只有停留超过一定时间才移到头部（减少移动开销）
        time_in_young = now() - page.last_moved_time
        young_traversal_time = estimate_young_traversal_time()
        if time_in_young > young_traversal_time / 4:
            move_to_young_head(page)
        // else: 不移动，避免频繁移动

    elif page in Old 区:
        // Old 区命中：判断是否是"真正的热访问"还是"扫描读取"
        time_in_old = now() - page.enter_old_time
        if time_in_old > innodb_old_blocks_time:
            // 在 Old 区停留超过阈值 → 升级到 Young 区头部
            move_to_young_head(page)
        // else: 停留不够长（可能是顺序扫描的重复读），不升级

evict_page() — 驱逐策略

evict_page():
    // 优先从 Old 区尾部驱逐（最久未访问的冷页）
    victim = LRU_list.old_tail()

    if victim is dirty:
        // 脏页不能直接驱逐，需要先刷到磁盘
        // 策略1（同步）：立即刷脏，有 I/O 等待开销
        // 策略2（异步）：触发 page_cleaner 线程后台刷脏
        //                 返回 null，上层重试或从 Young 区找干净页
        trigger_flush(victim)
        return null   // 让上层等待或重试

    // 干净页：直接驱逐
    remove_from_LRU(victim)
    del page_map[victim.key]
    add_to_free_list(victim.frame)
    return victim.frame

执行追踪

Buffer Pool 8 个页，Young 区 5，Old 区 3，old_blocks_time=1s

初始（Young 区有热点页 H1~H5）：
  Young: [H1, H2, H3, H4, H5]（H1 最热）
  Old:   [空, 空, 空]

场景1：全表扫描，连续读取冷页 P1, P2, P3, P4（> Old 区容量）

  读 P1：缺页 → 插入 Old 头部
    Young: [H1,H2,H3,H4,H5]  Old: [P1]

  读 P2：缺页 → 插入 Old 头部
    Old: [P2, P1]

  读 P3：缺页 → 插入 Old 头部
    Old: [P3, P2, P1]  （Old 区满）

  读 P4：缺页 → 驱逐 Old 尾部 P1（停留仅几毫秒 < 1s，未升级）
    Old: [P4, P3, P2]
    Young 区 H1~H5 完全未受影响！✅

场景2：扫描结束后，H1 被查询（Young 区命中）
  → 命中 H1，正常访问，H1 仍在 Young 区头部

场景3：若 P1 在 Old 区停留 > 1s 后被再次访问（真热点）
  → time_in_old=2s > 1s → 升级到 Young 头部 ✅
  → 替换 H5（Young 尾部最旧的热点）
    Young: [P1, H1, H2, H3, H4]
    Old: [P4, P3, P2]

刷脏策略

LRU Flush（驱逐触发）

触发时机：需要驱逐 Old 区页时，发现是脏页

处理流程：
  page_cleaner 线程扫描 LRU List 的尾部（Old 区）
  找到脏页 → 写入磁盘（double write buffer 保护原子性）
  → 清除 dirty 标记，移入 Free List

目标：保持 Free List 中有足够的空闲页（避免驱逐时等待刷脏）
参数：innodb_lru_scan_depth（每次扫描的页数，默认 1024）

Checkpoint Flush（WAL 推进触发）

目的：防止 redo log 被写满（循环使用的日志文件不能覆盖未刷盘的脏页）

触发机制：
  redo log 使用率超过 75%（soft checkpoint）→ 加快刷脏
  redo log 使用率超过 90%（hard checkpoint）→ 停止写入，强制刷脏

Flush List 按 LSN 排序：
  checkpoint 时从 Flush List 头部（oldest LSN）开始刷
  确保旧的修改先落盘，redo log 才能安全推进

page_cleaner 线程（MySQL 5.6+）：
  独立后台线程，周期性刷脏
  adaptive flushing：根据脏页数量和 redo log 增长速度动态调整刷脏速率

多 Buffer Pool 实例

问题：单个 Buffer Pool 有一个全局 mutex
      高并发时，所有线程争抢同一把锁 → 性能瓶颈

解法：innodb_buffer_pool_instances（默认 8，当 BP>=1GB 时）
  将 Buffer Pool 分为 N 个独立实例，每个实例有独立的 mutex
  page 根据 space_id+page_no 哈希到对应实例
  不同实例的页操作互不阻塞

效果：
  8 实例 → mutex 竞争降低约 8 倍
  适合高并发 OLTP 场景

注意：
  每个实例大小 = innodb_buffer_pool_size / instances
  单个实例过小（<1GB）可能影响效率
  推荐：每个实例 1~8 GB，总大小设为物理内存的 50~70%

异常场景

内存压力：Free List 耗尽

场景：并发请求暴增，Free List 中的空闲页耗尽

现象：每次读页都需要先驱逐 Old 区页
      若 Old 区全是脏页 → 每次需要等待刷脏完成
      查询延迟飙升（P99 从 5ms → 500ms）

解法：
  1. 增大 innodb_buffer_pool_size
  2. 增大 innodb_lru_scan_depth（更积极地预清理 Free List）
  3. 降低写入压力，减少脏页产生速度

脏页积压：Flush List 过长

场景：写入量大，page_cleaner 刷脏速度 < 脏页产生速度
     redo log 快写满 → 触发 hard checkpoint → 写操作被阻塞

监控指标：
  SHOW ENGINE INNODB STATUS 中 "Modified db pages"（脏页数量）
  "Log sequence number" vs "Log flushed up to"（redo log 落后距离）

解法：
  调大 innodb_io_capacity（page_cleaner 每秒刷脏的 IOPS 上限）
  调大 innodb_io_capacity_max（突发刷脏的 IOPS 上限）
  使用更快的存储（NVMe SSD）

预读失效

InnoDB 支持线性预读（顺序访问某页后，预读后续页）
问题：预读的页被加载到 Old 区后，还没来得及被访问就被驱逐
     → 预读完全没有收益，反而消耗 I/O

调整：
  innodb_read_ahead_threshold（触发预读的页数阈值，默认 56）
  全表扫描时可适当降低；随机访问为主时应禁用线性预读

关键参数

参考资料

• MySQL 官方文档：https://dev.mysql.com/doc/refman/8.0/en/innodb-buffer-pool.html
• 《MySQL 实战 45 讲》第 12 讲：为什么我的 MySQL 会"抖"一下？
• Jeremy Cole's InnoDB Internals: https://github.com/jeremycole/innodb_diagrams