数据库的隔离级别与2PL/MVCC算法原理

2019/03/24 Middleware

数据库隔离级别及底层实现原理,偏算法原理,不深入各类数据库细节

数据库隔离级别

一般数据库都有四种隔离级别,Read UnCommited(RU), Read Commited(RC), Repeatable Read(RR), Serializable(S) 在不同的隔离级别下可能存在不同的错误: 脏读, 读到另外一个事务还未提交的数据;不可重复读,在同一个事务读取一个数据多次,读到的值不唯一;幻读:同一个数据读取多行多次,读到的行数不唯一。

隔离级别 脏读 不可重复读 幻读
RU Y Y Y
RC N Y Y
RR N N Y
S N N N

不同数据库可能会提供这四种隔离级别以外的隔离级别,比如Snapshot Isolation,Read Snapshot Isolation等,本文主要介绍数据库隔离级别的底层原理,对这些细节不进行深入。

数据库实现隔离级别的常见方法有两种:两阶段加锁(2-Phase-Lock),多版本并发控制(Multiple-Version-Concurrency-Control)。

2PL

什么是2PL

对于大部分开发人员来说,说到并发控制最先想到的就是锁。2PL就是通过锁进行数据库并发控制的一种方法。为什么叫两阶段加锁,我们先看一下下边这个例子会有什么问题:

T1在第一次 Unlock(A) 后,T2 成功对 A 加锁,读取到了 T1 已经写入的数据,但是这时 T1 尚未提交,也就是发生了脏读。 RU 隔离级别下可以采用这种加锁方式,但是显然不满足RC隔离级别。

2PL就是对加锁的方式进行了限制,将事务加锁分为两个阶段,第一个阶段只能进行加锁,第二个阶段只能进行解锁。像上图这个例子,T1 在第一次对 A 解锁后又重新对 A 加锁就是不满足两阶段加锁的。满足两阶段加锁的方式如下:

这样 T2 获取到 A 的时候,一定是 T1 不会再对 A 进行数据更新了,但是一种特殊情况是,T1 在 解锁 A 之后,提交之前发生了异常,提交失败,这时 T2 读取到的还是 T1 未提交的数据。为了避免这种情况,有两种解决方案:

  • 级联终止: T1 发生异常后,数据库找出读取了 A 数据的事务,将所有的事务一起终止。这种情况下,一个事务失败,引发级联效应,引起后边一系列事务的回滚。
  • S2PL:严格的两阶段加锁(Strict-2-Phase-Lock), 类似于2PL,也分为两个阶段,第一阶段只能加锁,第二阶段只能解锁,但是解锁只能发生在事务结束的时候同时解锁。几幅图对比一下 2PL 和 S2PL 的区别。

2PL:

S2PL:

锁数量随时间的关系

2PL

S2PL

S2PL虽然避免了级联终止的发生,但是降低了事务的并发度,级联终止的在异常发生时,回滚代价比较大,但是并发度也比较高,所以需要在两种方案下进行权衡。

避免死锁

对于加锁算法,避免死锁是无法逃避的问题,避免死锁一般从两个方面入手:死锁检测、死锁预防

  • 死锁检测:为相互等待的事务之间维护一张 graph, 检测 graph 中 是否有环。如果检测到优化,则根据一定的策略选择终止一个事务,打破循环等待。

  • 死锁预防:按照一定顺序进行加锁,锁超时则终止等。

减小锁的粒度

为了提高事务并发度,一种重要的方法就是减小锁的粒度,按照层级分为库锁,表锁,行锁等。按照读写分为读锁和写锁。于是抽象出四种锁的类型:

  • S:Shared Lock,共享锁,是一种读锁,不会更新数据
  • X:Exclusive Lock,排它锁,是一种写锁,会更新数据
  • IS:Intented Shared Lock, 是 S 锁的分层锁,表示对自己的子节点加 S 锁
  • IX:Intented Exclusive Lock, 是 X 锁的分层所,表示对自己的子节点加 X 锁

四种锁的互斥性, Y表示同时获取,N表示不可以同时获取

  X S IX IS
X N N N N
S N Y N Y
IX N N Y Y
IS N Y Y Y

对一个节点加 S 锁相当于对所有子节点都加了 S 锁; 对一个节点加了 X 锁,相当于对所有子节点加了 X 锁。对一个节点加 IS 锁就是对自己某一个子节点加了 S 锁;对一个节点加 IX 锁就是对某一个子节点加了 X 锁。有了这样一个认识,很容易理解上述表。

加锁算法与隔离级别

隔离级别 加锁算法
RU 不需要 2PL,某次访问变量的时候加锁,访问完立即放锁即可
RC 2PL + 级联终止 或者 S2PL
RR 2PL + 级联终止 / S2PL 天然满足RR
S 需要层级锁实现

MVCC

什么是MVCC

MVCC 是一种为每个物理值维护多个逻辑值的并发控制方法,每个逻辑值都维护一个有效时间段,根据有效时间段判定一个事务可以读取到哪个值。所以 MVCC 需要按照时间顺序, 给每个事务分配一个 XID,下边例子可以假设 XID 为时间戳。

与 2PL 相比,由于 MVCC 每次更新都写入一个新的版本,所以读和写互相不会阻塞,但是写写还是会互相阻塞。所以,MVCC 不需要 S 和 IS 锁, 但是仍然需要 X 和 IX 锁。

MVCC 一个简单的例子

假设初始数据库如下,Version 代表版本;Value 代表版本对应的值;Begin代表有效时间段的开始时间;End代表有效时间段的结尾时间,其中~代表正无穷;IsCommited代表当前值的事务是否已经提交。

Version Value Begin End IsCommited
0 123 0 ~ True

现在有如下两个事务:

该例子中,以事务开始那一刻的时间戳作为事务的时间戳。

  • T1 第一次读取时,查找已经提交了的事务中,1 位于哪个Value的[Begin, End)区间内,读到Value 为 123
  • T2 对 A 进行了写入操作,则数据库增加一个新的版本,并更新 0 版本的 End 值为自己的开始时间,变为:
Version Value Begin End IsCommited
0 123 0 2 True
1 456 2 ~ False
  • T1 第二次读取时,依然查找已提交的事务中,1 位于哪个Value的[Begin, End)区间内,由于Version 1 尚未提交,所以读到的值仍然是 123。

我们发现这个例子已经满足了 RR 隔离级别,这其实是因为有两个隐含条件包含其中:

  1. 把事务起始的时间作为事务的时间戳

    这意味着多次读取,他们的时间戳是一致的,所以读取到的值也是一样的。这种情况一般称为 Snapshot Isolation。如果我们每次读取的时候,以读取操作那一刻的时间戳去查找数据库版本,这种情况下显然不满足 RR 了,因为两次读取中间可能已经有事务提交了新的版本,这种情况一般称为 Read Snapshot Isolation。

  2. 查找的是已经提交的版本

    这条限制满足了 RC, 如果我们查找的时候忽略 IsCommited 标志,那隔离级别就变为 RU 了。

MVCC 一个稍微复杂一点的例子

上文提到,MVCC只是消除了 S 锁, 并没有消除 X 锁,这个例子看一下,存在写写冲突时 MVCC 是怎样运行的。

依然假设数据库初始状态为:

Version Value Begin End IsCommited
0 123 0 ~ True

两个事务如下:

  • T1 事务开始时,对 A 加 X 锁
  • T1 第一次读取A,与上一次一样,读取到 123
  • T1 进行一次写入,写入后,数据库变为
Version Value Begin End IsCommited
0 123 0 1 True
1 456 1 ~ False
  • T2 事务开始,对 A 加 X 锁失败,阻塞等待
  • T1 第二次读取 A, Version 1 虽然没有提交,但是是自己写的,所以还是可以读到,读到 456
  • T1 提交释放 X 锁,并更新Version 1 为Commited,数据库变为
Version Value Begin End IsCommited
0 123 0 1 True
1 456 1 ~ True
  • T2 获取 X 锁,开始执行
  • T2 读取 A,读到 456, 因为 T1 在 T2 前开始,所以 T2 可以读取到 T1提交的值是合理的
  • T2 写入一个新的版本,提交,释放X锁,数据库变为
Version Value Begin End IsCommited
0 123 0 1 True
1 456 1 2 True
2 789 2 ~ True

这个例子中,在事务一开始就对要更新的值加 X 锁,导致事务的并发度会比较低,一种优化的方法是,在更新语句时,才对 A 加 X 锁。这样可能出现的问题是:

  • T2 在 T1 更新前已经读到了 123
  • T1 获取 X 锁并更新为 456
  • T2 获取 X 锁失败,阻塞等待
  • T1 提交事务,释放 X 锁
  • T2 获取 X 锁成功,继续执行,但是 T2 并不知道 T1 已经将值更新为了 456

上述情况属于 Second Lost Update (SLU) 的情况,需要说明 RC 并没有禁止 SLU 的情况,所以有些数据库 RC 是允许这样的情况发生的。具体情况就需要看不同数据库的具体实现了。

MVCC与隔离级别

隔离级别 MVCC 算法
RU 查找版本的时候,忽略版本的 IsCommited 属性
RC 查找版本的时候,多次读操作以每次读操作的时间戳为时间戳进行查找, 不忽略 IsCommited 属性,对数据更新的时候上 X 锁
RR 查找版本的时候,多次读操作都以事务开始的时间戳为时间戳进行查找,不忽略 IsCommited 属性,事务开始的时候上 X 锁
S 单纯的 MVCC 实现不了该级别,需要通过层级锁实现
  • MVCC X 锁的上锁时机视数据库具体实现而定,在事务开始的时候上锁,不会有 SLU,但是并发度较低。在更新的时候上锁,会发生 SLU,但是并发度较高。 RC 允许 SLU 的存在,RR 不允许 SLU 的存在。

引用

图片来自 CMU Database Group 的Slides

Search

    Table of Contents