从5.6到8.0看MySQL写Redo进化史（上）

前段时间学习了MySQL 8.0新特性中并行写redo的功能，简单总结了其中的原理，再次回顾时发现其中很多机制需要一定的知识储备才能理解透彻，所以决定从Buffer Pool的一些基础原理着手整理一系列文章，希望能帮助大家更好的理解MySQL 8.0中并行写redo的新特性。

本文所使用数据库版本为MySQL官方5.7.17。

我们知道一般情况下数据库中的数据都是存储在磁盘上的，这样才能达到数据持久化的目的，同时大家也都知道，磁盘的读写速度与CPU的处理速度有着量级的差异，而用户使用数据库最基本的要求就是能高效的读取和存储数据，为了弥补CPU与磁盘之间读写速度的巨大差异，所有的数据库都设计了缓冲池（Buffer Pool）。

因此MySQL服务器在接收到客户端的读写请求时，首先从磁盘中加载相应的数据页到缓冲池中，如果是只读操作，过程比较简单，如果是写入或修改操作，那么针对数据的修改会先在缓冲池中完成，然后在某个合适的时刻将修改过的数据页同步到磁盘上，完成数据的持久化。如果在同步的过程中数据库crash，或者服务器宕机，那么数据是否会丢失？

当然不会，一个成熟的数据库系统都有一套完整的机制来保证写入数据的过程要么完整的完成，要么就把已经写入的部分数据恢复到没有写入之前。为了避免发生上述问题，当前事务数据库系统普遍都采用了Write Ahead Log策略，即当事务提交时，先写重做日志（Redo Log），再修改页。当发生宕机而导致数据丢失时，再通过重做日志来完成数据的恢复，这也是事务ACID中D（Durability持久性）的要求。

理论上来说，如果MySQL数据库InnoDB存储引擎的Buffer Pool足够大，就不需要将数据本身持久化，将全部的Redo Log重新执行一遍就可以恢复所有的数据。但是随着时间的积累，Redo Log会变的很大很大，如果每次都从第一条记录开始恢复，恢复的过程就会很慢，从而无法被容忍。为了减少宕机恢复的时间，就引入了Checkpoint机制，当然这只是其中一个原因，关于Checkpoint具体作用后面有详细介绍。在说Checkpoint之前我们先了解缓冲池的一些工作机制。

多种链表管理

当启动MySQL服务器的时候，需要完成对Buffer Pool的初始化过程，就是分配Buffer Pool的内存空间。但是此时并没有真实的磁盘页被缓存到Buffer Pool中（因为还没有用到），之后随着程序的运行，会不断的有磁盘上的页被缓存到Buffer Pool中，那么问题来了，从磁盘上读取一个页到Buffer Pool中的时候该放到哪个缓存页的位置呢？或者说怎么区分Buffer Pool中哪些缓存页是空闲的，哪些已经被使用了呢？为了解决这个问题，MySQL引入了一个链表把所有的空闲页都添加到链表上，这个链表就是Free链表（或者说空闲链表）。因为刚刚完成初始化的Buffer Pool中所有的缓存页都是空闲的，所以每一个缓存页都会被加入到Free链表中。每当需要从磁盘中加载一个页到Buffer Pool中时，就从Free链表中取一个空闲的缓存页，并更新Free链表的控制信息，表示该缓存页已经被使用了。

由于服务器内存是有限的，随着数据量的增长也不可能将所有的数据都缓存到Buffer Pool中，这个时候就需要一个淘汰缓存页的策略。假设我们一共访问了某个数据页n次，那么这个页已经在缓存中的次数除以n即缓存命中率，我们的期望是让缓存命中率越高越好。如何提高缓存命中率呢？MySQL采用经典LRU算法来实现。当Buffer Pool中不再有空闲的缓存页时，就需要淘汰掉部分最近很少使用的缓存页。不过，我们怎么知道哪些缓存页最近频繁使用，哪些最近很少使用呢？MySQL引入了LRU链表（Least Recently Used）来按照最近最少使用的原则去淘汰缓存页。

当数据库需要访问某个数据页时，如果该页不在Buffer Pool中，在把该页从磁盘加载到Buffer Pool中的缓存页的同时也会把该缓存页包装成一个节点添加到LRU链表头部。如果该页在Buffer Pool中，则直接把该页对应的LRU链表节点移动到链表头部。这样就能保证LRU链表的尾端就是最近最少使用的缓存页，当Free链表上的空闲页用完时，就直接淘汰LRU链表尾端的缓存页，这样处理看似合理，实则有很多问题。比如一次大表的全表扫描就会把整个LRU链表清洗一遍，其他查询语句在执行时不得不重新从磁盘中加载数据，导致缓冲池污染问题，极大地降低了缓冲池命中率。因此InnoDB将LRU链表根据midpoint位置从逻辑上按照一定比例分为两个区域：一部分存储使用频率非常高的缓存页，称为young区域（热数据），在midpoint之前；另一部分存储使用频率不是很高的缓存页，称为为old区域（冷数据）。简单的示意图如下：

LRU结构调整之后，相应的算法也发生了变化：如果某个数据页第一次从磁盘加载到Buffer Pool中，则放到midpoint位置后，也就是old区域的头部。如果该页已经在Buffer Pool中，则将其放到young区域的头部，也就是整个LRU链表的头部。这样做有什么好处呢？当Free链表中无可用空间时，就可以从old区域中淘汰一些页，而不影响young区域中的缓存页。这样全表扫描的数据页虽然会进入Buffer Pool，但是由于首次缓存时只能放在old区域，young区域不受影响，也就是只会清洗部分LRU，这在一定程度上降低了全表扫描对Buffer Pool的缓存命中率的影响。InnoDB通过参数innodb_old_blocks_pct来控制midpoint在LRU链表中的位置。

LRU算法有以下规则：

大概3/8的区域作为old区域，这些页是可能被驱逐的对象。

链表的中点（midpoint）就是old区域头部和young区域尾部的界限。

新数据的读入首先会插入到midpoint位置后old区域的头部。

如果是old区域的数据被访问到了，这个页就会变成young区域，数据页会被移动到young区域头部。

在Buffer Pool中，不管是young区域还是old区域的数据如果不会被访问到，最后都会被移动到链表的尾部作为牺牲者。

现在我们知道首次从磁盘上加载到Buffer Pool的页会放到old区域，第二次访问该页的时候便会被放到young区域，这样的设计仍然无法解决大表扫描导致缓冲池污染问题，因为一个页中有很多条记录，也就是说一次大表扫描，这个页会被读多次，自然会移动到young区域头部（MySQL读数据虽然最小单元是按页从磁盘加载到内存，但是读记录是从页中一条一条读取，每读一条记录就需要读一次数据页）。InnoDB为了优化这个问题引入了一个间隔时间机制，当第二次访问old区域的某个缓存页时，如果距离上一次访问的时间小于这个时间，那就不把这个缓存页放到young区域，这个过程称之为page not made young。而如果距离上一次访问的时间不小于这个时间，那就把这个缓存页放到young区域，这个过程称之为page made young。这样就可以降低在全表扫描时需要对页读取多次而对缓冲池的污染。InnoDB中这个间隔时间由系统变量innodb_old_blocks_time控制，如下：

它的单位是毫秒，也就意味着如果在1秒内这个页被多次扫描，这些在old区域的页也不会被加入到young区域的。只有超过这1s，这个页还能在old区域存活下去，然后才有资格被移动到young区域。

另外，前面提到了数据页的修改是先在缓冲池中进行，那么这些数据页就跟磁盘的页不一致了，这样的缓冲页称为脏页。InnoDB对于脏页的管理也是通过链表来完成，在LRU链表中被修改过的页都需要加入这个链表中，同时这个链表中的页都需要被刷新到磁盘上，因此称为FLUSH链表。修改过的页是指被加载到Buffer Pool之后第一次被修改的页，只有第一次被修改的页才用加入FLUSH链表中，多次修改的页本来已经在链表中，因此不用再次添加。需要注意的是脏页数据实际上还是在LRU链表中，而FLUSH链表中的脏页记录只是通过指针指向了LRU链表中的脏页，有关脏页刷新到磁盘的原理会在Checkpoint机制中详细介绍。

总结

下面总结一下本文介绍的几种链表（当然除了这几种主要链表之外Buffer Pool中还有其它链表，如果大家感兴趣可以自行研究）：

FREE链表：空闲缓存页列表，需要加载磁盘数据页时，首先从此列表中取缓存页。

LRU链表：缓存了所有读入Buffer Pool的数据页，包含三类。1）未修改的页面，可以从该列表中摘除，然后移到Free链表中。2）已修改还未刷新到磁盘的页面。3）已修改且已经刷新到磁盘的页面，可并为第一类。

FLUSH链表：记录了在LRU链表中被修改但还没有刷新到磁盘的数据页列表，即脏页列表。

结尾

上文提到当Free链表上的空闲页用完时，会利用LRU算法淘汰LRU链表尾端的缓存页，如果要被淘汰的页是非脏页就直接淘汰，如果要被淘汰的页是脏页，那又是通过什么机制将脏页数据写入磁盘的呢？请关注下篇文章。