原子提交协议

《原子提交协议》由会员分享，可在线阅读，更多相关《原子提交协议（36页珍藏版）》请在装配图网上搜索。

1、原子提交协议原子提交协议分布式提交分布式提交o 一个事务处理分为N个进程o 每个进程都能决定是否提交或撤销这个事务处理o 一个事务处理必须在所有站点提交或者在所有的站点撤销单阶段提交单阶段提交应用程序/协调服务器参与站点参与站点提交提交一致性问题：经典的协定性问题一致性问题：经典的协定性问题o 模型n 一系列进程P1,PNn 可靠但不同步的通讯o 每条消息发送都会传达到所有的接受方n（转发，网络分片，最终处理)n 进程只有系统崩溃时才失败并终止执行o 正确的进程：执行过程中在任何点都没有失败o 错误的进程：恰恰相反o 如果进程重新开始则会以新的ID开始一致性问题一致性问题IIo 问题n所有进程

2、Pi开始于未定状态并推出一个数值Vin进程通过交换它们的值来通讯n每个进程对一个“决定变量”di进行设置，然后进入决定状态，并不再修改变量din条件o 终止：最后所有的进程都对其“决定变量”进行设置o 协定性（Agreement）：所有正确进程的决定变量都是一致的，即如果进程Pi和Pj是正确的并已进入决定状态，那么有di=djo 统一性（Intergrity）：如果所有正确的进程都推出了同一个值，那么所有已经处于决定状态的正确进程都取这个值o 解决方案：不存在 Fischer et al.,1985失败情况下的原子提交失败情况下的原子提交o 不可能性结果（在异步系统中，如果某时进程失败，则不能

3、达到一致）n通常为NOo 但是：我们将使用另一个的失败模型n进程Pi的集合 i=1,Nn可靠但不同步的通讯n进程能失效n失败后进程可恢复n进程可将其状态记录在稳定的存储空间n稳定存储空间挽救系统崩溃，并且在重新开始后是可访问的原子提交的构成原子提交的构成o 正常执行n没有失败发生时的执行步骤o 终止协议n当一个站点失败，正确的站点仍然能够对未决的处理结果作出决定n它们执行一个终止协议对所有未决的处理作出决定o 恢复n当一个站点失败并重新开始，它必须恢复所有未被提交的事务n单独站点恢复：终止所有失败时刻的事务n分布式系统：可能需要询问其它站点，也许在其它系统中一个活动的处理被提交了o 独立恢复：

4、一个站点在重新开始时不需要与其它站点通讯原子提交原子提交性质o 协定性（Agreement）：所有达到一个决定的进程都要达到同一个决定o 统一性（Intergrity）：所有进程同意，才能对提交作出决定o 非琐事（Non-triviality）：如果无失败并且所有进程同意，决定将提交o 可恢复性（liveness）：考虑一个带有一般失败的执行。如果所有的失败都被修复，在足够长的时间内不再有失败发生，那么所有的进程最终将给出决定。在无失败情况下的两段式提交协议在无失败情况下的两段式提交协议o协调者：n开始：协调者向所有的参与者发送VOTE-REQn在收到所有参与者表决的情况下o如果所有的表决都是

5、YESn向所有参与者发送提交决定n提交事务o如果至少有一个表决是NOn向所有表决YES的参与者发送终止决定n终止处理o参与者：n在收到一个VOTE-REQ时o发送一个YES或者NO的消息o如果表决NO，则终止处理n在收到决定时（只有当表决YES时）o如果决定是提交，那么提交事务o否则撤销事务处理两段式提交的正确性两段式提交的正确性该协议符合原子提交的情况o 协定性（Agreement）：所有进程都决定协调者作出的决定o 统一性（Intergrity）：只有所有进程决定提交，那么协调者才会决定提交o 非琐事（Non-triviality）：无失败并且全部表决YES，将作出提交决定o 强壮性（li

6、veness）：在失败情况下协议需要被延伸超时可能导致发生的事情超时可能导致发生的事情协调者初始状态初始状态等待表决等待表决发送发送VOTE-REQ发送提交决定发送提交决定发送终止决定发送终止决定提交提交终止终止all vote YESsome vote NO超时可能导致发生的事情超时可能导致发生的事情参与者等待等待VOTE-REQVote NOVote YES终止终止等待决定等待决定提交提交接受提交接受提交接受终止接受终止超时可能导致发生的事情超时可能导致发生的事情在这三个等待阶段o 协调者为等待表决而产生超时：决定终止o 参与者为等待VOTE-REQ产生超时：决定终止o 参与者为等待决定产

7、生超时：不能单方面作出任何决定，必须询问（根据一个终止协定）。如果此时各站点均处于无法收到决定的状态：进程将阻塞。这样的状态叫做“不确定阶段”o 只有当一个参与者知道其他所有参与者的时候，一个协同终止协议才能被执行终止协议终止协议怀疑时就询问。如果任何一方作出决定，将通知我们决定结果：o 至少总有一个进程已经作出或者能够作出决定。因此，如果所有的失败被修复，所有的进程将最终得出结果。o 如果在接受到所有YES表决之后但在发出任何提交信息之前，协调者失败：所有的参与者无法确定也不能作出任何决定，直到协调者恢复。这是两段式提交的阻塞行为。恢复恢复进程必须知道它们的状态，这样便能够告诉其它进程它们是

8、否得出结果。这个状态必须持续：o 持续性通过记录日志来实现，这要求将日志写入磁盘。o 在协议中，每次状态改变都将被记录。o 每次分布式处理都将被记录。o 这耗价很高。日志条目日志条目 I I协调者初始状态初始状态等待表决等待表决发送发送VOTE-REQ发送提交决定发送提交决定发送终止决定发送终止决定提交提交终止终止all vote YESsome vote NOStart 2PC logCOMMIT logABORT log日志条目日志条目 IIII参与者等待等待VOTE-REQVote NOVote YES终止终止等待决定等待决定提交提交接受终止接受终止ABORT logYES record

9、ABORT logCOMMIT log接受提交接受提交带有失败的协议带有失败的协议Coordinator:Write start-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

10、 all votes were YES(and coordinator votes YES)then (commit transaction)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 fro

11、m coordinator On timeout (abort transaction)Write ABORT record in log 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 COMMI

12、T,(Commit transaction)write COMMIT record in log Else (abort transaction)write ABORT record in log Else/*participant votes no*/(Abort transaction)Write ABORT record in log注解注解o 协议并未涵盖所有的情况n(e.g.,:参与者在受到VOTE-REQ前可能中止)o 与本地处理管理器的协调n在写入中止记录之前o 撤销处理并向稳定的存储器写入足够的信息以使撤销具有稳定性n在写入YES记录前o 向稳定的存储器中写入足够的信息使得对处

13、理的改变是稳定的，同时处理仍然是可改变的。n在写入提交记录前o 协调者：n向稳定存储器中写入足够信息使得改变是稳定的o 参与者：？重新启动协调者重新启动协调者o 对日志扫描o 对于事务处理T在协调者失败前执行n未找到开始两段式提交记录o 参与者的可能状态：中止或者仍在等待表决请求o 开始两段式提交协议或者中止n找到开始两段式提交记录，但没有找到提交/中止记录o 参与者的可能状态：暂停等待表决，等待表决请求，或者等待结果o 重新发送表决请求n找到提交/中止记录o 参与者的可能状态：提交/中止，等待结果o 重新发送提交/中止记录重新启动参与者重新启动参与者o 找到提交/中止记录n 不做任何事o 没

14、有YES/提交/中止的事务处理记录n 中止并（发送vote-abort到协调者）o 找到YES记录但没有提交/中止记录n 询问协调者垃圾回收垃圾回收o协调者重启时，协调者重新发送所有曾被终止的处理的提交/中止决定o在协调者之上的有限恢复n必须知道哪个事务处理在所有的站点被终止n通常处理中的解决方案o在提交/中止事务处理之后，参与者向协调者发送确认符o一旦协调者获得来自所有站点的确认符，它将做一个END-OF-TRANSACTION记录n在协调者重启之上o找到提交/中止记录，但没有END-OF-TRANSACTION：重新发送决定o找到END-OF-TRANSACTION：不做任何事n基于通常的

15、原则：从txn删除所有带有END-OF-TRANSACTION的记录保证保证不可能性结果意味着总有可能会持续不确定状态，因此：o 如果失败会发生，所有的完全异步提交协议会阻塞o 没有任何提交协议能保证独立的恢复这是一个在任何分布式系统中都隐含的重要问题。开销开销o 消息环节的数量n决定由协议引入的延迟n4个环节(vote-request,vote,decision,ack)n其中3个在事务处理边界o n+1个进程的消息数量n决定带宽协议要求的处理能力n点对点：n+n+n+(n)n广播媒介：1+n+1+(n)o 日志环节的数量n协调者开始2PC，表决，提交/中止，参与者开始提交/中止协议布局协议

16、布局o集中式协议n一个协调者管理协议流n通讯只在协调者和独立的参与者之间n参与者之间不需要彼此了解，也不需要通讯o可选的办法n分布式2PCn线性2PCn分级2PC线性线性2PC2PCo 线性2PC采用参与者网络结构来减少消息的数量YESYESYES.COM线性线性2PC2PCo 撤销情况YESYESNONONONO线性线性2PC2PCo 复杂性n 消息环：2nn 消息数量：2no 当只有两个站点时，经常应用o 协调者授权：最后的站点接受成为协调者来做决定状态n 其它的协调者授权协议在Oracle中被实现分级式分级式2PC2PCo 事实上，分布式系统可以拥有分级式呼叫记录n一个实例可以是服务器也

17、同时可以是客户端n电子商务应用软件J2EEClientTravel AgencyTransportationSafari TravelClientClientBrazil AirHotel 1Hotel 2Hotel 3分级式执行分级式执行o 普通处理n进程动态的构建树状结构n只要一个进程呼叫另一进程去处理子事务就会有新的边增加n一旦一个连接被建立，它可以为子向量再利用o 原子提交协议n横向：o 选择一个协调者o 在普通执行过程中，所有的进程必须在回复消息中背负它们和它们孩子的进程IDn纵向：o 中间节点是孩子和参与者与父进程的协调者分级式分级式2PC2PC的主要步骤的主要步骤o主协调者o中间

18、过程n当受到来自父节点的表决请求o如果自身表决是YES，递交向子节点表决请求o如果自身表决是NO，撤销事务向父节点和所有子节点传达NOn当从父节点接收到NOo撤销事务，并向子节点传达NOn当接收到所有来自子节点的表决o如果所有的表决都是YES并且该进程本身也YES，那么向父节点传达YESo如果至少有一个表决为NO，撤销事务并向父节点传达NOn当从父节点收到提交/撤销o本地提交/撤销，并向子节点传达提交/撤销o叶子进程（同上）工程范例工程范例嵌套事务处理嵌套事务处理o 想法n子进程只能当其父进程提交时才能提交n子进程撤销其父进程不一定撤销嵌套事务处理嵌套事务处理IIo 原子性依照以下两个规则n 提交规则：当某节点欲提交，那么它先通过上下文到达其父节点，只有当根节点提交时，他才能被提交n 撤销规则：如果一个节点撤销，它所有的子节点都要被撤销再见再见