说说mvcc 与 undo log

分析&回答

mvcc作为多版本并发控制，使用undo log实现，同样也可以实现上述四种隔离级别，只不过实现手段不是通过传统意义上的锁罢了。当然针对RU(读未提交)隔离级别，所有更改的语句别的事务都可以直接看到，那根本没有保留多个版本的必要，用到的就是最新的唯一版本，同样S(序列化)级别，排队一个个去读写，也根本没有保留多个版本数据的必要，因为都是用最新的数据就行了。

MVCC是什么？

　　1）官方一点的解释：并发访问(读或写)数据库时，对正在事务内处理的数据做 多版本的管理。以达到用来避免写操作的堵塞，从而引发读操作的并发问题。

　　2）无节操解释，拿厕所的纸巾举例子，为了让不同的人多次进来看到的纸巾都是一样的，那么每次有人用纸巾，先做个标记版本A，(A能看到的)，然后放在一个柜子里，然后复制一个一模一样的纸巾放在纸巾盒里，标记成当前版本（自己看到的）。然后假定做一个看的规则，每个人进来只能根据规则看到之前看到的那卷纸巾，保证每个人多次进来看到的纸巾是一致的，好吧，纸巾真多，够麻烦！后面在详细解释

InnoDB中的MVCC实现原理

数据表增加两个隐藏列DATA_TRX_ID和DATA_ROLL_PTR，用于实现mvcc

事务 A 对值 x 进行更新之后，该行即产生一个新版本和旧版本。假设之前插入该行的事务 ID 为 100，事务 A 的 ID 为 200。操作过程如下

1. 对 ID = 1 的记录加排他锁，毕竟要修改了，总不能加共享锁吧
2. 把该行原本的值拷贝到 undo log 中
3. 修改该行值并且更新 DATA_TRX_ID，将 DATA_ROLL_PTR 指向刚刚拷贝到 undo log 链中的旧版本记录，记住undo log是个链表，如果多个事务多次修改会继续生成undo log并通过DATA_ROLL_PTR建立指向关系

上文中的undo log是一个链表结构，也就是如果多个事务都修改了这行数据，会根据事务ID的先后，以链表形式存放，至于旧版本存放在链表的先后顺序，这个其实无关紧要，只要方便获取就好，我倾向于每次修改后把旧版放在链表的头部，这样可以保证从指针递归下来，先找到较新的数据，再找到更旧的数据，一个个版本去判断是否是自己可以看到的版本。

ReadView

当前事务读取数据的时候如何判断应该读取哪个版本？mysql中引入了一个可读试图ReadView的概念。

ReadView主要包含如下属性：

1. mIds 代表生成ReadView时，当前活跃所有的事务ID，活跃的意思就是事务开启了还没提交，这里可以提一点，事务开启事务ID会自增，实际上事务ID就是一个全局自增的数字
2. min_trx_id 表示当前活跃的mIds中最小的事务ID
3. max_trx_id 表示生成ReadView时，最大的事务ID，这里一定不要理解成mIds中最大的ID，这是一个相当错误的理解
4. creator_trx_id 该ReadView在那个事务里创建的

ReadView有了上面4个属性后，那么应该以什么样的规则，判断当前事务到底可以读取哪个版本的数据呢？

1. 如果被访问版本的 data_trx_id 小于 m_ids 中的最小值，说明生成该版本的事务在 ReadView 生成前就已经提交了，那么该版本可以被当前事务访问。
2. 如果被访问版本的 data_trx_id大于当前事务的最大值，说明生成该版本数据的事务在生成 ReadView 后才生成，那么该版本不可以被当前事务访问。为什么这里的最大值不是mIds的最大值，因为事务ID虽然是全局递增的，但是并不代表事务ID大的一定要在事务ID小的后面提交，也就是事务开启有先后，但是事务结束的先后和开启的先后并不是完全一致的，毕竟事务有长有短。如果此时数据的事务版本是200，而mIds中没有200，那么mIds最大值就可能小于200，那么以规则2判断就可能让本该可以访问到的数据因为这个规则，而访问不到了，归根结底就是因为没有正确找到生成ReadView时的最大事务ID，所以不能肯定的说生成该版本数据的事务在生成 ReadView 后才生成
3. 如果被访问版本的 data_trx_id属性值在 最大值和最小值之间（包含），那就需要判断一下 trx_id 的值是不是在 m_ids 列表中。如果在，说明创建 ReadView 时生成该版本所属事务还是活跃的，因此该版本不可以被访问；如果不在，说明创建 ReadView 时生成该版本的事务已经被提交，该版本可以被访问。

通俗点来说，也就是ReadView中通过最大事务ID，mIds最小事务ID，mIds活跃事务列表，将当前要读的数据的事务ID分成了3种情况：

1. 要么小于mIds的最小事务ID，很明显又在当前活跃的最小事务之前生成，又不在活跃事务中，一定是已提交的事务，这个版本肯定可以访问；
2. 要么大于生成ReadView的当前的最大事务ID，很明显在所有活跃事务之后，并且也不可能存在于活跃事务列表中，那么就说明，该版本在当前活跃事务之后才出现，总不能读取到未来的版本吧；
3. 要么处于最大最小值之间，这时候就有两种情况，因为并不是说最大最小值之间就一定是活跃的，毕竟先开启的事务并不一定会先结束，事务有大小长短，这时候就很简单，在mIds中就是还没提交的活跃版本，不可被读取，不在就是已经提交的版本，可以被读取。

当一个事务要读取一行数据，首先用上面规则判断数据的最新版本也就是那行记录，如果发现可以访问就直接读取了，如果发现不能访问，就通过DATA_ROLL_PTR指针找到undo log，递归往下去找每个版本，直到读取到自己可以读取的版本为止，如果读取不到那就返回空。

反思&扩展