为什么需要undo 日志（undo log）
事务需要保持原子性，但在事务的执行过程中（未提交），如果遇到不可抗力的因素造成事务未能执行完成或者开发人员手动的进行事务的rollback操作。这些问题会导致部分数据已经进行了修改，但不是全部，所以不能保持原子性。但为了实现原子性，那么我们就得将已经修改了的数据改回原来的样子，这就是回滚。
为了改回原来的样子，那你得知道原来是什么样子吧！
所以每当我们要对一条记录做改动时（这里的 改动 可以指 INSERT 、DELETE 、 UPDATE ），都需要留一手 —— 把回滚时所需的东西都给记下来。比方说：
你插入一条记录时，至少要把这条记录的主键值记下来，之后回滚的时候只需要把这个主键值对应的记录删
掉就好了。
你删除了一条记录，至少要把这条记录中的内容都记下来，这样之后回滚时再把由这些内容组成的记录插入
到表中就好了。
你修改了一条记录，至少要把修改这条记录前的旧值都记录下来，这样之后回滚时再把这条记录更新为旧值
就好了。
这些为了回滚而记录的信息称之为撤销日志，英文名为 undo log
由于查询操作（ SELECT ）并不会修改任何用户记录，所以在查询操作执行时，并不需要记录相应的 undo日志 。
事务id
一个事务可以是一个只读事务，或者是一个读写事务：
如果某个事务执行过程中对某个表执行了增、删、改操作，那么 InnoDB 存储引擎就会给它分配一个独一无二的事务id ，分配方式如下：
对于只读事务来说，只有在它 " 第一次对某个用户创建的临时表 " 执行增、删、改操作时才会为这个事务分配
一个 事务id ，否则的话是不分配 事务id 的。
对于读写事务来说，只有在它" 第一次对某个表（包括用户创建的临时表）" 执行增、删、改操作时才会为这个
事务分配一个 事务id ，否则的话也是不分配 事务id 的。
这个 事务id 本质上就是一个数字，它的分配策略和隐藏列 row_id （当用户没有为表创建主键和 UNIQUE 键时 InnoDB 自动创建的列）的分配策略大抵相同，具体策略如下：
服务器会在内存中维护一个全局变量，每当需要为某个事务分配一个 事务id 时，就会把该变量的值当作 事
务id 分配给该事务，并且把该变量自增1。
每当这个变量的值为 256 的倍数时，就会将该变量的值刷新到系统表空间的页号为 5 的页面中一个称之为
Max Trx ID 的属性处，这个属性占用 8 个字节的存储空间。
当系统下一次重新启动时，会将上边提到的 Max Trx ID 属性加载到内存中，将该值加上256之后赋值给我们
前边提到的全局变量（因为在上次关机时该全局变量的值可能大于 Max Trx ID 属性值）。
这样就可以保证整个系统中分配的 事务id 值是一个递增的数字。先被分配 id的事务得到的是较小的 事务id ，
后被分配 id 的事务得到的是较大的事务id 。
trx_id隐藏列
聚簇索引的记录除了会保存完整的用户数据以外，而且还会自动添加名为trx_id、roll_pointer的隐藏列，如果用户没有在表中定义主键以及UNIQUE键，还会自动添加一个名为row_id的隐藏列。
trx_id 列其实就是某个对这个聚簇索引记录做改动（ INSERT 、 DELETE 、 UPDATE）的语句所在的事务对应的 事务id 而已
小结个人理解：事务id其实就是一个数字，由服务器生成，trx_id等价于事务id，不过是对自己这条记录作出修改操作的事务的id
undo日志的格式
开始之前
一个事务在执行过程中可能新增、删除、更新若干条记录，也就是说需要记录很多条对应的 undo日志 ，这些 undo日志 会被从 0 开始编号，也就是说根据生成的顺序分别被称为 第0号undo日志 、 第1号undo日志 、…、 第n号undo日志 等，这个编号也被称之为 undo no 。这些 undo日志 是被记录到类型为 FIL_PAGE_UNDO_LOG的页面中。
eg：建一张表
CREATE TABLE undo_demo (
id INT NOT NULL,
key1 VARCHAR(100),
col VARCHAR(100),
PRIMARY KEY (id),
KEY idx_key1 (key1)
)Engine=InnoDB CHARSET=utf8;
其中 id 列是主键，我们为 key1 列建立了一个二级索引， col 列是一个普通的列。
每个表还会被分配一个唯一的 table id。
使用命令：
SELECT * FROM information_schema.innodb_tables WHERE name = '数据库名/undo_demo';
查看为1115
INSERT操作对应的undo日志
对于插入操作，如果希望回滚这个插入操作，那么把这条记录删除就好了，也就是说在写对应的 undo 日志时，主要是把这条记录的主键信息记上。
为了记录插入操作的日志类型为TRX_UNDO_INSERT_REC ：
undo no 在一个事务中是从 0 开始递增的，也就是说只要事务没提交，每生成一条 undo日志 ，那么该条日
志的 undo no 就增1。
如果记录中的主键只包含一个列，那么只需要把该列占用的存储空间大小和真实值记录下来，
如果记录中的主键包含多个列，那么每个列占用的存储空间大小和对应的真实值都需要记录下来
（图中的 len 就代表列占用的存储空间大小， value 就代表列的真实值）。
向 undo_demo 中插入两条记录：
BEGIN; # 显式开启一个事务，假设该事务的id为100
# 插入两条记录
INSERT INTO undo_demo(id, key1, col) VALUES (1, 'Tom', '汤姆'), (2, 'Jerry', '杰瑞');
因为记录的主键只有一个id列（ id 列的类型为 INT ， INT 类型占用的存储空间长度为 4 个字节），所以：
1、第一条 undo日志 的 undo no 为 0 ，记录主键占用的存储空间长度为 4 ，真实值为 1 。
2、第二条 undo日志 的 undo no 为 1 ，记录主键占用的存储空间长度为 4 ，真实值为 2 。
roll pointer隐藏列的含义
roll_pointer 本质上就是一个指向记录对应的 undo日志 的一个指针。 比方说我们上边向 undo_demo 表里插入了2条记录，每条记录都有与其对应的一条 undo日志 。记录被存储到了类型为 FIL_PAGE_INDEX 的页面中（就是我们前边一直所说的 数据页 ），undo日志 被存放到了类型为 FIL_PAGE_UNDO_LOG 的页面中。
DELETE操作对应的undo日志
被删除的记录会根据记录头信息中的next_record 属性组成一个链表，只不过这个链表中的记录占用的存储空间可以被重新利用，所以也称这个链表为 垃圾链表 。 Page Header 部分有一个称之为 PAGE_FREE 的属性，它指向由被删除记录组成的垃圾链表中的头节点。
使用 DELETE 语句把 正常记录链表 中的最后一条记录给删除掉，其实这个删除的过程需要经历两个阶段：
1、阶段一：仅仅将记录的 delete_mask 标识位设置为 1 ，其他的不做修改（其实会修改记录的 trx_id 、roll_pointer 这些隐藏列的值）。这个阶段称之为 delete mark 。
此时处于一个中间状态，至于为什么要有这中间状态，是为了后面的MVCC功能做准备
2、阶段二：当该删除语句所在的事务提交之后，会有专门的线程后来真正的把记录删除掉。所谓真正的删除就是把该记录从 正常记录链表 中移除，并且加入到 垃圾链表 中，然后还要调整一些页面的其他信息，比如页
面中的用户记录数量 、上次插入记录的位置 、垃圾链表头节点的指针、页面中可重用的字节数量 、还有页目的一些信息等等。这个阶段称之为 purge 。
垃圾链表重用
因为有垃圾链表存在，之后每当新插入记录时，首先判断PAGE_FREE指向的头节点代表的已删除记录占用的存储空间是否足够容纳这条新插入的记录，如果不可以容纳，就直接向页面中申请新的空间来存储这条记录，并不会尝试遍历整个垃圾链表，找到一个可以容纳新记录的节点。
如果新插入的那条记录占用的存储空间大小小于垃圾链表的头节点占用的存储空间大小，那就意味头节点对应的记录占用的存储空间里有一部分空间用不到，这部分空间就被称之为碎片空间。或者说插入的记录都比垃圾链表头结点的大，那么垃圾链表也会永远用不上。
但是，剩下的可用空间会被统计记录的（PAGE_GARBAGE属性）。
这些空间在整个页面快使用完前并不会被重新利用，不过当页面快满时，如果再插入一条记录，此时页面中并不能分配一条完整记录的空间，这时候会首先看一看PAGE_GARBAGE的空间和剩余可利用的空间加起来是不是可以容纳下这条记录，如果可以的话，InnoDB会尝试重新组织页内的记录，重新组织的过程就是先开辟一个临时页面，把页面内的记录依次插入一遍，因为依次插入时并不会产生碎片，之后再把临时页面的内容复制到本页面。 只是此操作会消耗性能。
删除语句的回滚
在删除语句所在的事务提交之前，只会经历 阶段一 ，也就是 delete mark阶段，提交之后我们就不用回滚了，所以只需考虑对删除操作的 阶段一 做的影响进行回滚。
对此，有为此设计的称之为 TRX_UNDO_DEL_MARK_REC 类型的 undo日志：
要注意的两个点：
图中记录了 old trx_id 和 old roll_pointer 属性。这样有一个好处，
那就是可以通过 undo日志 的 old roll_pointer 找到记录在修改之前对应的 undo 日志
如果某个列被包含在某个索引中，那么它的相关信息就应该被记录到
这个 索引列各列信息 部分，所谓的相关信息包括该列在记录中的位置（用 pos 表示），该列占用的存储空
间大小（用 len 表示），该列实际值（用 value 表示）。所以 索引列各列信息 存储的内容实质上就是
<pos, len, value> 的一个列表
eg;
向 undo_demo 中插入两条记录：
BEGIN; # 显式开启一个事务，假设该事务的id为100
# 插入两条记录
INSERT INTO undo_demo(id, key1, col) VALUES (1, 'Tom', '汤姆'), (2, 'Jerry', '杰瑞');
# 删除一条记录
DELETE FROM undo_demo WHERE id = 1;
对应的日志结构如下：
1、这条 undo 日志是 id 为 100 的事务中产生的第3条 undo 日志，所以它对应的 undo no 就是 2。
2、假设了这个事务id是100，所以old trx_id也就是100（对该记录最近的一次修改就发生在本事务中）
把记录的 roll_pointer 隐藏列的值取出来，填入 old roll_pointer 属性中，
这样就可以通过 old roll_pointer 属性值找到最近一次对该记录做改动时产生的 undo日志 。
3、表中有2个索引：一个是聚簇索引，一个是二级索引 idx_key1 。
只要是包含在索引中的列，那么这个列在记录中的位置（ pos ），占用存储空间大小（ len ）
和实际值（ value ）就需要存储到undo日志 中。
3.1 主键id列，pos为0，1个字节，类型为int，则占4字节，value为1,1字节，总6字节。
3.2 索引key，位置在id、old trx_id、old roll_pointer之后，所以为3,1字节；类型类型为 VARCHAR(100) ，
使用 utf8 字符集，被删除的记录实际存储的内容是Tom ，所以一共占用3个字节，
也就是所以 len 的值为 3 。 len 占用1个字节来存储。
value为“Tom”，3字节。总5字节。
4、<0, 4, 1> 和 <3, 3, 'Tom'> 共占用 11 个字节。然后 index_col_infolen 本身占用 2 个字节，
所以加起来一共占用 13 个字节，把数字 13 就填到了 index_col_info len 的属性中。
UPDATE操作对应的undo日志
在执行 UPDATE 语句时， InnoDB 对更新主键和不更新主键这两种情况有截然不同的处理方案。
不更新主键的情况
在不更新主键的情况下，又可以细分为被更新的列占用的存储空间不发生变化和发生变化的情况。
就地更新（in-place update）
如果更新后的列和更新前的列占用的存储空间都一样大，那么就可以进行 就地更新 ，也就是直接在原记录的基础上修改对应列的值。
比如这条id为2的记录：
如果修改key1的值为Cat，那么前后的占用空间是不变的，都是3字节。可以就地更新
但如果将“汤姆”修改成“波斯猫”，那么占用空间就比原来的大了，如果改成“猫”，那就比原来的小了，
都不是相等，就都不能进行就地更新
先删除掉旧记录，再插入新记录
在不更新主键的情况下，如果有任何一个被更新的列更新前和更新后占用的存储空间大小不一致，那么就需
要先把这条旧的记录从聚簇索引页面中删除掉，然后再根据更新后列的值创建一条新的记录插入到页面中。
这里所说的 删除 并不是 delete mark 操作，而是真正的删除掉，也就是把这条记录从 正常记录链表 中移除并加入到 垃圾链表 中，并且修改页面中相应的统计信息（比如 PAGE_FREE 、PAGE_GARBAGE 等这些信息）。
不过这里做真正删除操作的线程并不是在DELETE 语句中做 purge 操作时使用的另外专门的线程，而是由用户线程同步执行真正的删除操作，真正删除之后紧接着就要根据各个列更新后的值创建的新记录插入。
如果新创建的记录占用的存储空间大小不超过旧记录占用的空间，那么可以直接重用被加入到 垃圾链表 中的旧记录所占用的存储空间，否则的话需要在页面中新申请一段空间以供新记录使用，如果本页面内已经没有可用的空间的话，那就需要进行页面分裂操作，然后再插入新记录。
针对 UPDATE 不更新主键的情况（包括上边所说的就地更新和先删除旧记录再插入新记录），有一种类型为 TRX_UNDO_UPD_EXIST_REC 的 undo日志 ，它的完整结构如下：
n_updated 属性表示本条 UPDATE 语句执行后将有几个列被更新，后边跟着的 <pos, old_len, old_value>
分别表示被更新列在记录中的位置、更新前该列占用的存储空间大小、更新前该列的真实值。
如果在 UPDATE 语句中更新的列包含索引列，那么也会添加 索引列各列信息 这个部分，否则的话是不会添加
这个部分的。
update eg：
向 undo_demo 中插入两条记录：
BEGIN; # 显式开启一个事务，假设该事务的id为100
# 插入两条记录
INSERT INTO undo_demo(id, key1, col) VALUES (1, 'Tom', '汤姆'), (2, 'Jerry', '杰瑞');
# 更新一条记录
UPDATE undo_demo SET key1 = 'Cat', col = '波斯猫' WHERE id = 1;
这个 UPDATE 语句更新的列大小都没有改动，所以可以采用 就地更新 的方式来执行，在真正改动页面记录时，会先记录一条类型为 TRX_UNDO_UPD_EXIST_REC 的 undo日志：
这条日志的 roll_pointer 指向 undo no 为 0 的那条日志，也就是插入主键值为 1 的记录时产生的那条
undo日志 ，也就是最近一次对该id为1的记录做改动时产生的 undo日志 。
由于本条 UPDATE 语句中更新了索引列 key1 的值，所以需要记录一下 索引列各列信息 部分，也就是把主键
和 key1 列更新前的信息填入。
更新主键的情况
针对 UPDATE 语句中更新了记录主键值的这种情况， InnoDB 在聚簇索引中分了两步处理：
1、将旧记录进行 delete mark 操作
在 UPDATE语句所在的事务提交前，对旧记录只做一个 delete mark 操作，在事务提交后才由专门的线程做purge操作，把它加入到垃圾链表中。 之所以只对旧记录做delete mark操作，是因为别的事务同时也可能访问这条记录，如果把它真正的删除加入到垃圾链表后，别的事务就访问不到了。这个功能就是所谓的MVCC
2、根据更新后各列的值创建一条新记录，并将其插入到聚簇索引中（需重新定位插入的位置）。
由于更新后的记录主键值发生了改变，所以需要重新从聚簇索引中定位这条记录所在的位置，然后把它插进
去。
针对 UPDATE 语句更新记录主键值的这种情况，在对该记录进行 delete mark 操作前，会记录一条类型为
TRX_UNDO_DEL_MARK_REC 的 undo日志 ；之后插入新记录时，
会记录一条类型为 TRX_UNDO_INSERT_REC 的 undo日志 ，也就是说每对一条记录的主键值做改动时，
会记录2条 undo日志 。
通用链表结构
在写入 undo日志 的过程中会使用到多个链表，很多链表都有同样的节点结构，如图所示：
为了更好的管理链表，InnoDB 还提出了一个基节点的结构，里边存储了这个链表的 头节点 、 尾节点 以及链表长度信息，基节点的结构示意图如下：
List Length 表明该链表一共有多少节点。
使用 List Base Node 和 List Node 这两个结构组成的链表的示意图就是这样：
FIL_PAGE_UNDO_LOG页面
FIL_PAGE_UNDO_LOG 类型的页面是专门用来存储 undo日志的，这种类型的页面的通用结构如下图所示（以默认的 16KB 大小为例）：
以上简称undo 页面，其中结构File Header和 File Trailer 是各种页面都有。 Undo Page Header 是 Undo页面 所特有的。
TRX_UNDO_PAGE_TYPE ：本页面准备存储什么种类的 undo日志 。
前边的好几种类型的 undo日志 ，它们可以被分为两个大类：
TRX_UNDO_INSERT （使用十进制 1 表示）：类型为 TRX_UNDO_INSERT_REC 的 undo日志 属于此大类，一
般由 INSERT 语句产生，或者在 UPDATE 语句中有更新主键的情况也会产生此类型的 undo日志 。
TRX_UNDO_UPDATE （使用十进制 2 表示），除了类型为 TRX_UNDO_INSERT_REC 的 undo日志 ，其他类型
的 undo日志 都属于这个大类。
TRX_UNDO_PAGE_START ：表示在当前页面中是从什么位置开始存储 undo日志 的，
或者说表示第一条 undo日志 在本页面中的起始偏移量。
TRX_UNDO_PAGE_FREE ：与上边的 TRX_UNDO_PAGE_START 对应，表示当前页面中存储的最后一条 undo 日志
结束时的偏移量，或者说从这个位置开始，可以继续写入新的 undo日志 。
TRX_UNDO_PAGE_NODE ：代表一个 List Node 结构
eg：假设现在向页面中写入了3条 undo日志
Undo页面链表
单个事务中的Undo页面链表
因为一个事务可能包含多个语句，而且一个语句可能对若干条记录进行改动，而对每条记录进行改动前，都需要
记录1条或2条的 undo日志 ，所以在一个事务执行过程中可能产生很多 undo日志 ，这些日志可能一个页面放不
下，需要放到多个页面中，这些页面就通过我们上边介绍的 TRX_UNDO_PAGE_NODE 属性连成了链表
链表中的第一个 Undo页面 给标了出来，称它为 first undo page ，其余的 Undo页面 称之为 normal undo page ，这是因为在 first undo page 中除了记录 Undo Page Header 之外，还会记录其他的一些管理信息
同一个 Undo页面 要么只存储 TRX_UNDO_INSERT 大类的 undo日志 ，要么只存储TRX_UNDO_UPDATE 大类的 undo日志 ，反正不能混着存，所以在一个事务执行过程中就可能需要2个 Undo页面 的链表，一个称之为 insert undo链表 ，另一个称之为 update undo链表。另外，InnoDB 规定对普通表和临时表的记录改动时产生的 undo日志 要分别记录，所以在一个事务中最多有4个以 Undo页面 为节点组成的链表。
事务一开始就会为这个事务分配这4个链表，而是按需分配，啥时候需要啥时候再分配，不需要就不分配。
多个事务中的Undo页面链表
不同事务执行过程中产生的undo日志需要被写入到不同的Undo页面链表中。
假如有两个事务： trx 1 和 trx 2。trx 1 对普通表做了 DELETE 操作，对临时表做了 INSERT 和 UPDATE 操作。trx 2 对普通表做了 INSERT 、 UPDATE 和 DELETE 操作，没有对临时表做改动。那么InnoDB 共需为这两个事务分配5个 Undo页面 链表
undo日志具体写入过程
Undo Log Segment Header
在undo页面中，InnoDB也引入段的概念，每一个 Undo页面 链表都对应着一个 段 ，称之为 Undo Log Segment 。也就是说链表中的页面都是从这个段里边申请的。
段的结构：
Space ID of the INODE Entry ： INODE Entry 结构所在的表空间ID。
Page Number of the INODE Entry ： INODE Entry 结构所在的页面页号。
Byte Offset of the INODE Ent ： INODE Entry 结构在该页面中的偏移量
知道了表空间ID、页号、页内偏移量，就可以唯一定位一个 INODE Entry 的地址
在 Undo页面 链表的第一个页面，也就是上边提到的 first undopage 中设计了一个称之为 Undo Log Segment Header 的部分，这个部分中包含了该链表对应的段的 segment header 信息以及其他的一些关于这个段的信息
链表的第一个页面比普通页面多了个 Undo Log Segment Header
TRX_UNDO_STATE ：本 Undo页面 链表处在什么状态。
一个 Undo Log Segment 可能处在的状态包括：
TRX_UNDO_ACTIVE ：活跃状态，也就是一个活跃的事务正在往这个段里边写入 undo日志 。
TRX_UNDO_CACHED ：被缓存的状态。处在该状态的 Undo页面 链表等待着之后被其他事务重用。
TRX_UNDO_TO_FREE ：对于 insert undo 链表来说，如果在它对应的事务提交之后，该链表不能被重
用，那么就会处于这种状态。
TRX_UNDO_TO_PURGE ：对于 update undo 链表来说，如果在它对应的事务提交之后，该链表不能被重
用，那么就会处于这种状态。
TRX_UNDO_PREPARED ：包含处于 PREPARE 阶段的事务产生的 undo日志 。
TRX_UNDO_LAST_LOG ：本 Undo页面 链表中最后一个 Undo Log Header 的位置。
TRX_UNDO_FSEG_HEADER ：本 Undo页面 链表对应的段的 Segment Header 信息
TRX_UNDO_PAGE_LIST ： Undo页面 链表的基节点。
我们上边说 Undo页面 的 Undo Page Header 部分有一个12字节大小的 TRX_UNDO_PAGE_NODE 属性，这个属性
代表一个 List Node 结构。每一个 Undo页面 都包含 Undo Page Header 结构，这些页面就可以通过这个属
性连成一个链表。这个 TRX_UNDO_PAGE_LIST 属性代表着这个链表的基节点，当然这个基节点只存在于 Undo
页面 链表的第一个页面，也就是 first undo page 中。
Undo Log Header
InnoDB 认为同一个事务向一个 Undo页面 链表中写入的 undo日志 算是一个组。上边的 trx 1 由于会分配3个 Undo页面 链表，也就会写入3个组的 undo日志 ； trx 2 由于会分配2个 Undo页面 链表，也就会写入2个组的 undo日志 。在每写入一组 undo日志 时，都会在这组 undo日志 前先记录一下关于这个组的一些属性。InnoDB把存储这些属性的地方称之为 Undo Log Header 。 所以 Undo页面 链表的第一个页面在真正写入 undo日志 前，其实都会被填充 Undo Page Header 、 Undo Log Segment Header 、 Undo Log Header 这3个部分，
first undo page最终形态如下：
Undo Log Header 具体的结构如下：
TRX_UNDO_TRX_ID ：生成本组 undo日志 的事务 id 。
TRX_UNDO_TRX_NO ：事务提交后生成的一个需要序号，使用此序号来标记事务的提交顺序（先提交的此序号
小，后提交的此序号大）。
TRX_UNDO_DEL_MARKS ：标记本组 undo 日志中是否包含由于 Delete mark 操作产生的 undo日志 。
TRX_UNDO_LOG_START ：表示本组 undo 日志中第一条 undo日志 的在页面中的偏移量。
TRX_UNDO_XID_EXISTS ：本组 undo日志 是否包含XID信息。
TRX_UNDO_DICT_TRANS ：标记本组 undo日志 是不是由DDL语句产生的。
TRX_UNDO_TABLE_ID ：如果 TRX_UNDO_DICT_TRANS 为真，那么本属性表示DDL语句操作的表的 table id 。
TRX_UNDO_NEXT_LOG ：下一组的 undo日志 在页面中开始的偏移量。
TRX_UNDO_PREV_LOG ：上一组的 undo日志 在页面中开始的偏移量。
TRX_UNDO_HISTORY_NODE ：一个12字节的 List Node 结构，代表一个称之为 History 链表的节点。
总结
对于没有被重用的 Undo页面 链表来说，链表的第一个页面，也就是 first undo page 在真正写入 undo日志
前，会填充 Undo Page Header 、 Undo Log Segment Header 、 Undo Log Header 这3个部分，之后才开始正式写入 undo日志 。对于其他的页面来说，也就是 normal undo page 在真正写入 undo日志 前，只会填充 Undo
Page Header 。链表的 List Base Node 存放到 first undo page 的 Undo Log Segment Header 部分， List
Node 信息存放到每一个 Undo页面 的 undo Page Header 部分
个人理解就是：多个页面形成同一类型的链表记录，在第一个页面上记录整条链表的信息
重用Undo页面
为了能提高并发执行的多个事务写入 undo日志 的性能，InnoDB 决定为每个事务单独分配相应的 Undo页面 链表（最多可能单独分配4个链表）。但是这样也造成了一些问题，比如其实大部分事务执行过程中可能只修改了一条或几条记录，针对某个 Undo页面 链表只产生了非常少的 undo日志 ，这些 undo日志 可能只占用一丢丢存储空间，每开启一个事务就新创建一个 Undo页面 链表，这样就太浪费。
为了减少浪费，可以在事务提交后在某些情况下重用该事务的 Undo页面 链表。一个 Undo页面 链表是否可以被重用的条件很简单：
1、该链表中只包含一个 Undo页面 。
简短来说就是，事务提交后就算想重用这链表，但如果链表本身就有很多记录页面的话，
还要维护之前的记录，不是很划算，所以只有在 Undo页面 链表中只包含一个 Undo页面 时，
该链表才可以被下一个事务所重用。
至于为啥要维护之前的记录呢？我也不知道呢
2、该 Undo页面 已经使用的空间小于整个页面空间的3/4
undo日志 所属的大类可以被分为 insert undo链表 和 update undo链表 两种，
这两种链表在被重用时的策略也是不同的
2.1 insert undo链表
这种类型的 undo日志 在事务提交之后就没用了，就可以被清除掉。所以在某个事务提交后，
重用这个事务的 insert undo链表 （这个链表中只有一个页面）时，
可以直接把之前事务写入的一组 undo日志 覆盖掉，从头开始写入新事务的一组 undo日志 。
2.2 update undo链表
在一个事务提交后，它的 update undo链表 中的 undo日志 也不能立即删除掉（这些日志用于MVCC）。
所以如果之后的事务想重用 update undo链表 时，就不能覆盖之前事务写入的 undo日志 。
这样就相当于在同一个 Undo页面 中写入了多组的 undo日志
2.1 insert undo链表重用
2.2update undo链表
回滚段
回滚段的概念
一个事务在执行过程中最多可以分配4个 Undo页面 链表，在同一时刻不同事务拥有的 Undo页面 链表是不一样的，所以在同一时刻系统里其实可以有许许多多个 Undo页面 链表存在。为了更好的管理这些链表，InnoDB 的又设计了一个称之为 Rollback Segment Header 的页面，在这个页面中存放了各个 Undo页面 链表的 frist undo page 的 页号 ，这些 页号 称之为 undo slot 。
每个 Undo页面 链表都相当于是一个班，这个链表的 first undo page 就相当于这个班的班长，找到了这个班的班长，就可以找到班里的其他同学（其他同学相当于 normal undo page ）。有时候学校需要向这些班级传达一下精神，就需要把班长都召集在会议室，这个 Rollback Segment Header 就相当于是一个会议室。
TRX_RSEG_MAX_SIZE ：本 Rollback Segment 中管理的所有 Undo页面 链表中的 Undo页面 数量之和的最大值
TRX_RSEG_HISTORY_SIZE ： History 链表占用的页面数量。
TRX_RSEG_HISTORY ： History 链表的基节点。
TRX_RSEG_FSEG_HEADER ：本 Rollback Segment 对应的10字节大小的 Segment Header 结构，通过它可以找
到本段对应的 INODE Entry 。
TRX_RSEG_UNDO_SLOTS ：各个 Undo页面 链表的 first undo page 的 页号 集合，也就是 undo slot 集合。
一个页号占用 4 个字节，对于 16KB 大小的页面来说，这个 TRX_RSEG_UNDO_SLOTS 部分共存储了 1024 个
undo slot ，所以共需 1024 × 4 = 4096 个字节。
从回滚段中申请Undo页面链表
初始情况下，由于未向任何事务分配任何 Undo页面 链表，各个 undo slot 都被设置成了一个特殊的值：FIL_NULL ，表示该undo slot 不指向任何页面。
开始有事务需要分配 Undo页面 链表了，就从回滚段的第一个 undo slot 开始，看看该 undo slot 的值是不是 FIL_NULL ：
如果是 FIL_NULL ，那么在表空间中新创建一个段（也就是 Undo Log Segment ），然后从段里申请一个页面
作为 Undo页面 链表的 first undo page ，然后把该 undo slot 的值设置为刚刚申请的这个页面的地址，这
样也就意味着这个 undo slot 被分配给了这个事务。
如果不是 FIL_NULL，说明该 undo slot 已经指向了一个 undo链表 ，也就是说这个 undo slot 已经被别的
事务占用了，那就跳到下一个 undo slot ，判断该 undo slot 的值是不是 FIL_NULL ，重复上边的步骤。
一个 Rollback Segment Header 页面中包含 1024 个 undo slot ，如果这 1024 个 undo slot 的值都不为
FIL_NULL ，这就意味着这 1024 个 undo slot 都已经名花有主（被分配给了某个事务），此时由于新事务无法
再获得新的 Undo页面 链表，就会回滚这个事务并且给用户报错：
当一个事务提交时，它所占用的 undo slot 有两种命运：
1、如果该 undo slot 指向的 Undo页面 链表符合被重用的条件（就是我们上边说的 Undo页面 链表只占用一个
页面并且已使用空间小于整个页面的3/4）。
该 undo slot 就处于被缓存的状态，InnoDB 规定这时该 Undo页面 链表的TRX_UNDO_STATE属性会被设置为 TRX_UNDO_CACHED。
被缓存的 undo slot 都会被加入到一个链表，根据对应的 Undo页面 链表的类型不同，也会被加入到不同的
链表：insert undo ---insert undo cached；update undo---update undo cached
如果有新事务要分配 undo slot 时，先从对应的 cached链表 中找。如果没有被缓存的 undo slot ，才会到回滚段的 Rollback Segment Header 页面中再去找。
2、如果该 undo slot 指向的 Undo页面 链表不符合被重用的条件，那么针对该 undo slot 对应的 Undo页面 链
表类型不同，也会有不同的处理：
2.1 如果对应的 Undo页面 链表是 insert undo链表 ，则该 Undo页面 链表的 TRX_UNDO_STATE 属性会被设置
为 TRX_UNDO_TO_FREE ，之后该 Undo页面 链表对应的段会被释放掉，然后把该 undo slot 的值设置为 FIL_NULL 。
2.2如果对应的 Undo页面 链表是 update undo链表 ，则该 Undo页面 链表的 TRX_UNDO_STATE 属性会
被设置为 TRX_UNDO_TO_PRUGE ，则会将该 undo slot 的值设置为 FIL_NULL ，然后将本次事务写入的
一组undo 日志放到所谓的 History链表 中（并不会将 Undo页面 链表对应的段给释放掉，因为这些 undo 日志还有用）。
多个回滚段
一个事务执行过程中最多分配 4 个 Undo页面 链表，而一个回滚段里只有 1024 个 undo slot，只能支持1024个事务并发执行，所以InnoDB 定义了 128 个回滚段，也就相当于有了 128 × 1024 = 131072 个 undo slot 。假设一个读写事务执行过程中只分配 1 个 Undo页面 链表，那么就可以同时支持 131072 个读写事务并发执行。
每个回滚段都对应着一个 Rollback Segment Header 页面，有128个回滚段，自然就要有128个 Rollback Segment Header 页面。存储在系统表空间的第 5 号页面的某个区域，其中包含了128个8字节大小的格子：
每个格子的结构：
4字节大小的 Space ID ，代表一个表空间的ID。
4字节大小的 Page number ，代表一个页号。
格子 相当于一个指针，指向某个表空间中的某个页面，这些页面就是 Rollback Segment Header 。
这里需要注意的一点事，要定位一个 Rollback Segment Header 还需要知道对应的表空间ID，
这也就意味着不同的回滚段可能分布在不同的表空间中。
回滚段的分类
128个回滚段，最开始的回滚段称之为 第0号回滚段 ，之后依次递增，最后一个回滚段就称之为 第127号回滚段 。这128个回滚段可以被分成两大类：
第 0 号、第 33～127 号回滚段属于一类。其中第 0 号回滚段必须在系统表空间中（就是说第 0 号回滚段对
应的 Rollback Segment Header 页面必须在系统表空间中），第 33～127 号回滚段既可以在系统表空间中，
也可以在自己配置的 undo 表空间中
第 1～32 号回滚段属于一类。这些回滚段必须在临时表空间
为啥要把针对普通表和临时表来划分不同种类的 回滚段 呢？
对于临时表来说，因为修改临时表而产生的 undo日志 只需要在系统运行过程中有效，如果系统崩溃了，
那么在重启时也不需要恢复这些 undo 日志所在的页面，所以在写针对临时表的 Undo页面 时，
并不需要记录相应的 redo日志 。所以，在修改针对普通表的回滚段中的Undo页面时，需要记录对应的redo
日志，而修改针 对临时表的回滚段中的Undo页面时，不需要记录对应的redo日志。
为事务分配Undo页面链表详细过程
1、首先会到系统表空间的第 5 号页面中分配一个回滚段（其实就是获取一个 Rollback Segment Header 页面的地址）。一旦某个回滚段被分配给了这个事务，那么之后该事务中再对普通表的记录做改动时，就不会重复分配了。
相当于你想开一个班，那你得先跟学校报备申请，在哪栋教学楼（回滚段）开教室（undo slot）
2、在分配到回滚段后，首先看一下这个回滚段的两个 cached链表 有没有已经缓存了的 undo slot。
有缓存的 undo slot ，那么就把这个缓存的 undo slot 分配给该事务。如果没有缓存的 undo slot 可供分配，那么就要到 Rollback Segment Header 页面中找一个可用的 undoslot 分配给当前事务。
知道教学楼是哪栋后，安排教室，有可以用的教室，那就直接用，没有那就找备用的教室。
3、找到可用的 undo slot 后，如果该 undo slot 是从 cached链表 中获取的，那么它对应的 Undo LogSegment 已经分配了，否则的话需要重新分配一个 Undo Log Segment ，然后从该 Undo Log Segment 中申请一个页面作为 Undo页面 链表的 first undo page 。
找到教室后，班长就是first undo page
4、然后事务就可以把 undo日志 写入到上边申请的 Undo页面 链表了！
最后
回滚段相关配置的就不管了，用不上，实用至上，虽然前面的也用不上，但没那么用不上。嘻嘻嘻
至于前面出现的History链表没有说到，没认真思考的估计也不会想这是啥，也不影响理解undo日志