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_choose_next_log] Pop T1 from purge_queue;
- [trx_purge_get_next_rec] Iterator T1;
- [trx_purge_rseg_get_next_history_log] Get T1 next: T5;
- [trx_purge_choose_next_log] Push T5 into purge_queue;
- [trx_purge_choose_next_log] Pop T4 from purge_queue;
- [trx_purge_get_next_rec] Iterator T4;
- [trx_purge_rseg_get_next_history_log] Get T4 next: ...;
- [trx_purge_choose_next_log] Push ... into purge_queue;
- [trx_purge_choose_next_log] Pop T5 from purge_queue;
- [trx_purge_get_next_rec] Iterator T5;
- [trx_purge_rseg_get_next_history_log] Get T5 next: T6;
- [trx_purge_choose_next_log] Push T6 into 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/mysql-server/8.0.11/PAGE_INNODB_REDO_LOG_FORMAT.html
[2] MySQL Source Code
https://github.com/mysql/mysql-server
[3] The basics of the InnoDB undo logging and history system
https://blog.jcole.us/2014/04/16/the-basics-of-the-innodb-undo-logging-and-history-system/#:~:text=InnoDB keeps a copy of everything that is changed&text=It's called an undo log,record to its previous version.
[4] MySQL . 引擎特性 . InnoDB undo log 漫游
http://mysql.taobao.org/monthly/2015/04/01/
[5] 数据库故障恢复机制的前世今生
http://catkang.github.io/2019/01/16/crash-recovery.html
[6] 浅析数据库并发控制机制
http://catkang.github.io/2018/09/19/concurrency-control.html
[7] 庖丁解 InnoDB 之 REDO LOG
来源: http://zhuanlan.51cto.com/art/202111/689329.htm