浅谈 MySQL 的 MVCC 机制

最近公司组织技术分享，因为刚好周末空闲时间在翻译 MySQL 的文档，接触到 MySQL 的 MVCC 机制，于是便选了这个点进行分享，虽然做了 PPT，但还是写个博客，串联一下思路。

一、简介

MVCC 可用于实现 RC 和 RR 隔离级别的一致性读，基本思想是通过维护数据行的历史版本及比较版本数据和当前系统的活跃事务情况以决定返回给客户端查询的镜像数据。 MVCC 主要依赖：

数据行隐藏的辅助列
Read View
Undo Logs

二、辅助列

InnoDB 为聚簇索引中的记录加了几个隐藏的列（源码见 /storage/innobase/include/data0type.h）：

DB_ROW_ID：6 字节大小，隐式的自增的行标记，若表不定义聚簇索引，InnoDB 自动在该列上创建聚簇索引；
DB_TRX_ID：6 字节大小，标识最后插入、更新或删除该行的事务；
DB_ROLL_PTR：7 字节，回滚指针，指向回滚段的首个 page

所以一行数据大概长这样：

三、Read View

InnoDB 在实现 MVCC 时用到的一致性读视图，用于支持 RC 和 RR 隔离级别的实现，Read View 是以逆序排列的，其代码位于 storage/innobase/include/read0read.h，属性包括：

low_limit_id：事务 ID 大于等于该值的事务不能看到该视图，高水位
up_limit_id：事务 ID 小于等于该值的事务能看到该视图，低水位
n_trx_ids：当前活跃事务（即未提交的事务）的数量
trx_ids：以逆序排列的当前获取活跃事务 ID 的数组（其up_limit_id < tx_id < low_limit_id）
creator_trx_id：创建当前视图的事务 ID

视图创建过程：

获取当前全局事务链表，剔除其中已提交及当前事务得到当前事务的一致性视图，并记录高低水位的事务 ID，代码见 storage/innobase/read/read0read.cc 里面的 read_view_open_now_low 方法。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


static read_view_t* read_view_open_now_low(
	trx_id_t	cr_trx_id,	/*!< in: trx_id of creating
					transaction, or 0 used in purge */
	mem_heap_t*	heap)		/*!< in: memory heap from which
					allocated */
{
	read_view_t*	view;
	ulint		n_trx = UT_LIST_GET_LEN(trx_sys->rw_trx_list);
	ut_ad(mutex_own(&trx_sys->mutex));
	view = read_view_create_low(n_trx, heap);
	view->undo_no = 0;
	view->type = VIEW_NORMAL;
	view->creator_trx_id = cr_trx_id;
	/* No future transactions should be visible in the view */
	view->low_limit_no = trx_sys->max_trx_id;
	view->low_limit_id = view->low_limit_no;
	/* No active transaction should be visible, except cr_trx */
	ut_list_map(trx_sys->rw_trx_list, &trx_t::trx_list, CreateView(view));
	if (view->n_trx_ids > 0) {
		/* The last active transaction has the smallest id: */
		view->up_limit_id = view->trx_ids[view->n_trx_ids - 1];
	} else {
		view->up_limit_id = view->low_limit_id;
	}
	/* Purge views are not added to the view list. */
	if (cr_trx_id > 0) {
		read_view_add(view);
	}
	return(view);
}

四、Undo Logs

撤销日志，用于回滚事务对聚簇索引记录的更新

撤销日志段（undo log segments）：由多条撤销日志组成；
回滚段（rollback segments）：由多个撤销日志段组成，存在于系统表空间、撤销表空间和和临时表空间中。

回滚段的基本组织单元是页，一个数据记录的历史版本存储在某个段中，段以链表的形式存储，每个历史版本记为一个 log 记录，每个记录可能跨越多个页。

undo 记录的代码见storage/innobase/include/trx0undo.h 中的 trx_undo_t 结构
回滚段代码见 storage/innobase/include/trx0rseg.h 中的 trx_rseg_t 结构

按我理解，数据行和回滚段的结构及关系大概长这样：

五、版本可见性判断

Undo Logs 中记录了某个行的版本变化过程，当某个事务的查询过来的时候，如果查询在聚簇索引上，则将索引记录上的 DB_TRX_ID 和该事务的 Read View 进行匹配（见匹配规则）。如果查询走了二级索引，因为二级索引上只记录了最后更新该行的 DB_TRX_ID，所以也可以走匹配规则，如果匹配到并且走到覆盖索引，则可直接返回版本数据，否则需要进行回表，获取到回滚段的指针，并对版本链节点进行匹配（见匹配规则）

比较规则如下所示，代码见storage/innobase/include/read0read.ic 中的 read_view_sees_trx_id 函数：

如果 trx_id < up_limit_id，则该版本的事务已经提交，可以读取。
如果 trx_id >= low_limit_id，则该版本的事务还没提交，不能读取。
如果 trx_id == 当前事务 ID，可读取
如果 up_limit_id <= trx_id < low_limit_id，使用二分查找，看 DB_TRX_ID 是否在 trx_ids 中，是则表示事务是活跃的，还没提交，不可读该版本，否则可读取。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


bool read_view_sees_trx_id(
	const read_view_t*	view,	/*!< in: read view */
	trx_id_t		trx_id)	/*!< in: trx id */
{
	if (trx_id < view->up_limit_id) {
		return(true);
	} else if (trx_id >= view->low_limit_id) {
		return(false);
	} else {
		ulint	lower = 0;
		ulint	upper = view->n_trx_ids - 1;
		ut_a(view->n_trx_ids > 0);
		do {
			ulint		mid	= (lower + upper) >> 1;
			trx_id_t	mid_id	= view->trx_ids[mid];
			if (mid_id == trx_id) {
				return(FALSE);
			} else if (mid_id < trx_id) {
				if (mid > 0) {
					upper = mid - 1;
				} else {
					break;
				}
			} else {
				lower = mid + 1;
			}
		} while (lower <= upper);
	}
	return(true);
}

为了实现不同的隔离级别，MVCC 有不同的创建 Read View 的机制：

RR 级别下，事务中的第一个 SELECT 请求才开始创建 Read View，而且只会创建一个。
RC 级别下，事务中每次 SELECT 请求都会重新创建一个 Read View。

六、MVCC 工作实例

对于 RR 隔离级别，在第一次 SELECT 时创建的 Read View 伴随整个事务的生命周期，所以尽管事务 C 提交了新的修改，这个变动对事务 A 是不可见的，所以事务 A 两次获取到的 k 的值都是 1。

对于 RC 隔离级别，每次 SELECT 时都会创建新的 Read View，所以事务 A 第一次查到的 k 的值是 1，当事务 C 提交后，事务 A 再次查询，遍历到版本链中事务 C 提交的改动时便返回了。

七、RR 下的幻读问题

假设我们在 RR 下进行以下实验，脚本的位置代表执行的时序

事务 1 还没提交能够查询到事务 2 插入的数据，产生了所谓的幻读现象。

原因是对更新数据都是先读后写的，而这个读，只能读当前的值，称为“当前读”（current read）所以事务 1 会读到事务 2 在版本链中插入的数据，并且进行修改，最后将自己的事务 ID 记录到 Undo Log 中，等到下次读取的时候判断到是自己事务的修改，就能把 id 是 3 的记录读出来。

实际上 InnoDB 是解决了幻读问题的，因为读分为了快照读和当前读。

在快照读下，InnoDB 通过 MVCC 避免幻读；而在当前读情况下，通过 Next-Key Lock 避免幻读。

select * from t_user where id>1; 属于快照读
select * from t_user where id>1 lock in share mode; 属于当前读

不应该把快照读和当前读得到的结果不一样这种情况认为是幻读，这是两种不同的使用。

八、参考

2021-11-21 更新总结

生成 readView：遍历全局事务链，剔除已提交及当前事务 ID，得到
1. low_limit_id：事务 ID 大于等于该值的事务不能看到该视图，高水位
2. up_limit_id：事务 ID 小于等于该值的事务能看到该视图，低水位
3. trx_ids：以逆序排列的当前获取活跃事务 ID 的数组（其 up_limit_id < trx_id < low_limit_id）
在 cluster_idx 中找到目标索引记录，拿到对应的回滚段指针
1. 遍历回滚段（版本链），比对每个版本的 trx_id 与 readView
  1. 如果 trx_id > up_limit_id，说明该版本对应事务未提交，该版本不可读
  2. 如果 trx_id < low_limit_id，说明该版本对应事务已提交，该版本可读
  3. 如果 up_limit_id < trx_id < low_limit_id，对 trx_ids 进行二分查找，如果找到 trx_id，说明该版本对应事务处于活跃状态，还没提交，该版本不可读；否则该版本可读。

RR 与 RC 的差异在于生成 readView 过程，RR 在一个事务中只有一个 readView，RC 会为每个查询生成新的 readView。