MySQL InnoDB 存储引擎的 MVCC

转载自：http://hedengcheng.com/?p=286

简介、关于 MVCC

MVCC，即多版本并发控制，它是数据库系统中常用的一种并发访问控制的方法，但并没有一个统一的实现标准，所以不同的数据库、不同的存储引擎的实现都是不同的。它主要提供了两大功能：（1）读不阻塞写，写不阻塞读；（2）提供一致性读，也叫快照读的功能。
MySQL 的 InnoDB 存储引擎、Oracle、PostgreSQL 等都实现了 MVCC。下面主要说一下 MySQL 的 InnoDB 存储引擎的 MVCC 实现原理。

在 MVCC 的场景下，因为涉及到数据记录的读取更新，所以以聚簇索引和非聚簇索引角度来分析，但实际上用聚簇索引和二级索引这种角度来描述会更通顺一些。

一、行结构

InnoDB 表数据的组织方式为聚簇索引，数据记录和索引记录存储在一起，由于记录的主键值是可变的，因此二级索引中采用的是（索引键值 + 主键键值）的组合来唯一确定一条记录。

为了实现 MVCC，无论是聚簇索引还是二级索引，每条行记录的记录头都包含了一个 DELETED BIT 位，用于标识对应行记录是否是删除记录。除此之外，聚簇索引记录还有两个系统自动添加的隐藏列：DB_TRX_ID，DB_ROLL_PTR。DB_TRX_ID 表示最后修改对应记录的的事务 ID（如果是新记录就是 insert 它的事务 ID）；DB_ROLL_PTR 指向对应记录的 undo log。
DB_ROW_ID：6byte
DB_TRX_ID：6byte，InnoDB 内部维护了一个计数器用来生成递增的事务 ID 值
DB_ROLL_PTR：7byte

• 聚簇索引行记录结构（与多版本一致读有关的部分，DELETED BIT 省略）：
  

  聚簇索引行记录结构.png

• 二级索引行记录结构：

  
  二级索引行记录结构.png
  

  从聚簇索引与二级索引行结构可以看出，聚簇索引中包含记录的版本信息（事务 ID + 回滚指针），二级索引则不包含，那么根据二级索引查询时的可见性如何判断？

二、Read View

InnoDB 默认的隔离级别为 RR。InnoDB 在开始一个 RR 读之前，会创建一个 Read View。Read View 用于判断一条记录的可见性。Read View 主要的与可见性相关的属性如下：

m_low_limit_id;    // 表示下一个要创建的事务 ID 值，也就是当前所有活跃事务中最大的事务 ID值 + 1，事务 ID >= m_low_limit_id 的记录，对于当前 Read View 都是不可见的
m_up_limit_id;    // 表示当前所有活跃事务中最小的事务 ID，事务 ID < m_up_limit_id 的记录，对于当前 Read View 都是可见的

Read View 判断出的记录可见包括两层含义：

• 记录可见，且 DELETED BIT = 0，当前记录是可见的未删除记录，会返回该记录。
• 记录可见，且 DELETED BIT= 1，当前记录是可见的删除记录，不会返回该记录。

三、undo log

undo log 分为两类: insert undo log 和 update undo log：

• insert undo log : 事务对insert新记录时产生的 undo log，只在事务回滚时需要, 并且在事务提交后就可以立即丢弃。
• update undo log : 事务对记录进行 update/delete 操作时产生的 undo log, 不仅在事务回滚时需要，快照读也需要，所以不能随便删除，只有当数据库所使用的快照中不涉及该日志记录，对应的回滚日志才会被 purge 线程删除。

四、测试用例

1、准备工作

// 1. 创建表和索引
create table test (id int primary key, 
                   comment char(50)
                   ) engine=InnoDB;
create index test_idx on test(comment); // comment 列创建二级索引

// 2. insert 记录
insert into test values(1, ‘aaa’);
insert into test values(2, ‘bbb’);

2、测试结果

2.1、update primary key 更新主键

// 更新主键 id = 1 的记录的主键为 9
update test set id = 9 where id = 1;

执行后的索引结构：

执行后的索引结构

会将聚簇索引的旧记录（id = 1）标记为删除 DELETED BIT = 1，并插入一条新记录（id = 9）。
老版本记录（id = 1）仍旧存储在聚簇索引之中，其 DB_TRX_ID 被设置为1811，DELETED BIT 被设置为1，undo log 中记录了前一次事务的 DB_TRX_ID= 1809。新版本记录（id = 9） DB_TRX_ID 也为1811。通过此图，还可以发现，虽然新老版本是一条记录，但是在聚簇索引中是通过两条记录来标识的。同时，由于更新了主键，二级索引也需要做相应的更新(因为二级索引记录中包含主键值，具体见下图，就是把二级索引中主键值 = 1 的索引记录设置为 DELETED BIT= 1，新增一条主键值 = 9 的索引记录)。

2.2、update non-primary key with different value 使用不同值更新二级索引值

update test set comment = ‘ccc’ where id = 9; // 更新二级索引 comment 字段值

执行后的索引结构：

执行后的索引结构
从上图可见，更新二级索引的键值时，聚簇索引本身并不会产生新的记录项，而是将旧版本信息记录在 undo 之中。与此同时，二级索引将会产生新的索引项，其对应的主键索引值保持不变，指向聚簇索引的同一条记录。二级索引页面中有一个 MAX_TRX_ID，此值记录的是更新二级索引页面的最大事务ID。通过 MAX_TRX_ID 的过滤，INNODB 能够实现大部分的辅助索引覆盖性扫描（仅仅扫描辅助索引，不需要回聚簇索引）。
延伸：如果只更新没有建立任何索引的字段，则只在聚簇索引的undo 中记录一次旧版即可。

2.3、update non-primary key with same value 使用相同值更新二级索引值

update test set comment = ‘bbb’ where id = 2 and comment = ‘bbb’; // 更新二级索引 comment 字段为相同值

执行后的索引结构：

执行后的索引结构

聚簇索引仍旧会更新，但是二级索引保持不变。

2.4、总结

分为 会更新索引值 和 不会更新索引值 两种情况：

• 会更新索引值
  如果是聚簇索引值修改了，聚簇索引的当前版本就会成为老版本记录，会先将这个老版本记录拷贝一份加入到 undo log，并设置 DB_ROLL_PTR 指向这个最新加入的老版本记录拷贝，接着会将老版本记录的 DB_TRX_ID 更新为最新修改的事务 ID，并设置 DELETED BIT= 1，最后根据老版本记录的其它字段值生成一条新版本记录并插入，它的聚簇索引值就是修改后的值，DB_TRX_ID 就是最新修改的事务 ID；
  如果是二级索引值修改了，二级索引的当前版本就会成为老版本记录，会设置老版本记录的 DELETED BIT = 1，然后根据老版本记录的其它字段值生成一条新版本记录并插入，它的二级索引值就是修改后的值，同时更新二级索引页面的 MAX_TRX_ID 为最新修改的事务 ID，但老版本记录是不会加入 undo log 的，因为二级索引没有 undo log。
  特殊情况：对于二级索引，更新操作无论更新主键索引值还是二级索引值，都会导致对应的二级索引生成新版本记录。

• 不会更新索引值
  对于聚簇索引，如果更新操作没有更新主键索引值，会先将当前版本记录拷贝一份加入到 undo log，并设置 DB_ROLL_PTR 指向这个最新加入的当前版本记录拷贝，接着会根据要修改的字段值直接在当前版本记录上进行修改，
  并将它的 DB_TRX_ID 更新为最新修改的事务 ID，但不会创建新版本记录。
  对于二级索引，如果更新操作没有更新二级索引值，那么二级索引记录保持不变，什么都不做（但如果是使用相同二级索引值更新的情况，会更新二级索引页面的 MAX_TRX_ID 为最新的事务 ID）。
  特殊情况： 如果更新记录使用的是与当前聚簇索引中记录的字段值相同的值，那么聚簇索引同样会按照更新其它字段值的来处理。

五、可见性判断、

关键点：通过 read view 判断记录是否可见

• rr 隔离级别下，在每个事务开始的时候，会将当前所有的活跃事务拷贝到 read view 中，read view 可以理解为一个列表，因此能够避免不可重复读问题。
• rc 隔离级别下，在事务中的每个快照读开始时，会将当前所有的活跃事务拷贝到 read view 中，因此能够避免脏读，但可能产生不可重复读问题。

• 可见性判断逻辑

  
  判断记录的可见性.png

注意严格意义上这张图里的 tid0 > tmax 应该是 tid0 >= tmax。

// 判断 DB_TRX_ID = trx_id 的记录对当前事务是否可见 
bool changes_visible(trx_id_t id, const table_name_t& name){

    // 如果 trx_id < read view.m_up_limit_id 或者 trx_id 就是当前事务 id，则返回可见
    if (id < m_up_limit_id || id == m_creator_trx_id) {
        return(true);
    }

    check_trx_id_sanity(id, name);

    // 如果 trx_id >= read view.m_low_limit_id 则返回不可见
    if (id >= m_low_limit_id) {
        return(false);
    } else if (m_ids.empty()) {
        return(true);
    }

    const ids_t::value_type*    p = m_ids.data();

    // 如果 read view.m_up_limit_id =< trx_id < read view.m_low_limit_id，用二分查找判断 trx_id 是否在 read view
    // 集合中，在的话说明是活跃事务就返回不可见，不在的话说明是已提交的事务就返回可见
    return(!std::binary_search(p, p + m_ids.size(), id));
}

1、主键查找

select * from test where id = 1;

• 针对测试1，如果 1811(DB_TRX_ID) < read_view.up_limit_id，证明被标记为删除的记录1可见。删除可见 -> 无记录返回。

• 针对测试1，如果 1811(DB_TRX_ID) >= read_view.low_limit_id，证明被标记为删除的记录1不可见，通过 DB_ROLL_PTR 回滚记录，得到 DB_TRX_ID= 1809。如果1809可见，则返回记录(1，aaa)；否则无记录返回。

• 针对测试1，如果 up_limit_id，low_limit_id都无法判断可见性，通过二分查找判断 DB_TRX_ID 是否在 read view 列表中，在则不可见(更新未提交)，不在则可见。

select * from test where id = 9;

• 针对测试2，如果1816可见，返回(9, ccc)。

• 针对测试2，如果1816不可见，通过 DB_ROLL_PTR 回滚到1811，如果1811可见，返回(9, aaa)。

• 针对测试2，如果1811不可见，无结果返回。

select * from test where id > 0;

• 针对测试1，聚簇索引中满足条件的同一记录有两个版本(版本1，DELETED BIT=1)。那么是否会一条记录返回两次呢？必定不会，这是因为 pk = 1 的可见性与 pk = 9 的可见性是一致的，同时 pk = 1 是标记了 DELETED BIT 的版本。如果事务ID = 1811可见。那么pk = 1 delete可见，无记录返回，pk = 9返回记录；如果1811不可见，回滚到1809可见，那么pk = 1返回记录，pk = 9回滚后无记录。

• 总结：

1. 通过主键查找记录，需要配合read_view，记录DB_TRX_ID，记录DB_ROLL_PTR指针共同判断。
2. read_view用于判断当前记录是否可见(判断DB_TRX_ID)。DB_ROLL_PTR用于将当前记录回滚到前一版本。

2、非主键查找

select comment from test where comment > ‘ ‘;

• 针对测试2，二级索引，当前页面的最大更新事务MAX_TRX_ID = 1816。如果MAX_TRX_ID < read_view.up_limit_id，当前页面所有数据均可见，本页面可以进行索引覆盖性扫描。丢弃所有 DELETED BIT = 1的记录，返回 DELETED BIT = 0 的记录；此时返回 (ccc)。

• 针对测试2，二级索引，如果当前页面不能满足MAX_TRX_ID < read_view.up_limit_id，说明当前页面无法进行索引覆盖性扫描，此时需要针对每一项，到聚簇索引中判断可见性。回到测试2，二级索引中有两项pk = 9 (一项 DELETED BIT = 1，另一个为0)，对应的聚簇索引中只有一项pk= 9。如何保证通过二级索引过来的同一记录的多个版本，在聚簇索引中最多只能被返回一次？如果当前事务id 1811可见。二级索引pk = 9的记录(两项)，通过聚簇索引的undo，都定位到了同一记录项。此时，InnoDB通过以下的一个表达式，来保证来自二级索引，指向同一聚簇索引记录的多个版本项，有且最多仅有一个版本将会返回数据：

if(clust_rec && 
    (old_vers || rec_get_deleted_flag(rec, dict_table_is_comp(sec_index->table))) && 
    !row_sel_sec_rec_is_for_clust_rec(rec, sec_index, clust_rec, clust_index))

满足if判断的所有聚簇索引记录，都直接丢弃，以上判断的逻辑如下：

1. 需要回聚簇索引扫描，并且获得记录
2. 聚簇索引记录为回滚版本，或者二级索引中的记录为删除版本
3. 聚簇索引项，与二级索引项，其键值并不相等

为什么满足if判断，就可以直接丢弃数据？用白话来说，就是我们通过二级索引记录，定位聚簇索引记录，定位之后，还需要再次检查聚簇索引记录是否仍旧是我在二级索引中看到的记录。如果不是，则直接丢弃；如果是，则返回。

根据此条件，结合查询与测试2中的索引结构。可见版本为事务1811.二级索引中的两项pk = 9都能通过聚簇索引回滚到1811版本。但是，二级索引记录(ccc,9)与聚簇索引回滚后的版本(aaa,9)不一致，直接丢弃。只有二级索引记录(aaa,9)保持一致，直接返回。

总结：

1. 二级索引的多版本可见性判断，需要通过聚簇索引完成。

2. 二级索引页面中保存了MAX_TRX_ID，可以快速判断当前页面中，是否所有项均可见，可以实现二级索引页面级别的索引覆盖扫描。一般而言，此判断是满足条件的，保证了索引覆盖扫描 (index only scan)的高效性。

3. 二级索引中的项，需要与聚簇索引中的可见性进行比较，保证聚簇索引中的可见项，与二级索引中的项数据一致。

六、Purge 流程

• 相关问题：
  InnoDB的purge操作，是通过遍历undo来实现对于标记位deleted项的回收的。如果二级索引本身标记deleted位不记录undo，那么这个回收操作如何完成？还是说purge是通过解析redo来完成回收的？

• Purge功能：
  InnoDB由于要支持多版本协议，因此无论是更新，删除，都只是设置记录上的 DELETED BIT 标记位，而不是真正的删除记录。后续这些记录的真正删除，是通过Purge后台进程实现的。Purge进程定期扫描InnoDB的undo，按照先读老undo，再读新undo的顺序，读取每条undo record。对于每一条undo record，判断其对应的记录是否可以被purge(purge进程有自己的read view，等同于进程开始时最老的活动事务之前的view，保证purge的数据，一定是不可见数据，对任何人来说)，如果可以purge，则构造完整记录(row_purge_parse_undo_rec)。然后按照先purge二级索引，最后purge聚簇索引的顺序，purge一个操作生成的旧版本完整记录。

• 总结：

1. purge是通过遍历undo实现的。
2. purge的粒度是一条记录上的一个操作。如果一条记录被update了3次，产生3个old版本，均可purge。那么purge读取undo，对于每一个操作，都会调用一次purge。一个purge删除一个操作产生的old版本(按照操作从老到新的顺序)。
3. purge按照先二级索引，最后聚簇索引的顺序进行。
4. purge二级索引，通过构造出的索引项进行查找定位。不能直接针对某个二级页面进行，因为不知道记录的存放page。
5. 对于二级索引设置 DELETED BIT 为不需要记录undo，因为purge是根据聚簇索引undo实现。因此二级索引 DELETED BIT 被设置为1的项，没有记录undo，仍旧可以被purge。
6. purge是一个耗时的操作。二级索引的purge，需要search_path定位数据，相当于每个二级索引，都做了一次index unique scan。
7. 一次delete操作，IO翻番。第一次IO是将记录的 DELETED BIT 设置为1；第二次的IO是将记录删除。

七、一些其它点

• 当前读
  select ... lock in share mode
select ... for update
update
insert
delete
  这些操作都是当前读，它们读取的是数据记录的最新版本，读取时还要保证其它并发事务不能修改当前记录，会对读取的记录进行加 S/X 锁。所以，当前读可以看做是锁的具体实现。

• 快照读
  普通的 select 操作是快照读，即不加锁的非阻塞读，它在很多情况下，可以提高并发读写的性能，避免有加锁操作，降低了开销。快照读可以看做是 MVCC 的具体实现，那么多版本实现可能导致快照读读到的数据记录并不一定是最新版本。

• MVCC 只能 RC 和 RR 两个隔离级别下工作，其它两个隔离级别 MVCC 不兼容, 因为 RU 隔离级别下总是读取最新的行记录，而不一定是对当前事务可见的记录版本，SERIALIZABLE 隔离级别则自动会对所有读取的行记录加 S 锁，也就是退化为当前读。

• MVCC 可以在部分程度上解决幻读，并不能完全解决，在特定情况下还是会出现幻读的，这种特定情况一定在事务自身的写操作发生。
  最典型的一种场景：

id	age	name
1	20	xiaoming
2	22	xiaohong
3	25	xiaowang

事务 A	事务 B
select * from table where age < 23;
	insert into table (21, "xiaopeng") ;
update table set name = 'xiaogang' where age = 21;
select * from table where age < 23;

执行时序：
事务 A 第一次查询返回 id = 1、2 共两条记录；
事务 B 插入一条 age = 21 的记录；
事务 A 使用 update 更新了事务 B 刚刚插入的 age = 21 的记录，因为事务 A 使用的 update 是当前读，会读到最新的记录，即使该记录是其它活跃事务新增的；
事务 A 第二次查询返回 id = 1、2、4 共三条记录；
因此发生了幻读问题。

• MVCC 好处
  提高数据库并发读写的性能，当有并发读写操作时，使用快照读可以在读操作时不用阻塞其它事务的写操作，写操作时也可以用快照读不用阻塞其它事务的读操作。
  还可以解决 RU 的脏读，RC 的 不可重复读，并在部分程度上解决 RR 的幻读问题。