上面说的redo log记录了事务的行为，可以通过其对页进行重做操作，但是食物有时候需要进行回滚，这时候就需要undo log了。[1]
**关于Undo Log的存储：**InnoDB中有回滚段(rollback segment)，每个回滚段记录1024个undo log segment，在每个undo log segment段中进行申请undo页。系统表空间偏移量为5的页记录了所有的rollback segment header所在的页。
1、undo log的格式
根据行为不同分为两种：
insert undo log
insert undo log：只对事务本身可见，所以insert undo log在事务提交后可直接删除，无需执行purge操作；
insert undo log主要记录了：
| next | 记录下一个undo log的位置 |
|---|---|
| type_cmpl | undo的类型：insert or update |
| *undo_no | 记录事务的ID |
| *table_id | 记录表对象 |
| *len1, col1 | 记录列和值 |
| *len2, col2 | 记录列和值 |
| … | … |
| start | 记录undo log的开始位置 |
假设在事务1001中，执行以下sql，t20的table_id为10：
1 | insert into t20(id, a, b, c, d) values(12, 2, 3, 1, "init") |
那么对应会生成一条undo log：
update undo log
update undo log：执行update或者delete会产生undo log，会影响已存在的记录，为了实现MVCC(后边介绍)，update undo log不能再事务提交时立刻删除，需要将事务提交时放入到history list上，等待purge线程进行最后的删除操作。
update undo log主要记录了：
| next | 记录下一个undo log的位置 |
|---|---|
| type_cmpl | undo的类型：insert or update |
| *undo_no | undo日志编号 |
| *table_id | 记录表对象 |
| info_bits | |
| *DATA_TRX_ID | 事务的ID |
| *DATA_ROLL_PTR | 回滚指针 |
| *len1, i_col1 | n_unique_index |
| *len2, i_col2 | |
| … | |
| n_update_fields | 以下是update vector信息，表示update操作导致发送改变的列 |
| *pos1, *len1, u_old_col1 | |
| *pos2, *len2, u_old_col2 | |
| … | |
| n_bytes_below | |
| *pos, *len, col1 | |
| *pos, *len, col2 | |
| … | |
| start | 记录undo log的开始位置 |
假设在事务1002中，执行以下sql，t20的table_id为10：
1 | update t20 set d="update1" where id=60; |
那么对应会生成一条undo log：
如上图，每回退应用一个undo log，就回退一个版本，这就是MVCC(Multi versioning concurrency control)的实现原理。
下面我们在执行一个delete sql：
1 | delete from t20 where id=60; |
对应的undo log变为如下：
如上图，实际的行记录不会立刻删除，而是在行记录头信息记录了一个deleted_flag标志位。最终会在purge线程purge undo log的时候进行实际的删除操作，这个时候undo log也会清理掉。
2、MVCC实现原理
如上图所示，MySQL只会有一个行记录，但是会把每次执行的sql导致行记录的变动，通过undo log的形式记录起来，undo log通过回滚指针连接在一起，这样我们想回溯某一个版本的时候，就可以应用undo log，回到对应的版本视图了。
我们知道InnoDB是支持RC(Read Commit)和RR(Repeatable Read)事务隔离级别的，而这个是通过一致性视图(consistent read view)实现的。
一个事务开启瞬间，所有活跃的事务(未提交)构成了一个视图数组，InnoDB就是通过这个视图数组来判断行数据是否需要undo到指定的版本：
RR事务隔离级别
假设我们使用了RR事务隔离级别。我们看个例子：
如下图，假设id=60的记录a=1
事务C启动的瞬间，活跃的事务如下图黄色部分所示：
也就是对于事务A、事务B、事务C，他们能够看到的数据只有是行记录中的最大事务IDDATA_TRX_ID<=11的，如果大于，那么只能通过undo进行回滚了。如果TRX_ID=当前事务id，也可以看到，即看到自己的改动。
另外有一个需要注意的：
- 在RR隔离级别下，当事务更新事务的时候，只能用当前读来获取最新的版本数据来更新，如果当前记录的行锁被其他事务占用，就需要进入所等待；
- 在RC隔离级别下，每个语句执行都会计算出新的一致性视图。
所以我们分析上面的例子的执行流程：
- 事务C执行update，执行当前读，拿到的a=1，然后+1，最终a=2，同时添加一个TRX_ID=11的undo log；
- 事务B执行select，使用快照读，记录的DATA_TRX_ID > 11，所以需要通过undo log回滚到DATA_TRX_ID=11的版本，所以拿到的a是1；
- 事务B执行update，需要使用当前读，拿到最新的记录，a=2，然后加1，最终a=3；
- 事务B执行select，拿到当前最新的版本，为自己的事务id，所以得到a=3；
- 事务A执行select，使用快照读，记录的DATA_TRX_ID > 11，所以需要通过undo log回滚到DATA_TRX_ID=11的版本，所以拿到的a是1。
- 如果是RC隔离级别，执行select的时候会计算出新的视图，新的视图能够看到的最大事务ID=14，由于事务B还没提交，事务C提交了，所以可以得到a=2：
References
姜承尧. MySQL技术内幕-InnoDB存储引擎第二版[M]. 机械工业出版社, 2013-5:306. ↩︎
