崔明义
（ mycui369@126.com)
计算机应用技术 2007级研究生
1,分布式数据库的可靠性的概念及其度量
2.分布式数据库系统的故障原因和容错技术
3.分布式数据库的可靠性协议
4.网络分割和提交协议
5.不一致性监测和解决方法分布式数据库中的可靠性第 6章
可靠性
– 指数据库在一给定时间间隔内不产生任何失败的概率。
– 它强调数据库的正确性，要求数据库正确运行，既符合某种规格化要求。
– 通常用来描述不可修复的系统。
可用性
– 强调的是当需要访问数据库时，它是可用的。
– 指在给定的时间点系统可以正常运行的概率。
– 通常用于描述那些可以修复的系统。
两者关系
– 通常认为构建可用性的系统比可靠性的系统容易
– 两者是统一的，可靠性高的系统可用性自然是好的
– 两者又是矛盾的，增加错误风险的情况下，可提高可用性 ;采用太谨慎的策略会降低可用性
1.1 分布式数据库可靠性概念
1 分布式数据库可靠性概念及其度量例,Site1 Site2
x1 x2
Lock x1 Lock x2
2PC Ready
故障出现
Site1也 Ready
故 Commit
Site 2 等待此时 Site 2有两种可能,
a> 以正确性为标准,x2则等待,并 Lock 2,直到故障恢复。提高了可靠性，但牺牲了可用性。
b> 引入不一致性的风险下,
尽量 提高可用性,解锁 x2,
其它事务可以使用它的值。
Site 1 正常结束
1.1 分布式数据库可靠性概念
1 分布式数据库可靠性概念及其度量已知
x1和 x2是 x的副本
事务 T是更新 x的事务
Site 1是协调站点
Site 1是事务 T原发站点
遵守两阶段提交协议
平均故障间隔时间
– 指在可以自我修复的系统中相继失败之间的期望时间
– 通过可靠性函数来计算 MTBF=∫0∞R(t)dt
– MTBF与系统失败的概率有直接的关系
平均修复时间
– 是指修复一个系统所需要的期望时间,MTTR
– 它与失败概率有关
指数型失败和修复的概率的系统可用性
– A=MTBF/(MTBF+MTTR)
可用性系统
– 5个 9（ 99.999%）常用来描述可用性系统
– 但是可用性系统要求的成本比较高
– 具体设计时要综合用户两方面的要求
1.2 平均故障间隔时间和平均修复时间
1 分布式数据库可靠性概念及其度量
系统 （ System） 是由一组组件构成的一种机制，这些组件通过响应来自某个环境的具有可识别行为模式的刺激而相互作用。
component1 component2
component3
环境系统刺激 响应
系统规范说明 （ Specification） 系统提供的对所有可能的刺激将产生的响应行为必须遵循的说明
2.1 系统失败的原因
2 分布式数据库系统的故障原因和容错技术
故障
– 任何偏离规范说明的行为
软故障和硬故障
– 软故障包括间歇性（ intermittent）和瞬变性
（ transient）故障，通过重启动来修复
– 硬故障指永久性故障,错误设计等
软件和硬件故障
2.1 系统失败的原因
2 分布式数据库系统的故障原因和容错技术
软故障 占 90%以上并且该比例稳定
– 67年,美空军指出计算机中电子故障 80%是间歇性的
– 67年,IBM 指出 90%故障是间歇性的
– 80年，研究指出软故障明显高于硬故障
– 87年,Gray指出 大部分软件故障是瞬变性故障
2.1 系统失败的原因
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,曾有报告指出,1000条指令中,0.25-10
个 BUG
2.1 系统失败的原因
2 分布式数据库系统的故障原因和容错技术永久性故障错误的设计不稳定或者临界的组件不稳定的外部环境操作者的过失系统失败永久性错误间歇性错误瞬变的错误系统失败的原因
容错
– 设计一种使系统识别出可能会发生的错误的方法。
在系统中建立一种机制,使错误在造成系统故障之前就会被检测出来，并能被清除或得到补偿。
错误预防
– 保证所实现的系统不包含任何错误
– 错误回避,保证系统不会带入错误的技术（详细的设计方法学和质量控制）
– 错误清除,清查那些在使用了错误回避技术路线后还残留在系统中的错误，并清除它们（需要大量的测试和证实过程）
2.2 基本容错方法和技术
2 分布式数据库系统的故障原因和容错技术
故障检测
– 潜伏的故障,故障发生一段时间后才被检测出来
– 错误潜伏期,从故障发生到被检测出来的时间
– 平均检测时间 (MTTD)：平均错误潜伏时间
– 平均修复时间 (MTTR)：修复一个失败的系统所需要的期望时间
– 平均故障间隔时间 (MTBF)：在可以自我修复的系统中相继的失败之间的期望时间,由经验或从可靠性函数计算
2.2 基本容错方法和技术
2 分布式数据库系统的故障原因和容错技术
MTBF
MTTD MTTR
在这段时间内，
可能发生多起错误故障发生造成错误检测到错误 修复故障发生造成错误时间相继发生的事件
2.2 基本容错方法和技术
2 分布式数据库系统的故障原因和容错技术
冗余
– 所有容错系统设计中都采用的基本原则是在系统的组件中提供冗余
模块化
– 系统的每个组件都设计为具有定义很好的输入 /输出接口的模块
– 模块化可以把故障隔离在单一的组件中
系统实现
– 故障 -停止模块（ fail-stop module)
– 进程对（ Process pairs)
2.2 基本容错方法和技术
2 分布式数据库系统的故障原因和容错技术
time
正常 停止 恢复 正常易失存储丢失 稳定存储 ok
故障 -停止模块
– 不断地对自身进行检测，当检测到一个故障时，就自动停止。
– 优点是缩短了故障检测的潜伏期。
2.2 基本容错方法和技术
2 分布式数据库系统的故障原因和容错技术
进程对（ Process pairs)
– 通过 软件模块的双工来实现容错。两个进程,一个是主进程，一个是备份，它们同时提供同样的服务，主进程与备份进程都是基于故障 -停止模块实现。
– 分类方式（根据主进程和备份进程之间的通信方式）
锁定 -步进方式
自动检查点设置方式
状态检查点设置方式
Delta检查点设置方式
持久进程对
2.2 基本容错方法和技术
2 分布式数据库系统的故障原因和容错技术
事务故障
系统故障
介质故障
通信故障
3.1 分布式数据库系统故障
3 分布式数据库的可靠性协议站点故障
局部恢复管理器 (LRM)
– 每个站点一个
– 维护局部事务的原子性和持久性
体系结构
– 数据库存储在稳定存储器中
– 存储和访问稳定数据库的单位是页面
– 缓冲区中的数据库称作易失数据库
– LRM仅仅在易失数据库上执行事务操作
– 对数据库的访问都要经由数据库缓冲区管理器
– Flush(冲洗 ) 实现将数据库缓冲区页对稳定 DB的强迫写
3.2 局部可靠性协议
3 分布式数据库的可靠性协议数据库缓冲区
(易变数据库 )
局部恢复管理器数据库缓冲区管理器主存取出,
冲洗读 /写稳定
DB
读 /写
LRM与缓冲区管理器的接口
3.2 局部可靠性协议
3 分布式数据库的可靠性协议
恢复信息
– Log
– Undo
– Redo
旧的稳定
DB状态新的稳定
DB状态Redo
数据库 Log
新的稳定
DB状态旧的稳定
DB状态Undo
数据库 Log
3.2 局部可靠性协议
3 分布式数据库的可靠性协议
目的
– 保证在 DB上执行的事务的原子性和持久性。
– 协议描述了原语的执行过程
命令执行过程
– Begin-Transacrion,登录
– Read,LRM先在 Trans的缓冲区中读，若不在，则向缓冲区管理器发 Fetch命令，读出数据后,LRM将它交给调度程序
– Write,若在 Buffer中得到，则在那更新，否则对 Buffer
Manager发 Fetch命令，读出数据并修改，同时数据的前像和修改后的后像写入 Log
– Abort,通过 Log做 Undo
– Commit,将事务结束记录入 Log项
3.2 局部可靠性协议
3 分布式数据库的可靠性协议
目的
– 维持在多个数据库上执行的事务的原子性和持久性
原语
– Begin_Transaction
– read,write,
– Abort,commit
命令执行与局部协议类似
3.3 分布式可靠性协议
3 分布式数据库的可靠性协议
可靠性协议组成
– 包括提交、终结、恢复协议
– 提交和恢复协议详细说明提交命令和恢复命令是如何执行的
– 终结协议是分布式系统特有的协议。在执行一个分布式事务时，若一个 Site故障，希望其它 Site也停止该事务。处理这种情况的技术就称为终止协议。
3.3 分布式可靠性协议
3 分布式数据库的可靠性协议
终结协议与恢复协议的比较
– 假若一个 Site失效
终结协议确定了未失效 Site如何处理该失效事件
恢复协议确定失效 Site重启动后，进程（协调者，参与者）恢复它的状态的过程
– 网络分割时
终结协议采取必要的措施来终结在不同网络区间执行的活动事务
当网络重新连接后，恢复协议保证使各个冗余 DB相互一致
3.3 分布式可靠性协议
3 分布式数据库的可靠性协议
两阶段提交协议的要点
– 允许参与者单方面撤销事务，直到做出肯定性的建议
– 一旦参与者确定了提交或者撤销提议，它不能再更改
– 当参与者处于就绪状态，它可根据协调者发出的消息的种类，转换为相应的提交或者撤销状态
– 协调者依据全局提交规则作出全局终结决定
– 在发生故障的情况下，协调者和参与者可能会进入互相等待的状态，一般采用定时器来解决这种问题
3.4 两阶段提交协议的演变
3 分布式数据库的可靠性协议协调者 参与者
PREPARE
PREPARED
COMMIT
ACK
2PC-提交协调者参与者
PREPARE
NO
ABORT
ACK
2PC-夭折集中式 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*
标记,输入消息输出消息
* = 每一个
3.4 两阶段提交协议的演变
3 分布式数据库的可靠性协议
当参与者进入,R”状态,
– 它必定已获得所有资源
– 它只能根据协调者指令提交或夭折
当所有参与者是在,R”时,协调者才能进入,C” 状态,即,它一定 最终 能提交
3.4 两阶段提交协议的演变
3 分布式数据库的可靠性协议
假定撤销 2PC和假定提交 2PC协议
– 目的是改善 2PC的性能
– 假定撤销协议中，协调者不必等待参与者的
ACK消息，减少了协调者与参与者之间传递消息的数量
– 假定提交协议中，可以不将 Prepare写入 Log，
减少了 Log写入的次数
3.4 两阶段提交协议的演变
3 分布式数据库的可靠性协议
事务阻断：某个 Site上本来可以终结（提交或撤销）的子事务，由于 DDBS故障，
必须 等待到故障恢复（ 其占有的资源不释放）
阻断协议：提交协议称为阻断协议是指发生某类故障时,使分布式事务可能处于阻断状态
终结协议,允许事务在有故障情况下仍能正确结束
3.5 事务阻断与终结协议
3 分布式数据库的可靠性协议
判断 2PC协议是终结协议的条件
– 至少有一个 Site已收到结果命令（该 Site可以告知其它参与者关于该事务的结果，并由它们来终结该事务）
– 没有一个参与者收到命令，并且只有协调者
Site故障（此时，所有参与者站点都是可工作的，参与者可以选举一个 新的协调者,然后继续）
3.5 事务阻断与终结协议
3 分布式数据库的可靠性协议
终结协议在协调者和参与者的定时器超时时发挥作用
超时处理技术
– 协调者超时
在等待状态超时，可以决定“全局撤销”
在撤销状态超时，重发,G-abort”
在提交状态超时，重发,G-commit”
– 参与者超时（被阻断时出现）
在初始状态超时，单方面 Abort
在 Ready状态超时，被阻断，等待事务最终处理结果
3.6 2PC协议的终结协议
3 分布式数据库的可靠性协议协调者超时
I
W
C
A
F
commit-申请申请 -prepare*
ack*
-
ack*
-
_t_
abort
any
abort
any
commit
_t_
commit
_t_
abort*
no
abort*
prepared*
commit*
t=timeout
参与者超时
I
R
C
A
申请 -prepare
prepared
等价于结束状态
_t_
ping
申请 -prepare
no
commit
ack
abort
ack
commit
ack
abort
ack
设计终结协议
–假定 Pi是超时的参与者（询问 Pj），其它
Pj按如下响应
Pj处于初始状态，于是单方面 Abort，并回送
“建议 abort”给 Pi
Pj处于 Ready状态，此时不能帮助 Pi终结
Pj处于 Commit或 Abort状态，此时向 Pi发送
“建议提交”或“建议 Abort”
3.6 2PC协议的终结协议
3 分布式数据库的可靠性协议
–Pi超时，可能有的解释
Pi收到 Pj的“建议撤销”回答，此时 Pi夭折
Pi收到 Pj“建议撤销”回答，但是其它 Pj处于 Ready状态，此时 Pi仍然 Abort
Pi收到 Pj处于 Ready状态，此时没有一个参与者有足够的信息恰当地终结事务
Pi收到其他所有的 Pj”全局提交”或”全局夭折”消息,Pi可以根据消息终结
Pi收到某些 Pj的“全局提交”，而另一些
Pj处于 Ready状态,Pi可以提交
3.6 2PC协议的终结协议
3 分布式数据库的可靠性协议
协调者站点失效
– 协调者在初始状态失效
发生在协调者初始化提交过程之前
因此，它将在恢复时启动提交过程
– 协调者在等待状态失效
这时协调者已经发送了“准备”命令
恢复时，协调者将从头开始启动提交过程，再次发送“准备”
消息
– 协调者在提交状态或撤销状态失效
这时，协调者已经把它的决定通知了参与者，并终结了事务
在恢复时，如果它已经收到了所有的确认消息，就不需要做任何事情
否则，就要启动终结协议
3.7 2PC协议的恢复协议
3 分布式数据库的可靠性协议
参与者站点失效
– 一个参与者在初始状态失效
在恢复时，该参与者应该单方面撤销事务
– 一个参与者在就绪状态失效
这时协调者已经收到失效站点在失效前发送的肯定决定
恢复时，失效站点的参与者认为是在就绪状态发生了超时，于是启动终结协议来处理该事务
– 一个参与者在提交状态或撤销状态失效
这些状态表示了终结条件，所以在恢复时，参与者不需要采取任何专门的措施
附加情形（略）
3.7 2PC协议的恢复协议
3 分布式数据库的可靠性协议
提交协议 是非阻断的充要条件 是,在其状态转换图中不存在,
– 没有状态是即与提交又与撤销状态“相邻”
– 不存在不可提交状态是与提交状态“相邻”
相邻
– 从一个状态直接转换到另一个状态
3.8 三阶段提交协议
3 分布式数据库的可靠性协议
2PC中的状态
– C(提交 )状态是可提交状态,其它为不可提交状态
Ready 状态是不可提交状态
Wait状态是不可提交状态
– 它们都侵犯了非阻断协议的充要条件,从而考虑改变 2PC,使其满足非阻断协议条件
在 Wait 和 Commit 之间,或者在 Ready和
Commit之间加入另一种状态作为缓冲状态,从而有了 3PC协议
3.8 三阶段提交协议
3 分布式数据库的可靠性协议
I
W
A
C
commit
prepare
vote-abort
global-abort
vote-commit
prepare-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) 参与者协调者 参与者
PREPARE
PREPARED
COMMIT
DONE
PRECOMMIT
ACK
协调者 参与者
PREPARE
NO
ABORT
DONE
协调者 参与者开始 -3PC 记录写 Log
(参与者列表 )
commit记录写 Log
(状态 C)
prepared记录写 Log
(状态 W)
committed 记录写 Log
(状态 C)
PREPARE
PREPARED
COMMIT
PRECOMMIT
ACK
协调者 参与者初始写 begin_commit到日志等待有要求撤消的？
写 Prepare-to-
commit到日志准备提交写 end_of_trans.到日志初始准备提交？
写 ready到日志就绪消息类型？
写 abort到日志 写 prepare-to-
commit到日志准备提交撤消撤消写 abort到日志写 abort到日志准备撤消提交全局撤消准备提交
ACK
ACK
no
no
abort
Prepare
-to-
commit
写 commit到日志提交提交在中事务执行的过程写 commit到日志撤消提交准备提交
3PC
协调者
– 在 Wait状态超时：与 2PC中协调者在 Wait超时相同,协调者单方面 Abort
– 在 PC状态超时：此时协调者不知道未响应的参与者是否到达 PC,但是知道每个参与者至少在
Ready状态,因此协调者可以将所有参与者移入
PC状态
– 在 Commit/Abort状态超时 协调者不知参与者是否已执行命令,但是对 Commit而言,知道参与者至少在 PC状态。因此，协调者不需要做专门的处理
3.9 三阶段提交协议的超时处理
3 分布式数据库的可靠性协议
参与者超时
– 在 Initial状态超时：与 2PC中的情况相同
– 在 Ready状态超时：参与者准备 Commit,由于与协调者的通信丢失,终结协议将选举一个新的协调者，新协调者根据下面所述终结协议终结事务
– 在 PC状态超时：参与者已收到,Prepare-to-
commit”,正在等待来自协调者的“全局提交”
消息,处理同第二条。
3.9 三阶段提交协议的超时处理
3 分布式数据库的可靠性协议协调者 参与者
PREPARE
PREPARED
COMMIT
PRECOMMIT
ACK
1,超时,Abort
3,超时,忽略
1,超时,abort
2,超时,终结协议
3.超时,终结协议
2,超时,把参与者移入 PC
竞选新的协调者
– 使用竞选协议
新协调者送出 REQUEST状态给参与者
使用终结规则做出决定
与参与者通信
3.10 三阶段提交协议的终结协议
3 分布式数据库的可靠性协议竞选协议
进程全序
– 协调者 = 0,参与者 1,…,n
任何时候,选择,最小的” 工作进程为协调者
3.10 三阶段提交协议的终结协议
3 分布式数据库的可靠性协议
终结规则
– 新协调者在 Wait状态：将全局 Abort,此时参与者可以在任何状态,若参与者是在 PC状态,
即它是期望有,G-Commit”,但是得到了
,G-Abort”,3PC中缺少从 PC到 Abort的转换,
这对终结协议很有用,
– 新协调者在 PC状态：此时没有参与者是在
Abort状态,协调者可以全局提交,发送,G-
Commit”命令,
– 新协调者在 Abort状态：收到第一个消息后，
所有参与者进入 Abort状态
3.10 三阶段提交协议的终结协议
3 分布式数据库的可靠性协议
3PC与 2PC恢复协议的差别很小
– 协调者在 Wait状态故障,按照终结协议，参与者已终结事务,因此,协调者在恢复时必须查询以决定事务的命运
– 协调者在 PC状态故障,终结协议已使工作的参与者终结,因此,协调者需询问
– 一个参与者在 PC状态故障,必须询问以确定其它参与者如何终结事务
3.11 三阶段提交协议的恢复协议
3 分布式数据库的可靠性协议
网络分割是由通信线路故障引起的
– 简单分割，仅仅是网络分裂成两部分
– 多重分割，更复杂
网络分割非阻断协议的存在性
– 即在发生网络分割时,是否存在允许独立恢复的协议
– 独立恢复是指站点重启动时,无需远程访问
若存在处理分割的非阻断协议,那么,该协议可使某个分割中的站点到达终结决定,而且这个决定与另一分割中的决定一致
一般结论
– 独立恢复协议只存在于单站点故障的情形
– 若发生网络分割的时候,丢了报文的话,则不存在任何非阻断的协议能从网络分割故障中恢复
4.1 网络分割概述
4 网络分割与提交协议
非冗余数据库
– 任何需要访问存储在另一网络区域里的数据项的新事务都被阻断,等待网络修复
– 位于同一区域里的数据项的并发访问由并发控制算法处理
– 网络分割时由 提交协议 处理
冗余数据库
– 分割时,副本可能位于不同的区域
– 由 复制协议 处理
4.1 网络分割概述
4 网络分割与提交协议
网络分割处理策略
– 一致性与可用性的选择
– 非冗余数据库处理网络分割的终结协议
集中式协议，基于集中式并发控制算法 (主站点法和主副本法 )
基于表决的协议
– 冗余数据库处理网络分割的终结协议
复制控制协议
4.1 网络分割概述
4 网络分割与提交协议
多数法和基于法定人数法
– 在事务中止或提交前,大多数站点必须一致同意中止或提交
– 基于法定人数的规则
每个站点 i有选票数 Vi,Vi是正整数
V=? Vi
事务在提交前，它必须获得提交法定票数 Vc
事务在 Abort前，它必须获得 Abort法定票数 Va
Va+Vc≤V,当 0 ≤Va,Vc ≤V
n
i=1
4.2 基于表决的协议
4 网络分割与提交协议
网络分割时,在每个分割部分选择一个新的协调者
3PC中加入 PA状态,从而不允许从 Wait /Ready到
Abort 状态的转换
原因
– 有多个协调者阻止事务终结,不允许多个协调者得出不同的结论,因此希望协调者获得撤销的决定
– 如果新协调者故障,它不知道是否达到提交或撤销的法定票数,这样参与者必须明确做出提交或撤销的决定
– Ready(或 Wait)都不满足该需求,预示引入另一个状态 Pre-
Abort,该状态在 Ready和 Abort之间
4.2 基于表决的协议
4 网络分割与提交协议
I
W
A C
commit
prepare
vote-abort
global-abort
vote-commit
prepare-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) 参与者
PA
ready-to-abort
global-abort
PA
ready-to-abort
global-abort
基于法定人数的 3PC集中式协议
– 选择一个新的协调者
– 协调者收集状态信息,并按如下规则执行
1) 若至少一个站点已 Commit(Abort),则协调者对其它站点发送 Commit(Abort)命令
2) 若处于 PC状态站点的票数 >=Vc,则发送 Commit
3) 若 PA状态站点的票数 >=Va,则发送 Abort
4) 若 PC状态站点的票数 +Ready状态站点的票数 >=Vc,则发送
PC命令给不确定站点,等待 2)状态出现
5) 若 PA状态站点的票数 +Ready状态站点的票数 >=Va,则发送
PA命令给不确定站点,等待 3)状态出现
6) 否则,等待故障修复
4.2 基于表决的协议
4 网络分割与提交协议
数据复制的目的
– 高吞吐量
– 较好的响应时间
– 高可用性
复制作为可选择的提交协议
– 数据在多站点独立更新,使用“惰性复制协议”减少数据不一致问题,
4.3 复制控制协议
4 网络分割与提交协议
基本方法：
– 每个副本看作一个独立的数据项
X1 X2 X3
Lock
mgr X3
Lock
mgr X2
Lock
mgr X1
Txi Txj Txk
对象 X 有副本 X1,X2,X3
4.3 复制控制协议
4 网络分割与提交协议
Read(X):
– 获取 X1 共享锁
– 获取 X2 共享锁
– 获取 X3 共享锁
– 分别读 X1,X2,X3
– 事务结束时,释放 X1,X2,X3 锁
X1
lock
mgr
X3
lock
mgr
X2
lock
mgr
read
Write(X):
– 获取 X1 互斥锁
– 获取 X2 互斥锁
– 获取 X3 互斥锁
– 写新值到 X1,X2,X3
– 事务结束时,释放 X1,X2,X3 锁
X1 X3X2
lock locklock
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
UPDOWN (状态 )
网络上站点的状态站点 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)
修复后,可以看出 x3未曾修改
5.3 不一致性的检测
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.4 不一致性的解决方法
5 不一致性检测和解决方法
在分布式数据库中，冷启动是比较罕见的
一般来说，当网络中的一个站点丢失了运行记录信息之后，就要求冷启动
分布式数据库冷启动中,一个站点要建立一早期状态,那么所有其它站点也必须建立起与该站点一致的早期状态,这意味着此恢复过程本质上是全局的,要影响到数据库的全部站点,虽然引起冷启动的故障一般讲是本地的,
以前的一致性状态是由检查点来标志的
5.5 检查点和冷启动
5 不一致性检测和解决方法
一致的全局状态 C的两个特征
– 对于每个事务 T,C包含了 T在任何站点的全部事务所执行的更新,或者它不包含它们中的任何一个。
– 如果一事务 T被包含在 C中,则按串行化次序,在 T前面的全部冲突事务也包含在 C中
重构全局一致状态的最简单办法是使用
– 本地转储
– 本地的运行纪录
– 全局的检查点
5.5 检查点和冷启动
5 不一致性检测和解决方法
如果有全局检查点,则重构就相对容易,
– 首先在故障站点处决定认为是安全的最近的一个本地检查点,这就确定了必须重构的较早的全局状态
– 然后请求所有其它站点重新建立相对应的本地检查点的本地状态
存在的问题
– 只有一个站点把一“写检查点”报文广播给所有其它站点是不够的,因为可能出现如下页图所述的情况
5.5 检查点和冷启动
5 不一致性检测和解决方法站点 1
站点 2
站点 3
C1 时间
T2
C2
C3T3
R C
其中,T2和 T3是事务 T的子事务,T3是两阶段提交的协调者。
C1,C2和 C3 是本地检查点 (从站点 1开始 )
写检查点报文两阶段提交的报文 (R=READY,C=COMMIT)
全局检查点的同步问题
避免上述问题的简单办法是,要求在每个站点记录其本地检查点之前,使所有站点变成不活跃的,
全部站点必须同时停留在不活跃状态,需要进行协调,使用与 2PC类似的协议
– 由一协调者把“预备检查点”广播给所有站点
– 每个站点就终结了的事务的执行然后回答 Ready
– 于是该协调者再广播“执行检查点”
5.5 检查点和冷启动
5 不一致性检测和解决方法
更高效的方法有：
– 松散同步检查点：由一个协调者来要求所有站点记录一全局检查点,但是它们可在一较大的时间间隔内自由地执行之,保证同一事务的全部子事务都包含在相应于同一全局检查点的本地检查点的责任交事务管理器承担
– 为了完全避免建立全局检查点，让恢复过程在冷启动时承担重构一致的全局状态的任务。每个站点独立于其它站点记录其本地检查点,所以建立一致全局状态由冷启动过程实现
– 改进 2PC,使属于两个分布事务 T和 T’的所有子事务的检查点在执行这两个事务的所有站点中都以同样的次序记录
5.5 检查点和冷启动
5 不一致性检测和解决方法总 结
分布式数据库可靠性的概念
分布式数据库系统故障原因和容错技术
分布式数据库的可靠性协议
网络分割与提交协议
不一致性的检测和解决方法
（ mycui369@126.com)
计算机应用技术 2007级研究生
1,分布式数据库的可靠性的概念及其度量
2.分布式数据库系统的故障原因和容错技术
3.分布式数据库的可靠性协议
4.网络分割和提交协议
5.不一致性监测和解决方法分布式数据库中的可靠性第 6章
可靠性
– 指数据库在一给定时间间隔内不产生任何失败的概率。
– 它强调数据库的正确性，要求数据库正确运行，既符合某种规格化要求。
– 通常用来描述不可修复的系统。
可用性
– 强调的是当需要访问数据库时，它是可用的。
– 指在给定的时间点系统可以正常运行的概率。
– 通常用于描述那些可以修复的系统。
两者关系
– 通常认为构建可用性的系统比可靠性的系统容易
– 两者是统一的，可靠性高的系统可用性自然是好的
– 两者又是矛盾的，增加错误风险的情况下，可提高可用性 ;采用太谨慎的策略会降低可用性
1.1 分布式数据库可靠性概念
1 分布式数据库可靠性概念及其度量例,Site1 Site2
x1 x2
Lock x1 Lock x2
2PC Ready
故障出现
Site1也 Ready
故 Commit
Site 2 等待此时 Site 2有两种可能,
a> 以正确性为标准,x2则等待,并 Lock 2,直到故障恢复。提高了可靠性，但牺牲了可用性。
b> 引入不一致性的风险下,
尽量 提高可用性,解锁 x2,
其它事务可以使用它的值。
Site 1 正常结束
1.1 分布式数据库可靠性概念
1 分布式数据库可靠性概念及其度量已知
x1和 x2是 x的副本
事务 T是更新 x的事务
Site 1是协调站点
Site 1是事务 T原发站点
遵守两阶段提交协议
平均故障间隔时间
– 指在可以自我修复的系统中相继失败之间的期望时间
– 通过可靠性函数来计算 MTBF=∫0∞R(t)dt
– MTBF与系统失败的概率有直接的关系
平均修复时间
– 是指修复一个系统所需要的期望时间,MTTR
– 它与失败概率有关
指数型失败和修复的概率的系统可用性
– A=MTBF/(MTBF+MTTR)
可用性系统
– 5个 9（ 99.999%）常用来描述可用性系统
– 但是可用性系统要求的成本比较高
– 具体设计时要综合用户两方面的要求
1.2 平均故障间隔时间和平均修复时间
1 分布式数据库可靠性概念及其度量
系统 （ System） 是由一组组件构成的一种机制，这些组件通过响应来自某个环境的具有可识别行为模式的刺激而相互作用。
component1 component2
component3
环境系统刺激 响应
系统规范说明 （ Specification） 系统提供的对所有可能的刺激将产生的响应行为必须遵循的说明
2.1 系统失败的原因
2 分布式数据库系统的故障原因和容错技术
故障
– 任何偏离规范说明的行为
软故障和硬故障
– 软故障包括间歇性（ intermittent）和瞬变性
（ transient）故障，通过重启动来修复
– 硬故障指永久性故障,错误设计等
软件和硬件故障
2.1 系统失败的原因
2 分布式数据库系统的故障原因和容错技术
软故障 占 90%以上并且该比例稳定
– 67年,美空军指出计算机中电子故障 80%是间歇性的
– 67年,IBM 指出 90%故障是间歇性的
– 80年，研究指出软故障明显高于硬故障
– 87年,Gray指出 大部分软件故障是瞬变性故障
2.1 系统失败的原因
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,曾有报告指出,1000条指令中,0.25-10
个 BUG
2.1 系统失败的原因
2 分布式数据库系统的故障原因和容错技术永久性故障错误的设计不稳定或者临界的组件不稳定的外部环境操作者的过失系统失败永久性错误间歇性错误瞬变的错误系统失败的原因
容错
– 设计一种使系统识别出可能会发生的错误的方法。
在系统中建立一种机制,使错误在造成系统故障之前就会被检测出来，并能被清除或得到补偿。
错误预防
– 保证所实现的系统不包含任何错误
– 错误回避,保证系统不会带入错误的技术（详细的设计方法学和质量控制）
– 错误清除,清查那些在使用了错误回避技术路线后还残留在系统中的错误，并清除它们（需要大量的测试和证实过程）
2.2 基本容错方法和技术
2 分布式数据库系统的故障原因和容错技术
故障检测
– 潜伏的故障,故障发生一段时间后才被检测出来
– 错误潜伏期,从故障发生到被检测出来的时间
– 平均检测时间 (MTTD)：平均错误潜伏时间
– 平均修复时间 (MTTR)：修复一个失败的系统所需要的期望时间
– 平均故障间隔时间 (MTBF)：在可以自我修复的系统中相继的失败之间的期望时间,由经验或从可靠性函数计算
2.2 基本容错方法和技术
2 分布式数据库系统的故障原因和容错技术
MTBF
MTTD MTTR
在这段时间内，
可能发生多起错误故障发生造成错误检测到错误 修复故障发生造成错误时间相继发生的事件
2.2 基本容错方法和技术
2 分布式数据库系统的故障原因和容错技术
冗余
– 所有容错系统设计中都采用的基本原则是在系统的组件中提供冗余
模块化
– 系统的每个组件都设计为具有定义很好的输入 /输出接口的模块
– 模块化可以把故障隔离在单一的组件中
系统实现
– 故障 -停止模块（ fail-stop module)
– 进程对（ Process pairs)
2.2 基本容错方法和技术
2 分布式数据库系统的故障原因和容错技术
time
正常 停止 恢复 正常易失存储丢失 稳定存储 ok
故障 -停止模块
– 不断地对自身进行检测，当检测到一个故障时，就自动停止。
– 优点是缩短了故障检测的潜伏期。
2.2 基本容错方法和技术
2 分布式数据库系统的故障原因和容错技术
进程对（ Process pairs)
– 通过 软件模块的双工来实现容错。两个进程,一个是主进程，一个是备份，它们同时提供同样的服务，主进程与备份进程都是基于故障 -停止模块实现。
– 分类方式（根据主进程和备份进程之间的通信方式）
锁定 -步进方式
自动检查点设置方式
状态检查点设置方式
Delta检查点设置方式
持久进程对
2.2 基本容错方法和技术
2 分布式数据库系统的故障原因和容错技术
事务故障
系统故障
介质故障
通信故障
3.1 分布式数据库系统故障
3 分布式数据库的可靠性协议站点故障
局部恢复管理器 (LRM)
– 每个站点一个
– 维护局部事务的原子性和持久性
体系结构
– 数据库存储在稳定存储器中
– 存储和访问稳定数据库的单位是页面
– 缓冲区中的数据库称作易失数据库
– LRM仅仅在易失数据库上执行事务操作
– 对数据库的访问都要经由数据库缓冲区管理器
– Flush(冲洗 ) 实现将数据库缓冲区页对稳定 DB的强迫写
3.2 局部可靠性协议
3 分布式数据库的可靠性协议数据库缓冲区
(易变数据库 )
局部恢复管理器数据库缓冲区管理器主存取出,
冲洗读 /写稳定
DB
读 /写
LRM与缓冲区管理器的接口
3.2 局部可靠性协议
3 分布式数据库的可靠性协议
恢复信息
– Log
– Undo
– Redo
旧的稳定
DB状态新的稳定
DB状态Redo
数据库 Log
新的稳定
DB状态旧的稳定
DB状态Undo
数据库 Log
3.2 局部可靠性协议
3 分布式数据库的可靠性协议
目的
– 保证在 DB上执行的事务的原子性和持久性。
– 协议描述了原语的执行过程
命令执行过程
– Begin-Transacrion,登录
– Read,LRM先在 Trans的缓冲区中读，若不在，则向缓冲区管理器发 Fetch命令，读出数据后,LRM将它交给调度程序
– Write,若在 Buffer中得到，则在那更新，否则对 Buffer
Manager发 Fetch命令，读出数据并修改，同时数据的前像和修改后的后像写入 Log
– Abort,通过 Log做 Undo
– Commit,将事务结束记录入 Log项
3.2 局部可靠性协议
3 分布式数据库的可靠性协议
目的
– 维持在多个数据库上执行的事务的原子性和持久性
原语
– Begin_Transaction
– read,write,
– Abort,commit
命令执行与局部协议类似
3.3 分布式可靠性协议
3 分布式数据库的可靠性协议
可靠性协议组成
– 包括提交、终结、恢复协议
– 提交和恢复协议详细说明提交命令和恢复命令是如何执行的
– 终结协议是分布式系统特有的协议。在执行一个分布式事务时，若一个 Site故障，希望其它 Site也停止该事务。处理这种情况的技术就称为终止协议。
3.3 分布式可靠性协议
3 分布式数据库的可靠性协议
终结协议与恢复协议的比较
– 假若一个 Site失效
终结协议确定了未失效 Site如何处理该失效事件
恢复协议确定失效 Site重启动后，进程（协调者，参与者）恢复它的状态的过程
– 网络分割时
终结协议采取必要的措施来终结在不同网络区间执行的活动事务
当网络重新连接后，恢复协议保证使各个冗余 DB相互一致
3.3 分布式可靠性协议
3 分布式数据库的可靠性协议
两阶段提交协议的要点
– 允许参与者单方面撤销事务，直到做出肯定性的建议
– 一旦参与者确定了提交或者撤销提议，它不能再更改
– 当参与者处于就绪状态，它可根据协调者发出的消息的种类，转换为相应的提交或者撤销状态
– 协调者依据全局提交规则作出全局终结决定
– 在发生故障的情况下，协调者和参与者可能会进入互相等待的状态，一般采用定时器来解决这种问题
3.4 两阶段提交协议的演变
3 分布式数据库的可靠性协议协调者 参与者
PREPARE
PREPARED
COMMIT
ACK
2PC-提交协调者参与者
PREPARE
NO
ABORT
ACK
2PC-夭折集中式 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*
标记,输入消息输出消息
* = 每一个
3.4 两阶段提交协议的演变
3 分布式数据库的可靠性协议
当参与者进入,R”状态,
– 它必定已获得所有资源
– 它只能根据协调者指令提交或夭折
当所有参与者是在,R”时,协调者才能进入,C” 状态,即,它一定 最终 能提交
3.4 两阶段提交协议的演变
3 分布式数据库的可靠性协议
假定撤销 2PC和假定提交 2PC协议
– 目的是改善 2PC的性能
– 假定撤销协议中，协调者不必等待参与者的
ACK消息，减少了协调者与参与者之间传递消息的数量
– 假定提交协议中，可以不将 Prepare写入 Log，
减少了 Log写入的次数
3.4 两阶段提交协议的演变
3 分布式数据库的可靠性协议
事务阻断：某个 Site上本来可以终结（提交或撤销）的子事务，由于 DDBS故障，
必须 等待到故障恢复（ 其占有的资源不释放）
阻断协议：提交协议称为阻断协议是指发生某类故障时,使分布式事务可能处于阻断状态
终结协议,允许事务在有故障情况下仍能正确结束
3.5 事务阻断与终结协议
3 分布式数据库的可靠性协议
判断 2PC协议是终结协议的条件
– 至少有一个 Site已收到结果命令（该 Site可以告知其它参与者关于该事务的结果，并由它们来终结该事务）
– 没有一个参与者收到命令，并且只有协调者
Site故障（此时，所有参与者站点都是可工作的，参与者可以选举一个 新的协调者,然后继续）
3.5 事务阻断与终结协议
3 分布式数据库的可靠性协议
终结协议在协调者和参与者的定时器超时时发挥作用
超时处理技术
– 协调者超时
在等待状态超时，可以决定“全局撤销”
在撤销状态超时，重发,G-abort”
在提交状态超时，重发,G-commit”
– 参与者超时（被阻断时出现）
在初始状态超时，单方面 Abort
在 Ready状态超时，被阻断，等待事务最终处理结果
3.6 2PC协议的终结协议
3 分布式数据库的可靠性协议协调者超时
I
W
C
A
F
commit-申请申请 -prepare*
ack*
-
ack*
-
_t_
abort
any
abort
any
commit
_t_
commit
_t_
abort*
no
abort*
prepared*
commit*
t=timeout
参与者超时
I
R
C
A
申请 -prepare
prepared
等价于结束状态
_t_
ping
申请 -prepare
no
commit
ack
abort
ack
commit
ack
abort
ack
设计终结协议
–假定 Pi是超时的参与者（询问 Pj），其它
Pj按如下响应
Pj处于初始状态，于是单方面 Abort，并回送
“建议 abort”给 Pi
Pj处于 Ready状态，此时不能帮助 Pi终结
Pj处于 Commit或 Abort状态，此时向 Pi发送
“建议提交”或“建议 Abort”
3.6 2PC协议的终结协议
3 分布式数据库的可靠性协议
–Pi超时，可能有的解释
Pi收到 Pj的“建议撤销”回答，此时 Pi夭折
Pi收到 Pj“建议撤销”回答，但是其它 Pj处于 Ready状态，此时 Pi仍然 Abort
Pi收到 Pj处于 Ready状态，此时没有一个参与者有足够的信息恰当地终结事务
Pi收到其他所有的 Pj”全局提交”或”全局夭折”消息,Pi可以根据消息终结
Pi收到某些 Pj的“全局提交”，而另一些
Pj处于 Ready状态,Pi可以提交
3.6 2PC协议的终结协议
3 分布式数据库的可靠性协议
协调者站点失效
– 协调者在初始状态失效
发生在协调者初始化提交过程之前
因此，它将在恢复时启动提交过程
– 协调者在等待状态失效
这时协调者已经发送了“准备”命令
恢复时，协调者将从头开始启动提交过程，再次发送“准备”
消息
– 协调者在提交状态或撤销状态失效
这时，协调者已经把它的决定通知了参与者，并终结了事务
在恢复时，如果它已经收到了所有的确认消息，就不需要做任何事情
否则，就要启动终结协议
3.7 2PC协议的恢复协议
3 分布式数据库的可靠性协议
参与者站点失效
– 一个参与者在初始状态失效
在恢复时，该参与者应该单方面撤销事务
– 一个参与者在就绪状态失效
这时协调者已经收到失效站点在失效前发送的肯定决定
恢复时，失效站点的参与者认为是在就绪状态发生了超时，于是启动终结协议来处理该事务
– 一个参与者在提交状态或撤销状态失效
这些状态表示了终结条件，所以在恢复时，参与者不需要采取任何专门的措施
附加情形（略）
3.7 2PC协议的恢复协议
3 分布式数据库的可靠性协议
提交协议 是非阻断的充要条件 是,在其状态转换图中不存在,
– 没有状态是即与提交又与撤销状态“相邻”
– 不存在不可提交状态是与提交状态“相邻”
相邻
– 从一个状态直接转换到另一个状态
3.8 三阶段提交协议
3 分布式数据库的可靠性协议
2PC中的状态
– C(提交 )状态是可提交状态,其它为不可提交状态
Ready 状态是不可提交状态
Wait状态是不可提交状态
– 它们都侵犯了非阻断协议的充要条件,从而考虑改变 2PC,使其满足非阻断协议条件
在 Wait 和 Commit 之间,或者在 Ready和
Commit之间加入另一种状态作为缓冲状态,从而有了 3PC协议
3.8 三阶段提交协议
3 分布式数据库的可靠性协议
I
W
A
C
commit
prepare
vote-abort
global-abort
vote-commit
prepare-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) 参与者协调者 参与者
PREPARE
PREPARED
COMMIT
DONE
PRECOMMIT
ACK
协调者 参与者
PREPARE
NO
ABORT
DONE
协调者 参与者开始 -3PC 记录写 Log
(参与者列表 )
commit记录写 Log
(状态 C)
prepared记录写 Log
(状态 W)
committed 记录写 Log
(状态 C)
PREPARE
PREPARED
COMMIT
PRECOMMIT
ACK
协调者 参与者初始写 begin_commit到日志等待有要求撤消的？
写 Prepare-to-
commit到日志准备提交写 end_of_trans.到日志初始准备提交？
写 ready到日志就绪消息类型？
写 abort到日志 写 prepare-to-
commit到日志准备提交撤消撤消写 abort到日志写 abort到日志准备撤消提交全局撤消准备提交
ACK
ACK
no
no
abort
Prepare
-to-
commit
写 commit到日志提交提交在中事务执行的过程写 commit到日志撤消提交准备提交
3PC
协调者
– 在 Wait状态超时：与 2PC中协调者在 Wait超时相同,协调者单方面 Abort
– 在 PC状态超时：此时协调者不知道未响应的参与者是否到达 PC,但是知道每个参与者至少在
Ready状态,因此协调者可以将所有参与者移入
PC状态
– 在 Commit/Abort状态超时 协调者不知参与者是否已执行命令,但是对 Commit而言,知道参与者至少在 PC状态。因此，协调者不需要做专门的处理
3.9 三阶段提交协议的超时处理
3 分布式数据库的可靠性协议
参与者超时
– 在 Initial状态超时：与 2PC中的情况相同
– 在 Ready状态超时：参与者准备 Commit,由于与协调者的通信丢失,终结协议将选举一个新的协调者，新协调者根据下面所述终结协议终结事务
– 在 PC状态超时：参与者已收到,Prepare-to-
commit”,正在等待来自协调者的“全局提交”
消息,处理同第二条。
3.9 三阶段提交协议的超时处理
3 分布式数据库的可靠性协议协调者 参与者
PREPARE
PREPARED
COMMIT
PRECOMMIT
ACK
1,超时,Abort
3,超时,忽略
1,超时,abort
2,超时,终结协议
3.超时,终结协议
2,超时,把参与者移入 PC
竞选新的协调者
– 使用竞选协议
新协调者送出 REQUEST状态给参与者
使用终结规则做出决定
与参与者通信
3.10 三阶段提交协议的终结协议
3 分布式数据库的可靠性协议竞选协议
进程全序
– 协调者 = 0,参与者 1,…,n
任何时候,选择,最小的” 工作进程为协调者
3.10 三阶段提交协议的终结协议
3 分布式数据库的可靠性协议
终结规则
– 新协调者在 Wait状态：将全局 Abort,此时参与者可以在任何状态,若参与者是在 PC状态,
即它是期望有,G-Commit”,但是得到了
,G-Abort”,3PC中缺少从 PC到 Abort的转换,
这对终结协议很有用,
– 新协调者在 PC状态：此时没有参与者是在
Abort状态,协调者可以全局提交,发送,G-
Commit”命令,
– 新协调者在 Abort状态：收到第一个消息后，
所有参与者进入 Abort状态
3.10 三阶段提交协议的终结协议
3 分布式数据库的可靠性协议
3PC与 2PC恢复协议的差别很小
– 协调者在 Wait状态故障,按照终结协议，参与者已终结事务,因此,协调者在恢复时必须查询以决定事务的命运
– 协调者在 PC状态故障,终结协议已使工作的参与者终结,因此,协调者需询问
– 一个参与者在 PC状态故障,必须询问以确定其它参与者如何终结事务
3.11 三阶段提交协议的恢复协议
3 分布式数据库的可靠性协议
网络分割是由通信线路故障引起的
– 简单分割，仅仅是网络分裂成两部分
– 多重分割，更复杂
网络分割非阻断协议的存在性
– 即在发生网络分割时,是否存在允许独立恢复的协议
– 独立恢复是指站点重启动时,无需远程访问
若存在处理分割的非阻断协议,那么,该协议可使某个分割中的站点到达终结决定,而且这个决定与另一分割中的决定一致
一般结论
– 独立恢复协议只存在于单站点故障的情形
– 若发生网络分割的时候,丢了报文的话,则不存在任何非阻断的协议能从网络分割故障中恢复
4.1 网络分割概述
4 网络分割与提交协议
非冗余数据库
– 任何需要访问存储在另一网络区域里的数据项的新事务都被阻断,等待网络修复
– 位于同一区域里的数据项的并发访问由并发控制算法处理
– 网络分割时由 提交协议 处理
冗余数据库
– 分割时,副本可能位于不同的区域
– 由 复制协议 处理
4.1 网络分割概述
4 网络分割与提交协议
网络分割处理策略
– 一致性与可用性的选择
– 非冗余数据库处理网络分割的终结协议
集中式协议，基于集中式并发控制算法 (主站点法和主副本法 )
基于表决的协议
– 冗余数据库处理网络分割的终结协议
复制控制协议
4.1 网络分割概述
4 网络分割与提交协议
多数法和基于法定人数法
– 在事务中止或提交前,大多数站点必须一致同意中止或提交
– 基于法定人数的规则
每个站点 i有选票数 Vi,Vi是正整数
V=? Vi
事务在提交前，它必须获得提交法定票数 Vc
事务在 Abort前，它必须获得 Abort法定票数 Va
Va+Vc≤V,当 0 ≤Va,Vc ≤V
n
i=1
4.2 基于表决的协议
4 网络分割与提交协议
网络分割时,在每个分割部分选择一个新的协调者
3PC中加入 PA状态,从而不允许从 Wait /Ready到
Abort 状态的转换
原因
– 有多个协调者阻止事务终结,不允许多个协调者得出不同的结论,因此希望协调者获得撤销的决定
– 如果新协调者故障,它不知道是否达到提交或撤销的法定票数,这样参与者必须明确做出提交或撤销的决定
– Ready(或 Wait)都不满足该需求,预示引入另一个状态 Pre-
Abort,该状态在 Ready和 Abort之间
4.2 基于表决的协议
4 网络分割与提交协议
I
W
A C
commit
prepare
vote-abort
global-abort
vote-commit
prepare-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) 参与者
PA
ready-to-abort
global-abort
PA
ready-to-abort
global-abort
基于法定人数的 3PC集中式协议
– 选择一个新的协调者
– 协调者收集状态信息,并按如下规则执行
1) 若至少一个站点已 Commit(Abort),则协调者对其它站点发送 Commit(Abort)命令
2) 若处于 PC状态站点的票数 >=Vc,则发送 Commit
3) 若 PA状态站点的票数 >=Va,则发送 Abort
4) 若 PC状态站点的票数 +Ready状态站点的票数 >=Vc,则发送
PC命令给不确定站点,等待 2)状态出现
5) 若 PA状态站点的票数 +Ready状态站点的票数 >=Va,则发送
PA命令给不确定站点,等待 3)状态出现
6) 否则,等待故障修复
4.2 基于表决的协议
4 网络分割与提交协议
数据复制的目的
– 高吞吐量
– 较好的响应时间
– 高可用性
复制作为可选择的提交协议
– 数据在多站点独立更新,使用“惰性复制协议”减少数据不一致问题,
4.3 复制控制协议
4 网络分割与提交协议
基本方法：
– 每个副本看作一个独立的数据项
X1 X2 X3
Lock
mgr X3
Lock
mgr X2
Lock
mgr X1
Txi Txj Txk
对象 X 有副本 X1,X2,X3
4.3 复制控制协议
4 网络分割与提交协议
Read(X):
– 获取 X1 共享锁
– 获取 X2 共享锁
– 获取 X3 共享锁
– 分别读 X1,X2,X3
– 事务结束时,释放 X1,X2,X3 锁
X1
lock
mgr
X3
lock
mgr
X2
lock
mgr
read
Write(X):
– 获取 X1 互斥锁
– 获取 X2 互斥锁
– 获取 X3 互斥锁
– 写新值到 X1,X2,X3
– 事务结束时,释放 X1,X2,X3 锁
X1 X3X2
lock locklock
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
UPDOWN (状态 )
网络上站点的状态站点 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)
修复后,可以看出 x3未曾修改
5.3 不一致性的检测
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.4 不一致性的解决方法
5 不一致性检测和解决方法
在分布式数据库中，冷启动是比较罕见的
一般来说，当网络中的一个站点丢失了运行记录信息之后，就要求冷启动
分布式数据库冷启动中,一个站点要建立一早期状态,那么所有其它站点也必须建立起与该站点一致的早期状态,这意味着此恢复过程本质上是全局的,要影响到数据库的全部站点,虽然引起冷启动的故障一般讲是本地的,
以前的一致性状态是由检查点来标志的
5.5 检查点和冷启动
5 不一致性检测和解决方法
一致的全局状态 C的两个特征
– 对于每个事务 T,C包含了 T在任何站点的全部事务所执行的更新,或者它不包含它们中的任何一个。
– 如果一事务 T被包含在 C中,则按串行化次序,在 T前面的全部冲突事务也包含在 C中
重构全局一致状态的最简单办法是使用
– 本地转储
– 本地的运行纪录
– 全局的检查点
5.5 检查点和冷启动
5 不一致性检测和解决方法
如果有全局检查点,则重构就相对容易,
– 首先在故障站点处决定认为是安全的最近的一个本地检查点,这就确定了必须重构的较早的全局状态
– 然后请求所有其它站点重新建立相对应的本地检查点的本地状态
存在的问题
– 只有一个站点把一“写检查点”报文广播给所有其它站点是不够的,因为可能出现如下页图所述的情况
5.5 检查点和冷启动
5 不一致性检测和解决方法站点 1
站点 2
站点 3
C1 时间
T2
C2
C3T3
R C
其中,T2和 T3是事务 T的子事务,T3是两阶段提交的协调者。
C1,C2和 C3 是本地检查点 (从站点 1开始 )
写检查点报文两阶段提交的报文 (R=READY,C=COMMIT)
全局检查点的同步问题
避免上述问题的简单办法是,要求在每个站点记录其本地检查点之前,使所有站点变成不活跃的,
全部站点必须同时停留在不活跃状态,需要进行协调,使用与 2PC类似的协议
– 由一协调者把“预备检查点”广播给所有站点
– 每个站点就终结了的事务的执行然后回答 Ready
– 于是该协调者再广播“执行检查点”
5.5 检查点和冷启动
5 不一致性检测和解决方法
更高效的方法有：
– 松散同步检查点：由一个协调者来要求所有站点记录一全局检查点,但是它们可在一较大的时间间隔内自由地执行之,保证同一事务的全部子事务都包含在相应于同一全局检查点的本地检查点的责任交事务管理器承担
– 为了完全避免建立全局检查点，让恢复过程在冷启动时承担重构一致的全局状态的任务。每个站点独立于其它站点记录其本地检查点,所以建立一致全局状态由冷启动过程实现
– 改进 2PC,使属于两个分布事务 T和 T’的所有子事务的检查点在执行这两个事务的所有站点中都以同样的次序记录
5.5 检查点和冷启动
5 不一致性检测和解决方法总 结
分布式数据库可靠性的概念
分布式数据库系统故障原因和容错技术
分布式数据库的可靠性协议
网络分割与提交协议
不一致性的检测和解决方法
