第九章-分布式事务处理

1、COMPANY LOGO第九章第九章 分布式事务处理分布式事务处理袁帅袁帅 何杰涛何杰涛Company Logo第九章第九章 分布式事务处理分布式事务处理 9.1 概述概述 9.2 简单分布式事务和嵌套事务简单分布式事务和嵌套事务 9.3 原子提交协议原子提交协议 9.4 分布式事务的并发控制分布式事务的并发控制 9.5 分布式事务的死锁分布式事务的死锁 9.6 带复制数据的事务带复制数据的事务 9.7 小结小结Company Logo9.1 9.1 概述概述 事务事务 用于访问和修改各种数据项的一个程序单位。用于访问和修改各种数据项的一个程序单位。 数据库管理系统中的事务是访问数据库的一个程

2、数据库管理系统中的事务是访问数据库的一个程序的执行。序的执行。 分布式系统中，事务是指一组客户请求的执行。分布式系统中，事务是指一组客户请求的执行。从客户角度看，事务是组成一个步骤的一组操作，从客户角度看，事务是组成一个步骤的一组操作，它将服务器的数据从一个一致性状态转换到另一它将服务器的数据从一个一致性状态转换到另一个一致性状态。个一致性状态。Company Logo9.1 9.1 概述概述 分布式事务分布式事务 活动涉及多个服务器的事务。活动涉及多个服务器的事务。Company Logo9.2 9.2 简单分布式事务和嵌套事务简单分布式事务和嵌套事务 简单分布式事务：又称为平面分布式事务，

3、一个简单分布式事务：又称为平面分布式事务，一个客户可请求多台服务器，但每接收客户请求的服客户可请求多台服务器，但每接收客户请求的服务器并不调用其他服务器的操作。务器并不调用其他服务器的操作。XYZTCompany Logo9.2 9.2 简单分布式事务和嵌套事务简单分布式事务和嵌套事务 嵌套事务：一个服务器的一个操作可能触发另一嵌套事务：一个服务器的一个操作可能触发另一个服务器的某个操作，通常后者可能又进一步请个服务器的某个操作，通常后者可能又进一步请求操作，依次类推。同层次的子事务可以并发执求操作，依次类推。同层次的子事务可以并发执行。行。Company Logo9.2 9.2 简单分布式事

4、务和嵌套事务简单分布式事务和嵌套事务TT1T2T11T12T21T22XYMNPCompany Logo9.2 9.2 简单分布式事务和嵌套事务简单分布式事务和嵌套事务事务的第一个服务器成为事务的协调者，负责终止或提交事务。事务的第一个服务器成为事务的协调者，负责终止或提交事务。管理分布式事务访问的对象的每个服务器都是该事务的参与者，每个管理分布式事务访问的对象的每个服务器都是该事务的参与者，每个事务参与者负责跟踪所有参与分布式事务的可恢复对象。事务参与者负责跟踪所有参与分布式事务的可恢复对象。事务执行过程中，协调者在列表中记录所有对参与者的引用，每一个事务执行过程中，协调者在列表中记录所有对

5、参与者的引用，每一个参与者也记录一个对协调者的引用。参与者也记录一个对协调者的引用。join(Trans, Server-id of coordinator) 事务标识符事务标识符TID分为创建该事务的服务器标识符（分为创建该事务的服务器标识符（IP）和对该服务）和对该服务器来说是唯一的数字两部分。器来说是唯一的数字两部分。Company Logo9.2 9.2 简单分布式事务和嵌套事务简单分布式事务和嵌套事务 银银行事行事务务涉及服涉及服务务器器Branch X、Y、Z上的上的账户账户A、B、C、D，客，客户户事事务务T从从A转账转账$4到到C，从从B转账转账$3到到D。 T=openTra

6、nsaction A.withdraw(4); C.deposit(4); B.withdraw(3); D.deposit(3); closeTransaction Company Logo9.2 9.2 简单分布式事务和嵌套事务简单分布式事务和嵌套事务TABCDA.withdraw(4);B.withdraw(3);C.deposit(4);D.deposit(3);BranchX BranchY BranchZ协调者协调者joinjoinjoinopenTransactioncloseTransactionb.withdraw(T,3)协调者在其中某一服务器上，例如BranchX。Com

7、pany Logo9.3 原子提交协议 事务的原子性事务的原子性:要求当一个分布式事务结束时，它要求当一个分布式事务结束时，它的操作要么全部执行的操作要么全部执行,要么全部没执行。要么全部没执行。 原子提交协议：以原子方式完成事务的方式。原子提交协议：以原子方式完成事务的方式。Company Logo9.3 原子提交协议 两阶段提交协议：准备和执行两个阶段。两阶段提交协议：准备和执行两个阶段。CanCommit? (Trans) Yes/No 由协调者发给参与者，询问它是否提交事务。参与者将其表决作应答。由协调者发给参与者，询问它是否提交事务。参与者将其表决作应答。DoCommit（Trans

8、） 由协调者发给参与者，通知所有参与者提交事务。由协调者发给参与者，通知所有参与者提交事务。HaveCommitted（Trans,Woker） 由参与者发给协调者，以证实它已提交了它的事务。由参与者发给协调者，以证实它已提交了它的事务。GetDecision（Trans） Yes/No 当参与者已表决当参与者已表决Yes，而一段延迟后无应答时，由参与者发给协调者询问关于，而一段延迟后无应答时，由参与者发给协调者询问关于事务的决定。用于故障或超时恢复。事务的决定。用于故障或超时恢复。 Company Logo9.3 原子提交协议阶段阶段1（表决阶段）：（表决阶段）：（1）协调者向事务的每个参与

9、者发送一个）协调者向事务的每个参与者发送一个CanCommit？请求；？请求；（2）当参与者受到）当参与者受到CanCommit？请求，将其表决（？请求，将其表决（Yes或或No）应答传递给协调者。若表决为应答传递给协调者。若表决为No，参与者立即中止。，参与者立即中止。阶段阶段2 （根据表决结果完成）（根据表决结果完成）（3）协调者收集表决（包括自己的）；）协调者收集表决（包括自己的）； （a）若无故障且所有表决均为）若无故障且所有表决均为Yes，则协调者决定提交事务，则协调者决定提交事务且向每个参与者发送一个且向每个参与者发送一个DoCommit请求；请求； （b）否则，协调者决定中止事务

10、，且向所有表决为）否则，协调者决定中止事务，且向所有表决为Yes的参的参与者发送与者发送AbortTransaction请求。请求。（4）表决为）表决为Yes的参与者等待协调者的的参与者等待协调者的DoCommit或或AbortTransaction请求。当参与者收到某一消息，按其执行。若请求。当参与者收到某一消息，按其执行。若是提交，发一个是提交，发一个HaveCommitted给协调者作为确认。给协调者作为确认。Company Logo9.3 原子提交协议两阶段提交协议中的超时两阶段提交协议中的超时预备提交（等待表决）已提交完成协调者步骤 状态参与者步骤 状态预备提交（不确定）已提交Can

11、Commit?YesDoCommitHaveCCompany Logo9.3 原子提交协议 两阶段提交协议中的性能两阶段提交协议中的性能有有N个参与者需要传递个参与者需要传递N个个canCommit?消息和应答，消息和应答，然后再有然后再有N个个doCommit消息。消息。消息开销与消息开销与3N成正比，时间开销是成正比，时间开销是3次消息往返。次消息往返。由于协议在没有由于协议在没有haveCommitted消息时仍然能正确运消息时仍然能正确运行行-它们的作用只是通知服务器删除过时的协调者信息它们的作用只是通知服务器删除过时的协调者信息，所以不算在估计开销中。，所以不算在估计开销中。Comp

12、any Logo9.4 9.4 分布式事务的并发控制分布式事务的并发控制 每个服务器要管理很多对象，它必须保证在并发每个服务器要管理很多对象，它必须保证在并发事务访问这些对象时，这些对象仍保持一致性。事务访问这些对象时，这些对象仍保持一致性。因此，每个服务器需要对自己的对象应用并发控因此，每个服务器需要对自己的对象应用并发控制机制。制机制。 分布式事务所有服务器共同保证事务以串行等价分布式事务所有服务器共同保证事务以串行等价方式执行。这就意味着，如果事务方式执行。这就意味着，如果事务T对某一服务对某一服务器对象冲突访问在事务器对象冲突访问在事务U之前，那么在所有服务之前，那么在所有服务器上对对

13、象的冲突操作，事务器上对对象的冲突操作，事务T都在都在U之前。之前。Company Logo9.4 9.4 分布式事务的并发控制分布式事务的并发控制 锁机制锁机制 在一个分布式事务中，每个服务器都为其数据项在一个分布式事务中，每个服务器都为其数据项保留锁。本地锁管理者可以决定是授予锁还是让保留锁。本地锁管理者可以决定是授予锁还是让请求的事务等待。当它知道事务已在参加该事务请求的事务等待。当它知道事务已在参加该事务的所有服务器上提交或者中止之前不能释放锁。的所有服务器上提交或者中止之前不能释放锁。 由于服务器彼此独立地设置它们的锁，有可能不由于服务器彼此独立地设置它们的锁，有可能不同服务器将不同

14、的次序加于事务上，就可能出现同服务器将不同的次序加于事务上，就可能出现分布式死锁的情况。分布式死锁的情况。Company Logo9.4 9.4 分布式事务的并发控制分布式事务的并发控制 T UWrite(A)在服务器X上对A加锁Write(B)在服务器Y上对B加锁 Read(B)在服务器Y上等待U Read(A)在服务器X上等待TCompany Logo9.4 9.4 分布式事务的并发控制分布式事务的并发控制 分布式事务中的时间戳定序并发控制分布式事务中的时间戳定序并发控制 在分布式事务中，每个服务器可以分配全局唯一的时戳。在分布式事务中，每个服务器可以分配全局唯一的时戳。事务第一次访问的服

15、务器分配一个全局唯一的时戳给客户，事务第一次访问的服务器分配一个全局唯一的时戳给客户，该时戳被传给事务中执行了操作的每个服务器。该时戳被传给事务中执行了操作的每个服务器。 例如，在一个服务器上由事务例如，在一个服务器上由事务U访问的数据项在由事务访问的数据项在由事务T访问该数据项后提交，则当访问该数据项后提交，则当U和和T在另外的服务器上访问在另外的服务器上访问相同数据项时，它们也必须按照相同的次序提交。相同数据项时，它们也必须按照相同的次序提交。 为实现在所有服务器相同次序，必须在时戳次序上达成一为实现在所有服务器相同次序，必须在时戳次序上达成一致。时间戳是一个二元组致。时间戳是一个二元组C

16、ompany Logo9.4 9.4 分布式事务的并发控制分布式事务的并发控制 分布式事务中的乐观并发控制分布式事务中的乐观并发控制 乐观并发控制尽管放心去做你想做的事，不用在意其他人乐观并发控制尽管放心去做你想做的事，不用在意其他人正在做什么。如果有问题，那么以后再考虑。正在做什么。如果有问题，那么以后再考虑。 每个事务在允许提交前都是有效的。服务器在验证开始时每个事务在允许提交前都是有效的。服务器在验证开始时分配事务号，事务根据事务号的次序排序。分配事务号，事务根据事务号的次序排序。Company Logo9.4 9.4 分布式事务的并发控制分布式事务的并发控制TU读（A） 在X上读（B）

17、 在Y上写（A）写（B）读（B） 在Y上读（A） 在X上写（B）写（A）Company Logo9.4 9.4 分布式事务的并发控制分布式事务的并发控制并发度死锁性能锁低有中乐观法高无高（废弃度低时）时间戳法较高无较高Company Logo9.59.5分布式事务的死锁分布式事务的死锁UVW交错事务U、V、W，涉及到服务器X、Y管理的数据项A、B，和服务器Z管理的数据项C、DCompany Logo9.59.5分布式事务的死锁分布式事务的死锁WCDZAXUVB 被占用等待被占用被占用被占用等待等待WVU YCompany Logo9.59.5分布式事务的死锁分布式事务的死锁 边追逐法边追逐法

18、这种方法中，不需要构造全局等待图，但是每个服务器都有很多关于边的信息。服务器通过称为探针（probe）的正向消息沿着整个分布式系统的有向图的边传送来发现环路。 当服务器1发现某个事务T开始等待事务U时，而U在等待服务器2上对象时，服务器1发送一个T U的探针消息来启动一次检测过程，这个消息发给阻塞U的服务器2。Company Logo9.59.5分布式事务的死锁分布式事务的死锁WUVCBA 探针传递被占用被占用等待等待等待发起W UW U VW U V W死锁被死锁被检测到检测到服务器X服务器Y服务器ZCompany Logo 事务优先级事务优先级 在上面的算法中，死锁涉及的每个事务都可能发起死锁检在上面的算法中，死锁涉及的每个