基本概念
Redo Log记录了事务的行为，可以很好地通过其对页进行“重做”操作，但是事务有时候还需要进行回滚操作，这时就需要undo。因此在对数据库进行修改时，InnoDB存储引擎不但会产生redo log，还会产生一定量的undo log。这样如果用户执行的事务或语句由于某种原因失败了，又或者用户用一条ROLLBACK语句请求回滚，就可以利用这些undo log将数据回滚到修改之前的样子。
Undo Log默认被记录到系统表空间(ibdata)中，但从5.6开始，也可以使用独立的Undo 表空间。
Undo Log中存储的是老版本数据，当一个旧的事务需要读取数据时，为了能读取到老版本的数据，需要顺着undo链找到满足其可见性的记录。当版本链很长时，通常可以认为这是个比较耗时的操作。
当InnoDB存储引擎回滚时，它实际上做的是与先前相反的工作。对于每个INSERT，InnoDB存储引擎会完成一个DELETE；对于每个DELETE，InnoDB存储引擎会执行一个INSERT；对于每个UPDATE，InnoDB存储引擎会执行一个相反的UPDATE，将修改前的行放回去。
除了回滚操作，undo的另一个作用是MVCC，即在InnoDB存储引擎中MVCC的实现是通过undo来完成。
当用户读取一行记录时，若该记录已经被其他事务占用，当前事务可以通过undo读取之前的行版本信息，以此实现非锁定读取。
最后也是最为重要的一点是，undo log会产生redo log，也就是undo log的产生会伴随着redo log的产生，这是因为undo log也需要持久性的保护
格式
在InnoDB存储引擎中，Undo Log分为：
- insert undo log
- update undo log
insert undo log是指在insert操作中产生的undo log。因为insert操作的记录，只对事务本身可见，对其他事务不可见（这是事务隔离性的要求），故该undo log可以在事务提交后直接删除。不需要进行purge操作。insert undo log的格式如下图所示。
上图显示了insert undo log的格式，其中*表示对存储的字段进行了压缩。insert undo log开始的前两个字节next记录的是下一个undo log的位置，通过该next的字节可以知道一个undo log所占的空间字节数。类似地，尾部的两个字节记录的是undo log的开始位置。type_cmpl占用一个字节，记录的是undo的类型，对于insert undo log，该值总是为11。undo_no记录事务的ID，table_id记录undo log所对应的表对象。这两个值都是在压缩后保存的。接着的部分记录了所有主键的列和值。在进行rollback操作时，根据这些值可以定位到具体的记录，然后进行删除即可。
update undo log记录的是对delete和update操作产生的undo log。该undo log可能需要提供MVCC机制，因此不能在事务提交时就进行删除。提交时放入undo log链表，等待purge线程进行最后的删除。update undo log的结构如下图所示。
update undo log相对于之前介绍的insert undo log，记录的内容更多，所需占用的空间也更大。next、start、undo_no、table_id与之前介绍的insert undo log部分相同。这里的type_cmpl，由于update undo log本身还有分类，故其可能的值如下：
- 12 TRX_UNDO_UPD_EXIST_REC更新non-delete-mark的记录
- 13 TRX_UNDO_UPD_DEL_REC将delete的记录标记为not delete
- 14 TRX_UNDO_DEL_MARK_REC将记录标记为delete
接着的部分记录update_vector信息，update_vector表示update操作导致发生改变的列。每个修改的列信息都要记录的undo log中。对于不同的undo log类型，可能还需要记录对索引列所做的修改。
mvcc
在多线程编程中，读写的并发问题有三种策略，如下图所示
对比上面表格的三种并发策略可以知道，从上到下，并发度越来越高。而 InnoDB 用的就是CopyOnWrite思想，是在Undo Log里面实现的。每个事务修改记录之前，都会先把该记录拷贝一份出来，拷贝出来的这个备份存在Undo Log里。因为事务有唯一的编号ID，ID从小到大递增，每一次修改，就是一个版本，因此Undo Log维护了数据的从旧到新的每个版本，各个版本之间的记录通过链表串联。
也正因为每条记录都有多版本，才很容易实现事务ACID属性中的I（隔离性）。事务要并发，多个事务要读写同一条记录，为了实现第二个、第三个隔离级别，就不能让事务读取到正在修改的数据，而只能读取历史版本。
也正因为有了MVCC这种特性，通常的select语句都是不加锁的，读取的全部是数据的历史版本，从而支撑高并发的查询。这种读，专业术语叫作“快照读”，与之相对应的是“当前读”。
下图列举了快照读和当前读对应的SQL语句，快照读就是最常用的select语句，当前读包括了加锁的select语句和insert/update/delete语句。
Undo Log 逻辑结构
对于insert记录，没有历史版本数据，因此insert的Undo Log只记录了该记录的主键ID，当事务提交之后，该Undo Log就可以删除了；
对于update/delete记录，因为MVCC的存在，其历史版本数据可能还被当前未提交的其他事务所引用，一旦未提交的事务提交了，其对应的Undo Log也就可以删除了。
所以，更应该把Undo Log叫作记录的“备份数据”，即在事务未提交之前的时间里的“备份数据”！提交事务后，没有其他事务引用历史版本了，就可以删除了。
下面来看这个“备份数据”是怎么操作的。如下面的Undo Log逻辑结构图所示，Page中的每条记录，除了自身的主键ID和数据外，还有两个隐藏字段：一个是修改该记录的事务ID，一个是rollback_ptr，用来串联所有的历史版本。
假设该记录被tx_id为68、80、90、100的四个事务修改了四次，该数据就有四个版本，通过rollback_ptr从新到旧串联起来。
然后，三个历史版本分别被其他不同的事务读取。为什么会出现不同的事务读取到不同的版本呢？
因为T1、T2最先，此时历史版本3是最新的，还没有历史版本1、2；之后该记录被修改，产生了历史版本2，然后出现了T3；之后该记录又被修改，产生了历史版本1，然后出现了T4。每个事务读取的都是这个事务执行时最新的历史版本。
这些历史版本什么时候可以删除呢？在T1、T2 提交之后，历史版本3就可以删除了；在T3提交之后，历史版本2就可以删除了，依此类推。
Undo Log与Redo Log的关联
Undo Log本身也要写入磁盘，但一个事务修改多条记录，产生多条Undo Log，不可能同步写入磁盘，。那么如何解决Undo Log需要多次写入磁盘的效率问题呢？
Redo Log记录的是对数据的修改，凡是对数据的修改，都必须记入Redo Log。可以把Undo Log也当作数据！在内存中记录Undo Log，异步地刷盘，宕机重启，用Redo Log恢复Undo Log。
拿一个事务来举例：
把Undo Log和Redo Log加进去，此事务类似下面伪代码所示：
在这里，所有Undo Log和Redo Log的写入都可以只在内存中进行，只要保证Commit之后Redo Log落盘即可，Undo Log可以一直保留在内存里，之后异步刷盘。
参考资料：
https://dev.mysql.com/doc/refman/5.7/en/innodb-undo-logs.html
http://mysql.taobao.org/monthly/2015/04/01/
《软件架构设计：大型网站技术架构与业务架构融合之道》
《MySQL技术内幕 InnoDB存储引擎》第2版