数据库事务中调度串行化、冲突可串行化、前趋图(优先图) - 好文

延续上篇博文一文读懂Spring事务和MySQL事务与锁
<https://blog.csdn.net/J080624/article/details/53995591>我们继续学习。

在多用户DBS中，如果多个用户同时对同一数据进行操作称为并发操作。并发操作使多个事务之间可能产生相互干扰，破坏事务的隔离性(Isolation)。DBMS的并发控制子系统负责协调并发事务的执行，保证数据库的一致性，避免产生不正确的数据。

通常数据库事务是并发执行的(如果你的数据库隔离级别非serializable))，但是这里需要注意两点：

* 必须保证事务并发执行的正确性；
* 必须用正确的方法调度执行事务的并发操作；
这里就引入了一个概念：调度。

<>【1】调度

① 调度定义

多个事务的读写操作按时间排序的执行序列：
T1:r1(A)w1(A)r1(B)w1(B) T2:r2(A)w2(A)r2(B)w2(B)
Sc=r1(A)w1(A)r2(A)w2(A)r1(B)w1(B)r2(B)w2(B)
需要注意的是：

* 调度中每个事务的读写操作保持原来顺序
* 事务调度时不考虑
* 数据库的初始状态
* 事务的语义
② 调度方式

多个事务的并发执行存在多种调度方式：Serializable，Conflict-serializable，Avoid cascading
abort和Strict。

* 严格的
在一个事务写入的值在其提交或者中止之前没有其他事务读或者写

* 避免级联中止的
如果事务仅读已提交事务修改的数据，那么是避免级联终止的。

* 串行调度(Serial schedule)
各个事务之间没有任何操作交错执行，事务一个一个执行。S=T1T2T3…Tn。

* 可串行化调度(Serializable schedule)
如果一个调度的结果与某一串行调度执行的结果等价，则称该调度是可串行化调度，否则是不可串调度。

* 冲突可串行化调度
如果调度中一对连续操作是冲突的，则意味着如果它们的执行顺序交换，则至少i改变其中一个事务的最终执行结果。

如果两个连续操作不冲突，则可以在调度中交换顺序。

一个调度S在保证冲突操作的次序不变的情况下，通过交换两个事务不冲突操作的次序得到另一个调度S’，如果S’是串行的，称调度S为冲突可串行化的调度。

如果一个调度满足冲突可串行，则该调度是可串行化调度。但可串行化调度不一定满足冲突可串行。冲突可串行为可串行的充分条件。

实例如下图：

但是需要保证调度中每个事务读写操作保持原来顺序：

* 冲突操作
标记语言如下：
Ri(X):事务Ti的读X操作(Read(X,t)); Wi(X):事务Ti的写X操作(Write(X,t))
同一事务的两个动作冲突:ri(X);wi(X),

不同事务对同一数据库元素的写冲突:wj(X);wi(X),

不同事务对同一数据库元素的读和写冲突:ri(X);wj(X),

这些都是冲突操作：r1(A) w1(A), r1(A) w2(A) , w2(A) r1(A) , w1(A) w2(A)。

在前趋图中忽略同一事务的动作冲突，但需要保证调度中每个事务的读写操作保持原来顺序。

* 冲突等价
如果S1可以通过非冲突事务交换转换为S2，则称S1，S2为冲突等价。

* 目标可串行化
冲突可串行化调度是可串行化调度的充分条件，不是必要条件。还有不满足冲突可串行化条件的可串行化调度，称为目标可串行化(view
serializability)的调度。

有3个事务, L1和L2是目标等价的（view equivalence）：
T1=W1(Y)W1(X) T2=W2(Y)W2(X)， T3=W3(X)
调度L1=W1(Y)W1(X)W2(Y)W2(X) W3(X)是一个串行调度。
调度L2=W1(Y)W2(Y)W2(X)W1(X)W3(X)不满足冲突可串行化。
但是调度L2是可串行化的，因为L2执行的结果与调度L1相同，Y的值都等于T2的值，X的值都等于T3的值

③ 事务调度方式实例

事务序列如下所示：

* T1:R(X), T2:R(X), T1:W(X), T2:W(X)
* T1:R(X), T2:R(Y), T3:W(X), T2:R(X), T1:R(Y)
* T1:R(X), T2:W(X), T1:W(X), T2:Abort, T1:Commit
* T1:W(X), T2:R(X), T1:W(X), T2:Abort, T1:Commit
* T2: R(X), T3:W(X), T3:Commit, T1:W(Y), T1:Commit, T2:R(Y), T2:W(Z),
T2:Commit
其满足的调度方式如下：

* Not serializable, not conflict-serializable, avoid cascading aborts; not
strict.
* Serializable, conflict-serializable, not avoid cascading aborts, not strict.
* Serializable, conflict-serializable, avoid cascading aborts, not strict.
* Not serializable, not conflict-serializable, not avoid cascading aborts,
not strict.
* Serializable, conflict-serializable, avoid cascading aborts, strict
<>【2】优先图(Precedence Graph)/前趋图

优先图用于冲突可串行的判断，优先图无环则是冲突可串行化。

优先图结构：

* 结点：事务；
* 有向边(Arc):Ti—>Tj，满足Ti<s Tj
* 存在Ti中的操作A1和Tj中的操作A2，满足A1在A2前，并且A1和A2是冲突操作
优先图实例一：

优先图实例二：

优先图实例三：

Since the graph is acyclic schedule, a is conflict-serializable.
T3 , T1 ,T2 is the equivalent serial schedule.

优先图实例四：

Graph is not acyclic. Therefore schedule b is not conflict-serializable.

热门工具换一换