崔明义
（ mycui369@126.com)
计算机应用技术 2007级研究生
1,并发控制的概念和理论
2.分布式数据库系统并发控制的封锁技术
3.分布式数据库系统中的死锁处理
4.分布式数据库系统并发控制的时标技术
5.分布式数据库系统并发控制的多版本技术
6.分布式数据库系统并发控制的乐观方法分布式数据库中的并发控制第 5章
通常，数据库总有若干个事务在运行，这些事务可能并发地存取相同的数据，称为事务的并发操作。
当数据库中有多个事务并发执行时，系统必须对并发事务之间的相互作用加以控制，这是通过并发控制机制来实现的。
并发控制就是负责正确协调并发事务的执行，保证这种并发的存取操作不至于破坏数据库的完整性和一致性，确保并发执行的多个事务能够正确地运行并获得正确的结果。
分布式数据库中的并发控制解决多个分布式事务对数据并发执行的正确性，保证数据库的完整性和一致性。
比集中式并发控制更复杂。
1.1 并发控制的概念
1 并发控制的概念和理论集中式 DB环境
T1 T2 … Tn
DB
(一致性约束 )
1.1 并发控制的概念
1 并发控制的概念和理论分布式 DB环境
X Y Z
T1 T2
1.1 并发控制的概念
1 并发控制的概念和理论
多处理器
CPU1
CPU2
T1
T2
Time
1.1 并发控制的概念
1 并发控制的概念和理论并发执行
单处理器
T1
t1
T2
t2
T1
t3
T2
t4
Time
CPU
1.1 并发控制的概念
1 并发控制的概念和理论非并发执行
UPDATE x70t6
FIND xt2
200t7
UPDATE xt5
x:=x*2t4
x:=x-30t3
FIND xt1
100t0
更新事务 T2数据库中 X的值更新事务 T1时间注：其中 FIND表示从数据库中读值,UPDATE表示把值写回到数据库
T1T2，结果 140,T2T1,结果 170，
得到结果是 200，显然是不对的,T1在 t7丢失更新操作。
1.1 并发控制的概念
1 并发控制的概念和理论并发控制问题之一：丢失更新
FIND xt2
70t5
UPDATE xt4
x:=x-30t3
FIND xt1
100t0
更新事务 T2数据库中 A的值更新事务 T1时间注：在时间 t5事务 T2仍认为 x的值是 100
1.1 并发控制的概念
1 并发控制的概念和理论并发控制问题之二：不一致分析
100t6
x:=x-10t2
ROLLBACKt5
FIND x90t4
UPDATE xt3
FIND xt1
100t0
更新事务 T2数据库中 A的值更新事务 T1时间注,事务 T2依赖于事务 T1的未完成更新
1.1 并发控制的概念
1 并发控制的概念和理论并发控制问题之三：依赖于未提交更新（读脏数据）
事务 Ti
Ti= {?i,<i }
其中：
1,?i,操作符集合,{Ri(x),Wi(x) } U {Ai,Ci }
2,Ai,Ci 是最后的操作符，只能是其一
3,<i,(冲突 )操作有序执行,Ri(x) <i Wi(x) 或
Wi(x) <i Ri(x)
1.2 事务可串行化理论
1 并发控制的概念和理论
操作符集读 Ri(x)和写 Wi(x)动作序列
冲突动作
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)
1.2 事务可串行化理论
1 并发控制的概念和理论
T1 T2
1 (T1) a?X 5 (T2) c?X
2 (T1) X?a+100 6 (T2) X?2c
3 (T1) b?Y 7 (T2) d?Y
4 (T1) Y?b+100 8 (T2) Y?2d
先序关系例子已知：站点 1有数据 X，站点 2有数据 Y
约束,X=Y
1.2 事务可串行化理论
1 并发控制的概念和理论
(X站点 ) (Y站点 )
1 (T1) a?X
2 (T1) X?a+100
5 (T2) c?X 3 (T1) b? Y
6 (T2) X?2c 4 (T1) Y?b+100
7 (T2) d? Y
8 (T2) Y?2d
初值,X=Y=0,结果,X=Y=200
调度 S1 事务内事务间令 T= {T1,T2,…,Tn} 是一组事务,T上的调度 S 是具有如下顺序关系 <T的偏序，即 S={?T,<T},
(1)?T=? Ti
(2) <T <i
(3) 对于任意一组冲突操作 p,q?S,存在 p < q
或 q < p关系并发调度定义
i=1
N
N
i=1
1.2 事务可串行化理论
1 并发控制的概念和理论
调度
– 一组事务的调度必须包含这些事务的所有操作
– 调度中某个事务的操作顺序必须保持与该事务原有的顺序相同
串行调度
– 一个事务的第一个动作是在另一个事务的最后一个动作完成后开始,即调度中事务的各个操作不会交叉,每个事务相继执行,
一致性调度
– 调度可以使得数据库从一个一致性状态转变为另一个一致性状态，则称调度为一致性调度
1.2 事务可串行化理论
1 并发控制的概念和理论
调度等价
– S1与 S2等价,也就是说,对于冲突操作,
<Oi,Oj>,Oi < Oj在 S1中成立,同时 Oi < Oj
在 S2中也成立
可串行化调度
– 如果一个调度等价于某个串行调度，则该调度称为可串行化调度。
– 也就是说，该调度可以通过一系列非冲突动作的交换操作使其成为串行调度
1.2 事务可串行化理论
1 并发控制的概念和理论例子
两个事务，定义如下：
T1:
1,Read(x）
2,x=x+10
3,Write(x)
4,Read(y)
5,y=y-15
6,Write(y)
7,commit
1.2 事务可串行化理论
1 并发控制的概念和理论
T2:
1,Read(x）
2,x=x-20
3,Write(x)
4,Read(y)
5,y=y*2
6,Write(y)
7,commit
五种调度：
S1={R1(x),x=x+10,W1(x),R1(y),y=y-15,W1(y),C1,R2(x),x=x-
20,W2(x),R2(y),y=y*2,W2(y),C2}
S2={R1(x),x=x+10,W1(x),R2(x),x=x-20,W2(x),R1(y),y=y-
15,W1(y),C1,R2(y),y=y*2,W2(y),C2}
S3={R1(x),x=x+10,W1(x),R2(x),x=x-
20,W2(x),R2(y),y=y*2,W2(y),C2,R1(y),y=y-15,W1(y),C1}
S4={R2(x),x=x-
20,W2(x),R2(y),y=y*2,W2(y),C2,R1(x),x=x+10,W1(x),R1(y),y
=y-15,W1(y),C1}
S5={R2(x),x=x-20,W2(x),R1(x),x=x+10,W1(x),
R2(y),y=y*2,W2(y),C2,R1(y),y=y-15,W1(y),C1}
1.2 事务可串行化理论
1 并发控制的概念和理论
如果将事务提交延迟到两个事务操作完成之后执行，有：
– 调度 S1和 S4是串行调度
– 调度 S2和 S1的冲突操作具有相同的顺序，因此是等价调度； S2是可串行化调度，也是一致性调度
– 调度 S3虽是一致调度，但是它不与 S1或 S4等价，
所以 S3不是可串行化调度
– 调度 S5和 S4等价，所以 S5是一致调度，也是可串行化调度
1.2 事务可串行化理论
1 并发控制的概念和理论
有以下推论：
– 一个可串行化调度必定与某个串行调度等价，
且是一致性调度
– 一致性调度不一定是可串行化调度
– 同一事务集几个可串行化调度，他们的结果未必相同
1.2 事务可串行化理论
1 并发控制的概念和理论优先图 P(S)
调度 S 的优先图是一个有向图 G(N,E),其中
– N,一组节点 N={T1T2,…,Tn},S中的事务
– E,一组有向边 E={e1,e2,…,en},Ti? Tj 是图中的一条边，当且仅当? p? Ti,q? Tj 使得 p,q 冲突，
并且 p <S q
1.3 分布式事务的可串行化调度测试
1 并发控制的概念和理论测试调度 S的可串行化
对于调度 S中的事务 Ti，在图中创建一个节点 Ti
对于每一种这样的情形：如果 S中的在 Ti执行了 W(X)操作后执行 Tj的 R(X)操作，那么在优先图中创建一条边
（ Ti→ Tj ）
对于每一种这样的情形：如果 S中的在 Ti执行了 R(X)操作后执行 Tj的 W(X)操作，那么在优先图中创建一条边
（ Ti→ Tj ）
对于每一种这样的情形：如果 S中的在 Ti执行了 W(X)操作后执行 Tj的 W(X)操作，那么在优先图中创建一条边
（ Ti→ Tj ）
当且仅当优先图中没有闭环时，调度 S是可串行化的
1.3 分布式事务的可串行化调度测试
1 并发控制的概念和理论测试调度 S的可串行化
优先图中存在环路，说明调度是不可串行化的，否则是可串行化的。
环路是指有向图中每条边的起始节点（第一条边除外），
都与前一条边的终止节点连接，而第一条边的起始节点于最后一条边的终止节点连接，即事务序列是以同一个节点作为开始和结束的
调度 S中事务 Ti在事务 Tj之前，与 S等价的调度中 Ti也必须在 Tj之前
某项数据导致了调度中的一条边的生成，就把数据项标注到优先图中这条边的旁边
如果调度 S中不存在环路，那么就可能存在若干个与 S等价的串行调度
1.3 分布式事务的可串行化调度测试
1 并发控制的概念和理论
1.3 分布式事务的可串行化调度测试
1 并发控制的概念和理论
T1
T2
T1
T2
T1
T2
T1
T2
T1
T2
S1的优先图 S2的优先图 S3的优先图 S4的优先图 S5的优先图
X Y X Y X Y X Y X Y
存在环路举例
考虑如下 3个事务：
T1,Read(x); Write(x); Commit;
T2,Write(x); Write(y); Read(z); Commit;
T3,Read(x); Read(y); Read(z); Commit;
这 3个事务的一个调度：
S={W2(x),W2(y),R2(z),C2,R1(x),W1(x),C1,R3(x),R3(y),R3(z),C3}
优先图：
T2 T1 T3
无环,S是串行调度。
1.3 分布式事务的可串行化调度测试
1 并发控制的概念和理论另外一个调度 S’:
S={W2(x),R1(x),W1(x),C1,R3(x),W2(y),R3(y),R2(z),C2,R3(z),C3}
先序图：
T2 T1 T3
无环，是可串调度。
1.3 分布式事务的可串行化调度测试
1 并发控制的概念和理论可串性理论扩展
可串性理论可以 直接 扩展到无重复副本的分布式数据库中。
– 事务在每个站点上的执行调度称作 局部调度
– 如果数据库无重复副本的分布式数据库，并且每个局部调度都是可串调度，只要这些局部调度的顺序一致，则它们的并（全局调度）也是可串调度
– 但是有副本的情况下，就比较复杂。可能局部调度是可串行化的，而全局调度不是可串行化的。
1.3 分布式事务的可串行化调度测试
1 并发控制的概念和理论
保证只产生可串行化调度的机制
并发控制机制分类
– 按分配模式 (数据方式 )
完全复制的 DB
部分复制 DB或分片的 DB
– 按网络类型 (通信方式 )
广播能力的
星型网,环形网
– 同步化原则
建立在相互排斥地访问共享数据基础上的算法
通过一些准则 (协议 )对事务进行排序的算法
悲观并发控制法（事务是相互冲突的），乐观并发控制法
（没有太多的事务相互冲突）
1.4 并发控制机制的常用方法及其分类
1 并发控制的概念和理论并发控制算法悲观法 乐观法加锁法集中式加锁分布式加锁时标排序法 混合法 加锁法 时序排序法主副本加锁基本时标排序保守时标排序多版本时标排序并发控制算法的分类
封锁法
– 事 务的同步化是通过对数据库的片断或者数据项进行物理或逻辑封锁来实现的
– 封锁对象的大小通常称为封锁粒度
– 封锁方法的类型可以根据在哪里进行封锁来进一步细分
封锁法分类
– 集中式封锁方法
一个站点被指定为主站点，存放对整个数据库的封锁表，
并且负责对全系统事务进行封锁
– 主副本封锁法：主副本所在站点封锁
– 分布式封锁法：网络中的站点共享锁的管理
1.4 并发控制机制的常用方法及其分类
1 并发控制的概念和理论基本思想和概念
基本思想
– 事务访问数据项之前要对该数据项封锁，如果已经被其他事务锁定，就要等待，直到哪个事务释放该锁为止
锁的粒度
– 锁定数据项的范围
– 数据项层次
一条数据库记录
数据库记录中的一个字段值
一个磁盘块（页面）
一个完整的文件
整个数据库
2.1 基于封锁的并发控制方法概述
2 分布式数据库系统并发控制机制的封锁技术基本思想和概念
粒度对并发控制的影响
– 大多数 DBMS缺省设置为记录锁或页面锁
– 粒度小，并发度高，锁开销大
数据项比较多，锁也多，解锁和封锁操作多，锁表存储空间大（如存储读写时间戳）
– 粒度大，并发度低，锁开销小
如果是磁盘块，封锁磁盘块中的一条记录 B的事务 T必须封锁整个磁盘块
而另外一个事务 S如果要封锁记录 C,而 C也在磁盘块中，由于磁盘块正在封锁中,S只能等待
如果是封锁粒度是一条记录的话，就不用等待了
2.1 基于封锁的并发控制方法概述
2 分布式数据库系统并发控制机制的封锁技术基本思想和概念
如何来确定粒度
– 取决于参与事务的类型
– 如果参与事务都访问少量的记录，那么选择一个记录作为粒度较好
– 如果参与事务都访问同一文件中大量的记录，
则最好采用块或者文件作为粒度
2.1 基于封锁的并发控制方法概述
2 分布式数据库系统并发控制机制的封锁技术
锁的类型：
– 共享锁,Share锁,S锁或者读锁
– 排它锁,eXclusive锁,X锁，拒绝锁或写锁。
– 更新锁,Update锁,U锁
锁的选择：
– 数据项既可以读也可以写,则要用 X锁
– 如果数据项只可以读,则要用 S锁,
2.1 基于封锁的并发控制方法概述
2 分布式数据库系统并发控制机制的封锁技术基本思想和概念
锁的操作
– Read_lock(x):读锁
– Write_lock(x)：写锁
– unlock(x)：解锁
数据项的状态
– read_locked,读 锁
– Write_locked:写锁
具体操作方法
– 在系统锁表中记录关于锁的信息
– 锁表中每条记录有四个字段,<数据项名称，锁状态，读锁的数目，
正在封锁该数据项的事务 >
– 锁状态是上面两种，没有被封锁的数据项，在系统表中没有记录
2.1 基于封锁的并发控制方法概述
2 分布式数据库系统并发控制机制的封锁技术基本思想和概念
封锁准则：
– 事务 T在执行任何 read_item（ x）操作之前，必须先执行 read_lock(x)或者 write_lock(x)操作
– 事务 T在执行任何 write_item（ x）操作之前，必须先执行 write_lock(x)操作
– 如果事务 T执行 read_lock(x)操作,数据项 x必须没有加锁或者已经加了读锁，否则事务 T的这个操作不能进行
– 如果事务 T执行 write_lock(x)操作,数据项 x必须没有加锁，
否则事务 T的这个操作不能进行
2.1 基于封锁的并发控制方法概述
2 分布式数据库系统并发控制机制的封锁技术封锁准则和锁的转换
封锁准则：
– 事务 T在完成所有 read_item（ x）和 write_item（ x）操作之后，必须执行 unlock(x)操作
– 如果事务 T已经持有数据项 x上的一个读锁或者一个写锁，那么它不能再执行 read_lock(x)操作
– 如果事务 T已经持有数据项 x上的一个读锁或者一个写锁，那么它不能再执行 write_lock(x)操作
– 如果事务 T没有持有数据项 x上的一个读锁或者一个写锁，那么它不能执行 unlock(x)操作
2.1 基于封锁的并发控制方法概述
2 分布式数据库系统并发控制机制的封锁技术封锁准则和锁的转换
锁的转换
1,特定条件下，一个已经在数据项 x上持有锁的事务 T,
允许将某种封锁状态转换为另外一种封锁状态
2,比如，一个事务先执行了 read_lock（ x）操作，然后他可以通过执行 write_lock(x)操作来升级该锁
3,同样，一个事务先执行了 write_lock(x) 操作，然后他可以通过执行 read_lock（ x） 操作来降级该锁
2.1 基于封锁的并发控制方法概述
2 分布式数据库系统并发控制机制的封锁技术封锁准则和锁的转换
2.1 基于封锁的并发控制方法概述
2 分布式数据库系统并发控制机制的封锁技术
T1 T2
read_lock(Y);
read_item(Y);
unlock(Y);
write_lock(X);
read_item(X);
X:= X+Y;
write_item(X);
unlock(X);
read_lock(X);
read_item(X);
unlock(X);
write_lock(Y);
read_item(Y);
Y,= Y + X;
write_item(Y);
unlock(Y);
（ a）两个事务 T1和 T2
初始值,X=20,Y=30
串行调度 T1,T2的结果,X=50,Y=80
串行调度 T2,T1的结果,X=70,Y=50
（ b） T1和 T2可能的串行调度的结果
T1 T2
read_lock(Y);
read_item(Y);
unlock(Y);
write_lock(X);
read_item(X);
X:= X+Y;
write_item(X);
unlock(X);
read_lock(X);
read_item(X);
unlock(X);
write_lock(Y);
read_item(Y);
Y,= Y + X;
write_item(Y);
unlock(Y);
这个调度 S的结果：
X=50,Y=50
(不可串行化 )
（ c）使用锁的一个不可串行化调度的结果满足封锁规则不能保证产生串行化调度
简单的分布式封锁方法
– 类似集中式，将同一数据的全部副本封锁，然后更新，之后解除全部封锁
– 缺点是各站点间进行相当大的数据传输，如果有 N个站点，就有：
N个请求封锁的消息
N个封锁授权的消息
N个更新数据的消息
N个更新执行了的消息
N个解除封锁的消息
2.1 基于封锁的并发控制方法概述
2 分布式数据库系统并发控制机制的封锁技术分布式数据库基本封锁算法
主站点封锁法
– 定义一个站点为主站点，负责系统全部封锁管理
– 所有站点都向主站点提出封锁和解锁请求，由它去处理
– 缺点有：
所有封锁请求都送往单个站点，容易由于超负荷造成,瓶颈,
主站点故障造成会使系统瘫痪，封锁消息都在这里，制约了系统可用性和可靠性
2.1 基于封锁的并发控制方法概述
2 分布式数据库系统并发控制机制的封锁技术分布式数据库基本封锁算法
主副本封锁法
– 不指定主站点，指定数据项的主副本
– 事务对某个数据项进行操作时，先对其主副本进行封锁，再进行操作
– 主副本封锁，意味着所有的副本都被封锁
– 主副本按使用情况，尽量就近分布
– 可减少站点的负荷,使得各站点比较均衡
– 可减少传输量
快照方法
– 和上一章讲的类似
2.1 基于封锁的并发控制方法概述
2 分布式数据库系统并发控制机制的封锁技术分布式数据库基本封锁算法基本 2PL协议
如果一个事务所有的封锁操作（读写）都在第一个解锁操作之前，那么它就遵守 2PL协议
事务的执行中 Lock的管理分成两个阶段
– 上升阶段 (成长阶段 )：获取 Lock阶段（只能获取锁）
– 收缩阶段 (衰退阶段）：释放 Lock阶段（只能解锁）
封锁点是指事务获得了它所要求的所有锁，并且还没有开始释放任何锁的时刻
如果允许锁的转换，锁的升级必须在成长阶段进行，锁的降级必须在锁的衰退阶段进行。
2PL可以保证事务执行的可串行性,
2.2 2PL协议（两阶段封锁协议）
2 分布式数据库系统并发控制机制的封锁技术开始 加锁点 结束事务执行过程获得锁释放锁两阶段封锁协议
2.2 基本 2PL协议
2 分布式数据库系统并发控制机制的封锁技术
基本 2PL协议实现的难点
– 锁管理器必须要知道事务的锁点位置
级联撤销 (cascading aborts)
– 如果事务在开始释放 Lock后又 Abort时,将引起级联撤销 (cascading aborts)
（其他访问这个数据项的事务也被撤销）
保守 2PL
– 要求事务在开始执行之前就持有所有它要访问的数据项上的锁
– 事务要预先声明它的读集和写集
大多数 2PL调度器实现的是严格 2PL(S2PL)
– 事务在提交或者撤销之前，绝对不释放任何一个写锁
– 事务结束时（提交或者撤销），同时释放所有的锁
2.2 2PL协议
2 分布式数据库系统并发控制机制的封锁技术
严酷 2PL
– 事务 T在提交或撤销之前，不能释放任何一个锁（写锁或者读锁），
因此它比严格 2PL更容易实现
保守 2PL与严酷 2PL之间的区别
– 前者，事务必须在开始之前封锁它所需要的所有数据项，因此，
一旦事务开始就处在收缩阶段
– 后者,直到事务结束（提交或者撤销）后才开始解锁，因此，事务一直处于扩张阶段，直到结束
2.2 2PL协议
2 分布式数据库系统并发控制机制的封锁技术开始 结束事务执行阶段获得锁释放锁严格 2PL(Strict Two-phase Locking)协议数据项使用
2.2 2PL协议
2 分布式数据库系统并发控制机制的封锁技术
并发控制子系统
– 可以负责产生读锁和写锁操作（以严格 2PL协议为例）
– 当事务 T发出 read_item(x)操作请求时，系统会代表 T调用 read_lock(x)操作
– 如果 Lock(x)的状态是被另外一个事务 T’持有写锁，那么系统会把 T放到数据项 X的等待队列中；否则，系统同意 read_lock(x)的请求，从而允许事务 T执行 read_item(x)
操作
– 另外一个方面，如果事务 T发出 write_item（ x）操作请求时，系统会代表 T调用
write_lock(x)操作
– 如果 Lock(x)的状态是被另外一个事务 T’持有读锁或写锁，那么系统会把 T放到数据项 X的等待队列中；
– 如果 Lock(x)的状态是读锁，并且事务 T本身就是持有 x上的读锁的唯一事务，那么系统将该锁升级为写锁，并且允许 T执行 write_item(x)操作
– 如果 Lock(x)的状态是没有锁，那么系统同意 write_lock(x)的请求，进而允许事务 T
执行 write_item(x)操作
2.2 2PL协议
2 分布式数据库系统并发控制机制的封锁技术集中式 2PL的实现方法
2PL很容易扩展到分布式 DBMS(无论复制或无复制
DDB),
其最简单的方法是选择一个站点 (主站点 )做 Lock管理器,其他站点上的事务管理器都需要与该选出的站点
Lock管理器通信,而不是与本站点 Lock管理器通信,
这就是集中式 2PL方法
2.3 2PL协议的实现方法
2 分布式数据库系统并发控制机制的封锁技术
术语
– 协调事务管理器 (coordinating TM),
事务原发站点
– 数据处理器 (data processor,DP),其他参与站点
– 中心站点 LM,主站点锁管理器
2.3 2PL协议的实现方法
2 分布式数据库系统并发控制机制的封锁技术参与站点的数据处理器 协调 TM 中心站点 LM
加锁请求
①
②
③
④
⑤
允许加锁操作操作结束释放封锁集中式 2PL的通信结构中心站点
LM不需要向 DP发送操作
2.3 2PL协议的实现方法
2 分布式数据库系统并发控制机制的封锁技术集中式 2PL的实现方法主副本 2PL的实现方法
是主站点 2PL的直接扩展
– 选择一组站点做 Lock管理器
– 每个 Lock管理器管理一组数据 (即每个数据选择一个站点作自己的 Lock管理器 )
– 事务管理器根据 Lock申请的数据对象分别向这些数据的 LM发出锁申请
– 必须先为每一个数据项确定一个主副本站点，然后再向那个站点上的封锁管理程序发送封锁或释放锁的请求，目录的思想
为分布式 INGRES版本提出的，每个站点上要有一个复杂的目录
2.3 2PL协议的实现方法
2 分布式数据库系统并发控制机制的封锁技术
特点
– 每个站点都有 LM
– 无副本 DDB上如同主副本 2PL
– 有冗余副本 DDB上则使用 ROWA控制协议
与集中式相似，但有不同
– 集中式中向中心站点封锁管理程序发送的信息，在分布式中 发送给所有参与站点的封锁管理程序
– 另外不同之处在于操作并不通过协调者事务管理程序传到数 据处理器，而是通过参与者的封锁管理程序
– 参与者的数据处理器向协调者的事务管理程序发送“操作结 束”信息
– 另外一种方法，每个数据处理器执行自身解锁，并通知协调者事务管理程序的封锁管理程序
2.3 2PL协议的实现方法
2 分布式数据库系统并发控制机制的封锁技术分布式 2PL的实现方法参与者 DPs
①
②
加锁请求操作分布式 2PL的通信结构协调者 TM 参与者 LMs
③
操作结束释放锁
④
2.3 2PL协议的实现方法
2 分布式数据库系统并发控制机制的封锁技术分布式 2PL的实现方法
多粒度封锁
– 封锁的粒度不是单一的一种粒度，而是有多种粒度
– 可以定义多粒度树，根节点是整个数据库，叶节点表示最小的封锁粒度
直接封锁
– 事务对要进行读 /写的数据对象直接申请加锁
分层封锁
– DB中各数据对象从大到小存在一种层次关系,例如划分为 DB,段,关系,元组,字段等
– 当封锁了外层数据对象时,蕴含着也同时封锁了它的所有内层数据对象
– 数据项的显式封锁和隐式封锁
2.4 多粒度封锁与意向锁
2 分布式数据库系统并发控制机制的封锁技术数据库段 1 段 n
元组 元组 元组元组
….
多级粒度树关系 nn关系 11 ……...
……...
2.4 多粒度封锁与意向锁
2 分布式数据库系统并发控制机制的封锁技术
2.4 多粒度封锁与意向锁
2 分布式数据库系统并发控制机制的封锁技术
db
f1 f2
p11 P12……,p1n
r111…r11j r121…r12j …… r1n1…r1nj
p21 P22……,p2n
r211…r21j r221…r22j …… r2n1…r2nj
用来说明多粒度级别封锁的粒度层次结构
例子
– 假定事务 T1要更新文件 f1中的所有记录,T1请求并获得了 f1上的一个写锁
– 那么 f1下面的页面和记录就获得了隐式写锁
– 如果这时候，事务 T2想从 f1中的某个页面中读某个记录，那么 T2就要申请该记录上的读锁
– 但是要确认这个读锁和已经存在锁的相容性，
确认的方法就是要遍历该树：从记录到页，到文件最后到数据库，如果在任意时刻，在这些项中的任意一个上存在冲突锁，那么对记录的封锁请求就被拒绝,T2被阻止，要等待。
2.4 多粒度封锁与意向锁
2 分布式数据库系统并发控制机制的封锁技术
意向锁
– 如果对一个节点加意向锁，则说明该节点的下层节点正在被封锁
– 对任一节点封锁时，必须先对它的上层节点加意向锁
意向锁的类型
– 意向共享锁 (IS)：指示在其后代节点上将会请求共享锁，即如果对某个对象加 IS锁，表示它的后代节点拟加共享锁
– 意向排它锁 (IX)：指示在其后代节点上将会请求排他锁，即如果对某个对象加 IX锁，表示它的后代节点拟加排他锁
– 共享意向排它锁 (SIX)：指示当前节点处在共享方式的封锁中，但是在它的某些后代节点中将会请求排他锁。即如果对一个数据对象加 SIX锁,表示对它加共享锁，再加 IX锁（ SIX=S+IX）。例如：对某个表加 SIX锁，则表示该事务要读整个表（加 S锁），同时会更新个别元组（加 IX锁）
2.4 多粒度封锁与意向锁
2 分布式数据库系统并发控制机制的封锁技术
T2
T1
YYYYYY-
YNNYNNSIX
YNYYNNIX
YYYYNYIS
YNNNNNX
YNNYNYS
-SIXIXISXS
X
SIX
S IX
IS
Y=yes，表示相容的请求 N=no，表示不相容的请求
(a)数据锁的相容矩阵
(b)锁的强度的偏序关系锁的相容矩阵
2.4 多粒度封锁与意向锁
2 分布式数据库系统并发控制机制的封锁技术锁的强度：对其它锁的排斥程度
多粒度封锁协议的规则
– 必须遵守锁的相容性规则
– 必须首先封锁树的根节点，可以用任何一种方式的锁
– 只有当节点 N的父节点已经被事务 T以 IS或 IX方式封锁后，节点 N
才可以被 T以 S或者 IS方式封锁
– 只有当节点 N的父节点已经被事务 T以 IX或 SIX方式封锁后，节点 N
才可以被 T以 X,IX或者 SIX方式封锁
– 只有当事务 T还没有释放任何节点时,T才可以封锁一个节点
– 只有当事务 T当前没有封锁节点 N的任何子节点时,T才可以为节点 N解锁。
2.4 多粒度封锁与意向锁
2 分布式数据库系统并发控制机制的封锁技术
总结
– 具有意向锁的多粒度加锁方法中，任意事务 T要对一个数据对象加锁，必须先对它的上层节点加意向锁
– 申请封锁时应该按自上而下的次序进行
– 释放锁时则应该按自下而上的次序进行
– 具有意向锁的多粒度加锁方法提高了系统的并发度,减少了加锁和释放锁的开销
– 它已经在实际的 DBMS系统中广泛应用，例如 Oracle中
2.4 多粒度封锁与意向锁
2 分布式数据库系统并发控制机制的封锁技术
死锁发生的条件
– 互斥条件：事务请求对资源的独占控制
– 等待条件：事务已持有分配给它的资源,又去申请并等待别的资源
– 非抢占条件：直到资源被持有它的事务释放前,
不可能将资源强制从持有它的事务夺去
– 循环等待条件：存在事务互相等待的等待圈
死锁分类
– 局部死锁：仅在一个站点上发生的死锁
– 全局死锁：涉及多个站点的死锁 (即等待圈由多个站点组成 )
3.1 全局死锁与等待图
3 分布式数据库系统中的死锁处理事务 T1持有对 x的锁事务 T2请求对 x的锁事务 T2持有对 y的锁事务 T1请求对 y的锁站点 A 站点 B
T2等待 T1完成释放对 x的锁
T1等待 T2完成释放对 y的锁相互等待引起的全局死锁
3.1 全局死锁与等待图
3 分布式数据库系统中的死锁处理
T1
T2
T3
站点 A,x1,y1
站点 C,z3
站点 B,y2,z2
等待释放对 y 的锁等待释放对 x 的锁 等待释放对 z 的锁站点 A：存储 x和 y的副本,发出事务 T1,read(x),write(y)
站点 B：存储 y和 z的副本,发出事务 T2,read(y),write(z)
站点 C：存储 z的副本,发出事务 T3,read(z),write(x)
多副本引起的三个站点间的死锁
3.1 全局死锁与等待图
3 分布式数据库系统中的死锁处理
等待图
– 一种用来表示事务之间相互等待关系的有向图,是分析死锁的有用工具
– 节点表示事务
– 带有箭头的有向边表示“等待”关系
– 如果等待图有回路，就说明有死锁
等待图分类
– 局部等待图 (LWFG)
– 全局等待图 (GWFG)
3.1 全局死锁与等待图
3 分布式数据库系统中的死锁处理
T1
T3
T2
y
x
z T1等待 T2释放对 y的共享锁 (s)
T2等待 T3释放对 z的共享锁 (s)
T3等待 T1释放对 x的共享锁 (s)
上例的 GWFG等待图
3.1 全局死锁与等待图
3 分布式数据库系统中的死锁处理
(a)
(b)
T2
T1
T1
T2
T4
T3
T4
T3
站点 1 站点 2
LWFG和 GWFG之间的不同
3.1 全局死锁与等待图
3 分布式数据库系统中的死锁处理事务间的等待关系
T1→T2→T3→T4
解决死锁的方法
– 死锁预防，使引起死锁的必要条件不成立
所有资源排序,按资源序列申请
将所有并发事务排序,按标识符或开始时间
有死锁危险时，事务退出已占有的资源，有两种方法
– 等待 -死亡 (Wait-Die)：总是重启较年轻的事务 (非占先权 )
– 受伤 -等待 (Wound-Wait),年轻的等待年老的,较年轻的重启,而重启事务并不一定是目前正申请的事务 (占先权 )
– 死锁检测
即检测死锁时循环等待的圈
3.2 死锁的预防方法
3 分布式数据库系统中的死锁处理
等待 -死亡模式
– 如果 Ti对已被 Tj封锁的一数据项请求封锁的话，则只有在 Ti比 Tj年老时（ Ti<Tj），才允许 Ti等待
– 如果 Ti比 Tj年轻（ Ti>Tj），则 Ti被终止并带有同一时间戳重新启动
– 最好总是重新启动较年轻的事务
– 允许较年老的事务去等待已持有资源的较年轻的事务
– 但不允许较年轻的事务去等待较年老的事务
受伤 -等待模式
– 如果 Ti对已被 Tj封锁的一数据项请求封锁的话，则只有在 Ti比 Tj年轻时（ Ti>Tj），才允许 Ti等待
– 否则,Ti比 Tj年老（ Ti<Tj），则 Tj被终止并带有同一时间戳重新启动,而 Ti得锁执行
– 只有年轻的等待年老的
3.2 死锁的预防方法
3 分布式数据库系统中的死锁处理
集中式死锁检测
– 选择一个站点负责整个系统的死锁检测,死锁检测器放到这个站点
– 每个站点的锁管理器周期性地将本站点的 LWFG传送给死锁检测器,死锁检测器构造 GWFG,并在其中寻找回路
– 或者，其它每个站点上的锁管理器周期性地把记录本站点上事务的开始时间，
对锁的持有、请求情况变化的动态表，发送给负责处理封锁的站点，由它维护一张全局封锁动态表，形成 GWFG,并在其中寻找回路
– 如果至少包含一条回路，它会选择一个或者多个事务，把它们取消并恢复，
释放资源，使得其它事务继续进行。
– 选择的标准是尽可能使撤销并恢复的代价最小，如撤销年轻的事务，撤销占有较少、资源的事务，撤销具有最短运行时间的事务，撤销具有最长运行时间的事务等，使系统情况而定
3.3 死锁的检测和解决方法
3 分布式数据库系统中的死锁处理
层次式死锁检测
– 以层次方式组织成员 DBMS中的死锁检测器
– 死锁发生时,常常只涉及部分站点
– 层次检测的层次结构与网络拓扑结构有关
– 减少了对中心站点的依赖性，从而减少了传输开销
3.3 死锁的检测和解决方法
3 分布式数据库系统中的死锁处理
层次式死锁检测的步骤
– 树叶是各站点的局部死锁检测器，在本站点建立局部等待图
– 本站点的死锁检测器找出本站点局部等待图中的任何回路，
并把有关潜在全局回路的信息发送给上一层死锁检测器
– 每个非本地死锁检测器只对它所涉及的紧挨下层进行死锁检测，合并这些接收到的有关潜在全局回路的信息，并找出任何回路
– 如果还有上层死锁检测器，将经过简化的有关潜在全局回路的信息发送给它上一层死锁检测器，由上一层死锁检测器再进行合并，找出任何全局回路
– 这样，逐层检测，直到最高层。
3.3 死锁的检测和解决方法
3 分布式数据库系统中的死锁处理第 0层死锁检测器第 i层死锁检测器第 i层死锁检测器局部死锁检测器局部死锁检测器局部死锁检测器局部死锁检测器简化潜在死锁图简化潜在死锁图简化潜在死锁图简化潜在死锁图简化潜在死锁图简化潜在死锁图层次式死锁检测方法示意图
3.3 死锁的检测和解决方法
3 分布式数据库系统中的死锁处理
分布式检测
– 每个站点的检测死锁责任相同,站点之间交换信息
(LWFG)，是为了确定全局死锁
– EX是指的本地事务正在等待的其他事务所在的还不确定的站点
– 例子 站点 1 站点 2
T1
T2
T4
T3
EX
EX
3.3 死锁的检测和解决方法
3 分布式数据库系统中的死锁处理
信息传递方向 此处规定一种,以避免多次重复传递
– EX等待的事务号 > 等待 EX的事务号
分布式死锁检测算法
– 使用局部信息建造 LWFG,该 LWFG包含 EX节点
– 对每次接收到的信息,执行如下对 LWFG的修改
对报文中的每个事务,若 LWFG中不存在,则将其加入
从 EX节点开始,按照报文所给的信息,建立一个到下一个事务的边
– 在新的 LWFG中寻找不含 EX的 Loop,若存在,则检测到死锁
– 在新的 LWFG中找到含有 EX的 Loop,于是有潜在的死锁,再按规定向外传送信息
3.3 死锁的检测和解决方法
3 分布式数据库系统中的死锁处理
基本概念
– 不通过互斥来支持串行性，而是通过在事务启动时赋给时标（时间戳）来实现
– 时标是用来唯一识别每个事务并允许排序的标识
– 如果 ts(T1) < ts(T2) … < ts(T n),则调度器产生的序是,
T1,T2,..,Tn
规则
– 如果 T1的操作 O1(x)和 T2的操作 O2(x)是冲突操作,那么,
O1在 O2之前执行,当且仅当 ts(T1)<ts(T2)
4.1 基于时标的并发控制方法
4 分布式数据库系统并发控制的时标技术
时标分配方法
– 全局时标
使用全局的单调递增的计数器
全局的计数器维护是个难题
– 局部时标
每个站点基于其本地计数器自治地指定一个时标
标识符由两部分组成,〈 本地计数器值，站点标识符 〉
– 站点标识符是次要的，主要是本地计数器值
– 可以使用站点系统时钟来代替计数器值
4.1 基于时标的并发控制方法
4 分布式数据库系统并发控制的时标技术
时标法思想
– 每个事务赋一个唯一的时标，事务的执行等效于按时标次序串行执行
– 如果发生冲突，是通过撤销并重新启动一个事务来解决的
– 事务重新启动时，则赋予新的时标
– 优点是没有死锁，不必设置锁
– 封锁和死锁检测引起的通信开销也避免了
– 但要求时标在全系统中是唯一的
4.1 基于时标的并发控制方法
4 分布式数据库系统并发控制的时标技术
时标性质
– 唯一性
– 单调性
全局唯一时间的形成与调整
– 每个站点设置一个计数器,每发生一个事务,计数器加一
– 发送报文时包含本地计数器值,近似同步各站点计数器
4.1 基于时标的并发控制方法
4 分布式数据库系统并发控制的时标技术
4.1 基于时标的并发控制方法
4 分布式数据库系统并发控制的时标技术计数器 X 初值 X=0 计数器 Y 初值 Y=10
站点 1 站点 2
时标 A D 时标
TS(A)=<1,1> TS(D)=<11,2>
因为 X<Y E TS(E)=<12,2>
改 X=Y+1=11 B
TS(B)=<11,1> F 因为 Y>X
TS(C)=<12,1> C TS(F)=<13,2>
本地计数器 本地计数器
(或时钟 ) (或时钟 )
报文 1
报文 2
计数器站点基本时标法
规则
– 每个事务在本站点开始时赋予一个全局唯一时标
– 在事务结束前，不对数据库进行物理更新
– 事务的每个读操作或写操作都具有该事务的时标
– 对每个数据项 x,记下写和读操作的最大时标，记为
WTM(x)和 RTM(x)
– 如果事务被重新启动，则被赋予新的时标
4.2 基本时标法
4 分布式数据库系统并发控制的时标技术
基本时标法执行过程
– 令 read_TS是事务对 x进行读操作时的时标
若 read_TS<WTM(x)，则拒绝该操作,事务重新启动
否则,执行,令 RTM(x)=max{RTM(x),read_TS}
– 令 write_TS是事务对 x进行写操作时的时标
若 write_TS < RTM(x) 或 write_TS < WTM(x),则拒绝该操作,事务重新启动
否则,执行,令 WTM(x) = max{WTM(x),write_TS}
缺点是重启动多
4.2 基本时标法
4 分布式数据库系统并发控制的时标技术
基本思想
– 一种消除重启动的方法
– 通过缓冲年轻的操作，直至年长的操作执行完成，因此操作不会被拒绝，事务也绝不被重启动
规则
– 每个事务只在一个站点执行,它不能激活远程的程序,但是可以向远程站点发读 /写请求
– 站点 i接收到来自不同站点 j的读 /写请求必须按时标顺序，
即每个站点必须按时标顺序发送读 /写数据请求，在传输中也不会改变这个顺序
– 每个站点都为其它站点发来的读 /写操作开辟一个缓冲区,
分别保存接收到的读 /写申请
4.3 保守时标法
4 分布式数据库系统并发控制的时标技术
假定某个站点 k上,各个缓冲区队列都已不为空，即每个站点都已向它至少发送了一个读和一个写操作，就停止接收，处理在缓冲区中的操作
假定站点 i至少有一个缓冲的读和缓冲的写来自网中其它站点,根据规则 2,Site i 知道没有年老的请求来自其它 Site(因为按序接收,所以不可能有比此更年老的请求到来,年老的比年轻的先到 )
4.3 保守时标法
4 分布式数据库系统并发控制的时标技术例子已知站点 i的缓冲区队列中有来自所有站点的读 /写请求如下所示,
站点 1 站点 2 站点 3 …… 站点 n
R11 R21 R31 Rn1
R12 R22 R32
R13 R23
R24
W11 W21 W31 …… Wn1
W22 W32 … Wn2
W23
4.3 保守时标法
4 分布式数据库系统并发控制的时标技术执行步骤,
(1) 设 RT=min(Rij),WT= min(Wij)
(2) 按下法处理缓冲区中的 Rij和 Wij
a,若队列中有
(Rij) < WT的 Rij,则顺序执行这些 Rij，执行完删掉
b,若队列中有
(Wij) < RT的 Wij,则顺序执行这些 Wij，执行完删掉
(3) 修改 RT=min(Rij),WT=min(Wij),此时的 Rij和 Wij是队列中剩余的
(4) 重复上述 (2)和 (3),直到没有满足条件的操作,或者,
a,若某个或某些 R队列为空时,RTM=0;
b,若某个或某些 W队列为空时,WTM=0
4.3 保守时标法
4 分布式数据库系统并发控制的时标技术存在问题和解决方法
– 如果一个站点从来不向某个站点发送操作的话，那么执行过程中的假定就不符合，操作就无法进行。解决办法是，周期性的发送带有时标的空操作
– 此方法要求网络上所有站点都连通，这在大系统中很难办到。为避免不必要的通信，可对无读写操作请求的站点，发送一个时标很大的空操作
– 此方法过分保守，一律按照时序来进行，其中包括了不冲突的操作
4.3 保守时标法
4 分布式数据库系统并发控制的时标技术
基本思想
– 保存了已更新数据项的旧值
– 维护一个数据项的多个版本
– 通过读取数据项的较老版本来维护可串行性，使得系统可以接受在其他技术中被拒绝的一些读操作
– 写数据项时，写入一个新版本，老版本依然保存
缺点
– 需要更多的存储来维持数据库数据项的多个版本
模式分类
– 基于时标排序
– 基于两阶段封锁
5.1 多版本概念和思想
5 分布式数据库系统并发控制的多版本技术
数据项 X的多版本
– X1,X2,X3,…,Xk
系统保存的值
– Xi的值
– 两种时标
Read_TS(Xi),读时标，成功读取版本 Xi的事务的时标，
最大的一个
Write_TS(Xi),写时标，写入版本 Xi的值的事务的时标
5.2 基于时标的多版本技术
5 分布式数据库系统并发控制的多版本技术
多版本规则
– 如果事务 T发布一个 write_item(X)操作，并且 X的版本 Xi
具有 X所有版本中最高的 write_TS(Xi),同时
write_TS(Xi)<=TS(T)且 read_TS(Xi)>TS(T)，那么撤销并回滚 T；否则创建 X的一个新版本，并且令 read_TS(Xi)=
write_TS(Xi)= TS(T)
– 如果事务 T发布一个 read_item(X)操作，并且 X的版本 Xi
具有 X所有版本中最高的 write_TS(Xi),同时
write_TS(Xi)<=TS(T)，把 Xi的值返回给事务 T,并且将
read_TS(Xi)的值置为 TS(T)和当前 read_TS(Xi)中较大的一个
5.2 基于时标的多版本技术
5 分布式数据库系统并发控制的多版本技术图示写值
v1 v2 v3 … Vn-1 Vn
5 10 20 92 100
若读 TS(Ri)=95,则读 <92,Vn-1> 的值若写 TS(Wk)=93,则出现了
v1 v2 v3 … Vn-1 Vn
5 10 20 92 10093
v
于是要拒绝 TS(Wk),否则 TS(Ri)=95读的就是 Vn-1,而不是 v
的值,但是按规定 TS(Ri)=95应该读的是 v值
三种锁方式
– 读，写，验证
四种锁状态
– 读封锁（ read_locked）
– 写封锁（ write_locked）
– 验证封锁（ certify_locked）
– 未封锁（ unlocked）
锁相容性
– 标准模式锁相容性（写锁和读锁）
– 验证模式锁相容性（写锁、读锁和验证锁）
5.3 采用验证锁的多版本两阶段封锁
5 分布式数据库系统并发控制的多版本技术
5.3 采用验证锁的多版本两阶段封锁
5 分布式数据库系统并发控制的多版本技术
(a) 读 /写封锁模式的相容性表读 写读写是 否否 否读 写 验证读写是 是 否是 否 否验证 否 否 否
(b) 读 /写 /验证封锁模式的相容性表
多版本 2PL的思想
– 当只有一个单独的事务 T持有数据项上的写锁时，允许其他事务 T’读该项 X，这是通过给予每个项 X的两个版本来实现的
一个版本 X是由一个已提交的事务写入的
另一个版本 X’是每个事务 T获得该数据项上写锁时创建的、
– 当事务 T持有这个写锁时，其他事务可以继续读 X的已提交版本
– 事务 T可以写 X’的值，而不影响 X已提交版本的值
– 但是，一旦 T准备提交，它必须在能够提交之前，得到持有写锁的数据项上的验证锁，要等写锁释放之后
– 一旦获得验证锁，数据项的已提交版本 X被置为版本 X’
的值，版本 X’被丢弃，验证锁被释放。
5.3 采用验证锁的多版本两阶段封锁
5 分布式数据库系统并发控制的多版本技术
基本思想
– 对于冲突操作不像悲观方法那样采取挂起或拒绝的方法，而是让一个事务执行直到完成
基于如下假设
– 冲突的事务是少数（查询为主的系统中，冲突少于 5%）
– 大多数事务可以不受干扰地执行完毕
6.1 基本思想和假设
6 分布式数据库系统并发控制的乐观方法
6.2 执行阶段划分
6 分布式数据库系统并发控制的乐观方法验证 读 /计算 写 /提交读 /计算 验证 写 /提交乐观法事务执行的各个阶段悲观法事务执行的各个阶段
事务的三个阶段
– 读段 /计算,在数据对象的局部副本上执行事务，这时其他事务不能存取此副本。事务从 DB读数据，执行计算，并且确定写集数据项的新值。写操作总是对局部副本，仅当验证通过后，在事务结束处，才将其写入
DB。
– 验证段,检验并发事务的可串性，该阶段验证修改应用是否引起完整性（一致性）的丢失，验证阶段通过，
才能进入写段，否则事务重启动
– 写段 /提交,验证阶段通过，则把事务的更新应用于数据库，对数据进行更新，否则，忽略所有更新，并重新开始该事务
6.2 执行阶段划分
6 分布式数据库系统并发控制的乐观方法
验证
– 使用数据项和事务上的时标
– 只使用事务时标
6.3 验证分类
6 分布式数据库系统并发控制的乐观方法
使用数据项和事务上的时标
– 假设是一个 完全冗余的 DB，事务在读期间把更新写入一个更新表
– 事务时标,事务在启动执行时接受的具有唯一性的时标
– 数据项时标,对该数据项最后写入的事务的时间戳
– 算法假定：读集? 写集,即写必须先读
6.3 使用数据项和事务上的时标
6 分布式数据库系统并发控制的乐观方法
读阶段末，事务产生一个更新表 u，包括
– 读集的数据项，带有自身的时标
– 写集数据项的新值
– 该事务自身的时标
验证阶段
– 把更新表发送到每一站点，每个站点对是否确认该更新表进行表决，并把表决结果送回到该事务的源站点
– 如源站点收到多数肯定票，则决定事务提交并通知各站点
– 如多数表决是否定的，则把放弃更新表的决定通知所有站点，然后重新启动该事务
6.3 使用数据项和事务上的时标
6 分布式数据库系统并发控制的乐观方法
表决规则
– 比较更新表 u中数据项的时标与本地库中相应数据项的时标,全部相等则投赞成票
– 不相等,投反对派票,因为此时可能本地写入数据项之前或之后,又有事务对数据项做了写操作
表决结果
– 若赞成票是大多数,则考虑 Commit,并将结论发送给每个 Site
– 否则,其更新表无效,事务重启动
6.3 使用数据项和事务上的时标
6 分布式数据库系统并发控制的乐观方法
更新表冲突表决规则
– 比较 u表中读集中数据项的时标与数据库中对应数据项的时标，如果不等，投否定票
– 若相等,Site j在对 u表做表决时,若存在 Site k上的 u’表传送到 Site j,使 Site j处于对 u’的表决中
若 u’中有与 u冲突的更新表,当 u’中的时标大时,则反对
当 u’中的时标小时,则延迟表决
– 若与 u’中无冲突数据项,则赞成原发 Site
投票 Site j
更新表 u
DB
U’
6.3 使用数据项和事务上的时标
6 分布式数据库系统并发控制的乐观方法
事务 Tj的验证过程
– 检验由一些事务给出的执行调度是否可以成为一个按时标串行执行的调度,
参与验证的事务有,
– a> 已经提交的事务
– b> 当 Tj验证时也正处于验证的事务
– c> Tj本身
6.4 只使用事务上的时标
6 分布式数据库系统并发控制的乐观方法
对于所有 TS(Ti) < TS(Tj)的事务 Ti,Tj验证必须满足如下三个条件
– Ti在 Tj开始其读段前已完成其写段 (严格串行 )
– Ti的写集与 Tj的读集不相交,并且 Ti在 Tj开始其写段时已完成其写段 (Ti与 Tj不冲突 )
– Ti的写集与 Tj的写集不相交,并且 Ti在 Tj读段完成前已结束其读段 (写 /写不冲突 )
6.4 只使用事务上的时标
6 分布式数据库系统并发控制的乐观方法
Start(T) Finishi(T) TS(T)
验证在 Tj执行期间记录下列信息,
a> Tj的读集和写集
b> Tj启动时 TNC的值,称为 Start(Tj)
c> Tj结束其读段时的 TNC值,称为 Finish(Tj)
– TS(Tj)：只有在写段之后 (验证成功 )才把此唯一的时标赋给 Tj,仅当将 TS(Tj)赋给 Tj后,TNC值才增值,
– Finish(Tj)与 Start(Tj)无变化,说明在其执行期间没有事务完成写段
– 验证方式
集中式
分布式
6.4 只使用事务上的时标
6 分布式数据库系统并发控制的乐观方法
集中式验证
– Finish(Ti) < Finish(Tj)时
Ti写集? (Tj写集 U Tj 读集 ) =?
─TS(Ti) < Start(Tj)时,不需要验证
Ti
Tj
写 /写 冲突
─ Start(Tj) < TS(Ti) < Finish(Tj) 时
Ti写集? Tj 读集 =?
写 /读 冲突Ti
Ti
Tj
Tj
真正串行
6.4 只使用事务上的时标
6 分布式数据库系统并发控制的乐观方法
分布式验证
a> 同一个事务的每一个子事务接收同一个唯一的全局事务标识符
b> 每个站点进行每一个本地子事务的本地验证
c> 对每个子事务 Tij,在局部验证时收集信息,建立在 j站点上,
Tij之前已发出的 Ti集 HB(Tij)
d> 全局验证若 HB(Tij)中的所有事务或提交或夭折,该子事务验证通过若 HB(Tij)有未知提交 /夭折的事务,则 Tij被挂起
e> 写段：使用 2PC的思想,当事务全局验证结束,把相应报文送给该子事务的主站点上,若全部验证都肯定,则该事务提交,否则 Abort
6.4 只使用事务上的时标
6 分布式数据库系统并发控制的乐观方法总 结
并发控制的概念和理论
分布式数据库系统并发控制的封锁技术
分布式数据库系统中的死锁处理
分布式数据库系统并发控制的时标技术
分布式数据库系统并发控制的多版本技术
分布式数据库系统并发控制的乐观方法
（ mycui369@126.com)
计算机应用技术 2007级研究生
1,并发控制的概念和理论
2.分布式数据库系统并发控制的封锁技术
3.分布式数据库系统中的死锁处理
4.分布式数据库系统并发控制的时标技术
5.分布式数据库系统并发控制的多版本技术
6.分布式数据库系统并发控制的乐观方法分布式数据库中的并发控制第 5章
通常，数据库总有若干个事务在运行，这些事务可能并发地存取相同的数据，称为事务的并发操作。
当数据库中有多个事务并发执行时，系统必须对并发事务之间的相互作用加以控制，这是通过并发控制机制来实现的。
并发控制就是负责正确协调并发事务的执行，保证这种并发的存取操作不至于破坏数据库的完整性和一致性，确保并发执行的多个事务能够正确地运行并获得正确的结果。
分布式数据库中的并发控制解决多个分布式事务对数据并发执行的正确性，保证数据库的完整性和一致性。
比集中式并发控制更复杂。
1.1 并发控制的概念
1 并发控制的概念和理论集中式 DB环境
T1 T2 … Tn
DB
(一致性约束 )
1.1 并发控制的概念
1 并发控制的概念和理论分布式 DB环境
X Y Z
T1 T2
1.1 并发控制的概念
1 并发控制的概念和理论
多处理器
CPU1
CPU2
T1
T2
Time
1.1 并发控制的概念
1 并发控制的概念和理论并发执行
单处理器
T1
t1
T2
t2
T1
t3
T2
t4
Time
CPU
1.1 并发控制的概念
1 并发控制的概念和理论非并发执行
UPDATE x70t6
FIND xt2
200t7
UPDATE xt5
x:=x*2t4
x:=x-30t3
FIND xt1
100t0
更新事务 T2数据库中 X的值更新事务 T1时间注：其中 FIND表示从数据库中读值,UPDATE表示把值写回到数据库
T1T2，结果 140,T2T1,结果 170，
得到结果是 200，显然是不对的,T1在 t7丢失更新操作。
1.1 并发控制的概念
1 并发控制的概念和理论并发控制问题之一：丢失更新
FIND xt2
70t5
UPDATE xt4
x:=x-30t3
FIND xt1
100t0
更新事务 T2数据库中 A的值更新事务 T1时间注：在时间 t5事务 T2仍认为 x的值是 100
1.1 并发控制的概念
1 并发控制的概念和理论并发控制问题之二：不一致分析
100t6
x:=x-10t2
ROLLBACKt5
FIND x90t4
UPDATE xt3
FIND xt1
100t0
更新事务 T2数据库中 A的值更新事务 T1时间注,事务 T2依赖于事务 T1的未完成更新
1.1 并发控制的概念
1 并发控制的概念和理论并发控制问题之三：依赖于未提交更新（读脏数据）
事务 Ti
Ti= {?i,<i }
其中：
1,?i,操作符集合,{Ri(x),Wi(x) } U {Ai,Ci }
2,Ai,Ci 是最后的操作符，只能是其一
3,<i,(冲突 )操作有序执行,Ri(x) <i Wi(x) 或
Wi(x) <i Ri(x)
1.2 事务可串行化理论
1 并发控制的概念和理论
操作符集读 Ri(x)和写 Wi(x)动作序列
冲突动作
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)
1.2 事务可串行化理论
1 并发控制的概念和理论
T1 T2
1 (T1) a?X 5 (T2) c?X
2 (T1) X?a+100 6 (T2) X?2c
3 (T1) b?Y 7 (T2) d?Y
4 (T1) Y?b+100 8 (T2) Y?2d
先序关系例子已知：站点 1有数据 X，站点 2有数据 Y
约束,X=Y
1.2 事务可串行化理论
1 并发控制的概念和理论
(X站点 ) (Y站点 )
1 (T1) a?X
2 (T1) X?a+100
5 (T2) c?X 3 (T1) b? Y
6 (T2) X?2c 4 (T1) Y?b+100
7 (T2) d? Y
8 (T2) Y?2d
初值,X=Y=0,结果,X=Y=200
调度 S1 事务内事务间令 T= {T1,T2,…,Tn} 是一组事务,T上的调度 S 是具有如下顺序关系 <T的偏序，即 S={?T,<T},
(1)?T=? Ti
(2) <T <i
(3) 对于任意一组冲突操作 p,q?S,存在 p < q
或 q < p关系并发调度定义
i=1
N
N
i=1
1.2 事务可串行化理论
1 并发控制的概念和理论
调度
– 一组事务的调度必须包含这些事务的所有操作
– 调度中某个事务的操作顺序必须保持与该事务原有的顺序相同
串行调度
– 一个事务的第一个动作是在另一个事务的最后一个动作完成后开始,即调度中事务的各个操作不会交叉,每个事务相继执行,
一致性调度
– 调度可以使得数据库从一个一致性状态转变为另一个一致性状态，则称调度为一致性调度
1.2 事务可串行化理论
1 并发控制的概念和理论
调度等价
– S1与 S2等价,也就是说,对于冲突操作,
<Oi,Oj>,Oi < Oj在 S1中成立,同时 Oi < Oj
在 S2中也成立
可串行化调度
– 如果一个调度等价于某个串行调度，则该调度称为可串行化调度。
– 也就是说，该调度可以通过一系列非冲突动作的交换操作使其成为串行调度
1.2 事务可串行化理论
1 并发控制的概念和理论例子
两个事务，定义如下：
T1:
1,Read(x）
2,x=x+10
3,Write(x)
4,Read(y)
5,y=y-15
6,Write(y)
7,commit
1.2 事务可串行化理论
1 并发控制的概念和理论
T2:
1,Read(x）
2,x=x-20
3,Write(x)
4,Read(y)
5,y=y*2
6,Write(y)
7,commit
五种调度：
S1={R1(x),x=x+10,W1(x),R1(y),y=y-15,W1(y),C1,R2(x),x=x-
20,W2(x),R2(y),y=y*2,W2(y),C2}
S2={R1(x),x=x+10,W1(x),R2(x),x=x-20,W2(x),R1(y),y=y-
15,W1(y),C1,R2(y),y=y*2,W2(y),C2}
S3={R1(x),x=x+10,W1(x),R2(x),x=x-
20,W2(x),R2(y),y=y*2,W2(y),C2,R1(y),y=y-15,W1(y),C1}
S4={R2(x),x=x-
20,W2(x),R2(y),y=y*2,W2(y),C2,R1(x),x=x+10,W1(x),R1(y),y
=y-15,W1(y),C1}
S5={R2(x),x=x-20,W2(x),R1(x),x=x+10,W1(x),
R2(y),y=y*2,W2(y),C2,R1(y),y=y-15,W1(y),C1}
1.2 事务可串行化理论
1 并发控制的概念和理论
如果将事务提交延迟到两个事务操作完成之后执行，有：
– 调度 S1和 S4是串行调度
– 调度 S2和 S1的冲突操作具有相同的顺序，因此是等价调度； S2是可串行化调度，也是一致性调度
– 调度 S3虽是一致调度，但是它不与 S1或 S4等价，
所以 S3不是可串行化调度
– 调度 S5和 S4等价，所以 S5是一致调度，也是可串行化调度
1.2 事务可串行化理论
1 并发控制的概念和理论
有以下推论：
– 一个可串行化调度必定与某个串行调度等价，
且是一致性调度
– 一致性调度不一定是可串行化调度
– 同一事务集几个可串行化调度，他们的结果未必相同
1.2 事务可串行化理论
1 并发控制的概念和理论优先图 P(S)
调度 S 的优先图是一个有向图 G(N,E),其中
– N,一组节点 N={T1T2,…,Tn},S中的事务
– E,一组有向边 E={e1,e2,…,en},Ti? Tj 是图中的一条边，当且仅当? p? Ti,q? Tj 使得 p,q 冲突，
并且 p <S q
1.3 分布式事务的可串行化调度测试
1 并发控制的概念和理论测试调度 S的可串行化
对于调度 S中的事务 Ti，在图中创建一个节点 Ti
对于每一种这样的情形：如果 S中的在 Ti执行了 W(X)操作后执行 Tj的 R(X)操作，那么在优先图中创建一条边
（ Ti→ Tj ）
对于每一种这样的情形：如果 S中的在 Ti执行了 R(X)操作后执行 Tj的 W(X)操作，那么在优先图中创建一条边
（ Ti→ Tj ）
对于每一种这样的情形：如果 S中的在 Ti执行了 W(X)操作后执行 Tj的 W(X)操作，那么在优先图中创建一条边
（ Ti→ Tj ）
当且仅当优先图中没有闭环时，调度 S是可串行化的
1.3 分布式事务的可串行化调度测试
1 并发控制的概念和理论测试调度 S的可串行化
优先图中存在环路，说明调度是不可串行化的，否则是可串行化的。
环路是指有向图中每条边的起始节点（第一条边除外），
都与前一条边的终止节点连接，而第一条边的起始节点于最后一条边的终止节点连接，即事务序列是以同一个节点作为开始和结束的
调度 S中事务 Ti在事务 Tj之前，与 S等价的调度中 Ti也必须在 Tj之前
某项数据导致了调度中的一条边的生成，就把数据项标注到优先图中这条边的旁边
如果调度 S中不存在环路，那么就可能存在若干个与 S等价的串行调度
1.3 分布式事务的可串行化调度测试
1 并发控制的概念和理论
1.3 分布式事务的可串行化调度测试
1 并发控制的概念和理论
T1
T2
T1
T2
T1
T2
T1
T2
T1
T2
S1的优先图 S2的优先图 S3的优先图 S4的优先图 S5的优先图
X Y X Y X Y X Y X Y
存在环路举例
考虑如下 3个事务：
T1,Read(x); Write(x); Commit;
T2,Write(x); Write(y); Read(z); Commit;
T3,Read(x); Read(y); Read(z); Commit;
这 3个事务的一个调度：
S={W2(x),W2(y),R2(z),C2,R1(x),W1(x),C1,R3(x),R3(y),R3(z),C3}
优先图：
T2 T1 T3
无环,S是串行调度。
1.3 分布式事务的可串行化调度测试
1 并发控制的概念和理论另外一个调度 S’:
S={W2(x),R1(x),W1(x),C1,R3(x),W2(y),R3(y),R2(z),C2,R3(z),C3}
先序图：
T2 T1 T3
无环，是可串调度。
1.3 分布式事务的可串行化调度测试
1 并发控制的概念和理论可串性理论扩展
可串性理论可以 直接 扩展到无重复副本的分布式数据库中。
– 事务在每个站点上的执行调度称作 局部调度
– 如果数据库无重复副本的分布式数据库，并且每个局部调度都是可串调度，只要这些局部调度的顺序一致，则它们的并（全局调度）也是可串调度
– 但是有副本的情况下，就比较复杂。可能局部调度是可串行化的，而全局调度不是可串行化的。
1.3 分布式事务的可串行化调度测试
1 并发控制的概念和理论
保证只产生可串行化调度的机制
并发控制机制分类
– 按分配模式 (数据方式 )
完全复制的 DB
部分复制 DB或分片的 DB
– 按网络类型 (通信方式 )
广播能力的
星型网,环形网
– 同步化原则
建立在相互排斥地访问共享数据基础上的算法
通过一些准则 (协议 )对事务进行排序的算法
悲观并发控制法（事务是相互冲突的），乐观并发控制法
（没有太多的事务相互冲突）
1.4 并发控制机制的常用方法及其分类
1 并发控制的概念和理论并发控制算法悲观法 乐观法加锁法集中式加锁分布式加锁时标排序法 混合法 加锁法 时序排序法主副本加锁基本时标排序保守时标排序多版本时标排序并发控制算法的分类
封锁法
– 事 务的同步化是通过对数据库的片断或者数据项进行物理或逻辑封锁来实现的
– 封锁对象的大小通常称为封锁粒度
– 封锁方法的类型可以根据在哪里进行封锁来进一步细分
封锁法分类
– 集中式封锁方法
一个站点被指定为主站点，存放对整个数据库的封锁表，
并且负责对全系统事务进行封锁
– 主副本封锁法：主副本所在站点封锁
– 分布式封锁法：网络中的站点共享锁的管理
1.4 并发控制机制的常用方法及其分类
1 并发控制的概念和理论基本思想和概念
基本思想
– 事务访问数据项之前要对该数据项封锁，如果已经被其他事务锁定，就要等待，直到哪个事务释放该锁为止
锁的粒度
– 锁定数据项的范围
– 数据项层次
一条数据库记录
数据库记录中的一个字段值
一个磁盘块（页面）
一个完整的文件
整个数据库
2.1 基于封锁的并发控制方法概述
2 分布式数据库系统并发控制机制的封锁技术基本思想和概念
粒度对并发控制的影响
– 大多数 DBMS缺省设置为记录锁或页面锁
– 粒度小，并发度高，锁开销大
数据项比较多，锁也多，解锁和封锁操作多，锁表存储空间大（如存储读写时间戳）
– 粒度大，并发度低，锁开销小
如果是磁盘块，封锁磁盘块中的一条记录 B的事务 T必须封锁整个磁盘块
而另外一个事务 S如果要封锁记录 C,而 C也在磁盘块中，由于磁盘块正在封锁中,S只能等待
如果是封锁粒度是一条记录的话，就不用等待了
2.1 基于封锁的并发控制方法概述
2 分布式数据库系统并发控制机制的封锁技术基本思想和概念
如何来确定粒度
– 取决于参与事务的类型
– 如果参与事务都访问少量的记录，那么选择一个记录作为粒度较好
– 如果参与事务都访问同一文件中大量的记录，
则最好采用块或者文件作为粒度
2.1 基于封锁的并发控制方法概述
2 分布式数据库系统并发控制机制的封锁技术
锁的类型：
– 共享锁,Share锁,S锁或者读锁
– 排它锁,eXclusive锁,X锁，拒绝锁或写锁。
– 更新锁,Update锁,U锁
锁的选择：
– 数据项既可以读也可以写,则要用 X锁
– 如果数据项只可以读,则要用 S锁,
2.1 基于封锁的并发控制方法概述
2 分布式数据库系统并发控制机制的封锁技术基本思想和概念
锁的操作
– Read_lock(x):读锁
– Write_lock(x)：写锁
– unlock(x)：解锁
数据项的状态
– read_locked,读 锁
– Write_locked:写锁
具体操作方法
– 在系统锁表中记录关于锁的信息
– 锁表中每条记录有四个字段,<数据项名称，锁状态，读锁的数目，
正在封锁该数据项的事务 >
– 锁状态是上面两种，没有被封锁的数据项，在系统表中没有记录
2.1 基于封锁的并发控制方法概述
2 分布式数据库系统并发控制机制的封锁技术基本思想和概念
封锁准则：
– 事务 T在执行任何 read_item（ x）操作之前，必须先执行 read_lock(x)或者 write_lock(x)操作
– 事务 T在执行任何 write_item（ x）操作之前，必须先执行 write_lock(x)操作
– 如果事务 T执行 read_lock(x)操作,数据项 x必须没有加锁或者已经加了读锁，否则事务 T的这个操作不能进行
– 如果事务 T执行 write_lock(x)操作,数据项 x必须没有加锁，
否则事务 T的这个操作不能进行
2.1 基于封锁的并发控制方法概述
2 分布式数据库系统并发控制机制的封锁技术封锁准则和锁的转换
封锁准则：
– 事务 T在完成所有 read_item（ x）和 write_item（ x）操作之后，必须执行 unlock(x)操作
– 如果事务 T已经持有数据项 x上的一个读锁或者一个写锁，那么它不能再执行 read_lock(x)操作
– 如果事务 T已经持有数据项 x上的一个读锁或者一个写锁，那么它不能再执行 write_lock(x)操作
– 如果事务 T没有持有数据项 x上的一个读锁或者一个写锁，那么它不能执行 unlock(x)操作
2.1 基于封锁的并发控制方法概述
2 分布式数据库系统并发控制机制的封锁技术封锁准则和锁的转换
锁的转换
1,特定条件下，一个已经在数据项 x上持有锁的事务 T,
允许将某种封锁状态转换为另外一种封锁状态
2,比如，一个事务先执行了 read_lock（ x）操作，然后他可以通过执行 write_lock(x)操作来升级该锁
3,同样，一个事务先执行了 write_lock(x) 操作，然后他可以通过执行 read_lock（ x） 操作来降级该锁
2.1 基于封锁的并发控制方法概述
2 分布式数据库系统并发控制机制的封锁技术封锁准则和锁的转换
2.1 基于封锁的并发控制方法概述
2 分布式数据库系统并发控制机制的封锁技术
T1 T2
read_lock(Y);
read_item(Y);
unlock(Y);
write_lock(X);
read_item(X);
X:= X+Y;
write_item(X);
unlock(X);
read_lock(X);
read_item(X);
unlock(X);
write_lock(Y);
read_item(Y);
Y,= Y + X;
write_item(Y);
unlock(Y);
（ a）两个事务 T1和 T2
初始值,X=20,Y=30
串行调度 T1,T2的结果,X=50,Y=80
串行调度 T2,T1的结果,X=70,Y=50
（ b） T1和 T2可能的串行调度的结果
T1 T2
read_lock(Y);
read_item(Y);
unlock(Y);
write_lock(X);
read_item(X);
X:= X+Y;
write_item(X);
unlock(X);
read_lock(X);
read_item(X);
unlock(X);
write_lock(Y);
read_item(Y);
Y,= Y + X;
write_item(Y);
unlock(Y);
这个调度 S的结果：
X=50,Y=50
(不可串行化 )
（ c）使用锁的一个不可串行化调度的结果满足封锁规则不能保证产生串行化调度
简单的分布式封锁方法
– 类似集中式，将同一数据的全部副本封锁，然后更新，之后解除全部封锁
– 缺点是各站点间进行相当大的数据传输，如果有 N个站点，就有：
N个请求封锁的消息
N个封锁授权的消息
N个更新数据的消息
N个更新执行了的消息
N个解除封锁的消息
2.1 基于封锁的并发控制方法概述
2 分布式数据库系统并发控制机制的封锁技术分布式数据库基本封锁算法
主站点封锁法
– 定义一个站点为主站点，负责系统全部封锁管理
– 所有站点都向主站点提出封锁和解锁请求，由它去处理
– 缺点有：
所有封锁请求都送往单个站点，容易由于超负荷造成,瓶颈,
主站点故障造成会使系统瘫痪，封锁消息都在这里，制约了系统可用性和可靠性
2.1 基于封锁的并发控制方法概述
2 分布式数据库系统并发控制机制的封锁技术分布式数据库基本封锁算法
主副本封锁法
– 不指定主站点，指定数据项的主副本
– 事务对某个数据项进行操作时，先对其主副本进行封锁，再进行操作
– 主副本封锁，意味着所有的副本都被封锁
– 主副本按使用情况，尽量就近分布
– 可减少站点的负荷,使得各站点比较均衡
– 可减少传输量
快照方法
– 和上一章讲的类似
2.1 基于封锁的并发控制方法概述
2 分布式数据库系统并发控制机制的封锁技术分布式数据库基本封锁算法基本 2PL协议
如果一个事务所有的封锁操作（读写）都在第一个解锁操作之前，那么它就遵守 2PL协议
事务的执行中 Lock的管理分成两个阶段
– 上升阶段 (成长阶段 )：获取 Lock阶段（只能获取锁）
– 收缩阶段 (衰退阶段）：释放 Lock阶段（只能解锁）
封锁点是指事务获得了它所要求的所有锁，并且还没有开始释放任何锁的时刻
如果允许锁的转换，锁的升级必须在成长阶段进行，锁的降级必须在锁的衰退阶段进行。
2PL可以保证事务执行的可串行性,
2.2 2PL协议（两阶段封锁协议）
2 分布式数据库系统并发控制机制的封锁技术开始 加锁点 结束事务执行过程获得锁释放锁两阶段封锁协议
2.2 基本 2PL协议
2 分布式数据库系统并发控制机制的封锁技术
基本 2PL协议实现的难点
– 锁管理器必须要知道事务的锁点位置
级联撤销 (cascading aborts)
– 如果事务在开始释放 Lock后又 Abort时,将引起级联撤销 (cascading aborts)
（其他访问这个数据项的事务也被撤销）
保守 2PL
– 要求事务在开始执行之前就持有所有它要访问的数据项上的锁
– 事务要预先声明它的读集和写集
大多数 2PL调度器实现的是严格 2PL(S2PL)
– 事务在提交或者撤销之前，绝对不释放任何一个写锁
– 事务结束时（提交或者撤销），同时释放所有的锁
2.2 2PL协议
2 分布式数据库系统并发控制机制的封锁技术
严酷 2PL
– 事务 T在提交或撤销之前，不能释放任何一个锁（写锁或者读锁），
因此它比严格 2PL更容易实现
保守 2PL与严酷 2PL之间的区别
– 前者，事务必须在开始之前封锁它所需要的所有数据项，因此，
一旦事务开始就处在收缩阶段
– 后者,直到事务结束（提交或者撤销）后才开始解锁，因此，事务一直处于扩张阶段，直到结束
2.2 2PL协议
2 分布式数据库系统并发控制机制的封锁技术开始 结束事务执行阶段获得锁释放锁严格 2PL(Strict Two-phase Locking)协议数据项使用
2.2 2PL协议
2 分布式数据库系统并发控制机制的封锁技术
并发控制子系统
– 可以负责产生读锁和写锁操作（以严格 2PL协议为例）
– 当事务 T发出 read_item(x)操作请求时，系统会代表 T调用 read_lock(x)操作
– 如果 Lock(x)的状态是被另外一个事务 T’持有写锁，那么系统会把 T放到数据项 X的等待队列中；否则，系统同意 read_lock(x)的请求，从而允许事务 T执行 read_item(x)
操作
– 另外一个方面，如果事务 T发出 write_item（ x）操作请求时，系统会代表 T调用
write_lock(x)操作
– 如果 Lock(x)的状态是被另外一个事务 T’持有读锁或写锁，那么系统会把 T放到数据项 X的等待队列中；
– 如果 Lock(x)的状态是读锁，并且事务 T本身就是持有 x上的读锁的唯一事务，那么系统将该锁升级为写锁，并且允许 T执行 write_item(x)操作
– 如果 Lock(x)的状态是没有锁，那么系统同意 write_lock(x)的请求，进而允许事务 T
执行 write_item(x)操作
2.2 2PL协议
2 分布式数据库系统并发控制机制的封锁技术集中式 2PL的实现方法
2PL很容易扩展到分布式 DBMS(无论复制或无复制
DDB),
其最简单的方法是选择一个站点 (主站点 )做 Lock管理器,其他站点上的事务管理器都需要与该选出的站点
Lock管理器通信,而不是与本站点 Lock管理器通信,
这就是集中式 2PL方法
2.3 2PL协议的实现方法
2 分布式数据库系统并发控制机制的封锁技术
术语
– 协调事务管理器 (coordinating TM),
事务原发站点
– 数据处理器 (data processor,DP),其他参与站点
– 中心站点 LM,主站点锁管理器
2.3 2PL协议的实现方法
2 分布式数据库系统并发控制机制的封锁技术参与站点的数据处理器 协调 TM 中心站点 LM
加锁请求
①
②
③
④
⑤
允许加锁操作操作结束释放封锁集中式 2PL的通信结构中心站点
LM不需要向 DP发送操作
2.3 2PL协议的实现方法
2 分布式数据库系统并发控制机制的封锁技术集中式 2PL的实现方法主副本 2PL的实现方法
是主站点 2PL的直接扩展
– 选择一组站点做 Lock管理器
– 每个 Lock管理器管理一组数据 (即每个数据选择一个站点作自己的 Lock管理器 )
– 事务管理器根据 Lock申请的数据对象分别向这些数据的 LM发出锁申请
– 必须先为每一个数据项确定一个主副本站点，然后再向那个站点上的封锁管理程序发送封锁或释放锁的请求，目录的思想
为分布式 INGRES版本提出的，每个站点上要有一个复杂的目录
2.3 2PL协议的实现方法
2 分布式数据库系统并发控制机制的封锁技术
特点
– 每个站点都有 LM
– 无副本 DDB上如同主副本 2PL
– 有冗余副本 DDB上则使用 ROWA控制协议
与集中式相似，但有不同
– 集中式中向中心站点封锁管理程序发送的信息，在分布式中 发送给所有参与站点的封锁管理程序
– 另外不同之处在于操作并不通过协调者事务管理程序传到数 据处理器，而是通过参与者的封锁管理程序
– 参与者的数据处理器向协调者的事务管理程序发送“操作结 束”信息
– 另外一种方法，每个数据处理器执行自身解锁，并通知协调者事务管理程序的封锁管理程序
2.3 2PL协议的实现方法
2 分布式数据库系统并发控制机制的封锁技术分布式 2PL的实现方法参与者 DPs
①
②
加锁请求操作分布式 2PL的通信结构协调者 TM 参与者 LMs
③
操作结束释放锁
④
2.3 2PL协议的实现方法
2 分布式数据库系统并发控制机制的封锁技术分布式 2PL的实现方法
多粒度封锁
– 封锁的粒度不是单一的一种粒度，而是有多种粒度
– 可以定义多粒度树，根节点是整个数据库，叶节点表示最小的封锁粒度
直接封锁
– 事务对要进行读 /写的数据对象直接申请加锁
分层封锁
– DB中各数据对象从大到小存在一种层次关系,例如划分为 DB,段,关系,元组,字段等
– 当封锁了外层数据对象时,蕴含着也同时封锁了它的所有内层数据对象
– 数据项的显式封锁和隐式封锁
2.4 多粒度封锁与意向锁
2 分布式数据库系统并发控制机制的封锁技术数据库段 1 段 n
元组 元组 元组元组
….
多级粒度树关系 nn关系 11 ……...
……...
2.4 多粒度封锁与意向锁
2 分布式数据库系统并发控制机制的封锁技术
2.4 多粒度封锁与意向锁
2 分布式数据库系统并发控制机制的封锁技术
db
f1 f2
p11 P12……,p1n
r111…r11j r121…r12j …… r1n1…r1nj
p21 P22……,p2n
r211…r21j r221…r22j …… r2n1…r2nj
用来说明多粒度级别封锁的粒度层次结构
例子
– 假定事务 T1要更新文件 f1中的所有记录,T1请求并获得了 f1上的一个写锁
– 那么 f1下面的页面和记录就获得了隐式写锁
– 如果这时候，事务 T2想从 f1中的某个页面中读某个记录，那么 T2就要申请该记录上的读锁
– 但是要确认这个读锁和已经存在锁的相容性，
确认的方法就是要遍历该树：从记录到页，到文件最后到数据库，如果在任意时刻，在这些项中的任意一个上存在冲突锁，那么对记录的封锁请求就被拒绝,T2被阻止，要等待。
2.4 多粒度封锁与意向锁
2 分布式数据库系统并发控制机制的封锁技术
意向锁
– 如果对一个节点加意向锁，则说明该节点的下层节点正在被封锁
– 对任一节点封锁时，必须先对它的上层节点加意向锁
意向锁的类型
– 意向共享锁 (IS)：指示在其后代节点上将会请求共享锁，即如果对某个对象加 IS锁，表示它的后代节点拟加共享锁
– 意向排它锁 (IX)：指示在其后代节点上将会请求排他锁，即如果对某个对象加 IX锁，表示它的后代节点拟加排他锁
– 共享意向排它锁 (SIX)：指示当前节点处在共享方式的封锁中，但是在它的某些后代节点中将会请求排他锁。即如果对一个数据对象加 SIX锁,表示对它加共享锁，再加 IX锁（ SIX=S+IX）。例如：对某个表加 SIX锁，则表示该事务要读整个表（加 S锁），同时会更新个别元组（加 IX锁）
2.4 多粒度封锁与意向锁
2 分布式数据库系统并发控制机制的封锁技术
T2
T1
YYYYYY-
YNNYNNSIX
YNYYNNIX
YYYYNYIS
YNNNNNX
YNNYNYS
-SIXIXISXS
X
SIX
S IX
IS
Y=yes，表示相容的请求 N=no，表示不相容的请求
(a)数据锁的相容矩阵
(b)锁的强度的偏序关系锁的相容矩阵
2.4 多粒度封锁与意向锁
2 分布式数据库系统并发控制机制的封锁技术锁的强度：对其它锁的排斥程度
多粒度封锁协议的规则
– 必须遵守锁的相容性规则
– 必须首先封锁树的根节点，可以用任何一种方式的锁
– 只有当节点 N的父节点已经被事务 T以 IS或 IX方式封锁后，节点 N
才可以被 T以 S或者 IS方式封锁
– 只有当节点 N的父节点已经被事务 T以 IX或 SIX方式封锁后，节点 N
才可以被 T以 X,IX或者 SIX方式封锁
– 只有当事务 T还没有释放任何节点时,T才可以封锁一个节点
– 只有当事务 T当前没有封锁节点 N的任何子节点时,T才可以为节点 N解锁。
2.4 多粒度封锁与意向锁
2 分布式数据库系统并发控制机制的封锁技术
总结
– 具有意向锁的多粒度加锁方法中，任意事务 T要对一个数据对象加锁，必须先对它的上层节点加意向锁
– 申请封锁时应该按自上而下的次序进行
– 释放锁时则应该按自下而上的次序进行
– 具有意向锁的多粒度加锁方法提高了系统的并发度,减少了加锁和释放锁的开销
– 它已经在实际的 DBMS系统中广泛应用，例如 Oracle中
2.4 多粒度封锁与意向锁
2 分布式数据库系统并发控制机制的封锁技术
死锁发生的条件
– 互斥条件：事务请求对资源的独占控制
– 等待条件：事务已持有分配给它的资源,又去申请并等待别的资源
– 非抢占条件：直到资源被持有它的事务释放前,
不可能将资源强制从持有它的事务夺去
– 循环等待条件：存在事务互相等待的等待圈
死锁分类
– 局部死锁：仅在一个站点上发生的死锁
– 全局死锁：涉及多个站点的死锁 (即等待圈由多个站点组成 )
3.1 全局死锁与等待图
3 分布式数据库系统中的死锁处理事务 T1持有对 x的锁事务 T2请求对 x的锁事务 T2持有对 y的锁事务 T1请求对 y的锁站点 A 站点 B
T2等待 T1完成释放对 x的锁
T1等待 T2完成释放对 y的锁相互等待引起的全局死锁
3.1 全局死锁与等待图
3 分布式数据库系统中的死锁处理
T1
T2
T3
站点 A,x1,y1
站点 C,z3
站点 B,y2,z2
等待释放对 y 的锁等待释放对 x 的锁 等待释放对 z 的锁站点 A：存储 x和 y的副本,发出事务 T1,read(x),write(y)
站点 B：存储 y和 z的副本,发出事务 T2,read(y),write(z)
站点 C：存储 z的副本,发出事务 T3,read(z),write(x)
多副本引起的三个站点间的死锁
3.1 全局死锁与等待图
3 分布式数据库系统中的死锁处理
等待图
– 一种用来表示事务之间相互等待关系的有向图,是分析死锁的有用工具
– 节点表示事务
– 带有箭头的有向边表示“等待”关系
– 如果等待图有回路，就说明有死锁
等待图分类
– 局部等待图 (LWFG)
– 全局等待图 (GWFG)
3.1 全局死锁与等待图
3 分布式数据库系统中的死锁处理
T1
T3
T2
y
x
z T1等待 T2释放对 y的共享锁 (s)
T2等待 T3释放对 z的共享锁 (s)
T3等待 T1释放对 x的共享锁 (s)
上例的 GWFG等待图
3.1 全局死锁与等待图
3 分布式数据库系统中的死锁处理
(a)
(b)
T2
T1
T1
T2
T4
T3
T4
T3
站点 1 站点 2
LWFG和 GWFG之间的不同
3.1 全局死锁与等待图
3 分布式数据库系统中的死锁处理事务间的等待关系
T1→T2→T3→T4
解决死锁的方法
– 死锁预防，使引起死锁的必要条件不成立
所有资源排序,按资源序列申请
将所有并发事务排序,按标识符或开始时间
有死锁危险时，事务退出已占有的资源，有两种方法
– 等待 -死亡 (Wait-Die)：总是重启较年轻的事务 (非占先权 )
– 受伤 -等待 (Wound-Wait),年轻的等待年老的,较年轻的重启,而重启事务并不一定是目前正申请的事务 (占先权 )
– 死锁检测
即检测死锁时循环等待的圈
3.2 死锁的预防方法
3 分布式数据库系统中的死锁处理
等待 -死亡模式
– 如果 Ti对已被 Tj封锁的一数据项请求封锁的话，则只有在 Ti比 Tj年老时（ Ti<Tj），才允许 Ti等待
– 如果 Ti比 Tj年轻（ Ti>Tj），则 Ti被终止并带有同一时间戳重新启动
– 最好总是重新启动较年轻的事务
– 允许较年老的事务去等待已持有资源的较年轻的事务
– 但不允许较年轻的事务去等待较年老的事务
受伤 -等待模式
– 如果 Ti对已被 Tj封锁的一数据项请求封锁的话，则只有在 Ti比 Tj年轻时（ Ti>Tj），才允许 Ti等待
– 否则,Ti比 Tj年老（ Ti<Tj），则 Tj被终止并带有同一时间戳重新启动,而 Ti得锁执行
– 只有年轻的等待年老的
3.2 死锁的预防方法
3 分布式数据库系统中的死锁处理
集中式死锁检测
– 选择一个站点负责整个系统的死锁检测,死锁检测器放到这个站点
– 每个站点的锁管理器周期性地将本站点的 LWFG传送给死锁检测器,死锁检测器构造 GWFG,并在其中寻找回路
– 或者，其它每个站点上的锁管理器周期性地把记录本站点上事务的开始时间，
对锁的持有、请求情况变化的动态表，发送给负责处理封锁的站点，由它维护一张全局封锁动态表，形成 GWFG,并在其中寻找回路
– 如果至少包含一条回路，它会选择一个或者多个事务，把它们取消并恢复，
释放资源，使得其它事务继续进行。
– 选择的标准是尽可能使撤销并恢复的代价最小，如撤销年轻的事务，撤销占有较少、资源的事务，撤销具有最短运行时间的事务，撤销具有最长运行时间的事务等，使系统情况而定
3.3 死锁的检测和解决方法
3 分布式数据库系统中的死锁处理
层次式死锁检测
– 以层次方式组织成员 DBMS中的死锁检测器
– 死锁发生时,常常只涉及部分站点
– 层次检测的层次结构与网络拓扑结构有关
– 减少了对中心站点的依赖性，从而减少了传输开销
3.3 死锁的检测和解决方法
3 分布式数据库系统中的死锁处理
层次式死锁检测的步骤
– 树叶是各站点的局部死锁检测器，在本站点建立局部等待图
– 本站点的死锁检测器找出本站点局部等待图中的任何回路，
并把有关潜在全局回路的信息发送给上一层死锁检测器
– 每个非本地死锁检测器只对它所涉及的紧挨下层进行死锁检测，合并这些接收到的有关潜在全局回路的信息，并找出任何回路
– 如果还有上层死锁检测器，将经过简化的有关潜在全局回路的信息发送给它上一层死锁检测器，由上一层死锁检测器再进行合并，找出任何全局回路
– 这样，逐层检测，直到最高层。
3.3 死锁的检测和解决方法
3 分布式数据库系统中的死锁处理第 0层死锁检测器第 i层死锁检测器第 i层死锁检测器局部死锁检测器局部死锁检测器局部死锁检测器局部死锁检测器简化潜在死锁图简化潜在死锁图简化潜在死锁图简化潜在死锁图简化潜在死锁图简化潜在死锁图层次式死锁检测方法示意图
3.3 死锁的检测和解决方法
3 分布式数据库系统中的死锁处理
分布式检测
– 每个站点的检测死锁责任相同,站点之间交换信息
(LWFG)，是为了确定全局死锁
– EX是指的本地事务正在等待的其他事务所在的还不确定的站点
– 例子 站点 1 站点 2
T1
T2
T4
T3
EX
EX
3.3 死锁的检测和解决方法
3 分布式数据库系统中的死锁处理
信息传递方向 此处规定一种,以避免多次重复传递
– EX等待的事务号 > 等待 EX的事务号
分布式死锁检测算法
– 使用局部信息建造 LWFG,该 LWFG包含 EX节点
– 对每次接收到的信息,执行如下对 LWFG的修改
对报文中的每个事务,若 LWFG中不存在,则将其加入
从 EX节点开始,按照报文所给的信息,建立一个到下一个事务的边
– 在新的 LWFG中寻找不含 EX的 Loop,若存在,则检测到死锁
– 在新的 LWFG中找到含有 EX的 Loop,于是有潜在的死锁,再按规定向外传送信息
3.3 死锁的检测和解决方法
3 分布式数据库系统中的死锁处理
基本概念
– 不通过互斥来支持串行性，而是通过在事务启动时赋给时标（时间戳）来实现
– 时标是用来唯一识别每个事务并允许排序的标识
– 如果 ts(T1) < ts(T2) … < ts(T n),则调度器产生的序是,
T1,T2,..,Tn
规则
– 如果 T1的操作 O1(x)和 T2的操作 O2(x)是冲突操作,那么,
O1在 O2之前执行,当且仅当 ts(T1)<ts(T2)
4.1 基于时标的并发控制方法
4 分布式数据库系统并发控制的时标技术
时标分配方法
– 全局时标
使用全局的单调递增的计数器
全局的计数器维护是个难题
– 局部时标
每个站点基于其本地计数器自治地指定一个时标
标识符由两部分组成,〈 本地计数器值，站点标识符 〉
– 站点标识符是次要的，主要是本地计数器值
– 可以使用站点系统时钟来代替计数器值
4.1 基于时标的并发控制方法
4 分布式数据库系统并发控制的时标技术
时标法思想
– 每个事务赋一个唯一的时标，事务的执行等效于按时标次序串行执行
– 如果发生冲突，是通过撤销并重新启动一个事务来解决的
– 事务重新启动时，则赋予新的时标
– 优点是没有死锁，不必设置锁
– 封锁和死锁检测引起的通信开销也避免了
– 但要求时标在全系统中是唯一的
4.1 基于时标的并发控制方法
4 分布式数据库系统并发控制的时标技术
时标性质
– 唯一性
– 单调性
全局唯一时间的形成与调整
– 每个站点设置一个计数器,每发生一个事务,计数器加一
– 发送报文时包含本地计数器值,近似同步各站点计数器
4.1 基于时标的并发控制方法
4 分布式数据库系统并发控制的时标技术
4.1 基于时标的并发控制方法
4 分布式数据库系统并发控制的时标技术计数器 X 初值 X=0 计数器 Y 初值 Y=10
站点 1 站点 2
时标 A D 时标
TS(A)=<1,1> TS(D)=<11,2>
因为 X<Y E TS(E)=<12,2>
改 X=Y+1=11 B
TS(B)=<11,1> F 因为 Y>X
TS(C)=<12,1> C TS(F)=<13,2>
本地计数器 本地计数器
(或时钟 ) (或时钟 )
报文 1
报文 2
计数器站点基本时标法
规则
– 每个事务在本站点开始时赋予一个全局唯一时标
– 在事务结束前，不对数据库进行物理更新
– 事务的每个读操作或写操作都具有该事务的时标
– 对每个数据项 x,记下写和读操作的最大时标，记为
WTM(x)和 RTM(x)
– 如果事务被重新启动，则被赋予新的时标
4.2 基本时标法
4 分布式数据库系统并发控制的时标技术
基本时标法执行过程
– 令 read_TS是事务对 x进行读操作时的时标
若 read_TS<WTM(x)，则拒绝该操作,事务重新启动
否则,执行,令 RTM(x)=max{RTM(x),read_TS}
– 令 write_TS是事务对 x进行写操作时的时标
若 write_TS < RTM(x) 或 write_TS < WTM(x),则拒绝该操作,事务重新启动
否则,执行,令 WTM(x) = max{WTM(x),write_TS}
缺点是重启动多
4.2 基本时标法
4 分布式数据库系统并发控制的时标技术
基本思想
– 一种消除重启动的方法
– 通过缓冲年轻的操作，直至年长的操作执行完成，因此操作不会被拒绝，事务也绝不被重启动
规则
– 每个事务只在一个站点执行,它不能激活远程的程序,但是可以向远程站点发读 /写请求
– 站点 i接收到来自不同站点 j的读 /写请求必须按时标顺序，
即每个站点必须按时标顺序发送读 /写数据请求，在传输中也不会改变这个顺序
– 每个站点都为其它站点发来的读 /写操作开辟一个缓冲区,
分别保存接收到的读 /写申请
4.3 保守时标法
4 分布式数据库系统并发控制的时标技术
假定某个站点 k上,各个缓冲区队列都已不为空，即每个站点都已向它至少发送了一个读和一个写操作，就停止接收，处理在缓冲区中的操作
假定站点 i至少有一个缓冲的读和缓冲的写来自网中其它站点,根据规则 2,Site i 知道没有年老的请求来自其它 Site(因为按序接收,所以不可能有比此更年老的请求到来,年老的比年轻的先到 )
4.3 保守时标法
4 分布式数据库系统并发控制的时标技术例子已知站点 i的缓冲区队列中有来自所有站点的读 /写请求如下所示,
站点 1 站点 2 站点 3 …… 站点 n
R11 R21 R31 Rn1
R12 R22 R32
R13 R23
R24
W11 W21 W31 …… Wn1
W22 W32 … Wn2
W23
4.3 保守时标法
4 分布式数据库系统并发控制的时标技术执行步骤,
(1) 设 RT=min(Rij),WT= min(Wij)
(2) 按下法处理缓冲区中的 Rij和 Wij
a,若队列中有
(Rij) < WT的 Rij,则顺序执行这些 Rij，执行完删掉
b,若队列中有
(Wij) < RT的 Wij,则顺序执行这些 Wij，执行完删掉
(3) 修改 RT=min(Rij),WT=min(Wij),此时的 Rij和 Wij是队列中剩余的
(4) 重复上述 (2)和 (3),直到没有满足条件的操作,或者,
a,若某个或某些 R队列为空时,RTM=0;
b,若某个或某些 W队列为空时,WTM=0
4.3 保守时标法
4 分布式数据库系统并发控制的时标技术存在问题和解决方法
– 如果一个站点从来不向某个站点发送操作的话，那么执行过程中的假定就不符合，操作就无法进行。解决办法是，周期性的发送带有时标的空操作
– 此方法要求网络上所有站点都连通，这在大系统中很难办到。为避免不必要的通信，可对无读写操作请求的站点，发送一个时标很大的空操作
– 此方法过分保守，一律按照时序来进行，其中包括了不冲突的操作
4.3 保守时标法
4 分布式数据库系统并发控制的时标技术
基本思想
– 保存了已更新数据项的旧值
– 维护一个数据项的多个版本
– 通过读取数据项的较老版本来维护可串行性，使得系统可以接受在其他技术中被拒绝的一些读操作
– 写数据项时，写入一个新版本，老版本依然保存
缺点
– 需要更多的存储来维持数据库数据项的多个版本
模式分类
– 基于时标排序
– 基于两阶段封锁
5.1 多版本概念和思想
5 分布式数据库系统并发控制的多版本技术
数据项 X的多版本
– X1,X2,X3,…,Xk
系统保存的值
– Xi的值
– 两种时标
Read_TS(Xi),读时标，成功读取版本 Xi的事务的时标，
最大的一个
Write_TS(Xi),写时标，写入版本 Xi的值的事务的时标
5.2 基于时标的多版本技术
5 分布式数据库系统并发控制的多版本技术
多版本规则
– 如果事务 T发布一个 write_item(X)操作，并且 X的版本 Xi
具有 X所有版本中最高的 write_TS(Xi),同时
write_TS(Xi)<=TS(T)且 read_TS(Xi)>TS(T)，那么撤销并回滚 T；否则创建 X的一个新版本，并且令 read_TS(Xi)=
write_TS(Xi)= TS(T)
– 如果事务 T发布一个 read_item(X)操作，并且 X的版本 Xi
具有 X所有版本中最高的 write_TS(Xi),同时
write_TS(Xi)<=TS(T)，把 Xi的值返回给事务 T,并且将
read_TS(Xi)的值置为 TS(T)和当前 read_TS(Xi)中较大的一个
5.2 基于时标的多版本技术
5 分布式数据库系统并发控制的多版本技术图示写值
v1 v2 v3 … Vn-1 Vn
5 10 20 92 100
若读 TS(Ri)=95,则读 <92,Vn-1> 的值若写 TS(Wk)=93,则出现了
v1 v2 v3 … Vn-1 Vn
5 10 20 92 10093
v
于是要拒绝 TS(Wk),否则 TS(Ri)=95读的就是 Vn-1,而不是 v
的值,但是按规定 TS(Ri)=95应该读的是 v值
三种锁方式
– 读，写，验证
四种锁状态
– 读封锁（ read_locked）
– 写封锁（ write_locked）
– 验证封锁（ certify_locked）
– 未封锁（ unlocked）
锁相容性
– 标准模式锁相容性（写锁和读锁）
– 验证模式锁相容性（写锁、读锁和验证锁）
5.3 采用验证锁的多版本两阶段封锁
5 分布式数据库系统并发控制的多版本技术
5.3 采用验证锁的多版本两阶段封锁
5 分布式数据库系统并发控制的多版本技术
(a) 读 /写封锁模式的相容性表读 写读写是 否否 否读 写 验证读写是 是 否是 否 否验证 否 否 否
(b) 读 /写 /验证封锁模式的相容性表
多版本 2PL的思想
– 当只有一个单独的事务 T持有数据项上的写锁时，允许其他事务 T’读该项 X，这是通过给予每个项 X的两个版本来实现的
一个版本 X是由一个已提交的事务写入的
另一个版本 X’是每个事务 T获得该数据项上写锁时创建的、
– 当事务 T持有这个写锁时，其他事务可以继续读 X的已提交版本
– 事务 T可以写 X’的值，而不影响 X已提交版本的值
– 但是，一旦 T准备提交，它必须在能够提交之前，得到持有写锁的数据项上的验证锁，要等写锁释放之后
– 一旦获得验证锁，数据项的已提交版本 X被置为版本 X’
的值，版本 X’被丢弃，验证锁被释放。
5.3 采用验证锁的多版本两阶段封锁
5 分布式数据库系统并发控制的多版本技术
基本思想
– 对于冲突操作不像悲观方法那样采取挂起或拒绝的方法，而是让一个事务执行直到完成
基于如下假设
– 冲突的事务是少数（查询为主的系统中，冲突少于 5%）
– 大多数事务可以不受干扰地执行完毕
6.1 基本思想和假设
6 分布式数据库系统并发控制的乐观方法
6.2 执行阶段划分
6 分布式数据库系统并发控制的乐观方法验证 读 /计算 写 /提交读 /计算 验证 写 /提交乐观法事务执行的各个阶段悲观法事务执行的各个阶段
事务的三个阶段
– 读段 /计算,在数据对象的局部副本上执行事务，这时其他事务不能存取此副本。事务从 DB读数据，执行计算，并且确定写集数据项的新值。写操作总是对局部副本，仅当验证通过后，在事务结束处，才将其写入
DB。
– 验证段,检验并发事务的可串性，该阶段验证修改应用是否引起完整性（一致性）的丢失，验证阶段通过，
才能进入写段，否则事务重启动
– 写段 /提交,验证阶段通过，则把事务的更新应用于数据库，对数据进行更新，否则，忽略所有更新，并重新开始该事务
6.2 执行阶段划分
6 分布式数据库系统并发控制的乐观方法
验证
– 使用数据项和事务上的时标
– 只使用事务时标
6.3 验证分类
6 分布式数据库系统并发控制的乐观方法
使用数据项和事务上的时标
– 假设是一个 完全冗余的 DB，事务在读期间把更新写入一个更新表
– 事务时标,事务在启动执行时接受的具有唯一性的时标
– 数据项时标,对该数据项最后写入的事务的时间戳
– 算法假定：读集? 写集,即写必须先读
6.3 使用数据项和事务上的时标
6 分布式数据库系统并发控制的乐观方法
读阶段末，事务产生一个更新表 u，包括
– 读集的数据项，带有自身的时标
– 写集数据项的新值
– 该事务自身的时标
验证阶段
– 把更新表发送到每一站点，每个站点对是否确认该更新表进行表决，并把表决结果送回到该事务的源站点
– 如源站点收到多数肯定票，则决定事务提交并通知各站点
– 如多数表决是否定的，则把放弃更新表的决定通知所有站点，然后重新启动该事务
6.3 使用数据项和事务上的时标
6 分布式数据库系统并发控制的乐观方法
表决规则
– 比较更新表 u中数据项的时标与本地库中相应数据项的时标,全部相等则投赞成票
– 不相等,投反对派票,因为此时可能本地写入数据项之前或之后,又有事务对数据项做了写操作
表决结果
– 若赞成票是大多数,则考虑 Commit,并将结论发送给每个 Site
– 否则,其更新表无效,事务重启动
6.3 使用数据项和事务上的时标
6 分布式数据库系统并发控制的乐观方法
更新表冲突表决规则
– 比较 u表中读集中数据项的时标与数据库中对应数据项的时标，如果不等，投否定票
– 若相等,Site j在对 u表做表决时,若存在 Site k上的 u’表传送到 Site j,使 Site j处于对 u’的表决中
若 u’中有与 u冲突的更新表,当 u’中的时标大时,则反对
当 u’中的时标小时,则延迟表决
– 若与 u’中无冲突数据项,则赞成原发 Site
投票 Site j
更新表 u
DB
U’
6.3 使用数据项和事务上的时标
6 分布式数据库系统并发控制的乐观方法
事务 Tj的验证过程
– 检验由一些事务给出的执行调度是否可以成为一个按时标串行执行的调度,
参与验证的事务有,
– a> 已经提交的事务
– b> 当 Tj验证时也正处于验证的事务
– c> Tj本身
6.4 只使用事务上的时标
6 分布式数据库系统并发控制的乐观方法
对于所有 TS(Ti) < TS(Tj)的事务 Ti,Tj验证必须满足如下三个条件
– Ti在 Tj开始其读段前已完成其写段 (严格串行 )
– Ti的写集与 Tj的读集不相交,并且 Ti在 Tj开始其写段时已完成其写段 (Ti与 Tj不冲突 )
– Ti的写集与 Tj的写集不相交,并且 Ti在 Tj读段完成前已结束其读段 (写 /写不冲突 )
6.4 只使用事务上的时标
6 分布式数据库系统并发控制的乐观方法
Start(T) Finishi(T) TS(T)
验证在 Tj执行期间记录下列信息,
a> Tj的读集和写集
b> Tj启动时 TNC的值,称为 Start(Tj)
c> Tj结束其读段时的 TNC值,称为 Finish(Tj)
– TS(Tj)：只有在写段之后 (验证成功 )才把此唯一的时标赋给 Tj,仅当将 TS(Tj)赋给 Tj后,TNC值才增值,
– Finish(Tj)与 Start(Tj)无变化,说明在其执行期间没有事务完成写段
– 验证方式
集中式
分布式
6.4 只使用事务上的时标
6 分布式数据库系统并发控制的乐观方法
集中式验证
– Finish(Ti) < Finish(Tj)时
Ti写集? (Tj写集 U Tj 读集 ) =?
─TS(Ti) < Start(Tj)时,不需要验证
Ti
Tj
写 /写 冲突
─ Start(Tj) < TS(Ti) < Finish(Tj) 时
Ti写集? Tj 读集 =?
写 /读 冲突Ti
Ti
Tj
Tj
真正串行
6.4 只使用事务上的时标
6 分布式数据库系统并发控制的乐观方法
分布式验证
a> 同一个事务的每一个子事务接收同一个唯一的全局事务标识符
b> 每个站点进行每一个本地子事务的本地验证
c> 对每个子事务 Tij,在局部验证时收集信息,建立在 j站点上,
Tij之前已发出的 Ti集 HB(Tij)
d> 全局验证若 HB(Tij)中的所有事务或提交或夭折,该子事务验证通过若 HB(Tij)有未知提交 /夭折的事务,则 Tij被挂起
e> 写段：使用 2PC的思想,当事务全局验证结束,把相应报文送给该子事务的主站点上,若全部验证都肯定,则该事务提交,否则 Abort
6.4 只使用事务上的时标
6 分布式数据库系统并发控制的乐观方法总 结
并发控制的概念和理论
分布式数据库系统并发控制的封锁技术
分布式数据库系统中的死锁处理
分布式数据库系统并发控制的时标技术
分布式数据库系统并发控制的多版本技术
分布式数据库系统并发控制的乐观方法
