Page 166 - 《软件学报》2021年第7期

2084 Journal of Software 软件学报 Vol.32, No.7, July 2021

局可矫正作业和全局一致作业的容错难度依次增加,并且能够支持高难度作业,如全局一致作业的容错机制往
往也能支持低难度作业,如自稳定作业.因此,可支持的最高难度作业类型成为衡量面向分布式图计算作业容错
机制质量的重要指标之一.

1.3 失效模型和容错框架
故障(fault)是软件或硬件中被激活缺陷的最低级别抽象,错误(error)是指故障导致的系统内部状态的改变
或丢失,失效(failure)则是指由于错误导致的系统行为与预期行为之间的偏差 [3840] .这三者的关系如图 5 所示.

Fig.5 Failure model
图 5 失效模型
具体而言,故障按照其发生的时机通常可以分为瞬时故障(transient fault)、间歇性故障(intermittent fault)和
永久性故障(permanent fault)这 3 类,其中,瞬时故障是由于某些影响系统运行的条件临时改变而导致的,如网络
波动、线程竞争等,故障只会导致当前任务失效,通常无需修改代码,当任务重新运行时,故障很可能不会再次发
生;间歇性故障则以不规则间隔随机发生,其极难诊断和永久解决,如由于温度波动而无法正常工作的硬盘会在
某个阶段又恢复正常;永久性故障在其软件缺陷未解决之前将一直存在,如代码的逻辑 bug 等.在面向分布式图
计算作业的容错中主要处理的是由瞬时故障引起的失效.
外部观察者观察到系统行为的偏差后,如未得到计算结果或得到了错误的计算结果之后,对系统失效原因
进行猜想假设.根据假设的失效原因的不同,从复杂到简单,失效可被分为拜占庭失效(Byzantine failure)、性能失
效(performance failure)、遗漏失效(omission failure)、崩溃失效(crash failure)和故障停止失效(fail-stop failure).
在分布式图计算中,拜占庭失效的原因可以是任意错误,包括节点内部状态出错、传输数据损坏或网络路由错
误等;性能失效的原因是集群中某计算节点 M i 未按时从其他节点收到所需消息;而遗漏失效的原因则是该节点
M i 根本未从其他节点收到所需的消息;崩溃失效则进一步简化,即该节点 M i 未从某个其他节点 M j 收到所需消
息的原因是后者 M j 崩溃了;而故障停止失效则是假设了当集群中节点 M j 崩溃时,其他节点均知道其崩溃了,它
强调了故障不会造成错误的系统状态改变,体现在两个方面:一是在节点 M j 崩溃前,故障的发生未导致其遗漏
须发送的消息或发送错误的消息;二是在节点 M j 崩溃后,其他节点未在缺少部分消息的情况下继续运算,从而
产生错误的作业状态.在故障停止失效中,系统只会丢失部分内部状态,而所有幸存的内部状态均是正确的.在
分布式图计算作业中,故障停止失效被进一步细分,从复杂到简单,可以分为级联失效(cascading failure)、多点失
效(multi-node failure)和单点失效(single-node failure).其中,单点失效是指同一时间只有一个节点崩溃了;多点
失效则是指同时存在多个节点崩溃;而级联失效则是指在对崩溃节点的状态进行恢复的过程中,集群中又有节
点崩溃了.容错机制的实现难度与失效的复杂度通常是正相关的,并且能够处理复杂失效的容错机制往往也能
够处理较简单的失效,因此,可处理的最复杂失效类型成为衡量面向分布式图计算作业容错机制质量的重要指
标之一.
面向分布式图计算作业的容错机制通常是针对预期的失效类型来设计相应的状态冗余方法和失效恢复方
法,通常包括 3 个组件:状态冗余、失效检测和失效恢复.图 6 展示了作业全局状态和容错组件间的相互作用.当
作业正常运行时,一方面,状态冗余组件对作业全局状态即正常状态进行冗余保存,生成冗余状态,并定期地对
其进行更新;另一方面,失效检测组件也定期地对作业的运行状态进行检测,当检测到失效发生时,作业全局状
态即成为失效状态.同时,失效恢复组件被启用.失效恢复组件利用失效状态和冗余状态对作业进行恢复,当恢