InnoDB中undo日志的组织及实现
Undo日志在InnoDB中起着重要的作用，保证着事务的原子性，解决崩溃恢复的问题，满足隔离性要求等。InnoDB中undo日志的结构是什么样的、这些undo日志是如何组织起来的、为满足事务原子性InnoDB中undo是如何实现的？针对这些问题，本文分两部分展开介绍：第一部分undo日志的结构和组织；第二部分Undo日志作用及实现。本文的侧重点是InnoDB中undo日志是如何组织及实现的，对主要点进行介绍，一些细节步过多展开。Undo日志存储在undo tablespace中为。了提升并发写undo日志能力，每个undo tablespace会划分128个rollback segment来进行管理，每个rollback segment包含1024个undo slot。写事务执行时要分配一个rollback segment，任何一类写操作（insert、update、temp insert、temp update）都要分配一个undo slot，该undo slot对应分配一个undo segment，维护着一个undo页面链表，该事务某类型的写操作的undo日志就写到这个undo页面链表中。有些事物写操作对应的undo日志很少，就会有针对undo页面链表的重用，即一个undo页面链表会包含多个事物的同类型undo日志。undo日志分为insert、update与delete这三类。下面围绕Undo日志格式、Undo页面结构以及undo tablespace组织展开进行说明：Undo日志格式分为insert操作、delete操作以及update操作对应的日志，读请求不更改记录，没有undo日志。INSERT操作对应的undo日志Insert操作对应的undo日志类型是TRX_UNDO_INSERT_REC的undo日志，记录这条记录对应的主键信息等，完整的结构如下图：DELETE操作对应的undo日志记录的删除操作分为两个阶段：阶段1: 仅仅将记录的deleted_flag标示位设置为1，其他的不做修改(实际会修改记录的trx_id，roll_pointer等隐藏列的信息)，这个阶段称为delete mark 。阶段2:当该删除语句所在的事务提交之后，undo purge线程来真正的把记录删除掉。就是把记录从正常记录链表移除，加入到垃圾连表中。然后对页面的一些信息作修改，如页面中的用户记录数量PAGEN_RECS、上次插入记录的位置PAGE_LAST_INSERT、垃圾链表头节点的指针PAGE_FREE、页面中可重用的字节数量PAGE_GARBAGE,以及页目录的一些信息等，这个阶段称为purge。阶段2执行完后，这条记录就算是真正地被删除了。这条己删除记录占用的存储空间可以重新利用了。在执行一条删除语句的过程中，在删除语句所在的事务提交前，只会经历阶段1，也就是delete mark阶段。而一旦事务提交，我们也就不需要再回滚越个事务了。所以在设计udo日志时，只需要考虑对删除操作在阶段1所做的影响进行回滚。 针对删除操作的阶段1，Innodb设计TRX_UNDO_DEL_MARK_REC类型的undo日志，在对一条记录进行delete mark操作前，需要把该记录的trx_id和roll——pointer的隐藏列旧值都记到对应的undo日志中的txid和olpointer属性中。可以通过undo日志的roll_pointer的属性找到上一次对该记录改动产生的undo日志，即结合roll_pointer属性将记录的undo日志历史修改串成一个链表。与类型为TRX_UNDO_INSERT_REC的undo日志不同，类型为TRX_UNDO_DEL_MARK_REC的udo日志还多了一个索引列各列信息的内容。也就是说，如果某个列被包含在某个索引中，那么它的相关信息就应该记录到这个索引列各列的信息部分。“相关信息”包括该列在记录中的位置（用pos表示）、该列占用的存储空间大小（用len表示)、该列实际值（用value表示）。所以，索引列各列信息存储的内容实质上就是的一个列表。这部分信息主要在事务提交后使用，用来对中间状态的记录进行真正的删除（即在阶段2，也就是puge阶段中使用）。具体日志结构如下：UPDATE操作对应的undo日志在执行UPDATE语句时，InnoDB对更新主键和不更新主键这两种情况有截然不同的处理：1. 不更新主键在不更新主键的情况下，又可以细分为被更新的列占用的存储空间不发生变化和发生变化两种情况：就地更新(in-place update) ：在更新记录时，对于被更新的每个列来说，如果更新后的列与更新前的列占用的存储空间一样大，那么可以进行就地更新，也就是直接在原记录的基础上修改对应列的值。每个列在更新前后占用的存储空间一样大，只要有任何一个被更新的列在更新前比更新后占用的存储空间大，或者在更新前比更新后占用的存储空间小，就不能进行就地更新。先删除旧记录，再插入新记录： 在不更新主键的情况下，如果有任何一个被更新的列在更新前和更新后占用的存储空间大小不一致，那么就需要先把这条旧记录从聚簇索引页面中别除，然后再根据更新后列的值创建一条新的记录并插入到页面中。这里的删除并不是delete mark操作，而是真正地除掉，也就是把这条记录从正常记录链表中移除并加入到垃圾链表中，并且修改页面中相应的统计信息（比如PAGE FREE、PAGE GARBAGE等信息)。不过，这里执行真正删除操作的线程并不是在DELETE语句中进行purge操作时使用的专门的线程，而是由用户线程同步执行真正的删除操作。在真正删除之后，紧接着就要根据各个列更新后的值来创建一条新记录，然后把这条新记录插入到页面中。如果新创建的记录占用的存储空间不超过旧记录占用的空间，那么可以直接重用加入到垃圾链表中的旧记录所占用的存储空间，否则需要在页面中新申请一块空间供新记录使用。如果本页面内已经没有可用的空间，就需要进行页面分裂操作，然后再插入新记录。针对UPDATE操作不更新主键的情况（包括上面说的就地更新和先删除旧记录再插入新记录)，InnoDB设计类型为TRX_UNDO_UPD_EXIST_REC的undo日志，这个undo日志的大部分属性与前面介绍过的TRX_UNDO_DEL_MARK_REC类型的undo日志是类似的，不过要注意下面几点： n_updated属性表示在本条UPDATE语句执行后将有几个列被更新，后边跟着的列表中的pos、old_len和old_value分别表示被更新列在记录中的位置、更新前该列占用的存储空间大小、更新前该列的真实值。 如果在UPDATE语句中更新的列包含索引列，那么也会添加“索引列各列信息”这个部分，否则不会添加这个部分。 具体结构如下图所示：2.更新主键针对UPDATE语句更新记录主键的情况，Innodb分了两步进行处理。 步骤1. 将旧的记录进行delete mark操作，也就是只标记删除，在事务提交后有purge线程进行真正的删除。 步骤2. 根据更新后各列的值创建一条新记录，并将其插入到主键索引中。 针对UPDATE培句更新记录主键值的这种情况，在对该记录进行delete mark操作时，会记录一条类型为TRX_UNDO_DEL_MARK_REC的undo日志：之后插入新记录时，会记录类型为TRX_UNDO_NSERT_REC的undo日志。就是说，每对一条记录的主键值进行改,都会记录2条undo日志。这些日志的格式都在前面已经介绍过，就不再赘述。增删改操作涉及二级索引只有主键索引的记录才有trx_id、roll_pointer这些属性，也就是有对应的undo日志链，二级索引的更改没有对应的trx_id、roll_pointer，也就是没有对应的undo日志链。但每当我们增删改一条二级索引记录时，都会影响这条二级索引记录所在页面的Page Header部分中一个名为PAGE_MAX_TRX_ID的属性，通过这个属性及通过二级索引回查主键，判断索引版本的可见性等。 如果更新了二级索引记录的键值，就要进行下面这两个操作：1. 对旧的二级索引记录执行delete mark操作（是delete mark操作，而不是彻底将这条二级索引记录删除，这主要是考虑到MVCC)。 2. 根据更新后的值创建一条新的二级索引记录，然后在二级索引对应的B+树中重新定位到它的位置并插进去。FIL_PAGE_UNDO_LOG类型的页面（简称undo页面）是专门用来存放undo日志的，undo页面的结构主要由File Header、Undo Page Header、Undo Log Segment Header（只有undo页面链表的first page有）、Undo Log Header以及真正的undo日志（具体见上面不同的undo日志格式），下面结合undo页面结构图，展开分析undo页面的不同Header结构Undo Page Header是Undo页面特有的，我们来看一下它的结构 TRX_UNDO_PAGE_TYPE: 本页面准备存储什么类型的undo日志，不同类型的undo日志不能混着存储.比如一个Undo页面的TRX_UNDO_PAGE_TYPE属性值为TRX_UNDO INSERT,那么这个页面就只能存储类型为TRX_UNDO_INSERT_REC的undo日志，其他类型的undo日志就不能放到这个页面中了：之所以把ndo日志分成2个大类，是因为类型为TRX_UNDO_INSERT_REC的undo日志在事务提交后可以直接删除掉，而共他类型的undo日志还需要为MVCC服务 TRX_UNDO_INSERT（使用十进制1表示)：类型为TRX_UNDO _INSERT_REC的undo日志属于这个大类，一般由INSERT语句产生：当UPDATE语句更新主健的情况时也会产生此类型的undo日志。我们把属于这个TRX_UNDO_INSERT大类的undo日志简称为insert undo日志. TRX_UNDO_UPDATE (使用十进制2表示)，除类型为TRX_UNDO_INSERT_REC外的undo日志都属于这个类型.比如前面说的TRX_UNDO_DEL_MARK_REC, TRX_UNDO_UPD_EXIST_REC等。一般由DELETE UPDATE语句产生的undo日志，我们把属于TRX_UNDO_UPDATE的undo日志简称为update undo日志。TRX_UNDO_PAGE_START: 表示在当前页面中从什么位置开始存储undo日志，或者说表示第一条undo日志在本页面中的起始偏移量。 TRX_UNDO_PAGE_FREE: 与上面的TRX_UNDO_PAGE_START对应，表示当前页面中存储的最后一条undo日志结束时的偏移量；或者说从这个位置开始，可以继续写入新的undo日志。 TRX_UNDO_PAGE_NODE: 代表一个链表节点结构Undo Log Segment Header的结构Undo页面链表的第一个页面比普通页面多了一个Undo Log Segment Header, TRX_UNDO_STATE: 本Undo页面链表处于什么状态。可能的状态有下面几种：TRX_UNDO_ACTIVE: 活跃状态，也就是一个活跃的事务正在向这个Undo页面链表中写入undo日志。   TRX_UNDO_CACHED: 被缓存的状态。处于该状态的Undo页面链表等待之后被其他事务重用。 TRX_UNDO_TO_FREE: 等待被释放的状态，对于insert undo链表来说，如果在它对应的事务提交之后，该链表不能被重用，那么就会处于这种状态。TRX_UNDO_TO_PURGE：等待被purge的状态。对于update undo链表来说，如果在它对应的事务提交之后，该链表不能被重用，那么就会处于这种状态。TRX_UNDO_PREPARED：处于此状态的Undo页面链表用于存储处于PREPARE阶段的事务产生的日志。 TRX_UNDO_LAST_LOG: 本Undo页面链表中最后一个Undo Log Header的位置。 TRX_UNDO_FSEG_HEADER: 本Undo页面链表对应的段的Segment Header信息 TRX_UNDO_PAGE_LIST: Undo页面链表的基节点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信息 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页面中可能存放多组ndo日志.因为一个事务可能包含多个语句，而且一个语句可能会对若干条记录进行改动，而对每条记录进行改动前（再强调一下，这里指的是聚簇素引记录），都需要记录1条或2条undo日志。所以在一个事务执行过程中可能产生很多uo日志。这些日志可能在一个页面中放不下，需要放到多个页面中。这些页面就通过前文介绍的TRX_UNDO_PAGE_NODE属性连成了链表，一个事务中最多有4个以Undo页面为节点组成的链表，并不是在事务一开始就为它分配这4个链表，具体分配策略如下：刚开启事务时，一个Undo页面链表也不分配： 当事务执行过程中向普通表插入记录或者执行更新记录主键的操作之后，就会为其分配一个普通表的insert undo链表当事务执行过程中刷除或者更新了普通表中的记录之后，就会为其分配一个普通表的update undo链表当事务执行过程中向临时表插入记录或者执行更新记录主键的操作之后，就会为其分配一个临时表的insert undo链表当事务执行过程中删除或者更新了临时表中的记录之后，就会为其分配一个临时表的update undo链表。 总之就是：按需分配，啥时候需要啥时候分配，不需要就不分配。为提高并非执行多个事务写undo日志的性能，InnoDB为每个事务单独分配相应的Undo页面链表（最多可能分配4个链表）。但大部分事务执行的过程中至少修改一条或者几条记录，产生的undo日志非常少，占用很少的空间，一个页面链表（虽然链表只有一个页面）只存这几条undo日志，也造成空间浪费。 为提高空间利用，在事务提交后某些情况下Undo页面链表可以被重用，需要满足两个条件：1.该链表只有一个Undo页面；2. 该Undo页面以及使用空间小雨整个页面空间的3/4. 如果没有undo页面链表重用，每个undo页面链表（一个Undo log segment）对应一组undo日志，一个Undo Log Header。Undo页面重用后，一个undo页面链表（一个Undo log segment）对应多组undo日志，多条Undo Log Header。Innodb中至少存在两个undo tablespace，每个Undo tablespace特定的页存储着128个（可修改）Rollback Segment Header页面地址，每个Rollback Segment Header就相当于一个回滚段。在Rollback Segment Header页面中，又包含1024个undo slot。写事务在执行时，会为每一类写操作分配一个undo slot，每个undo slot都对应一个Undo页面链表，具体结构如下图所示：在事务提交后，update类型undo日志会按照trx no从小到大插入到rseg的history list上，方便后面使用rollback segment小顶堆，有序的purge这些undo日志，undo history list结构如下图所示： Undo日志保证了事务的原子性、解决了崩溃恢复的问题，满足隔离性要求。Innodb针对undo log的实现涉及的地方比较多，我们这里围绕着启动时undo相关操作、undo tablespace如果修改、事务写操作、MVCC读请求、事务回滚、Undo Purge &amp; Truncate展开，包含了undo的整个生命周期，主要介绍关键流程，不对细节过多展开（个别地方可能分析有偏差）。下文中代码实现介绍基于mysql 8.0（commit为ea7087d885006918ad54458e7aad215b1650312c），代码介绍中的缩进表示调用下一级函数。启动时undo相关操作包括undo tablespace初始化，相关内存对象初始化，crash前的事务恢复以及回滚，实现见如下：undo tablespace的创建修改分两种场景：1.实例创建启动时创建对应的undotablespace（上面已经介绍）；2. 实例运行中进行创建及修改，代码实现如下：事务写操作对应的undo主要分为三个点： 1. 事务启动时为写事务分配undo rseg，基于round-robin的方式从undo tablespace中分配 2. 事务执行中为写操作分配undo log并将对应类型的undo内容写入日志 3. 事务commit时为undo log分配trx no，将rseg加入到purge queue，并将update undo加入rseg history list读请求根据隔离性级别不同实现也不同，本篇主要讲undo，所以这里只围绕非锁定一致性读稍作展开，即使用mvcc的读请求。主要是基于read view和undo不同版本的trx id判断可见性，来构建相应版本的数据返回，见下面代码：undo的回滚操作分为两种场景：一种是在事务中主动执行rollback回滚；另外一种是在实例crash recovery时对事务的回滚.回滚主要分为三个步骤：1. 触发及构建需要回滚的trx的信息保存到roll_node_t； 2. trx rollback query graph基于roll_node_t构建undo_node_t；3. row undo query graph使用undo_node_t对btree上的记录进行回撤操作。代码如下：Undo purge的流程是围绕purge queue（基于tx no的小顶堆）展开的： 首先：在transaction commit阶段给update操作对应的undo分配tx no，将update操作对应的rseg加入到purge queue（见函数trx_serialisation_number_get），接着将对应的update undo log加入到rseg history list开头（见函数trx_purge_add_update_undo_to_history） 然后：后台trx purge 线程使用purge queue将undo log按照trx no从小到大扫出来一批，分配到不同的row purge线程 最后：row purge 线程基于undo log的不同类型删除（TRX_UNDO_DEL_MARK_REC），更新（TRX_UNDO_UPD_EXIST_REC）分别调用不同的函数将undo log对应记录的二级索引、主键从btree上真正的删除掉，并加入到garbage listUndo truncate分为两个步骤，第一步是将undo log从各个undo tablespace的rseg undo history摘除掉；第二步是对undo tablespace文件truncate（先删除，再创建），具体代码实现如下：InnoDB中undo日志设计及实现相对清晰，但涉及的地方比较多，有些地方设计的比较巧妙，需要仔细的研究，整体对undo日志这块做下梳理。