20.1 事务回滚的需求

事务要保证原子性，但是偏偏有时在事务执行一半时出现以下情况：

  • 事务执行过程中遇到各种错误；
  • 程序员在事务执行事务执行过程中手动输入 ROLLBACK语句结束当前事务的执行。

所以每当要改动一条记录时(指 INSERT 、 DELETE 、 UPDATE )，都要把回滚时需要的东西记录下来——撤销日志( undo 日志)。

20.2 事务 id

如果某个事务在执行过程中对某个表执行了增删改操作，InnoDB 会给它分配一个独一无二的事务id。分配方式如下：

  • 对只读事务来说，只有在它第一次对某个用户创建的临时表执行增删改操作时，才会为这个事务分配一个事务 id ；
  • 对读写事务来说，只有在它第一次对某个表(包括用户创建的临时表)执行增删改操作时，才会为这个事务分配一个事务 id 。

事务 id 的生成策略如下：

  • 服务器在内存中维护一个全局变量，每当要分配事务 id 时，就把该变量的值作为事务id分配给该事务，并且把该变量自增 1；
  • 每当该变量值为 256 倍数时，就将该变量的值刷新到系统表空间中页号为 5 的页面中一个名为 Max Trx ID的属性中( 8 字节)；
  • 当系统下一次重新启动时，将这个 Max Trx ID属性加载到内存中，将该值加上 256 之后赋值给前面的全局变量。

trx_id 隐藏列

聚簇索引记录除了保存完整的用户数据外，还自动添加隐藏列：
image.png
其中的 trx_id 就是对这个聚簇索引记录进行改动的语句所在的事务对应的事务 id 。

20.3 undo日志的格式

InnoDB在实际增删改记录时，都要先把对应的 undo 日志记下来，会从 0 开始编号，依次递增，这个编号也叫 undo_no 。

这些 undo 日志被记录到类型为 FIL_PAGE_UNDO_LOG 的页面中。

INSERT 操作对应的 undo 日志

当向表中插入记录时，结果是这条记录被放入数据页中。如果要回滚该插入操作，只需要删除这条记录。在写对应undo日志时，只要把这条记录的主键信息记录上即可。

于是有了类型为 TRX_UNDO_INSERT_REC 的undo日志：
image.png

  • 如果记录中的主键只包含一列，那么在 undo 日志中，只需把该列占用的存储空间大小和真实值记录下来。如果记录中的主键包含多个列，那么每个列占用的存储空间和真实值记录都要记录下来。

当向某个表中插入记录时，实际上要向聚簇索引和所有二级索引都插入一条记录，不过记录 undo 日志时，只需要针对聚簇索引记录来记录一条 undo 日志即可。

聚簇索引记录和二级索引记录是一一对应的，在回滚 INSERT 操作时，只要知道这条记录的主键信息，然后根据主键信息进行对应的删除操作时，就会把聚簇索引和所有二级索引中相应的记录都删除。

roll_pointer 本质上是一个指向记录对应的 undo 日志的指针，插入记录时，大致如下：
image.png

DELETE 操作对应的 undo 日志

插入到页面中的记录会根据记录头信息中的 next_record 属性组成一个单向链表；被删除链表也由该属性组成一个链表，只不过该链表中的记录占用的空间可以被重用——垃圾链表。

在使用 DELETE 删除记录时，会有两个阶段：

  • 阶段1：仅将记录的 deleted_flag 标识位设置为 1 ，其他不做修改，此阶段为 delete mark 。此时虽然标识位被置为 1 ，但是这条记录没有被加入到垃圾链表中。所以在删除语句所在的事务提交之前，被删除的记录都处于这种中间状态。
  • 阶段2：在删除语句所在事务提交后，会有专门的线程将记录删除掉——将其从正常记录链表中移除，加入垃圾链表中并调整其他信息。该阶段为 purge 。

在被删除记录加入垃圾链表中时，实际上是加入到链表头节点处还会跟着修改 PAGE_FREE 属性的值。

TRX_UNDO_DEL_MARK_REC 类型的 undo 日志：
image.png
在对一条记录进行 delete mark 操作前，需要把该记录的 trx_id 和 roll_pointer 隐藏列的旧值都记录到对应的 undo 日志中的 trx_id 和 roll_pointer 属性中。这样就可以通过 undo 日志的 roll_pointer 属性找到上一次对该记录改动时产生的 undo 日志。

e.g. 对一条记录先进行插入操作，再进行删除操作，过程如下：
image.png
在执行完 delete mark 操作后，中间状态记录、delete mark 操作产生的 undo 日志和 INSERT 操作产生的 undo 日志就串成了链表——版本链。

UPDATE 操作对应的 undo 日志

在执行 UPDATE 语句时， InnoDB 对更新主键和不更新主键有两种处理方案：

  1. 不更新主键

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

  • 就地更新

对于被更新的每个列，如果更新后的列与更新前的列占用的存储空间一样大，就可以就地更新，即直接在原记录上修改对应列的值。

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

在不更新主键情况下，如果有任何一个被更新的列在更新前后占用的存储空间大小不一致，就要先把就记录从聚簇索引页面中删除，再根据更新后列的值创建一条新纪录并插入到页面中。

InnoDB 给出一种类型为 TRX_UNDO_UPD_EXIST_REC 的 undo 日志：
image.png

  1. 更新主键

在聚簇索引中，记录按照主键值大小连成一个单向链表。如果修改某条记录的主键值，意味着该记录在聚簇索引中的位置将会发生改变，所以在聚簇索引中分为两步处理：

  • 将旧记录进行 delete mark 操作

在 UPDATE 提交前，对旧记录只执行一个 delete mark 操作，在事务提交后才由专门的线程执行 purge 操作，从而加入到垃圾链表中。

  • 根据更新后各列的值创建一条新记录，并插入到聚簇索引中

由于更新后的记录主键值发生改变，所以需要重新从聚簇索引中定位这条记录所在的位置，然后插进去。

在对该记录进行 delete mark 操作时，会记录一条类型为 TRX_UNDO_DEL_MARK_REC 的 undo 日志；之后插入新记录时，会记录一条类型为 TRX_INSERT_REC 的 undo 日志。

增删改操作对二级索引的影响

如果操作没有涉及二级索引，那么就不需要对二级索引执行任何操作；如果在 UPDATE 语句中涉及二级索引的列，要进行一下两个操作：

  • 对旧的二级索引记录执行 delete mark 操作(考虑到 MVCC 所以只是 delete mark 操作 而不是彻底删除)
  • 根据更新后的值创建一条新的二级索引记录，然后在二级索引对应的B+树中重新定位到它的位置并插入。

20.5 FIL_PAGE_UNDO_LOG 页面

有一种类型的页面专门用于存储 undo 日志—— FIL_PAGE_UNDO_HDR ：
image.png
其中， Undo Page Header 的结构如下：
image.png

  • TRX_UNDO_PAGE_TYPE：本页面准备存储什么类型的 undo 日志；
  • TRX_UNDO_PAGE_START：在当前页面从什么位置开始存储 undo 日志，或第一条 undo 日志在本页面中的起始偏移量；
  • TRX_UNDO_PAGE_FREE：表示当前页面中存储的最后一条 undo 日志结束时的偏移量；
  • TRX_UNDO_PAGE_NODE：表示一个链表节点结构。

20.6 Undo 页面链表

在一个事务执行过程中产生的 undo 日志过多的话，在一个页面中放不下，就会放到多个页面，通过 TRX_UNDO_PAGE_NODE属性连成链表：
image.png
而由于一个页面中只存储同一类型操作的日志，如 INSERT、UPDATE、DELETE 语句。所以一般一个事务执行过程中可能需要两个 Undo 页面的链表—— insert into 链表、update into 链表。

此外，InnoDB 规定对临时表和普通表的记录改动时所产生的 undo 日志要分别记录，所以在一个事务中最多有 4 个以 Undo 页面为节点组成的链表：
image.png

20.7 undo 日志具体写入过程

段的概念

段是一个逻辑上的概念，本质上由若干个零散页面和完整的区组成。 e.g. 一个B+树索引被划分为两个段：一个叶子节点段和非叶子节点段。这样叶子节点与非叶子节点就可以分别尽可能放在一起。

每一个段对应一个 INODE Entry 结构，该结构描述该段各种信息，段 ID 、段内各种链表基节点、零散页面的页号等。

为了定位一个 INODE Entry， InnoDB设计了 Segment Header 结构：
image.png

  • Space ID of the INODE Entry： INODE Entry 结构所在表空间ID；
  • Page Number of the INODE Entry： INODE Entry结构所在的页面页号；
  • Byte Offset of the INODE Entry：INODE Entry结构在该页面中的偏移量。

Undo Log Segment Header

InnoDB 规定每个 Undo 页面链表都对应一个段—— Undo Log Segment。链表中的页面都是从该段中申请的，所以在 Undo 页面链表的第一个页面中设计了一个名为 Undo Log Segment Header部分。该部分包含该链表对应的段的 Segment Header 信息。

Undo 链表第一个页面如图：
image.png
Undo页面链表的第一个页面比普通页面多了一个 Undo Log Segment Header 结构：
image.png

  • TRX_UNDO_STATE：本 Undo 页面链表处于的状态；
  • TRX_UNDO_LAST_LOG：本 Undo页面链表中最后一个 Undo Log Header的位置；
  • TRX_UNDO_FSEG_HEADER：本 Undo 页面链表对应的段的 Segment Header信息；
  • TRX_UNDO_PAGE_LIST：Undo 页面链表的基节点。

不想看了。。。

20.8 重用 Undo 页面

Undo 页面链表需要符合两个条件才能重用：

  • 该链表中只包含一个 Undo 页面

如果一个事务在执行过程中产生了许多 undo 日志，那么可能申请非常多的页面加入 Undo 页面链表中。如果在该事务提交后，如果将整个链表中的页面都重用，就意味着即使新的事物没有向该 Undo 页面链表中写入很多 undo 日志，该链表也得维护很多页面。

  • 该 Undo 页面已经使用的空间小于整个页面空间的 3/4

如果该 Undo 页面已经使用了本页中绝大部分的存储空间，那么重用该 Undo 页面也得不到更多好处。

Undo页面链表可分为 insert undo 链表和 update undo 链表两种，这两种链表在重用时策略也不同：

  • insert undo 链表

insert undo 链表只存储类型为 TRX_UNDO_INSERT_REC 的 undo 日志。 这种类型的日志在事务提交之后就没用了，可以被清除掉。在事务提交后重用该事务的 insert undo 链表时，可以直接把之前事务写入的一组 undo 日志覆盖掉，从头开始写入新事务的 undo 日志：
image.png

  • update undo 链表

在事务提交后，它的 update undo 链表中的 undo 日志不能立即删除掉(这些日志用于 MVCC )之后的事务想要重用 update undo 链表，不能覆盖之前事务写入的 undo 日志，而是追加写入：
image.png

20.9 回滚段

在同一时刻不同事务拥有的 Undo 页面链表是不同的，系统在同一时刻可以存在许多个 Undo 页面链表。为了管理这些链表， InnoDB 设计了名为 Rollback Segment Header 的页面。这个页面中存放了各个 Undo 页面链表的 first undo page 的页号，这些页号被称为 undo slot 。
image.png
每个 Rollback Segment Header 页面都对应一个段，这个段为回滚段。
其中各项属性如下：

  • TRX_RSEG_MAX_SIZE：该回滚段中管理的所有 Undo 页面链表中的 Undo页面数量之和的最大值。默认为无限大。
  • TRX_RSEG_HISTORY_SIZE：History 链表占用的页面数量。
  • TRX_RSEG_HISTORY：History 链表的基节点。
  • TRX_RSEG_HEADER：该回滚段对应的 10字节大小的 Segment Header结构，通过它可以找回本回滚段对应的 INODE Entry。
  • TRX_RSEG_UNDO_SLOTS：各个 Undo 页面链表的 first undo page 的页号集合，即 undo slot 集合。

从回滚段中申请 Undo 页面链表

在初始情况下，由于未向任何事物分配任何 Undo 页面链表，所以对于一个 Rollback Segment Header 页面来说，各个 undo slot 都被设置为 FIL_NULL，表示该 undo slot 不指向任何页面。

随时间流逝，开始有事务需要分配 Undo 页面链表了。于是从回滚段的第一个 undo slot 开始，看该 undo slot值是否为 FIL_NULL：

  • 如果是 FIL_NULL，那么就在表空间中新创建一个段(即 Undo Log Segment)，然后从段中申请一个页面作为 Undo 页面链表的 first undo page ，最后把该 undo slot 的值设置为刚刚申请的这个页面的地址。
  • 如果不是 FIL_NULL ，说明该 undo slot 已经指向了一个 undo 链表(即已被别的事务占用)。这样就要跳到下一个 undo slot，判断该 undo slot 的值是否为 FIL_NULL ，并重复上述步骤。

当一个事务提交时，它所占用的 undo slot 会有两种处理策略：

  • 如果该 undo slot 指向的 Undo 页面链表符合被重用的条件(Undo 页面链表只占用一个页面，并且已使用空间小于整个页面的3/4)，该 undo slot 就处于被缓存的状态。被缓存的 undo slot会被加入到一个链表中。不同类型的 Undo 页面链表对应的 undo slot 会被加入到不同的链表中：

    • 如果对应的 Undo 页面链表是 insert undo 链表，则该 undo slot 会被加入 insert undo cached 链表中；
    • 如果对应的 Undo 页面链表是 update undo 链表，则该 undo slot 会被加入 update undo cached 链表中。

  • 如果该 undo slot 指向的 Undo 页面链表不符合被重用条件，根据该 undo slot 对应的 Undo 页面链表类型的不同，也会有不同的处理。

    • 如果对应的 Undo 页面链表是 insert undo 链表，则该 Undo 页面链表的 TRX_UNDO_STATE 属性会被设置为 TRX_UNDO_TO_FREE。之后该 Undo 页面链表对应的段会被释放掉，最后将该 undo slot值设置为 FIL_NULL 。

    • 如果对应的 Undo 页面链表是 update undo 链表，则该 Undo 页面链表的 TRX_UNDO_STATE 属性会被设置为 TRX_UNDO_TO_PRUGE。之后将该 undo slot 的值设置为 FIL_NULL，然后将本次事务写入的一组 undo 日志放到 History 链表中(而不会将 Undo 页面链表对应的段给释放掉，要留着为 MVCC 服务)。

多个回滚段

一个事务在执行过程中最多分配 4 个 Undo 页面链表，而一个回滚段中只有 1024 个 undo slot ，显然过少。所以 InnoDB 定义了 128 个回滚段，相当于有了 128 × 1024 = 131072 个 undo slot。

每个回滚段都对应一个 Rollback Segment Header 页面。InnoDB 将这些页面放在系统表空间第 5 号页面的某个区域中的 128 个 8 字节大小的格子中：
image.png
每个 8 字节小格子构造：image.png

回滚段的分类

128 个回滚段可分为两大类：

  • 第 0 号、第 33~127 号回滚段属于一类。其中第 0 号回滚段必须在系统表空间中；第 33~127 号回滚段既可以在表空间中，也可以在自己配置的 undo 表空间中。

  • 第 1 ~ 32 号回滚段属于一类。这些回滚段必须在临时表空间。

如果一个事务在执行过程中既对普通表进行了改动，又对临时表记录进行了改动，就需要为这个记录分配2个回滚段，然后分别到这两个回滚段中分配对应的 undo slot。

roll_pointer 的组成

聚簇索引中包含一个名为 roll_pointer 的隐藏列：
image.png

  • is_insert：表示该指针指向的 undo 日志是否是 TRX_UNDO_INSERT 大类的 undo 日志；
  • rseg id：表示该指针指向的 undo 日志的回滚段编号；
  • page number：表示该指针指向的 undo 日志在页面中的偏移量；
  • offset：表示该指针指向的 undo 日志在页面中的偏移量。

为事务分配 Undo 页面链表的过程

  1. 事务在执行过程中对普通表的记录进行首次改动之前，首先会到系统表空间的第 5 号页面分配一个回滚段(即获取一个 Rollback Segment Header页面的地址)。一旦某个回滚段被分配给这个事务，后续该事务再对普通表的记录改动时，就不会重复分配。

  2. 在分配到回滚段后，先看一下这个回滚段的两个 cached 链表有没有已经缓存的 undo slot。如果有缓存的 undo slot，就把这个缓存的 undo slot 分配给该事务；如果没有缓存的 undo slot 可供分配，就到 Rollback Segment Header 页面中找一个可用的 undo slot 分配给当前事务。

  3. 找到可用的 undo slot后，如果该 undo slot 是从 cached 链表中获取的，那么它对应的 Undo Log Segment 就已经分配了；否则需要重新分配一个 Undo Log Segment ，然后从中申请一个页面作为 Undo 页面链表的 first undo page ，并把该页的页号填入获取的 undo slot中。

  4. 然后事务就可以把 undo 日志写入上面申请的 Undo 页面链表中。

20.11 undo 日志在崩溃恢复时的作用

在服务器因为崩溃而恢复的过程中，首先需要按照 redo 日志将各个页面的数据恢复到崩溃之前的状态，这样可以保证已提交事务的持久性。但哪些没有提交的事务写的 redo 日志可能也已经刷盘，这些未提交的事务修改过的页面在 MySQL服务器重启时可能也被恢复了。

为了保证事务的原子性，需要通过 undo 日志，在服务器重启时将这些未提交的事务回滚掉。