通用链表结构
在写入undo日志的过程中会使用到多个链表,很多链表都有同样的节点结构,如图所示:在某个表空间内,我们可以通过一个页的页号和在页内的偏移量来唯一定位一个节点的位置,这两个信息也就相当于指向这个节点的一个指针。所以:
Pre Node Page Number 和 Pre Node Offset的组合就是指向前一个节点的指针
Next Node Page Number 和 Next Node Offset的组合就是指向后一个节点的指针。
整个List Node占用12个字节的存储空间。
为了更好的管理链表,设计InnoDB的大佬还提出了一个基节点的结构,里边存储了这个链表的头节点、尾节点以及链表长度信息,基节点的结构示意图如下: 其中:
List Length表明该链表一共有多少节点。
First Node Page Number和First Node Offset的组合就是指向链表头节点的指针。
Last Node Page Number和Last Node Offset的组合就是指向链表尾节点的指针。
整个List Base Node占用16个字节的存储空间。
所以使用List Base Node和List Node这两个结构组成的链表的示意图就是这样:
FIL_PAGE_UNDO_LOG页面
我们前面介绍表空间的时候说过,表空间其实是由许许多多的页面构成的,页面默认大小为16KB。这些页面有不同的类型,比如类型为 FIL_PAGE_INDEX 的页面用于存储聚簇索引以及二级索引,类型为FIL_PAGE_TYPE_FSP_HDR 的页面用于存储表空间头部信息的,还有其他各种类型的页面,其中有一种称之为 FIL_PAGE_UNDO_LOG 类型的页面是专门用来存储undo日志的,这种类型的页面的通用结构如下图所示(以默认的16KB大小为例):
“类型为FIL_PAGE_UNDO_LOG的页” 这种说法太绕口,以后我们就简称为Undo页面了。上图中的File Header和File Trailer是各种页面都有的通用结构,我们前面介绍过很多遍了,这里就不赘述了(忘记了的可以到讲述数据页结构或者表空间的章节中查看)。Undo Page Header是Undo页面所特有的,我们来看一下它的结构:
其中各个属性的意思如下:
TRX_UNDO_PAGE_TYPE:本页面准备存储什么种类的undo日志。
我们前面介绍了好几种类型的undo日志,它们可以被分为两个大类:
TRX_UNDO_INSERT(使用十进制1表示):类型为TRX_UNDO_INSERT_REC的undo日志属于此大类,一般由INSERT语句产生,
或者在UPDATE语句中有更新主键的情况也会产生此类型的undo日志。
TRX_UNDO_UPDATE(使用十进制2表示),除了类型为TRX_UNDO_INSERT_REC的undo日志,其他类型的undo日志都属于这个大类,
比如我们前面说的TRX_UNDO_DEL_MARK_REC、TRX_UNDO_UPD_EXIST_REC什么的,一般由DELETE、UPDATE语句产生的undo日志属于这个大类。
这个 TRX_UNDO_PAGE_TYPE 属性可选的值就是上面的两个,用来标记本页面用于存储哪个大类的undo日志,不同大类的undo日志不能混着存储,
比如一个Undo页面的TRX_UNDO_PAGE_TYPE属性值为TRX_UNDO_INSERT,那么这个页面就只能存储类型为TRX_UNDO_INSERT_REC的undo日志,
其他类型的undo日志就不能放到这个页面中了。
小贴士:之所以把undo日志分成两个大类,是因为类型为TRX_UNDO_INSERT_REC的undo日志在事务提交后可以直接删除掉,
而其他类型的undo日志还需要为所谓的 MVCC 服务,不能直接删除掉,对它们的处理需要区别对待。当然,
如果你看这段话迷迷糊糊的话,那就不需要再看一遍了,现在只需要知道undo日志分为2个大类就好了,更详细的东西我们后边会仔细介绍的。
TRX_UNDO_PAGE_START:表示在当前页面中是从什么位置开始存储undo日志的,或者说表示第一条undo日志在本页面中的起始偏移量。
TRX_UNDO_PAGE_FREE:与上面的TRX_UNDO_PAGE_START对应,表示当前页面中存储的最后一条undo日志结束时的偏移量,或者说从这个位置开始,可以继续写入新的undo日志。
TRX_UNDO_PAGE_NODE:代表一个List Node结构(链表的普通节点,我们上面刚说的 12字节的 List Node)。
假设现在向页面中写入了3条undo日志,那么TRX_UNDO_PAGE_START和TRX_UNDO_PAGE_FREE的示意图就是这样:
当然,在最初一条undo日志也没写入的情况下,TRX_UNDO_PAGE_START 和
TRX_UNDO_PAGE_FREE 的值是相同的。
Undo页面链表
单个事务中的Undo页面链表
因为一个事务可能包含多个语句,而且一个语句可能对若干条记录进行改动,而对每条记录进行改动前,都需要记录1条或2条的undo日志,所以在一个事务执行过程中可能产生很多undo日志,这些日志可能一个页面放不下,需要放到多个页面中,这些页面就通过我们上面介绍的 TRX_UNDO_PAGE_NODE 属性连成了链表:
在一个事务执行过程中,可能混着执行INSERT、DELETE、UPDATE语句,也就意味着会产生不同类型的undo日志。但是我们前面又强调过,同一个Undo页面要么只存储TRX_UNDO_INSERT大类的undo日志,要么只存储TRX_UNDO_UPDATE大类的undo日志,反正不能混着存,所以在一个事务执行过程中就可能需要2个Undo页面的链表,一个称之为insert undo链表,另一个称之为update undo链表;
另外,设计InnoDB的大佬规定对普通表和临时表的记录改动时产生的undo日志要分别记录(我们稍后阐释为什么这么做),所以在一个事务中最多有4个以Undo页面为节点组成的链表。当然,并不是在事务一开始就会为这个事务分配这4个链表,具体分配策略如下:
刚刚开启事务时,一个Undo页面链表也不分配。
当事务执行过程中向普通表中插入记录或者执行更新记录主键的操作之后,就会为其分配一个普通表的insert undo链表。
当事务执行过程中删除或者更新了普通表中的记录之后,就会为其分配一个普通表的update undo链表。
当事务执行过程中向临时表中插入记录或者执行更新记录主键的操作之后,就会为其分配一个临时表的insert undo链表。
当事务执行过程中删除或者更新了临时表中的记录之后,就会为其分配一个临时表的update undo链表。
总结一句就是:按需分配,什么时候需要什么时候再分配,不需要就不分配。
多个事务中的Undo页面链表
为了尽可能提高 undo 日志的写入效率,不同事务执行过程中产生的undo日志需要被写入到不同的Undo页面链表中。
比方说现在有事务id分别为1、2的两个事务,我们分别称之为trx 1和trx 2,假设在这两个事务执行过程中:
trx 1对普通表做了DELETE操作,对临时表做了INSERT和UPDATE操作。
InnoDB会为trx 1分配3个链表,分别是:
针对普通表的update undo链表
针对临时表的insert undo链表
针对临时表的update undo链表。
trx 2对普通表做了INSERT、UPDATE和DELETE操作,没有对临时表做改动。
InnoDB会为trx 2分配2个链表,分别是:
针对普通表的insert undo链表
针对普通表的update undo链表。
综上所述,在trx 1和trx 2执行过程中,InnoDB共需为这两个事务分配5个Undo页面链表,画个图就是这样:
Undo日志具体写入过程
段(Segment)的概念
简单讲,这个段是一个逻辑上的概念,本质上是由若干个零散页面和若干个完整的区组成的。比如一个B+树索引被划分成两个段,一个叶子节点段,一个非叶子节点段,这样叶子节点就可以被尽可能的存到一起,非叶子节点被尽可能的存到一起。每一个段对应一个 INODE Entry 结构,这个INODE Entry 结构描述了这个段的各种信息,比如段的ID,段内的各种链表基节点,零散页面的页号有哪些等信息(具体该结构中每个属性的意思大家可以到表空间那一章里再次重温一下)。我们前面也说过,为了定位一个 INODE Entry,设计InnoDB的大佬设计了一个 Segment Header 的结构:
整个Segment Header占用10个字节大小,各个属性的意思如下:
Space ID of the INODE Entry:INODE Entry结构所在的表空间ID。
Page Number of the INODE Entry:INODE Entry结构所在的页面页号。
Byte Offset of the INODE Ent:INODE Entry结构在该页面中的偏移量
知道了表空间ID、页号、页内偏移量,不就可以唯一定位一个INODE Entry的地址了么~
Undo Log Segment Header
设计InnoDB的大佬规定,每一个Undo页面链表都对应着一个段,称之为Undo Log Segment 。也就是说链表中的页面都是从这个段里边申请的 ,所以他们在Undo页面链表的第一个页面,也就是上面提到的 first undo page 中设计了一个称之为 Undo Log Segment Header 的部分,这个部分中包含了该链表对应的段的 segment header 信息以及其他的一些关于这个段的信息,所以Undo页面链表的第一个页面其实长这样:
可以看到这个Undo链表的第一个页面比普通页面多了个Undo Log Segment Header,我们来看一下它的结构:
其中各个属性的意思如下:
TRX_UNDO_STATE:本Undo页面链表处在什么状态。
一个Undo Log Segment可能处在的状态包括:
TRX_UNDO_ACTIVE:活跃状态,也就是一个活跃的事务正在往这个段里边写入undo日志。
TRX_UNDO_CACHED:被缓存的状态。处在该状态的Undo页面链表等待着之后被其他事务重用。
TRX_UNDO_TO_FREE:对于insert undo链表来说,如果在它对应的事务提交之后,该链表不能被重用,那么就会处于这种状态。
TRX_UNDO_TO_PURGE:对于update undo链表来说,如果在它对应的事务提交之后,该链表不能被重用,那么就会处于这种状态。
TRX_UNDO_PREPARED:包含处于PREPARE阶段的事务产生的undo日志。
小贴士:Undo页面链表什么时候会被重用,怎么重用我们之后会详细说的。事务的PREPARE阶段是在所谓的分布式事务中才出现的,本书中不会介绍更多关于分布式事务的事情,所以大家目前忽略这个状态就好了。
TRX_UNDO_LAST_LOG:本Undo页面链表中最后一个Undo Log Header的位置。
小贴士:关于什么是Undo Log Header,我们稍后马上介绍。
TRX_UNDO_FSEG_HEADER:本Undo页面链表对应的段的Segment Header信息(就是我们上一节介绍的那个10字节结构,通过这个信息可以找到该段对应的INODE Entry)。
TRX_UNDO_PAGE_LIST:Undo页面链表的基节点。
我们上面说 Undo 页面的 Undo Page Header 部分有一个12字节大小的 TRX_UNDO_PAGE_NODE 属性,这个属性代表一个List Node结构。
每一个Undo页面都包含 Undo Page Header 结构,这些页面就可以通过这个属性连成一个链表。
这个 TRX_UNDO_PAGE_LIST属性代表着这个链表的基节点,当然这个基节点只存在于Undo页面链表的第一个页面,也就是first undo page中。
Undo Log Header
一个事务在向Undo页面中写入undo日志时的方式是十分简单暴力的,就是直接往里怼,写完一条紧接着写另一条,各条undo日志之间是亲密无间的。写完一个Undo页面后,再从段里申请一个新页面,然后把这个页面插入到Undo页面链表中,继续往这个新申请的页面中写。设计InnoDB的大佬认为同一个事务向一个Undo页面链表中写入的undo日志算是一个组,比方说我们上面介绍的trx 1由于会分配3个Undo页面链表,也就会写入3个组的undo日志;trx 2由于会分配2个Undo页面链表,也就会写入2个组的undo日志。
这个Undo Log Header具体的结构如下:
TRX_UNDO_TRX_ID:生成本组undo日志的事务id。
TRX_UNDO_TRX_NO:事务提交后生成的一个需要序号,使用此序号来标记事务的提交顺序(先提交的此序号小,后提交的此序号大)。
TRX_UNDO_DEL_MARKS:标记本组undo日志中是否包含由于Delete mark操作产生的undo日志。
TRX_UNDO_LOG_START:表示本组undo日志中第一条undo日志的在页面中的偏移量。
TRX_UNDO_XID_EXISTS:本组undo日志是否包含XID信息。
小贴士:本书不会讲述更多关于XID是个什么东东,有兴趣的同学可以到搜索引擎或者文档中搜一搜。
TRX_UNDO_DICT_TRANS:标记本组undo日志是不是由DDL语句产生的。
TRX_UNDO_TABLE_ID:如果TRX_UNDO_DICT_TRANS为真,那么本属性表示DDL语句操作的表的table id。
TRX_UNDO_NEXT_LOG:下一组的undo日志在页面中开始的偏移量。
TRX_UNDO_PREV_LOG:上一组的undo日志在页面中开始的偏移量。
小贴士:一般来说一个Undo页面链表只存储一个事务执行过程中产生的一组undo日志,但是在某些情况下,
可能会在一个事务提交之后,之后开启的事务重复利用这个Undo页面链表,这样就会导致一个Undo页面中可能存放多组Undo日志,
TRX_UNDO_NEXT_LOG和TRX_UNDO_PREV_LOG就是用来标记下一组和上一组undo日志在页面中的偏移量的。
关于什么时候重用Undo页面链表,怎么重用这个链表我们稍后会详细说明的,
现在先理解TRX_UNDO_NEXT_LOG和TRX_UNDO_PREV_LOG这两个属性的意思就好了。
TRX_UNDO_HISTORY_NODE:一个12字节的List Node结构,代表一个称之为History链表的节点。
小贴士:关于History链表我们后边会格外详细的介绍,现在先不用管。
参考: 当一个事务提交时,它所占用的undo slot有两种命运之“该undo slot指向的Undo页面链表不符合被重用的条件”
如果对应的 Undo 页面链表是update undo链表,
则该 Undo 页面链表的 TRX_UNDO_STATE 属性会被设置为 TRX_UNDO_TO_PRUGE,
则会将该undo slot的值设置为FIL_NULL,然后将本次事务写入的一组undo日志放到所谓的 History 链表中
重用Undo页面
我们前面说为了能提高并发执行的多个事务写入undo日志的性能,设计InnoDB的大佬决定为每个事务单独分配相应的Undo页面链表(最多可能单独分配4个链表)。但是这样也造成了一些问题,比如其实大部分事务执行过程中可能只修改了一条或几条记录,针对某个Undo页面链表只产生了非常少的 undo 日志,这些undo日志可能只占用一丢丢存储空间,每开启一个事务就新创建一个Undo页面链表(虽然这个链表中只有一个页面)来存储这么一丢丢undo日志岂不是太浪费了么?的确是挺浪费,于是设计InnoDB的大佬本着勤俭节约的优良传统,决定在事务提交后在某些情况下重用该事务的Undo页面链表。一个Undo页面链表是否可以被重用的条件很简单:
- 该链表中只包含一个Undo页面。
- 该Undo页面已经使用的空间小于整个页面空间的3/4。
我们前面说过,Undo页面链表按照存储的undo日志所属的大类可以被分为insert undo链表和update undo链表两种,这两种链表在被重用时的策略也是不同的,我们分别看一下:
- insert undo链表
insert undo链表中只存储类型为 TRX_UNDO_INSERT_REC 的 undo 日志,这种类型的 undo 日志在事务提交之后就没用了,就可以被清除掉。所以在某个事务提交后,重用这个事务的insert undo链表(这个链表中只有一个页面)时,可以直接把之前事务写入的一组undo日志覆盖掉,从头开始写入新事务的一组undo日志,如下图所示:
- update undo链表 - 和 MVCC 有关
在一个事务提交后,它的update undo链表中的undo日志也不能立即删除掉(这些日志用于MVCC,我们后边会说的)。所以如果之后的事务想重用update undo链表时,就不能覆盖之前事务写入的undo日志。这样就相当于在同一个Undo页面中写入了多组的undo日志,效果看起来就是这样: