原子提交协议ppt课件

1、原子提交协议原子提交协议分布式提交分布式提交o一个事务处置分为N个进程o每个进程都能决议能否提交或撤销这个事务处置o一个事务处置必需在一切站点提交或者在一切的站点撤销单阶段提交单阶段提交应用程序/协调服务器参与站点参与站点提交提交一致性问题：经典的协定性问题一致性问题：经典的协定性问题o模型o一系列进程P1 ,PNo可靠但不同步的通讯o每条音讯发送都会传到达一切的接受方o转发，网络分片，最终处置)o进程只需系统解体时才失败并终止执行o正确的进程：执行过程中在任何点都没有失败o错误的进程：恰恰相反o假设进程重新开场那么会以新的ID开场一致性问题一致性问题IIIIo问题o一切进程Pi开场于未定形状

2、并推出一个数值Vio进程经过交换它们的值来通讯o每个进程对一个“决议变量di进展设置，然后进入决议形状，并不再修正变量dio条件o终止：最后一切的进程都对其“决议变量进展设置o协定性Agreement：一切正确进程的决议变量都是一致的，即假设进程Pi和Pj是正确的并已进入决议形状，那么有di=djo一致性Intergrity：假设一切正确的进程都推出了同一个值，那么一切曾经处于决议形状的正确进程都取这个值o处理方案：不存在 Fischer et al.,1985失败情况下的原子提交失败情况下的原子提交o不能够性结果在异步系统中，假设某时进程失败，那么不能到达一致o通常为NOo但是：我们将运用另

3、一个的失败模型o进程Pi的集合 i=1,No可靠但不同步的通讯o进程能失效o失败后进程可恢复o进程可将其形状记录在稳定的存储空间o稳定存储空间挽救系统解体，并且在重新开场后是可访问的原子提交的构成原子提交的构成o正常执行o没有失败发生时的执行步骤o终止协议o当一个站点失败，正确的站点依然可以对未决的处置结果作出决议o它们执行一个终止协议对一切未决的处置作出决议o恢复o当一个站点失败并重新开场，它必需恢复一切未被提交的事务o单独站点恢复：终止一切失败时辰的事务o分布式系统：能够需求讯问其它站点，也许在其它系统中一个活动的处置被提交了o独立恢复：一个站点在重新开场时不需求与其它站点通讯原子提交原子

4、提交性质协定性Agreement：一切到达一个决议的进程都要到达同一个决议一致性Intergrity：一切进程赞同，才干对提交作出决议非琐事Non-triviality：假设无失败并且一切进程赞同，决议将提交可恢复性liveness：思索一个带有普通失败的执行。假设一切的失败都被修复，在足够长的时间内不再有失败发生，那么一切的进程最终将给出决议。在无失败情况下的两段式提交协议在无失败情况下的两段式提交协议o协调者：o开场：协调者向一切的参与者发送VOTE-REQo在收到一切参与者表决的情况下o假设一切的表决都是YESo向一切参与者发送提交决议o提交事务o假设至少有一个表决是NOo向一切表决YE

5、S的参与者发送终止决议o终止处置o参与者：o在收到一个VOTE-REQ时o发送一个YES或者NO的音讯o假设表决NO，那么终止处置o在收到决议时只需当表决YES时o假设断定是提交，那么提交事务o否那么撤销事务处置两段式提交的正确性两段式提交的正确性该协议符合原子提交的情况协定性Agreement ：一切进程都决议协调者作出的决议一致性Intergrity ：只需一切进程决议提交，那么协调者才会决议提交非琐事Non-triviality ：无失败并且全部表决YES，将作出提交决议强健性liveness ：在失败情况下协议需求被延伸超时能够导致发生的事情超时能够导致发生的事情协调者初始形状初始形状

6、等待表决等待表决发送发送VOTE-REQ发送提交决议发送提交决议发送终止决议发送终止决议提交提交终止终止all vote YESsome vote NO超时能够导致发生的事情超时能够导致发生的事情参与者等待等待VOTE-REQVote NOVote YES终止终止等待决议等待决议提交提交接受提交接受提交接受终止接受终止超时能够导致发生的事情超时能够导致发生的事情在这三个等待阶段协调者为等待表决而产生超时：决议终止参与者为等待VOTE-REQ产生超时：决议终止参与者为等待决议产生超时：不能一方面作出任何决议，必需讯问根据一个终止协定。假设此时各站点均处于无法收到决议的形状：进程将阻塞。这样的形状

7、叫做“不确定阶段只需当一个参与者知道其他一切参与者的时候，一个协同终止协议才干被执行终止协议终止协议疑心时就讯问。假设任何一方作出决议，将通知我们决议结果：至少总有一个进程曾经作出或者可以作出决议。因此，假设一切的失败被修复，一切的进程将最终得出结果。假设在接遭到一切YES表决之后但在发出任何提交信息之前，协调者失败：一切的参与者无法确定也不能作出任何决议，直到协调者恢复。这是两段式提交的阻塞行为。恢复恢复进程必需知道它们的形状，这样便可以通知其它进程它们能否得出结果。这个形状必需继续：继续性经过记录日志来实现，这要求将日志写入磁盘。在协议中，每次形状改动都将被记录。每次分布式处置都将被记录。

8、这耗价很高。日志条目日志条目 I协调者初始形状初始形状等待表决等待表决发送发送VOTE-REQ发送提交决议发送提交决议发送终止决议发送终止决议提交提交终止终止all vote YESsome vote NOStart 2PC logCOMMIT logABORT log日志条目日志条目 IIII参与者等待等待VOTE-REQVote NOVote YES终止终止等待决议等待决议提交提交接受终止接受终止ABORT logYES recordABORT logCOMMIT log接受提交接受提交带有失败的协议带有失败的协议Coordinator: Write start-2PC record in

9、 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 transaction)

10、 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 l

11、og Return; 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 tr

12、ansaction) write ABORT record in log Else /* participant votes no */ (Abort transaction) Write ABORT record in log注解注解o协议并未涵盖一切的情况o(e.g.,:参与者在遭到VOTE-REQ前能够中止)o与本地处置管理器的协调o在写入中止记录之前o撤销处置并向稳定的存储器写入足够的信息以使撤销具有稳定性o在写入YES记录前o向稳定的存储器中写入足够的信息使得对处置的改动是稳定的，同时处置依然是可改动的。o在写入提交记录前o协调者：o向稳定存储器中写入足够信息使得改动是稳定的o参与者

13、：？重新启动协调者重新启动协调者o对日志扫描o对于事务处置T在协调者失败前执行o未找到开场两段式提交记录o参与者的能够形状：中止或者仍在等待表决恳求o开场两段式提交协议或者中止o找到开场两段式提交记录，但没有找到提交/中止记录o参与者的能够形状：暂停等待表决，等待表决恳求，或者等待结果o重新发送表决恳求o找到提交/中止记录o参与者的能够形状：提交/中止，等待结果o重新发送提交/中止记录重新启动参与者重新启动参与者o找到提交/中止记录o不做任何事o没有YES/提交/中止的事务处置记录o中止并发送vote-abort到协调者o找到YES记录但没有提交/中止记录o讯问协调者渣滓回收渣滓回收o协调者重

14、启时，协调者重新发送一切曾被终止的处置的提交/中止决议o在协调者之上的有限恢复o必需知道哪个事务处置在一切的站点被终止o通常处置中的处理方案o在提交/中止事务处置之后，参与者向协调者发送确认符o一旦协调者获得来自一切站点确实认符，它将做一个END-OF-TRANSACTION记录o在协调者重启之上o找到提交/中止记录，但没有END-OF-TRANSACTION：重新发送决议o找到END-OF-TRANSACTION：不做任何事o基于通常的原那么：从txn删除一切带有END-OF-TRANSACTION的记录保证保证不能够性结果意味着总有能够会继续不确定形状，因此：假设失败会发生，一切的完全异步

15、提交协议会阻塞没有任何提交协议能保证独立的恢复这是一个在任何分布式系统中都隐含的重要问题。开销开销o音讯环节的数量o决议由协议引入的延迟o4个环节(vote-request, vote, decision, ack)o其中3个在事务处置边境on+1个进程的音讯数量o决议带宽协议要求的处置才干o点对点：n + n + n + (n)o广播媒介：1 + n + 1 + (n)o日志环节的数量o协调者开场2PC，表决，提交/中止，参与者开场提交/中止协议规划协议规划o集中式协议o一个协调者管理协议流o通讯只在协调者和独立的参与者之间o参与者之间不需求彼此了解，也不需求通讯o可选的方法o分布式2PCo

16、线性2PCo分级2PC线性线性2PC2PCo线性2PC采用参与者网络构造来减少音讯的数量YESYESYES. . .COM线性线性2PC2PCo撤销情况YESYESNONONONO线性线性2PC2PCo复杂性o音讯环：2no音讯数量：2no当只需两个站点时，经常运用o协调者授权：最后的站点接受成为协调者来做决议形状o其它的协调者授权协议在Oracle中被实现分级式分级式2PC2PCo现实上，分布式系统可以拥有分级式呼叫记录o一个实例可以是效力器也同时可以是客户端o电子商务运用软件J2EEClientTravel AgencyTransportationSafari TravelClientCl

17、ientBrazil AirHotel 1Hotel 2Hotel 3分级式执行分级式执行o普通处置o进程动态的构建树状构造o只需一个进程呼叫另一进程去处置子事务就会有新的边添加o一旦一个衔接被建立，它可以为子向量再利用o原子提交协议o横向：o选择一个协调者o在普通执行过程中，一切的进程必需在回复音讯中背负它们和它们孩子的进程IDo纵向：o中间节点是孩子和参与者与父进程的协调者分级式分级式2PC2PC的主要步骤的主要步骤o主协调者o中间过程o当遭到来自父节点的表决恳求o假设本身表决是YES，递交向子节点表决恳求o假设本身表决是NO，撤销事务向父节点和一切子节点传达NOo当从父节点接纳到NOo撤销事务，并向子节点传达NOo当接纳到一切来自子节点