简介：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
原文链接
本文为阿里云原创内容，未经容许不得转载。