《《原子提交协议》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《原子提交协议》PPT课件.ppt（36页珍藏版）》请在三一办公上搜索。
1、原子提交协议,分布式提交,一个事务处理分为N个进程每个进程都能决定是否提交或撤销这个事务处理一个事务处理必须在所有站点提交或者在所有的站点撤销,单阶段提交,一致性问题：经典的协定性问题,模型一系列进程P1,PN可靠但不同步的通讯每条消息发送都会传达到所有的接受方（转发，网络分片，最终处理)进程只有系统崩溃时才失败并终止执行正确的进程：执行过程中在任何点都没有失败错误的进程：恰恰相反如果进程重新开始则会以新的ID开始,一致性问题II,问题所有进程Pi开始于未定状态并推出一个数值Vi进程通过交换它们的值来通讯每个进程对一个“决定变量”di进行设置，然后进入决定状态，并不再修改变量di条件终止：最后
2、所有的进程都对其“决定变量”进行设置协定性（Agreement）：所有正确进程的决定变量都是一致的，即如果进程Pi和Pj是正确的并已进入决定状态，那么有di=dj统一性（Intergrity）：如果所有正确的进程都推出了同一个值，那么所有已经处于决定状态的正确进程都取这个值解决方案：不存在 Fischer et al.,1985,失败情况下的原子提交,不可能性结果（在异步系统中，如果某时进程失败，则不能达到一致）通常为NO但是：我们将使用另一个的失败模型进程Pi的集合 i=1,N可靠但不同步的通讯进程能失效失败后进程可恢复进程可将其状态记录在稳定的存储空间稳定存储空间挽救系统崩溃，并且在重新开
3、始后是可访问的,原子提交的构成,正常执行没有失败发生时的执行步骤终止协议当一个站点失败，正确的站点仍然能够对未决的处理结果作出决定它们执行一个终止协议对所有未决的处理作出决定恢复当一个站点失败并重新开始，它必须恢复所有未被提交的事务单独站点恢复：终止所有失败时刻的事务分布式系统：可能需要询问其它站点，也许在其它系统中一个活动的处理被提交了独立恢复：一个站点在重新开始时不需要与其它站点通讯,原子提交,性质协定性（Agreement）：所有达到一个决定的进程都要达到同一个决定统一性（Intergrity）：所有进程同意，才能对提交作出决定非琐事（Non-triviality）：如果无失败并且所有进
4、程同意，决定将提交可恢复性（liveness）：考虑一个带有一般失败的执行。如果所有的失败都被修复，在足够长的时间内不再有失败发生，那么所有的进程最终将给出决定。,在无失败情况下的两段式提交协议,协调者：开始：协调者向所有的参与者发送VOTE-REQ在收到所有参与者表决的情况下如果所有的表决都是YES向所有参与者发送提交决定提交事务如果至少有一个表决是NO向所有表决YES的参与者发送终止决定终止处理参与者：在收到一个VOTE-REQ时发送一个YES或者NO的消息如果表决NO，则终止处理在收到决定时（只有当表决YES时）如果决定是提交，那么提交事务否则撤销事务处理,两段式提交的正确性,该协议符合
5、原子提交的情况协定性（Agreement）：所有进程都决定协调者作出的决定统一性（Intergrity）：只有所有进程决定提交，那么协调者才会决定提交非琐事（Non-triviality）：无失败并且全部表决YES，将作出提交决定强壮性（liveness）：在失败情况下协议需要被延伸,超时可能导致发生的事情,协调者,初始状态,等待表决,发送VOTE-REQ,发送提交决定,发送终止决定,提交,终止,all vote YES,some vote NO,超时可能导致发生的事情,参与者,等待VOTE-REQ,Vote NO,Vote YES,终止,等待决定,提交,接受提交,接受终止,超时可能导致发生的
6、事情,在这三个等待阶段协调者为等待表决而产生超时：决定终止参与者为等待VOTE-REQ产生超时：决定终止参与者为等待决定产生超时：不能单方面作出任何决定，必须询问（根据一个终止协定）。如果此时各站点均处于无法收到决定的状态：进程将阻塞。这样的状态叫做“不确定阶段”只有当一个参与者知道其他所有参与者的时候，一个协同终止协议才能被执行,终止协议,怀疑时就询问。如果任何一方作出决定，将通知我们决定结果：至少总有一个进程已经作出或者能够作出决定。因此，如果所有的失败被修复，所有的进程将最终得出结果。如果在接受到所有YES表决之后但在发出任何提交信息之前，协调者失败：所有的参与者无法确定也不能作出任何决
7、定，直到协调者恢复。这是两段式提交的阻塞行为。,恢复,进程必须知道它们的状态，这样便能够告诉其它进程它们是否得出结果。这个状态必须持续：持续性通过记录日志来实现，这要求将日志写入磁盘。在协议中，每次状态改变都将被记录。每次分布式处理都将被记录。这耗价很高。,日志条目 I,协调者,初始状态,等待表决,发送VOTE-REQ,发送提交决定,发送终止决定,提交,终止,all vote YES,some vote NO,日志条目 II,参与者,等待VOTE-REQ,Vote NO,Vote YES,终止,等待决定,提交,接受终止,接受提交,带有失败的协议,Coordinator:Write start-
8、2PC record in log Send VOTE-REQ to all participants set timer Wait for vote messages(YES/NO)from all participants On timeout(abort transaction)Write ABORT record in log Send ABORT to all processes from which YES was received;Return;if all votes were YES(and coordinator votes YES)then(commit transact
9、ion)Write COMMIT record to log Send COMMIT decision to all participants Else(abort transaction)Write ABORT record in log Send ABORT decision to all processes from which YES was received,带有失败的协议,Participant:Wait for VOTE-REQ from coordinator On timeout(abort transaction)Write ABORT record in log Retu
10、rn;If participant votes YES(write undo/redo information in log)Write a YES record in log Send YES to coordinator Wait for decision message from coordinator On timeout initiate termination protocol If decision message is COMMIT,(Commit transaction)write COMMIT record in log Else(abort transaction)wri
11、te ABORT record in log Else/*participant votes no*/(Abort transaction)Write ABORT record in log,注解,协议并未涵盖所有的情况(e.g.,:参与者在受到VOTE-REQ前可能中止)与本地处理管理器的协调在写入中止记录之前撤销处理并向稳定的存储器写入足够的信息以使撤销具有稳定性在写入YES记录前向稳定的存储器中写入足够的信息使得对处理的改变是稳定的，同时处理仍然是可改变的。在写入提交记录前协调者：向稳定存储器中写入足够信息使得改变是稳定的参与者：？,重新启动协调者,对日志扫描对于事务处理T在协调者失败前
12、执行未找到开始两段式提交记录参与者的可能状态：中止或者仍在等待表决请求开始两段式提交协议或者中止找到开始两段式提交记录，但没有找到提交/中止记录参与者的可能状态：暂停等待表决，等待表决请求，或者等待结果重新发送表决请求找到提交/中止记录参与者的可能状态：提交/中止，等待结果重新发送提交/中止记录,重新启动参与者,找到提交/中止记录不做任何事没有YES/提交/中止的事务处理记录中止并（发送vote-abort到协调者）找到YES记录但没有提交/中止记录询问协调者,垃圾回收,协调者重启时，协调者重新发送所有曾被终止的处理的提交/中止决定在协调者之上的有限恢复必须知道哪个事务处理在所有的站点被终止通
13、常处理中的解决方案在提交/中止事务处理之后，参与者向协调者发送确认符一旦协调者获得来自所有站点的确认符，它将做一个END-OF-TRANSACTION记录在协调者重启之上找到提交/中止记录，但没有END-OF-TRANSACTION：重新发送决定找到END-OF-TRANSACTION：不做任何事基于通常的原则：从txn删除所有带有END-OF-TRANSACTION的记录,保证,不可能性结果意味着总有可能会持续不确定状态，因此：如果失败会发生，所有的完全异步提交协议会阻塞没有任何提交协议能保证独立的恢复这是一个在任何分布式系统中都隐含的重要问题。,开销,消息环节的数量决定由协议引入的延迟4个
14、环节(vote-request,vote,decision,ack)其中3个在事务处理边界n+1个进程的消息数量决定带宽协议要求的处理能力点对点：n+n+n+(n)广播媒介：1+n+1+(n)日志环节的数量协调者开始2PC，表决，提交/中止，参与者开始提交/中止,协议布局,集中式协议一个协调者管理协议流通讯只在协调者和独立的参与者之间参与者之间不需要彼此了解，也不需要通讯可选的办法分布式2PC线性2PC分级2PC,线性2PC,线性2PC采用参与者网络结构来减少消息的数量,YES,YES,YES,COM,线性2PC,撤销情况,YES,YES,NO,NO,NO,NO,线性2PC,复杂性消息环：2n
15、消息数量：2n当只有两个站点时，经常应用协调者授权：最后的站点接受成为协调者来做决定状态其它的协调者授权协议在Oracle中被实现,分级式2PC,事实上，分布式系统可以拥有分级式呼叫记录一个实例可以是服务器也同时可以是客户端电子商务应用软件J2EE,Client,Travel Agency,Transportation,Safari Travel,Client,Client,Brazil Air,Hotel 1,Hotel 2,Hotel 3,分级式执行,普通处理进程动态的构建树状结构只要一个进程呼叫另一进程去处理子事务就会有新的边增加一旦一个连接被建立，它可以为子向量再利用原子提交协议横向：
16、选择一个协调者在普通执行过程中，所有的进程必须在回复消息中背负它们和它们孩子的进程ID纵向：中间节点是孩子和参与者与父进程的协调者,分级式2PC的主要步骤,主协调者中间过程当受到来自父节点的表决请求如果自身表决是YES，递交向子节点表决请求如果自身表决是NO，撤销事务向父节点和所有子节点传达NO当从父节点接收到NO撤销事务，并向子节点传达NO当接收到所有来自子节点的表决如果所有的表决都是YES并且该进程本身也YES，那么向父节点传达YES如果至少有一个表决为NO，撤销事务并向父节点传达NO当从父节点收到提交/撤销本地提交/撤销，并向子节点传达提交/撤销叶子进程（同上）,工程范例,嵌套事务处理,想法子进程只能当其父进程提交时才能提交子进程撤销其父进程不一定撤销,嵌套事务处理II,原子性依照以下两个规则提交规则：当某节点欲提交，那么它先通过上下文到达其父节点，只有当根节点提交时，他才能被提交撤销规则：如果一个节点撤销，它所有的子节点都要被撤销,再见,
