为什么要有undo日志 #
因为有事务回滚的需求。
事务id #
- 对于读写事务来说，只有在它第一次对某张表执行增删改操作时，才会为这个事务分配一个事务id，否则是不分配事务id的。
事务id是怎么生成的？ #
事务id本质时一个数字，分配策略与row_id隐藏类大致相同。
分配策略：
服务器会在内存中维护一个全局变量，每当需要为某个事务分配事务id时，就会把该变量的值当做事务id分配给该事务，并且把该变量自增。
每当这个变量的值为256的倍数时，就会将该变量的值刷新到系统表空间中某个页面名为Max Trx ID属性中。占8个字节。
系统重启时，会将这个属性加载到内存中，将该值加上256，之后赋值给前面提到的全局变量。
trx_id隐藏列 #
聚簇索引的记录除了会保存完整的用户数据以外，还会自动添加名为trx_id，roll_pointer的隐藏列。如果用户没有在表中定义主键以及不允许存储null值的unique键，还会自动添加一个名为row_id的隐藏列。
undo日志的格式 #
insert操作对应的undo日志 #
向某个表中插入一条记录时，实际上需要向聚簇索引和所有二级索引都插入一条记录。
但是在记录undo日志时，我们只需要针对聚簇索引记录来记录一条undo日志。
聚簇索引记录和二级所以记录时一一对应的，我们在回滚insert操作时，只需要知道这条记录的主键信息，然后根据主键信息进行对应的删除操作。在执行删除操作时，就会把聚簇索引和所有二级索引中响应的记录都删除掉。
insert类型的undo日志中有什么？
最主要是，有主键各列信息。其它的，有undo类型，undo no，表id。
delete操作对应的undo日志 #
垃圾链表
在每个页面中，被删除的记录会组成一个链表，这个链表就是垃圾链表。
这个链表通过每条记录头信息中的next_record属性链接起来。
页面Page Header中的PAGE_FREE指向表头。
删除的两个阶段
delete mark阶段，将记录的deleted_flag标识置为1。 这是一种中间状态，既不是正常记录，也不是已删除记录。
阶段2：该删除语句所在的事务提交之后，会有专门的线程来真正地把记录删除掉。即把该记录加入垃圾链表中（加入到表头）。
当前页面中可重用存储空间占用的总字节数，会存储在表头中（PAGE_GARBAGE)。记录被加入到垃圾链表后，这个属性的值就会增加。 插入新记录时，先判断垃圾链表头节点对应的已删除记录空间是否足够容纳新插入的记录。如果无法容纳，就直接向页面申请新的空间来存储，而不会遍历垃圾链表。如果可以容纳，就直接重用，PAGE_FREE指向下一条已删除记录。 碎片空间：如果新插入的记录小于重用的已删除记录的空间，那就会产生碎片。随着新记录的积累，碎片会越来越多。 页面内记录重组：页面无法分配一条完整记录的空间，但PAGE_GARBAGE+剩余空间可以容纳，InnoDB会尝试重新组织页面内的记录。 重组方法：
- 第一步，开辟临时页面，将现有页面的记录依次插入一遍。
- 第二步，把临时页面内的内容复制到本页面。
delete类型的undo日志中有什么？
日志类型，日志编号，表id，主键各列信息，索引各列信息（主要在事务提交后使用，用来对中间状态的记录进行真正的删除），旧记录的事务id，旧记录的回滚指针。
update操作对应的undo日志 #
执行update语句时，更新主键和不更新主键，处理方式不同。
不更新主键 #
分存储空间变化和不变化两种情况。
就地更新。如果更新后的记录大小不变，就直接在原记录的基础上修改对应列的值。
这里说的大小不变，是指任何一列大小都没有变化。
先删除旧记录，再插入新记录。如果更新后，记录某一列的大小发生了变化，就需要先把这条记录删除，然后再插入一条新的记录。
此处的删除是真正的删除，不是delete mark。
如果新记录占用的存储空间不超过旧记录，可以直接重用加入到垃圾链表中的旧记录所占用的存储空间，否则就要申请一块新的空间。如本页面不够用，就要进行页分裂，然后插入新记录。
update日志内容 除了旧记录id，旧记录的回滚指针，主键信息等，还会记录所有被更新列更新前的信息。
更新主键 #
在聚簇索引中，记录是按照主键大小顺序排列的，如果一条记录的主键大小发生了变化，那它的位置也就发生了变化。
步骤如下：
- 步骤1，将旧记录进行delete mark操作。
只对旧记录进行delete mark操作，是因为别的事务可能会在mvcc中用到。
- 步骤2，插入一条新记录。
每对一条记录的主键值进行改动，都会记录两条undo日志。一条是类型为TRX_UNDO_DEL_MARK_REC的undo日志，另一条是类型为TRX_uNDO_INSERT_REC的undo日志。
增删改操作对二级索引的影响 #
对于二级索引记录来说，insert操作和delete操作与在聚簇索引中执行时产生的影响差不多。 但update 不同，如果update更新了二级索引的键值，则需要：
- 对旧的二级索引记录执行delete mark操作。
- 添加新的二级索引记录。
只有聚簇索引记录才有trx_id、roll_pointer。 在增删改二级索引记录时，会影响记录所在二级索引记录所在页面的最大事务id。
通用链表结构 #
在某个表空间内，可以通过一个页的页号和在页内偏移量来唯一定位一个节点的位置。
undo页面链表 #
一个事务执行过程中可能会产生很多undo日志。这些日志可能会被放到多个页面中，这些页面组成了链表。 同一个undo页面要么只存储insert大类的undo日志，要么只存储update大类的undo日志，不能混合存储。 对普通表和临时表的记录改动产生的undo日志分别记录。 一个事务最多有4个undo页面链表。这些页面链表是按需分配的，不是在事务一开始就分配，具体分配策略如下：
- 开启事务时，不分屏。
- 想普通表插入或更新主键操作时，分配普通表的insert undo链表。
- 删除或更新了普通表中的记录，分配普通表的update undo链表。
- 向临时表中插入记录或更新记录主键，分配临时表的insert undo列表。
- 删除或更新了临时表中的记录，分配临时表的update undo链表。
undo日志具体写入过程 #
段的概念 #
段是一个逻辑概念，本质上是由若干个零散页面和若干个完整的区组成。
一个B+树索引被分成两个段:一个叶子节点段和一个非叶子节点段。这样叶子节点就可以被尽可能地存放到一起，非叶子节点被尽可能地存放到一起。
每个undo页面链表都对应着一个段。
重用undo日志 #
每个事务最多会分配4个undo页面链表。如果一个事务在执行过程中，只产生了非常少的undo日志，占用的空间很少，就会造成空间浪费。 在事务提交后的某些情况下会重用该事务的undo页面链表。要重用一个undo页面链表，必须满足以下两个条件：
- 该链表中只包含一个undo页面。 如果事务执行过程中产生的undo日志较多，会申请很多页面加入undo页面链表。在该事务提交后，如果将整个链表中的页面都重用，那即使新的事物没有写入很多日志，用不到的页面不能被其它事务所使用，该链表也要维护很多页面，是另一种浪费。
- 该undo页面已经使用的空间小于整个页面空间的3/4。 如果该undo页面已经使用了本页中的大部分空间，那重用该undo页面也得不到很多好处。
insert undo链表和update undo链表在被重用时，策略不同：
- insert undo链表 这种类型的undo日志在事务提交之后就没用了， 可以被清除掉。所以在事务提交后，重用这个事务的insert undo链表（只有一个页面）时，可以直接覆盖，从头开始写。
- update undo链表 在一个事务提交后，其update undo链表中的undo日志不能立即删除（要被用于mvcc）。如果重用，就不能覆盖。相当于同一个undo页面中写入了多组undo日志。
回滚段 #
为了更好地管理undo页面链表，InnoDB设计了名为Rollback Segment Header的页面。这个页面中存放了各个undo页面链表的first undo page的页号，这些页号称为undo slot。
每一个Rollback Segment Header都对应着一个段，这个段就称为回滚段。这个回滚段其实只有一个页面。
从回滚段中申请undo页面链表 #
在事务需要分配undo页面链表时，从回滚段的第一个undo slot开始，判断该undo slot的值是否为FIL_NULL。
- 如果是FIL_NULL，则在表空间中创建一个新段（undo log segment），然后从段中申请一个页面作为undo页面链表的first undo page，然后把该undo slot的值设置为新页面的地址。
- 不是，说明该undo slot已经指向了一个undo链表，已经被别的事务占用了。跳到下一个slot，重复上面步骤。
事务被提交时，所占用的undo slot有两种"命运“：
可以被重用，则该slot处于被缓存状态。
- 如果对应的undo页面链表时insert undo链表。则该undo slot会被加入insert undo cached链表中。
- 如果对应的undo页面链表时update undo链表。则该undo slot会被加入update undo cached链表中。
一个回滚段对应着上述两个cached链表。新事务要分配undo slot，先从cached链表中找。不能被重用，则根据该undo slot对应的undo页面链表的类型，有不同处理：
- 如果是insert undo链表，则该页面链表对应的段会被释放掉，然后把该undo slot的值设置为FIL_NULL。
- 如果对应的undo页面是update类型，则会将该undo slot的值设置为FIL_NULL，然后将本事务写入的一组undo日志放到History链表中（不会释放，还需要为mvcc服务）。
多个回滚段 #
第5号页面
一个事务在执行过程中最多分配4个undo页面链表，一个回滚段中只有1024个undo slot。InnoDB支持128个回滚段，相当于有128*1,024=131,072个undo slot。最多同时支持131,072个读写事务并发执行。
每个回滚段对应着一个Rollback Segment Header页面。
undo日志在崩溃恢复时的作用 #
服务器崩溃恢复时，首先需要按照redo日志将各个页面的数据恢复到崩溃之前的状态，这样可以保证已经提交的事务的持久性。
未提交的事务的redo日志可能也已经刷盘。
为了保证事务的原子性，有必要在服务器重启时将这些未提交的事务回滚掉。这就需要undo日志了。
步骤如下：
- 通过系统表空间的第5号也没定位到128个回滚段的位置。
- 在每一个回滚段的undo slot中找到那些不为FIL_NULL的undo slot，每个对应着一个undo页面链表。
- 从undo页面链表第一个页面的Undo Segment Header中读取当前undo页面链表状态。如果是活跃状态，则意味着有一个活跃事务正在向这个undo页面链表中写入undo日志。
- 找到本undo页面链表最后一个Undo Log Header的位置，从中可以找到对应事务id以及其一些其他信息，该事务id对应的事务就是未提交的事务。通过undo日志中记录的信息将该事务对页面所做的更改全部回滚掉。这就保证了事务的原子性。