第7章_分布式数据库中的可靠性

1、分布式数据库的可靠性的概念及其度量分布式数据库的可靠性的概念及其度量分布式数据库系统的故障原因和容错技术分布式数据库系统的故障原因和容错技术分布式数据库的可靠性协议分布式数据库的可靠性协议网络分割和提交协议网络分割和提交协议不一致性监测和解决方法不一致性监测和解决方法分布式数据库中的可靠性分布式数据库中的可靠性 第第7章章 可靠性 指数据库在一给定时间间隔内不产生任何失败的概率。 它强调数据库的正确性，要求数据库正确运行，既符合某种规格化要求。 通常用来描述不可修复的系统。 可用性 强调的是当需要访问数据库时，它是可用的。 指在给定的时间点系统可以正常运行的概率。 通常用于描述那些可以修复的系

2、统。 两者关系 通常认为构建可用性的系统比可靠性的系统容易 两者是统一的，可靠性高的系统可用性自然是好的 两者又是矛盾的，增加错误风险的情况下，可提高可用性;采用太谨慎的策略会降低可用性1.1 分布式数据库可靠性概念分布式数据库可靠性概念1 1 分布式数据库可靠性概念及其度量分布式数据库可靠性概念及其度量例: Site1 Site2 x1 x2 Lock x1 Lock x2 2PC Ready故障出现Site1也Ready故CommitSite 2 等待此时Site 2有两种可能:a 以正确性为标准，x2则等待, 并Lock 2, 直到故障恢复。提高了可靠性，但牺牲了可用性。b 引入不一致性

3、的风险下, 尽量提高可用性，解锁x2, 其它事务可以使用它的值。Site 1 正常结束1.1 分布式数据库可靠性概念分布式数据库可靠性概念1 1 分布式数据库可靠性概念及其度量分布式数据库可靠性概念及其度量已知已知x1和和x2是是x的副本的副本事务事务T是更新是更新x的事务的事务Site 1是协调站点是协调站点Site 1是事务是事务T原发站点原发站点遵守两阶段提交协议遵守两阶段提交协议 平均故障间隔时间 指在可以自我修复的系统中相继失败之间的期望时间 通过可靠性函数来计算MTBF=0R(t)dt MTBF与系统失败的概率有直接的关系 平均修复时间 是指修复一个系统所需要的期望时间，MTTR

4、它与失败概率有关 指数型失败和修复的概率的系统可用性 A=MTBF/(MTBF+MTTR) 可用性系统 5个9（99.999%）常用来描述可用性系统 但是可用性系统要求的成本比较高 具体设计时要综合用户两方面的要求1.2 平均故障间隔时间和平均修复时间平均故障间隔时间和平均修复时间1 1 分布式数据库可靠性概念及其度量分布式数据库可靠性概念及其度量 系统（System） 是由一组组件构成的一种机制，这些组件通过响应来自某个环境的具有可识别行为模式的刺激而相互作用。component1component2component3环境系统刺激响应 系统规范说明（Specification） 系统提供的

5、对所有可能的刺激将产生的响应行为必须遵循的说明2.1 系统失败的原因系统失败的原因2 2 分布式数据库系统的故障原因和容错技术分布式数据库系统的故障原因和容错技术 故障 任何偏离规范说明的行为 软故障和硬故障 软故障包括间歇性（intermittent）和瞬变性（transient）故障，通过重启动来修复 硬故障指永久性故障, 错误设计等 软件和硬件故障2.1 系统失败的原因系统失败的原因2 2 分布式数据库系统的故障原因和容错技术分布式数据库系统的故障原因和容错技术 软故障 占90%以上并且该比例稳定 67年， 美空军指出计算机中电子故障80%是间歇性的 67年，IBM 指出 90%故障是间

6、歇性的 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的原因是产生软件故障的主要原因. 代

7、码中的Bug, 曾有报告指出, 1000条指令中, 0.25-10个BUG2.1 系统失败的原因系统失败的原因2 2 分布式数据库系统的故障原因和容错技术分布式数据库系统的故障原因和容错技术永久性故障错误的设计不稳定或者临界的组件不稳定的外部环境操作者的过失系统失败永久性错误间歇性错误瞬变的错误系统失败的原因 容错 设计一种使系统识别出可能会发生的错误的方法。在系统中建立一种机制，使错误在造成系统故障之前就会被检测出来，并能被清除或得到补偿。 错误预防 保证所实现的系统不包含任何错误 错误回避：保证系统不会带入错误的技术（详细的设计方法学和质量控制） 错误清除：清查那些在使用了错误回避技术路线

8、后还残留在系统中的错误，并清除它们（需要大量的测试和证实过程）2.2 基本容错方法和技术基本容错方法和技术2 2 分布式数据库系统的故障原因和容错技术分布式数据库系统的故障原因和容错技术 故障检测 潜伏的故障：故障发生一段时间后才被检测出来 错误潜伏期：从故障发生到被检测出来的时间 平均检测时间(MTTD)：平均错误潜伏时间 平均修复时间(MTTR)：修复一个失败的系统所需要的期望时间 平均故障间隔时间(MTBF)：在可以自我修复的系统中相继的失败之间的期望时间, 由经验或从可靠性函数计算2.2 基本容错方法和技术基本容错方法和技术2 2 分布式数据库系统的故障原因和容错技术分布式数据库系统的

9、故障原因和容错技术 MTBF MTTDMTTR在这段时间内，可能发生多起错误故障发生造成错误检测到错误修复故障发生造成错误时间 相继发生的事件2.2 基本容错方法和技术基本容错方法和技术2 2 分布式数据库系统的故障原因和容错技术分布式数据库系统的故障原因和容错技术 冗余 所有容错系统设计中都采用的基本原则是在系统的组件中提供冗余 模块化 系统的每个组件都设计为具有定义很好的输入/输出接口的模块 模块化可以把故障隔离在单一的组件中 系统实现 故障-停止模块（fail-stop module) 进程对（Process pairs)2.2 基本容错方法和技术基本容错方法和技术2 2 分布式数据库系

10、统的故障原因和容错技术分布式数据库系统的故障原因和容错技术time正常 停止 恢复 正常易失存储丢失稳定存储 ok 故障-停止模块 不断地对自身进行检测，当检测到一个故障时，就自动停止。 优点是缩短了故障检测的潜伏期。2.2 基本容错方法和技术基本容错方法和技术2 2 分布式数据库系统的故障原因和容错技术分布式数据库系统的故障原因和容错技术 进程对（Process pairs) 通过软件模块的双工来实现容错。两个进程，一个是主进程，一个是备份，它们同时提供同样的服务，主进程与备份进程都是基于故障-停止模块实现。 分类方式（根据主进程和备份进程之间的通信方式） 锁定-步进方式 自动检查点设置方式

11、 状态检查点设置方式 Delta检查点设置方式 持久进程对2.2 基本容错方法和技术基本容错方法和技术2 2 分布式数据库系统的故障原因和容错技术分布式数据库系统的故障原因和容错技术 分布式数据库的可靠性协议是为了保证在分布式数据库上执行的分布式事务的原子性和持久性。 这些协议描述了Begin_Transaction、Read、Write、Abort、 Commit和Recover原语的分布式执行过程。3.1 分布式可靠性协议分布式可靠性协议3 3 分布式数据库的可靠性协议分布式数据库的可靠性协议 分布式数据库系统的可靠性协议包括提交协议、终结协议和恢复协议 提交协议和恢复协议详细说明了提交命

12、令和恢复命令是如何执行的。 终结协议是分布式系统特有的。设想在执行一个分布式事务时，其中一个站点失效了，我们希望其它站点也停止该事务，处理这种情况的技术就称为终结协议。 终结协议和恢复协议是恢复问题的两个相反的方面：假定一个站点失效了，终结协议确定了未失效站点如何处理该失效事件； 而恢复协议确定失效站点重新启动后，其进程（协调者或参与者）恢复它的状态的过程。在网络分割的情况下，终结协议采取必要的措施来终结在不同的网络区间执行的活动事务；在网络重新连接后，恢复协议保证使各个冗余数据库相互一致。3.1 分布式可靠性协议分布式可靠性协议3 3 分布式数据库的可靠性协议分布式数据库的可靠性协议 目的

13、维持在多个数据库上执行的事务的原子性和持久性 原语 Begin_Transaction read, write, Abort, commit 命令执行与局部协议类似3.1 分布式可靠性协议分布式可靠性协议3 3 分布式数据库的可靠性协议分布式数据库的可靠性协议 可靠性协议组成 包括提交、终结、恢复协议 提交和恢复协议详细说明提交命令和恢复命令是如何执行的 终结协议是分布式系统特有的协议。在执行一个分布式事务时，若一个Site故障，希望其它Site也停止该事务。处理这种情况的技术就称为终止协议。3.1 分布式可靠性协议分布式可靠性协议3 3 分布式数据库的可靠性协议分布式数据库的可靠性协议 终结

14、协议与恢复协议的比较 假若一个Site失效 终结协议确定了未失效Site如何处理该失效事件 恢复协议确定失效Site重启动后，进程（协调者，参与者）恢复它的状态的过程 网络分割时 终结协议采取必要的措施来终结在不同网络区间执行的活动事务 当网络重新连接后，恢复协议保证使各个冗余DB相互一致3.1 分布式可靠性协议分布式可靠性协议3 3 分布式数据库的可靠性协议分布式数据库的可靠性协议 两阶段提交协议的要点 允许参与者单方面撤销事务，直到做出肯定性的建议 一旦参与者确定了提交或者撤销提议，它不能再更改 当参与者处于就绪状态，它可根据协调者发出的消息的种类，转换为相应的提交或者撤销状态 协调者依据

15、全局提交规则作出全局终结决定 在发生故障的情况下，协调者和参与者可能会进入互相等待的状态，一般采用定时器来解决这种问题3.2 两阶段提交协议的演变两阶段提交协议的演变3 3 分布式数据库的可靠性协议分布式数据库的可靠性协议协调者参与者PREPAREPREPAREDCOMMITACK2PC-提交协 调 者参 与 者PREPARENOABORTACK2PC-夭折集中式2PC协调者 参与者IWCAIRCAcommit-申请 申请-prepare* no abort* prepared* commit commit ACK 申请-prepare prepared 申请-prepare no abort

16、 ACKF ACK* ACK* 标记: 输入消息 输出消息* = 每一个3.2 两阶段提交协议的演变两阶段提交协议的演变3 3 分布式数据库的可靠性协议分布式数据库的可靠性协议 当参与者进入“R”状态: 它必定已获得所有资源 它只能根据协调者指令提交或夭折 当所有参与者是在“R”时, 协调者才能进入“C” 状态, 即, 它一定最终能提交3.2 两阶段提交协议的演变两阶段提交协议的演变3 3 分布式数据库的可靠性协议分布式数据库的可靠性协议 假定撤销2PC和假定提交2PC协议 目的是改善2PC的性能 假定撤销协议中，协调者不必等待参与者的ACK消息，减少了协调者与参与者之间传递消息的数量 假定提

17、交协议中，可以不将Prepare写入Log，减少了Log写入的次数3.2 两阶段提交协议的演变两阶段提交协议的演变3 3 分布式数据库的可靠性协议分布式数据库的可靠性协议 事务阻断：某个Site上本来可以终结（提交或撤销）的子事务，由于DDBS故障，必须等待到故障恢复（其占有的资源不释放） 阻断协议：提交协议称为阻断协议是指发生某类故障时，使分布式事务可能处于阻断状态 终结协议：允许事务在有故障情况下仍能正确结束3.3 事务阻断与终结协议事务阻断与终结协议3 3 分布式数据库的可靠性协议分布式数据库的可靠性协议 判断2PC协议是终结协议的条件 至少有一个Site已收到结果命令（该Site可以告

18、知其它参与者关于该事务的结果，并由它们来终结该事务） 没有一个参与者收到命令，并且只有协调者Site故障（此时，所有参与者站点都是可工作的，参与者可以选举一个新的协调者，然后继续）3.3 事务阻断与终结协议事务阻断与终结协议3 3 分布式数据库的可靠性协议分布式数据库的可靠性协议 终结协议在协调者和参与者的定时器超时时发挥作用 超时处理技术 协调者超时 在等待状态超时，可以决定“全局撤销” 在撤销状态超时，重发“G-abort” 在提交状态超时，重发“G-commit” 参与者超时（被阻断时出现） 在初始状态超时，单方面Abort 在Ready状态超时，被阻断，等待事务最终处理结果3.4 2P

19、C协议的终结协议协议的终结协议3 3 分布式数据库的可靠性协议分布式数据库的可靠性协议协调者超时IWCAFcommit-申请申请-prepare*ack*-ack*-_t_abortanyabortanycommit_t_commit_t_abort*noabort*prepared*commit*t=timeout参与者超时IRCA申请-prepareprepared等价于结束状态_t_ ping申请-preparenocommitackabortackcommitackabortack 设计终结协议 假定Pi是超时的参与者（询问Pj），其它Pj按如下响应 Pj处于初始状态，于是单方面Abo

20、rt，并回送“建议abort”给Pi Pj处于Ready状态，此时不能帮助Pi终结 Pj处于Commit或Abort状态，此时向Pi发送“建议提交”或“建议Abort”3.4 2PC协议的终结协议协议的终结协议3 3 分布式数据库的可靠性协议分布式数据库的可靠性协议 Pi超时，可能有的解释 Pi收到Pj的“建议撤销”回答，此时Pi夭折 Pi收到Pj“建议撤销”回答，但是其它Pj处于Ready状态，此时Pi仍然Abort Pi收到Pj处于Ready状态，此时没有一个参与者有足够的信息恰当地终结事务 Pi收到其他所有的Pj”全局提交”或”全局夭折”消息，Pi可以根据消息终结 Pi收到某些Pj的“全

21、局提交”，而另一些Pj处于Ready状态，Pi可以提交3.4 2PC协议的终结协议协议的终结协议3 3 分布式数据库的可靠性协议分布式数据库的可靠性协议 协调者站点失效 协调者在初始状态失效 发生在协调者初始化提交过程之前 因此，它将在恢复时启动提交过程 协调者在等待状态失效 这时协调者已经发送了“准备”命令 恢复时，协调者将从头开始启动提交过程，再次发送“准备”消息 协调者在提交状态或撤销状态失效 这时，协调者已经把它的决定通知了参与者，并终结了事务 在恢复时，如果它已经收到了所有的确认消息，就不需要做任何事情 否则，就要启动终结协议3.5 2PC协议的恢复协议协议的恢复协议3 3 分布式数

22、据库的可靠性协议分布式数据库的可靠性协议 参与者站点失效 一个参与者在初始状态失效 在恢复时，该参与者应该单方面撤销事务 一个参与者在就绪状态失效 这时协调者已经收到失效站点在失效前发送的肯定决定 恢复时，失效站点的参与者认为是在就绪状态发生了超时，于是启动终结协议来处理该事务 一个参与者在提交状态或撤销状态失效 这些状态表示了终结条件，所以在恢复时，参与者不需要采取任何专门的措施 附加情形（略）3.5 2PC协议的恢复协议协议的恢复协议3 3 分布式数据库的可靠性协议分布式数据库的可靠性协议 提交协议是非阻断的充要条件是, 在其状态转换图中不存在: 没有状态是即与提交又与撤销状态“相邻” 不

23、存在不可提交状态是与提交状态“相邻” 相邻 从一个状态直接转换到另一个状态3.6 三阶段提交协议三阶段提交协议3 3 分布式数据库的可靠性协议分布式数据库的可靠性协议 2PC中的状态 C(提交)状态是可提交状态, 其它为不可提交状态 Ready 状态是不可提交状态 Wait状态是不可提交状态 它们都侵犯了非阻断协议的充要条件, 从而考虑改变2PC, 使其满足非阻断协议条件 在Wait 和 Commit 之间, 或者在Ready和Commit之间加入另一种状态作为缓冲状态, 从而有了3PC协议3.6 三阶段提交协议三阶段提交协议3 3 分布式数据库的可靠性协议分布式数据库的可靠性协议IWcomm

24、itpreparevote-abortglobal-abortvote-commitprepare-to-commitIRpreparevote-commitglobal-abortACKprepare-to-commitready-to-commitpreparevote-abort3PC中事务的状态转换图PCPCready-to-commitglobal-commit global-commitACK(a) 协调者(b) 参与者协调者参与者 PREPAREPREPAREDCOMMITDONE PRECOMMITACK协调者参与者 PREPARENOABORTDONE协调者参与者开始-3PC

25、 记录写Log (参与者列表)commit记录写Log (状态C)prepared记录写Log (状态 W)committed 记录写Log (状态 C) PREPAREPREPAREDCOMMIT PRECOMMITACK协调者参与者初始写begin_commit到日志等待有要求撤消的？写Prepare-to-commit到日志准备提交写end_of_trans.到日志初始准备提交？写ready到日志就绪消息类型？写abort到日志写prepare-to-commit到日志准备提交撤消撤消写abort到日志写abort到日志准备撤消提交全局撤消准备提交ACKACK nono abortPre

26、pare-to-commit写commit到日志提交提交 在 中事务执行的过程 写commit到日志撤消提交准备提交3PC 协调者 在Wait状态超时：与2PC中协调者在Wait超时相同, 协调者单方面Abort 在PC状态超时：此时协调者不知道未响应的参与者是否到达PC. 但是知道每个参与者至少在Ready状态, 因此协调者可以将所有参与者移入PC状态 在Commit/Abort状态超时 协调者不知参与者是否已执行命令,但是对Commit而言, 知道参与者至少在PC状态。因此，协调者不需要做专门的处理3.7 三阶段提交协议的超时处理三阶段提交协议的超时处理3 3 分布式数据库的可靠性协议分布

27、式数据库的可靠性协议 参与者超时 在Initial状态超时：与2PC中的情况相同 在Ready状态超时：参与者准备Commit. 由于与协调者的通信丢失, 终结协议将选举一个新的协调者，新协调者根据下面所述终结协议终结事务 在PC状态超时：参与者已收到“Prepare-to-commit”, 正在等待来自协调者的“全局提交”消息, 处理同第二条。3.7 三阶段提交协议的超时处理三阶段提交协议的超时处理3 3 分布式数据库的可靠性协议分布式数据库的可靠性协议协调者参与者 PREPAREPREPAREDCOMMIT PRECOMMITACK1. 超时: Abort3. 超时: 忽略1. 超时: a

28、bort2. 超时:终结协议3.超时:终结协议2. 超时: 把参与者移入PC 竞选新的协调者 使用竞选协议 新协调者送出 REQUEST状态给参与者 使用终结规则做出决定 与参与者通信3.8 三阶段提交协议的终结协议三阶段提交协议的终结协议3 3 分布式数据库的可靠性协议分布式数据库的可靠性协议竞选协议 进程全序 协调者 = 0, 参与者 1,n 任何时候, 选择 “最小的” 工作进程为协调者3.8 三阶段提交协议的终结协议三阶段提交协议的终结协议3 3 分布式数据库的可靠性协议分布式数据库的可靠性协议 终结规则 新协调者在Wait状态：将全局Abort. 此时参与者可以在任何状态, 若参与者

29、是在PC状态, 即它是期望有“G-Commit” , 但是得到了“G-Abort”. 3PC中缺少从PC到Abort的转换, 这对终结协议很有用. 新协调者在PC状态：此时没有参与者是在Abort状态, 协调者可以全局提交, 发送“G-Commit”命令. 新协调者在Abort状态：收到第一个消息后，所有参与者进入Abort状态3.8 三阶段提交协议的终结协议三阶段提交协议的终结协议3 3 分布式数据库的可靠性协议分布式数据库的可靠性协议 3PC与2PC恢复协议的差别很小 协调者在Wait状态故障, 按照终结协议，参与者已终结事务, 因此, 协调者在恢复时必须查询以决定事务的命运 协调者在PC

30、状态故障, 终结协议已使工作的参与者终结, 因此, 协调者需询问 一个参与者在PC状态故障, 必须询问以确定其它参与者如何终结事务3.9 三阶段提交协议的恢复协议三阶段提交协议的恢复协议3 3 分布式数据库的可靠性协议分布式数据库的可靠性协议 网络分割是由通信线路故障引起的 简单分割，仅仅是网络分裂成两部分 多重分割，更复杂 网络分割非阻断协议的存在性 即在发生网络分割时, 是否存在允许独立恢复的协议 独立恢复是指站点重启动时, 无需远程访问 若存在处理分割的非阻断协议, 那么, 该协议可使某个分割中的站点到达终结决定, 而且这个决定与另一分割中的决定一致 一般结论 独立恢复协议只存在于单站点

31、故障的情形 若发生网络分割的时候, 丢了报文的话, 则不存在任何非阻断的协议能从网络分割故障中恢复4.1 网络分割概述网络分割概述4 4 网络分割与提交协议网络分割与提交协议 非冗余数据库 任何需要访问存储在另一网络区域里的数据项的新事务都被阻断, 等待网络修复 位于同一区域里的数据项的并发访问由并发控制算法处理 网络分割时由提交协议处理 冗余数据库 分割时, 副本可能位于不同的区域 由复制协议处理4.1 网络分割概述网络分割概述4 4 网络分割与提交协议网络分割与提交协议 网络分割处理策略 一致性与可用性的选择 非冗余数据库处理网络分割的终结协议 集中式协议，基于集中式并发控制算法(主站点法

32、和主副本法) 基于表决的协议 冗余数据库处理网络分割的终结协议 复制控制协议4.1 网络分割概述网络分割概述4 4 网络分割与提交协议网络分割与提交协议 集中式终结协议基于集中式并发控制算法。 由于主站点管理着封锁表，所以主站点并发控制算法允许在包含主站点的区域继续进行正常的操作。 主副本并发控制算法允许在多个区域执行不同的查询。 对任意给定的查询，只有包含事务写集中的数据项的主副本区域可以继续执行该事务。4.2 集中式终结协议集中式终结协议4 4 网络分割与提交协议网络分割与提交协议 多数法和基于法定人数法 在事务中止或提交前, 大多数站点必须一致同意中止或提交 基于法定人数的规则 每个站点

33、i有选票数Vi, Vi是正整数 V= Vi 事务在提交前，它必须获得提交法定票数Vc 事务在Abort前，它必须获得Abort法定票数Va Va+VcV, 当0 Va, Vc Vni=14.3 基于表决的协议基于表决的协议4 4 网络分割与提交协议网络分割与提交协议 网络分割时, 在每个分割部分选择一个新的协调者 3PC中加入PA状态, 从而不允许从Wait /Ready到Abort 状态的转换 原因 有多个协调者阻止事务终结, 不允许多个协调者得出不同的结论, 因此希望协调者获得撤销的决定 如果新协调者故障, 它不知道是否达到提交或撤销的法定票数, 这样参与者必须明确做出提交或撤销的决定 R

34、eady(或Wait)都不满足该需求, 预示引入另一个状态Pre-Abort, 该状态在Ready和Abort之间4.3 基于表决的协议基于表决的协议4 4 网络分割与提交协议网络分割与提交协议IWcommitpreparevote-abortglobal-abortvote-commitprepare-to-commitIRpreparevote-commitglobal-abortACKprepare-to-commitready-to-commitpreparevote-abort基于法定人数3PC中事务的状态转换图PCPCready-to-commitglobal-commit glo

35、bal-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状态站点

36、的票数+Ready状态站点的票数=Va, 则发送PA命令给不确定站点, 等待3)状态出现6) 否则, 等待故障修复4.3 基于表决的协议基于表决的协议4 4 网络分割与提交协议网络分割与提交协议 数据复制的目的 高吞吐量 较好的响应时间 高可用性 复制作为可选择的提交协议 数据在多站点独立更新, 使用“惰性复制协议”减少数据不一致问题. 4.4 复制控制协议复制控制协议4 4 网络分割与提交协议网络分割与提交协议 基本方法： 每个副本看作一个独立的数据项X1X2X3Lockmgr X3Lockmgr X2Lockmgr X1TxiTxjTxk对象 X 有副本 X1, X2, X34.4 复制控

37、制协议复制控制协议4 4 网络分割与提交协议网络分割与提交协议 Read(X): 获取 X1 共享锁 获取 X2 共享锁 获取 X3 共享锁 分别读 X1, X2, X3 事务结束时, 释放 X1, X2, X3 锁X1lockmgrX3lockmgrX2lockmgrread Write(X): 获取 X1 互斥锁 获取 X2 互斥锁 获取 X3 互斥锁 写新值到 X1, X2, X3 事务结束时, 释放 X1, X2, X3 锁X1X3X2locklocklockwritewritewrite 读锁和访问只对一个副本 写锁全部, 并且更新全部副本 读可用性高 写可用性低，只要有一个副本不可

38、获得，更新事务就不能终结ROWA方法X1X2X3读者加锁写者发现冲突!4.4 复制控制协议复制控制协议4 4 网络分割与提交协议网络分割与提交协议ROWA的改进(ROWA-A) ROWA-A “读一个写所有可获得协议” 基本思想是写命令在所有可获得的副本上执行，然后事务终结，当时不可获得的副本将在它们重新可获得时被捕获 更新事务T的协调者向所有包含x副本的站点发送WT(x), 并等待执行(或拒绝)的确认. 当不可获得站点恢复时, 也将更新自己的数据库. 但如果站点在T开始之前就不可获得, 它们就可能没有注意到T的存在, 以及T对x的更新. 问题 协调者认为不可获得的参与者仍然工作, 并且更新了

39、x , 但是其确认没有到达协调者 站点在事务启动时不可获得, 随后恢复并开始执行事务4.4 复制控制协议复制控制协议4 4 网络分割与提交协议网络分割与提交协议 于是, 协调者在提交前要进行有效性验证 检查所有不可获得的站点是否仍然不可获得, 如果协调者收到一个响应, 它就撤销T. 若都是不可获得, 则检查在WT(x)执行是可获得的站点仍然可获得, 是则提交事务 ROWA-A比ROWA协议能更好地适应失效, 包括网络分割.ROWA的改进(ROWA-A)4.4 复制控制协议复制控制协议4 4 网络分割与提交协议网络分割与提交协议基于法定人数的复制控制 Gifford算法 读法定人数Vr, 写法定

40、人数Vw 规则1：Vr + Vw V，可避免读-写冲突 规则2：Vw V/2，避免写-写冲突 该算法确保了在两个不同网络区域上启动且访问同一数据的事务不会同时终结4.4 复制控制协议复制控制协议4 4 网络分割与提交协议网络分割与提交协议惰性复制协议 思想 只在一个或多个副本上执行更新, 以后再将更新传播到所有副本上 特点 所有权参数：定义更新副本的权限, 副本可以更新就称为主Copy(主站点), 否则称辅Copy(辅站点) 传播参数：定义何时把对一个副本的更新传播到包含该对象的其它副本 刷新参数：定义了刷新事务的调度策略 配置参数：描述站点和网络的特点4.4 复制控制协议复制控制协议4 4

41、网络分割与提交协议网络分割与提交协议 两类 所有副本都可更新, 存在副本的组所有权, 常用延迟立即方式更新 只有一个被更新的主站点(惰性主站点法) 几种刷新方案: 按需刷新, 每次提交执行查询时, 执行所有收到的刷新事务来刷新被查询读取的辅Copy, 造成查询响应延迟 成组刷新, 根据应用刷新要求, 成组执行刷新事务 定期刷新, 在固定时间间隔内触发刷新惰性复制协议4.4 复制控制协议复制控制协议4 4 网络分割与提交协议网络分割与提交协议 网络的一致视图 可靠性算法是假定: 全部能工作的站点对网络的所有站点(包括其本身)的状态(即工作或故障)具有一致的视图 决定网络的一致视图 监视网络的状态

42、，当站点状态发生转换时, 能及时发现 新的信息一致地传播给全部站点5.1 决定网络的状态决定网络的状态5 5 不一致性检测和解决方法不一致性检测和解决方法 假设 建于广义的网络范围内 每个站点有一状态表, 每个站点一个表项, 记录其工作/不工作，程序可查询状态表得到状态信息 任何程序能够在任一站点设置一个“看守”, 当该站点变化状态时它就收到一个中断 分割时, 状态表和一致视图的意义 站点只认为那些能和它通信的站点是工作的 一致视图的数目与分离的站点组数目一样多5.1 决定网络的状态决定网络的状态5 5 不一致性检测和解决方法不一致性检测和解决方法 监视网络的状态 决定一站点是否工作时向它请求

43、一个报文, 然后等待到超时 控制站点 (请求站点) 受控站点 在一广义监视算法中，受控站点周期性地发送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的网络视图 广播新的状态 监视功能每次检测出一个状态变化, 就激活此广播功能 此功能

44、的目的是广播新的状态表，使同一组的全部站点具有相同的状态表 此功能可由若干站点并行激活, 需要某种机构来控制冲突 状态表的每个新的版本附加一全局唯一的时间戳 在I-am-up报文中包含当前状态表的版本号 启动新状态表广播的站点首先执行一次同步以获得一时间戳，然后发送状态表给已回答的所有站点5.1 决定网络的状态决定网络的状态5 5 不一致性检测和解决方法不一致性检测和解决方法 需求 处理故障的策略有可能牺牲正确性来提高可用性，因此接受了不一致性的风险 在这种情况下，监测这些不一致性，并尽可能地加以解决是很有用的 概念 需要首先发现哪些数据部分已经不一致（不一致性检测） 然后根据发生的情况，给这

45、些部分赋予一个最合理的值（不一致性的解法）5.2 不一致性的检测和解决方法概念不一致性的检测和解决方法概念5 5 不一致性检测和解决方法不一致性检测和解决方法 提出问题 假设网络分割期间, 在两个或多个站点组中已执行了若干事务, 可能对同一数据片断的不同副本进行了独立更新 检测方法 一种比较自然的方法 比较各副本的内容, 检查其是否相同，但是这种方法不仅效率低，一般也是不正确的。5.3 不一致性的检测不一致性的检测5 5 不一致性检测和解决方法不一致性检测和解决方法 检测方法 采用版本号 允许对数据项操作的站点的副本是主副本, 其它是孤立或隔离的副本 正常工作期间, 全部副本都是主副本, 并且

46、互相一致, 每份副本维持一个原版号和一个当前版本号 网络分割时, 每个孤立副本的原版本号被置为当前版本号值, 并且, 直到分割修复为止, 此原版号不会改变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为主副本, 版本号变

47、为 V1=(0, 2)，V2 =(0, 2)， V3=(2, 2) 网络分割期间, 假设只更新主副本, 版本号为 V1=(0, 3)，V2 =(0, 3) ，V3=(2, 2) 修复后, 可以看出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) 那么，此孤立副本