《《分布式并发》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《分布式并发》PPT课件.ppt（51页珍藏版）》请在三一办公上搜索。
1、第5章 分布式并发控制,计算机科学与技术学院,5.1 问题提出与抽象,一 读写异常问题 二 分布式数据库管理系统的抽象1 数据库与DM（Data Managers）数据库可以看作是一个逻辑数据项集合，记作X，Y，Z,.每一个逻辑数据项可以存储在系统的任何DM中，也可以冗余地存储在多个DM中。TM（Transaction Managers）。,2 用户与事务 用户的数据库请求是通过执行事务与DDB发生联系的。事务可以来自于自含查询语言的联机查询如（QUEL）；也可是报告书写语言的报告生成程序如（PRG）；还可以是应用程序设计语言嵌入的数据操纵语言编写的应用程序，如（PROC）。,一个事务模拟为一
2、个READ和WRITE操作的序列，而不关心其内部计算。一个事务的逻辑写集是该事务要写的所有逻辑数据项的集合。如果一个事务的存储读集或存储写集与另一个事务的存储写集相交，则称这两个事务是冲突的（Conflict）。,5.2 用于并发控制的DDBS抽象结构,每一个在DDBMS中执行的事务都由一个单独的TM管理，即事务发出其所有的操作给一个特定的TM，所有为执行该事务所需要的分布式计算由该TM管理。在响应事务的命令时，TM向DM发出命令，说明具体的存储数据项将被读或写。由DM对相应数据子集进行操作。,一、集中式事务处理模式,一个集中式DBMS可以看作是在一个站点上的只有一个TM机构的管理软件。当一个
3、事务T发出BEGIN操作时，TM给T初始化一个私有工作区。当T发出READ（X）时，TM检查私有工作区是否包含X的一个副本。如果包含X的一个副本值并返回到T，否则TM发命令到相应的DM，检索X的一个副本值并返回到T，这个操作记为：DM-READ(X).,当T发出WRITE（X，VALUE）时，如果私有工作区含有X则更新其值，否则建一个具有此新值的X的副本，并放入工作区。当一个事务T发出END操作时，TM为每一个更新的逻辑数据项X发出DM-WRITE（X），使相应的DM对X所在的数据子集的X的值得到更新。当所有的DM-WRITE处理后，T的执行完成，撤销私有工作区。在这种模式下，可以把READ和
4、WRITE看作是用户对数据库请求的事务级操作，而把DM-READ和DM-WRITE看作是对数据库的内部操作。,两段提交（TWO-phase Commit）提交工作分两步完成：从T的私有工作区中复制X，Y，Z，.的值，并把这些值暂时放在安全的地方。如果在这一步中DBMS失效，则放弃事务的提交。DBMS把X，Y，Z，.的值复制到存储数据库。如果在这一步中DBMS失效，应启动恢复过程，从安全存储器中读出X,Y,Z,的值，并重新提交，直到成功为止。,二、分布事务处理模型,1 DDBMS中的私有工作区 一个事务T的私有工作区通常并不在与T的TM相同的场所，而是分布在包含T所访问数据的所有场所中。2 DD
5、BMS中的两阶段提交问题 在DDBMS中，由于可能一个场所失效而系统的其它部分继续工作，使得原子提交问题变得更加复杂与困难。在分布式DBMS中，引入TM与DM之间的预提交操作（pre-commit）。这个操作使DM从私有工作区复制数据项到安全存储器。每个接收与提交的DM能够确定在提交活动中还有哪些DM参加。如果T的TM在发生所有的DM-WRITE之前失效，则尚未收到DM-WRITE的那些DM能够识别这些情况，并查询是否有DM收到DM-WRITE。如果有DM接收到DM-WRITE，则剩余的这些DM就像它们也接收到命令一样的进行执行。,三、分布式事务处理模式,当一个事务T发出BEGIN操作时，T的
6、TM给T初始化一个私有工作区；当T发出READ（X）时，TM检查私有工作区是否存在X的一个副本。如果包含X的一个副本，T就使用这个副本的值，否则TM选择X的某个存储副本Xi，DM从数据库中检索这个副本的值，把这个值存入私有工作区,当T发出WRITE（X，VALUE）时，如果工作区含有X的一个副本值，则将私有工作区相应的更新，否则建一个具有新值VALUE的X的副本。当一个事务T发出END操作时，两段提交开始。对于T更新的每一个逻辑数据项X、X的每一个存储副本Xi，TM给Xi所在的DM发出Pre-Commit，在所有预提交处理以后，TM对所有由T更新的逻辑数据项的所有副本发DM-WRITE。直到所
7、有数据项的所有副本处理结束后T的执行结束。,5.3 分布式并发控制理论,一、无干扰执行与可串行性考虑事务的一个集合T1.Tn,令E0是这些事务的一个执行。E0最保险的实现策略是串行执行，即每一个事务是在下一个事务开始之前完成。如果这些事务的另一个执行E1中有事务的并行执行，但E1和E0在输出和对数据库的影响上都有相同的结果，则称E1是可串行的（Serilizable）。数据库并发控制的目标就是只允许可串行的执行出现。计程：用一组计程（Log）做事务的执行模型，其中每一个DM有一个计程，每个计程指出在一个DM中DM-READ和DM-WRITE的执行次序。,定义5-1 由一组计程所代表的执行是可串
8、行的，如果满足下列条件：（1）对每一个计程，对于其操作出现在此计程中的每一次事务Ti和Tj，要么所有的Ti的操作在Tj的操作之前进行，要么所有的Tj的操作在Ti的操作之前完成；（2）对每一对事务Ti和Tj，如果在某一计程中，Ti的操作 在Tj之前，则在任一Ti和Tj同时出现的其他计程中，Ti的操作也必须在Tj的操作之前。,例5-1 假设有事务T1，T2，T3。涉及的数据项X，Y和 Z的副本用Xi，Yj和Zk(i,j,k=1,2,.)表示。设Ri和Wi(i=1,2,3)分别表示事务Ti的读/写操作。则下列执行是串行的，因为它满足定义5-1的条件（1）和（2），即对所有DM的计程都满足T1先于T2
9、，T2先于T3。DM1：R1X2 R2Y1W3X1 DM2：W1Y2 W2Z1DM3：W2Z2 R3Z3,下列执行可能不是串行的,因为他满足条件5-1,但不满足5-2DM1：R1X1 W1Y1 R2Y1 W3X1 DM2：W2X2 W1Y1DM3：W2Z3 R3Z3,下列执行不是串行的，因为它不满足条件5-1或条件5-2DM1：R1X2 R2Y1W3X1 W1Y1 DM2：W2Z1 W1Y2DM3：W2Z3 Y3Z3,二、操作的冲突与执行的等价,1 操作冲突的类型（1）读写冲突 对数据项X，Ti发出DM-READ（X）,Tj发出DM-WRITE（X），Ti，Tj次序不同则Ti执行结果不同。（2
10、）写写冲突 对数据项X，如果事务Ti发出DM-WRITE(X)，Tj也发出DM-WRITE(X)。执行的次序不同，执行的结果不一样。,2 执行的等价 定义5-2 令E1和E2是两个执行等价，分别用计程L11,L12,.L1n,L21,L22,L2n来刻画，其中Lij表示Ei在DMj的执行。如果下列条件成立，则E1，E2 是等价的。对每个j（1jn），L1j和L2j包含相同集合的DM-READ和DM-WRITE，而且每一对冲突的操作在其两个计程中的相对次序相同。这样就能保证：每个DM-READ操作在两个执行中所读的数据项是相同的；每个数据项的最后DM-WRITE操作是相同的。,定理5-1 设T=
11、T1，T2，Tn是该事务的集合，E是这些事务的一个执行，用计程集合L1，.Ln来表示，如果存在一种T的总次序（称作串行性次序），使得对所有的Ti和Tj的对应冲突操作Oi和Oj，保证在所有计程中Oi和Oj遵循这个串行性次序，则E是可串行的。,三、并发控制处理模式,1 关系（）令E是由一组计程所表示的执行,在E中可能有三种二元关系值得关注,分别记作 RW,WR，WW。对每一对事务Ti，Tj，他们的定义为:,Ti RW Tj 当且仅当在E的某个计程中，Ti读某个数据，随后Tj写此数据。Ti WRTj,当且仅当在E的某个计程中，Ti写某个数据，随后Tj读此数据。Ti WWTj当且仅当在E的某个计程中，
12、Ti写某个数据，随后Tj写此数据。RWR用来标记 RW，WR的连续实施。,用 的术语意味着：对于给定的，如果存在着一个总事务次序，使得与所有的 关系一致，则E是可串行的，要使后面这个条件成立，当且仅当 是无回路的，即不存在一个序列i1 i2,i2 i3,.使得中间出现交叉。,2读写和写写同步的结合模式,定理5-2，令 RWR和WW与执行E相关联，如果下列条件满足，则E是可串行的。所有的 RWR和WW关系是无回路的；存在一个总事务次序，使得这个次序即与所有RWR关系相一致，也与所有WW关系一致。,5.4 两相封锁并发控制算法,一 锁的粒度（Granularity）(1)表锁(2)页锁(3)行锁(
13、4)项锁二 锁类型（1）读锁 S（Shared）（2）写锁 X(eXclusive)（3）更新锁 U(Update)三 锁的相容性,四、两相封锁（2PL）算法思想,2PL算法对并发的控制，通过两个相对独立的阶段进行：第一阶段:称为生长阶段，在这个阶段，一个事务得到越来越多的锁，而不释放任何锁；第二阶段：称为紧缩阶段，如果一个事务释放一个锁，则进入紧缩阶段。在紧缩阶段，这个事务逐步释放锁，并禁止它得到另外的锁；当事务终止或撤销时，所剩余的锁自动释放。,五、2PL算法的基本实现,无副本，且把数据项X的调度程序布置在同X所在的DM中，通过DM的操作隐含地实现锁的请求和释放。(1)读锁可以隐含地DM-
14、READ操作来请求。(2)写锁可隐含地由Pre-Commit 请求。(3)写锁隐含地由DM-WRITE操作释放。因为DM-WRITE表示紧缩阶段的开始。(4)释放读锁需要特殊的释放锁操作，因为DM-READ并不导致紧缩阶段的开始。,六、主副本2PL算法,主副本2PL算法是对基本的2PL算法的改进，要求：(1)对所有逻辑数据项的所有副本，指定其中一个为该数据项的主副本。(2)在访问逻辑数据项的任何副本之前，都必须得到主副本的有关锁。实现过程为：读锁情况：事务首先访问存放主副本X1的DM已确定是否存在冲突锁，无冲突时然后访问存储X2的DM以完成数据的传输。写锁情况：事务首先请求X的主副本X1的DM
15、，以确定是否存在冲突锁，在不存在冲突锁时给X的主副本加写锁，然后向所有的副本发出预提交操作Pre-Commit。为了减少读操作的代价，可以使用快照技术。,七、表决2PL算法,当事务T要写时，它的DM给每一个拥有X副本的DM发Pre-Commit操作，这些DM总是发回“置锁”或“锁阻塞”信号。当DM中大多响应“置锁”后，TM给所有的DM发出DM-WRITE操作，进入第二阶段。否则等待，直到接收到足够的“置锁”操作，才进行提交的第二阶段。,八、集中式2PL算法,2PL的调度程序可以集中放在一个单一的中心场所，而不在数据库中分布。在访问任何场所的数据之前，必须从集中式2PL调度程序中得到对应的锁。实
16、现简单，但通信费用高。,5.5 时间戳并发控制方法,一、基于时标的并发控制方法 1 基本概念（1）时标：用来唯一地识别每个事务并允许排序的标识符。时标除具有唯一性外还有单调性，同一事务管理程序所产生的两个时标将是单调递增的。（2）分配时标的方法 A 使用一个全局（整个系统）的单调递增的计数器（缺点难以维护）。B 每个站点基于本地计数器自治地指定一个时标。时标由两部分组成，如果每个站点能够访问其自身的系统时钟，那么可使用系统时钟值来代替计数器值。,（3）时标排序规则 设两个冲突操作Qij与Qkl分别属于事务Ti与Tk，Qij在Qkl之前执行当且仅当ts(Ti)ts(Tk)。在这种情况下，Ti称为
17、年老的事务，Tk被称为年轻的事务。基本时标法参见图5-1。在图5-1中，有三个事务在并发执行。事务T1的时间戳为ts(T1),事务T2的时间戳为ts(T2),事务T3的时间戳为ts(T3),且ts(T1)ts(T2)ts(T3)。在时刻t8，事务T2的写操作违反了第一条规则，从而T2被撤销，并在时刻t14重新启动。在时刻T14，按照忽略废弃写规则，事务T1的写操作被安全地忽略，因为这次写操作本应在时刻t12被事务T2的写操作覆盖。,2 全局性时标的形成和调整,假设有两个站点，在每个站点设置一个计数器，每当发生一个事务，计数器值加一，这就解决了同一站点内事务的次序问题。对不同站点，在发送报文时把
18、本站点计数器值包含在报文中，用以近似的同步各站点的计数器值。若站点1收到一个报文的计数器值为Y，它比本地现行计数器X的值大，则把本地计数器值X改为Y+1；否则本地计数器值在原值基础上加1。,二、基本时标法,1 规则（1）每个事务在本站点开始时赋予一个全局性唯一时标；（2）在事务结束之前，不对数据库进行物理修改；（3）事务的每个读操作或写操作都具有该事务的时标；（4）对于数据库中的每个数据X，记录对其进行读操作和写操作的最大时标，分别记为RTM（X）和WTM（X）；（5）如果事务被重新启动，则被赋予新的时标。,2 执行过程（1）设Ts是对数据X进行读操作的时标，如果TsWTM(X)则拒绝该操作，
19、并使发出该操作的事务用新时标重新启动；否则执行操作，且把RTM(X)置为：max(RTM(X),Ts)。（2）设Ts是对数据X进行写操作的时标，如果TsRTM(X)或TsWTM(X)则拒绝该操作，并使发出该操作的事务用新时标重新启动；否则执行写操作，且把WTM(X)置为：max(WTM(X),Ts)。这种方法避免死锁是以重新启动作为代价的。,三、保守时标法,1 保守时标法的规则（1）每个事务只在一个站点执行，他不激活远程的程序，仅仅能向远程站点发出读或写请求。（2）每个站点必须按时标时间的顺序发送读/写数据的请求，在传输中也不会改变这个次序，以保证各个站点能够按时标顺序接收来自不同站点的全部读
20、写请求。（3）每个站点都为其他各个站点发来的读写操作开辟一个缓冲区，把接收到的读写操作分别保存在相应的缓冲区中。,2 保守时标的执行步骤假定某个站点K上，其各个缓冲区队列都已不空，即每个站点都已向它至少发送了一个读和一个写操作，就停止接收，处理在缓冲区队列中的操作.例如：站点i上的缓冲区队列情况如下：,站点1 站点2 站点3.站点nR11 R21 R31.Rn1R12 R22 R32.Rn2R13 R23 R24 W11 W21 W31.Wn1 W22 W32.Wn2 W23,由规则2 知不可能有来自任何站点的年长请求到达本站点，此时执行步骤如下：(1)设RT=min（Rij）WT=min（W
21、ij）(2)按下法处理在缓冲区队列里的Rij和Wij：扫描R队列，若各队列中存在：R（ij）WT的Rij则按顺序执行他们，执行完成后就从队列中把它们去掉；扫描W队列，若各队列中存在(Wij)RT的Wij就按顺序执行它们，执行完成后从队列中把它们去掉。(3)修改：RT=min（Rij），WT=min（Wij）此时的Rij和Wij已是剩余的Rij和Wij了。,(4)重复上述（2）和（3），直到没有满足条件的操作，或者：若某个或某些R队列为空时，RT=0；若某个或某些W队列为空时，WT=0。继续接收各个站点发送来的读写请求操作，若其各个缓冲区队列又都不为空，仍按上面的步骤继续。,3 存在的问题和解决
22、办法(1)如果一个站点从不向某个别站点发送操作的话，则执行中假定就不符合，操作就无法执行，解决办法是周期性的发送“空操作”。(2)该方法要求网络上所有站点都连通，这在大型系统中难以做到，可对无实际读写请求的每个站点发送一个时标为很大的空操作。(3)该方法过分保守，一律按时标的顺序执行R和W，其中包括了不会发生冲突的读操作，也被缓冲起来同等对待。,四、多版本时标法,事务管理器分配给每个事务一个时标，这个时标也用来跟踪每一个版本的时标，具体处理如下：（1）一个Ri（X）表示事务i对数据X的一个版本上的读操作，这是通过查找X的一个版本来完成的，如果Ts(Xr)是比Ts（Ti）小的最大时标，那么Xr就
23、是被查找的版本，然后就把Ri（Xr）传送给数据处理器；（2）一个Wi（X）表示为Wi（Xw）操作，这样Ts（Xw）=Ts（Ti），并且被送给数据处理器，当且仅当写操作事务时标Ts（Ti）比其他已经读取X的一个版本（比如Xr）的事务的时标值大，Ts（Xw）Ts（Xr）；换言之，如果调度器已经处理了一个Rj（Xr）操作，若Ts（Ti）Ts（Xr）=Ts（Tj），那么Wi（X）被拒绝。为了节省空间，数据库的多个版本可以不时地被清除。,五、死锁问题,死锁的形成：,1.死锁预防 在2PL调度程序中，如果一个锁请求被拒绝，则调度程度对请求锁的事务Ti和现在拥有锁的事务加以“死锁测试”，如果不发生死锁，则T
24、i允许等待；否则，其中一个事务被撤销。也可以给事务指派优先级，让Ti等待Tj，当且仅当Ti的优先级低于Tj。基于时间戳的死锁预防方法大体有两类：等待 死亡:若Ti等待Tj 如果Ti的优先级低于Tj 则允许等待,否则撤销Tj并迫使它重新启动。受伤 等待:Ti的优先级等于Tj，Ti等待，否则撤销Tj。,2.死锁检测（1）集中式死锁检测 指派一个场所为分布式系统的死锁检测器，每一个调度程序将其局部等待图发送到死锁检测器，然后构造局部图，并组合局部图成系统范围的等待图。（2）层次死锁检测 把数据库场所组成一个层次（或一个树），层次中每一个节点有一个死锁检测器。局部于一个单一节点之死锁在那个场所被检测，
25、包含相同区域的两个或两个以上的场所中的死锁将由区域死锁检测器检测。,六、分布式并发控制算法的性能分析,1.性能评价问题 一个并发控制算法性能的衡量是一个综合指标，涉及四个主要因素：场所间的通信开销；局部处理开销；事务重新启动的次数和费用；事务阻塞的数量。,2.2PL性能分析（1）2PL技术的通信开销 RW 同步 基本2PL：用于RW同步时，需要额外读锁释放操作，它引起通信开锁。主副本2PL：所有的事务必须请求和释放对主副本的读锁，因此RW同步比基本2PL的开销更大。集中式2PL：锁的请求与释放都由集中的2PL调度程序进行，该技术的开销直接与在事务执行期间请求锁的不同点数目成正比。,WW同步 写
26、锁由Pre-Commit隐含并由DM-WRITE隐含释放，因此2PL算法不会引起附加的通信开销。2PL的局部处理开锁：2PL都需要处于活动状态的事务正在读的数据项的读锁。基本2PL做WW/RW 同步，对由活动事务更新的逻辑数据项的所有副本，都需要写锁。用主副本或集中式2PL做WW/RW同步，对由活动事务更新的每一个逻辑数据项都需要一个单一写锁。用主副本或集中式2PL作RW同步，或用表决2PL作WW同步，对由活动事务更新的每一个逻辑数据项的大多数副本需要写锁。,3.2PL的重新启动开销 2PL的重新启动次数和费用取决于死锁的解决技术的选择。4.2PL的阻塞开销 直接与死锁解决方法有关。,七、TO
27、的通信开销,1.基本TO 技术不引起额外的超过基本要求的通信开销。2.T/O的局部处理开销 对由新近事务所读的所有数据项需要R时间戳，对由新近事务所写的所有数据项需要W时间戳（在多版本的情况下，可能需要多个时间戳）,3.TO重新启动开销 基本的TO在发现冲突时，总是重新启动事务，对应费用很高，保守T/O，Thomas写规则尽量减少了重新启动次数，多版本T/O介于两者之间。4.TO的阻塞开销 保守TO用阻塞作为其正常的操作方式。Thomas写规则用在WW同步时不引起阻塞。多版本T/O能获得很好的阻塞特性。,八、并发控制的方法选择,处理悲观情形 假定运行时冲突是经常的，应用保守TO作RW同步，Thomas写规则作WW同步。处理乐观情形 主要是通信与计算开销间的权衡，根据应用而定。,
