Buffer Pool是InnoDB中非常重要的组成部分，也是数据库用户最关心的组件之一。Buffer Pool的基本功能并不复杂，设计实现也比较清晰，但作为一个有几十年历史的工业级数据库产品，不可避免的在代码上融合了越来越多的功能，以及很多细节的优化，从而显得有些臃肿和晦涩。本文希望聚焦在Buffer Pool的本职功能上，从其提供的接口、内存组织方式、Page获取、刷脏等方面进行介绍，其中会穿插一些重要的优化手段，之后用单独的一节介绍其中稍显复杂的并发控制，也就是各种mutex的设计及实现。而除此之外，像Change Buffer、压缩Page、Double Write Buffer等功能虽然大量的穿插在Buffer Pool的实现之中，但其本身并不属于Buffer Pool的核心逻辑，本文并不会包括这部分内容，本文代码相关内容基于MySQL 8.0[1]。
背景
传统数据库中的数据是完整的保存在磁盘上的，但计算却只能发生在内存中，因此需要有良好的机制来协调内存及磁盘的数据交互，这就是Buffer Pool存在的意义。也因此Buffer Pool通常按固定长度的Page来管理内存，从而方便的进行跟磁盘的数据换入换出。除此之外，磁盘和内存在访问性能上有着巨大的差距，如何最小化磁盘的IO就成了Buffer Pool的设计核心目标。《数据库故障恢复的前世今生》[2]一文中介绍过，主流的数据库会采用REDO LOG加UNDO LOG，而不是限制刷脏顺序的方式，来保证数据库ACID特性。这种做法也保证了Buffer Pool可以更专注地实现高效的Cache策略。 Buffer Pool作为一个整体，其对外部使用者提供的其实是非常简单的接口，我们称之为FIX-UNFIX接口[3]，之所以需要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的并发访问。
使用方式
首先，我们来看在InnoDB中，Buffer Pool的功能是如何被使用的。《B+树数据库加锁历史》[4]以及《B+树数据库故障恢复概述》[5]两篇文章中，指出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* block = buf_page_get_gen(page_id, page_size, rw_latch, guess, buf_mode, mtr);
其中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）
...
/* 1.标记page的FIX状态，阻止其被换出，这里是一个page结构上的计数器buf_fix_count */
buf_block_fix(fix_block);
...
/* 2. 对Page加对应的rw_latch模式的的Latch，也就是block结构上的lock */
mtr_memo_type_t fix_type;
switch (rw_latch) {
...
case RW_S_LATCH:
rw_lock_s_lock_inline(&fix_block->lock, 0, file, line);
fix_type = MTR_MEMO_PAGE_S_FIX;
break;
...
}
/* 最后这个block的指针以及加锁的模式还会一起记录在mtr的结构中，方便mtr commit时的释放 */
mtr_memo_push(mtr, fix_block, fix_type);
...
3. MTR Commit的时候释放Lock
MTR结构中会包含一个或多个已经持有锁的Page，最后mtr提交的时候，一起做UNFIX并放锁：
static void memo_slot_release(mtr_memo_slot_t *slot) {
switch (slot->type) {
buf_block_t *block;
case MTR_MEMO_BUF_FIX:
case MTR_MEMO_PAGE_S_FIX:
case MTR_MEMO_PAGE_SX_FIX:
case MTR_MEMO_PAGE_X_FIX:
block = reinterpret_cast<buf_block_t *>(slot->object);
/* 1. 对Page UNFIX，即buf_fix_count-- */
buf_block_unfix(block);
/* 2. 释放Page的锁，block->lock */
buf_page_release_latch(block, slot->type);
break;
...
}
...
}
通过本节的介绍，我们已经了解了InnoDB是中是如何使用Buffer Pool提供的接口访问Page的了，在具体介绍如何维护Page支持高效的查找和刷脏之前，我们先从整体上了解一下Buffer Pool的组织结构。
组织结构
为了减少并发访问的冲突，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等），从而他们之间可以直接做类型强制转换：
struct buf_block_t {
buf_page_t page; /*!< page information; this must
be the first field, so that
buf_pool->page_hash can point
to buf_page_t or buf_block_t */
...
}
单个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上。整个内存结构如下图所示：
