《6章_分布式数据库中的可靠性_.ppt》由会员分享，可在线阅读，更多相关《6章_分布式数据库中的可靠性_.ppt（88页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、徐俊刚徐俊刚（)20092009年年2 2月月20092009年年6 6月月1.1.分布式数据库的可靠性的概念及其度量分布式数据库的可靠性的概念及其度量2.2.分布式数据库系统的故障原因和容错技术分布式数据库系统的故障原因和容错技术3.3.分布式数据库的可靠性协议分布式数据库的可靠性协议4.4.网络分割和提交协议网络分割和提交协议5.5.不一致性监测和解决方法不一致性监测和解决方法分布式数据库中的可靠性分布式数据库中的可靠性 第第6章章可靠性指数据库在一给定时间间隔内不产生任何失败的概率。它强调数据库的正确性，要求数据库正确运行，既符合某种规格化要求。通常用来描述不可修复的系统。可用性强调的是
2、当需要访问数据库时，它是可用的。指在给定的时间点系统可以正常运行的概率。通常用于描述那些可以修复的系统。两者关系通常认为构建可用性的系统比可靠性的系统容易两者是统一的，可靠性高的系统可用性自然是好的两者又是矛盾的，增加错误风险的情况下，可提高可用性;采用太谨慎的策略会降低可用性1.1 分布式数据库可靠性概念分布式数据库可靠性概念1 1 分布式数据库可靠性概念及其度量分布式数据库可靠性概念及其度量例:Site1 Site2 x1 x2 Lock x1 Lock x2 2PC Ready故障出现Site1也Ready故CommitSite 2 等待此时Site 2有两种可能:a 以正确性为标准，x
3、2则等待,并Lock 2,直到故障恢复。提高了可靠性，但牺牲了可用性。b 引入不一致性的风险下,尽量提高可用性，解锁x2,其它事务可以使用它的值。Site 1 正常结束1.1 分布式数据库可靠性概念分布式数据库可靠性概念1 1 分布式数据库可靠性概念及其度量分布式数据库可靠性概念及其度量已知已知x1和和x2是是x的副本的副本事务事务T是更新是更新x的事务的事务Site 1是协调站点是协调站点Site 1是事务是事务T原发站点原发站点遵守两阶段提交协议遵守两阶段提交协议平均故障间隔时间指在可以自我修复的系统中相继失败之间的期望时间通过可靠性函数来计算MTBF=0R(t)dtMTBF与系统失败的概
4、率有直接的关系平均修复时间是指修复一个系统所需要的期望时间，MTTR它与失败概率有关指数型失败和修复的概率的系统可用性A=MTBF/(MTBF+MTTR)可用性系统5个9（99.999%）常用来描述可用性系统但是可用性系统要求的成本比较高具体设计时要综合用户两方面的要求1.2 平均故障间隔时间和平均修复时间平均故障间隔时间和平均修复时间1 1 分布式数据库可靠性概念及其度量分布式数据库可靠性概念及其度量系统（System）是由一组组件构成的一种机制，这些组件通过响应来自某个环境的具有可识别行为模式的刺激而相互作用。component1component2component3环境系统刺激响应系统
5、规范说明（Specification）系统提供的对所有可能的刺激将产生的响应行为必须遵循的说明2.1 系统失败的原因系统失败的原因2 2 分布式数据库系统的故障原因和容错技术分布式数据库系统的故障原因和容错技术故障任何偏离规范说明的行为软故障和硬故障软故障包括间歇性（intermittent）和瞬变性（transient）故障，通过重启动来修复硬故障指永久性故障,错误设计等软件和硬件故障2.1 系统失败的原因系统失败的原因2 2 分布式数据库系统的故障原因和容错技术分布式数据库系统的故障原因和容错技术软故障 占90%以上并且该比例稳定67年，美空军指出计算机中电子故障80%是间歇性的67年，I
6、BM 指出 90%故障是间歇性的80年，研究指出软故障明显高于硬故障87年，Gray指出 大部分软件故障是瞬变性故障2.1 系统失败的原因系统失败的原因2 2 分布式数据库系统的故障原因和容错技术分布式数据库系统的故障原因和容错技术审查不同计算机系统中出错的统计数据IBM/XA 的OS 可靠性报告 57%是硬件,12%软件,14%操作,7%环境（斯坦福 线性加速器SLAC）Tandem计算机 18%硬件 25%软件 25%维护 17%操作,14%环境AT&T 5ESS数字交换机 32.3%硬件,44.3%软件,17.5%操作 软件故障通信或DB的原因是产生软件故障的主要原因.代码中的Bug,曾
7、有报告指出,1000条指令中,0.25-10个BUG2.1 系统失败的原因系统失败的原因2 2 分布式数据库系统的故障原因和容错技术分布式数据库系统的故障原因和容错技术永久性故障错误的设计不稳定或者临界的组件不稳定的外部环境操作者的过失系统失败永久性错误间歇性错误瞬变的错误系统失败的原因容错 设计一种使系统识别出可能会发生的错误的方法。在系统中建立一种机制，使错误在造成系统故障之前就会被检测出来，并能被清除或得到补偿。错误预防保证所实现的系统不包含任何错误错误回避：保证系统不会带入错误的技术（详细的设计方法学和质量控制）错误清除：清查那些在使用了错误回避技术路线后还残留在系统中的错误，并清除它
8、们（需要大量的测试和证实过程）2.2 基本容错方法和技术基本容错方法和技术2 2 分布式数据库系统的故障原因和容错技术分布式数据库系统的故障原因和容错技术故障检测潜伏的故障：故障发生一段时间后才被检测出来 错误潜伏期：从故障发生到被检测出来的时间平均检测时间(MTTD)：平均错误潜伏时间平均修复时间(MTTR)：修复一个失败的系统所需要的期望时间平均故障间隔时间(MTBF)：在可以自我修复的系统中相继的失败之间的期望时间,由经验或从可靠性函数计算2.2 基本容错方法和技术基本容错方法和技术2 2 分布式数据库系统的故障原因和容错技术分布式数据库系统的故障原因和容错技术 MTBF MTTDMTT
9、R在这段时间内，可能发生多起错误故障发生造成错误检测到错误修复故障发生造成错误时间 相继发生的事件2.2 基本容错方法和技术基本容错方法和技术2 2 分布式数据库系统的故障原因和容错技术分布式数据库系统的故障原因和容错技术冗余所有容错系统设计中都采用的基本原则是在系统的组件中提供冗余模块化系统的每个组件都设计为具有定义很好的输入/输出接口的模块模块化可以把故障隔离在单一的组件中系统实现故障-停止模块（fail-stop module)进程对（Process pairs)2.2 基本容错方法和技术基本容错方法和技术2 2 分布式数据库系统的故障原因和容错技术分布式数据库系统的故障原因和容错技术t
10、ime正常 停止 恢复 正常易失存储丢失稳定存储 ok故障-停止模块不断地对自身进行检测，当检测到一个故障时，就自动停止。优点是缩短了故障检测的潜伏期。2.2 基本容错方法和技术基本容错方法和技术2 2 分布式数据库系统的故障原因和容错技术分布式数据库系统的故障原因和容错技术进程对（Process pairs)通过软件模块的双工来实现容错。两个进程，一个是主进程，一个是备份，它们同时提供同样的服务，主进程与备份进程都是基于故障-停止模块实现。分类方式（根据主进程和备份进程之间的通信方式）锁定-步进方式自动检查点设置方式状态检查点设置方式Delta检查点设置方式持久进程对2.2 基本容错方法和技
11、术基本容错方法和技术2 2 分布式数据库系统的故障原因和容错技术分布式数据库系统的故障原因和容错技术事务故障系统故障介质故障通信故障3.1 分布式数据库系统故障分布式数据库系统故障3 3 分布式数据库的可靠性协议分布式数据库的可靠性协议站点故障站点故障局部恢复管理器(LRM)每个站点一个维护局部事务的原子性和持久性体系结构数据库存储在稳定存储器中存储和访问稳定数据库的单位是页面缓冲区中的数据库称作易失数据库LRM仅仅在易失数据库上执行事务操作对数据库的访问都要经由数据库缓冲区管理器Flush(冲洗)实现将数据库缓冲区页对稳定DB的强迫写3.2 局部可靠性协议局部可靠性协议3 3 分布式数据库的
12、可靠性协议分布式数据库的可靠性协议数据库缓冲区(易变数据库)局部恢复管理器数据库缓冲区管理器主存取出,冲洗读/写稳定DB读/写LRM与缓冲区管理器的接口3.2 局部可靠性协议局部可靠性协议3 3 分布式数据库的可靠性协议分布式数据库的可靠性协议恢复信息LogUndoRedo旧的稳定DB状态新的稳定DB状态Redo数据库Log新的稳定DB状态旧的稳定DB状态Undo数据库Log3.2 局部可靠性协议局部可靠性协议3 3 分布式数据库的可靠性协议分布式数据库的可靠性协议目的保证在DB上执行的事务的原子性和持久性。协议描述了原语的执行过程命令执行过程Begin-Transaction：登录Read：
13、LRM先在Trans的缓冲区中读，若不在，则向缓冲区管理器发Fetch命令，读出数据后，LRM将它交给调度程序Write：若在Buffer中得到，则在那更新，否则对Buffer Manager发Fetch命令，读出数据并修改，同时数据的前像和修改后的后像写入LogAbort：通过Log做UndoCommit：将事务结束记录入Log项3.2 局部可靠性协议局部可靠性协议3 3 分布式数据库的可靠性协议分布式数据库的可靠性协议目的维持在多个数据库上执行的事务的原子性和持久性原语Begin_Transactionread,write,Abort,commit命令执行与局部协议类似3.3 分布式可靠性
14、协议分布式可靠性协议3 3 分布式数据库的可靠性协议分布式数据库的可靠性协议可靠性协议组成 包括提交、终结、恢复协议提交和恢复协议详细说明提交命令和恢复命令是如何执行的终结协议是分布式系统特有的协议。在执行一个分布式事务时，若一个Site故障，希望其它Site也停止该事务。处理这种情况的技术就称为终止协议。3.3 分布式可靠性协议分布式可靠性协议3 3 分布式数据库的可靠性协议分布式数据库的可靠性协议终结协议与恢复协议的比较假若一个Site失效终结协议确定了未失效Site如何处理该失效事件恢复协议确定失效Site重启动后，进程（协调者，参与者）恢复它的状态的过程网络分割时终结协议采取必要的措施
15、来终结在不同网络区间执行的活动事务当网络重新连接后，恢复协议保证使各个冗余DB相互一致3.3 分布式可靠性协议分布式可靠性协议3 3 分布式数据库的可靠性协议分布式数据库的可靠性协议两阶段提交协议的要点允许参与者单方面撤销事务，直到做出肯定性的建议一旦参与者确定了提交或者撤销提议，它不能再更改当参与者处于就绪状态，它可根据协调者发出的消息的种类，转换为相应的提交或者撤销状态协调者依据全局提交规则作出全局终结决定在发生故障的情况下，协调者和参与者可能会进入互相等待的状态，一般采用定时器来解决这种问题3.4 两阶段提交协议的演变两阶段提交协议的演变3 3 分布式数据库的可靠性协议分布式数据库的可靠
16、性协议协调者参与者PREPAREPREPAREDCOMMITACK2PC-提交协 调 者参 与 者PREPARENOABORTACK2PC-夭折集中式2PC协调者 参与者IWCAIRCAcommit-申请 申请-prepare*no abort*prepared*commit commit ACK 申请-prepare prepared 申请-prepare no abort ACKF ACK*ACK*标记:输入消息 输出消息*=每一个3.4 两阶段提交协议的演变两阶段提交协议的演变3 3 分布式数据库的可靠性协议分布式数据库的可靠性协议当参与者进入“R”状态:它必定已获得所有资源它只能根据协
17、调者指令提交或夭折当所有参与者是在“R”时,协调者才能进入“C”状态,即,它一定最终能提交3.4 两阶段提交协议的演变两阶段提交协议的演变3 3 分布式数据库的可靠性协议分布式数据库的可靠性协议假定撤销2PC和假定提交2PC协议目的是改善2PC的性能假定撤销协议中，协调者不必等待参与者的ACK消息，减少了协调者与参与者之间传递消息的数量假定提交协议中，可以不将Prepare写入Log，减少了Log写入的次数3.4 两阶段提交协议的演变两阶段提交协议的演变3 3 分布式数据库的可靠性协议分布式数据库的可靠性协议事务阻断：某个Site上本来可以终结（提交或撤销）的子事务，由于DDBS故障，必须等待
18、到故障恢复（其占有的资源不释放）阻断协议：提交协议称为阻断协议是指发生某类故障时，使分布式事务可能处于阻断状态终结协议：允许事务在有故障情况下仍能正确结束3.5 事务阻断与终结协议事务阻断与终结协议3 3 分布式数据库的可靠性协议分布式数据库的可靠性协议判断2PC协议是终结协议的条件至少有一个Site已收到结果命令（该Site可以告知其它参与者关于该事务的结果，并由它们来终结该事务）没有一个参与者收到命令，并且只有协调者Site故障（此时，所有参与者站点都是可工作的，参与者可以选举一个新的协调者，然后继续）3.5 事务阻断与终结协议事务阻断与终结协议3 3 分布式数据库的可靠性协议分布式数据库
19、的可靠性协议终结协议在协调者和参与者的定时器超时时发挥作用超时处理技术协调者超时在等待状态超时，可以决定“全局撤销”在撤销状态超时，重发“G-abort”在提交状态超时，重发“G-commit”参与者超时（被阻断时出现）在初始状态超时，单方面Abort在Ready状态超时，被阻断，等待事务最终处理结果3.6 2PC协议的终结协议协议的终结协议3 3 分布式数据库的可靠性协议分布式数据库的可靠性协议协调者超时IWCAFcommit-申请申请-prepare*ack*-ack*-_t_abortanyabortanycommit_t_commit_t_abort*noabort*prepared*
20、commit*t=timeout参与者超时IRCA申请-prepareprepared等价于结束状态_t_ ping申请-preparenocommitackabortackcommitackabortack设计终结协议假定Pi是超时的参与者（询问Pj），其它Pj按如下响应Pj处于初始状态，于是单方面Abort，并回送“建议abort”给PiPj处于Ready状态，此时不能帮助Pi终结Pj处于Commit或Abort状态，此时向Pi发送“建议提交”或“建议Abort”3.6 2PC协议的终结协议协议的终结协议3 3 分布式数据库的可靠性协议分布式数据库的可靠性协议Pi超时，可能有的解释Pi收到
21、Pj的“建议撤销”回答，此时Pi夭折Pi收到Pj“建议撤销”回答，但是其它Pj处于Ready状态，此时Pi仍然AbortPi收到Pj处于Ready状态，此时没有一个参与者有足够的信息恰当地终结事务Pi收到其他所有的Pj”全局提交”或”全局夭折”消息，Pi可以根据消息终结Pi收到某些Pj的“全局提交”，而另一些Pj处于Ready状态，Pi可以提交3.6 2PC协议的终结协议协议的终结协议3 3 分布式数据库的可靠性协议分布式数据库的可靠性协议协调者站点失效协调者在初始状态失效发生在协调者初始化提交过程之前因此，它将在恢复时启动提交过程协调者在等待状态失效这时协调者已经发送了“准备”命令恢复时，协
22、调者将从头开始启动提交过程，再次发送“准备”消息协调者在提交状态或撤销状态失效这时，协调者已经把它的决定通知了参与者，并终结了事务在恢复时，如果它已经收到了所有的确认消息，就不需要做任何事情否则，就要启动终结协议3.7 2PC协议的恢复协议协议的恢复协议3 3 分布式数据库的可靠性协议分布式数据库的可靠性协议参与者站点失效一个参与者在初始状态失效在恢复时，该参与者应该单方面撤销事务一个参与者在就绪状态失效这时协调者已经收到失效站点在失效前发送的肯定决定恢复时，失效站点的参与者认为是在就绪状态发生了超时，于是启动终结协议来处理该事务一个参与者在提交状态或撤销状态失效这些状态表示了终结条件，所以在
23、恢复时，参与者不需要采取任何专门的措施附加情形（略）3.7 2PC协议的恢复协议协议的恢复协议3 3 分布式数据库的可靠性协议分布式数据库的可靠性协议提交协议是非阻断的充要条件是,在其状态转换图中不存在:没有状态是即与提交又与撤销状态“相邻”不存在不可提交状态是与提交状态“相邻”相邻从一个状态直接转换到另一个状态3.8 三阶段提交协议三阶段提交协议3 3 分布式数据库的可靠性协议分布式数据库的可靠性协议2PC中的状态 C(提交)状态是可提交状态,其它为不可提交状态Ready 状态是不可提交状态Wait状态是不可提交状态它们都侵犯了非阻断协议的充要条件,从而考虑改变2PC,使其满足非阻断协议条件
24、在Wait 和 Commit 之间,或者在Ready和Commit之间加入另一种状态作为缓冲状态,从而有了3PC协议3.8 三阶段提交协议三阶段提交协议3 3 分布式数据库的可靠性协议分布式数据库的可靠性协议IWACcommitpreparevote-abortglobal-abortvote-commitprepare-to-commitIRACpreparevote-commitglobal-abortACKprepare-to-commitready-to-commitpreparevote-abort3PC中事务的状态转换图PCPCready-to-commitglobal-commi
25、t global-commitACK(a)协调者(b)参与者协调者参与者 PREPAREPREPAREDCOMMITDONE PRECOMMITACK协调者参与者 PREPARENOABORTDONE协调者参与者开始-3PC 记录写Log (参与者列表)commit记录写Log (状态C)prepared记录写Log (状态 W)committed 记录写Log (状态 C)PREPAREPREPAREDCOMMIT PRECOMMITACK协调者参与者初始写begin_commit到日志等待有要求撤消的？写Prepare-to-commit到日志准备提交写end_of_trans.到日志初始
26、准备提交？写ready到日志就绪消息类型？写abort到日志写prepare-to-commit到日志准备提交撤消撤消写abort到日志写abort到日志准备撤消提交全局撤消准备提交ACKACK nono abortPrepare-to-commit写commit到日志提交提交 在 中事务执行的过程 写commit到日志撤消提交准备提交3PC协调者在Wait状态超时：与2PC中协调者在Wait超时相同,协调者单方面Abort在PC状态超时：此时协调者不知道未响应的参与者是否到达PC.但是知道每个参与者至少在Ready状态,因此协调者可以将所有参与者移入PC状态在Commit/Abort状态超时
27、 协调者不知参与者是否已执行命令,但是对Commit而言,知道参与者至少在PC状态。因此，协调者不需要做专门的处理3.9 三阶段提交协议的超时处理三阶段提交协议的超时处理3 3 分布式数据库的可靠性协议分布式数据库的可靠性协议参与者超时在Initial状态超时：与2PC中的情况相同在Ready状态超时：参与者准备Commit.由于与协调者的通信丢失,终结协议将选举一个新的协调者，新协调者根据下面所述终结协议终结事务在PC状态超时：参与者已收到“Prepare-to-commit”,正在等待来自协调者的“全局提交”消息,处理同第二条。3.9 三阶段提交协议的超时处理三阶段提交协议的超时处理3 3
28、 分布式数据库的可靠性协议分布式数据库的可靠性协议协调者参与者 PREPAREPREPAREDCOMMIT PRECOMMITACK1.超时:Abort3.超时:忽略1.超时:abort2.超时:终结协议3.超时:终结协议2.超时:把参与者移入PC竞选新的协调者使用竞选协议新协调者送出 REQUEST状态给参与者使用终结规则做出决定与参与者通信3.10 三阶段提交协议的终结协议三阶段提交协议的终结协议3 3 分布式数据库的可靠性协议分布式数据库的可靠性协议竞选协议进程全序协调者=0,参与者 1,n任何时候,选择“最小的”工作进程为协调者3.10 三阶段提交协议的终结协议三阶段提交协议的终结协议
29、3 3 分布式数据库的可靠性协议分布式数据库的可靠性协议终结规则新协调者在Wait状态：将全局Abort.此时参与者可以在任何状态,若参与者是在PC状态,即它是期望有“G-Commit”,但是得到了“G-Abort”.3PC中缺少从PC到Abort的转换,这对终结协议很有用.新协调者在PC状态：此时没有参与者是在Abort状态,协调者可以全局提交,发送“G-Commit”命令.新协调者在Abort状态：收到第一个消息后，所有参与者进入Abort状态3.10 三阶段提交协议的终结协议三阶段提交协议的终结协议3 3 分布式数据库的可靠性协议分布式数据库的可靠性协议3PC与2PC恢复协议的差别很小协
30、调者在Wait状态故障,按照终结协议，参与者已终结事务,因此,协调者在恢复时必须查询以决定事务的命运协调者在PC状态故障,终结协议已使工作的参与者终结,因此,协调者需询问一个参与者在PC状态故障,必须询问以确定其它参与者如何终结事务3.11 三阶段提交协议的恢复协议三阶段提交协议的恢复协议3 3 分布式数据库的可靠性协议分布式数据库的可靠性协议网络分割是由通信线路故障引起的简单分割，仅仅是网络分裂成两部分多重分割，更复杂网络分割非阻断协议的存在性即在发生网络分割时,是否存在允许独立恢复的协议独立恢复是指站点重启动时,无需远程访问若存在处理分割的非阻断协议,那么,该协议可使某个分割中的站点到达终
31、结决定,而且这个决定与另一分割中的决定一致一般结论独立恢复协议只存在于单站点故障的情形若发生网络分割的时候,丢了报文的话,则不存在任何非阻断的协议能从网络分割故障中恢复4.1 网络分割概述网络分割概述4 4 网络分割与提交协议网络分割与提交协议非冗余数据库任何需要访问存储在另一网络区域里的数据项的新事务都被阻断,等待网络修复位于同一区域里的数据项的并发访问由并发控制算法处理网络分割时由提交协议处理冗余数据库分割时,副本可能位于不同的区域由复制协议处理4.1 网络分割概述网络分割概述4 4 网络分割与提交协议网络分割与提交协议网络分割处理策略一致性与可用性的选择非冗余数据库处理网络分割的终结协议
32、集中式协议，基于集中式并发控制算法(主站点法和主副本法)基于表决的协议冗余数据库处理网络分割的终结协议复制控制协议4.1 网络分割概述网络分割概述4 4 网络分割与提交协议网络分割与提交协议多数法和基于法定人数法在事务中止或提交前,大多数站点必须一致同意中止或提交基于法定人数的规则每个站点i有选票数Vi,Vi是正整数V=Vi事务在提交前，它必须获得提交法定票数Vc事务在Abort前，它必须获得Abort法定票数VaVa+VcV,当0 Va,Vc Vni=14.2 基于表决的协议基于表决的协议4 4 网络分割与提交协议网络分割与提交协议网络分割时,在每个分割部分选择一个新的协调者3PC中加入PA
33、状态,从而不允许从Wait/Ready到Abort 状态的转换原因有多个协调者阻止事务终结,不允许多个协调者得出不同的结论,因此希望协调者获得撤销的决定如果新协调者故障,它不知道是否达到提交或撤销的法定票数,这样参与者必须明确做出提交或撤销的决定Ready(或Wait)都不满足该需求,预示引入另一个状态Pre-Abort,该状态在Ready和Abort之间4.2 基于表决的协议基于表决的协议4 4 网络分割与提交协议网络分割与提交协议IWACcommitpreparevote-abortglobal-abortvote-commitprepare-to-commitIRACpreparevot
34、e-commitglobal-abortACKprepare-to-commitready-to-commitpreparevote-abort基于法定人数3PC中事务的状态转换图PCPCready-to-commitglobal-commit global-commitACK(a)协调者(b)参与者PAready-to-abortglobal-abortPAready-to-abortglobal-abort基于法定人数的3PC集中式协议选择一个新的协调者协调者收集状态信息,并按如下规则执行1)若至少一个站点已Commit(Abort),则协调者对其它站点发送Commit(Abort)命令2
35、)若处于PC状态站点的票数=Vc,则发送Commit3)若PA状态站点的票数=Va,则发送Abort4)若PC状态站点的票数+Ready状态站点的票数=Vc,则发送PC命令给不确定站点,等待2)状态出现5)若PA状态站点的票数+Ready状态站点的票数=Va,则发送PA命令给不确定站点,等待3)状态出现6)否则,等待故障修复4.2 基于表决的协议基于表决的协议4 4 网络分割与提交协议网络分割与提交协议数据复制的目的高吞吐量较好的响应时间高可用性复制作为可选择的提交协议数据在多站点独立更新,使用“惰性复制协议”减少数据不一致问题.4.3 复制控制协议复制控制协议4 4 网络分割与提交协议网络分
36、割与提交协议基本方法：每个副本看作一个独立的数据项X1X2X3Lockmgr X3Lockmgr X2Lockmgr X1TxiTxjTxk对象 X 有副本 X1,X2,X34.3 复制控制协议复制控制协议4 4 网络分割与提交协议网络分割与提交协议Read(X):获取 X1 共享锁获取 X2 共享锁获取 X3 共享锁分别读 X1,X2,X3事务结束时,释放 X1,X2,X3 锁X1lockmgrX3lockmgrX2lockmgrreadWrite(X):获取 X1 互斥锁获取 X2 互斥锁获取 X3 互斥锁写新值到 X1,X2,X3事务结束时,释放 X1,X2,X3 锁X1X3X2lock
37、locklockwritewritewrite读锁和访问只对一个副本写锁全部,并且更新全部副本读可用性高写可用性低，只要有一个副本不可获得，更新事务就不能终结ROWA方法X1X2X3读者加锁写者发现冲突!4.3 复制控制协议复制控制协议4 4 网络分割与提交协议网络分割与提交协议ROWA的改进(ROWA-A)ROWA-A “读一个写所有可获得协议”基本思想是写命令在所有可获得的副本上执行，然后事务终结，当时不可获得的副本将在它们重新可获得时被捕获更新事务T的协调者向所有包含x副本的站点发送WT(x),并等待执行(或拒绝)的确认.当不可获得站点恢复时,也将更新自己的数据库.但如果站点在T开始之前
38、就不可获得,它们就可能没有注意到T的存在,以及T对x的更新.问题协调者认为不可获得的参与者仍然工作,并且更新了x,但是其确认没有到达协调者站点在事务启动时不可获得,随后恢复并开始执行事务4.3 复制控制协议复制控制协议4 4 网络分割与提交协议网络分割与提交协议于是,协调者在提交前要进行有效性验证检查所有不可获得的站点是否仍然不可获得,如果协调者收到一个响应,它就撤销T.若都是不可获得,则检查在WT(x)执行是可获得的站点仍然可获得,是则提交事务ROWA-A比ROWA协议能更好地适应失效,包括网络分割.ROWA的改进(ROWA-A)4.3 复制控制协议复制控制协议4 4 网络分割与提交协议网络
39、分割与提交协议基于法定人数的复制控制Gifford算法 读法定人数Vr,写法定人数Vw规则1：Vr+Vw V，可避免读-写冲突规则2：Vw V/2，避免写-写冲突该算法确保了在两个不同网络区域上启动且访问同一数据的事务不会同时终结4.3 复制控制协议复制控制协议4 4 网络分割与提交协议网络分割与提交协议惰性复制协议思想只在一个或多个副本上执行更新,以后再将更新传播到所有副本上特点所有权参数：定义更新副本的权限,副本可以更新就称为主Copy(主站点),否则称辅Copy(辅站点)传播参数：定义何时把对一个副本的更新传播到包含该对象的其它副本刷新参数：定义了刷新事务的调度策略配置参数：描述站点和网
40、络的特点4.3 复制控制协议复制控制协议4 4 网络分割与提交协议网络分割与提交协议两类所有副本都可更新,存在副本的组所有权,常用延迟立即方式更新只有一个被更新的主站点(惰性主站点法)几种刷新方案:按需刷新,每次提交执行查询时,执行所有收到的刷新事务来刷新被查询读取的辅Copy,造成查询响应延迟成组刷新,根据应用刷新要求,成组执行刷新事务定期刷新,在固定时间间隔内触发刷新惰性复制协议4.3 复制控制协议复制控制协议4 4 网络分割与提交协议网络分割与提交协议网络的一致视图可靠性算法是假定:全部能工作的站点对网络的所有站点(包括其本身)的状态(即工作或故障)具有一致的视图决定网络的一致视图监视网
41、络的状态，当站点状态发生转换时,能及时发现新的信息一致地传播给全部站点5.1 决定网络的状态决定网络的状态5 5 不一致性检测和解决方法不一致性检测和解决方法假设建于广义的网络范围内每个站点有一状态表,每个站点一个表项,记录其工作/不工作，程序可查询状态表得到状态信息任何程序能够在任一站点设置一个“看守”,当该站点变化状态时它就收到一个中断分割时,状态表和一致视图的意义站点只认为那些能和它通信的站点是工作的一致视图的数目与分离的站点组数目一样多5.1 决定网络的状态决定网络的状态5 5 不一致性检测和解决方法不一致性检测和解决方法监视网络的状态决定一站点是否工作时向它请求一个报文,然后等待到超
42、时控制站点 (请求站点)受控站点在一广义监视算法中，受控站点周期性地发送I-am-up（我在工作）报文5.1 决定网络的状态决定网络的状态5 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的网络视图广播新的状态监视功能每次检测出一个状态变化,就激活此广播功能此功能的目的是广播新的状态表，使同一组的全部
43、站点具有相同的状态表此功能可由若干站点并行激活,需要某种机构来控制冲突状态表的每个新的版本附加一全局唯一的时间戳在I-am-up报文中包含当前状态表的版本号启动新状态表广播的站点首先执行一次同步以获得一时间戳，然后发送状态表给已回答的所有站点5.1 决定网络的状态决定网络的状态5 5 不一致性检测和解决方法不一致性检测和解决方法需求处理故障的策略有可能牺牲正确性来提高可用性，因此接受了不一致性的风险在这种情况下，监测这些不一致性，并尽可能地加以解决是很有用的概念需要首先发现哪些数据部分已经不一致（不一致性检测）然后根据发生的情况，给这些部分赋予一个最合理的值（不一致性的解法）5.2 不一致性的
44、检测和解决方法概念不一致性的检测和解决方法概念5 5 不一致性检测和解决方法不一致性检测和解决方法提出问题假设网络分割期间,在两个或多个站点组中已执行了若干事务,可能对同一数据片断的不同副本进行了独立更新检测方法一种比较自然的方法比较各副本的内容,检查其是否相同，但是这种方法不仅效率低，一般也是不正确的。5.3 不一致性的检测不一致性的检测5 5 不一致性检测和解决方法不一致性检测和解决方法检测方法采用版本号允许对数据项操作的站点的副本是主副本,其它是孤立或隔离的副本正常工作期间,全部副本都是主副本,并且互相一致,每份副本维持一个原版号和一个当前版本号网络分割时,每个孤立副本的原版本号被置为当
45、前版本号值,并且,直到分割修复为止,此原版号不会改变5.3 不一致性的检测不一致性的检测5 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)修
46、复后,可以看出x3未曾修改5.3 不一致性的检测不一致性的检测5 5 不一致性检测和解决方法不一致性检测和解决方法假设分割时,只更新x3,版本号为V1=(0,2)V2=(0,2)V3=(2,3)此时若没有其它孤立副本,则可以用x3的更新施加到主副本,但若还有x4，V4=(2,3)，则即使x3与x4版本号相同也不能说其是一致的若主副本与孤立副本都更新过,版本号为V1=(0,3)V2=(0,3)V3=(2,3)那么，此孤立副本的原版本号和当前版本号是不同的，而且此孤立副本的原版本号也与主副本的当前版本号不同5.3 不一致性的检测不一致性的检测5 5 不一致性检测和解决方法不一致性检测和解决方法网络
47、分割已修复和不一致性已检测出来后，必须给同一数据项的全部拷贝赋予一共同的值，不一致性解法的问题是如何决定这个值不一致的解决办法与应用相关航空订票系统暂停订票,收集旅客请求,网络修复后再集中订票赋予各订票点的订票数小于总数5.4 不一致性的解决方法不一致性的解决方法5 5 不一致性检测和解决方法不一致性检测和解决方法在分布式数据库中，冷启动是比较罕见的一般来说，当网络中的一个站点丢失了运行记录信息之后，就要求冷启动分布式数据库冷启动中,一个站点要建立一早期状态,那么所有其它站点也必须建立起与该站点一致的早期状态,这意味着此恢复过程本质上是全局的,要影响到数据库的全部站点,虽然引起冷启动的故障一般
48、讲是本地的.以前的一致性状态是由检查点来标志的5.5 检查点和冷启动检查点和冷启动5 5 不一致性检测和解决方法不一致性检测和解决方法一致的全局状态C的两个特征对于每个事务T,C包含了T在任何站点的全部事务所执行的更新,或者它不包含它们中的任何一个。如果一事务T被包含在C中,则按串行化次序,在T前面的全部冲突事务也包含在C中重构全局一致状态的最简单办法是使用本地转储本地的运行纪录全局的检查点5.5 检查点和冷启动检查点和冷启动5 5 不一致性检测和解决方法不一致性检测和解决方法如果有全局检查点,则重构就相对容易.首先在故障站点处决定认为是安全的最近的一个本地检查点,这就确定了必须重构的较早的全
49、局状态 然后请求所有其它站点重新建立相对应的本地检查点的本地状态存在的问题只有一个站点把一“写检查点”报文广播给所有其它站点是不够的,因为可能出现如下页图所述的情况5.5 检查点和冷启动检查点和冷启动5 5 不一致性检测和解决方法不一致性检测和解决方法站点1站点2站点3C1时间T2C2C3T3RC其中：T2和T3是事务T的子事务，T3是两阶段提交的协调者。C1、C2和C3 是本地检查点(从站点1开始)写检查点报文 两阶段提交的报文(R=READY,C=COMMIT)全局检查点的同步问题避免上述问题的简单办法是,要求在每个站点记录其本地检查点之前,使所有站点变成不活跃的.全部站点必须同时停留在不
50、活跃状态,需要进行协调,使用与2PC类似的协议由一协调者把“预备检查点”广播给所有站点每个站点就终结了的事务的执行然后回答Ready于是该协调者再广播“执行检查点”5.5 检查点和冷启动检查点和冷启动5 5 不一致性检测和解决方法不一致性检测和解决方法更高效的方法有：松散同步检查点：由一个协调者来要求所有站点记录一全局检查点,但是它们可在一较大的时间间隔内自由地执行之,保证同一事务的全部子事务都包含在相应于同一全局检查点的本地检查点的责任交事务管理器承担为了完全避免建立全局检查点，让恢复过程在冷启动时承担重构一致的全局状态的任务。每个站点独立于其它站点记录其本地检查点,所以建立一致全局状态由冷