上篇讲了redo log的实现原理，本篇继续讨论实现事务的重要机制之undo log。
undo log
redo log记录的是事务做了什么事，但是事务开始到提交之间的行为redo log是不管的，那如果事务执行到一半发生问题了怎么办？按照事务的原子性，事务要么都成功，要么都失败，既然有问题，那显然应该回退事务开始之后的所有操作，怎么办呢？这些操作可以从哪里找到呢，答案就是undo log。
undo log的功能
上面那段讲得就是undo log的功能之一，事务回滚，将执行过程中的事务的操作rollback到事务开始时的状态。需要注意的是，这和redo log的恢复不一样，redo log的恢复直接写磁盘数据的，也就是redo log是直接将结果应用到需要恢复的磁盘页上，而undo log的恢复是逻辑上的回滚，它回滚的是行为，就是说不是将事务开始的状态记下来，事务回滚直接将用初始状态刷新内存，而且对每一步的操作进而回退，插入操作就执行删除操作，更新操作就反向更新。那么这种回退操作有一个问题，就是某些非事务主动进行的操作是不会被回退的，比如说某事务一次性插入10w行数据，这个操作是触发表空间扩容的操作，但这个操作其实并不是事务本身的操作，所以当把这10w行数据rollback后，这个表空间的空间并不会被回收。
除了回滚事务，undo log还有一个非常重要的功能是支持MVCC。当用户需要读取一行记录时，如果某个事务正在更新这条记录，那么MySQL是通过undo log来获取事务开始的记录的版本，实现非锁定读。
最后，undo log也需要被持久化保存，所以undo log也会产生redo log。
undo log的格式
undo log有两种类型的格式，insert undo log和update undo log，这两种log格式上其实差别并不大。
insert undo log主要记录了这条log的开始的位置信息，下一条log的位置信息，插入数据主键列和值，产生log的事务等主要信息，insert undo log在事务提交后就会被删除，为什么呢？我的理解是，从undo log的功能分析，第一，事务已经提交，回滚就不会再发生了，第二，由于是插入，数据库本身不存在这些记录，所以其它事务不可能有访问这些记录的需求，那么MVCC也不需要用这个log，所以这个log继续存在的意义也就没有了。
insert undo log的内容在update undo log里都有，update log里多了一些被改变列变化前的值和变化后的值的记录。与insert log不同的是，update undo log在事务提交后并不会马上被删除，原因是update log需要提供MVCC的支持。这些log会被加入到一个引擎内的undo log链表中，等待后续操作来处理。
undo log的存储
在InnoDB引擎里有rollback segment，rollback segment里总共有1024个undo log segment，记录undo log时需要在undo log segment里申请内存页来存储。在InnoDB1.1版本之前，存储引擎只支持1个rollback segment，书上说这样就只能支持同时1024个在线的事务，所以说其实一个事务就会占据了一整个undo log segment，从1.1版本开始支持128个rollback segment，所以最大同时在线的事务数量提高为128x1024个。
undo log重用
按照前文undo log的格式一节所说，update log在事务提交后并不会马上删除，也就意味着占用的undo页并不会马上就释放，如果一个事务就占据一整个页，那么一来，这个页分配的空间会有所浪费，二来，这个页如果迟迟不释放后面会影响事务的并发总量。所以InnoDB存储引擎加入了undo页重用的机制，如果一个事务提交了，且undo log并不会马上删除的情况下，首先将这个undo log加入到内部一个链表中记录起来，其次需要判断这个页的已使用空间是否小于页大小的3/4，只有小于的才是符合重用的标准的。然后将新的undo log记录记录在这个undo页内。
purge
delete和update操作是不会直接删除原有的数据的，如果是删除操作，其实是在被删除记录上将delete flag设置为1，记录仍然存在，索引没有发生任何变化。真正删除记录是交由的存储引擎的purge操作完成的。这也是为了支持MVCC机制。purge操作会判断某条记录是否可能被删除，最终完成delete和update操作。
在之前的介绍中，我们提到了update undo log并不是在事务提交时就被清理的，后续会有操作来清理，这个操作同样也是purge。
看下面这这张图，这个history list就是我们之前一直提到的存放undo log的链表，由于引擎的设计，先提交的事务是在链表尾端的，所以图中事务提交的顺序为tx1-tx7。purge开始时，存储引擎先从尾端开始清理，也就是tx1，这时会通过记录的引用找到undo page1里的trx1的undo log并清理，之后，并不会返回history list去找tx2，而且直接查找当前undo页里的下一条undo log，也就是trx3，发现并没有被任何事务引用，则清理，继续下一条log trx5，深色表示有被事务引用，这时候才停止查找下一条log，返回history list查找尾端的trx2，接下来就依次清理undo log，这一次会把undo page2的log全部清理。
存储引擎先从history找到undo log，再从undo page中查找undo log的目的是避免purge操作在清理过程中产生大量的随机读操作，提高效率。
当存储引擎压力特别大的时候，purge操作清理的速度跟不上事务产生的速度，最终history的长度会越来越长，直到达到最大值，这时候DML操作会被delay一段时间。最坏的情况甚至有可能导致无限制的等待。
