共计 6976 个字符,预计需要花费 18 分钟才能阅读完成。
绪论
在上篇,咱们剖析了 ANSI SQL-92 和「A Critique of ANSI SQL Isolation Levels」对隔离级别做出的定义,并且指出了在现今的认知中,其中的一些缺点。本篇将持续探讨隔离级别的问题,讲述实现无关的隔离级别定义和 TiDB 的体现和隔离级别。
Generalized Isolation Level Definitions
介绍
上文所讲的「A Critique of ANSI SQL Isolation Levels」这篇文章在定义隔离级别的时候,对事务的过程也提出了诸多的要求,然而「Generalized Isolation Level Definitions」仅对胜利提交的事务做了束缚,即所有异常现象都是由胜利提交的事务产生的。在例 1-a 中,因为 T1 没有胜利提交,所以并没有出现异常,而例 1-b 中 T1 读到了 abort 事务 T2 的写入内容并且提交胜利了,产生了异常现象(G1a – Aborted Read)。
Txn1 | Txn2 |
---|---|
w(x, 1) |
|
r(x, 1) |
|
abort |
|
abort |
例 1-a – 提交是出现异常的必要条件
Txn1 | Txn2 |
---|---|
w(x, 1) |
|
r(x, 1) |
|
abort |
|
commit |
例 1-b – 提交是出现异常的必要条件
「Generalized Isolation Level Definitions」提出了与实现无关的隔离级别定义,并且更清晰的解释了 predicate 和 item 景象所带来的异样区别,提出了对标 ANSI SQL-92 的隔离级别。
依赖图
Adya 首先引入了三类依赖,能够简略的概括为写读 (WR),读写(RW) 和写写(WW)。含有读的依赖依照读操作的 item 和 predicate 查问类别被细分为两种类型,item 指的是在一个 key 之上产生的依赖;而 predicate 则是指扭转了一个 predicate 后果集,包含扭转其中某个 item 的值和扭转某个 item 在 predicate 下的命中状态。
两个事务间存在依赖则肯定水平上代表了两个事务在事实工夫中的先后关系,如果两个依赖中别离呈现了 T1 先于 T2 和 T2 先于 T1 的景象,那么就证实呈现了事务在事实事件中穿插呈现的景象,毁坏了 Serializable,这是本篇论文的外围观点。
Read Dependencies (WR)
WR 依赖指的是为 T2 读到了 T1 写入的值。
例 2 是针对单个 key 的 WR 依赖,T2 读到了 T1 写入的值,称为 Directly item-read-depends。
Txn1 | Txn2 |
---|---|
w(x, 1) |
|
r(x, 1) |
|
commit |
|
commit |
例 2 – Directly item-read-depends
例 3 是 predicate 条件下的 WR 依赖,例 3-a 是将一个 key 从合乎 predicate 条件改为了不符合条件,而例 3-b 是将一个 key 从不合乎 predicate 条件改为了符合条件。
Txn1 | Txn2 | |
---|---|---|
r(x, 1) |
||
w(x, 10) |
||
`r(sum(x)\ | x<10)` | |
commit |
||
commit |
例 3-a – Directly predicate-read-depends
Txn1 | Txn2 | |
---|---|---|
r(x, 10) |
||
w(x, 1) |
||
`r(sum(x)\ | x<10)` | |
commit |
||
commit |
例 3-b – Directly predicate-read-depends
Anti-Dependencies(RW)
WR 依赖指的是为 T2 批改了 T1 读到的值。
例 4 是针对单个 key 的 RW 依赖,T1 在 T2 读到的 key 之上写入了新值,称为 Directly item-anti-depends。
Txn1 | Txn2 |
---|---|
r(x, 1) |
|
w(x, 2) |
|
commit |
|
commit |
例 4 – Directly item-anti-depends
例 5 是 predicate 条件下的 WR 依赖,例 5-a 是将一个 key 从合乎 predicate 条件改为了不符合条件,而例 5-b 是将一个 key 从不合乎 predicate 条件改为了符合条件。
Txn1 | Txn2 | |
---|---|---|
r(x, 1) |
||
`r(sum(x)\ | x<10)` | |
w(x, 10) |
||
commit |
||
commit |
例 5-a – Directly predicate-anti-depends
Txn1 | Txn2 | |
---|---|---|
r(x, 10) |
||
`r(sum(x)\ | x<10)` | |
w(x, 1) |
||
commit |
||
commit |
例 5-b – Directly predicate-anti-depends
Write Dependencies(WW)
WW 依赖指的是两个事务写了同一个 key,例 6 中 T1 写入了 x 的第一个值,T2 写入了 x 的第二个值。
Txn1 | Txn2 |
---|---|
w(x, 1) |
|
w(x, 2) |
|
commit |
|
commit |
例 6 – Directly Write-Depends
DSG
DSG (Direct Serialization Graph) 能够被称为有向序列化图,是将对一系列事务进行以来剖析后,将上述的三种依赖作为 edge,将事务作为 node 绘制进去的图。图 1 展现了从事务历史剖析失去 DSG。如果 DSG 是一个有向无环图(如图 1 所示),那么这些事务间的依赖关系所决定的事务先后关系不会呈现矛盾,反之则代表可能有异样,这篇文章依据出现异常时组成环的 edge 的依赖类型,定义了隔离级别。
图 1 – 从事务历史剖析 DSG
异常现象与隔离级别
为了不和「A Critique of ANSI SQL Isolation Levels」产生符号上的抵触,这篇文章应用 G 示意异常现象,应用 PL 示意隔离级别。
PL-1 & G0
G0 (Write Cycles) 和相似于脏写定义,但要求 P0 (Dirty Write) 景象理论产生异样,如果仅仅是两个事务写同一个 key 并且并行了,他们还是能够被视为 Serializable,只有当两个事务相互呈现依赖的时候才属于 G0 景象。例 7- a 属于 P0 景象,但只看这个景象自身,是合乎 Serializable 的,而例 7-b 同时产生了 P0 和 G0。
Txn1 | Txn2 |
---|---|
w(x, 1) |
|
w(x, 2) |
|
commit |
commit |
例 7-a – P0 (Dirty Write) 与 G0 比照 – P0
Txn1 | Txn2 |
---|---|
w(x, 1) |
|
w(x, 2) |
|
w(y, 1) |
|
w(y, 2) |
|
commit |
commit |
例 7-b – P0 (Dirty Write) 与 G0 比照 – G0
如果不会呈现 G0 景象,则达到了 PL-1 的隔离级别。
PL-2 & G1
G1 景象有三条,其中 G1a 和 G1b 与依赖图无关,G1c 是依赖图上的异样。
G1a (Aborted Reads) 指读到了中断事务的内容,例 8 是 G1a 景象的两种状况,不论是通过 item 类型还是 predicate 类型的查问读到了中断事务的内容,都属于 G1a 景象。例 8-a 中,T1 将 x 写为 2,然而这个事务最初产生了 abort,而 T2 读到了 T1 写入的后果,产生了 G1a 景象;在例 8-b 中 T1 将 x 从 1 改写为 2,此时 sum 的值也会因而从 10 变为 11,然而因为 T1 最初产生了 abort,所以 T2 读取到 sum 为 11 的值也属于 G1a 景象。
Txn1 | Txn2 | |
---|---|---|
r(x, 1) |
||
w(x, 2) |
||
r(x, 2) |
||
abort |
commit |
例 8-a – G1a 景象
Txn1 | Txn2 |
---|---|
r(x, 1) |
|
r(sum, 10) |
|
w(x, 2) |
|
r(sum, 11) |
|
abort |
commit |
例 8-b – G1a 景象
G1b (Intermediate Reads) 指读到了事务的两头内容,例 9 是 G1b 的两种状况,item 类型和 predicate 类型的读取都属于 G1b 景象。在例 9-a 中,T1 将 x 从 1 批改为 2,最初批改为 3,然而对于其余事务而言,只能察看到 T1 最初批改的值 3,所以 T2 读取到 x=2 的行为属于 G1b 景象;在例 9-b 中,T2 尽管没有间接从 T1 读取到 x=2 的值,然而其读取到的 sum=11 也包含了 x=2 的后果,其后果而言依然读取到了事务的中间状态,属于 G1b 景象。
Txn1 | Txn2 |
---|---|
r(x, 1) |
|
w(x, 2) |
|
w(x, 3) |
|
r(x, 2) |
|
commit |
commit |
例 9-a – G1b 景象
Txn1 | Txn2 |
---|---|
r(x, 1) |
|
r(sum, 10) |
|
w(x, 2) |
|
w(x, 3) |
|
r(sum, 11) |
|
commit |
commit |
例 9-b – G1b 景象
G1c (Circular Information Flow) 指 WW 依赖和 WR 依赖组成的 DSG 中存在环,图 2 形容了 G1c 景象,这个例子能够了解为,T1 和 T2 同时写了 x,并且 T2 是后写的,所以 T2 应该晚于 T1 提交,同理 T3 应该晚于 T2 提交。而最初 T1 读到了 T3 写入的 z = 4,所以 T3 须要早于 T1 提交,产生了矛盾。
图 2 – G1c 景象
如果不会呈现 G0 和 G1 的三个子景象,则达到了 PL-2 的隔离级别。
PL-3 & G2
G2 (Anti-dependency Cycles) 指的是 WW 依赖、WR 依赖和 RW 依赖组成的 DSG 中存在环,图 3 展现了对上篇的 Phantom 景象进行剖析,在其中发现 G2 景象的例子。在这个例子中,如果 T1 或者 T2 任意一个事务失败,或者 T1 没有读取到 T2 写入的值,那么实际上就不存在 G2 景象也不会产生异样,然而依据 P3 的定义,Phantom 景象曾经产生了。本文认为 G2 比 P3 用一种更加正当的形式来束缚 Phantom 问题带来的异样,同时也补充了 ANSI SQL-92 的 Phantom Read 必须要两次 predicate 读能力算作异样的不合理之处。
图 3 – G2 景象
如果不会呈现 G0、G1 和 G2 景象,则达到了 PL-3 的隔离级别。
PL-2.99 & G2-item
PL-3 的要求十分严格,而 PL-2 又相当于 Read Committed 的隔离级别,这就须要在 PL-2 和 PL-3 之间为 Repeatable Read 找到地位。上篇提到过 Non-repeatable Read 和 Phantom Read 的区别在于是 item 还是 predicate 类型的读取,了解了这一点之后,G2-item (Item Anti-dependency Cycles) 就跃然纸上了。
G2-item 指的是 WW 依赖、WR 依赖和 item 类型的 RW 依赖组成的 DSG 中存在环。图 4 展现了对 Non-repeatable 景象进行剖析,在其中发现 G2-item 景象的例子。
图 4 – G2-item 景象
如果不会呈现 G0、G1 和 G2-item 景象,则达到了 PL-2.99 的隔离级别。
小结
表 1 给出了与实现无关的隔离级别定义,图 5 将其与「A Critique of ANSI SQL Isolation Levels」所提出的隔离级别进行了比照,右侧是这篇文章所给出的定义,略低于左侧是因为这一定义要求事务被提交才可能产生异样。
G0 | G1 | G2-item | G2 | |
---|---|---|---|---|
PL-1 | x | ✓ | ✓ | ✓ |
PL-2 | x | x | ✓ | ✓ |
PL-2.99 | x | x | x | ✓ |
PL-3 | x | x | x | x |
表 1 – Adya 的隔离级别定义
图 5 – 隔离级别定义比照
这篇文章所做出的隔离级别的定义的长处在于:
- 定义与实现无关;
- 只束缚了胜利提交的事务,此前的定义限度了并发控制技术的空间,例如乐观事务“first-committer-wins”的策略可能被这一隔离级别更加好的解释;
- 指出了读到事务中间状态的异样;
- 对 Phantom 景象提出了更加清晰和精确的定义;
- 事务间的依赖关系和事务产生的程序无关,在这一定义下,更容易辨别隔离性和线性一致性。
留神到前文所提到的 Snapshot Isolation 并没有呈现在这篇文章中,而如果剖析 A5B – Write Skew 景象的话,会发现它其实是属于 G2-item 景象的,这就导致很多 SI 的隔离级别只能被划分到 PL-2 的隔离级别上。这是因为这篇文章只对胜利提交事务的状态做出了规定,而在 Adya 的博士论文「Weak Consistency: A Generalized Theory and Optimistic Implementations for Distributed Transactions」中对事务的过程状态也作出了束缚,基于此提出了对事务中间状态的补充,其中也包含 PL-SI 的隔离级别,本文对于此不再深刻开展。
TiDB 的隔离级别
在这一节,咱们将钻研 TiDB 的行为,TiDB 的乐观事务模型和 MySQL 在行为上十分相似,其剖析能够类推到 MySQL 之上。
乐观锁与乐观锁
乐观锁和乐观锁是两种加锁技术,对应了乐观事务模型和乐观事务模型,乐观锁会在事务提交时查看事务是否胜利提交,“first-committer-wins”的策略会让后提交的抵触事务失败,TiDB 会返回 write conflict 谬误。因为一个事务只有有一行记录产生了抵触,整个事务都须要被回滚,所以乐观锁在高抵触的状况下会大幅度降低性能。
乐观锁则是在事务中的每个操作执行时去查看是否会产生抵触,如果会产生抵触,则会反复尝试加锁行为,直到造成抵触的事务中断或提交。就算在无抵触的状况下,乐观锁也会减少事务执行过程中每个操作的提早,这一点减少了事务执行过程中的开销,而乐观锁则确保了事务在提交时不会因为 write conflict 而失败,减少了事务提交的成功率,防止了清理失败事务的额定开销。
快照读与以后读
快照读和以后读的概念在 MySQL 和 TiDB 中都存在。快照读会遵循快照隔离级别的字面定义,从事务的快照版本读取数据,一个例外情况是在快照读下会优先读取到本身事务批改的数据(local read)。以后读可能读取到最新的数据,实现形式为获取一个最新的工夫戳,将此作为以后读读取的快照版本。Insert/update/delete/select for update 会应用以后读去读取数据,应用以后读也常常被称为“隔离级别降级为 Read Committed”。这两种读取形式的混合应用可能产生十分难以了解的景象。例 10 给出了在混合应用状况下,以后读影响快照读的例子,依照快照读和以后读的行为定义,快照读是不能看到事务开始后新插入的数据的,而以后读能够看到,然而当以后读对这行数据进行批改之后,这行数据就变为了“本身事务批改的数据”,于是快照读优先应用了 local read。
Txn1 | Txn2 |
---|---|
create table t(id int primary key, c1 int); |
|
begin |
|
select * from t; -- 0 rows |
|
insert into t values(1, 1); |
|
select * from t; -- 0 rows |
|
update t set c1 = c1 + 1; -- 1 row affected |
|
select * from t; -- 1 row, (1, 2) |
|
commit; |
例 10 – 混合应用快照读与以后读
读时加锁
在乐观事务下,point get 和 batch point get 的执行器在应用以后读时,TiDB 有非凡的读时加锁策略,执行流程为:
- 读取数据并加锁
- 将数据返回给客户端
相比之下,其余执行器在以后读下的加锁流程为:
- 读取数据
- 给读取到的数据加锁
- 将数据返回给客户端
如例 11 所示,他们的区别在于,读时加锁可能锁上不存在的数据索引(point get 和 batch point get 肯定存在惟一索引),即便没有读到数据,也不会让这个索引被其余事务所写入。回顾一下 P2 – Fuzzy Read,这一行为正好和 P2 的读锁要求统一,因而,乐观事务下的以后读配合读时加锁的策略可能避免 Fuzzy Read 异样的产生。
create table t(id int primary key);
begin pessimistic;
select * from t where id > 1 for update; -- 0 rows returns, will not lock any key
select * from t where id = 1 for update; -- 0 rows returns, lock pk(id = 1)
例 11 – 混合应用快照读与以后读
RC 与读一致性
RC 有两种了解,一种是 ANSI SQL-92 中的 Read Committed,另一种是 Oracle 中定义的 Read Consistency。一致性读要求读取操作要读到雷同的内容,图 6 是读不统一的例子,在一个读申请产生的过程中,产生了另一个事务的写入,对 x 和 y 读到了不同时刻的数据,毁坏了 x + y = 100 的束缚,呈现了一致性问题,读一致性可能避免这种状况的产生。
图 6 – 读不统一
在 Oracle 中,读一致性有两个级别:
- 语句级别
- 事务级别
语句级别保障了单条语句读一致性,而事务级别保障了整个事务的读一致性。如果应用快照的概念来进行了解的话,语句级别的读一致性代表每条语句会从一个快照进行读取,而事务级别的读一致性代表一个事务中的每一条语句都会从一个快照进行读取,也就是咱们常说的快照隔离级别。
TiDB 的 RC 实现了语句级别的读一致性,并且保障每次读取都可能读到最新提交的数据,从而实现了 Read Committed 的隔离级别。
异样剖析
快照隔离级别通过多版本的形式来避免了 P0 可能会带来的异常现象,Fuzzy Read 会因为两个状况产生:
- 乐观事务模型下不加读锁的以后读
- 混合应用快照读和以后读
而 Phantom 异样则会因为不存在给 predicate 的加锁行为而呈现。
综上所述,如果只应用快照读的话,TiDB 是不会呈现 Phantom 或者 G2 异样的,然而快照读因为会呈现 A5B (Write Skew),依旧会违反 G2-item,只有读时加锁可能避免 A5B,须要因场景抉择事务模型才可能获得现实的后果。
总结
在下篇中,咱们解读了实现无关的隔离级别定义,实现无关隔离级别定义的提出大大简化了对事务隔离性的剖析,同时也会作为后续剖析的根底内容。最初咱们剖析了 TiDB 中的一些行为,商业数据库在实现时在遵循规范的同时又有着更简单的,不论对于数据库的开发者还是用户,了解数据库行为的起因都是非常重要且无益的。