数据库内核月报 - 2019 / 08

MySQL · 引擎特性 · 8.0 Innodb redo log record 源码分析

Introduction

redo log对于innodb高效实现事务有至关重要的作用,关于redo log的介绍目前已有许多资料,但大都针对MySQL 5.6、MySQL 5.7版本,内容大都聚集在redo log与事务、redo log与恢复、checkpoint技术等特性上,对于redo log record本身却很少有(甚至几乎没有)资料介绍。目前8.0.16版本,redo log record一共有64种类型,对每种类型都进行详细分析是困难的。本文针对insert语句的redo log类型进行分析,重点分析B+树分裂产生新页时,redo log作为物理日志是如何准确地描述该过程。由于涉及到B+树,本文也会对innodb的数据页进行简单总结。

Index Page

关于索引页,可以查看这篇文章,此处总结索引页的一些关键设计

  • innodb page的大小由innodb_page_size确定,默认为16 KB
  • index page的结构图如下所示

FIL Header / Trailer

  • Offset(Page Number):每个表空间从0开始,该值乘以数据页的大小得到数据页在文件中的起始偏移量。在redo log通过记录该值指示操作修改了哪个页面
  • Previous/Next Page:两个指针,按照逻辑顺序(一般是主键顺序)组织成双向链表。这也可以看到,聚集索引指的是逻辑上的聚集,而物理上实际不一定是连续的。通过双向链表可以很方便进行范围查找
  • FIL_PAGE_LSN:最新被修改的LSN,用于实现幂等特性
  • FIL_PAGE_TYPE:可能的page typeindex、undo、blob等十多种
  • FIL_PAGE_ARCH_LOG_NO_OR_SPACE_IDspace id,redo log通过该值与page no唯一标识一个page

Page Header

  • Number of Directory Slots:目录槽的个数。
    • index page overview图中看到,记录从上往下涨,而目录槽从下往上堆。
    • Page Directory是一个稀疏目录,按照key排序。里面的每个slot指向了本slot中的第一个记录。
    • 当定位到一个page时,先通过page directory找到对应的slot,然后找到slot中的第一个记录,通过遍历slot内的所有记录,最终找到指定的记录
    • slot上的记录数不能太多也不能太少,对于普通记录在[4,8]区间内,如果超过则要重新整理,方法是将slot按照中间点拆分成两个,后续的目录进行平移(为了给新的slot腾出空间)
  • PAGE_HEAP_TOP:空闲空间的起始地址,
  • PAGE_N_HEAP:最高位用来标记格式(compact还是redundant),不会减少,只要有空闲空间记录就会增加
  • PAGE_FREE:删除记录的链表。
    • 当一个记录被删除时,会先被标记为delete状态,随后被purge线程彻底删除,最后用头插法加入这个链表。
    • 当一个记录被插入时,会先去page_free找,不行再用空闲空间(heap
  • PAGE_LAST_INSERT, PAGE_DIRECTION, PAGE_N_DIRECTION:上一次被插入的记录、最后一个记录插入的防线、同一个方法插入的记录数,这些都是为了加速连续插入操作
  • PAGE_N_RECS:用户的记录(不包括最大和最小记录)
  • PAGE_MAX_TRX_ID:修改此数据页的当前最大事务id
  • PAGE_LEVEL:索引页索引id
  • PAGE_INDEX_ID:索引页的索引ID
  • PAGE_BTR_SEG_LEAF,PAGE_BTR_SEG_TOP:叶子节点和非叶子节点的段头页地址

Infimum and Supremum Records

数据页上逻辑最小和最大的记录,数据页被创建时创建,不能被删除,目的是方便页内操作。

Compact Format

变长字段长度列表 NULL字段标记 记录头 字段1数据 字段2数据
0~n 0~m 5 bytes 字段1长度 字段2长度

上表是一个典型的compact格式的行记录,关于compact记录已有许多资料,具体可参考引用。 以下将补充许多资料中讲得相对模糊的地方:

  • 变长字段长度列表只记录变长字段的长度,比如VARCHAR,值得注意的是:
    • CHAR类型也会被记录,因为从mysql 4.1开始,CHR(N)中的N指的的字符个数,而不是字节个数,所以CHAR本身也需要存储其变长长度
  • 变长字段长度列表可以只有0个字节,只要行记录中没有变长字段
  • 对于一个变长字段,其字段长度最多只有2个字节,当长度小于256字节,用1字节表示,否则用2字节
  • NULL字段标记可以也只有0个字节,只要行记录中没有nullable字段
  • non-nullable字段是不会在NULL字段标记中被标记的 -NULL字段标记的标记方法:
    • 每一个nullable列都在NULL字段标记中有1 bit 对应的标记位
    • 从右往左,即第一个nullable列在最低位
    • 如果nullable列为NULL,则对应的标记位为1,否则为0
  • NULL字段标记可以不止1个字节(网上许多资料均标注这里固定采用1个字节,其实是不对的),具体可以参考这篇文章。此处简单总结下结论:
    • NULL字段标记的长度不是固定的,每8nullable列占用1个字节
    • nullable列数不足8的整数倍时,最后一个字节高位补0
    • 基于上述原因,在设计表时,并非nullalbe字段越多越节省空间
  • 记录头总是固定的5个字节,其格式如下图所示

  • 记录头其中有两位是预留位,GCS格式中用来实现instantly add column,具体原理可参考这篇文章
  • 记录头后就是各个字段的具体数据,值得注意的有:
    • 第一个字段是主键,如果没有显示指定,则innodb会隐式增加一个6字节的字段作为主键
    • 接下来是两个隐藏的字段:事务ID列以及回滚指针列,分别占6 byte 7 bytes
    • 接下来是个非主键字段,如果nullable字段且其值为NULL,则不占用空间

insert && redo log

Flow Chart

insert redo record

上表是一条insert语句对应的redo log记录。值得注意的是,这条insert语句没有涉及到instant列,也不是临时表上的插入,并且上一条记录与本记录的extra_lendata_len都相同(见compact format, 同一张表的不同记录,这两部分的长度可能不同)。

即使是同一种类型的redo record,其解析格式也可能不同,如果上一条记录与本记录的extra_lendata_len都不同,则会额外记录本条记录在page中的偏移,以及本条记录发生mismatch的位置。

关于redo log record的资料很少,本次分析是最为简单的一种,下面简单阐述该表中较为难以理解的部分:

  • compressed:一种压缩格式,从最高位开始,第几位开始为0则意味着它的字节长度,如第1位为0(0nnnnnnn,则它是1个字节的数据;如第2位为0(10nnnnnn nnnnnnnn 则它为2个字节的数据;以此类推
  • mismatch len:插入的记录与逻辑顺序上的上一条记录比对中,不一致的长度。
    • recovery发生时,通过上一条记录与redo log中记录结合,可以恢复出插入的记录。
    • 不同记录的记录头部分不一样,但在寻找mismatch点时,会跳过该部分,在恢复过程中,新insert的记录的记录头会被重新计算填充

Notes

  • offset:在构造index page record以及redo log record过程中,会使用到offset数组
    • offset数组用于标记一条记录中各个列相对于记录头的偏移
    • 该数组默认情况下从栈上分配,当表的列数超过100时,则从innodb中获取
    • 其结构如下所示:

  • rec_t*: 由于一条记录的extra以及data部分都是变长的,所以传入的指针rec_t*一般指向中间:即它的左侧是extra部分,包括变长字段长度列表、NULL标志、记录头;右侧则是各列的数据
  • LSN的值为当前已经写入的redo log长度,它没有在redo log record中记录,其原因在于:redo log block的头部中记录了本block的第一个redo log recrodLSN。在解析过程中,结合redo log record的长度可以获知该recordLSN
  • redo log的刷写不需要double write保护,原因在于redo log block的长度为512个字节,与硬盘扇区的长度一致。读写一个扇区是原子操作。

create page && redo log

可以看到,当插入一条记录时,edo log记录了对对应数据页的修改过程。但当当前page不足以放下新插入的记录时,且邻居page也没有空间时,会触发B+树的分裂操作。具体过程:

// 持有page的X-latch
btr_cur_optimistic_insert--> 
// 当前page空间不足,乐观插入失败, 
// 进行悲观插入之前,btr_pcur_open对父亲子树进行上锁
btr_cur_pessimistic_insert--> 
// 分裂,并将记录插入指定page
btr_page_split_and_insert-->  
...

create page redo log record

btr_page_split_and_insert函数中,调用btr_page_alloc分配新的page,然后调用btr_page_create创建新页,期间调用page_create_write_log生成一条类型为MLOG_COMP_PAGE_CREATEredo log记录,其典型format如下:

type space_id page_no
MLOG_COMP_PAGE_CREATE, 1 byte 1~5 bytes 1~5 bytes

接着在btr_page_set_level方法中,生成一条类型为MLOG_2BYTESrecord,记录pageB+树上的level(叶子节点的level0,根节点level为深度),其format如下所示:

type space_id page_no page_offset val
MLOG_2BYTES, 1 byte 1~5 bytes 1~5 bytes 2 bytes compressed, 1~3 bytes

接下来btr_page_set_index_id方法中,生成一条类型为MLOG_8BYTES,该record表示将对应的page(space_id + page_no )中的PAGE_INDEX_ID字段设置为val值,其format与上述MLOG_2BYTES类似

接下来btr_insert_on_non_leaf_level_func会调用btr_cur_optimistic_insert,或者btr_cur_pessimistic_insert来将聚集索引的非叶子节点的记录插入。聚集索引的非叶子节点的记录形如下:

可以看到非叶子节点的记录与用户表记录实际并没有本质区别,该过程可以看成是往page中插入一条“用户记录”。

由于B+树的分裂是个递归过程,btr_insert_on_non_leaf_level_func函数也会被递归调用,直到调整好B+树。期间会继续不断产生相应的redo record,包括但不限于类型为MLOG_COMP_REC_INSERTMLOG_COMP_PAGE_CREATEMLOG_8BYTES等的redo log record

Reference