事务是需要保证原子性的，也就是事务中的操作要么全部完成，要么什么也不做。如果在事务执行过程中遇到了异常或手动执行 ROLLBACK 结束当前事务执行时，此时为了保证事务的原子性，我们需要回滚之前所做的所有操作，以保证事务符合原子性要求。因此，在我们进行增、删、改操作时，MySQL 需要把回滚时所需的改动都记录下来，这些为了回滚而记录的日志被称为撤销日志（undo log）。注意：由于查询操作并不会修改任何用户记录，所以执行查询操作时，并不需要记录相应的 undo 日志。

undo 日志在 MySQL 事务的实现中有两个作用：回滚事务和多版本并发事务，即 MVCC 机制。在 MySQL 启动事务之前，会先将要修改的数据记录存储到 undo 日志中。如果数据库的事务回滚或者 MySQL 数据库崩溃，可以利用 undo 日志对数据库中未提交的事务进行回滚操作，从而保证数据库中数据的一致性。

undo log 与 redo log 不同，redo log 记录的是页的物理日志，undo log 记录的是逻辑日志，因为在同一时刻可能会有多个并发事务的执行，一个事务在修改当前页的某几条记录时，同时还有别的事务在对同一个页中另几条记录进行修改。因此，不能直接将页回滚到开始的样子，因为这样会影响其他事务。

由于 MySQL 事务执行过程中产生的 undo 日志也需要进行持久化操作，所以 undo 日志也会产生 redo 日志。由于 undo 日志的完整性和可靠性需要 redo 日志来保证，因此数据库崩溃时需要先做 redo 日志的数据恢复，然后再做 undo 日志的回滚。

undo log 格式

为了实现事务的原子性，InnoDB 存储引擎在实际进行增、删、改一条记录时，都需要先把对应的 undo log 记下来。一个事务在执行过程中可能新增、删除、更新若干条记录，也就是说需要记录很多条对应的 undo 日志，这些 undo 日志会被从 0 开始编号，这个编号被称为 undo no。

这些 undo 日志是被记录到类型为 FIL_PAGE_UNDO_LOG 的页中。这些页可以从系统表空间中分配，也可以从专门存放 undo 日志的表空间，即所谓的 undo tablespace 中分配。下面，我们先来看看不同的操作都会产生什么不同类型的 undo 日志。

1. INSERT undo 日志

当我们向表中插入一条记录时，最终导致的结果就是这条记录被放到了一个数据页中。如果希望回滚这个插入操作，那么把这条记录删除即可，也就是说在写对应的 undo 日志时，主要是把这条记录的主键信息记上。所以 InnoDB 设计了一个类型为 TRX_UNDO_INSERT_REC 的 undo 日志，完整结构如下图所示：
image.png
如果记录中的主键只包含一个列，那么在类型为 TRX_UNDO_INSERT_REC 的 undo 日志中只需要把该列占用的存储空间大小和真实值记录下来，如果记录中的主键包含多个列，那么每个列占用的存储空间大小和对应的真实值都需要记录下来（图中的 len 代表列占用的存储空间大小，value 代表列的真实值）。

实际上，当我们向某个表中插入一条记录时，需要向聚簇索引和所有的二级索引都插入一条记录。不过记录 undo 日志时，我们只需要考虑向聚簇索引插入记录时的情况就好，因为聚簇索引记录和二级索引记录是一一对应的，我们在回滚插入操作时，只需要知道这条记录的主键信息，然后根据主键信息做对应的删除操作，做删除操作时就会顺带着把所有二级索引中相应的记录也删掉。

start_of_record 表示本条 redo 日志的开始地址，我们前面提到过的，每条列记录中的 roll_pointer 隐藏列其本质上就是一个指针，指向了记录对应的 undo日志，即指向 undo 日志中的 start_of_record 地址。

2. DELETE undo 日志

我们知道，插入到页中的记录会根据记录头信息中的 next_record 属性组成一个单向链表，我们把这个链表称为正常记录链表；被删除的记录其实也会根据记录头信息中的 next_record 属性组成一个链表，只不过这个链表中的记录占用的存储空间可以被重用，所以也称这个链表为垃圾链表。页的 Page Header 部分有个 PAGE_FREE 属性，它指向由被删除记录组成的垃圾链表中的头节点。示意图如下：
image.png
如果此时，我们准备使用 DELETE 语句把正常记录链表中的最后一条记录给删除掉，其实这个删除的过程需要经历两个阶段：

  • 阶段一：仅仅将记录的 delete_mask 标识位设置为 1，这个阶段被称为 delete mark。在删除语句所在的事务提交之前，被删除的记录一直都处于这种所谓的中间状态。

  • 阶段二：当该删除语句所在的事务提交后，会有专门的线程来真正的把记录删除掉。所谓真正的删除就是把该记录从正常记录链表中移除，并加入到垃圾链表中，然后调整一些页面的其他信息，比如页中的用户记录数量 PAGE_N_RECS、垃圾链表头节点的指针 PAGE_FREE（垃圾链表采用的是头插法）等。这个阶段被称为 purge。

当把阶段二执行完后，这条记录才算是真正的被删除掉了。这条已删除记录占用的存储空间也可以被重新利用了。由于在删除语句所在的事务提交前，只会经历阶段一，也就是 delete mark 阶段。即提交后我们就不用回滚了，所以只需考虑对删除操作的阶段一做的影响进行回滚，于是 InnoDB 设计了 TRX_UNDO_DEL_MARK_REC 类型的 undo 日志，完整结构如下图所示：
image.png
在对一条记录进行 delete mark 操作前，需要把该记录的旧的 trx_id 和 roll_pointer 隐藏列的值都给记到对应的 undo 日志中，即上图中的 old trx_id 和 old roll_pointer 属性。好处是可以通过 undo 日志的 old roll_pointer 找到记录在修改前对应的 undo 日志。比方我们在一个事务中，先插入了一条记录，然后又删除该记录，这样通过该属性可以在 delete undo log 中关联到之前的 insert undo log。

索引列各列信息的含义，就是说如果某个列被包含在某个索引中，那么它的相关信息就应该被记录到这个索引列各列信息部分，所谓的相关信息包括该列在记录中的位置（用 pos 表示），该列占用的存储空间大小（用 len 表示），该列实际值（用 value 表示）。这部分信息主要是用在事务提交后，对该中间状态记录做真正删除的阶段二，也就是 purge 阶段中使用。

3. UPDATE undo 日志

在执行 UPDATE 语句时，InnoDB 对更新主键和不更新主键这两种情况有截然不同的处理方案。

3.1 不更新主键

在不更新主键的情况下，又可以细分为被更新的列占用的存储空间不发生变化和发生变化的情况。

就地更新（in-place update）

更新记录时，对于被更新的每个列来说，如果更新后的列和更新前的列占用的存储空间都一样大，那么就可以进行就地更新，也就是直接在原记录的基础上修改对应列的值。如果有任何一个被更新的列更新前比更新后占用的存储空间大或小都不能进行就地更新。

先删除掉旧记录，再插入新记录

在不更新主键的情况下，如果有任何一个被更新的列更新前和更新后占用的存储空间大小不一致，那么就需要先把这条旧的记录从聚簇索引页面中删除掉，然后再根据更新后列的值创建一条新的记录插入到页面中。注意，这里的删除就不是 delete mark 操作了，而是真正的删除，也就是把这条记录从正常记录链表中移除并加入到垃圾链表中，并且是由用户线程同步执行真正的删除操作，而非 purge 操作时使用的另外专门的线程。

真正删除后紧接着就要根据各个列更新后的值创建的新记录插入。如果新创建的记录占用的存储空间大小不超过旧记录占用的空间，那么可以直接重用被加入到垃圾链表中的旧记录所占用的存储空间，否则的话需要在页面中新申请一段空间以供新记录使用，如果本页面内已经没有可用的空间的话，那就需要进行页面分裂操作，然后再插入新记录。

针对 UPDATE 不更新主键的情况，包括就地更新和先删除旧记录再插入新记录的情况，InnoDB 设计了一种类型为 TRX_UNDO_UPD_EXIST_REC 的 undo 日志，完整结构如下图所示：
image.png
n_updated 属性表示本条 UPDATE 语句执行后将有几个列被更新，后边跟着的 分别表示被更新列在记录中的位置、更新前该列占用的存储空间大小、更新前该列的真实值。如果在 UPDATE 语句中更新的列包含索引列，那么也会添加索引列各列信息这个部分。

3.2 更新主键

在聚簇索引中，记录是按照主键值的大小连成了一个单向链表，如果我们更新了某条记录的主键值，意味着这条记录在聚簇索引中的位置将会改变，记录更新前后在聚簇索引中的位置可能离得非常远，甚至中间隔了好多个页面。针对 UPDATE 语句中更新了记录主键值的情况，InnoDB 在聚簇索引中分了两步处理：

  • 将旧记录进行 delete mark 操作。注意，这里只进行 delete mark 操作。即在 UPDATE 语句所在的事务提交前，对旧记录只做一个 delete mark 操作，在事务提交后才由专门的线程做 purge 操作，把它加入到垃圾链表中。这里要和上边说的在不更新记录主键值时，先真正删除旧记录再插入新记录的方式区分开。


  • 根据更新后各列的值创建一条新记录，并将其插入到聚簇索引中。由于更新后的记录的主键值变了，所以需要重新从聚簇索引中定位这条记录所在的位置，然后把它插进去。

针对 UPDATE 语句更新记录主键值的这种情况，在对该记录进行 delete mark 操作前，会记录一条类型为 TRX_UNDO_DEL_MARK_REC 的 undo 日志。之后插入新记录时，会记录一条 TRX_UNDO_INSERT_REC 类型的 undo 日志，也就是说每对一条记录的主键值做改动时，会记录两条 undo 日志。

undo log 页结构

1. FIL_PAGE_UNDO_LOG

前面说过，表空间其实是由许许多多的页面构成的，页面默认大小为 16KB。这些页面有不同的类型，比如类型为 FIL_PAGE_INDEX 的页面用于存储聚簇索引以及二级索引，此外还有其他各种类型的页面，其中有一种称为
FIL_PAGE_UNDO_LOG 类型的页面是专门用来存储 undo 日志的，这种类型的页的通用结构如下所示：
image.png
上图中的 File Header 和 File Trailer 是各种页面都有的通用结构，而 Undo Page Header 是 Undo 页面所特有的属性，我们来看一下它的结构：
image.png

  • TRX_UNDO_PAGE_TYPE：本页面准备存储什么种类的 undo 日志，可以分为两个大类：
    • TRX_UNDO_INSERT：类型为 TRX_UNDO_INSERT_REC 的 undo 日志属于此类，由 INSERT 语句以及在 UPDATE 语句中有更新主键的情况时会产生此类型的 undo 日志。
    • TRX_UNDO_UPDATE：除了类型为 TRX_UNDO_INSERT_REC 的 undo 日志，其他类型的 undo 日志都属于这个大类，一般由 DELETE、UPDATE 语句会产生此类型的 undo 日志。

如果一个 Undo 页面的 TRX_UNDO_PAGE_TYPE 属性值为 TRX_UNDO_INSERT 类型，那么这个页面就只能存储类型为 TRX_UNDO_INSERT_REC 的 undo 日志，其他类型的 undo 日志就不能放到这个页面中了。之所以要把 undo 日志分成两个大类，是因为 TRX_UNDO_INSERT_REC 类型的 undo 日志在事务提交后可以直接删掉，而其他类型的 undo 日志还需要为 MVCC 服务，不能直接删除，所以对它们的处理需要区别对待。

  • TRX_UNDO_PAGE_START：表示在当前页面中是从什么位置开始存储 undo 日志的，即第一条 undo 日志在本页面中的起始偏移量。
  • TRX_UNDO_PAGE_FREE：表示当前页面中存储的最后一条 undo 日志结束时的偏移量。即可以写入 undo 日志的位置。
  • TRX_UNDO_PAGE_NODE：代表一个 List Node 结构。

2. undo 页面链表

因为一个事务可能包含多个语句，而且一个语句可能对若干条记录进行改动，而对每条记录进行改动前，都需要记录一条或两条的 undo 日志，所以在一个事务执行过程中可能会产生很多 undo 日志，这些日志可能一个页面放不下，需要放到多个页面中，这些页面就通过 TRX_UNDO_PAGE_NODE 属性行成了链表：
image.png
在一个事务执行过程中，可能混着执行 INSERT、DELETE、UPDATE 语句，这意味着会产生不同类型的 undo 日志。由于同一个 Undo 页面要么只存储 TRX_UNDO_INSERT 大类的 undo 日志，要么只存储
TRX_UNDO_UPDATE 大类的 undo 日志，所以在一个事务执行过程中就可能需要两个 Undo 页面的链表，一个称之为 insert undo 链表，另一个称之为 update undo 链表，具体如下图所示：
image.png
当然，并不是事务一开始就分配这两个链表，而是按需分配，啥时候需要啥时候再分配，不需要就不分配。同时为了尽可能提高 undo 日志的写入效率，不同事务执行过程中产生的 undo 日志需要被写入到不同的 Undo 页面链表中。因此，如果有多个事务，那就意味着可能会产生更多的 Undo 页面链表。

3. first undo page 结构

InnoDB 规定每一个 Undo 页链表都对应着一个段，称为 Undo Log Segment。链表中的页都是从这个段里边申请的，在 Undo 页链表的第一个页（first undo page）中设计了一个 Undo Log Segment Header 部分，在这个部分中包含了该链表对应的段的一些信息。

一个事务在向 Undo 页面中写入 undo 日志时，是写完一条紧接着写另一条，各条 undo 日志之间是无缝连接的。写完一个 Undo 页面后，再从段里申请一个新页面，然后把这个页面插入到 Undo 页面链表中，继续往这个新申请的页面中写。InnoDB 认为同一个事务在向一个 Undo 页面链表中写入的 undo 日志算一个组，在每写入一组 undo 日志时，都会在这组 undo 日志前先记录下关于组的一些属性，InnoDB 设计了一个 Undo Log Header 部分来存储这些属性。所以 Undo 页面链表的第一个页在真正写 undo 日志前，其结构如下图所示：
image.png
总结一下，对于 Undo 页面链表来说，链表的第一个页面（first undo page）在真正写入 undo 日志前，会填充 Undo Page Header、Undo Log Segment Header、Undo Log Header 这三个部分，之后才开始正式写入 undo 日志。对于其他的页面来说，即链表的普通页在真正写入 undo 日志前，只会填充 Undo Page Header。链表的基节点（List Base Node）会存放到 first undo page 的 Undo Log Segment Header 部分中，而页节点（List Node）信息则存放到每一个 Undo 页面的 Undo Page Header 部分，所以一个 Undo 页链表结构图为：
image.png

重用 undo log 页

InnoDB 为了提高并发执行的多个事务写入 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 链表
在一个事务提交后，它的 update undo 链表中的 undo 日志不能立即删除，因为这些日志还要用于 MVCC。所以如果之后的事务想重用 update undo 链表时，就不能覆盖之前事务写入的 undo 日志。 这样就相当于在同一个 Undo 页面中写入了多组的 undo 日志。