基本容错方法和技术分布式数据库系统的故障原因-OSCARLab.PPT

Write(X): 获取 X1 互斥锁 获取 X2 互斥锁 获取 X3 互斥锁 写新值到 X1, X2, X3 事务结束时, 释放 X1, X2, X3 锁 X1 X3 X2 lock lock lock write write write 读锁和访问只对一个副本 写锁全部, 并且更新全部副本 读可用性高 写可用性低，只要有一个副本不可获得，更新 事务就不能终结 ROWA方法 X1 X2 X3 读者加锁 写者发现冲突! 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-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不一定是有故障, 它们可能在分割的另一组中， 图反映了站点K和K-3的网络视图 广播新的状态 监视功能每次检测出一个状态变化, 就激活此广播功能 此功能的目的是广播新的状态表，使同一组的全部站点具有相同的状态表 此功能可由若干站点并行激活, 需要某种机构来控制冲突 状态表的每个新的版本附加一全局唯一的时间戳 在I-am-up报文中包含当前状态表的版本号 启动新状态表广播的