分布式数据库中的并发控制PPT学习教案

1、会计学1分布式数据库中的并发控制分布式数据库中的并发控制v并发控制的概念并发控制的概念v事务可串行化理论事务可串行化理论v分布式事务的可串行化调度测试分布式事务的可串行化调度测试v并发控制机制的常用方法及其分类并发控制机制的常用方法及其分类第1页/共50页v基于封锁的并发控制方法概述基于封锁的并发控制方法概述v2PL协议协议v2PL协议的实现方法协议的实现方法v多粒度封锁与意向锁多粒度封锁与意向锁第2页/共50页分布式数据库系统中的死锁处理分布式数据库系统中的死锁处理分布式数据库系统并发控制的时标技术分布式数据库系统并发控制的时标技术12教教 学学 内内 容容分布式数据库系统并发控制的多版本技

2、术分布式数据库系统并发控制的多版本技术分布式数据库系统并发控制的乐观方法分布式数据库系统并发控制的乐观方法34第3页/共50页难难 点点掌握死锁的预防、检测和解决方法掌握死锁的预防、检测和解决方法重重点点 理解基于时标的并发控制方法理解基于时标的并发控制方法 理解基于时标的多版本技术理解基于时标的多版本技术采用验证锁的多版本两阶段封锁采用验证锁的多版本两阶段封锁保守时标法保守时标法第4页/共50页v 全局死锁与等待图全局死锁与等待图v 死锁的预防方法死锁的预防方法v 死锁的检测和解决方法死锁的检测和解决方法第5页/共50页v死锁发生的条件死锁发生的条件 互斥条件：事务请求对资源的独占控制互斥条

3、件：事务请求对资源的独占控制 等待条件：事务已持有分配给它的资源等待条件：事务已持有分配给它的资源, , 又去申请并又去申请并等待别的资源等待别的资源 非抢占条件：直到资源被持有它的事务释放前非抢占条件：直到资源被持有它的事务释放前, , 不可不可能将资源强制从持有它的事务夺去能将资源强制从持有它的事务夺去 循环等待条件：存在事务互相等待的等待圈循环等待条件：存在事务互相等待的等待圈v死锁分类死锁分类 局部死锁：仅在一个站点上发生的死锁局部死锁：仅在一个站点上发生的死锁 全局死锁：涉及多个站点的死锁全局死锁：涉及多个站点的死锁( (即等待圈由多个站即等待圈由多个站点组成点组成) )第6页/共5

4、0页事务事务T1持有持有对对x的锁的锁事务事务T2请求请求对对x的锁的锁事务事务T2持有持有对对y的锁的锁事务事务T1请求请求对对y的锁的锁站点站点A站点站点BT2等待等待T1完成完成释放对释放对x的锁的锁T1等待等待T2完成完成释放对释放对y的锁的锁相互等待引起的全局死锁相互等待引起的全局死锁第7页/共50页T1T2T3站点站点A：x1,y1站点站点C：z3站点站点B：y2,z2等待释放等待释放对对y 的锁的锁等待释放等待释放对对x 的锁的锁等待释放等待释放对对z 的锁的锁站点站点A：存储：存储x和和y的副本，的副本， 发出事务发出事务T1：read(x),write(y)站点站点B：存储：

5、存储y和和z的副本，的副本， 发出事务发出事务T2：read(y),write(z)站点站点C：存储：存储z的副本，的副本， 发出事务发出事务T3：read(z),write(x)多多副副本本引引起起的的三三个个站站点点间间的的死死锁锁第8页/共50页v 等待图等待图一种用来表示事务之间相互等待关系的有向图一种用来表示事务之间相互等待关系的有向图, 是分析死锁是分析死锁的有用工具的有用工具节点表示事务节点表示事务带有箭头的有向边表示带有箭头的有向边表示“等待等待”关系关系如果等待图有回路，就说明有死锁如果等待图有回路，就说明有死锁v 等待图分类等待图分类局部等待图局部等待图(LWFG)全局等待

6、图全局等待图(GWFG)第9页/共50页T1T3T2yxzT1等待等待T2释放对释放对y的共享锁的共享锁(s)T2等待等待T3释放对释放对z的共享锁的共享锁(s)T3等待等待T1释放对释放对x的共享锁的共享锁(s)上例的上例的GWFG等待图等待图第10页/共50页(a)(b)T2T1T1T2T4T3T4T3站点站点1站点站点2LWFG和和GWFG之间的之间的不同不同事务间的等待关事务间的等待关系系T1T2T3T4第11页/共50页v解决死锁的方法解决死锁的方法死锁预防，使引起死锁的必要条件不成立死锁预防，使引起死锁的必要条件不成立 所有资源排序所有资源排序, , 按资源序列申请按资源序列申请

7、将所有并发事务排序将所有并发事务排序, , 按标识符或开始时间按标识符或开始时间 有死锁危险时，事务退出已占有的资源，有两种有死锁危险时，事务退出已占有的资源，有两种方法方法 等待等待- -死亡死亡(Wait-Die)(Wait-Die)：总是重启较年轻的事务：总是重启较年轻的事务( (非占非占先权先权) ) 受伤受伤- -等待等待(Wound-Wait) (Wound-Wait) ：年轻的等待年老的：年轻的等待年老的, , 较年较年轻的重启轻的重启, ,而重启事务并不一定是目前正申请的事务而重启事务并不一定是目前正申请的事务 ( (占先权占先权) ) 死锁检测死锁检测 即检测死锁时循环等待的

8、圈即检测死锁时循环等待的圈第12页/共50页v等待等待-死亡模式死亡模式如果如果TiTi对已被对已被TjTj封锁的一数据项请求封锁的话，则只有在封锁的一数据项请求封锁的话，则只有在TiTi比比TjTj年老时（年老时（TiTjTiTjTiTj），则），则TiTi被终止并带有同一时间戳重新被终止并带有同一时间戳重新启动启动最好总是重新启动较年轻的事务最好总是重新启动较年轻的事务允许较年老的事务去等待已持有资源的较年轻的事务允许较年老的事务去等待已持有资源的较年轻的事务但不允许较年轻的事务去等待较年老的事务但不允许较年轻的事务去等待较年老的事务v受伤受伤-等待模式等待模式如果如果TiTi对已被对已被

9、TjTj封锁的一数据项请求封锁的话，则只有在封锁的一数据项请求封锁的话，则只有在TiTi比比TjTj年轻时（年轻时（TiTjTiTj），才允许），才允许TiTi等待等待否则，否则，TiTi比比TjTj年老（年老（TiTjTiTj），则），则TjTj被终止并带有同一时间戳重被终止并带有同一时间戳重新启动新启动, ,而而TiTi得锁执行得锁执行只有年轻的等待年老的只有年轻的等待年老的第13页/共50页v集中式死锁检测集中式死锁检测选择一个站点负责整个系统的死锁检测选择一个站点负责整个系统的死锁检测, ,死锁检测器放到这个站点死锁检测器放到这个站点每个站点的锁管理器周期性地将本站点的每个站点的锁管理

10、器周期性地将本站点的LWFGLWFG传送给死锁检测器传送给死锁检测器, , 死锁死锁检测器构造检测器构造GWFG, GWFG, 并在其中寻找回路并在其中寻找回路或者，其它每个站点上的锁管理器周期性地把记录本站点上事务的开始或者，其它每个站点上的锁管理器周期性地把记录本站点上事务的开始时间，对锁的持有、请求情况变化的动态表，发送给负责处理封锁的站时间，对锁的持有、请求情况变化的动态表，发送给负责处理封锁的站点，由它维护一张全局封锁动态表，形成点，由它维护一张全局封锁动态表，形成GWFG, GWFG, 并在其中寻找回路并在其中寻找回路如果至少包含一条回路，它会选择一个或者多个事务，把它们取消并恢如

11、果至少包含一条回路，它会选择一个或者多个事务，把它们取消并恢复，释放资源，使得其它事务继续进行。复，释放资源，使得其它事务继续进行。选择的标准是尽可能使撤销并恢复的代价最小，如撤销年轻的事务，撤选择的标准是尽可能使撤销并恢复的代价最小，如撤销年轻的事务，撤销占有较少资源的事务，撤销具有最短运行时间的事务，撤销具有最长销占有较少资源的事务，撤销具有最短运行时间的事务，撤销具有最长运行时间的事务等，使系统情况而定运行时间的事务等，使系统情况而定第14页/共50页v层次式死锁检测层次式死锁检测 以层次方式组织成员以层次方式组织成员DBMS中的死锁检测器中的死锁检测器 死锁发生时死锁发生时, 常常只涉

12、及部分站点常常只涉及部分站点 层次检测的层次结构与网络拓扑结构有关层次检测的层次结构与网络拓扑结构有关 减少了对中心站点的依赖性，从而减少了传输开减少了对中心站点的依赖性，从而减少了传输开销销第15页/共50页v 层次式死锁检测的步骤层次式死锁检测的步骤树叶是各站点的局部死锁检测器，在本站点建立局部等待树叶是各站点的局部死锁检测器，在本站点建立局部等待图图本站点的死锁检测器找出本站点局部等待图中的任何回路本站点的死锁检测器找出本站点局部等待图中的任何回路，并把有关潜在全局回路的信息发送给上一层死锁检测器，并把有关潜在全局回路的信息发送给上一层死锁检测器每个非本地死锁检测器只对它所涉及的紧挨下层

13、进行死锁每个非本地死锁检测器只对它所涉及的紧挨下层进行死锁检测，合并这些接收到的有关潜在全局回路的信息，并找检测，合并这些接收到的有关潜在全局回路的信息，并找出任何回路出任何回路如果还有上层死锁检测器，将经过简化的有关潜在全局回如果还有上层死锁检测器，将经过简化的有关潜在全局回路的信息发送给它上一层死锁检测器，由上一层死锁检测路的信息发送给它上一层死锁检测器，由上一层死锁检测器再进行合并，找出任何全局回路器再进行合并，找出任何全局回路这样，逐层检测，直到最高层。这样，逐层检测，直到最高层。第16页/共50页层层次次式式死死锁锁检检测测方方法法示示意意图图第第0层层死锁检测器死锁检测器第第i层层

14、死锁检测器死锁检测器第第i层层死锁检测器死锁检测器局部局部死锁检测器死锁检测器局部局部死锁检测器死锁检测器局部局部死锁检测器死锁检测器局部局部死锁检测器死锁检测器简化潜在简化潜在死锁图死锁图简化潜在简化潜在死锁图死锁图简化潜在简化潜在死锁图死锁图简化潜在简化潜在死锁图死锁图简化潜在简化潜在死锁图死锁图简化潜在简化潜在死锁图死锁图第17页/共50页v分布式检测分布式检测 每个站点的检测死锁责任相同每个站点的检测死锁责任相同, , 站点之间交换信息站点之间交换信息(LWFG)(LWFG)，是为了确定全局死锁，是为了确定全局死锁 EXEX是指的本地事务正在等待的其他事务所在的还不确是指的本地事务正在

15、等待的其他事务所在的还不确定的站点定的站点 例子例子站点站点1站点站点2T1T2T4T3EXEX第18页/共50页v 分布式死锁检测算法分布式死锁检测算法 使用局部信息建造使用局部信息建造LWFG, LWFG, 该该LWFGLWFG包含包含EXEX节点节点 对每次接收到的信息对每次接收到的信息, , 执行如下对执行如下对LWFGLWFG的修改的修改 对报文中的每个事务对报文中的每个事务, , 若若LWFGLWFG中不存在中不存在, , 则将其加入则将其加入 从从EXEX节点开始节点开始, , 按照报文所给的信息按照报文所给的信息, , 建立一个到下一建立一个到下一个事务的边个事务的边 在新的在

16、新的LWFGLWFG中寻找不含中寻找不含EXEX的的Loop, Loop, 若存在若存在, , 则检测则检测到死锁到死锁 在新的在新的LWFGLWFG中找到含有中找到含有EXEX的的Loop, Loop, 于是有潜在的死于是有潜在的死锁锁, , 再按规定向外传送信息再按规定向外传送信息第19页/共50页v基于时标的并发控制方法基于时标的并发控制方法v基本时标法基本时标法v保守时标法保守时标法第20页/共50页v 基本概念基本概念 不通过互斥来支持串行性，而是通过在事务启动时不通过互斥来支持串行性，而是通过在事务启动时赋给时标（时间戳）来实现赋给时标（时间戳）来实现 时标是用来唯一识别每个事务并

17、允许排序的标识时标是用来唯一识别每个事务并允许排序的标识 如果如果 ts(T1) ts(T2) ts(T1) ts(T2) ts(Tn), ts(Tn), 则调度器产则调度器产生的序是生的序是: T1,T2, . Tn : T1,T2, . Tn v 规则规则 如果如果T1T1的操作的操作Q1(x)Q1(x)和和T2T2的操作的操作Q2(x)Q2(x)是冲突操作是冲突操作, , 那么那么, Q1, Q1在在Q2Q2之前执行之前执行, , 当且仅当当且仅当ts(T1)ts(T2)ts(T1)ts(T2)第21页/共50页v 时标分配方法时标分配方法 全局时标全局时标 使用全局的单调递增的计数器使

18、用全局的单调递增的计数器 全局的计数器维护是个难题全局的计数器维护是个难题 局部时标局部时标 每个站点基于其本地计数器自治地指定一个时标每个站点基于其本地计数器自治地指定一个时标 标识符由两部分组成：标识符由两部分组成：本地计数器值，站点标识符本地计数器值，站点标识符 站点标识符是次要的，主要是本地计数器值站点标识符是次要的，主要是本地计数器值 可以使用站点系统时钟来代替计数器值可以使用站点系统时钟来代替计数器值第22页/共50页v时标法思想时标法思想 每个事务赋一个唯一的时标，事务的执行等效于按时每个事务赋一个唯一的时标，事务的执行等效于按时标次序串行执行标次序串行执行 如果发生冲突，是通过

19、撤销并重新启动一个事务来解如果发生冲突，是通过撤销并重新启动一个事务来解决决 事务重新启动时，则赋予新的时标事务重新启动时，则赋予新的时标 优点是没有死锁，不必设置锁优点是没有死锁，不必设置锁 封锁和死锁检测引起的通信开销也避免了封锁和死锁检测引起的通信开销也避免了 但要求时标在全系统中是唯一的但要求时标在全系统中是唯一的第23页/共50页v 时标性质时标性质 唯一性唯一性 单调性单调性v 全局唯一时间的形成与调整全局唯一时间的形成与调整 每个站点设置一个计数器每个站点设置一个计数器, 每发生一个事务每发生一个事务, 计数器加一计数器加一 发送报文时包含本地计数器值发送报文时包含本地计数器值,

20、 近似同步各站近似同步各站点计数器点计数器第24页/共50页 计数器计数器X X 初值初值X=0 X=0 计数器计数器Y Y 初值初值Y=10Y=10 站点站点1 1 站点站点2 2 时标时标 A D A D 时标时标 TS(A)= TS(D)=TS(A)= TS(D)= 因为因为XY E TS(E)=XY E TS(E)= 改改X=Y+1=11 BX=Y+1=11 B TS(B)= F TS(B)= F 因为因为YX YX TS(C)= C TS(F)= TS(C)= C TS(F)= 本地计数器本地计数器 本地计数器本地计数器 ( (或时钟或时钟) () (或时钟或时钟) )报文报文1 1

21、报文报文2 2计数计数器器站站点点第25页/共50页v规则规则 每个事务在本站点开始时赋予一个全局唯一时标每个事务在本站点开始时赋予一个全局唯一时标 在事务结束前，不对数据库进行物理更新在事务结束前，不对数据库进行物理更新 事务的每个读操作或写操作都具有该事务的时标事务的每个读操作或写操作都具有该事务的时标 对每个数据项对每个数据项x, x, 记下写和读操作的最大时标，记为记下写和读操作的最大时标，记为WTM(x)WTM(x)和和RTM(x)RTM(x) 如果事务被重新启动，则被赋予新的时标如果事务被重新启动，则被赋予新的时标第26页/共50页v基本时标法执行过程基本时标法执行过程令令read

22、_TSread_TS是事务对是事务对x x进行读操作时的时标进行读操作时的时标 若若read_TSWTM(x)read_TSWTM(x)，则拒绝该操作，则拒绝该操作, , 事务重新启事务重新启动动 否则否则, , 执行执行, , 令令RTM(x)=maxRTM(x), read_TSRTM(x)=maxRTM(x), read_TS令令write_TSwrite_TS是事务对是事务对x x进行写操作时的时标进行写操作时的时标 若若write_TS RTM(x) write_TS RTM(x) 或或 write_TS WTM(x) ,write_TS WTM(x) ,则拒绝该操作则拒绝该操作,

23、, 事务重新启动事务重新启动 否则否则, , 执行执行, , 令令WTM(x) = maxWTM(x), WTM(x) = maxWTM(x), write_TSwrite_TSv缺点是重启动多缺点是重启动多第27页/共50页v 基本思想基本思想 一种消除重启动的方法一种消除重启动的方法 通过缓冲年轻的操作，直至年长的操作执行完成，因通过缓冲年轻的操作，直至年长的操作执行完成，因此操作不会被拒绝，事务也绝不被重启动此操作不会被拒绝，事务也绝不被重启动v 规则规则 每个事务只在一个站点执行每个事务只在一个站点执行, , 它不能激活远程的程序它不能激活远程的程序, , 但是可以向远程站点发读但是可

24、以向远程站点发读/ /写请求写请求 站点站点i i接收到来自不同站点接收到来自不同站点j j的读的读/ /写请求必须按时标写请求必须按时标顺序，即每个站点必须按时标顺序发送读顺序，即每个站点必须按时标顺序发送读/ /写数据请写数据请求，在传输中也不会改变这个顺序求，在传输中也不会改变这个顺序 每个站点都为其它站点发来的读每个站点都为其它站点发来的读/ /写操作开辟一个缓写操作开辟一个缓冲区冲区, , 分别保存接收到的读分别保存接收到的读/ /写申请写申请第28页/共50页v 假定某个站点假定某个站点k上上,各个缓冲区队列都已不为空，即每个各个缓冲区队列都已不为空，即每个站点都已向它至少发送了一

25、个读和一个写操作，就停止站点都已向它至少发送了一个读和一个写操作，就停止接收，处理在缓冲区中的操作接收，处理在缓冲区中的操作v 假定站点假定站点i至少有一个缓冲的读和缓冲的写来自网中其它至少有一个缓冲的读和缓冲的写来自网中其它站点站点, 根据规则根据规则2, Site i 知道没有年老的请求来自其它知道没有年老的请求来自其它Site(因为按序接收因为按序接收, 所以不可能有比此更年老的请求到所以不可能有比此更年老的请求到来来, 年老的比年轻的先到年老的比年轻的先到)第29页/共50页例子例子 已知站点已知站点i的缓冲区队列中有来自所有站点的读的缓冲区队列中有来自所有站点的读/写请求如下所示写请

26、求如下所示: 站点站点1 站点站点2 站点站点3 站点站点n R11 R21 R31 Rn1 R12 R22 R32 R13 R23 R24 W11 W21 W31 Wn1 W22 W32 Wn2 W23第30页/共50页执行步骤执行步骤: (1) 设设RT=min(Rij), WT= min(Wij) (2) 按下法处理缓冲区中的按下法处理缓冲区中的Rij和和Wij a. 若队列中有若队列中有 (Rij) WT的的Rij , 则顺序执行这些则顺序执行这些Rij，执行完删掉，执行完删掉 b. 若队列中有若队列中有 (Wij) RT的的Wij, 则顺序执行这些则顺序执行这些Wij，执行完删掉，执

27、行完删掉 (3) 修改修改 RT=min(Rij), WT=min(Wij) ，此时的，此时的Rij和和Wij是队列中剩是队列中剩 余的余的 (4) 重复上述重复上述(2)和和(3), 直到没有满足条件的操作直到没有满足条件的操作, 或者或者: a. 若某个或某些若某个或某些R队列为空时队列为空时, RT=0; b. 若某个或某些若某个或某些W队列为空时队列为空时, WT=0第31页/共50页存在问题和解决方法存在问题和解决方法 如果一个站点从来不向某个站点发送操作的话，那如果一个站点从来不向某个站点发送操作的话，那么执行过程中的假定就不符合，操作就无法进行。么执行过程中的假定就不符合，操作就

28、无法进行。解决办法是，周期性的发送带有时标的空操作解决办法是，周期性的发送带有时标的空操作 此方法要求网络上所有站点都连通，这在大系统中此方法要求网络上所有站点都连通，这在大系统中很难办到。为避免不必要的通信，可对无读写操作很难办到。为避免不必要的通信，可对无读写操作请求的站点，发送一个时标很大的空操作请求的站点，发送一个时标很大的空操作 此方法过分保守，一律按照时序来进行，其中包括此方法过分保守，一律按照时序来进行，其中包括了不冲突的操作了不冲突的操作第32页/共50页v多版本概念和思想多版本概念和思想v基于时标的多版本技术基于时标的多版本技术v采用验证锁的多版本两阶段封锁采用验证锁的多版本

29、两阶段封锁第33页/共50页v基本思想基本思想 保存了已更新数据项的旧值保存了已更新数据项的旧值 维护一个数据项的多个版本维护一个数据项的多个版本 通过读取数据项的较老版本来维护可串行性，使通过读取数据项的较老版本来维护可串行性，使得系统可以接受在其他技术中被拒绝的一些读操得系统可以接受在其他技术中被拒绝的一些读操作作 写数据项时，写入一个新版本，老版本依然保存写数据项时，写入一个新版本，老版本依然保存v缺点缺点 需要更多的存储来维持数据库数据项的多个版本需要更多的存储来维持数据库数据项的多个版本v模式分类模式分类 基于时标排序基于时标排序 基于两阶段封锁基于两阶段封锁第34页/共50页v 数

30、据项数据项X的多版本的多版本 X1, X2, X3, Xkv 系统保存的值系统保存的值 Xi的值的值 两种时标两种时标 Read_TS(Xi): 读时标，成功读取版本读时标，成功读取版本Xi的事务的时的事务的时标，最大的一个标，最大的一个 Write_TS(Xi): 写时标，写入版本写时标，写入版本Xi的值的事务的时的值的事务的时标标第35页/共50页v 多版本规则多版本规则如果事务如果事务T T发布一个发布一个write_item(X)write_item(X)操作，并且操作，并且X X的版本的版本XiXi具具有有X X所有版本中最高的所有版本中最高的write_TS(Xi),write_T

31、S(Xi),同时同时write_TS(Xi)=TS(T)write_TS(Xi)TS(T)read_TS(Xi)TS(T)，那么撤销并回，那么撤销并回滚滚T T；否则创建；否则创建X X的一个新版本，并且令的一个新版本，并且令read_TS(Xi)= read_TS(Xi)= write_TS(Xi)= TS(T)write_TS(Xi)= TS(T)如果事务如果事务T T发布一个发布一个read_item(X)read_item(X)操作，并且操作，并且X X的版本的版本XiXi具有具有X X所有版本中最高的所有版本中最高的write_TS(Xi),write_TS(Xi),同时同时writ

32、e_TS(Xi)=TS(T)write_TS(Xi)=TS(T)，把，把XiXi的值返回给事务的值返回给事务T,T,并且将并且将read_TS(Xi)read_TS(Xi)的值置为的值置为TS(T)TS(T)和当前和当前read_TS(Xi)read_TS(Xi)中较大的一中较大的一个个第36页/共50页图图示示写值写值v1v2v3Vn-1Vn5102092100若读若读 TS(Ri)=95, 则读则读 的值的值若写若写TS(Wk)=93, 则出现了则出现了v1v2v3Vn-1Vn510209210093v于是要拒绝于是要拒绝TS(Wk), 否则否则 TS(Ri)=95读的就是读的就是Vn-1

33、, 而不是而不是v的值的值, 但是按但是按规定规定 TS(Ri)=95应该读的是应该读的是v值值第37页/共50页v 三种锁方式三种锁方式 读，写，验证读，写，验证v 四种锁状态四种锁状态 读封锁（读封锁（read_lockedread_locked） 写封锁（写封锁（write_lockedwrite_locked） 验证封锁（验证封锁（certify_lockedcertify_locked） 未封锁（未封锁（unlockedunlocked）v 锁相容性锁相容性 标准模式锁相容性（写锁和读锁）标准模式锁相容性（写锁和读锁） 验证模式锁相容性（写锁、读锁和验证锁）验证模式锁相容性（写锁、读

34、锁和验证锁）第38页/共50页 (a) 读读/写封锁模式的相容性表写封锁模式的相容性表 读读 写写 读读 写写 是是 否否 否否 否否 读读 写写 验证验证 读读 写写 是是 是是 否否 是是 否否 否否 验证验证 否否 否否 否否 (b) 读读/写写/验证封锁模式的相容性表验证封锁模式的相容性表第39页/共50页v 多版本多版本2PL的思想的思想 当只有一个单独的事务当只有一个单独的事务T T持有数据项上的写锁时，允持有数据项上的写锁时，允许其他事务许其他事务T T读该项读该项X X，这是通过给予每个项，这是通过给予每个项X X的两个的两个版本来实现的版本来实现的 一个版本一个版本X X是由

35、一个已提交的事务写入的是由一个已提交的事务写入的 另一个版本另一个版本X X是每个事务是每个事务T T获得该数据项上写锁时创建的获得该数据项上写锁时创建的 当事务当事务T T持有这个写锁时，其他事务可以继续读持有这个写锁时，其他事务可以继续读X X的的已提交版本已提交版本 事务事务T T可以写可以写X X的值，而不影响的值，而不影响X X已提交版本的值已提交版本的值 但是，一旦但是，一旦T T准备提交，它必须在能够提交之前，得准备提交，它必须在能够提交之前，得到持有写锁的数据项上的验证锁，要等写锁释放之到持有写锁的数据项上的验证锁，要等写锁释放之后后 一旦获得验证锁，数据项的已提交版本一旦获得

36、验证锁，数据项的已提交版本X X被置为版本被置为版本X X的值，版本的值，版本X X被丢弃，验证锁被释放。被丢弃，验证锁被释放。第40页/共50页v基本思想和假设基本思想和假设v执行阶段划分执行阶段划分v使用数据项和事务上的时标使用数据项和事务上的时标v只使用事务上的时标只使用事务上的时标第41页/共50页v基本思想基本思想对于冲突操作不像悲观方法那样采取挂起或拒绝的方法，而是让一个事务执行直到完成对于冲突操作不像悲观方法那样采取挂起或拒绝的方法，而是让一个事务执行直到完成v基于如下假设基于如下假设冲突的事务是少数（查询为主的系统中，冲突少于冲突的事务是少数（查询为主的系统中，冲突少于5%5%

37、）大多数事务可以不受干扰地执行完毕大多数事务可以不受干扰地执行完毕第42页/共50页 验证验证 读读/计算计算 写写/提交提交 读读/计算计算 验证验证 写写/提交提交 乐观法事务执行的各个阶段乐观法事务执行的各个阶段 悲观法事务执行的各个阶段悲观法事务执行的各个阶段第43页/共50页v 事务的三个阶段事务的三个阶段 读段读段/ /计算：计算：在数据对象的局部副本上执行事务，这在数据对象的局部副本上执行事务，这时其他事务不能存取此副本。事务从时其他事务不能存取此副本。事务从DBDB读数据，执读数据，执行计算，并且确定写集数据项的新值。写操作总是行计算，并且确定写集数据项的新值。写操作总是对局部副本，仅当验证通过后，在事务结束处，才对局部副本，仅当验证通过后，在事务结束处，才将其写入将其写入DBDB。 验证段：验证段：检验并发事务的可串性，该阶段验证修改检验并发事务的可串性，该阶段验证修改应用是否引起完整性（一致性）的丢失，验证阶段应用是否引起完整性（一致性）的丢失，验证阶段通过，才能进入写段，否则事务重启动通过，才能进入写段，否则事务重启动 写段写段/ /提交：提交：验证阶段通过，则把事务的更新应用于验证阶段通过，则把事务的