InnoDB 的 Buffer Pool

Buffer Pool

InnoDB 记录的存储结构 中说到页是 InnoDB 中磁盘和内存交换的基本单位，大小为 16KB

每次需要访问一条记录时，都需要先根据 B+ 树索引 找到该记录所在的数据页，然后将数据页从磁盘加载到内存中。如果访问结束后，对应的数据页是否需要从内存中移除呢？

InnoDB 并没有立刻移除，而是先将数据页缓存到 Buffer Pool 中，以便下次如果还需要访问该数据页时可以无须从磁盘中加载，减少了磁盘 IO 开销！！

在 MySQL 服务启动时就向操作系统申请了一片连续的内存，专门用来缓存数据页，称之为 Buffer Pool，默认大小 128MB，最小不能低于 5MB，可以通过参数设置：

xxxxxxxxxx
[server]
innodb_buffer_pool_size 268435456  # 单位字节，268435456 / 1024 / 1024 = 256MB

Buffer Pool 结构

Buffer Pool 被划分为若干个页面，页面大小和 InnoDB 中页面大小一致，均为 16MB，从这也可以看出缓存的是页面，而非单独的记录。为了和磁盘中页面区分，Buffer Pool 中页面称之为缓冲页

为了更好的管理缓冲页，为每个缓冲页都分配了一个大小相等的控制块，记录了缓冲页的一些信息，包括：页面所属表空间编号、页号、缓冲页在 Buffer Pool 中的地址、链表节点信息等

Buffer Pool 中控制块和缓冲页的空间布局为：控制块在前，缓冲页在后。如下图所示：

在 Buffer Pool 中以每组 (控制块 + 缓冲页) 为单位分配，那么最后剩余一点内存不足以满足一组的大小，就被称之为碎片。如果 Buffer Pool 的大小设置的刚刚好，可能不会产生碎片

控制块大小大约是缓冲页的 5%，参数innodb_buffer_pool_size其实不包含控制块的大小，所以 InnoDB 在为 Buffer Pool 向操作系统申请连续内存时，这片内存会比设置的值大 5% 左右

缓冲页的哈希处理

当没有 Buffer Pool 时，访问一条记录的过程：加载索引的根页面，然后一层一层的二分遍历到叶子节点，期间用到的页面都需要从磁盘加载到磁盘中

当加入了 Buffer Pool 时，访问一条记录的过程和上面差不多，唯一不同之处在于每需要一个页面时会先检查 Buffer Pool 中是否存在，如果存在就不需要从磁盘加载

那么如何确定所需页面是否在 Buffer Pool 中呢？有一个简单粗暴的方法：遍历 Buffer Pool 中的缓冲页，看是否存在所需页面。该方法过于愚蠢！！

通过哈希表可以快速判断某个页是否在 Buffer Pool 中，以「表空间号 + 页号」为 key，「控制块」为 value

如果哈希表中有所需页的「表空间号 + 页号」key，就表示 Buffer Pool 中存在所需页，通过哈希表的 value 获取到控制块，进而获取到缓冲页

这里看到一个很有意思的问题：如果 Buffer Pool 足够大，是否可以不需要 Redis？这个问题的立足点在于 Buffer Pool 足够大，就可以把所有页面都缓存到内存中，类似于 Redis 基于内存的数据库

假设我们把一棵 B+ 树索引的全部页面都缓存到 Buffer Pool 中，那么通过该索引执行一条查询 SQL 的流程依旧是从索引的根页面二分遍历到叶子节点，时间复杂度 O(logn)

而 Redis 查询一条数据的时间复杂度可以为 O(1)，这两者还是相差很多滴。Redis 的优势还在于高效的数据结构：String、List、Hash、Set、ZSet，可以很快的查询内存中的数据

所以 Buffer Pool 只是减少了页面从磁盘加载到内存中的次数，但抛开磁盘 IO 开销的话，Buffer Pool 并没有提高查询的效率

free 链表

当需要访问一个页面时，先检查 Buffer Pool 中是否存在，可以通过哈希处理快速判断。如果 Buffer Pool 中不存在，从磁盘中加载页面，同时将页面放入 Buffer Pool 中，也就是找一个空闲缓冲页

那么如何快速从 Buffer Pool 找一个空闲缓冲页呢？同样有一个简单粗暴的方法：遍历 Buffer Pool 中的缓冲页，返回找到的第一个空闲缓冲页。该方法过于愚蠢！！

更聪明的做法是维护一个 free 链表，链表中是所有空闲缓冲页，当需要空闲缓冲页时，直接从链表中取一个即可，时间复杂度 O(1)

将所有空闲缓冲页对应的控制块作为一个节点放到 free 链表中，刚刚完成初始化的 Buffer Pool 中所有缓冲页都是空闲的，所以 free 链表中包含了所有缓冲页

每个 free 链表都有一个基节点，保存着 free 链表的头尾节点以及节点数量，只要我们获得了基节点的地址，就可以访问 free 链表

flush 链表

当缓冲页被修改过，那么内存中和磁盘中的该页面数据就会不一致，这样的页面称之为脏页

如果缓冲页数据被修改了就立刻刷新回磁盘，这样也可以，但开销会巨大。InnoDB 的做法是只标记为脏页，但不立刻刷新回磁盘，而是在未来某段时间统一刷新回磁盘

那么现在问题又来了，如何快速从 Buffer Pool 找到需要刷新回磁盘的脏页呢？遍历？？虽然可以但肯定不是，和 free 链表一样，会维护一个脏页链表，称之为 flush 链表

每个 flush 链表都有一个基节点，保存着 flush 链表的头尾节点以及节点数量，只要我们获得了基节点的地址，就可以访问 flush 链表

注意：free 链表中是空闲缓冲页，flush 链表中是被修改过的缓冲页，所以这两条链表中肯定没有相交的节点

LRU 链表

如果 Buffer Pool 用完了怎么办？我们需要采用策略淘汰一些页面，淘汰的原则就是尽量保留最近使用率高的页面，淘汰最近使用率低的页面，这样可以最大程度的减少磁盘 IO

相信学过操作系统的同学肯定都听过页面置换算法 LRU (Least Recently Used，最近最少使用)，同样的，可以维护一条 LRU 链表：(关于 LRU 算法的实现可见 手撸 LRU)

• 如果该页面不在 Buffer Pool 中，那么把页面从磁盘加载到 Buffer Pool 的缓冲页时，同时把缓冲页对应的控制块作为节点加到 LRU 链表的头部

• 如果该页面已经在 Buffer Pool 中，那么直接把该缓冲页对应的控制块移动到 LRU 链表的头部

LRU 主要是为了提高缓冲页的命中率，保留热点页面，淘汰冷门页面，可是存在两种情况，会大大降低页面的命中率：

• 预读：程序具有空间局部性，靠近当前被访问的数据，在未来很大概率会被访问到，所以 InnoDB 在加载页面时，会提前把与它相邻的数据页一起加载进来。但如果预加载的页面后续不会被访问，那么就白白将 LRU 链表头部的热点数据挤到尾部，甚至会被淘汰，大大降低了缓冲页的命中率

• 全表扫描：全表扫描需要访问聚簇索引所有叶子节点，也会加载大量页面，这些页面可能只会在全表扫描时访问一次，可是却会被放到 LUR 头部，挤掉了原来热点的缓存页，大大降低了缓冲页的命中率

总结：可能会加载一些后续不会使用的页面或者后续使用率很低的页面，将原来的热点页面挤到 LRU 链表尾部，甚至直接淘汰，大大降低了缓冲页的命中率

根据上面两种情况，将 LRU 链表按照比例划分成冷热两部分，比例可根据参数innodb_old_blocks_pct调整，默认情况下 [冷 : 热] = [37 : 63]

• 热数据：存储使用率非常高的缓冲页，称为 young 区域

• 冷数据：存储使用率不是很高的缓冲页，称为 old 区域

优化后的 LRU 链表的维护规则：

• 对于初次加载的页面，会被添加到 old 区域的头部，也就是冷数据的最前面

• 记录页面第一次访问的时间，如果最后一次和第一次访问页面的时间间隔小于规定时间，那么就不会被加入到 young 区域头部，反之就会被加入到 young 区域头部

规定时间可以通过参数innodb_old_blocks_time设置，默认 1s

下面解释一下上面两条维护规则是如何解决预读和全表扫描时的窘况：

• 预读页面可能后续不会被访问到，所以只会被添加到 old 区域，不会影响热点页面

• 全表扫描虽然可能会被访问，但只是会在很短的时间间隔内连续访问一个页面，所以对于最后一次和第一次访问时间间隔小于 1s 的页面也不会移动到 young 区域

近一步优化 LRU 链表：对于 young 区域的页面会被频繁访问，所以需要频繁的移动到 young 区域头部，存在一定的开销。优化后只有处于 young 区域后 3/4 的页面才会被移动到头部，前 1/4 的页面不需要移动到头部，节约了一部分开销

脏页刷新回磁盘

首先，在上面介绍的三种链表中，只有 flush 链表和 lru 链表中才会有脏页，更具体的：flush 链表中全是脏页，lru 链表中有部分脏页，部分干净页

有专门的后台线程负责每隔一段时间就把脏页刷新到磁盘中，这样可以不影响用户线程处理正常请求。主要的刷新方式有两种：

• 从 LRU 链表冷数据中刷新一部分页面到磁盘：后台线程定时从 LUR 链表尾部开始扫描一些页面，如果发现是脏页就刷新到磁盘，可以通过缓冲页的控制块快速判断是否为脏页

• 从 flush 链表中刷新一部分页面到磁盘：后台线程定时从 flush 链表中刷新一些页面到磁盘

有时，后台线程刷新比较慢，会导致用户线程准备加载一个磁盘页到 Buffer Pool 中时没有可以使用缓冲页，这个时候用户线程自己会尝试从 LRU 链表尾部找一个干净页或者脏页释放，也可能会从 flush 链表释放一个脏页

多 Buffer Pool 实例

在多线程情况下，访问 Buffer Pool 中各种链表都需要加索保证线程安全，所以可以把 Buffer Pool 拆分成若干个独立的 Buffer Pool，相当于锁的粒度更细，并发度更高

为了可以在 MySQL 运行时动态调整 Buffer Pool 的大小，又将每一个 Buffer Pool 实例划分为大小相等的 chunk

因为重新分配内存需要移动原来内容到新申请的内存中，非常耗时，所以每次都以 chunk 为单位向操作系统申请空间，也不需要重新移动原来的内容

总结：划分多个 Buffer Pool 是为了提高并发；划分为多个 chunk 是为了运行时动态调整内存