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

张程博 等:面向分布式图计算作业的容错技术研究综述 2085

复成功后,作业全局状态即成为正常状态.

Fig.6 Global states in distributed graph processing jobs and fault tolerant framework
图 6 分布式图计算作业全局状态和容错框架
值得注意的是,在分布式图计算中,由于作业运行时所产生的天然冗余和作业本身鲁棒性的不同,容错中的
状态冗余方法也多种多样,基本上可归为 3 类:检查点(checkpointing)、日志(logging)和复制(replication)方法,并
且,还有一些作业的容错甚至不进行状态冗余.因此,依据容错所采用的作业状态冗余方法的不同,面向分布式
图计算作业的容错可分为 4 类:(1) 基于检查点的容错;(2) 基于日志的容错;(3) 基于复制的容错;(4) 基于算法
补偿的容错.具体各类容错的状态冗余方法和相应的失效恢复方法将在第 4 节结合相关工作进一步加以论述.
此外,绝大多数面向分布式图计算作业的容错是针对故障停止失效的,在这种情况下,简单的心跳机制就能
对失效进行有效的检测,而极个别能够处理拜占庭失效的容错,其失效检测相对复杂,具体的将在第 4 节结合相
关工作进行介绍.
2 目标和挑战

本节首先介绍面向分布式图计算作业容错技术的三大优化目标——更低的容错成本、更高的失效恢复效
率和更好的容错质量,并分析了实现这 3 个优化目标所面临的难点和挑战,最后,提出基于成本、效率和质量这
3 个维度的面向分布式图计算作业的容错技术评估框架.
2.1 优化目标
如上所述,随着分布式图计算作业处理的图数据日益庞大、计算日益复杂,其对性能和可扩展性(scalability)
的追求日益迫切,但同时,分布式图计算作业面临的故障发生频率高、传播快、影响大等问题,对其性能和可扩
展性的提高也造成了巨大的威胁.为了缓解这一矛盾,更低的容错成本、更高的失效恢复效率和更好的容错质
量是面向分布式图计算作业的容错技术不懈的追求之一.而这 3 点优化目标则分别涉及到设计容错机制时需
要考虑的 3 个维度:成本、效率和质量.
(1) 成本是指容错机制的实现和启用对分布式图计算作业的实现和正常运行带来的负面影响,一般包括人
力成本和资源成本.人力成本通过实现分布式图计算作业容错时用户的参与度来衡量,对用户不透明的容错机
制往往比对用户透明的容错机制要消耗更多的人力成本;资源成本则通常是指容错机制在分布式图计算作业
正常运行时所消耗的 CPU、内存、网络带宽和磁盘 I/O 等计算机资源,这通常会给分布式图计算作业的正常运
行带来额外的性能开销,并常用因此增加的运行时间来衡量;
(2) 效率是指失效发生后容错机制对作业运行的正面影响,包括失效恢复(failure recovery)阶段和后恢复
(post recovery)运行阶段,通常使用失效恢复时间和后恢复运行时间来衡量容错机制的效率.值得一提的是,在相
当多的支持全局一致作业的容错工作中,将失效恢复看作是从故障状态 s e 恢复至失效前最新状态 s la 而非其他
任一全局一致状态的过程,并且,由于失效前最新状态 s la 至最终状态 s a 的运行时间在发生失效的情况和正常
(failure-free)情况下相同,故直接使用失效恢复时间来衡量容错机制的效率;
(3) 质量则是指面向分布式图计算作业的容错机制的容错能力.如上一节所述,可支持的作业类型和可处
理的失效类型分别是衡量容错机制容错质量的两个重要指标.其中,可处理的失效类型越复杂,可支持的作业类