关于数据库:庖丁解InnoDB之UNDO-LOG

简介： Undo Log是InnoDB非常重要的组成部分，它的作用横贯InnoDB中两个最次要的局部，并发管制（Concurrency Control）和故障复原（Crash Recovery），InnoDB中Undo Log的实现亦日志亦数据。本文将从其作用、设计思路、记录内容、组织构造，以及各种性能实现等方面，整体介绍InnoDB中的Undo Log。

作者 | 瀚之
起源 | 阿里技术公众号

Undo Log是InnoDB非常重要的组成部分，它的作用横贯InnoDB中两个最次要的局部，并发管制（Concurrency Control）和故障复原（Crash Recovery），InnoDB中Undo Log的实现亦日志亦数据。本文将从其作用、设计思路、记录内容、组织构造，以及各种性能实现等方面，整体介绍InnoDB中的Undo Log，文章会深刻肯定的代码实现，但在细节上还是心愿用形象的实现思路代替具体的代码。本文基于MySQL 8.0，但在大多数的设计思路上MySQL的各个版本都是统一的。思考到篇幅无限，以及防止过多信息的烦扰，从而可能聚焦Undo Log自身的内容，本文中一笔带过或无意省略了一些内容，包含索引、事务零碎、长期表、XA事务、Virtual Column、内部记录、Blob等。

一 Undo Log的作用

数据库故障复原机制的前世今生中提到过，Undo Log用来记录每次批改之前的历史值，配合Redo Log用于故障复原。这也就是InnoDB中Undo Log的第一个作用：

1 事务回滚

在设计数据库时，咱们假如数据库可能在任何时刻，因为如硬件故障，软件Bug，运维操作等起因忽然解体。这个时候尚未实现提交的事务可能曾经有局部数据写入了磁盘，如果不加解决，会违反数据库对Atomic的保障，也就是任何事务的批改要么全副提交，要么全副勾销。针对这个问题，直观的想法是等到事务真正提交时，能力容许这个事务的任何批改落盘，也就是No-Steal策略。不言而喻，这种做法一方面造成很大的内存空间压力，另一方面提交时的大量随机IO会极大的影响性能。因而，数据库实现中通常会在失常事务进行中，就一直的间断写入Undo Log，来记录本次批改之前的历史值。当Crash真正产生时，能够在Recovery过程中通过回放Undo Log将未提交事务的批改抹掉。InnoDB采纳的就是这种形式。

既然曾经有了在Crash Recovery时反对事务回滚的Undo Log，天然地，在失常运行过程中，死锁解决或用户申请的事务回滚也能够利用这部分数据来实现。

2 MVCC（Multi-Versioin Concurrency Control）

浅析数据库并发管制机制中提到过，为了防止只读事务与写事务之间的抵触，防止写操作期待读操作，简直所有的支流数据库都采纳了多版本并发管制（MVCC）的形式，也就是为每条记录保留多份历史数据供读事务拜访，新的写入只须要增加新的版本即可，无需期待。InnoDB在这里复用了Undo Log中曾经记录的历史版本数据来满足MVCC的需要。

二 什么样的Undo Log

庖丁解InnoDB之REDO LOG中讲过的基于Page的Redo Log能够更好的反对并发的Redo利用，从而缩短DB的Crash Recovery工夫。而对于Undo Log来说，InnoDB用Undo Log来实现MVCC，DB运行过程中是容许有历史版本的数据存在的。因而，Crash Recovery时利用Undo Log的事务回滚齐全能够在后盾，像失常运行的事务一样异步回滚，从而让数据库先复原服务。因而，Undo Log的设计思路不同于Redo Log，Undo Log须要的是事务之间的并发，以及不便的多版本数据保护，其重放逻辑不心愿因DB的物理存储变动而变动。因而，InnoDB中的Undo Log采纳了基于事务的Logical Logging的形式。

同时，更多的责任意味着更简单的治理逻辑，InnoDB中其实是把Undo当做一种数据来保护和应用的，也就是说，Undo Log日志自身也像其余的数据库数据一样，会写本人对应的Redo Log，通过Redo Log来保障本人的原子性。因而，更适合的称说应该是Undo Data。

三 Undo Record中的内容

每当InnoDB中须要批改某个Record时，都会将其历史版本写入一个Undo Log中，对应的Undo Record是Update类型。当插入新的Record时，还没有一个历史版本，但为了不便事务回滚时做逆向（Delete）操作，这里还是会写入一个Insert类型的Undo Record。

1 Insert类型的Undo Record

这种Undo Record在代码中对应的是TRX_UNDO_INSERT_REC类型。不同于Update类型的Undo Record，Insert Undo Record仅仅是为了可能的事务回滚筹备的，并不在MVCC性能中承当作用。因而只须要记录对应Record的Key，供回滚时查找Record地位即可。

其中Undo Number是Undo的一个递增编号，Table ID用来示意是哪张表的批改。上面一组Key Fields的长度不定，因为对应表的主键可能由多个field组成，这里须要记录Record残缺的主键信息，回滚的时候能够通过这个信息在索引中定位到对应的Record。除此之外，在Undo Record的头尾还各留了两个字节用户记录其前序和后继Undo Record的地位。

2 Update类型的Undo Record

因为MVCC须要保留Record的多个历史版本，当某个Record的历史版本还在被应用时，这个Record是不能被真正的删除的。因而，当须要删除时，其实只是批改对应Record的Delete Mark标记。对应的，如果这时这个Record又从新插入，其实也只是批改一下Delete Mark标记，也就是将这两种状况的delete和insert转变成了update操作。再加上惯例的Record批改，因而这里的Update Undo Record会对应三种Type：TRX_UNDO_UPD_EXIST_REC、TRX_UNDO_DEL_MARK_REC和TRX_UNDO_UPD_DEL_REC。他们的存储内容也相似：

除了跟Insert Undo Record雷同的头尾信息，以及主键Key Fileds之外，Update Undo Record减少了：

• Transaction Id记录了产生这个历史版本事务Id，用作后续MVCC中的版本可见性判断
• Rollptr指向的是该记录的上一个版本的地位，包含space number，page number和page内的offset。沿着Rollptr能够找到一个Record的所有历史版本。
• Update Fields中记录的就是以后这个Record版本绝对于其之后的一次批改的Delta信息，包含所有被批改的Field的编号，长度和历史值。

四 Undo Record的组织形式

下面介绍了一个Undo Record中的寄存的内容，每一次的批改都会产生至多一个Undo Record，那么大量Undo Record如何组织起来，来反对高效的拜访和治理呢，这一大节咱们将从几个层面来进行介绍：首先是在不思考物理存储的状况下的逻辑组织形式；之后，物理组织形式介绍如何将其存储到到理论16KB物理块中；而后文件组织形式介绍整体的文件构造；最初再介绍其在内存中的组织形式。

1 逻辑组织形式 - Undo Log

每个事务其实会批改一组的Record，对应的也就会产生一组Undo Record，这些Undo Record收尾相连就组成了这个事务的Undo Log。除了一个个的Undo Record之外，还在结尾减少了一个Undo Log Header来记录一些必要的管制信息，因而，一个Undo Log的构造如下所示：

Undo Log Header中记录了产生这个Undo Log的事务的Trx ID；Trx No是事务的提交程序，也会用这个来判断是否能Purge，这个在前面会具体介绍；Delete Mark表明该Undo Log中有没有TRX_UNDO_DEL_MARK_REC类型的Undo Record，防止Purge时不必要的扫描；Log Start Offset中记录Undo Log Header的完结地位，不便之后Header中减少内容时的兼容；之后是一些Flag信息；Next Undo Log及Prev Undo Log标记前后两个Undo Log，这个会在接下来介绍；最初通过History List Node将本人挂载到为Purge筹备的History List中。

索引中的同一个Record被不同事务批改，会产生不同的历史版本，这些历史版本又通过Rollptr穿成一个链表，供MVCC应用。如下图所示：

示例中有三个事务操作了表t上，主键id是1的记录，首先事务I插入了这条记录并且设置filed a的值是A，之后事务J和事务K别离将这条id为1的记录中的filed a的值批改为了B和C。I，J，K三个事务别离有本人的逻辑上间断的三条Undo Log，每条Undo Log有本人的Undo Log Header。从索引中的这条Record沿着Rollptr能够顺次找到这三个事务Undo Log中对于这条记录的历史版本。同时能够看出，Insert类型Undo Record中只记录了对应的主键值：id=1，而Update类型的Undo Record中还记录了对应的历史版本的生成事务Trx_id，以及被批改的field a的历史值。

2 物理组织格局 - Undo Segment

下面形容了一个Undo Log的构造，一个事务会产生多大的Undo Log自身是不可控的，而最终写入磁盘却是依照固定的块大小为单位的，InnoDB中默认是16KB，那么如何用固定的块大小承载不定长的Undo Log，以实现高效的空间调配、复用，防止空间节约。InnoDB的基本思路是让多个较小的Undo Log紧凑存在一个Undo Page中，而对较大的Undo Log则随着一直的写入，按需分配足够多的Undo Page扩散承载。上面咱们就看看这部分的物理存储形式：

如上所示，是一个Undo Segment的示意图，每个写事务开始写操作之前都须要持有一个Undo Segment，一个Undo Segment中的所有磁盘空间的调配和开释，也就是16KB Page的申请和开释，都是由一个FSP的Segment治理的，这个跟索引中的Leaf Node Segment和Non-Leaf Node Segment的治理形式是统一的，这部分之后会有独自的文章来进行介绍。

Undo Segment会持有至多一个Undo Page，每个Undo Page会在结尾38字节到56字节记录Undo Page Header，其中记录Undo Page的类型、最初一条Undo Record的地位，以后Page还闲暇局部的结尾，也就是下一条Undo Record要写入的地位。Undo Segment中的第一个Undo Page还会在56字节到86字节记录Undo Segment Header，这个就是这个Undo Segment中磁盘空间治理的Handle；其中记录的是这个Undo Segment的状态，比方TRX_UNDO_CACHED、TRX_UNDO_TO_PURGE等；这个Undo Segment中最初一条Undo Record的地位；这个FSP Segment的Header，以及以后调配进去的所有Undo Page的链表。

Undo Page残余的空间都是用来寄存Undo Log的，对于像上图Undo Log 1，Undo Log 2这种较短的Undo Log，为了防止Page内的空间节约，InnoDB会复用Undo Page来寄存多个Undo Log，而对于像Undo Log 3这种比拟长的Undo Log可能会调配多个Undo Page来寄存。须要留神的是Undo Page的复用只会产生在第一个Page。

3 文件组织形式 - Undo Tablespace

每一时刻一个Undo Segment都是被一个事务独占的。每个写事务都会持有至多一个Undo Segment，当有大量写事务并发运行时，就须要存在多个Undo Segment。InnoDB中的Undo 文件中筹备了大量的Undo Segment的槽位，依照1024一组划分为Rollback Segment。每个Undo Tablespace最多会蕴含128个Rollback Segment，Undo Tablespace文件中的第三个Page会固定作为这128个Rollback Segment的目录，也就是Rollback Segment Arrary Header，其中最多会有128个指针指向各个Rollback Segment Header所在的Page。Rollback Segment Header是按需分配的，其中蕴含1024个Slot，每个Slot占四个字节，指向一个Undo Segment的First Page。除此之前还会记录该Rollback Segment中已提交事务的History List，后续的Purge过程会程序从这里开始回收工作。

能够看出Rollback Segment的个数会间接影响InnoDB反对的最大事务并发数。MySQL 8.0因为反对了最多127个独立的Undo Tablespace，一方面防止了ibdata1的收缩，不便undo空间回收，另一方面也大大增加了最大的Rollback Segment的个数，减少了可反对的最大并发写事务数。如下图所示：

4 内存组织构造

下面介绍的都是Undo数据在磁盘上的组织构造，除此之外，在内存中也会保护对应的数据结构来治理Undo Log，如下图所示：

对应每个磁盘Undo Tablespace会有一个undo::Tablespace的内存构造，其中最次要的就是一组trx_rseg_t的汇合，trx_rseg_t对应的就是下面介绍过的一个Rollback Segment Header，除了一些根本的元信息之外，trx_rseg_t中保护了四个trx_undo_t的链表，Update List中是正在被应用的用于写入Update类型Undo的Undo Segment；Update Cache List中是闲暇空间比拟多，能够被后续事务复用的Update类型Undo Segment;对应的，Insert List和Insert Cache List别离是正在应用中的Insert类型Undo Segment，和空间空间较多，能够被后续复用的Insert类型Undo Segment。因而trx_undo_t对应的就是下面介绍过的Undo Segment。接下来，咱们就从Undo的写入、Undo用于Rollback、MVCC、Crash Recovery以及如何清理Undo等方面来介绍InnoDB中Undo的角色和性能。

五 Undo的写入

当写事务开始时，会先通过trx_assign_rseg_durable调配一个Rollback Segment，该事务的内存构造trx_t也会通过rsegs指针指向对应的trx_rseg_t内存构造，这里的调配策略很简略，就是顺次尝试下一个Active的Rollback Segment。之后当第一次真正产生批改须要写Undo Record的时，会调用trx_undo_assign_undo来取得一个Undo Segment。这里会优先复用trx_rseg_t上Cached List中的trx_undo_t，也就是曾经调配进去但没有被正在应用的Undo Segment，如果没有才调用trx_undo_create创立新的Undo Segment，trx_undo_create中会轮询抉择以后Rollback Segment中可用的Slot，也是就值FIL_NUL的Slot，申请新的Undo Page，初始化Undo Page Header，Undo Segment Header等信息，创立新的trx_undo_t内存构造并挂到trx_rseg_t的对应List中。

取得了可用的Undo Segment之后，该事务会在适合的地位初始化本人的Undo Log Header，之后，其所有批改产生的Undo Record都会程序的通过trx_undo_report_row_operation程序的写入以后的Undo Log，其中会依据是insert还是update类型，别离调用trx_undo_page_report_insert或者trx_undo_page_report_modify。本文开始曾经介绍过了具体的Undo Record内容。简略的讲，insert类型会记录插入Record的主键，update类型除了记录主键以外还会有一个update fileds记录这个历史值跟索引值的diff。之后指向以后Undo Record地位的Rollptr会返回写入索引的Record上。

当一个Page写满后，会调用trx_undo_add_page来在以后的Undo Segment上增加新的Page，新Page写入Undo Page Header之后持续供事务写入Undo Record，为了不便保护，这里有一个限度就是单条Undo Record不跨page，如果以后Page放不下，会将整个Undo Record写入下一个Page。

当事务完结（commit或者rollback）之后，如果只占用了一个Undo Page，且以后Undo Page应用空间小于page的3/4，这个Undo Segment会保留并退出到对应的insert/update cached list中。否则，insert类型的Undo Segment会间接回收，而update类型的Undo Segment会期待后盾的Purge做完后回收。依据不同的状况，Undo Segment Header中的State会被从TRX_UNDO_ACTIVE改成TRX_UNDO_TO_FREE，TRX_UNDO_TO_PURGE或TRX_UNDO_CACHED，这个批改其实就是InnoDB的事务完结的标记，无论是Rollback还是Commit，在这个批改对应的Redo落盘之后，就能够返回用户后果，并且Crash Recovery之后也不会再做回滚解决。

六 Undo for Rollback

InnoDB中的事务可能会由用户被动触发Rollback；也可能因为遇到死锁异样Rollback；或者产生Crash，重启后对未提交的事务回滚。在Undo层面来看，这些回滚的操作是统一的，根本的过程就是从该事务的Undo Log中，从后向前顺次读取Undo Record，并依据其中内容做逆向操作，复原索引记录。

回滚的入口是函数row_undo，其中会先调用trx_roll_pop_top_rec_of_trx获取并删除该事务的最初一条Undo Record。如下图例子中的Undo Log包含三条Undo Records，其中Record 1在Undo Page 1中，Record 2，3在Undo Page 2中，先通过从Undo Segment Header中记录的Page List找到以后事务的最初一个Undo Page的Header，并依据Undo Page 2的Header上记录的Free Space Offset定位最初一条Undo Record完结的地位，当然理论运行时，这两个值是缓存在trx_undo_t的top_page_no和top_offset中的。利用Prev Record Offset能够找到Undo Record 3，做完对应的回滚操作之后，再通过前序指针Prev Record Offset找到前一个Undo Record，顺次进行解决。解决完以后Page中的所有Undo Records后，再沿着Undo Page Header中的List找到前一个Undo Page，反复后面的过程，实现一个事务所有Page上的所有Undo Records的回滚。

拿到一个Undo Record之后，天然地，就是对其中内容的解析，这里会调用row_undo_ins_parse_undo_rec，从Undo Record中获取批改行的table，解析出其中记录的主键信息，如果是update类型，还会拿到一个update vector记录其绝对于更新的一个版本的变动。

TRX_UNDO_INSERT_REC类型的Undo回滚在row_undo_ins中进行，insert的逆向操作当然就是delete，依据从Undo Record中解析进去的主键，用row_undo_search_clust_to_pcur定位到对应的ROW， 别离调用row_undo_ins_remove_sec_rec和row_undo_ins_remove_clust_rec在二级索引和主索引上将以后行删除。

update类型的undo包含TRX_UNDO_UPD_EXIST_REC，TRX_UNDO_DEL_MARK_REC和TRX_UNDO_UPD_DEL_REC三种状况，他们的Undo回滚都是在row_undo_mod中进行，首先会调用row_undo_mod_del_unmark_sec_and_undo_update，其中依据从Undo Record中解析出的update vector来回退这次操作在所有二级索引上的影响，可能包含从新插入被删除的二级索引记录、去除其中的Delete Mark标记，或者用update vector中的diff信息将二级索引记录批改之前的值。之后调用row_undo_mod_clust同样利用update vector中记录的diff信息将主索引记录批改回之前的值。

实现回滚的Undo Log局部，会调用trx_roll_try_truncate进行回收，对不再应用的page调用trx_undo_free_last_page将磁盘空间交还给Undo Segment，这个是写入过程中trx_undo_add_page的逆操作。

七 Undo for MVCC

多版本的目标是为了防止写事务和读事务的相互期待，那么每个读事务都须要在不对Record加Lock的状况下， 找到对应的应该看到的历史版本。所谓历史版本就是假如在该只读事务开始的时候对整个DB打一个快照，之后该事务的所有读申请都从这个快照上获取。当然实现上不能真正去为每个事务打一个快照，这个工夫空间都太高了。InnoDB的做法，是在读事务第一次读取的时候获取一份ReadView，并始终持有，其中记录所有以后沉闷的写事务ID，因为写事务的ID是自增调配的，通过这个ReadView咱们能够晓得在这一瞬间，哪些事务曾经提交哪些还在运行，依据Read Committed的要求，未提交的事务的批改就是不应该被看见的，对应地，曾经提交的事务的批改应该被看到。

作为存储历史版本的Undo Record，其中记录的trx_id就是做这个可见性判断的，对应的主索引的Record上也有这个值。当一个读事务拿着本人的ReadView拜访某个表索引上的记录时，会通过比拟Record上的trx_id确定是否是可见的版本，如果不可见就沿着Record或Undo Record中记录的rollptr一路找更老的历史版本。如下图所示，事务R开始须要查问表t上的id为1的记录，R开始时事务I曾经提交，事务J还在运行，事务K还没开始，这些信息都被记录在了事务R的ReadView中。事务R从索引中找到对应的这条Record[1, C]，对应的trx_id是K，不可见。沿着Rollptr找到Undo中的前一版本[1, B]，对应的trx_id是J，不可见。持续沿着Rollptr找到[1, A]，trx_id是I可见，返回后果。

后面提到过，作为Logical Log，Undo中记录的其实是前后两个版本的diff信息，而读操作最终是要取得残缺的Record内容的，也就是说这个沿着rollptr指针一路查找的过程中须要用Undo Record中的diff内容顺次结构出对应的历史版本，这个过程在函数row_search_mvcc中，其中trx_undo_prev_version_build会依据以后的rollptr找到对应的Undo Record地位，这里如果是rollptr指向的是insert类型，或者找到了曾经Purge了的地位，阐明到头了，会间接返回失败。否则，就会解析对应的Undo Record，复原出trx_id、指向下一条Undo Record的rollptr、主键信息，diff信息update vector等信息。之后通过row_upd_rec_in_place，用update vector批改以后持有的Record拷贝中的信息，取得Record的这个历史版本。之后调用本人ReadView的changes_visible判断可见性，如果可见则返回用户。实现这个历史版本的读取。

八 Undo for Crash Recovery

Crash Recovery时，须要利用Undo中的信息将未提交的事务的所有影响回滚，以保障数据库的Failure Atomic。后面提到过，InnoDB中的Undo其实是像数据一样解决的，也从下面的组织构造中能够看进去，Undo自身有着比Redo Log简单得多、按事务调配而不是程序写入的组织构造，其自身的Durability像InnoDB中其余的数据一样，须要靠Redo来保障，像庖丁解InnoDB之REDO LOG中介绍的那样。除了通用的一些MLOG_2BYTES、MLOG_4BYTES类型之外，Undo自身也有本人对应的Redo Log类型：MLOG_UNDO_INIT类型在Undo Page舒服化的时候记录初始化；在调配Undo Log的时候，须要重用Undo Log Header或须要创立新的Undo Log Header的时候，会别离记录MLOG_UNDO_HDR_REUSE和MLOG_UNDO_HDR_CREATE类型的Redo Record；MLOG_UNDO_INSERT是最常见的，在Undo Log里写入新的Undo Record都对应的写这个日志记录写入Undo中的所有内容；最初，MLOG_UNDO_ERASE_END 对应Undo Log跨Undo Page时抹除最初一个不残缺的Undo Record的操作。

如数据库故障复原机制的前世今生中讲过的ARIES过程，Crash Recovery的过程中会先重放所有的Redo Log，整个Undo的磁盘组织构造，也会作为一种数据类型也会通过下面讲到的这些Redo类型的重放复原进去。之后在trx_sys_init_at_db_start中会扫描Undo的磁盘构造，遍历所有的Rollback Segment和其中所有的Undo Segment，通过读取Undo Segment Header中的State，能够晓得在Crash前，最初持有这个Undo Segment的事务状态。如果是TRX_UNDO_ACTIVE，阐明过后事务须要回滚，否则阐明事务曾经完结，能够持续清理Undo Segment的逻辑。之后，就能够复原出Undo Log的内存组织模式，包含沉闷事务的内存构造trx_t，Rollback Segment的内存构造trx_rseg_t，以及其中的trx_undo_t的四个链表。

Crash Recovery实现之前，会启动在srv_dict_recover_on_restart中启动异步回滚线程trx_recovery_rollback_thread，其中对Crash前还沉闷的事务，通过trx_rollback_active进行回滚，这个过程跟下面提到的Undo for Rollback是统一的。

九 Undo的清理

咱们曾经晓得，InnoDB在Undo Log中保留了多份历史版本来实现MVCC，当某个历史版本曾经确认不会被任何现有的和将来的事务看到的时候，就应该被清理掉。因而就须要有方法判断哪些Undo Log不会再被看到。InnoDB中每个写事务完结时都会拿一个递增的编号trx_no作为事务的提交序号，而每个读事务会在本人的ReadView中记录本人开始的时候看到的最大的trx_no为m_low_limit_no。那么，如果一个事务的trx_no小于以后所有沉闷的读事务Readview中的这个m_low_limit_no，阐明这个事务在所有的读开始之前曾经提交了，其批改的新版本是可见的， 因而不再须要通过undo构建之前的版本，这个事务的Undo Log也就能够被清理了。如下图所所以，因为ReadView List中最老的ReadView在获取时，Transaction J就曾经Commit，因而所有的读事务都肯定能被Index中的版本或者第一个Undo历史版本满足，不须要更老的Undo，因而整个Transaction J的Undo Log都能够清理了。

Undo的清理工作是由专门的后盾线程srv_purge_coordinator_thread进行扫描和散发， 并由多个srv_worker_thread真正清理的。coordinator会首先在函数trx_purge_attach_undo_recs中扫描innodb_purge_batch_size配置个Undo Records，作为一轮清理的工作分发给worker。

1 扫描一批要清理Undo Records

事务完结的时候，对于须要Purge的Update类型的Undo Log，会依照事务提交的程序trx_no，挂载到Rollback Segment Header的History List上。Undo Log回收的基本思路，就是依照trx_no从小到大，顺次遍历所有Undo Log进行清理操作。后面介绍了，InnoDB中有多个Rollback Segment，那么就会有多个History List，每个History List内部事务有序，但还须要从多个History List上找一个trx_no全局有序的序列，如下图所示：

图中的事务编号是依照InnoDB这里引入了一个堆构造purge_queue，用来顺次从所有History List中找到下一个领有最小trx_no的事务。purge_queue中记录了所有期待Purge的Rollback Segment和其History中trx_no最小的事务，trx_purge_choose_next_log顺次从purge_queue中pop出领有全局最小trx_no的Undo Log。调用trx_purge_get_next_rec遍历对应的Undo Log，解决每一条Undo Record。之后持续调用trx_purge_rseg_get_next_history_log从purge_queue中获取下一条trx_no最小的Undo Log，并且将以后Rollback Segment上的下一条Undo Log持续push进purge_queue，期待后续的程序解决。对应上图的处理过程和对应的函数调用，如下图所示：

其中，trx_purge_get_next_rec会从上到下遍历一个Undo Log中的所有Undo Record，这个跟后面讲过的Rollback时候从下到上的遍历方向是相同的，还是以同样的场景为例，要Purge的Undo Log横跨两个Undo Page，Undo Record 1在Page 1中，而Undo Record 2，3在Page 2中。如下图所示，首先会从以后的Undo Log Header中找到第一个Undo Record的地位Log Start Offset，解决完Undo Record1之后沿着Next Record Offset去找下一个Undo Record，当找到Page开端时，要通过Page List Node找下一个Page，找到Page内的第一个Undo Record，反复下面的过程直到找出所有的Undo Record。

对每个要Purge的Undo Record，在真正删除它自身之前，可能还须要解决一些索引上的信息，这是因为失常运行过程中，当须要删除某个Record时，为了保障其之前的历史版本还能够通过Rollptr找到，Record是没有真正删除的，只是打了Delete Mark的标记，并作为一种非凡的Update操作记录了Undo Record。那么在对应的TRX_UNDO_DEL_MARK_REC类型的Undo Record被清理之前，须要先从索引上真正地删除这个Delete Mark的记录。因而Undo Record的清理工作会分为两个过程：

• TRX_UNDO_DEL_MARK_REC类型Undo Record对应的Record的真正删除，称为Undo Purge；
• 以及Undo Record自身从旧到新的删除，称为Undo Truncate。

除此之外，当配置的独立Undo Tablespace大于两个的时候，InnoDB反对通过重建来放大超过配置大小的Undo Tablespace：

Undo Tablespace的重建放大，称为Undo Tablespace Truncate

2 Undo Purge

这一步次要针对的是TRX_UNDO_DEL_MARK_REC类型的Undo Record，用来真正的删除索引上被标记为Delete Mark的Record。worker线程会在row_purge函数中，循环解决coordinator调配来的每一个Undo Records，先通过row_purge_parse_undo_rec，顺次从Undo Record中解析出type、table_id、rollptr、对应记录的主键信息以及update vector。之后，针对TRX_UNDO_DEL_MARK_REC类型，调用row_purge_remove_sec_if_poss将须要删除的记录从所有的二级索引上删除，调用row_purge_remove_clust_if_poss从主索引上删除。另外，TRX_UNDO_UPD_EXIST_REC类型的Undo尽管不波及主索引的删除，但可能须要做二级索引的删除，也是在这里解决的。

3 Undo Truncate

coordinator线程会期待所有的worker实现一批Undo Records的Purge工作，之后尝试清理不再须要的Undo Log，trx_purge_truncate函数中会遍历所有的Rollback Segment中的所有Undo Segment，如果其状态是TRX_UNDO_TO_PURGE，调用trx_purge_free_segment开释占用的磁盘空间并从History List中删除。否则，阐明该Undo Segment正在被应用或者还在被cache（TRX_UNDO_CACHED类型），那么只通过trx_purge_remove_log_hd将其从History List中删除。

须要留神的是，Undo Truncate的动作并不是每次都会进行的，它的频次是由参数innodb_rseg_truncate_frequency管制的，也就是说要攒innodb_rseg_truncate_frequency个batch才进行一次，后面提到每一个batch中会解决innodb_purge_batch_size个Undo Records，这也就是为什么咱们从show engine innodb status中看到的Undo History List的缩短是跳变的。

4 Undo Tablespace Truncate

如果innodb_trx_purge_truncate配置关上，在函数trx_purge_truncate中还会去尝试重建Undo Tablespaces以放大文件空间占用。Undo Truncate之后，会在函数trx_purge_mark_undo_for_truncate中扫描所有的Undo Tablespace，文件大小大于配置的innodb_max_undo_log_size的Tablespace会被标记为inactive，每一时刻最多有一个Tablespace处于inactive，inactive的Undo Tablespace上的所有Rollback Segment都不参加给新事物的调配，等该文件上所有的沉闷事务退出，并且所有的Undo Log都实现Purge之后，这个Tablespace就会被通过trx_purge_initiate_truncate重建，包含重建Undo Tablespace中的文件构造和内存构造，之后被从新标记为active，参加调配给新的事务应用。

十 总结

本文首先概括地介绍了Undo Log的角色，之后介绍了一个Undo Record中的内容，紧接着介绍它的逻辑组织形式、物理组织形式、文件组织形式以及内存组织形式，详细描述了Undo Tablespace、Rollback Segment、Undo Segment、Undo Log和Undo Record的之间的关系和层级。这些组织形式都是为了更好的应用和保护Undo信息。最初在此基础上，介绍了Undo在各个重要的DB性能中的作用和实现形式，包含事务回滚、MVCC、Crash Recovery、Purge等。

参考：

[1] MySQL 8.0.11Source Code Documentation: Format of redo log
https://dev.mysql.com/doc/dev...
[2] MySQL Source Code
https://github.com/mysql/mysq...
[3] The basics of the InnoDB undo logging and history system
https://blog.jcole.us/2014/04...'s%20called%20an%20undo%20log,record%20to%20its%20previous%20version.
[4] MySQL · 引擎个性 · InnoDB undo log 漫游
http://mysql.taobao.org/month...
[5] 数据库故障复原机制的前世今生
http://catkang.github.io/2019...
[6] 浅析数据库并发管制机制
http://catkang.github.io/2018...
[7] 庖丁解InnoDB之REDO LOG

原文链接
本文为阿里云原创内容，未经容许不得转载。