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

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

面能够通过更细粒度的状态冗余管理实现更低的容错成本、更高的容错效率和更好的容错质量,另一方面能够
通过结合不同作业的容错需求在容错的成本、效率和质量之间实现更灵活而准确的权衡和取舍.
因此,面向分布式图计算作业的容错技术是目前分布式图计算容错的主流技术.

4 面向分布式图计算作业的容错技术

如前面第 1.3 节所述,根据容错所采用的作业状态冗余方法,面向分布式图计算作业的容错可分为 4 类.
(1) 基于检查点的容错;(2) 基于日志的容错;(3) 基于复制的容错;(4) 基于算法补偿的容错.大体来讲,基于检
查点的容错应用得最为广泛,可以应用于基于同步和异步调度的图计算作业,并实现较高的容错质量;而基于日
志和复制的容错仅能应用于基于同步调度机制的作业.其中,基于日志的容错和基于检查点的容错通常是正交
的,前者通常可以作为后者的重要补充,从而提高整体的恢复效率,例如 Spark 中的容错就组合使用了基于检查
点的容错机制和基于日志的容错机制——在 lineage 过长时通过检查点制作快照以缩短 lineage 的长度,减少重
播,加速失效恢复效率.而基于复制的容错机制能够在容错效率方面实现更快的失效恢复,或者能够在容错质量
方面处理更复杂的失效类型,如拜占庭失效等.在这种情境下,基于复制的容错机制是基于检查点容错的良好替
代;此外,基于算法补偿的容错则依据补偿算法的不同可以应用在基于同步或异步调度的作业中,能够在容忍一
定容错质量损失的情况下,实现容错质量方面的零性能开销和容错效率方面的快速恢复.该技术相比前 3 类容
错技术有着极大的优势,但其适用范围相对较小,仅能用于某些特定类型的作业,并且要求用户对作业有深入的
理解.本节将结合具体的工作介绍在实现具体的容错机制时如何充分利用分布式图计算框架的功能结构和图
计算作业的运行特点,并通过 3 个维度、6 个指标的评价体系分析各个容错机制在成本、效率和质量方面的侧
重和取舍.
4.1 基于检查点的容错

检查点是指在程序运行特定位置保存用于故障恢复的必要状态信息的过程 [46] .在面向分布式图计算作业
容错机制中,根据保存快照一致性的不同,基于检查点的容错可以分为全局一致检查点容错和局部一致检查点
容错.其中,前者应用得最为广泛,同时也成为后续大多数研究工作进行比较和优化的基准.在同步调度机制中,
如图 9 所示,全局一致检查点容错的基本思路是在作业正常运行时,按照预先指定的超步间隔,保存系统全局一
致快照到可靠存储中,包括顶点/边值、消息等;而在失效恢复时,重启或新启的节点加载失效节点的图拓扑结构
和最新的快照数据,幸存节点也回滚并加载相应的全局一致快照,使得作业恢复至从最近保存的全局一致状态
开始运行,以避免作业从头重新运行.

Fig.9 An example of fault tolerance based on global consistency checkpointing
图 9 全局一致检查点容错