分布式数据库中的可靠性

分布式数据库系统及其应用2021年11月——2021年1月分布式数据库的可靠性的概念及其度量分布式数据库系统的故障原因和容错技术分布式数据库的可靠性协议网络分割和提交协议不一致性监测和解决方法分布式数据库中的可靠性

第6章可靠性指数据库在一给定时间间隔内不产生任何失败的概率。它强调数据库的正确性，要求数据库正确运行，既符合某种规格化要求。通常用来描述不可修复的系统。可用性强调的是当需要访问数据库时，它是可用的。指在给定的时间t，数据库按照说明能正常运行的概率。通常用于描述那些可以修复的系统。两者关系通常认为构建可用性的系统比可靠性的系统容易；两者是统一的，可靠性高的系统可用性自然是好的；两者又是矛盾的，增加错误风险的情况下，可提高可用性；采用太谨慎的策略会降低可用性。1.1分布式数据库可靠性概念1分布式数据库可靠性概念及其度量例:Site1Site2x1x2Lockx1Lockx22PC

Ready故障出现Site1也Ready故CommitSite2等待此时站点2有两种可能策略:策略一：以正确性为标准，x2保持在锁定状态,直到故障修复时为止。提高了可靠性，但牺牲了可用性。策略二：在数据库中引入不一致性的风险下尽量提高可用性，解锁x2,其它事务可以使用它的值。两阶段提交协议实现了第一个策略，牺牲可用性获得高可靠性；如果要得到高可用性，就要考虑使用第二个策略。Site1正常结束1.1分布式数据库可靠性概念1分布式数据库可靠性概念及其度量：x1和x2是x的副本；事务T是更新x的事务；Site1是协调站点且是事务T原发站点；遵守两阶段提交协议。通常使用两个参数的指标来度量一个分布式数据库的可靠性程度：平均故障间隔时间MTBF和平均修复时间MTTR。平均故障间隔时间MTBF指在可以自我修复的系统中相继失败之间的期望时间；通过可靠性函数R(t)来计算MTBF=∫0∞R(t)dt可靠性函数R(t)与系统失败的概率有直接的关系。平均修复时间MTTR是指修复一个失败的系统所需要的期望时间。它与失败概率有关指数型失败和修复的概率的系统可用性可以描述为：

A=MTBF/(MTBF+MTTR)1.2平均故障间隔时间和平均修复时间1分布式数据库可靠性概念及其度量可用性系统5个9〔99.999%〕常用来描述可用性系统；建立一个高可用性系统比建立一个通常要求的系统要花费更高的本钱(时间、人力、财力等)。具体设计时要仔细分析，与最终用户商定，以确定用户可以忍受多长的停机时间，以及停机可能造成的影响，并且明确说明高可用性系统的本钱。1.2平均故障间隔时间和平均修复时间1分布式数据库可靠性概念及其度量故障任何偏离标准说明的行为称为故障。软故障和硬故障软故障包括间歇性〔intermittent〕和瞬变性〔transient〕故障，通过重启动来修复；硬故障指永久性故障,错误设计等。2.1系统失败的原因2分布式数据库系统的故障原因和容错技术软故障占90%以上并且该比例稳定67年，美空军指出计算机中电子器件故障80%是间歇性的67年，IBM指出90%故障是间歇性的80年，研究指出软故障的发生明显高于硬故障87年，Gray指出大局部软件故障是瞬变性故障软件故障通信或数据库的原因是产生软件故障的主要原因。软件故障的典型原因是代码中的Bug,曾有报告指出,1000条指令中,0.25-10个BUG。软件故障难以排除，一个典型的软件工程在到达测试阶段以前，要经过大量的设计审查和代码检验。审查不同计算机系统中出错的统计数据IBM/XA的OS可靠性报告57%是硬件,12%软件,14%操作,7%环境〔斯坦福线性加速器SLAC〕Tandem计算机18%硬件25%软件25%维护17%操作,14%环境AT&T5ESS数字交换机32.3%硬件,44.3%软件,17.5%操作2.1系统失败的原因2分布式数据库系统的故障原因和容错技术永久性故障错误的设计不稳定或者临界的组件不稳定的外部环境操作者的过失系统失败永久性错误间歇性错误瞬变的错误系统失败的原因容错设计出一种使系统识别出可能会发生的错误的方法。在系统中建立一种机制，使错误在造成系统故障之前就会被检测出来，并能被去除或得到补偿。错误预防技术保证所实现的系统不包含任何错误。错误预防有两个方面：错误回避：保证系统不会带入错误的技术〔详细的设计方法学和质量控制〕错误去除：清查那些在使用了错误回避技术路线后还残留在系统中的错误，并去除它们〔需要大量的测试和证实过程〕2.2基本容错方法和技术2分布式数据库系统的故障原因和容错技术故障检测潜伏的故障：故障发生一段时间后才被检测出来；错误潜伏期：从故障发生到被检测出来的时间；平均检测时间(MTTD)：平均错误潜伏时间；平均修复时间(MTTR)：修复一个失败的系统所需要的期望时间；平均故障间隔时间(MTBF)：在可以自我修复的系统中相继的失败之间的期望时间,由经验或从可靠性函数计算。2.2基本容错方法和技术2分布式数据库系统的故障原因和容错技术

MTBF

MTTDMTTR在这段时间内，可能发生多起错误故障发生造成错误检测到错误修复故障发生造成错误时间

相继发生的事件2.2基本容错方法和技术2分布式数据库系统的故障原因和容错技术冗余所有容错系统设计中都采用的根本原那么是在系统的组件中提供冗余。对冗余的附加和补充的容错原那么是设计的模块化。模块化系统的每个组件被设计为具有定义很好的输入/输出接口的模块。模块化可以把故障隔离在单一的组件中。容错系统实现故障-停止模块〔fail-stopmodule)进程对〔Processpairs)2.2基本容错方法和技术2分布式数据库系统的故障原因和容错技术time正常 停止 恢复 正常易失存储丧失稳定存储ok故障-停止模块不断地对自身进行检测，当检测到一个故障时，就自动停止。优点是缩短了故障检测的潜伏期。2.2基本容错方法和技术2分布式数据库系统的故障原因和容错技术进程对〔Processpairs)通过软件模块的双工来实现容错。它的思想是通过两个相互通信和合作的进程，完成系统的每一个效劳的方法来减少单个的故障点。这两个进程中的一个叫做主进程，另外一个叫备份进程，它们同时提供同样的效劳，主进程与备份进程都是基于故障-停止模块实现。进程对机制要求进程之间进行通信，可以通过共享存储区的手段来实现进程之间的通信。当设计一个可靠的软件环境时，使用基于消息传送的通信机制来实现一个操作系统是非常重要的。由于每个进程都在自己的地址区间内执行，一个进程可能发生的错误就不会传播到另外一个进程，这种方法可以有效地进行错误隔离。2.2基本容错方法和技术2分布式数据库系统的故障原因和容错技术目的分布式数据库可靠性协议是为了保证在分布式数据库上执行的分布式事务的原子性和持久性。这些协议描述了begin-transaction,read,write,abort,commit和recover原语的分布式执行过程。原语Begin_Transaction：该命令执行登记的功能；Read：该命令指定一个数据项；LRM先在Trans的缓冲区中读，假设不在，那么向缓冲区管理器发Fetch命令，读出数据后，LRM将它交给调度程序。Write：该命令指定了数据项和新值。假设在Buffer中得到，那么在那更新，否那么对BufferManager发Fetch命令，读出数据并修改，同时数据的前像和修改后的后像写入Log。Abort：该命令是异常终结事务处理失败的一个信号。LTM读取相应的事务处理日志，并且用数据项的前值取代在易变数据库中的更新后的数据项的值。同时，调度程序被告知异常终结已经被成功地完成。Commit：该命令使LTM将一个事务处理结束记录写入日志中。3.1分布式数据库可靠性协议的组成3分布式数据库的可靠性协议分布式数据库系统的可靠性协议组成包括提交协议、终结协议、恢复协议。提交和恢复协议详细说明了提交命令和恢复命令是如何被执行的。终结协议是分布式系统特有的协议。在执行一个分布式事务时，假设一个站点有故障，希望其它站点也停止该事务。处理这种情况的技术就称为终结协议。3.3分布式数据库可靠性协议的组成3分布式数据库的可靠性协议终结协议与恢复协议的比较假假设一个站点失效终结协议确定了未失效站点如何处理该失效事件；恢复协议确定失效站点重启动后，进程〔协调者，参与者〕恢复它的状态的过程。网络分割时终结协议采取必要的措施终结在不同网络区间执行的活动事务；当网络重新连接后，恢复协议保证使各个冗余数据库相互一致。3.1分布式数据库可靠性协议的组成3分布式数据库的可靠性协议两阶段提交协议的要点:将本地原子性提交行为的效果扩展到分布式事务,保证分布式事务提交的原子性,在不损坏日志情况下,实现快速故障恢复，提高DDB系统的可靠性。两阶段提交协议把事务的提交过程分为两个阶段：第一阶段：表决阶段，即形成一个共同的决定。第二阶段：执行阶段，目的是实现这个决定。允许参与者单方面撤销事务，直到做出肯定性的建议；一旦参与者确定了提交或者撤销提议，它不能再更改它的提议；当参与者处于就绪状态，根据协调者发出的消息的种类，它可转换为相应的提交或者撤销状态；协调者依据全局提交规那么作出全局终结决定；在发生故障的情况下，协调者和参与者可能会进入互相等待的状态，一般采用定时器来解决这种问题。每个进程进入一个状态时都要设置定时器。如果所期待的消息在定时器超时之前没有到来，定时器向进程报警，进程于是调用它自己的超时协议。3.2两阶段提交协议的演变3分布式数据库的可靠性协议初始写begin_commit到日志等待有要求撤消的？写commit到日志提交写end_of_trans.到日志初始准备提交？写ready到日志就绪消息类型？写abort到日志写commit到日志提交撤消撤消写abort到日志写abort到日志协调者参与者nonoabortcommit发送准备消息发送“建议撤消〞消息发送“建议提交〞消息发送“全局撤消〞消息发送“全局提交〞消息ACK发送〞应答ACK确认〞消息两阶段提交协议的活动yesyes假定撤销2PC和假定提交2PC协议这两种协议的根本思想是：只要当一个已就绪的参与者向协调者询问事务的结果时，如果在协调者的日志中找不到该事务的任何信息，就认为该事务“被撤销〞(对假定撤销2PC协议)或“已经提交〞(对假定提交2PC协议)。目的是改善2PC的性能；假定撤销2PC协议中，协调者不必等待参与者的ACK消息，减少了协调者与参与者之间传递消息的数量；当使用假定撤销2PC协议时，可以看出协调者在决定撤销后，可以立即忘记该事务。它可以写入撤销记录，且不用等待参与者确认撤销命令。写入撤销记录后，协调者无需写入事务结束记录。3.2两阶段提交协议的演变3分布式数据库的可靠性协议假定撤销2PC和假定提交2PC协议假定提交2PC协议中，可以不将Prepare写入Log，减少了Log写入的次数；如果使用假定提交2PC协议，协调者在发送准备消息之前，强制性写入一条收集记录，它包含了参与执行事务的所有参与者的名字，此时协调者进入收集状态。随后协调者发送准备消息并进入等待状态。当参与者收到准备消息后，以“建议撤销〞或者以“建议提交〞消息响应。当协调者收到所有参与者的决定后，它就可以作出该事务是撤销或提交的决定。如果断定撤销，协调者写入撤销记录，进入撤销状态，并发送“全局撤销〞命令，直到协调者收到参与者的撤销确认，就写入一条结束记录，并忘记该事务。如果它决定提交该事务，就写入提交记录，发送“全局提交〞消息，然后忘记该事务。当参与者收到“全局提交〞消息后，它们写入提交记录，并更新数据库。如果参与者收到“全局撤销〞消息，它们写入撤销记录并确认。3.2两阶段提交协议的演变3分布式数据库的可靠性协议事务阻断：某个站点上本来可以终结〔提交或撤销〕的子事务，由于分布式数据库系统的故障，它必须等到有故障的子事务修复后，取得必要的信息才能决定。故障的恢复是不可预料，所以它占有的资源也不能释放，也没法继续执行，此时称该事务处于事务阻断状态。阻断协议：提交协议称为阻断协议是指发生某类故障时，使分布式事务可能处于阻断状态。在两阶段提交协议中，如果在提交阶段协调者出故障，假设某个参与者与此同时宣布其已就绪提交，它必须等到协调者修复后，才能决定是否提交。在这种情况下，两阶段提交协议是阻断协议。事务阻断降低了系统的可用性，因为它们持有的锁不能被释放。3.3事务阻断与终结协议3分布式数据库的可靠性协议终结协议：允许一事务在有故障情况下仍能正确地结束。它提高系统的可用性。当正常的提交过程被故障中断时，就调用终结协议，使无故障的站点正确地终结该事务。终结的可能类型(提交还是撤销)依赖于当事务被故障中断时提交协议使它处于什么状态。终结协议仅对某些类型的故障起作用，而不是对所有故障都起作用。3.3事务阻断与终结协议3分布式数据库的可靠性协议判断2PC协议是终结协议的条件至少有一个站点已收到结果命令。此时，可由该站点告诉其它参与者关于该事务的结果，并由它们来终结该事务。没有一个参与者曾收到过结果命令，并且只有协调者站点出故障。此时，所有参与者站点都是可工作的，参与者可以选举一个新的协调者，然后继续。没有一个可工作的参与者曾收到此命令，并且至少有一个参与者出故障时，终结就不可能。因为可工作的参与者无法知道出故障的参与者它已干过什么，仍无法独立作出决定。3.3事务阻断与终结协议3分布式数据库的可靠性协议终结协议在协调者和参与者的定时器超时时发挥作用。超时发生在目的站点在期望的时间内没有从发送站点得到所期望的消息时。处理超时的方法依赖于失效发生的时间和失效的类型。因此需要考虑在两阶段提交协议执行时的不同时间发生失效的情况。由于使用两阶段提交协议的状态转换图而使讨论变得容易。状态图中，圆形表示状态，边表示状态转换，终结状态用同心圆表示。边的标号按如下方式解释：横线上方表示状态转换的原因，即所收到的消息；横线下方表示状态转换时所发出的消息。3.42PC协议的终结协议3分布式数据库的可靠性协议超时处理技术协调者超时：协调者可以在三种状态中发生超时故障：等待状态、提交状态和撤销状态。在等待状态超时：在等待状态，协调者正在等待参与者的局部决定。协调者不能单方面提交事务，因为不满足全局提交规那么。协调者可以决定“全局撤销〞事务，此时，协调者在日志中写入撤销记录，并向所有参与者发送“全局撤销〞消息。在提交状态或撤销状态发生超时：在这种情况下，协调者不能确定是否在所有参与者站点上本地恢复管理程序都执行完提交或撤销过程。因此协调者重复发出“全局提交〞命令或“全局撤销〞命令给没有响应的站点，并等待确认。3.42PC协议的终结协议3分布式数据库的可靠性协议初始写begin_commit到日志等待有要求撤消的？写commit到日志提交写end_of_trans.到日志初始准备提交？写ready到日志就绪消息类型？写abort到日志写commit到日志提交撤消撤消写abort到日志写abort到日志协调者参与者nonoabortcommit发送准备消息发送“建议撤消〞消息发送“建议提交〞消息发送“全局撤消〞消息发送“全局提交〞消息ACK发送〞应答ACK确认〞消息两阶段提交协议的活动yesyes协调者超时IWCAFcommit-申请申请-prepare*ack*-ack*-_t_abortanyabortanycommit_t_commit_t_abort*noabort*prepared*commit*t=timeout超时处理技术参与者超时〔被阻断时出现〕在初始状态发生超时：参与者在该状态下正在等待“准备〞消息，此时协调者必然在初始状态发生失效。参与者在超时后可以单方面撤销事务。在就绪状态发生超时：参与者在该状态下正提议提交事务，但不知道协调者的全局决定，参与者不能单方面作出决定。由于它处于就绪状态，它必须提议事务。因此，它不能改变它的决定和单方面撤销。另一方面，它不能单方面决定提交事务，因为其他参与者可能提议撤销。在这种情况下，参与者将保持阻断，直到它从其他站点处了解到事务的最终命运。3.42PC协议的终结协议3分布式数据库的可靠性协议初始写begin_commit到日志等待有要求撤消的？写commit到日志提交写end_of_trans.到日志初始准备提交？写ready到日志就绪消息类型？写abort到日志写commit到日志提交撤消撤消写abort到日志写abort到日志协调者参与者nonoabortcommit发送准备消息发送“建议撤消〞消息发送“建议提交〞消息发送“全局撤消〞消息发送“全局提交〞消息ACK发送〞应答ACK确认〞消息两阶段提交协议的活动yesyes参与者超时IRCA申请-prepareprepared等价于结束状态_t_ping申请-preparenocommitackabortackcommitackabortack设计终结协议如果参与者之间能够互相通信，可以设计一个更加分布的终结协议。超时的参与者只需简单地请求其他参与者来帮助它作出决定。考虑：假定Pi是超时的参与者〔询问Pj〕，其它参与者Pj按如下响应：Pj处于初始状态，于是单方面Abort，并回送“建议abort〞给Pi；Pj处于就绪状态，此时不能帮助Pi终结；Pj处于提交或撤销状态，此时向Pi发送“建议提交〞或“建议撤销〞消息。3.42PC协议的终结协议3分布式数据库的可靠性协议协调者站点失效协调者在初始状态失效发生在协调者初始化提交过程之前。因此，它将在恢复时启动提交过程。协调者在等待状态失效这时协调者已经发送了“准备〞命令。恢复时，协调者将从头开始启动提交过程，再次发送“准备〞消息。协调者在提交状态或撤销状态失效这时，协调者已经把它的决定通知了参与者，并终结了事务。在恢复时，如果它已经收到了所有确实认消息，就不需要做任何事情。否那么，就要启动终结协议。3.52PC协议的恢复协议3分布式数据库的可靠性协议参与者站点失效一个参与者在初始状态失效在恢复时，该参与者应该单方面撤销事务。一个参与者在就绪状态失效这时协调者已经收到失效站点在失效前发送的肯定决定。恢复时，失效站点的参与者认为是在就绪状态发生了超时，于是启动终结协议来处理该事务。一个参与者在提交状态或撤销状态失效这些状态表示了终结条件，所以在恢复时，参与者不需要采取任何专门的措施。3.52PC协议的恢复协议3分布式数据库的可靠性协议提交协议是非阻断的充要条件是在其状态转换图中不包含两种情形:没有状态是即与提交状态又与撤销状态“相邻〞；不存在不可提交状态是与提交状态“相邻〞；相邻指从一个状态经过一次转换就可以到达的另一个状态。3.6三阶段提交协议3分布式数据库的可靠性协议2PC中的状态如果任意一个进程处于提交状态，就知道所有站点都已建议提交事务，这些状态称为可提交的。C(提交)状态是可提交状态,其它为不可提交状态。就绪状态是不可提交状态，由于一个进程处于此状态并不意味着所有进程都已建议提交事务，所以它是不可提交的。等待状态是不可提交状态。它们都侵犯了非阻断协议的充要条件,从而考虑改变2PC,使其满足非阻断协议条件。在等待状态和提交状态之间,或者在就绪状态和提交状态之间增加另一种状态作为缓冲状态,用于在准备提交但还没有提交的时候，从初始状态到提交状态之间有三次状态转换，从而有了3PC协议。3.6三阶段提交协议3分布式数据库的可靠性协议IWACcommitpreparevote-abortglobal-abortvote-commitprepare-to-commitIRACpreparevote-commitglobal-abortACKprepare-to-commitready-to-commitpreparevote-abort3PC中事务的状态转换图PCPCready-to-commitglobal-commitglobal-commitACK(a)协调者(b)参与者协调者参与者初始写begin_commit到日志等待有要求撤消的？写Prepare-to-commit到日志准备提交写end_of_trans.到日志初始准备提交？写ready到日志就绪消息类型？写abort到日志写prepare-to-commit到日志准备提交撤消撤消写abort到日志写abort到日志准备撤消提交全局撤消准备提交ACKACK

nonoabortPrepare-to-commit写commit到日志提交提交写commit到日志撤消提交准备提交

在中事务执行的过程3PC协调者超时在等待状态超时：与2PC中协调者在等待超时相同,协调者单方面决定撤销事务，然后它在日志中写入撤销记录，向所有建议提交事务的参与者发送“全局撤销〞消息。在预备提交状态超时：此时协调者不知道未响应的参与者是否已经转换到预备提交状态。但它知道它们至少处于就绪状态，这意味着它们一定已经建议提交事务。因此协调者可以发送“预备提交〞消息使所有参与者转换到预备提交状态，再将提交记录写入日志，并发送“全局提交〞消息给所有可操作的参与者。在提交/撤销状态超时：协调者不知参与者是否已确实执行了提交(撤销)命令，但是它们至少处于预备提交状态。因此协调者不需要做专门的处理。3.7三阶段提交协议的超时处理3分布式数据库的可靠性协议参与者超时在初始状态超时：与2PC中的情况相同。在就绪状态超时：参与者已经建议提交事务，但不知道协调者的全局决定。由于与协调者失去联系，终结协议将选举一个新的协调者，新协调者根据三阶段提交协议的终结协议终结事务。在预备提交状态超时：参与者已收到“预备提交Prepare-to-commit〞消息,正在等待来自协调者的“全局提交〞消息,处理同第二条。3.7三阶段提交协议的超时处理3分布式数据库的可靠性协议协调者参与者PREPAREPREPAREDCOMMITPRECOMMITACK1.等待超时:撤销事务3.提交/撤销超时:

忽略1.初始超时:

撤销事务2.就绪超时:

终结协议3.预备提交超时:

终结协议2.预备提交超时:把参与者移入预备提交终结协议规那么新协调者在等待状态：将全局撤销事务。此时参与者可能处于初始状态、就绪状态、撤销状态或预备提交状态等任何状态。假设参与者处于预备提交状态，正在等待“全局提交〞消息，但它们却收到“全局撤销〞消息。它们的状态转换图不存在从预备提交状态到撤销状态的转换，而这种转换对于终结协议是必需的，所以该转换应当是执行终结协议时的一种合法转换。新协调者处于预备提交状态：此时参与者可以处于就绪状态、预备提交状态或提交状态。没有参与者可能处于撤销状态。协调者因此将全局提交事务,并发送“全局提交〞消息。新协调者处于撤销状态：收到第一个消息后，参与者也都转换到撤销状态。3.8三阶段提交协议的终结协议3分布式数据库的可靠性协议3PC与2PC恢复协议的差异很小协调者在等待状态失效按照终结协议，参与者已终结事务,因此,协调者在恢复时必须向它们询问以确定如何终结事务。协调者在预备提交状态失效终结协议再一次指导可操作参与者终结事务。由于此过程可从预备提交状态转换到撤销状态，协调者必须询问以确定如何终结事务。一个参与者在预备提交状态失效它必须询问以确定其它参与者如何终结事务。3.9三阶段提交协议的恢复协议3分布式数据库的可靠性协议三阶段提交协议的一个特性：使用三阶段提交协议，能够无阻断地终结事务。网络分割是由通信线路故障引起的简单分割，仅仅是网络分裂成两局部多重分割，更复杂网络分割非阻断协议的存在性即在发生网络分割时,是否存在允许独立恢复的协议独立恢复是指站点重启动时,无需远程访问假设存在处理分割的非阻断协议,那么,该协议可使某个分割中的站点到达终结决定,而且这个决定与另一分割中的决定一致一般结论独立恢复协议只存在于单站点故障的情形假设发生网络分割的时候,丢了报文的话,那么不存在任何非阻断的协议能从网络分割故障中恢复4.1网络分割概述4网络分割与提交协议非冗余数据库任何需要访问存储在另一网络区域里的数据项的新事务都被阻断,等待网络修复位于同一区域里的数据项的并发访问由并发控制算法处理网络分割时由提交协议处理冗余数据库分割时,副本可能位于不同的区域由复制协议处理4.1网络分割概述4网络分割与提交协议网络分割处理策略一致性与可用性的选择非冗余数据库处理网络分割的终结协议集中式协议，基于集中式并发控制算法(主站点法和主副本法)基于表决的协议冗余数据库处理网络分割的终结协议复制控制协议4.1网络分割概述4网络分割与提交协议多数法和基于法定人数法在事务中止或提交前,大多数站点必须一致同意中止或提交基于法定人数的规那么每个站点i有选票数Vi,Vi是正整数V=Vi事务在提交前，它必须获得提交法定票数Vc事务在Abort前，它必须获得Abort法定票数VaVa+Vc≤V,当0≤Va,Vc≤Vni=14.2基于表决的协议4网络分割与提交协议网络分割时,在每个分割局部选择一个新的协调者3PC中参加PA状态,从而不允许从Wait/Ready到Abort状态的转换原因有多个协调者阻止事务终结,不允许多个协调者得出不同的结论,因此希望协调者获得撤销的决定如果新协调者故障,它不知道是否到达提交或撤销的法定票数,这样参与者必须明确做出提交或撤销的决定Ready(或Wait)都不满足该需求,预示引入另一个状态Pre-Abort,该状态在Ready和Abort之间4.2基于表决的协议4网络分割与提交协议IWACcommitpreparevote-abortglobal-abortvote-commitprepare-to-commitIRACpreparevote-commitglobal-abortACKprepare-to-commitready-to-commitpreparevote-abort基于法定人数3PC中事务的状态转换图PCPCready-to-commitglobal-commitglobal-commitACK(a)协调者(b)参与者PAready-to-abortglobal-abortPAready-to-abortglobal-abort基于法定人数的3PC集中式协议选择一个新的协调者协调者收集状态信息,并按如下规那么执行1)假设至少一个站点已Commit(Abort),那么协调者对其它站点发送Commit(Abort)命令2)假设处于PC状态站点的票数>=Vc,那么发送Commit3)假设PA状态站点的票数>=Va,那么发送Abort4)假设PC状态站点的票数+Ready状态站点的票数>=Vc,那么发送PC命令给不确定站点,等待2)状态出现5)假设PA状态站点的票数+Ready状态站点的票数>=Va,那么发送PA命令给不确定站点,等待3)状态出现6)否那么,等待故障修复4.2基于表决的协议4网络分割与提交协议数据复制的目的高吞吐量较好的响应时间高可用性复制作为可选择的提交协议数据在多站点独立更新,使用“惰性复制协议〞减少数据不一致问题.4.3复制控制协议4网络分割与提交协议根本方法：每个副本看作一个独立的数据项X1X2X3LockmgrX3LockmgrX2LockmgrX1TxiTxjTxk对象X有副本X1,X2,X34.3复制控制协议4网络分割与提交协议Read(X):获取X1共享锁获取X2共享锁获取X3共享锁分别读X1,X2,X3事务结束时,释放X1,X2,X3锁X1lockmgrX3lockmgrX2lockmgrreadWrite(X):获取X1互斥锁获取X2互斥锁获取X3互斥锁写新值到X1,X2,X3事务结束时,释放X1,X2,X3锁X1X3X2locklocklockwritewritewrite读锁和访问只对一个副本写锁全部,并且更新全部副本读可用性高写可用性低，只要有一个副本不可获得，更新事务就不能终结ROWA方法X1X2X3读者加锁写者发现冲突!4.3复制控制协议4网络分割与提交协议ROWA的改进(ROWA-A)ROWA-A“读一个写所有可获得协议〞根本思想是写命令在所有可获得的副本上执行，然后事务终结，当时不可获得的副本将在它们重新可获得时被捕获更新事务T的协调者向所有包含x副本的站点发送WT(x),并等待执行(或拒绝)确实认.当不可获得站点恢复时,也将更新自己的数据库.但如果站点在T开始之前就不可获得,它们就可能没有注意到T的存在,以及T对x的更新.问题协调者认为不可获得的参与者仍然工作,并且更新了x,但是其确认没有到达协调者站点在事务启动时不可获得,随后恢复并开始执行事务4.3复制控制协议4网络分割与提交协议于是,协调者在提交前要进行有效性验证检查所有不可获得的站点是否仍然不可获得,如果协调者收到一个响应,它就撤销T.假设都是不可获得,那么检查在WT(x)执行是可获得的站点仍然可获得,是那么提交事务ROWA-A比ROWA协议能更好地适应失效,包括网络分割.ROWA的改进(ROWA-A)4.3复制控制协议4网络分割与提交协议基于法定人数的复制控制Gifford算法读法定人数Vr,写法定人数Vw规那么1：Vr+Vw>V，可防止读-写冲突规那么2：Vw>V/2，防止写-写冲突该算法确保了在两个不同网络区域上启动且访问同一数据的事务不会同时终结4.3复制控制协议4网络分割与提交协议惰性复制协议思想只在一个或多个副本上执行更新,以后再将更新传播到所有副本上特点所有权参数：定义更新副本的权限,副本可以更新就称为主Copy(主站点),否那么称辅Copy(辅站点)传播参数：定义何时把对一个副本的更新传播到包含该对象的其它副本刷新参数：定义了刷新事务的调度策略配置参数：描述站点和网络的特点4.3复制控制协议4网络分割与提交协议两类所有副本都可更新,存在副本的组所有权,常用延迟立即方式更新只有一个被更新的主站点(惰性主站点法)几种刷新方案:按需刷新,每次提交执行查询时,执行所有收到的刷新事务来刷新被查询读取的辅Copy,造成查询响应延迟成组刷新,根据应用刷新要求,成组执行刷新事务定期刷新,在固定时间间隔内触发刷新惰性复制协议4.3复制控制协议4网络分割与提交协议网络的一致视图可靠性算法是假定:全部能工作的站点对网络的所有站点(包括其本身)的状态(即工作或故障)具有一致的视图决定网络的一致视图监视网络的状态，当站点状态发生转换时,能及时发现新的信息一致地传播给全部站点5.1决定网络的状态5不一致性检测和解决方法假设建于广义的网络范围内每个站点有一状态表,每个站点一个表项,记录其工作/不工作，程序可查询状态表得到状态信息任何程序能够在任一站点设置一个“看守〞,当该站点变化状态时它就收到一个中断分割时,状态表和一致视图的意义站点只认为那些能和它通信的站点是工作的一致视图的数目与别离的站点组数目一样多5.1决定网络的状态5不一致性检测和解决方法监视网络的状态决定一站点是否工作时向它请求一个报文,然后等待到超时控制站点(请求站点)受控站点在一广义监视算法中，受控站点周期性地发送I-am-up〔我在工作〕报文5.1决定网络的状态5不一致性检测和解决方法网络站点K-3UP站点K-2DOWN站点K-1站点KUPDOWN(状态)网络上站点的状态站点K控制站点K-3,即它检查来自K-3的I-am-up报文是否到达，站点K负责发现站点K-1和K-2从不工作到工作的恢复，上图中K-1和K-2不一定是有故障,它们可能在分割的另一组中，图反映了站点K和K-3的网络视图播送新的状态监视功能每次检测出一个状态变化,就激活此播送功能此功能的目的是播送新的状态表，使同一组的全部站点具有相同的状态表此功能可由假设干站点并行激活,需要某种机构来控制冲突状态表的每个新的版本附加一全局唯一的时间戳在I-am-up报文中包含当前状态表的版本号启动新状态表播送的站点首先执行一次同步以获得一时间戳，然后发送状态表给已答复的所有站点5.1决定网络的状态5不一致性检测和解决方法需求处理故障的策略有可能牺牲正确性来提高可用性，因此接受了不一致性的风险在这种情况下，监测这些不一致性，并尽可能地加以解决是很有用的概念需要首先发现哪些数据局部已经不一致〔不一致性检测〕然后根据发生的情况，给这些局部赋予一个最合理的值〔不一致性的解法〕5.2不一致性的检测和解决方法概念5不一致性检测和解决方法提出问题假设网络分割期间,在两个或多个站点组中已执行了假设干事务,可能对同一数据片断的不同副本进行了独立更新检测方法一种比较自然的方法比较各副本的内容,检查其是否相同，但是这种方法不仅效率低，一般也是不正确的。5.3不一致性的检测5不一致性检测和解决方法检测方法采用版本号允许对数据项操作的站点的副本是主副本,其它是孤立或隔离的副本正常工作期间,全部副本都是主副本,并且互相一致,每份副本维持一个原版号和一个当前版本号网络分割时,每个孤立副本的原版本号被置为当前版本号值,并且,直到分割修复为止,此原版号不会改变5.3不一致性的检测5不一致性检测和解决方法例子前提数据项x的副本x1,x2,x3存储在三个不同站点V1,V2,V3分别是x1,x2,x3的版本号初始时,三份副本一致,所以有:V1=(0,2)，V2=(0,2)，V3=(0,2)，假设经过了两次更新〔原版本号，当前版本号〕发生一次分割,把x3从其它两个副本分开,多数法选择x2和x1为主副本,版本号变为V1=(0,2)，V2=(0,2)，V3=(2,2)网络分割期间,假设只更新主副本,版本号为V1=(0,3)，V2=(0,3)，V3=(2,2)修