前言

Flush List介绍

一些说明，

  • Page：内存结构记录了oldest_modification，自从载入Buffer Pool后修改该Page的第一个Redo日志的LSN（即是最小的LSN）
  • Flush List：按照oldest_modification排序，沿着链表头方向，Page的oldest_modification增大（头插法）
  • Page Cleaner线程：从Flush List尾部开始遍历，依次将Page刷写入磁盘中

同一个Page可能被修改多次（如图中，Page5被LSN=6和LSN=10的两条日志修改过）：

  • 那么Page Cleaner刷写Page5时，会同时LSN=6和LSN=10两条日志的“变更”持久化=>导致Redo Log中暂时的出现“未持久化变更“的“日志空洞”

  • Checkpoint“参考”oldest_modification，只能取checkpoint_lsn=6

    约束

    【Flush-List的顺序约束】MTR1（LSN1和Page1）和MTR2（LSN2和Page2）：

  • 如果LSN1<LSN2，Page1先于Page2插入Flush-List

这个约束，即Flush-List的有序性，是InnoDB Checkpoint机制的前提。否则，Checkpoint无法正确的向前推进：
【例1】Flush-List不再有序：

MySQL 8.0的优化点

这里主要介绍和分析MySQL 8.0的两个优化点：

  • 【Redo Log 】 “串行写入”的Log Buffer => “并行写入”的Log Buffer
  • 【Buffer Pool】 “严格顺序”的Flush List => “宽松顺序”的Flush List

【附】MTR提交时的步骤

Log Buffer为串行写入：所有的用户线程去争抢一个“log buffer的mutex”（代码中为log_sys->mutex）

Link_buf —- “无锁”的数据结构

Link_buf是一个环形数组，数组的每一个位置称作一个Slot：

  • 每个Slot有两个属性：位置（index）和值（value）
  • Linkbuf的大小定义为“Slot的数量”，记为L_
  • 每个Slot的值原子地更新
  • 每个Slot的值初始化为0，当在位置idx写入值n：表示（idx，idx+n）这个区间被“使用”
  • 一个独立的线程通过由数组头->尾的遍历，来追踪连续被“使用”的最大可达区间（具体追踪方法，见下节）
  • 一般地，记最大可达连续区间的右端点，记为M

并发写入的Log Buffer

Redo日志（Log Buffer + Log Files）系统可以抽象为生产者-消费者模型：

  • 多个生产者：用户线程
  • 一个消费者：Crash Recovery时的主线程

因此需要保证Redo日志系统（Log Buffer + Log Files）的线程安全

【MySQL < 8.0】线程安全的设计：

什么是Log Buffer的线程安全？

  • MTR提交时（拷贝日志到公共Log Buffer），日志全部地，连续地拷贝至Log Buffer相应的位置；MTR内的日志拷贝至公共Log Buffer中也是连续的，不会在以后被其余的MTR日志覆盖

在MTR将私有Redo日志提交到公共Log Buffer时：

  • 互斥地获得start_lsn（写入到公共Log Buffer的位置）

  • 互斥地“拷贝”

    【MySQL >= 8.0】线程安全的设计：

    在MTR将私有Redo日志提交到公共Log Buffer时：

  • 互斥地获得start_lsn（写入到公共Log Buffer的位置），std::atomic实现

  • 并发地“拷贝”

具体地，采用无锁的环形数组recent_written（Link_buf类型）实现（Log Buffer是环形写入的）。流程为：

  1. 每次准备拷贝日志到Log Buffer时，先向Log Buffer申请一段“预留区间”（start_lsn，end_lsn）【例2】假设Log Buffer容量（buf_size）是50 Byte，刚刚把一段日志（10，20）从Log Buffer中刷入文件Cache中（尚未保证sync）：
    • flushed_lsn = 10：直到LSN=10的日志持久化到了磁盘文件中
    • write_lsn=20：直到LSN=20的日志已写入到文件缓存中
    • sn_limit_for_end = write_lsn + buf_size = 20 + 50 = 70：表示如果当前Log Buffer写满了的话（从write_lsn写到尾部，在从头部开始写到“write_lsn的位置”），最大的LSN就是70
  2. 在recent_written中位置（startlsn/recent_written.L_）写入值（end_lsn - start_lsn）,表示一个从start_lsn指向end_lsn的“Link”

【总结】recent_written**记录了“有哪些日志已经写入了Log Buffer中”**
这个流程记为第一阶段
【1】Log Buffer类似这样（是环形数组，图中未表示）

【2】当我们又写入了一批日志

【3】触发特定的线程（log_writter）扫描recent_written，更新M

【4】异步地更新recent_written的M，赋值给buf_ready_for_write_lsn，表示Log Buffer中连续的可以被写入磁盘的LSN的最大值

“宽松顺序”（Relax-Order）的Flush-List

MySQL 5.6/5.7

红色部分保证了【Flush-List约束】
紫色部分保证了并发插入Flush-List的线程安全（对链表Prev/Next指针的修改）

MySQL 8.0

MySQL 8.0去掉了flushorder.mutex，不再保证Flush-List全局有序；取而代之的是只保证Flush-List局部有序
类似于Log Buffer使用recent_written，这里也使用一个Link_buf数组，叫做recent_closed_
流程为：

  1. 在第一阶段完成之后，需要将日志（start_lsn，end_lsn）产生的脏页加入到Flush-List中
  2. 当start_lsn - **recent**_closed.M > recent_closed.L时，阻塞；否则，向下执行【例3】recent_closed大小（capacity）是50，M是20，MTR提交时，产生的日志start_lsn=80 80-20>50，意味着80%50>20，那么MTR在此处阻塞，否则将写入到已被预留的Slot（图中的红色区域） !!
  3. 将日志（start_lsn，end_lsn）产生的脏页加入到Flush-List中
  4. 在recent_closed中位置（startlsn/recent_closed.L_）写入值（end_lsn - start_lsn）,表示一个从start_lsn指向end_lsn的“Link”
  5. Logcloser线程异步的更新**_recent_closed**的M

【总结】recent_closed记录了“有哪些日志产生的脏页已经加入到Flush-List中”

【Flush-List的顺序约束-8.0】MTR1（LSN1和Page1）和MTR2（LSN2和Page2）：

  • 【1】若0 < LSN1 - LSN2 < L，Page1和Page2在Flush-List中无必然的先后关系
  • 【2】若LSN1 - LSN2 > L，Page2比Page1先插入到Flush-List中

MySQL 5.6/5.7是：

  • 若LSN1 - LSN2 > 0，Page2比Page1先插入到Flush-List中

MySQL 8.0是：

  • 若LSN1 - LSN2 > L，Page2比Page1先插入到Flush-List中

运行中的recent_closed和Flush-List类似下图：橙色方框内的Page按照oldest_modification无序；橙色方框内的Page按照oldest_modification有序（即集合{74，76，77，75}任一元素均大于集合{72，73，71}）

下图的每个紫色方块为一个脏页，纵坐标为脏页的oldest_modifaction，横坐标为脏页加入到Flush-List的时间

  • OLD_DESIGN：脏页的oldest_modifaction越小，插入到Flush-List的时间越早
  • NEW_DESIGN：在同一个“L区间”，Page无序；在不同的“L区间”，Page有序

注：Flush-List采用头插法，越早插入的页越靠近链表尾部
【Flush-List的顺序约束】是InnoDB Checkpoint的重要前提，而【Flush-List的顺序约束】不再保证，那么Checkpoint如何设计？

MySQL 8.0的Checkpoint

MySQL 8.0由log_checkpointer线程负责定期的生成checkpoint_lsn

Checkpoint 1

  1. Log Buffer中Redo日志（修改的Page）已加入到Flush-List的“Low-Water Mark”，记为C1
    C1 = recent_closed.M
    【例4】LSN=6、7、9、10、12的Redo日志修改的Page已加入到Flush-List中，“Low-Water Mark”就是7（因为日志LSN=8产生的Page尚未加入Flush-List）

    Checkpoint 2

    Flush-List中的尾部第一个、不属于临时表空间的Page记为P：
  • 记为C2= P.oldest_modification - L

记P’是LSN=P.oldestmodification_lsn - L的Redo修改的脏页
**（脏页）P’已经被持久化_**
【证明】根据【Flush-List的顺序约束-8.0】，一定早于P加入到Flush-List中：要么P’已被移除Flush-List（刷写入磁盘），要么P’在P的前面（靠近尾部）

  • 要么P’在P的前面（靠近尾部）与P是Flush-List尾部第一个Page矛盾

    计算最终的checkpoint_lsn

    C1：若Redo日志的LSNC2：若Redo日志的LSN<C2，那么该Redo日志产生的脏页已经刷写到磁盘

情况一：C2 < 0
Flush-List刚被清空，或者数据库刚启动不久
情况二：0< C2 < last_checkpoint_lsn
数据库运行时，但Flush-List长度“突然”变短
【例5】假设flushed_lsn从始至终都是10，Time=1之前没有做过Checkpoint（last_checkpoint_lsn = 0）

情况三：C2 > last_checkpoint_lsn
一般的，数据库运行时
【注意】我们期望找到目前最大的LSN，记为L’，使得：

  • 若Redo日志的LSN<L’，那么该Redo日志产生的脏页已经刷写到磁盘

但通过Flush-List，我们只能保证C2“之前”的Redo满足此要求，C2“之前”的Redo可能满足、可能不满足
因为C2的存在，MySQL 8.0的checkpoint_lsn相对于MySQL 5.6/5.7“不那么精确”

Checkpoint带来的问题

选取C2 = Page.oldestmodification_lsn - L，**可能导致checkpointlsn并未指向一个日志记录的开始__，而是中间**。比如继续上面的例子：

  • MTR1产生日志记录R1：LSN=1，长度10
  • 那么，MTR2产生的日志记录R2：LSN=11
  • L = 5，MTR2在Flush-List的头部：checkpoint_lsn可以是11（R2的LSN） - L = 6；指向了R1的中间

这需要我们继续修改Crash Recovery的设计

MySQL 8.0的Crash Recovery

当checkpoint_lsn指向日志记录的中间时：

  • 通过checkpoint_lsn找到Block的LOG_BLOCK_FIRST_REC_GROUP（Log Block中第一条Redo日志的偏移）
  • 从该Log Block的第一个日志记录（LOG_BLOCK_FIRST_REC_GROUP）依次向后扫描/解析，直至日志记录的LSN>=checkpoint_lsn
  • 从该LSN开始进行崩溃恢复

    遗留问题

  1. flush_order mutex的粒度，只是保护链表指针的修改？2. flush list做成有序链表的代价？用红黑树？3. C2的实现，取Flush-List第一个Page，还是最后一个？

    参考

  2. MySQL · 特性分析 · 8.0 对WAL的设计修改

  3. MySQL 8.0: New Lock free, scalable WAL design
  4. Sunny+Bains%40InnoDB.pdf