《5章_分布式数据库中的并发控制2012-12-29》由会员分享，可在线阅读，更多相关《5章_分布式数据库中的并发控制2012-12-29（152页珍藏版）》请在金锄头文库上搜索。
1、1,分布式数据库系统及其应用,徐喜荣（),2012年11月2013年1月,2,并发控制的概念和理论分布式数据库系统并发控制的封锁技术分布式数据库系统中的死锁处理分布式数据库系统并发控制的时标技术分布式数据库系统并发控制的多版本技术分布式数据库系统并发控制的乐观方法,分布式数据库中的并发控制,第5章,3,通常，数据库总有若干个事务在运行，这些事务可能并发地存取相同 的数据，称为事务的并发操作。当数据库中有多个事务并发执行时，系统必须对并发事务之间的相互 作用加以控制，这是通过并发控制机制来实现的。并发控制就是负责正确协调并发事务的执行，保证这种并发的存取操 作不至于破坏数据库的完整性和一致性，确
2、保并发执行的多个事务能 够正确地运行并获得正确的结果。,4,以一个实例，说明并发操作带来的数据的不一致性问题。 例如：飞机订票系统中的一个活动序列 1.甲售票点（甲事务）读出某航班的机票余额A, 设A=16. 2.乙售票点（乙事务）读出同一航班的机票余额A, 也为16. 3.甲售票点卖出一张机票，修改余额AA-1。所以A为15, 把A写回 数据库。 4.乙售票点也卖出去一张机票，修改余额AA-1。所以A为15，把A 写回数据库。 结果明明卖出两张机票，数据库中机票余额只减少1。,5,并发操作带来的数据不一致性包括三类： 丢失更新、不一致性和读“脏”数据。丢失修改（Lost Update） 不一
3、致性读（Non-repeatable Read） 读“脏”数据（Dirty Read）,这种情况称为数据库的不一致性是由并发操作引起的。 在并发操作情况下，对甲、乙两个事务的操作序列的调度是随机的。 若按上面的调度序列执行，甲事务的修改就被丢失。 原因：第4步中乙事务修改 A 并写回后覆盖了甲事务的修改。,6,UPDATE x,70,t6,FIND x,t2,200,t7,UPDATE x,t5,x:=x*2,t4,x:=x-30,t3,FIND x,t1,100,t0,更新事务T2,数据库中X的值,更新事务T1,时间,注：其中FIND表示从数据库中读值，UPDATE表示把值写回到数据库T1T
4、2，结果140，T2T1,结果170，得到结果是200，显然是不对的，T1在t7丢失更新操作。,并发控制问题之一-丢失更新：两个事务T1和T2读入同一数据并修改，T2提交的结果破坏了T1提交的结果，导致T1的修改被丢失。,7,FIND x,t2,70,t5,UPDATE x,t4,x:=x-30,t3,FIND x,t1,100,t0,更新事务T2,数据库中A的值,更新事务T1,时间,注：在时间t5事务T2仍认为x的值是100,并发控制问题之二-不一致分析：指事务T1读取数据X后，事务T2读取数据X。之后事务T1更新了数据X的值，此时事务T2使用的X值仍然是原来的数据X的值。,8,100,t6
5、,x:=x-10,t2,ROLLBACK,t5,FIND x,90,t4,UPDATE x,t3,FIND x,t1,100,t0,更新事务T2,数据库中A的值,更新事务T1,时间,并发控制问题之三-依赖于未提交更新（读脏数据）:事务T1修改某一数据，并将其写回磁盘。事务T2读取同一数据后，T1由于某种原因被撤消。事务T1已修改过的数据恢复原值，T2读到的数据就与数据库中的数据不一致。,9,产生上述三类数据不一致性的主要原因是：并发操作破坏了事务的隔离性。并发控制就是要用正确的方式调度并发操作，使一个用户事务的执行不 受其它事务的干扰，从而避免造成数据的不一致性。并发控制的主要技术是：封锁（L
6、ocking）、时间戳和乐观控制法；商用的DBMS一般都采用封锁方法。,例如，甲事务要修改A，若在读出A前先锁住A，其他事务就不能再读取 和修改A了，直到甲修改并写回A后解除了对A的封锁为止。这样就不会丢失甲的修改。,10,分布式数据库中的并发控制主要解决多个分布式事务对数据并发执行的正确性，保证数据库的完整性和一致性。在分布式数据库中，允许数据被复制在多个站点上，当需要对数据执行更新操作时，也必须同时正确地更新它的所有副本。当来自同一站点或 /和不同站点的多个事务对数据进行并发操作时，如果不能正确处理， 数据库的完整性和一致性很容易遭到破坏。因此分布式并发控制比集中式并发控制更复杂。,11,
7、对一组并发的分布式事务可能存在多种正确调度，分布式DBMS事务 管理器的并发控制机制应该采用那种代价最小的正确调度。与集中式数据库系统一样，可串行化调度也是分布式事务能否正确执行的基本方法。事务的可串行性是指若干个事务并发执行的结果与按希望的顺序执行的结果相同时，称诸事务是可串行的。即，如果事务的并发执行能够通过以一定顺序串行执行就可使数据库处于新的一致状态，那么诸如丢失更新的问题就可能得到解决，这就是串行化理论的观点。,12,1. 分布式事务的调度定义： 在数据库系统中，事务访问数据库中数据的方式是通过发出读操作和写操作原语来实现的。通常以Ti表示某个事务，以Ri(x)表示该事务 对数据项x
8、的读操作，以Wi(x)表示该事务对数据项x的写操作。 事务的一个操作序列称为一个调度(Schedule也称history)，一般 以字母S表示。例如，关于两个事务的一个调度： S： R1(x)，R2(y)，W2(y)，R2(x)，W1(x)，W2(x),13,2. 操作冲突定义： 两个同时访问同一数据项x的操作，如果其中至少有一个是写操作， 那么称这两个操作是冲突的。 注意两点： 第一，只有两种冲突：读-写冲突(或写-读冲突)及写-写冲突。 第二，两个操作可以属于同一事务或者两个不同的事务，在后者的情况下，称为两个事务冲突。 如果有两个事务Ti 和Tj， Ti 的所有操作都先于Tj 的操作，那
9、么这两个 事务为串行执行的，必定不会有冲突。,14,3. 分布式事务串行调度定义 设有一组事务T=T1，T2，Tn，如果事务Ti的所有操作都 先于事务Tj 的操作，记为 Ti Tj 。 若一个调度S，其每个事务的执行均有TiTj，ij，记为： S = Ti Tj 称 S 是一个串行调度。,15,对一个串行调度来说，它总是可以正确地执行，执行它可以使数据库 保持一致状态。原因如下： （1）如果S正确执行完成，则S中的每一个事务都被提交，由于事务 的原子性，保证了数据库的一致性。 （2）如果S在执行时发生故障，若Tk之前的事务都已提交，则夭折Tk ,使数据库的状态恢复到Tk前的状态。该状态的数据库
10、也是一致的，因为Tk之前的事务都已提交。 （3）如果S在执行时发生故障，若Tk之前的事务有被夭折的，则夭折Tk，重做Tk以前已被提交的事务，撤销Tk以前被夭折的事务，此时数据库也是一致的。 所以，串行调度总是可以使数据库保持一致。但是串行调度时系统 的运行效率较低。,16,4. 可串行化调度 可串行化调度是让有冲突的操作串行执行，非冲突的操作并行执行，所以可串行化调度就是事务并发控制要寻求的基本方法。 因为分布式事务之间的冲突最终分解，转换为同一站点上子事务间 的冲突操作，而且由于分布式数据库中数据的复制，会使冲突的几率 比集中式更小，从而使并行执行的程度更高。 因此，通常分布式事务的可串行化
11、调度可以转化为子事务的可串行 化调度，但涉及多副本选择时，分布式事务调度要多做一个选择副本 的操作，以避免冲突操作。,17,1. 事务的定义 一个事务是一个偏序集：Ti= i , i ，其中： （1）i ：操作符集合，包含Rix, Wix/ x为数据项 U Ai , Ci ， Ai, Ci 是i 中最后一个操作符，且只能出现其中之一个； Ai为撤销(abort), Ci 为提交(commit)； i ：排序关系，即(冲突)操作有先后次序执行。 （2）如果Rix,Wixi，则它们必满足 Ri(x)iWi(x)或Wi(x)iRi(x)。 （3）Rix, Wix，Ai，Ci 或公式的每一个都是事务T
12、i操作符序列中的 一个操作。 这是对事务的简单定义，实际上事务中还可能包含其他操作如封锁、 通信原语等。,18,fbssjk,19,2. 冲突动作 如果有两个操作P和Q对同一个数据A进行操作，其中有一个是写操作W(A)，则 P和Q称为冲突操作。 R1(A) W2(A) W1(A) W2(A) R1(A) W2(A)一个调度事务的一个操作序列称为一个调度，一般用S表示。比如，S：R1(x), R2(y), W2(y), R2(x), W1(x), W2(x),20,T1 T21(T1) a X 5 (T2) c X2(T1) X a+100 6 (T2) X 2c3(T1) b Y 7 (T2)
13、 d Y4(T1) Y b+100 8 (T2) Y 2d,先序关系,例子. 已知：站点1有数据X，站点2有数据Y 约束：X=Y,21,(X站点)(Y站点)1(T1) a X 2(T1) X a+100 5 (T2) c X 3 (T1) b Y6 (T2) X 2c 4 (T1) Y b+100 7 (T2) d Y 8 (T2) Y 2d 初值: X=Y=0 , 结果: X=Y=200,调度S1,事务内事务间,22,令T= T1,T2,Tn 是一组并发执行事务。T上的调度 S 是具有如下 顺序关系 T 的偏序集，即 S= T , T : (1) T = Ti (2) T i (3) 对任意两个冲突操作 p,q S, 存在 p q 或 q p关系。 第一种情况简单地说明了调度的域是每个事务域的并集。 第二种情况定义排序关系为每个事务排序关系的超集，这保证了每一个事务内部的操作的顺序。 最后一种情况定义了冲突操作的执行顺序。,3. 并发事务的一个调度(简称并发调度)定义,i=1,N,
