可串行性(数据库)
时间：2022-12-31 00:30:01 | 来源：信息时代
时间：2022-12-31 00:30:01 来源：信息时代
可串行性 : 度量事务并发调度的一个属性,被用于作为事务并发调度正确与否的标准。如果一个事务并发调度的结果与某个串行调度的结果是一样的,就称这个调度满足可串行性。
让多个数据库事务同时执行,无疑会提高数据库系统的事务处理吞吐量。但是,多个事务的交叉执行,意味着多个事务可以同时存取数据库中的数据,彼此之间可能产生相互干扰,从而可能破坏数据库的一致性。为此,需要为事务并发执行定义一个正确性标准。事务的隔离性要求事务在有其他事务干扰下的执行效果和没有其他事务存在下的执行效果是一样的,这意味着事务的任何串行执行的结果都是正确的。因此,一个合适的正确性调度的定义可以是: 如果n个事务的某个并发执行调度的效果和这n个事务的某个串行调度的执行效果是一样的,那么这个并发调度就是正确的,也称这个调度满足可串行性或是可串行化调度。但是,由于n个事务有n!种可能的串行调度,不可能事先计算所有不同的串行调度的结果,因此,事物调度的正确性还需要其他可操作更强的定义,这就是冲突可串行性的。可以通过一个基于优先图的简单算法来判定一个并发调度是否正确。必须说明的是,冲突可串行性是事务并发调度正确性的充分条件,并不是必要条件。因此,寻找那些比冲突可串行化更弱的条件或者给出并发调度的充分必要条件是有意义的,视图可串行化是在这个方面的一个尝试。
1. 可串行化调度
满足可串行性的事务并发调度就称为可串行化调度(seralizable schedule)。例说,考虑银行中的转账业务。设事务T1从账户A转5000元到账户B,事务T2从账户A转其余额的10%到账户B。两个事务的操作序列如下:
T1:Read(A);
A:=A-5000;
Write(A);
Read(B);
B:=B+5000;
Write(B); | T2:Read(A);
temp:=A*0.1;
A:=A-temp;
Write(A);
Read(B);
B:=B+temp;
Write(B); |
设账户A和B的初值分别为10000元和20000元。先执行T
1后执行T
2的串行调度如图1所示,账户A和B的最终余额分别为4500元和25500元。
| T1 | T2 |
Read(A)
A:=A-5000
Write(A)
Read(B)
B:=B+5000
Write (B) | |
| | Read (A)
temp:=A*0.1
A:=A-temp Write (A)
Read(B)
B:=B+temp Write (B) |
图1 串行调度1: 先T1后T2
先执行T
2后执行T
1的串行调度如图2所示,账户A和B的最终余额分别为4000元和26000元。虽然两种调度的结果(账户余额)不同,但是这两种串行调度方式都保持了账户A和B的资金总和(30000元)不变。
| T1 | T2 |
| | Read(A)
temp:=A*0.1
A:=A-temp Write (A)
Read (B)
B:=B+temp Write (B) |
Read (A)
A:=A-5000
Write(A)
Read(B)
B:=B+5000
Write (B) | |
图2 串行调度2: 先T2后T1
这两种串行执行结果都是正确的。但当事务并发调度时,情况就变得复杂得多。一种可能的并发调度如图3所示,它的执行结果与图1的串行调度结果一致,账户A和B的终值分别为4500元和25500元。即图3所示的并发调度与图1所示的串行调度是结果等价的。
| T1 | T2 |
Read(A)
A:=A-5000
Write(A) | |
| | Read(A)
temp:=A*0.1
A:=A-temp Write (A) |
Read (B)
B:=B+5000
Write (B) | |
| | Read(B)
B:=B+temp Write(B) |
图3 可串行化的并发调度
另一种可能的并发调度如图4所示,当它执行完后,账户A和B的终值分别为5000元和21000元,A和B之和为26000元。两个事务执行后账户A和B的总和未能保持不变,因此,这个调度是不正确的。
| T1 | T2 |
Read(A)
A:=A-5000 | |
| | Read(A)
temp:=A*0.1
A:=A-temp Write(A)
Read(B) |
Write(A)
Read (B)
B:=B+5000
Write (B) | |
| | B:=B+temp Write(B) |
图4 不可串行化的并发调度
2. 冲突可串行化
冲突可串行化(conflict serializability)是判断某一个并发调度是否正确的操作性定义。它通过调换操作序列中不冲突操作对来变换调度,如果能够通过这样的变换形成一个串行调度,那么这个并发调度就是冲突可串行化调度。
考虑到事务中对数据库有影响的操作是read和write语句,因此可以把事务抽象成只有read和write语句组成的操作序列,同样并发调度也可以抽象为读写操作的序列。例如,图3所示的调度S
1可以简单表达为如下的操作序列:S
1＝R
1(A)W
1(A)R
2(A)W
2(A)R
1(B)W
1(B)R
2(B)W
2(B)。
其中,read操作简写为R,write操作简写为W,下标表示该操作所属事务号,操作的数据对象写在括号中。
不同事务的一对操作,如果作用在同一个数据对象上,就可能造成冲突(conflict)。有两种类型的冲突: 读-写冲突(即R
i(x)和W
j(x)之间)和写-写冲突(即W
i(x)和W
j(x)之间)。冲突操作的执行次序会影响执行的结果,例如,如果R
i(x)在W
j(x)之前,则事务S
i读的是S
j写前x的旧值; 如果R
i(x)在W
j(x)之后,则S
i读的是S
j写后x的新值。
不冲突的操作对也可以分为两类: 一是读操作对,如R
i(x)和R
j(x);二是虽然有写操作,但作用的数据对象不同,如R
i(x)和W
j(y)。显然事务调度中相邻的不冲突操作的次序可以互相调换,不会影响执行的结果。注意,假定同一个事务中的操作顺序是不能调换次序的。
如果调度S′是从调度S通过调换一系列相邻的不冲突操作的次序得到,那么称S′和S是一对“冲突等价”的调度。如果调度S与某个串行调度是“冲突等价”的,那么称调度S是“冲突可串行化”的调度。
例如,对图3中的并发调度S
1可以按下列步骤通过调换相邻的不冲突操作得到一个冲突等价的串行调度S
1′:
S
1→R
1(A)W
1(A)R
2(A)R
1(B)W
2(A)W
1(B)R
2(B)W
2(B)→R
1(A)W
1(A)R
1(B)R
2(A)W
2(A)W
1(B)R
2(B)W
2(B) →R
1(A)W
1(A)R
1(B)R
2(A)W
1(B)W
2(A)R
2(B)W
2(B) →R
1(A)W
1(A)R
1(B)W
1(B)R
2(A)W
2(A)R
2(B)W
2(B)=S
1′。S
1′是先执行事务T
1再执行事务T
2的一个串行调度(即图1对应的调度),故并发调度S
1是冲突可串行化的。
3.冲突可串行化调度的判断
将调度S转化成有向图表示,称为优先图(precedence graph),记为G(S)=(V,E),其中V是结点的集合,它包含所有参与调度的事务; E是边的集合,可以通过分析S中的冲突操作来确定每条边。如果下列条件之一成立,则在E中添加一条边T
i→T
j:
调度S中,冲突操作R
i(x)在W
j(x)之前;
调度S中,冲突操作W
i(x)在R
j(x)之前;
调度S中,冲突操作W
i(x)在W
j(x)之前。
如此构成的优先图中若有回路,则S显然不可能冲突等价于任何串行调度;如果优先图中无回路,则可以采用拓扑排序,得到一个等价的串行调度。
拓扑排序的方法如下: 由于图中无回路,必然存在入度为0的结点,可将这个结点及其发出的边从图中移去,并且把这个结点存放在一个先进先出队列中(若有多个这样的结点,其存放次序任意)。对所剩的图作相同的处理,如此继续进行,直到所有结点都移入队列为止。按队列中结点次序串行安排相应各事务的操作,就可以得到一个冲突等价的串行调度。
例如,判定由四个事务构成的调度S
2＝W
3(y)R
1(x)R
2(y)W
3(x)W
2(x)W
3(z)R
4(z)W
4(x)的冲突可串行化的步骤如下: 首先分别分析对数据对象x,y,z的所有操作。对每一对冲突操作,按其在S
2中执行的先后顺序,在优先图中添加相应的边。如此可得图5所示的优先图。
图5 优先图
由于优先图中无回路,调度S
2是冲突可串行化的调度。按照拓扑排序算法,可以得到结点的队列为T
1,T
3,T
2,T
4。因此得到S
2的冲突等价串行调度S
2′:S
2′=R
1(x)W
3(x)W
3(x)W
3(z)R
2(y)W
2(x)R
4(z)W
4(x)。
必须说明的是,尽管运用优先图判定办法能检验给定调度是否冲突可串行化,但是在实际运行时,由于事务是随机到达的,而且还和事务的执行情况(例如等待CPU还是等待I/O等)等诸多因素有关,不可能事先制定好一个调度然后交给系统执行。因此,冲突可串行化的意义还是限于事务理论上的研究。比较实际的方法是让DBMS按一定的并发控制协议调度事务,只要保证按照这个协议生成的调度能够保证其执行是可串行化就可以了,而不必关心其具体的调度。
4.视图可串行化
如果将冲突可串行化调度和可串行化调度记为两个集合Sc和S,那么Sc是S的真子集。是否存在比Sc大但是比S小的集合呢?显然寻找这样的集合是有意义的。先看一个例子:
设有并发调度S
3＝R
1(x)W
2(x)W
1(x)W
3(x)。在S
3中,三个事务之间的操作都是冲突的,不可能通过交换不冲突操作次序而获得串行调度,因而S
3不是冲突可串行化的。但是却可以找到一个串行调度S
3′=R
1(x)W
1(x)W
2(x)W
3(x),比较S
3和S
3′可见,两个调度中的R
1(x)读的值是相同的,W
1(x)和W
2(x)在次序上调换了,虽然会影响x的中间值,但x的终值仍由W
3(x)决定,与x在W
3(x)之前所取的值无关。调度S
3和S
3′的执行效果是完全一样的,因此是等价的调度。这种等价性称之为视图等价。
如果两个调度S和S′,在数据库的任何初始状态下,所有读出的数据都是一样的,同时最后写数据库中数据对象的事务也是一样的,则称S和S′是“视图等价”的调度。如果调度S与某个串行调度是“视图等价”的,那么称调度S是视图可串行化(view serializability)调度。视图可串行化调度是一种比“冲突可串行化”定义要宽松一些的另一种可串行化调度。
可以证明: 每个冲突可串行化的调度都是视图可串行化的调度; 但每个视图可串行化的调度不一定是冲突可串行化的调度。
虽然,视图可串行化比冲突可串行化更加普遍,但是其测试却是NP完全问题,而且也没有找到可保证视图可串行化的简单的生成规则或协议,因而并不实用。冲突可串行化覆盖了绝大部分可串行化的实例,且测试方法简单,在DBMS中也很容易实现,因此是目前商用DBMS中普遍采用的并发控制的正确性准则。在一般文献中,若不特别声明,可串行化都指冲突可串行化。
在线咨询
