深度｜庖丁解 InnoDB 之 Buffer Pool
以下文章来源于 MySQL 内核剖析 ，作者王康
前言
Buffer Pool 是 InnoDB 中非常重要的组成部分，也是数据库用户最关心的组件之一。Buffer Pool 的基本功能并不复杂，设计实现也比较清晰，但作为一个有几十年历史的工业级数据库产品，不可避免的在代码上融合了越来越多的功能，以及很多细节的优化，从而显得有些臃肿和晦涩。
本文希望聚焦在 Buffer Pool 的本职功能上，从其提供的接口、内存组织方式、Page 获取、刷脏等方面进行介绍，其中会穿插一些重要的优化手段，之后用单独的一节介绍其中稍显复杂的并发控制，也就是各种 mutex 的设计及实现。
而除此之外，像 Change Buffer、压缩 Page、Double Write Buffer 等功能虽然大量的穿插在 Buffer Pool 的实现之中，但其本身并不属于 Buffer Pool 的核心逻辑，本文并不会包括这部分内容，本文代码相关内容基于MySQL 8.0。
01. 背景
传统数据库中的数据是完整的保存在磁盘上的，但计算却只能发生在内存中，因此需要有良好的机制来协调内存及磁盘的数据交互，这就是 Buffer Pool 存在的意义。也因此 Buffer Pool 通常按固定长度的 Page 来管理内存，从而方便的进行跟磁盘的数据换入换出。
除此之外，磁盘和内存在访问性能上有着巨大的差距，如何最小化磁盘的 IO 就成了 Buffer Pool 的设计核心目标。《数据库故障恢复的前世今生》一文中介绍过，主流的数据库会采用 REDO LOG 加 UNDO LOG，而不是限制刷脏顺序的方式，来保证数据库 ACID 特性。这种做法也保证了 Buffer Pool 可以更专注地实现高效的 Cache 策略。
Buffer Pool 作为一个整体，其对外部使用者提供的其实是非常简单的接口，我们称之为FIX-UNFIX接口，之所以需要 FIX 和 UNFIX，是因为对 Buffer Pool 来说，上层对 Page 的使用时长是未知的，这个过程中需要保证 Page 被正确的维护在 Buffer Pool 中：
上层调用者先通过索引获得要访问的 Page Number；
之后用这个 Page Number 调用 Buffer Pool 的 FIX 接口，获得 Page 并对其进行访问或修改，被 FIX 的 Page 不会被换出 Buffer Pool；
之后调用者通过 UNFIX 释放 Page 的锁定状态。
不同事务、不同线程并发的调用 Buffer Pool 的 FIX-UNFIX 接口的序列，我们称为 Page 访问序列（Page Reference String），这个序列本身是 Buffer Pool 无关的，只取决于数据库上面的负载类型、负载并发度、上层的索引实现以及数据模型。而通用数据库的 Buffer Pool 设计就是希望能在大多数的 Page 访问序列下，尽可能的实现最小化磁盘 IO 以及高效访问的目标。
为了实现这个目标，Buffer Pool 内部做了大量的工作，而替换算法是其中最至关重要的部分，由于内存容量通常是远小于磁盘容量的，替换算法需要在内存容量达到上限时，选择将现有的内存 Page 踢出，替换成新的被访问的 Page，好的替换算法可以在给定的 Buffer Size 下尽量少的出现 Buffer Miss。理想的情况下， 我们每次替换未来的访问序列中最远的那个 Page，这也是 OPT 算法的思路，但显然获得未来的 Page 序列是不切实际的，因此 OPT 算法只是一个理想模型，作为评判替换算法的一个最优边界。与之相反的是作为最劣边界的 Random 算法，其思路是完全随机的替换。
大多数的情况下， Page 的访问其实是有热度区分的，这也就给替换算法一个通过历史序列判断未来序列的可能，参考的指标通常有两个：
访问距离（Age）：在 Page 访问序列上，某个 Page 上一次访问到现在的距离；
引用次数（References）：某个 Page 历史上或者一段时间的历史上被访问的次数。
只考虑访问距离的 FIFO（First In First Out）算法和只考虑引用次数的 LFU（Least Frequently Used）算法都被证明在特定序列下会有巨大的缺陷。而好的实用的替换算法会同时考虑这两个因素，其中有我们熟悉的 LRU（Least Recently Used）算法以及 Clocks 算法。本文接下来会详细的介绍 InnoDB 中的 LRU 替换算法的实现，除此之外，还会包括如何实现高效的 Page 查找、内存管理、刷脏策略以及 Page 的并发访问。
02. 使用方式
首先，我们来看在 InnoDB 中，Buffer Pool 的功能是如何被使用的。
《B+树数据库加锁历史》以及《B+树数据库故障恢复概述》两篇文章中，指出 B+树数据库为了获得更高的事务并发度，在并发控制和故障恢复中都区分逻辑内容和物理内容。其中物理内容指的就是就是对 Page 的访问，一个逻辑事务可以在不同时刻发起并提交多个 System Transaction，System Transaction 会在很短的时间内就提交，并且不需要回滚；通常只会涉及几个 Page，比如发生分裂或合并的父子节点，数据节点和 Undo 节点；System Transaction 通过 Redo + No Steal 的方式保证多个 Page 的 Crash Safe；不同 System Transaction 之间会通过比 Lock 更轻量的 Latch 来保证安全的并发访问。
简而言之，System Transaction 需要依次获取几个不同的 Page，对获取的 Page 加 Latch，使用或修改 Page，并写 Redo Log，来保证多个 Page 访问的原子。在 InnoDB 中这个 System Transaction 就是 MTR（Mini-Transaction）。而 Buffer Pool 提供的就是通过 Page No 获取对应 Page 的接口。因此可以说，在 InnoDB 中 MTR（Min-Transaction）就是 Buffer Pool 的主要使用方式。
1. 上层用调用 buf_page_get_gen 获取需要的 Page
如下是上层通过 Buffer Pool 获取一个需要的 Page 的代码，buf_page_get_gen 接口对应上面提到的 FIX 接口：
其中 buf_block_t 是 Page 对应的内存管理结构，通过 block->frame 指针可以访问完整的 Page 内容；第一个参数 page_id 指定需要获取的 Page 号，这个 page_id 通常是通过上层的 BTree 搜索得到；第三个参数 rw_latch 指定需要对 Page 加的读写 Latch 模式；最后一个 mtr 参数就是上面提到的 Mini-Transaction，同一个 mtr 访问多个 page 时，会将这个 mtr 结构在每次调用 buf_page_get_gen 的时候传递下去。
2. buf_page_get_gen 内部获取 Page 并标记 FIX 及加锁
在 buf_page_get_gen 内部首先需要获取需要的 Page，这个过程会在后面详细介绍，在此之后会做两件事清，标记 page 的 FIX 状态（page->buf_fix_count），阻止 Page 的换出，以及对 Page 加对应的 rw_latch 模式的的锁（block->lock）。
3. MTR Commit 的时候释放 Lock
MTR 结构中会包含一个或多个已经持有锁的 Page，最后 mtr 提交的时候，一起做 UNFIX 并放锁：
通过本节的介绍，我们已经了解了 InnoDB 是中是如何使用 Buffer Pool 提供的接口访问 Page 的了，在具体介绍如何维护 Page 支持高效的查找和刷脏之前，我们先从整体上了解一下 Buffer Pool 的组织结构。
03. 组织结构
为了减少并发访问的冲突，InnoDB 将 Buffer Pool 划分为 innodb_buffer_pool_instances 个 Buffer Pool Instances，Instance 之间没有锁冲突，每个 Page 固定属于其中一个 Instance。从结构上看每个 Instance 都是对等的，因此本文接下来的内容都以一个 Instance 来进行介绍的。
▶︎ Block、Page 和 Chunk
Buffer Pool 将分配的内存大小划分为相等的 Block，同时为每一个 Block 分配了一个内存管理结构 buf_block_t，用来维护 Block 相关的状态信息、加锁信息、内存数据结构指针等。Block 是 Page 在内存中的载体，很多场景下他就是 Page。代码上看 buf_block_t 的开头就是维护 Page 信息的 buf_page_t（其中包括 page_id，发生修改的 lsn 信息 oldest_modification, newest_modification 等），从而他们之间可以直接做类型强制转换：
单个 buf_block_t 需要几百个字节存储，以 100G 的 Buffer Pool，16KB 的 Page Size 为例，将会有 6M 个 Block，这么多的 buf_block_t 的内存占用也是非常可观的。为了方便这部分内存的分配和管理，InnoDB 将其直接拼接到 Block 数组之前，这也是为什么 Buffer Pool 的实际内存占用会看到略大于配置的 innodb_buffer_pool_size。后来为了方便在线调整大小，从 5.7 开始 Buffer Pool 又将内存划分为默认 128MB 的 Chunk，每个 Chunk 内部都是如下的内存结构：
在启动时，buf_chunk_init 函数中通过 mmap 分配 Buffer Pool 需要的所有内存，因此 InnoDB 在启动时并不会真正占用这么大的物理内存，而是随着 Page 的分配不断上涨的。另外，由于每个 Block 的内存地址要求按照 Page Size 对齐，而 buf_block_t 并不是一定存在 Page Size 的约数关系，在 Page 数组的之前还可能有部分不会使用的内存碎片。
▶︎ Hash Map、LRU List、Free List、Flush List
从使用的角度出发， 用指定的 page_id 调用接口 buf_page_get_gen 是一个统一且非常频繁的操作，InnoDB 用一个从 page_id 到 Block 的 Hash Map 来支持高效的查询，所有在 Buffer Pool 中的 Page 都可以在 Hash Map 中找到。这个 Hash Map 采用链式冲突的方式实现，通过 buf_pool_t 中的 page_hash 指针访问。
除此之外，Buffer Pool 在内存中还维护了很多的链表来管理 Block，其中 LRU List 承担的就是 LRU 替换算法中的栈的功能，Block 被访问到时会被移动到 LRU List 的 Header 上，而长期未被访问的 Page 会逐步的被推到 LRU List 的 Tail 位置，直至被换出。
Free List 中维护的是尚未被使用到的 Block，每一个 Block，在同一时刻一定存在于 LRU List 或者 Free List 上。被修改的 Page 在 InnoDB 中被称为脏页，脏页需要在合适的时候进行刷盘。为了获取可以 Checkpoint 的位置，推进尚未刷脏的最小脏页位置是必要的，因此需要一个按 oldest_modification 有序的脏页序列，这就是 Flush List 的意义，脏页一定是在使用中的 Block，因此一定同时也在 LRU List 上。整个内存结构如下图所示：
04. 获取 Page
作为 Buffer Pool 统一的对外接口，buf_page_get_gen 会首先用给定的 Page ID 从 Hash Map 中查找对应的 Page，最简单的，该 Page 已经在 Buffer Pool，可以直接标记 FIX 加 Lock 后返回。对良好配置的 Buffer Pool，绝大多数的 Page 需求都是可以在这里就满足的。show engine innodb status 命令结果的 Buffer Pool Section 中有专门的 hit rate 的统计。如果 Page 还不在 Buffer Pool 就需要找到一块空闲的内存 Block，初始化内存结构，然后将磁盘对应的 Page 加载进来。
▶︎ 获取 Free Block
获取空闲 Block 的逻辑在函数 buf_LRU_get_free_block 中实现。
Free List 中维护了所有的空闲 Block，可以通过 buf_LRU_get_free_only 直接摘取一个下来使用。但更常见的情况是，Free List 根本没有 Block，所有的 Block 已经都在 LRU List 上。这个时候就需要 LRU 替换算法来踢出一个已有的 Page，将其 Block 分配给新的 Page 使用。buf_LRU_scan_and_free_block 会从 LRU 的尾部向前遍历 innodb_lru_scan_depth 个 Page，被选择的 Page 必须要满足三个条件：不是脏页、没有被上层 FIX 以及没有在 IO 过程中。如果没有找到满足条件的 Page，第二轮的遍历就会覆盖整 LRU。
极端条件下，到这里仍然没能获得一个可以逐出的 Page，可能是因为脏页太多导致，这个时候就需要通过 buf_flush_single_page_from_LRU 来直接 Flush 一个没有被 FIX，且没有 IO 的 Page，之后将其变成一个上面讲到的可以逐出的 Page。被选择可以逐出的 Page 会通过 buf_LRU_free_page 从 LRU List 及 Page Hash 中删除，之后加入到 Free List 中，供本次访问的 Page 使用。
▶︎ 填充新的 Page 内容
获取到的 Free Block 会先通过 buf_page_init 进行初始化，其中会对 buf_block_t，包括 buf_page_t 的字段进行初始化和填充，之后加入到 Hash Map 中，并通过 buf_LRU_add_block 加入到 LRU List。最后在通过磁盘 IO 将 Page 数据填充到 buf_block_t 的 frame 字段中。在 IO 读取的过程中会对 Page 标记 IO FIX 状态来阻止其他线程 buf_page_get_gen 时的换出，并且持有 buf_block_t 的 lock 来阻止其他线程对 Page 内容的访问。
为了更好的利用磁盘的顺序读性能，InnoDB 还支持两种预读方式，每当读一个 Page 成功后都会判断是否要将周围 Page 一起加载进 Buffer Pool，随机预读会参考同一个 Extend 中最近是不是有大量 Page 被访问，可以通过 innodb_random_read_ahead 配置，而顺序预读参考的是是否有大量的 Page 正在顺序被访问到，可以通过 innodb_read_ahead_threshold 配置。
05. LRU 实现
严格的 LRU 替换算法，会在每次被访问的时候，将对应的 Page 移动到 LRU List 的 Header，也就是提升近期刚访问 Page 的热度，使之更不容易被换出。但这样的实现会存在一个问题，通常数据库的一个 Scan 操作可能会访问到大量的，甚至超过内存容量的 Page 数，但这些 Page 在 Scan 结束后可能并不会继续被使用，在这个过程中，LRU List 被整个替换一遍，导致 Scan 操作结束后的一段时间内，Buffer Pool 的命中率变的很低。这当然是我们不愿意看到的。
InnoDB 应对这个问题的方式，是将LRU List分成两段，如下图所示是LRU实现的示意图，通过一个 Midpoint 将整个 List 分为 New Sublist 和 Old Sublist，每次需要 Page 换出的时候会从 List 的尾部选择：
当 LRU List 的长度超过 BUF_LRU_OLD_MIN_LEN(512)时，新的插入会开始维护出 Midpoint 位置，实现里是一个叫做 LRU_old 的指针，该指针指向 LRU List 距离 Tail 大约 3/8 的位置。之后新的 buf_LRU_add_block 都会将 Page 插入到 LRU_old 的位置，而不是 LRU List 的 Header。每次 Page 插入或者删除时，都需要通过 buf_LRU_old_adjust_len 来尝试调整 LRU_old 位置，尽量将 LRU_old 指针保持在 3/8 的位置，之所以说尽量，是因为 InnoDB 中为了避免频繁的调整 LRU_old，设置了 BUF_LRU_OLD_TOLERANCE(20)的容忍区间。
那么，什么时候会插入到 Header 呢？每次通过 buf_page_get_gen 获取一个 Page 以后，无论是直接命中还是从磁盘换入，都会通过 buf_page_make_young_if_needed 判断是否移动这个 Page 到 LRU List 的 Header 位置，选择移动的有两种情况：
如果这个 Page 是在 LRU_old 之后的位置，那么必须满足距离首次访问超过 innodb_old_blocks_time 参数配置的时间，如此一来，无论多大的 Scan 操作最多只会污染大约 3/8 的 LRU List，避免了前面所说的 Buffer Pool 效率降低问题。
如果这个 Page 在 LRU_old 之前的位置，那么需要距离 LRU List 的 Header 超过大约 1/6 的位置，这个做法是为了避免太热的 Page 频繁的反复向 LRU Header 插入。
06. Flush
Buffer Pool 中发生修改的 Page 被称为脏页，脏页最终是需要写回到磁盘中的，这个就是 Buffer Pool 的 Flush 过程。脏页除了在 LRU List 上之外，还会被插入到 Flush List，Flush List 上的 Page 大体是按照 oldest_modification 有序排列的，但实现上因为并发的原因，其实是接受了在一个小范围（log_sys->recent_closed 的容量大小）内存在乱序的，当然这一点需要在确认checkpoint位置的时候做处理。
▶︎ 脏页的产生
首先，先来看脏页产生的过程。当 DB 需要修改的 Page 的时候会在 buf_page_get_gen 获取的 Page 的时候指定 RW_X_LATCH 的 latch 模式，来对获得到的 Page 加 X Lock；之后修改 Page 内容的同时，将对应的 Redo Log 写入到独占的 Min-transaction buffer 中；Min-transaction commit 的时候将 log 拷贝到全局的 Log Buffer 中，并通过 buf_flush_note_modification 函数将该 Page 加入到 Buffer Pool 的 Flush List 上面，并用 mtr 的 start_lsn 及 end_lsn 更新 Page 的 oldest_modification 及 newest_modification。
▶︎ 刷脏时机
脏页最终是需要写回到磁盘中的，而这个写回时机，其实是数据库的故障恢复策略决定的，InnoDB 采用了《数据库故障恢复机制的前世今生》中介绍的 Redo + Undo 的策略，将 Page 的刷脏跟事务的提交时间完全剥离开来，使得 Buffer Pool 的刷脏策略可以更灵活。理论上讲，假设 Buffer Pool 足够大，那么将 Page 一直缓存在 Buffer Pool 中，等所有的修改完成再写 Page 一定是最高效的，因为这样最小化了相对于内存访问很慢的磁盘 IO。但显然，这是不现实的，主要影响因素有两个，这两个因素也决定了 InnoDB Buffer Pool 的刷脏时机：
脏页总量：
由于通常 Buffer Pool 的容量都是远小于磁盘数据总量的，当内存不足时需要通过 LRU 换出老 Page，前面也提到了脏页是不能直接被换出的。
脏页总量的因素倾向于优先 Flush LRU Tail 附近 Page。
Active Redo 总量：
也就是 Checkpoint LSN 之后的 Redo 总量，《庖丁解InnoDB之REDO LOG》[8]]中介绍过，InnoDB 的 Redo 是在 innodb_log_files_in_group 配置的 redo 数量中循环使用的，落后 Checkpoint 会导 Active Redo 总量过高，致使剩余可用的 Redo 空间不足，而最老脏页的位置是限制 Checkpoint 推进的最直接原因。
Active Redo 总量因素倾向于优先将 oldest_modification 最小的 Page，也就是 Flush List 的 Tail 位置进行刷脏。
依据这两个因素，InnoDB 的 Buffer Pool 提供了三种模式的 Flush，其中 Single Flush 应对的是脏页总量过高的极端情况，由用户线程在完全找不到可以换出的 Clean Page 时触发，每次同步刷一个 Page；而 Sync Flush 可以认为是应对 Active Redo 总量过高的极端情况，在可用的 Redo 空间严重不足或需要强制推进 Checkpoint 时触发，Sync Flush 会尽可能的将 oldest_modification 小于制定 LSN 的 Page 全部刷脏，因此可能会涉及大量 Page，从而严重影响用户请求。因此，理想情况下，这两种刷脏模式都是应该尽量避免的。而更多的时候应该依靠的是后台一直在运行的 Batch Flush。
▶︎ Batch Flush
Batch Flush 由一个 Page Coordinator 线程和一组 Page Cleaner 线程负责，具体的个数跟 Buffer Pool 的 Instance 数绑定，所有的线程共用一个 page_cleaner_t 结构体来做一些统计和状态管理。
通常情况下 Page Coordinator 会周期性被唤醒，通过 page_cleaner_flush_pages_recommendation 计算每一轮需要刷脏的 Page 数，然后将这个需求下发给所有的 Page Cleaner 线程，并等待所有的 Page Cleaner 刷脏完毕，Page Coordinator 自己也会承担一份刷脏任务。而 page_cleaner_flush_pages_recommendation 判断刷脏量的时候，会综合考虑当前的脏页总量，Active Redo 总量，以及磁盘 IO 的承载能，其中磁盘能力这个可以通过参数 innodb_io_capacity 以及 innodb_io_capacity_max 指定，下面是整理过的计算公式：
静态脏页总量（pct_for_dirty）:
根据当前已有的脏页总量计算的一个刷脏比例。
脏页量低于 innodb_max_dirty_pages_pct_lwm 不刷脏，高于 innodb_max_dirty_pages_pct_lwm，则按脏页量占 innodb_max_dirty_pages_pct 的百分比刷脏，也就说大于 innodb_max_dirty_pages_pctpct_for_diry 就会成为百分百。
也就是说，pct_for_dirty 是一个在 pct_lwm 到 pct 之间，从 0 到 100 按脏页率线性增长的值。
静态 Active Redo（pct_for_lsn）:
根据当前的 Active Redo 计算的刷脏比例。
如果 Active Redo 的量超过了一个接近 Redo 空间满的值 log_sys->max_modified_age_async，或者用户配置了 innodb_adaptive_flushing，这里就用当前的 Active Redo 水位计算一个 pct_for_lsn，这里实现上不是一个纯线性的关系，而是随着 Active Redo 的增加 pct_for_lsn 增长速度也在加快。
动态脏页量变化（avg_page_rate）:
由于 n_pages 的判断过程是一个周期的打点行为，只考虑静态的水位显然是不够的，这里还会将这个周期内的脏页增长速率作为一个因素计算进来。
动态 Active Redo 变化（pages_for_lsn）:
类似的这里也会考虑周期内的 Redo 增长速率，这里的计算方式是将单位时间内 Redo 的增长之后的 LSN，投影到 BP 中 Page 的 oldest_modification 上，所覆盖的 Page 数就是 pages_for_lsn 的值。
通过上面过程计算出的 n_pages 数，会平分给多个 Page Cleaner，然后将他们唤醒。每个 Page Cleaner 会负责自己独立的 Buffer Pool Instance，因此之间没有冲突，每个 Page Cleaner 被唤醒后，会先后从 LRU List 及 Flush List 上进行刷脏，一轮刷脏结束后才会发起下一轮的刷脏。
之所以要从 LRU List 做刷脏还是为了保持足够用的 Free Page，因此只有当 Free List 上的 Page 小于 innodb_lru_scan_depth 的时候才会发起。如果不是脏页可以直接用 buf_LRU_free_page 从 LRU 上删除，否则还需要调用 buf_flush_page_and_try_neighbors 先进行刷脏，从函数名字也可以看出，刷每一个 Page 的时候都会尝试对其周围的其他脏页也进行 Flush，这个主要还是为了利用磁盘的顺序写性能，可以通过 innodb_flush_neighbors 配置开关。如果从 LRU List 上没有 Flush 足够量的 Page 就需要遍历 Flush List，同样调用 buf_flush_page_and_try_neighbors 进行刷脏。
无论哪种方式的刷脏，最终都会进入 buf_flush_write_block_low 写盘，除了 Single Flush 以外，所有的 Flush 操作都是异步进行的，IO 结束后会在 IO 线程中回调 buf_page_io_complete 做收尾工作，包括清空 IO FIX 状态，释放 Page Lock，以及从 Flush List 和 LRU List 上删除。
07. 并发控制
InnoDB 中可能存在大量的线程同时竞争访问 Buffer Pool，包括所有通过 buf_page_get_gen 获取 Page 的用户线程和后台线程；上面提到的 Flush 线程；以及 IO 线程。
作为整个数据库的数据中枢，Buffer Pool 对并发访问的支持能力直接影响数据库的性能，从代码中也可以看出其中有大量锁相关的逻辑，作为一个工业级的数据库实现，这些逻辑都经过了大量细节上的优化，一定程度上增加了代码的复杂性。而锁的优化思路，无外乎降低锁粒度，减少锁时间，消除锁请求等，本节就沿着这样的思路介绍 Buffer Pool 中锁的设计与实现。
Buffer Pool 中涉及到的锁，按照锁保护对象的层次，依次分为：保护 Hash 表的 Hash Map Lock、保护 List 结构的 List Mutex、保护 buf_block_t 中结构的 Block Mutex、保护真正的 Page 内容的 Page Frame Lock。
▶︎ Hash Map Lock
所有的 buf_page_get_gen 请求的第一步就是通过 Hash Map 判断 Block 是否存在于 Buffer Pool 中，可想而知这里的竞争是极其强烈的，InnoDB 中采用了分区锁的办法，分区的数量可以通过 innodb_page_hash_locks（16）来配置，每个分区会维护一个独立的读写锁。每次请求会先通过 page_id 映射到一个分区上，然后请求这个分区的读写锁。如此一来只有映射到同一个分区的请求才会产生所冲突。
▶︎ List Mutex
上面讲过 Buffer Pool 中的 Block 是按照 List 维护的，最基础的包括维护全量使用 Block 的 LRU List，空闲页的 Free List，以及脏页的 Flush List。这些 List 都有自己独立的互斥锁 Mutex，对 List 的读取或修改都需要持有 List 本身的 Mutex。这些锁的目的是保护对应的 List 本身的数据结构，因此会最小化到对 List 本身数据结构访问和修改的范围内。
▶︎ Block Mutex
每个 Page 的控制结构体 buf_block_t 上都有一个 block->mutex 用来保护这个 block 的一些诸如 io_fix，buf_fix_count、访问时间等状态信息。相对于外层无论是 Hash Map 还是 List Mutex，Block Mutex 的锁粒度都小的很多，通过 Block Mutex 来避免更长时间的持有上层容器的锁显然是划算的。
而 io_fix，buf_fix_count 这些信息也能显著的减少对 Page Lock 的争抢， 比如当 Buffer Pool 需要从 LRU 上踢出一个老 Page 时，需要确定这个 Page 没有正在被使用，以及没有在做 IO 操作，这个是个非常常见的行为，但他本身其实并不关心 Page 的内容。这时，短暂的持有 Block Mutex 并判断 io_fix 状态和 buf_fix_count 计数，显然会比争抢 Page Frame Lock 更轻量。
▶︎ Page Frame Lock
除了 Block Mutex，buf_block_t 上还有一个读写锁结构 block->lock，这个读写锁保护的是真正的 page 内容，也就是 block->frame。这个锁就是《B+树数据库加锁历史》一文中讲到的保护 Page 的 Latch，在对 B+Tree 的遍历和修改中都可能需要获取这把锁，除此之外，涉及到 Page 的 IO 的过程中也需要持有这把锁，Page 读 IO 由于需要直接修改内存 frame 内容，需要持有 X lock，而写 IO 的过程持有的是 SX Lock，来避免有其他写 IO 操作同时发生。
▶︎ 死锁避免
当上面这些锁中的多个需要同时获取时，为了避免不同线程间发生死锁，InnoDB 规定了严格的加锁顺序，也就是 Latch Order，如下所示，所有对锁的获取必须要按照这个顺序从下往上进行。这个顺序跟大多数场景的使用是一致的，但也是有例外的，比如从 Flush List 上选择 Page 进行刷脏的时候，由于 Flush List Mutex 的级别比较低，可以看到放掉 Flush List Mutex 再去获取 Block Mutex 的情况。
▶︎ 示例场景
为了更好的理解 Buffer Pool 的加锁过程，我们设想这样一种场景：一个用户读请求，需要通过 buf_page_get_gen 来获取 Page a，首先查找 Hash Map 发现其不在内存，检查 Free List 发现也没有空页，只好从 LRU 的 Tail 先踢出一个老的 Page，将其 Block A 加入 Free List，之后再从磁盘将 Page a 读入 Block A，最后获得这个 Page a，并持有其 Lock 及 FIX 状态。得到一个如下表所示的加锁过程：
这张表中可以清楚的看到：
每种锁都限制在真正操作其保护的数据结构的较小范围内；
当需要同时持有多个锁时，严格遵守上面说的 Latch Order，比如从 LRU 和 Hash Map 中加入或删除时，严格遵守 LRU List Mutex -> Hash Map Mutex -> Block Mutex 的顺序。
在 IO 过程中，除了 Page Frame Lock 外不持有任何锁，同时也通过设置 io_fix，避免了诸如 LRU 算法检查是否可以换出时，对 Page Frame Lock 加锁。篇幅关系，这里只介绍了这一种场景的加锁顺序，更多的内容可以见链接：Flush List刷脏加锁，LRU List刷脏加锁。
08. 总结
本文聚焦于 InnoDB 中的 Buffer Pool 的核心功能，首先从宏观上介绍其背景，包括设计目标、接口、遇到的问题及替换算法的选择等；然后从使用者的角度介绍了 Buffer Pool 作为一个整体对外暴露的统一接口和调用方式；之后介绍了 Buffer Pool 内部获取 Page 的详细过程以及 LRU 替换算法的实现；再之后介绍了 Page 刷脏的触发因素及过程；最后梳理了 Buffer Pool 如何安全的实现高并发高性能。
微信公众号「阿里云瑶池数据库」 2023-06-19 加入
瑶池，喻指汇聚宝藏之地。阿里云瑶池数据库，汇集数据无价之宝，让数据业务持续在线，数据价值不断放大。
评论