MySQL数据库InnoDB存储引擎多版本控制(MVCC)实现原理

 

导读:  

这个是网友++C++在群里问的一个关于MySQL的问题,本篇文章实验测试环境为MySQL 5.6.20,事务隔离级别为REPEATABLE-READ ,在演示问题前,我们先准备测试环境。准备一个测试表test以及一个存储过程循环往test表里面插入记录。

来自网易研究院的MySQL内核技术研究人何登成,把MySQL数据库InnoDB存储引擎的多版本控制(简称:MVCC)实现原理,做了深入的研究与详细的文字图表分析,方便大家理解InnoDB存储引擎实现的多版本控制技术(简称:MVCC)。

 

基本知识

假设对于多版本控制(MVCC)的基础知识,有所了解。MySQL数据库InnoDB存储引擎为了实现多版本的一致性读,采用的是基于回滚段的协议。

CREATE TABLE test

(

  `id` int(11) primary key not null,

  `name` char(255) 

) ENGINE=InnoDB DEFAULT CHARSET=utf8 COLLATE=utf8_bin;

 

 

delimiter &&

drop procedure if exists prc_insert;

 

create procedure prc_insert(in  cnt int)

begin

declare i int;

set i=1;

while i < cnt do

    insert into test(id, name) select i,  CONCAT('name',i) from dual;

    

    set i = i+1;

 

end while;

end &&

 

delimiter ;

行结构

MySQL数据库InnoDB存储引擎表数据的组织方式为主键聚簇索引。由于采用索引组织表结构,记录的ROWID是可变的(索引页分裂的时 候,Structure Modification Operation,SMO),因此二级索引中采用的是(索引键值, 主键键值)的组合来唯一确定一条记录。

无论是聚簇索引,还是二级索引,其每条记录都包含了一个DELETED BIT位,用于标识该记录是否是删除记录。除此之外,聚簇索引记录还有两个系统列:DATA_TRX_ID,DATA_ROLL_PTR。DATA _TRX_ID表示产生当前记录项的事务ID;DATA _ROLL_PTR指向当前记录项的undo信息。

聚簇索引行结构(与多版本一致读有关的部分,DELETED BIT省略):

金沙官网线上 1

二级索引行结构:

金沙官网线上 2

从聚簇索引行结构,与二级索引行结构可以看出,聚簇索引中包含版本信息(事务号+回滚指针),二级索引不包含版本信息,二级索引项的可见性如何判断?下面将会给出。

 

 

Read View

InnoDB存储引擎默认的隔离级别为Repeatable Read (RR),可重复读。InnoDB存储引擎在开始一个RR读之前,会创建一个Read View。Read View用于判断一条记录的可见性。Read View定义在read0read.h文件中,其中最主要的与可见性相关的属性如下:

?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
    dulint    low_limit_id;    /* 事务号 >= low_limit_id的记录,对于当前Read View都是不可见的 */
 
    dulint    up_limit_id;    /* 事务号 < up_limit_id ,对于当前Read View都是可见的 */
 
    ulint    n_trx_ids;    /* Number of cells in the trx_ids array */
 
    dulint*    trx_ids;    /* Additional trx ids which the read should
 
                not see: typically, these are the active
 
                transactions at the time when the read is
 
                serialized, except the reading transaction
 
                itself; the trx ids in this array are in a
 
                descending order */
 
dulint    creator_trx_id;    /* trx id of creating transaction, or
 
                (0, 0) used in purge */

简单来说,Read View记录读开始时,所有的活动事务,这些事务所做的修改对于Read View是不可见的。除此之外,所有其他的小于创建Read View的事务号的所有记录均可见。可见包括两层含义:

  • 记录可见,且Deleted bit = 0;当前记录是可见的有效记录。

  • 记录可见,且Deleted bit = 1;当前记录是可见的删除记录。此记录在本事务开始之前,已经删除。

 

在线程ID为14的会话中,开启事务,然后执行查询test的SQL语句

测试方法:

?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
create table and index
create table test (id int primary key, comment char(50)) engine=InnoDB;
create index test_idx on test(comment);
 
Insert
insert into test values(1, ‘aaa’);
insert into test values(2, ‘bbb’);
 
update primary key
update test set id = 9 where id = 1;
 
update non-primary key with different value
update test set comment = ‘ccc’ where id = 9;
 
update non-primary key with same value
update test set comment = ‘bbb’ where id = 2 and comment = ‘bbb’;

–read隔离级别

repeatable read(RR)

 

 

测试结果

 

mysql> select connection_id() from dual;

+-----------------+

| connection_id() |

+-----------------+

|              14 |

+-----------------+

1 row in set (0.00 sec)

 

mysql> start transaction;

Query OK, 0 rows affected (0.00 sec)

 

mysql> select * from test;

update primary key

代码调用流程:

?

1
ha_innobase::update_row -> row_update_for_mysql -> row_upd_step -> row_upd -> row_upd_clust_step -> row_upd_clust_rec_by_insert -> btr_cur_del_mark_set_clust_rec -> row_ins_index_entry

简单来说,就是将cluster index的旧记录标记位删除;插入一条新纪录。该语句执行完之后,数据结构如下:

金沙官网线上 3

老版本仍旧存储在聚簇索引之中,其DATA_TRX_ID被设置为1811,Deleted bit设置为1,undo中记录了前镜像的事务id = 1809。新版本DATA_TRX_ID也为1811。通过此图,还可以发现,虽然新老版本是一条记录,但是在聚簇索引中是通过两条记录来标识的。同时, 由于更新了主键,二级索引也需要做相应的更新(二级索引中包含主键项)。

 

 

update non-primary key(diff value)

更新comment字段,代码调用流程与上面有部分不同,可以自行跟踪,此处省略。更新操作执行完之后,索引结构变更如下:

金沙官网线上 4

从上图可见,更新二级索引的键值时,聚簇索引本身并不会产生新的记录项,而是将旧版本信息记录在undo之中。与此同时,二级索引将会产生 新的索引项,其PK值保持不变,指向聚簇索引的同一条记录。细心的读者可能会发现,二级索引页面中有一个MAX_TRX_ID,此值记录的是更新二级索引 页面的最大事务ID。通过MAX_TRX_ID的过滤,INNODB能够实现大部分的辅助索引覆盖性扫描(仅仅扫描辅助索引,不需要回聚簇索引)。具体过 滤方法,将在后面的内容中给出。

 

 

update non-primary key(same value)

最后一个测试用例,是更新comment项为同样的值。在我的测试中,更新之后的索引结构如下:

金沙官网线上 5

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

 

然后在线程ID为12的会话中,循环往表test里面插入1000000记录

总结

  1. 无论是聚簇索引,还是二级索引,只要其键值更新,就会产生新版本。将老版本数据deleted bti设置为1;同时插入新版本。

  2. 对于聚簇索引,如果更新操作没有更新primary key,那么更新不会产生新版本,而是在原有版本上进行更新,老版本进入undo表空间,通过记录上的undo指针进行回滚。

  3. 对于二级索引,如果更新操作没有更新其键值,那么二级索引记录保持不变。

  4. 对于二级索引,更新操作无论更新primary key,或者是二级索引键值,都会导致二级索引产生新版本数据。

  5. 聚簇索引设置记录deleted bit时,会同时更新DATA_TRX_ID列。老版本DATA_TRX_ID进入undo表空间;二级索引设置deleted bit时,不写入undo。

 

 

可见性判断

 

mysql> select connection_id() from dual;

+-----------------+

| connection_id() |

+-----------------+

|              12 |

+-----------------+

1 row in set (0.00 sec)

 

mysql> call prc_insert(1000000);

Query OK, 1 row affected (8 min 32.11 sec)

主键查找

select * from test where id = 1;

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

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

  • 针对测试1,如果up_limit_id,low_limit_id都无法判断可见性,那么遍历read_view中的trx_ids,依次对比事务id,如果在DATA_TRX_ID在trx_ids数组中,则不可见(更新未提交)。

     

select * from test where id = 9;

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

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

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

     

select * from test where id > 0;

  • 针对测试1,索引中, 满足条件的同一记录,有两个版本(版本1,delete 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,记录DATA_TRX_ID,记录DATA_ROLL_PTR指针共同判断。

  2. read_view用于判断当前记录是否可见(判断DATA_TRX_ID)。DATA_ROLL_PTR用于将当前记录回滚到前一版本。

 

 

非主键查找

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)。(row_select_for_mysql -> lock_sec_rec_cons_read_sees)

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

    ?

    1
    2
    3
    4
    5
    6
    7
        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. 二级索引中的项,需要与聚簇索引中的可见性进行比较,保证聚簇索引中的可见项,与二级索引中的项数据一致。

 

在执行循环插入的这段时间里(SQL执行需要几分钟时间),我们在线程ID 为14的会话中反复执行select * from test这个SQL语句,你会发现该SQL的执行时间变长。那么引起SQL语句执行时间变长的原因是什么呢? 如何解释得通呢?

疑问

  1. http://blogs.InnoDB.com/wp/2011/04/mysql-5-6-multi-threaded-purge/中, 作者提到,InnoDB存储引擎的purge操作,是通过遍历undo来实现对于标记位deleted项的回收的。如果二级索引本身标记deleted位 不记录 undo,那么这个回收操作如何完成?还是说purge是通过解析redo来完成回收的?(根据下面对于purge的流程分析,此问题已解决)

 

 

Purge流程

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一个操作生成的旧版 本完整记录。

一个完整的purge函数调用流程如下:

?

1
2
3
row_purge_step->row_purge->trx_purge_fetch_next_rec->row_purge_parse_undo_rec
->row_purge_del_mark->row_purge_remove_sec_if_poss
->row_purge_remove_clust_if_poss

总结:

  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是将记录删除。

 

金沙官网线上 6

 

刚开始讨论的时候,以为MySQL会像ORACLE那样会在UNDO的回滚段中产生大量UNDO记录,最后导致SQL语句会像ORACLE那样产生额外的一致性读,产生额外的IO,从而导致执行时间变长。 后面测试发现,其实对于MySQL而言,INSERT操作在事务提交前只对当前事务可见,因此产生的Undo日志可以在事务提交后直接删除,而此处使用是自动提交模式。用“MySQL技术内幕:InnoDB存储引擎”里面提供的脚本py_innodb_page_info.py测试验证。也是确实如此(UNDO日志的大小变化很小,时而增长,时而变小)。其实MySQL里面多版本并发控制(MVCC)的实现机制跟Oracle还是不同的。不能生搬硬套Oracle下的那套理论。

 

 

[root@DB-Server kerry]# python py_innodb_page_info.py /data/mysql/ibdata1

Total number of page: 4864:

Insert Buffer Free List: 32

Insert Buffer Bitmap: 1

System Page: 130

Transaction system Page: 1

Freshly Allocated Page: 1326

Undo Log Page: 3224

File Segment inode: 6

B-tree Node: 142

File Space Header: 2

[root@DB-Server kerry]# python py_innodb_page_info.py /data/mysql/ibdata1

Total number of page: 4864:

Insert Buffer Free List: 32

Insert Buffer Bitmap: 1

System Page: 130

Transaction system Page: 1

Freshly Allocated Page: 1326

Undo Log Page: 3223

File Segment inode: 6

B-tree Node: 143

File Space Header: 2

[root@DB-Server kerry]# python py_innodb_page_info.py /data/mysql/ibdata1

Total number of page: 4864:

Insert Buffer Free List: 32

Insert Buffer Bitmap: 1

System Page: 130

Transaction system Page: 1

Freshly Allocated Page: 1326

Undo Log Page: 3213

File Segment inode: 5

B-tree Node: 154

File Space Header: 2

[root@DB-Server kerry]# python py_innodb_page_info.py /data/mysql/ibdata1

Total number of page: 4864:

Insert Buffer Free List: 32

Insert Buffer Bitmap: 1

System Page: 130

Transaction system Page: 1

Freshly Allocated Page: 1326

Undo Log Page: 3205

File Segment inode: 5

B-tree Node: 162

File Space Header: 2

[root@DB-Server kerry]# python py_innodb_page_info.py /data/mysql/ibdata1

Total number of page: 4864:

Insert Buffer Free List: 32

Insert Buffer Bitmap: 1

System Page: 130

Transaction system Page: 2

Freshly Allocated Page: 1326

Undo Log Page: 3240

File Segment inode: 5

B-tree Node: 127

File Space Header: 1

 

其实InnoDB的多版本并发控制(MVCC),“高性能MySQL”这本书中有这么一段描述:

 

 

InnoDB的MVCC,是通过每行记录后面保存的两个隐藏的列来实现的。 这两个列一个保存了行的创建时间,一个保存行的过期时间(或删除时间),当然存储的并不是实际的时间值,而是系统版本号(System version number),每开始一个新的事务,系统版本号都会自动递增,事务开始时刻的系统版本号会作为事务的版本号,用来和查询到的每行记录的版本号进行比较。下面看一下在REPEATABLE READ隔离级别下, MVCC是如何具体操作的。

 

SELECT

 

InnoDB会根据以下两个条件检查每行的记录:

 

    a.  InnoDB只查找版本早于当前事务版本的数据行(也就是,行的系统版本号小于或等于事务的系统版本号),这样可以确保事务读取的行,要么是在事务开始前已经存在的,要么是事务自身插入或修改过的。

    b.  行的删除要么未定义,要么大于当前事务版本号。这可以确保事务读取到的行,在事务开始之前未被删除。

 

只有符合上述两个条件的记录,才能返回作为查询结果。

..............................................

 

其实至少从MySQL 5.5之后, 每一行开始额外包含三个隐藏字段,而不是二个字段(没有查证高性能MySQL主要讲述哪个MySQL版本)。

 

 

·         6字节的事务ID(DB_TRX_ID)字段: 用来标识最近一次对本行记录做修改(insert|update)的事务的标识符, 即最后一次修改(insert|update)本行记录的事务ID。

    至于delete操作,在InnoDB看来也不过是一次update操作,更新行中的一个特殊位将行表示为deleted, 并非真正删除。

 

·         7字节的回滚指针(DB_ROLL_PTR)字段: 指写入回滚段(rollback segment)的 undo log record (撤销日志记录记录)。

    如果一行记录被更新, 则 undo log record 包含 '重建该行记录被更新之前内容' 所必须的信息。

本文由金沙官网线上发布于数据库,转载请注明出处:MySQL数据库InnoDB存储引擎多版本控制(MVCC)实现原理

您可能还会对下面的文章感兴趣: