多版本并发控制及其实现

2021年8月22日 176点热度 1人点赞 0条评论

InnoDB存储引擎在可重复读的隔离级别下解决了幻读问题,实现的方式正是多版本并发控制。多版本并发控制对读这个操作进行了优化,对写操作仍然是通过加锁来保证隔离性的,这样解决了读写冲突的问题。

多版本并发控制(MVCC) 是通过保存数据在某个时间点的快照来实现并发控制的。也就是说,不管事务执行多长时间,事务内部看到的数据是不受其它事务影响的,根据事务开始的时间不同,每个事务对同一张表,同一时刻看到的数据可能是不一样的。

简单来说,多版本并发控制 的思想就是保存数据的历史版本,通过对数据行的多个版本管理来实现数据库的并发控制。这样我们就可以通过比较版本号决定数据是否显示出来,读取数据的时候不需要加锁也可以保证事务的隔离效果。

如何存储记录的多个版本

事务版本号

每开启一个事务,我们都会从数据库中获得一个事务 ID(也就是事务版本号),这个事务 ID 是自增长的,通过 ID 大小,我们就可以判断事务的时间顺序。

版本号的更新:

插入(INSERT)

InnoDB为新插入的每一行保存当前系统版本号作为行版本号。

删除(DELETE)

InnoDB为删除的每一行保存当前系统版本号作为行删除标识。
删除在内部被视为更新,行中的一个特殊位会被设置为已删除。

更新(UPDATE)

InnoDB为插入一行新记录,保存当前系统版本号作为行版本号,同时保存当前系统版本号到原来的行作为行删除标识。

行记录的隐藏列

InnoDB 的叶子段存储了数据页,数据页中保存了行记录,而在行记录中有一些重要的隐藏字段:

  • DB_ROW_ID:6-byte,随着新行插入而单调递增的行ID,用来生成默认聚簇索引。当表没有主键或唯一非空索引时,Innodb就会使用这个行ID自动产生聚簇索引。如果表有主键或唯一非空索引,聚簇索引就不会包含这个行ID了。
  • DB_TRX_ID:6-byte,表示最近一次对本记录行作修改(insert | update)的事务ID。至于delete操作,InnoDB认为是一个update操作,不过会更新一个另外的删除位,将行表示为deleted。并非真正删除。
  • DB_ROLL_PTR:7-byte,回滚指针,也就是指向这个记录的 undo Log 信息。

undo log

InnoDB 将行记录快照保存在了 undo Log 里,我们可以在回滚段中找到它们,如下图所示:

从图中能看到回滚指针将数据行的所有快照记录都通过链表的结构串联了起来,每个快照的记录都保存了当时的 db_trx_id,也是那个时间点操作这个数据的事务 ID。这样如果我们想要找历史快照,就可以通过遍历回滚指针的方式进行查找。

Read View

Read View(读视图)就是一个快照,主要是用来做可见性判断的,里面保存了“对本事务不可见的其他活跃事务”。

Read View里面主要需要了解几个重要的字段:

  1. low_limit_id:目前出现过的最大的事务ID+1,即下一个将被分配的事务ID
  2. up_limit_id:活跃事务列表trx_ids中最小的事务ID,如果trx_ids为空,则up_limit_id low_limit_id

因为trx_ids中的活跃事务号是逆序的,所以最后一个为最小活跃事务ID。

  1. trx_ids:Read View创建时其他未提交的活跃事务ID列表。意思就是创建Read View时,将当前未提交事务ID记录下来,后续即使它们修改了记录行的值,对于当前事务也是不可见的。

注意:Read View中trx_ids的活跃事务,不包括当前事务自己和已提交的事务(正在内存中)。

  1. creator_trx_id当前创建事务的ID,是一个递增的编号。

可见性比较算法

在Innodb中,创建一个新事务后,执行第一个select语句的时候,Innodb会创建一个快照(read view),快照中会保存系统当前不应该被本事务看到的其他活跃事务ID列表(即trx_ids)。当用户在这个事务中要读取某个记录行的时候,Innodb会将该记录行的DB_TRX_ID与该Read View中的一些变量进行比较,判断是否满足可见性条件。

假设当前事务要读取某一个记录行,该记录行的DB_TRX_ID(即最新修改该行的事务ID)为trx_id,Read View的活跃事务列表trx_ids中最早的事务ID为up_limit_id,将在生成这个Read Vew时系统出现过的最大的事务ID+1记为low_limit_id(即还未分配的事务ID)。

具体算法如下:

  • 如果trx_id < up_limit_id,说明“最新修改该行的事务”在“当前事务”创建快照之前就提交了,所以该记录行的值对当前事务是可见的。
  • 如果trx_id >= low_limit_id,说明“最新修改该行的事务”在“当前事务”创建快照之后才修改该行,所以该记录行的值对当前事务不可见。
  • 如果up_limit_id <= trx_id < low_limit_id,说明最新修改该行的事务”在“当前事务”创建快照的时候可能处于“活动状态”或者“已提交状态”;所以就要对活跃事务列表trx_ids进行查找(源码中是用的二分查找,因为是有序的):
    • 如果在活跃事务列表trx_ids中能找到 ID 为 trx_id 的事务,那么①在“当前事务”创建快照前,“该记录行的值”被“ID为trx_id的事务”修改了,但没有提交;或者②在“当前事务”创建快照后,“该记录行的值”被“ID为trx_id的事务”修改了(不管有无提交);这些情况下,这个记录行的值对当前事务都是不可见的。
    • 在活跃事务列表中找不到,则表明“ID为trx_id的事务”在修改“该记录行的值”后,在“当前事务”创建快照前就已经提交了,所以记录行对当前事务可见,

在Innodb中的Repeatable Read级别, 只有事务在begin之后,执行第一条select(读操作)时, 才会创建一个快照(read view),将当前系统中活跃的其他事务记录起来;并且事务之后都是使用的这个快照,不会重新创建,直到事务结束。

对于一条记录,只有经过可见性算法的验证后,如果对当前事务可见,才能作为查询结果返回。

参考资料

https://segmentfault.com/a/1190000037557620

https://zhuanlan.zhihu.com/p/371696661

agedcat_xuanzai

这个人很懒,什么都没留下

文章评论