MySQL的InnoDB存储引擎对MVCC的实现 mysqlinnodbmvcc

热衷学习，热衷生活！
沉淀、分享、成长，让自己和他人都能有所收获！

一、一致性非锁定读
对于一致性非锁定度的实现，通常的方式是加一个版本号或者时间戳，在更新数据的时候版本号+1或者更新时间戳。查询时，将当前可见的版本号与对应记录的版本号做对比，如果记录的版本号小于可见版本，则表示该记录可见。
在InnoDB存储引擎中，多版本控制就是对一致性非锁定读的实现。如果读取的行正在执行delete或者update操作，这时候读取操作不会去等待行释放锁，而是会去读取行的一个快照数据，对于这种读取历史数据的方式，叫做快照度。
在可重复读和读取已提交两个隔离级别下，如果是执行普通的select语句（不包括select ... lock in share mode, select ... for update）则会使用一致性非锁定读。
并且在可重复读下 MVCC 实现了可重复读和防止部分幻读。
二、锁定读（当前读）
如果执行的是下面语句，就是锁定读。

select ... lock in share mode
select ... for update
insert、update、delete操作

在锁定读下，读取的是数据的最新版本，这种读也被称为当前读。锁定读会对读取到的记录加锁：

select ... lock in share mode：对记录加S锁，其他事务也可以加S锁，如果加X锁则会被阻塞。
select ... for update、insert、update、delete：对记录加X锁，且其他事务不能加任何锁。

在一致性非锁定读下，即使读取的数据已经被其它事务加上了X锁，记录也是可以被读取的，读取的是快照数据。上面说了在可重复读隔离级别下MVCC防止了部分幻读，这个部分是指在一致性锁定读情况下，只能读取到第一次查询之前插入的数据（根据Read View判断数据可见性，Read View在第一次查询时生成）。但是如果是当前读，每次读取的都是最新数据，这个如果两次查询中间有其他事物插入数据就可以产生幻读。所以InnoDB在可重读时，如果当前执行的是当前读，则会对读取的记录使用Next-Key Lock，来防止其他事物在间隙间插入数据。
快照读和当前读栗子开启A和B两个会话。
首先在A会话中查询user_id = 1的user_name的记录：

begin; select user_name from t_user where user_id = 1;

查询出来的结果是：user_name = '张三'。
然后再B会话对user_id = 1的user_name进行修改：

update t_user set user_name = '李四' where user_id = 1;

然后再回到A会话继续做查询操作：

select user_name from t_user where user_id = 1; select user_name from t_user where user_id = 1 for update; select user_name from t_user where user_id = 1 lock in share mode;

三条数据查询出来的结果分别是：user_name = '张三'、user_name = '李四'、user_name = '李四'
可以看出A会话中的第一条查询是快照读，读取到的当前事务开启时的数据记录，后面两个查询是当前读，读取到的是最新数据。
三、InnoDB对MVCC的实现
MVCC（Multi-Version Concurrency Control） 多版本并发控制。
MVCC的实现主要依赖于：隐藏字段、Read View、undo log。在内部实现中通过数据行的DB_TRX_ID和Read View来判断数据的可见性，如不可见，则通过数据行的DB_ROLL_PTR找到undo log中的历史版本。每个事务读取到的数据版本可能是不一致的，在同一个事务中，用户只能看到该事务创建Read View之前已经提交的修改或者该事务本身做的修改。
隐藏字段在内部，InnoDB存储引擎为每行数据添加了三个隐藏字段，如下：

DB_TRX_ID（6字节）：表示最后一次插入或者更新改行的事务id，当我们要开始一个事务时，会向InnoDB的事务系统申请一个事务id，这个事务id是一个严格递增且唯一的数字，当前行是被哪个事务修改的，就会把对应的事务id记录在当前行中。对于delete操作会在记录头Record header中的delete_flag字段将其标记为已删除。
DB_ROLL_PTR（7字节）：回滚指针，这个回滚指针指向一个undo log日志的地址，可以通过undo log日志放这条记录恢复到历史版本，如果该行未被更新，则为空。
DB_ROW_ID（6字节）：行id，用来唯一标识一行数据，如果没有设置主键且该表没有唯一非空索引时，会使用该id来当主键生成聚簇索引。

Read View

class ReadView { private: trx_id_t m_low_limit_id; /*大于等于这个id的事务均不可见*/ trx_id_t m_up_limit_id; /*小于这个id的事务均可见*/ trx_id_t m_creator_trx_id; /*创建该Read View的事务id*/ trx_id_t m_low_limit_no; /*事务Number, 小于该Number的Undo log均可以被purge*/ ids_t m_ids; /*创建该Read View时的活跃事务列表*/ m_closed; /*标记Read View是否关闭*/ }

Read View主要是用来做可见性判断，里面保存了“当前对本事务不可见的其他活跃事务”。
主要有以下字段：

m_low_limit_id：目前出现过的最大事务id+1，即下一个将为分配的事务id，大于等于这个id的数据版本均不可见。
m_up_limit_id：活跃事务列表m_ids中最小的事务id，如果m_ids为空，则为m_low_limit_id，小于这个id的数据版本均可见。
m_ids：Read View创建时其他未提交活跃事务ID列表。创建Read View时，将当前未提交事务id记录下来，后续即使他们修改了记录行的值，对于当前事务也是不可见的。m_ids不包括当前事务自己和已提交的事务。
m_creator_trx_id：创建该Read View的事务id。

事务可见性示意图

文章图片

undo log undo log主要有两个作用：

将事务回滚时用于将数据恢复到修改前的样子。
另一个作用是MVCC，当读取记录时，若该条记录被其他事务占用或者当前版本对该事务不可见时，则可以通过undo log读取之前的版本数据，实现非锁定读。

在InnoDB存储引擎中undo log分为了两种：insert undo log和update undo log：

insert undo log：在insert 操作中产生的undo log。因为insert操作的记录只对事务本身可见，对其他事务不可见，所以insert undo log可以在事务提交后直接删除。不需要purge操作。
insert时数据初始化状态：

文章图片
update undo log：update或者delete操作中产生的undo log。该undo log可能需要提供MVCC机制，因此不能在事务提交后就进行删除。提交时放入undo log链表，等待purge线程进行最后的删除。
数据第一次被修改时：

文章图片

数据第二次被修改时：

文章图片

不同事务或者相同事务对同一记录进行的修改，会使该行记录的undo log成为一条链表，链首就是最新的记录，链尾就是最早的旧记录。
数据可见性算法在InnoDB存储引擎中，创建一个新事务后，执行每个select语句前都会创建一个快照（Read View），快照中保存了当前数据库所有正在处于活跃的事务（没有提交）id。说简单点就是保存了不应该被当前事务所能见的其他事务id（即m_ids）。当用户在这个事务中要读取某个记录行的时候，InnoDB会将该记录行的DB_TRX_ID与Read View中的当前事务事务id进行比较，判断是否满足可见条件。
具体的比较算法源码如下：图源

文章图片

如果记录DB_TRX_ID < m_up_limit_id表示最新修改的该行事务在当前事务创建快照之前就已经提交了，所以改行记录的值对当前事务是可见的。
如果记录DB_TRX_ID >= m_low_limit_id表示最新修改的行事务在当前事务创建快照之后再才修改该行，所以该记录行的值对当前事务是不可见的，跳到步骤5。
md_ids为空，说明在当前事务创建快照之前，修改该行的事务就已经提交了，所以该记录行的值对所有事务都可见。
如果m_up_limit_id <= DB_TRX_ID < m_low_limit_id ，表明最新修改行的事务在当前事务创建快照时可能处于“活跃状态”或者“已提交状态”。所以要对活跃事务列表m_ids进行查找（源码中用的二分查找法）：
- 如果在活跃事务列表m_ids能找到DB_TRX_ID说明：①在当前事务创建快照时，改行记录的值被事务DB_TRX_ID的事务修改了，但没有提交；或者②在当前事务创建快照后，该记录行的值被ID为DB_TRX_ID的事务修改了，这些情况下这个记录行的值对当前事务是不可见的。跳到步骤5。
- 如果在活跃事务列表m_ids找不到，说明DB_TRX_ID的事务在修改该记录行的值在当前事务创建快照前已经提交了，所以该行记录的值对当前事务是可见的。
在该行记录的DB_ROLL_PTR执行所指向的undo log取出快照数据，用快照数据的DB_TRX_ID跳到步骤1重新开始判断直到找到满足的快照版本或返回空。

四、读取已提交（RC）和可重复（RR）隔离级别下MVCC的差异。
在事务隔离级别RC和RR下，InnoDB存储引擎使用MVCC生成的Read View的时机不同。

在RC隔离级别下每次 select查询前都生成一个Read View（m_ids列表）。
在RR隔离级别下只在事务开始后第一次select数据前生成一个Read View（m_ids列表）。

五、MVCC解决不可重复读问题
虽然RC和RR都通过MVCC来读取快照数据，但是由于生成Read View时机不同，从而在RR级别下实现可重复读。
举个例子：

	事务101	事务102	事务103
T1	begin;
T2		begin;	begin;
T3	update user set name = '张三' where id = 1;
T4	update user set name = '李四' where id = 1;	...	select * from user where id = 1;
T5	commit;	update uset set name = '王五' where id = 1;
T6			select * from user where id = 1;
T7		update uset set name = '赵六' where id = 1;
T8		commit;
T9			select * from user where id = 1;
T10			commit;

在RC下Read View生成情况

假设时间线来到T4，那么此时数据行 id = 1的版本链为：

文章图片

由于RC级别下每次查询都会生成Read View，并且事务101、102没有提交，此时103事务生成的Read View中活跃事务为m_ids为[101,102]，m_low_limit_id为104，m_up_limit_id为101，m_creator_id为103。
- 此时最新记录的DB_TRX_ID为101，所以m_up_limit_id <= DB_TRX_ID < m_low_limit_id，所以要在m_ids列表中查找，发现DB_TRX_ID存在列表中，所以这个记录不可见。
- 根绝DB_ROLL_PTR找到undo_log中上一版本记录，上一条记录的DB_TRX_ID还是101不可见。
- 继续找上一条DB_TRX_ID为1，满足1 < m_up_limit_id所以可见，所以事务103查询的数据为name = 菜花。
假设时间线来到T6，数据的版本链为：

文章图片

因为在RC级别下，重新生成Read View，此时事务101已经提交，102事务未提交，所以此时Read View中活跃的事务m_ids为[102]，m_low_limit_id为104，m_up_limit_id为102，m_creator_id为103。
- 此时最新记录的DB_TRX_ID为102，m_up_limit_id <= DB_TRX_ID < m_up_limit_ud，所以要在m_ids中查找，发现DB_TRX_ID存在列表中，那么这个记录不可见。
- 根据DB_ROLL_PTR找到undo log中的上一版本记录，上一条记录的DB_TRX_ID为101，满足101 < t_up_limit_id，所以记录可见，所以在T6时间点查询到的数据为name = 李四 ，与时间T4查询到的结果不一致，发生了不可重复读。
假设时间先来到T9，数据的版本链为：

文章图片
- 因为在RC级别下，重新生成Read View，此时事务101、102都已经提交，所以m_ids为空，则m_up_limit_id = m_low_limit_id = 104，最新版本事务ID为102，满足102 < m_up_limit_id，所以可见，查询结果为name = 赵六。

总结：在RC隔离级别下，事务在每次查询的开始都会生成Read View，所以导致不可重复读。
在RR选Read View生成情况在可重复读级别下，只会在事务开始后的第一次读取数据是生成一个Read View（m_ids）。

假设时间线来到T4，那么此时数据行 id = 1的版本链为：

文章图片

在执行当前select语句时生成一个Read View，事务101，102未提交，此时m_ids为[101,102]，m_low_limit_id为104，m_up_limit_id为101，m_creator_trx_id为103
此时和RC级别下一样：
- 最新记录的 DB_TRX_ID 为 101，m_up_limit_id <= 101 < m_low_limit_id，所以要在 m_ids 列表中查找，发现 DB_TRX_ID 存在列表中，那么这个记录不可见
- 根据 DB_ROLL_PTR 找到 undo log 中的上一版本记录，上一条记录的 DB_TRX_ID 还是 101，不可见
- 继续找上一条 DB_TRX_ID为 1，满足 1 < m_up_limit_id，可见，所以事务 103 查询到数据为 name = 菜花。
假设时间线来到T6，那么此时数据行 id = 1的版本链为：

文章图片

因为在RR级别下只会生成一次Read View，所以此时m_ids还是为[101,102]，m_low_limit_id为104，m_up_limit_id为101，m_creator_trx_id为103
- 最新记录DB_TRX_ID为102，满足m_up_limit_id <= 102 < m_low_limit_id，且在m_ids中存在102，所以这个记录不可见。
- 根据BD_ROLL_PTR找到undo log中的上一版本，上一条记录的DB_TRX_ID为101，和上面一样，不可见。
- 继续根据DB_ROLL_PTR找到undo log的中上一版本记录，上一条记录的DB_TRX_ID还是101，还是不可见。
- 继续找上一条DB_TRX_UD为1，满足1 < m_up_limit_id，可见，所以事务103查询到的数据为name=菜花，和T4查询出来的结果一样，避免了不可重复。
假设时间线来到T9，那么此时数据行 id = 1的版本链为：

文章图片

此时情况和T6完全一样，由于已经生成了 Read View，此时依然沿用 m_ids ：[101,102] ，所以查询结果依然是 name = 菜花。

总结：在RR级别下只会在事务开始后的第一次查询生成Read View，所以可以避免不可重复的现象。
六、MVCC+Next-key Lock防止幻读
InnoDB存储引擎在RR级别下通过MVCC和Next-key Lock来解决幻读问题：

执行普通select，此时会以MVCC快照读的方式读取数据
在快照读的情况下，RR隔离级别只会在事务开始后的第一次查询生成Read View，并使用至事务提交。所以在生成Read View之后其它事务所做的更新、插入记录版本对当前事务并不可见，实现了可重复读和防止快照读下的“幻读”。
执行select for update/lock int share mode、insert、update、delete等当前读、
【MySQL的InnoDB存储引擎对MVCC的实现】在当前读下，读取的都是最新的数据，如果其它事务有插入新的记录，并且刚好在当前事务查询范围内，就会产生幻读。InnoDB使用Next-key lock来防止这种情况，在执行当前读时，会锁定读取到的记录，同时也会锁定它们的间隙，防止其它事务在查询范围内插入数据，只要我不让你插入，就不会发生幻读。