数据库原理 - 序列4 - 事务是如何实现的？ - Redo Log解析（续）
> 本文节选自《软件架构设计：大型网站技术架构与业务架构融合之道》第6.4章节。 作者微信公众号：
> 架构之道与术。进入后，可以加入书友群，与作者和其他读者进行深入讨论。也可以在京东、天猫上购买纸质书。
## 6.5.5 redo log block结构
log block还需要有check sum的字段，另外还有一些头部字段。事务可大可小，可能一个block存不下产生的日志数据，也可能一个block能存下多个事务的数据。所以在block里面，得有字段记录这种偏移量。
图6-9展示了一个redo log block的详细结构，头部有12字节，尾部check sum有4个字节，所以实际一个block能存的日志数据只有496字节。
图6-9 redo log block详细结构
头部4个字段的含义分别如下：
block no：每个block的唯一编号，可以由lsn换算得到。
date len：该block中实际日志数据的大小，可能496字节没有存满。
first rec group：该block中第一条日志的起始位置，可能因为上一条日志很大，上一个block没有存下，日志的部分数据到了当前的block。如果first rec group = data len，则说明上一条日志太大，大到横跨了上一个block、当前block、下一个block，当前block中没有新日志。
checkpoint no：当前block进行check point时对应的lsn（下文会专门讲checkpoint）。
## 6.5.6 事务、lsn与log block的关系
知道了redo log的结构，下面从一个事务的提交开始分析，看事务和对应的redo log之间的关联关系。假设有一个事务，伪代码如下：
start transaction
update 表1某行记录
delete 表1某行记录
insert 表2某行记录
commit
其产生的日志，如图6-10所示。应用层所说的事务都是“逻辑事务”，具体到底层实现，是“物理事务”，也叫作mini transaction（mtr）。在逻辑层面，事务是三条sql语句，涉及两张表；在物理层面，可能是修改了两个page（当然也可能是四个page，五个page……），每个page的修改对应一个mtr。每个mtr产生一部分日志，生成一个lsn。
这个“逻辑事务”产生了两段日志和两个lsn。分别存储到redo log的block里，这两段日志可能是连续的，也可能是不连续的（中间插入的有其他事务的日志）。所以，在实际磁盘上面，一个逻辑事务对应的日志不是连续的，但一个物理事务（mtr）对应的日志一定是连续的（即使横跨多个block）。
图6-11展示了两个逻辑事务，其对应的redo log在磁盘上的排列示意图。可以看到，lsn是单调递增的，但是两个事务对应的日志是交叉排列的。
图6-10 事务与产生的redo log对应关系
图6-11 两个逻辑事务的redo log在磁盘上排列示意图
同一个事务的多条lsn日志也会通过链表串联，最终数据结构类似表6-9。其中，txid是innodb为每个事务分配的一个唯一的id，是一个单调递增的整数。
表6-9 redo log与lsn和事务的关系
## 6.5.7 事务rollback与崩溃恢复（aries算法）
**1．未提交事务的日志也在redo log中**
通过上面的分析，可以看到不同事务的日志在redo log中是交叉存在的，这意味着未提交的事务也在redo log中！因为日志是交叉存在的，没有办法把已提交事务的日志和未提交事务的日志分开，或者说前者刷到磁盘的redo log上面，后者不刷。比如图6-11的场景，逻辑事务1提交了，要把逻辑事务1的redo log刷到磁盘上，但中间夹杂的有逻辑事务2的部分redo log，逻辑事务2此时还没有提交，但其日志会被“连带”地刷到磁盘上。
所以这是aries算法的一个关键点，不管事务有没有提交，其日志都会被记录到redo log上。当崩溃后再恢复的时候，会把redo log全部重放一遍，提交的事务和未提交的事务，都被重放了，从而让数据库“原封不动”地回到宕机之前的状态，这叫repeating history。
重放完成后，再把宕机之前未完成的事务找出来。这就有个问题，怎么把宕机之前未完成的事务全部找出来？这点讲checkpoint时会详细介绍。
把未完成的事务找出来后，逐一利用undo log回滚。
**2．rollback转化为commit**
回滚是把未提交事务的redo log删了吗？显然不是。在这里用了一个巧妙的转化方法，把回滚转化成为提交。
如图6-12所示，客户端提交了rollback，数据库并没有更改之前的数据，而是以相反的方向生成了三个新的sql语句，然后commit，所以是逻辑层面上的回滚，而不是物理层面的回滚。
图6-12 一个rollback事务被转换为commit事务示意图
同样，如果宕机时一个事务执行了一半，在重启、回滚的时候，也并不是删除之前的部分，而是以相反的操作把这个事务“补齐”，然后commit，如图6-13所示。
图6-13 宕机未完成的事务被转换成commit事务
这样一来，事务的回滚就变得简单了，不需要改之前的数据，也不需要改redo log。相当于没有了回滚，全部都是commit。对于redo log来说，就是不断地append。这种逆向操作的sql语句对应到redo log里面，叫作compensation log record（clr），会和正常操作的sql的log区分开。
**3．aries恢复算法**
如图6-14所示，有t0～t5共6个事务，每个事务所在的线段代表了在redo log中的起始和终止位置。发生宕机时，t0、t1、t2已经完成，t3、t4、t5还在进行中，所以回滚的时候，要回滚t3、t4、t5。
图6-14 aries算法示意图
aries算法分为三个阶段：
**（1）阶段1：分析阶段**
分析阶段，要解决两个核心问题。
第一，确定哪些数据页是脏页，为阶段2的redo做准备。发生宕机时，虽然t0、t1、t2已经提交了，但只是redo log在磁盘上，其对应的数据page是否已经刷到磁盘上不得而知。如何找出从checkpoint到crash之前，所有未刷盘的page呢？
第二，确定哪些事务未提交，为阶段3的undo做准备。未提交事务的日志也写入了redo log。对应到此图，就是t3、t4、t5的部分日志也在redo log中。如何判断出t3、t4、t5未提交，然后对其回滚呢？
这就要谈到aries的checkpoint机制。checkpoint是每隔一段时间对内存中的数据拍一个“快照”，或者说把内存中的数据“一次性”地刷到磁盘上去。但实际上这做不到！因为在把内存中所有的脏页往磁盘上刷的时候，数据库还在不断地接受客户端的请求，这些脏页一直在更新。除非把系统阻塞住，不再接受前端的请求，这时redo log也不再增长，然后一次性把所有的脏页刷到磁盘中，叫作sharp checkpoint。
sharp checkpoint的应用场景很狭窄，因为系统不可能停下来，所以用的更多的是fuzzy checkpoint，具体怎么做呢？
在内存中，维护了两个关键的表：活跃事务表（表6-10）和脏页表（表6-11）。
活跃事务表是当前所有未提交事务的集合，每个事务维护了一个关键变量lastlsn，是该事务产生的日志中最后一条日志的lsn。
表6-10 活跃事务表
脏页表是当前所有未刷到磁盘上的page的集合（包括了已提交的事务和未提交的事务），recoverylsn是导致该page为脏页的最早的lsn。比如一个page本来是clean的（内存和磁盘上数据一致），然后事务1修改了它，对应的lsn是lsn1；之后事务2、事务3又修改了它，对应的lsn分别是lsn2、lsn3，这里recoverylsn取的就是lsn1。
表6-11 脏页表
所谓的fuzzy checkpoint，就是对这两个关键表做了一个checkpoint，而不是对数据本身做checkpoint。这点非常巧妙！因为page本身很多、数据量大，但这两个表记录的全是id，数据量很小，很容易备份。
所以，每一次fuzzy checkpoint，就把两个表的数据生成一个快照，形成一条checkpoint日志，记入redo log。
基于这两个关键表，可以求取两个问题：
问题（1）：求取crash的时候，未提交事务的集合。
以图6-14为例，在最近的一次checkpoint 2时候，未提交事务集合是{t2，t3}，此时还没有t4、t5。从此处开始，遍历redo log到末尾。
在遍历的过程中，首先遇到了t2的结束标识，把t2从集合中移除，剩下{t3}；
之后遇到了事务t4的开始标识，把t4加入集合，集合变为{t3，t4}；
之后遇到了事务t5的开始标识，把t5加入集合，集合变为{t3，t4，t5}。
最终直到末尾，没有遇到{t3，t4，t5}的结束标识，所以未提交事务是{t3，t4，t5}。
图6-15展示了事务的开始标识、结束标识以及checkpoint在redo log中的排列位置。其中的s表示start transaction，事务开始的日志记录；c表示commit，事务结束的日志记录。每隔一段时间，做一次checkpoint，会插入一条checkpoint日志。checkpoint日志记录了checkpoint时所对应的活跃事务的列表和脏页列表（脏页列表在图中未展示）。
问题（2）：求取crash的时候，所有未刷盘的脏页集合。
假设在checkpoint2的时候，脏页的集合是{p1，p2}。从checkpoint开始，一直遍历到redo log末尾，一旦遇到redo log操作的是新的page，就把它加入脏页集合，最终结果可能是{p1，p2，p3，p4}。
这里有个关键点：从checkpoint2到crash，这个集合会只增不减。可能p1、p2在checkpoint之后已经不是脏页了，但把它认为是脏页也没关系，因为redo log是幂等的。
图6-15 事务在redo log上排列示意图
阶段2：进行redo
假设最后求出来的脏页集合是{p1，p2，p3，p4，p5}。在这个集合中，可能都是真的脏页，也可能是已经刷盘了。取集合中所有脏页的recoverylsn的最小值，得到firstlsn。从firstlsn遍历redo log到末尾，把每条redo log对应的page全部重刷一次磁盘。
关键是如何做幂等？磁盘上的每个page有一个关键字段——pagelsn。这个lsn记录的是这个page刷盘时最后一次修改它的日志对应的lsn。如果重放日志的时候，日志的lsn <= pagelsn，则不修改日志对应的page，略过此条日志。
如图6-16所示，page1被多个事务先后修改了三次，在redo log的时间线上，分别对应的日志的lsn为600、900、1000。当前在内存中，page1的pagelsn = 1000（最新的值），因为还没来得及刷盘，所以磁盘中page1的pagelsn = 900（上一次的值）。现在，宕机重启，从lsn=600的地方开始重放，从磁盘上读出来pagelsn = 900，所以前两条日志会直接过滤掉，只有lsn = 1000的这条日志对应的修改操作，会被作用到page1中。
图6-16 pagelsn实现redo log幂等示意图
这点与tcp在接收端对数据包的判重有异曲同工之妙！在tcp中，是对发送的数据包从小到大编号（seq number），这里是对所有日志从小到大编号（lsn），接收的一方发现收到的日志编号比之前的还要小，就说明不用重做了。
有了这种判重机制，我们就实现了redo log重放时的幂等。从而可以从firstlsn开始，将所有日志全部重放一遍，这里面包含了已提交事务和未提交事务的日志，也包含对应的脏页或者干净的页。
redo完成后，就保证了所有的脏页都成功地写入到了磁盘，干净页也可能重新写入了一次。并且未提交事务t3、t4、t5对应的page数据也写入了磁盘。接下来，就是要对t3、t4、t5回滚。
阶段3：进行undo
在阶段1，我们已经找出了未提交事务集合{t3，t4，t5}。从最后一条日志逆向遍历，因为每条日志都有一个prevlsn字段，所以可以沿着t3、t4、t5各自的日志链一直回溯，最终直到t3的第一条日志。
所谓的undo，是指每遇到一条属于t3、t4、t5的log，就生成一条逆向的sql语句来执行，其执行对应的redo log是compensation log record（clr），会在redo log尾部继续追加。所以对于redo log来说，其实不存在所谓的“回滚”，全部是正向的commit，日志只会追加，不会执行“物理截断”之类的操作。
要生成逆向的sql语句，需要记录对应的历史版本数据，这点将在分析undo log的时候详细解释。
这里要注意的是：redo的起点位置和undo的起点位置并没有必然的先后关系，图中画的是undo的起点位置小于redo的起点位置，但实际也可以反过来。以为redo对应的是所有脏页的最小lsn，undo对应的是所有未提交事务的起始lsn，两者不是同一个维度的概念。
在进行undo操作的时候，还可能会遇到一个问题，回滚到一半，宕机，重启，再回滚，要进行“回滚的回滚”。
如图6-17所示，假设要回滚一个未提交的事务t，其有三条日志lsn分别为600、900、1000。第一次宕机重启，首先对lsn=1000进行回滚，生成对应的lsn=1200的日志，这条日志里会有一个字段叫作undonxtlsn，记录的是其对应的被回滚的日志的前一条日志，即undonxtlsn = 900。这样当再一次宕机重启时，遇到lsn=1200的clr，首先会忽略这条日志；然后看到undonxtlsn = 900，会定位到lsn=900的日志，为其生成对应的clr日志lsn=1600；然后继续回滚，lsn=1700的日志，回滚的是lsn=600。
这样，不管出现几次宕机，重启后最终都能保证回滚日志和之前的日志一一对应，不会出现“回滚嵌套”问题。
图6-17 回滚过程中出现宕机后再次重启回滚
到此为止，已经对事务的a（原子性）和d（持久性）有了一个全面的理解，接下来将讨论i的实现。在此先对redo log做一个总结：
(1) 一个事务对应多条redo log，事务的redo log不是连续存储的。
(2) redo log不保证事务的原子性，而是保证了持久性。无论提交的，还是未提交事务的日志，都会进入redo log。从而使得redo log回放完毕，数据库就恢复到宕机之前的状态，称为repeating history。
(3) 同时，把未提交的事务挑出来并回滚。回滚通过checkpoint记录的“活跃事务表”+ 每个事务日志中的开始/结束标记 + undo log 来实现。
(4) redo log具有幂等性，通过每个page里面的pagelsn实现。
(5) 无论是提交的、还是未提交的事务，其对应的page数据都可能被刷到了磁盘中。未提交的事务对应的page数据，在宕机重启后会回滚。
(6) 事务不存在“物理回滚”，所有的回滚操作都被转化成了commit。