《DDB的可靠性》PPT课件.ppt

1、1,第七章 DDB的可靠性,2,概念,系统（System） 是由一组组件构成的一种机制，这些构成组件通过响应来自某个环境的具有可识别行为模式的刺激而相互作用。,component1,component2,component3,环境,系统,刺激,响应,系统规范说明（Specification） 系统提供的对所有可能的刺激将产生的响应行为必须遵循的说明,3,概念-续,故障 任何偏离规范说明的行为 软故障与硬故障 软故障 间歇性（intermittent）和瞬变性（transient）故障 硬故障 指永久性故障, 错误设计等,Fault,Error,Failure,原因,结果,导致系统失败的事件链,

2、4,概念-续,软故障 软故障 占90%以上并且该比例稳定 67年 美空军指出计算机中电子故障80%是间歇性的 67年 IBM 指出 90%故障是间歇性的 80年 研究指出软故障明显高于硬故障 87年 Gray指出 大部分软件故障是瞬时性故障 其它不同计算机系统中出现的统计数据:,5,DDS的容错-续,IBM/XA 的OS 可靠性报告 57%是硬件, 12% 软件, 14%操作, 7% 环境（斯坦福 线性加速器SLAC） Tandem计算机 18%硬件 25% 软件 25%维护 17%操作, 14%环境 AT&T 5ESS数字交换机 32.3%硬件, 44.3%软件, 17.5%操作 软件故障难

3、以讨论, Tandem指出: 通信或DB的原因是产生软件故障的主要原因. 软件故障的主要原因 代码中的Bug, 曾有报告指出, 1000条指令中, 0.25-10个BUG,6,永久性 故障,错误的 设计,不稳定 或者 临界的 组件,不稳定的 外部环境,操作者 的过失,系 统 失 败,永久性 错误,间歇性 错误,瞬变的 错误,系统失败的原因,7,概念-续,可靠性DDBMS 指即使当底层系统不可靠时，该DDBMS仍然能继续处理用户需求。也就是说，即使是分布式计算环境的组成出故障，该DDBMS仍然能执行用户需求，而不破坏数据库的一致性。 提交协议与恢复协议 可靠性与事务的原子性和持久性相关，涉及的协

4、议是提交与恢复,8,可靠性与可用性,可靠性 对系统行为遵从某种权威性规格要求的一种度量。指在一给定时间间隔内不产生任何失败的概率。可靠性通常用于描述那些不能修复的系统。 可用性 对系统行为遵从某种权威性规格要求的一种度量。指在给定的时间点系统可以运行的概率。通常用于描述哪些可以修复的系统。,9,可靠性与可用性-续,DB的行为所要求的规格说明 与应用有关的 事务满足一般的系统规格要求, 其中包括一致性约束(事务与应用之间的语义关系) 与应用无关的 事务维持其ACID性质(事务本身应具有的性质),10,可靠性与可用性-续,正确性 DB正确运行, 符合某种规格化要求 可用性 当需要访问DB时, 它是

5、可用的 二者有时存在矛盾,11,可靠性与可用性-续,例: Site1 Site2 x1 x2 Lock x1 Lock x2 2PC,Ready,故障出现,Site1也Ready 故Commit,Site 2 等待,此时Site 2有两种可能: a 以正确行为标准 则等待, 并Lock 2, 直到故障恢复, 但牺牲了可用性 b 引入不一致, 尽量提高可用性, Release x2, 其它事务可以执行,Site 1 正常结束,12,分布式系统容错,容错 设计一种使系统识别出可能会发生的错误方法。在系统中建立一种机制，使错误在造成系统故障之前就会被检测出来，并能被清除或得到补偿。,13,基本容错方

6、法和技术,错误预防 保证所实现的系统不包含任何错误 错误回避 保证系统不会带入错误的技术（详细的设计方法学和质量控制） 错误清除 清查那些在使用了错误回避技术路线后还残留在系统中的错误，并清除它们（大量的测试和证实过程） 故障检测,14,基本容错方法和技术-续,潜伏的（Latent）故障 故障发生一段时间后才被检测出来 错误潜伏期 从故障发生到被检测出来的时间 平均检测时间(MTTD) 平均错误潜伏时间 平均修复时间(MTTR) 修复一个失败的系统所需要的期望时间 平均故障间隔时间(MTBF) 在可以自我修复的系统中相继的失败之间的期望时间, 由经验或从可靠性函数计算,15,MTBF,MTTD

7、,MTTR,在这段时间内， 可能发生多起错误,故障 发生,造成 错误,检测到 错误,修复,故障 发生,造成 错误,时间,相继发生的事件,16,基本容错方法和技术-续,冗余 所有容错系统设计中都采用的基本原则是在系统的组件中提供冗余 模块化 系统的每个组件都设计为具有定义很好的输入/输出接口的模块 系统实现 故障-停止模块（fail-stop module) 进程对（Process pairs),17,time 正常 停止 恢复 正常,易失存储丢失,稳定存储 ok,故障-停止模块 不断地对自身进行检测，当检测到一个故障时，就自动停止。优点是缩短了故障检测的潜伏期。,基本容错方法和技术-续,18,

8、基本容错方法和技术-续,进程对（Process pairs) 通过软件模块的双工来实现容错。两个进程，一个是主进程，一个是备份，它们同时提供同样的服务，主进程与备份进程都是基于故障-停止模块实现。 锁定-步进方式 自动检查点设置方式 状态检查点设置方式 Delta检查点设置方式 持久进程对,19,基本容错方法和技术-续,面向对话的通信（Session-Oriented Communication) 授权OS中的消息服务器（而不是应用程序）去检测和控制那些丢失的或重复的消息,20,分布式DBMS的故障,事务故障 站点故障 介质故障 通信故障,21,局部可靠性协议,局部恢复管理器 (LRM) 每个

9、Site一个 维护局部事务的原子性和持久性 体系结构 数据库存储在稳定存储器中 存储和访问稳定数据库的单位是页 缓冲区中的数据库称作易失数据库 LRM仅仅在易失数据库上执行事务操作 对数据库的访问都要经由数据库缓冲区管理器 Flush(冲洗) 实现将数据库缓冲区页对稳定DB的强迫写,22,数据库 缓冲区 (易变数据库),局部恢复 管理器,数据库缓冲区 管理器,主存,取出, 冲洗,读/写,稳定 DB,读/写,LRM与缓冲区管理器的接口,23,局部可靠性协议-续,恢复信息 Log Undo Redo 原位更新 影子（shadowing）更新,24,局部可靠性协议-续,目的 保证在DB上执行的事务的

10、原子性和持久性。协议描述了原语的执行过程 命令执行过程 Begin-Trans 登录 Read LRM先在Trans的缓冲区中读，若不在，则向缓冲区管理器发Fetch命令，读出数据后，LRM将它交给调度程序 Write 若在Buffer中得到，则在那更新，否则对Buffer Manager发Fetch命令，读出数据并修改，同时数据的前像和修改后的后像写入Log Abort 通过Log做Undo Commit 将事务结束记录入Log项,25,分布式可靠性协议,目的：维持在多个数据库上执行的事务的原子性和持久性 原语 Begin_Trans read, write, Abort, commit,

11、recover 命令执行与局部协议类似 Read/write 使用ROWA规则,26,分布式可靠性协议-续,可靠性协议组成 包括提交、终结、恢复协议 终结协议 分布式系统特有的协议。若一个Site故障，希望其它Site也停止该事务。,27,分布式可靠性协议-续,非阻断协议 允许Trans在非失效的Site终结，而不必等待失效Site的恢复，从而改进Trans的响应时间 独立的恢复协议 如何在发生失效时终结Trans, 而不必求助于其它Site,可以减少恢复时需要交换的信息,28,分布式可靠性协议-续,终结协议与恢复协议的比较 假若一个Site失效 终结协议确定了为失效Site如何处理该失效事件

12、 恢复协议确定失效Site重启动后，进程（协调者，参与者）恢复它的状态的过程,29,分布式可靠性协议-续,网络分割时 终结协议采取必要的措施来终结在不同网络区间执行的活动事务 当网络重新连接后，恢复协议保证使各个冗余DB相互一致,30,2PC协议,简单的能保证分布式事务原子提交的协议,31,协调者,参与者,2PC-提交,32,协 调 者,参 与 者,2PC-夭折,33,集中式2PC,协调者 参与者,I,W,C,A,I,R,C,A,commit-申请 申请-prepare*,no abort*,prepared* commit,commit ACK,申请-prepare prepared,申请-

13、prepare no,abort ACK,F,ACK*,ACK*,标记: 输入消息 输出消息 * = 每一个,34,当参与者进入“R”状态: 它必定已获得所有资源 它只能根据协调者指令提交或夭折 当所有参与者是在“R”时, 协调者才能进入“C” 状态, 即, 它一定最终能提交,35,2PC的演变,2PC讨论 参与者可以单方面撤销Trans，直至它作出肯定性的提议（单方面中止的时间是在其作出肯定提议之前） 一旦参与者确定了提交或撤销协议，它就不能更改它的提议。 参与者处于Ready状态，可以根据协调者发来的消息种类，直接转为Abort/Commit 全局提交必须是所有参与者共同作出的全局终结决定

14、 通信故障出现时，协调者和参与者可能会出现互等状态,36,2PC的演变-续,假撤销2PC和假提交2PC协议 改善2PC的性能 假撤销协议中，协调者不必等待参与者的ACK消息，减少了协调者与参与者之间传递消息的数量 假提交协议中，可以不将Prepare写入Log，减少了Log写入的次数,37,Trans阻断与终结协议,Trans阻断 某个Site上本来可以终结（提交或撤销）的子事务，由于DDBS故障，必须等待到故障恢复（其占有的资源不释放） 阻断协议 发生某类故障时，使分布式Trans处于阻断状态 终结协议 允许事务在有故障情况下仍能正确结束,38,Trans阻断与终结协议-续,2PC协议是终结

15、协议的条件 至少有一个Site已收到结果命令（该Site可以告知其它参与者） 没有一个参与者收到命令，并且只有协调者Site故障（可以新造协调者）,39,2PC 阻断,例: CoordP2 R P1P3 RR P4R,40,2PC的终结协议,使用超时技术 协调者超时 在等待状态超时，可以决定“全局撤销” 在撤销/提交状态超时，重发“G-abort”/“G-commit” 参与者超时（被阻断时出现） 在初始状态超时，单方面Abort 在Ready状态超时，被阻断，等待 设计终结协议,41,协调者超时,I,W,C,A,F,commit-申请 申请-prepare*,ack* -,ack* -,no

16、 abort*,prepared* commit*,t=timeout,42,参与者超时,I,R,C,A,申请-prepare prepared,等价于结束状态,_t_ ping,申请-prepare no,commit ack,abort ack,commit ack,abort ack,43,2PC的终结协议-续,设计 假定Pi超时（询问Pj），其它Pj按如下响应 Pj处于初始状态，于是单方面Abort，并回送“建议abort”给Pi Pj处于Ready状态，此时不能帮助Pi终结 Pj处于Commit或Abort状态，此时向Pi发送“建议提交”或“建议Abort”,44,2PC的终结协议-

17、续,Pi超时，可能有的解释 Pi收到Pj的“建议撤销”回答，此时Pi夭折 Pi受到Pj“建议撤销”回答，但是其它Pj处于Ready状态，此时Pi仍然Abort Pi收到Pj处于Ready状态，此时没有一个参与者有足够的信息恰当地终结事务 Pi收到Pj”全局提交”或”全局夭折”消息，Pi可以根据消息终结 Pi收到某些Pj的“全局提交”，而另一些Pj处于Ready状态，Pi可以提交,45,假撤销2PC协议,集中式 2PC的优化 减少 log 记录 保留撤销消息 假提交类似,46,假撤销2PC协议-续,原则 恢复时, 如果在协调者的Log记录中没有事务T的记录, 那么协调者假定事务T夭折 夭折 协调

18、者不需要在Log中写2PC开始Prepare 协调者不需要在Log中写complete 参与者不必延迟夭折, 也不需要发送ACK,47,协调者,参与者,无 2PC开始记录,因为无信息,协调者 响应Abort,假夭折,prepared 记录写Log,参与者超时,重新发送,故障!,恢复,48,协调者,参与者,无2PC开始记录,假提交,prepared 记录写Log,参与者超时重发,故障!,恢复,Commit项 记录入Log,commit 记录写Log,49,2PC的恢复协议,参与者在Ready状态的恢复（1a） 此时P重启时通过识别Log中有Ready记录，没有Commit/Abort记录判定其在

19、Ready状态，重启时询问协调者或其它Site。 协调者已发出Prepare命令 此时恢复程序可识别出Log中有Prepare记录，但没有“G-commit”/“G-abort”记录，重发命令 协调者已发出Global命令 恢复时识别出Log中“G-commit”/“G-abort”记录，重发命令,50,2PC中远程Site恢复问题,但P回答了Ready之后，还没有收到有关命令之前故障，需要远程Site之间交换信息，获取信息的方法有： 向协调者询问 若此时C也故障，则得不到回答，P被阻断 重定向询问 向其它P询问，此时只要有一个P收到命令，则该P也可以获得命令（要求有关结束事务的信息也必须在P

20、站点保留) 脱机方式 给每个Site分配一组脱机站点S(i), 当i故障时，所有有关i的信息都送到S(i)保留,51,集中式2PC（再讨论）,协调者 参与者,I,W,C,A,I,R,C,A,commit-申请 申请-prepare*,no abort*,prepared* commit,commit ACK,申请-prepare prepared,申请-prepare no,abort ACK,F,ACK*,ACK*,标记: 输入消息 输出消息 * = 每一个,52,2PC 阻断,例: 协调者P2 R P1P3 RR P4R,53,非阻断协议,提交协议是非阻断的充要条件是, 在其状态转换图中不

21、存在: 没有状态是即与提交又与夭折状态“相邻” 不存在不可提交状态是与提交状态“相邻” 相邻 从一个状态直接转换到另一个状态,54,非阻断协议-续,2PC中, C(提交)状态是可提交状态, 其它为不可提交状态 Ready 状态是不可提交状态 Wait状态是不可提交状态 它们都侵犯了非阻断协议的充要条件, 从而考虑改变2PC, 使其满足非阻断协议条件 在Wait 和 Commit 之间, 或者在Ready和Commit之间加入另一种状态作为缓冲状态, 从而有了3PC协议,55,I,W,A,C,commit prepare,vote-abort global-abort,vote-commit p

22、repare-to-commit,I,R,A,C,prepare vote-commit,global-abort ACK,prepare-to-commit ready-to-commit,prepare vote-abort,3PC中事务的状态转换图,PC,PC,ready-to-commit global-commit,global-commit ACK,(a) 协调者,(b) 参与者,56,协调者,参与者,57,协调者,58,协调者,参与者,开始-3PC 记录写Log (参与者列表),commit记录写Log (状态C),prepared记录写Log (状态 W),committed

23、记录写Log (状态 C),59,3PC协议中的超时处理,协调者 Wait状态超时 与2PC中协调者在Wait超是相同, 协调者单方面Abort PC状态超时 此时协调者不知道没有相应的P是否到达PC. 但是知道每个P至少在Ready状态, 因此协调者可以将所有P移入PC状态 Commit/Abort状态超时 协调者不知P是否已执行命令,但是对Commit而言, 知道P至少在PC状态,60,3PC协议中的超时处理-续,参与者超时 Initial状态超时 与2PC中的情况相同 Ready状态超时 知道P准备Commit. 由于与协调者的通信丢失, 终结协议将选举一个新的协调者 PC状态超时 P已

24、收到“Prepare-to-commit”, 正在等待来自协调者的全面提交, 处理同上,61,协调者,参与者,1. 超时: Abort,2. 超时: 忽略,1. 超时t: abort,2. 超时:终结协议,3.超时:终结协议,62,终结协议,仅仅工作的进程参与终结协议. 恢复进程一直要等待到做出决定, 然后获得该决定,63,协调者,参与者,申请-PREPARE,可以夭折 (A),不确定 (U),预提交 (PC),提交 (C),64,3PC协议,例: 协调者P2 W P1P3 W P4W,65,3PC 原理,如果每个工作的站点都处于“不确定”状态, 没有站点(无论是工作的还是失败的)能够提交 注

25、: 假定网络可靠,66,进程分类,工作的 失败的 恢复,67,终结协议,竞选新的协调者 使用竞选协议 新协调者送出 REQUEST状态 给参与者 使用终结规则做出决定 与参与者通信,68,协调者,69,协调者,70,协调者,71,协调者,参与者,预提交,不提交,72,终结协议,例: 协调者P1 W P2 W P3W,73,终结协议,例: 协调者P1 W P2 W P3PC,74,终结协议期间的故障,站点故障 协调者超时检测出来 协调者忽略故障站点 协调者故障 某些站点超时 启动竞选协议选择新协调者,75,终结协议,例: 协调者P2 W P1P3 WPC P4W,76,终结协议,新协调者工作如下

26、 在Wait状态 将全局Abort. 此时P可以在任何状态, 若P是在PC状态, 即它是期望有“G-Commit” , 但是得到了“G-Abort”. 3PC中缺少从PC到Abort的转换, 这对终结协议很有用. 在PC状态 此时没有P是在Abort状态, 协调这可以全局提交, 发送“G-Commit”命令. 在Abort状态 所有P进入Abort状态,77,恢复站点,恢复站点发送 “决策申请” 等待响应 只要不是全失败, 就一定能获得响应,78,全故障,例: 协调者P2 P1P3 W P4,79,全故障,恢复进程必须等待, 直到 单个独立的恢复进程P恢复 P 响应决定申请 故障恢复的最新进程

27、恢复 运行终结协议 阻塞!,80,竞选协议,进程全序 协调者 = 0, 参与者 1,n 任何时候, 选择 “最小的” 工作进程为协调者,81,竞选协议实现,UP(p) = 进程集, p是工作的进程 P在协调者超时: 从UP(p) 中移去 c 令 q = UP(p)中最小的元素 如果q=p, p 认为本身当选 否则 p 发送 UR-ELECTED 消息给 q,82,竞选协议实现,当 q 接收到UR-ELECTED 更新 UP(q) 认为本身是新协调者 发送 REQUEST状态 消息给UP(q)中所有参与者 问题 如果p 不是从q处收到REQUEST状态, 将如何办? 参与者P周期性的日志UP(p

28、) 惰性日志 OK,83,注: 3PC对通信故障不安全!,W,W,W,P,P,84,恢复协议,3PC与2PC恢复协议的差别很小 协调者在Wait状态故障, 终结协议P已终结事务, 因此, 协调者必须查询以决定事务的命运 协调者在PC状态故障, 终结协议已使工作的P终结, 因此, 协调者需询问 P在PC状态故障, 必须询问以确定其它参与者如何终结事务,85,网络分割apr.18,简单分割 多分割 网络分割非阻断协议的存在性 也可换成讨论: 在站点故障时, 是否存在允许独立恢复的协议 独立恢复: 指重启动时, 无需远程访问 若存在处理分割的非阻断协议, 那么, 该协议可是分割中的站点到达终结决定,

29、 而且这个决定与另一分割中的决定一致,86,网络分割-续,3PC不能从分割中恢复 例: 若发生了分割, 但不是协调者故障. 此时, 协调者组和参与者组都认为其它站点有故障, 把事务终结, 但是不能保证他们是以同样的非阻断形式终结. 所以, 3PC是在网络分割是存在灾难性故障的风险条件下获得非阻断的性质. 结论 独立恢复协议只存在于单站点故障的情形 若发生网络分割的时候, 丢了报文的话, 则不存在任何非阻断的协议能从网络分割故障中恢复,87,网络分割的终结协议,能处理分割的协议 允许事务至少有一组站点来终止, 于是阻断被减少 主站点法 2PC时 需要当所有挂起事务的协调者都属于此组, 才可能使此

30、站点的全部事务终止. 3PC时 事务由主组的站点来终止,88,网络分割的终结协议-续,多数法和基于法定人数法 在事务中止或提交前, 大多数站点必须一致同意中止或提交 基于法定人数的规则 每个站点i有选票数Vi, Vi是正整数 V= Vi 事务在提交前必须收集提交选票数Vc 事务在Abort前必须收集Abort选票数Va Va+VcV,n,i=1,89,例: 协调者 P2 W P1P3 W P4 W N=5, 多数=,因为 P2, P3, P4 是多数, 所以它们知道没有它们的参与 协调者和 P1 不能 “Commit” 因此, T 事务可以Abort!,90,网络分割的终结协议-续,网络分割时

31、, 在每个分割部分选择一个新的协调者 3PC中加入PA状态, 从而不允许从Wait /Ready到Abort 状态的转换 原因 有多个协调者阻止事务终结, 不允许多个协调者得出不同的结论, 因此希望协调者获得夭折的决定 如果新协调者故障, 它不知道提交或夭折的票数, 这样参与者要得到明确的决定,与参与提交或夭折的法定人数 Ready(或Wait)都不满足该需求, 预示引入另一个状态Pre-Abort, 该状态在Ready和Abor之间,91,网络分割-续,基于法定人数的3PC集中式协议 选择一个新的协调者 协调者收集状态信息, 并按如下规则执行 1) 若至少一个站点已Commit(Abort)

32、, 则对其它站点发送Commit(Abort)命令 2) 若处于PC状态站点的票数=Vc, 则发送Commit 3) 若PA状态站点的票数=Va, 则发送Abort 4) 若PC状态站点的票数+Ready状态站点的票数=Vc, 则发送PC命令给不确定站点, 等待2)状态出现 5) 若PA状态站点的票数+Ready状态站点的票数=Va, 则发送PA命令给不确定站点, 等待3)状态出现 6) 否则, 等待故障修复,92,I,W,A,C,commit prepare,vote-abort global-abort,vote-commit prepare-to-commit,I,R,A,C,prepa

33、re vote-commit,global-abort ACK,prepare-to-commit ready-to-commit,prepare vote-abort,基于法定人数3PC中事务的状态转换图,PC,PC,ready-to-commit global-commit,global-commit ACK,(a) 协调者,(b) 参与者,PA,ready-to-abort global-abort,PA,ready-to-abort global-abort,93,协调者,94,协调者,95,2,多数规则保证了该多数组的任何决定都将被所有分组的决定采纳,1,4,5,3,决定 # 2,决

34、定 # 1,96,简单3PC 与 多数 3PC,简单(基本) 3PC 仅仅工作的站点参与 任何大小的分割组都可以commit/abort (即使是单站点都可以) 全故障后, 必须等待所有的站点恢复(阻塞) 通信故障是不安全 多数 3PC 工作的和恢复的站点都可以参与 只有占多数的分割组才能 commit/abort (阻塞) 能处理通信故障,97,网络分割与提交协议,网络分割 简单分割(二分割) 多重分割 网络分割终结协议 讨论在分割时, 如何终结在分割的每个区域上处于活动的事务 结论: 网络分割时, 不可能找到非阻断的终结协议, 因此这将限制分布式数据库系统的可靠性.,98,非冗余与冗余数据

35、库,非冗余数据库 任何需要访问存储在另一区域里的数据项的新事务都被阻断, 等待网络修复 位于同一区域里的数据项的并发访问有并发控制算法处理 网络分割时有提交协议处理 冗余数据库 分割时, 副本可能位于不同的区域 由复制协议处理,99,网络分割的处理策略,一致性与可用性的选择 非冗余数据库处理网络分割的终结协议 集中式协议 基于集中式并发控制算法(主站点法和主副本法) 基于表决的协议 冗余数据库处理网络分割的终结协议 复制控制协议,100,数据复制,数据库站点 1站点 2站点 3,数据项,分片,101,数据复制的目的 高吞吐量 较好的响应时间 高可用性 复制作为可选择的提交协议 数据在多站点独立

36、更新, 使用“惰性复制协议”减少数据不一致问题.,研究一个片断 可靠网络, 失败-停止站点,102,基本方法,每个副本看作一个独立的数据项,X1,X2,X3,Lock mgr X3,Lock mgr X2,Lock mgr X1,Txi,Txj,Txk,对象 X 有副本 X1, X2, X3,103,Read(X): 获取 X1 共享锁 获取 X2 共享锁 获取 X3 共享锁 分别读 X1, X2, X3 事务结束时, 释放 X1, X2, X3 锁,X1,lock mgr,X3,lock mgr,X2,lock mgr,read,104,Write(X): 获取 X1 互斥锁 获取 X2 互

37、斥锁 获取 X3 互斥锁 写新值到 X1, X2, X3 事务结束时, 释放 X1, X2, X3 锁,X1,X3,X2,lock,lock,lock,write,write,write,105,读锁和访问只对一个副本 写锁全部, 并且更新全部副本,ROWA方法,X1,X2,X3,读者加锁,写者发现冲突!,106,ROWA,读可用性高 写可用性低,107,ROWA的改进(ROWA-A),ROWA-A 读一个写所有可获得协议 更新事务T的协调者向所有包含x副本的站点发送WT(x), 并等待执行(或拒绝)的确认. 当不可获得站点恢复时, 也将更新自己的数据库. 但如果站点在T开始之前就不可获得,

38、它们就可能没有注意到T的存在, 以及T对x的更新. 问题 协调者认为不可获得的参与者仍然工作, 并且更新了x , 但是其确认没有到达协调者 站点在事务启动时不可获得, 随后恢复并开始执行事务,108,ROWA-A,于是, 协调者在提交前要进行有效性验证 检查所有不可获得的站点是否仍然不可获得, 如果写调者收到一个响应, 他就撤销T. 若都是不可获得, 则检查在WT(x)执行时可获得的站点仍然可获得, 是则提交事务 ROWA-A比ROWA协议能更好地适应失效, 包括网络分割.,109,基于法定人数的复制控制,Gifford算法 读法定人数Vr, 写法定人数Vw Vr + Vw V 避免读-写冲突

39、 Vw V/2 避免写-写冲突 该算法确保了在两个不同区域上启动且访问同一数据的事务不会同时终结,110,惰性复制协议,只在一个或多个副本上执行更新, 以后再将更新传播到所有副本上 所有权参数 定义更新副本的权限, 副本可以更新就称为主Copy(主站点), 否则称辅Copy(辅站点) 传播参数 定义何时把对一个副本的更新传播到包含该对象的其它副本 刷新参数 定义了刷新事务的调度策略 配置参数 描述站点和网络的特点,111,惰性复制协议-续,两类 所有副本都可更新, 副本的组所有权, 延迟立即方式更新，多个站点更新同一个冗余对象时有冲突 只有一个被更新的主站点(惰性主站点法) 集中刷新方案: 按

40、需 每次提交执行查询时, 执行所有收到的刷新事务来刷新被查询读取的辅Copy, 造成查询响应延迟 成组刷新 根据应用刷新要求, 成组执行刷新事务 定期刷新 在固定时间间隔内触发刷新,112,不一致性检测(1),网络的一致视图 可靠性算法是假定: 全部能工作的站点对网络的所有站点(包括其本身)的状态(即工作或故障)具有一致的视图 决定网络的一致视图 监视网络的状态 当站点状态发生转换时, 能及时发现 新的信息一致地传播给全部站点,113,不一致性检测(2),假设 广义的网络范围内 每个站点有一状态表, 每个站点一个表项, 记录其工作/不工作 任何程序能够在任一站点设置一个“看守”, 当该站点变化

41、状态时它就收到一个中断 分割时, 状态表和一致视图的意义 站点只认为那些能和它通信的站点是工作的 一致视图的数目与分离的站点组数目一样多,114,不一致性检测(3),监视网络的状态 决定一站点是否工作时向它请求一个报文, 然后等待到超时 控制站点 (请求站点) 受控站点 受控站点周期性地发送I-an-up报文,115,网络,站点 K-3,UP,站点 K-2,DOWN,站点 K-1,站点 K,UP,DOWN,(状态),网络上站点的状态,站点K控制站点K-3, 即它检查来自K-3的I-am-up报文是否到达 站点K负责发现站点K-1和K-2从不工作到工作的恢复 上图中K-1和K-2不一定是有故障,

42、 它们可能在分割的另一组中 图反映了站点K和K-3的网络视图,116,不一致性检测(4),广播新的状态 监视功能每次检测出一个状态变化, 就即获此广播功能 此功能可由若干站点并行激活, 需要某种机构来控制冲突 状态表的每个新的版本附加一全局唯一的时间戳 在I-am-up报文中包含当前状态表的版本号 启动新状态表传播的站点首先执行同步以获得一时间戳,117,不一致的检测方法(1),假设分割期间, 在两个或多个站点组中已执行了若干事务, 可能对同一数据片断的不同副本进行了独立更新 比较各副本的内容, 检查其是否相同 航空订票系统 采用版本号 允许对数据项操作的副本是主副本, 其它是孤立或隔离的副本

43、,118,不一致的检测方法(2),正常工作期间, 全部副本都是主副本, 并且互相一致, 每份副本维持一个原版号和一个当前版本号 网络分割时, 每个孤立副本的原版号被置为当前版本号值, 并且, 直到分割修复为止, 此原版号不会改变 例子 数据项x的副本x1, x2, x3 存储在三个不同站点 V1, V2, V3分别是x1, x2, x3的版本号,119,不一致的检测方法(3),初始时, 三份副本一致, 所以有: V1=(0, 2) V2 =(0, 2) V3=(0, 2) 发生一次分割, 把x3从其它两个副本分开, 多数法选择x2和x1为主副本, 版本号变为 V1=(0, 2) V2 =(0, 2) V3=(2, 2) 网络分割期