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

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

实现零性能开销和快速恢复,但仅能支持有限的具有特殊性质的作业 [36,37] ;如图 7(c)中重叠区域所示,能够处理
更复杂的失效类型(高质量)并能提供更高恢复效率(高效率)的容错机制也会消耗更多的资源(高成本).例
如,被动复制机制仅能处理崩溃失效,而采用 3f+1 副本的主动复制机制则能一定程度地处理拜占庭失
效 [42] .
以上性质在不同的容错工作中会反复体现,因此,本文在对一个面向分布式图计算作业的容错机制进行评
估时,综合考量了成本、效率和质量这 3 个维度,同时,相应的有 6 个衡量指标:作业性能开销、用户透明度、失
效恢复时间、后恢复运行时间、可支持的最难作业类型、可处理的最复杂失效类型.
3 发展脉络

分布式图计算的容错实现方式与其计算逻辑的实现方式息息相关,随着分布式计算框架的发展,分布式图
计算的容错实现方式也随之发生变化,先后可以分为 3 个阶段,分别是面向专用计算作业的容错、面向通用大
数据处理作业的容错和面向分布式图计算作业的容错,如图 8 所示.

Fig.8 Development of fault tolerance in distributed graph processing
图 8 分布式图计算的容错技术发展脉络

(1) 面向专用计算作业的容错.这一阶段最早可追溯到 20 世纪 80 年代的高性能计算领域,用户基于底层库
编写专用程序来实现分布式图计算作业计算逻辑,用户须自己处理计算并行、图切分、节点通信等问题,同时
计算资源和计算作业的分布式化对容错提出了新的需求,引起了一波面向专用计算作业的容错技术的研究热
潮.在这一过程中,图计算作业作为高性能计算作业的子集,其容错也得到了一定的发展,其容错技术主要是基
于硬件 [15,16] 、操作系统 [1720] 或运行时库 [2124] 的实现,以及少量基于用户应用程序 [30,31] 的实现.这些技术的局限
性表现在:一方面,基于硬件、操作系统或运行时库的容错实现难以移植,并且粗粒度的应用状态冗余管理,无法
满足分布式图计算作业的性能需求;另一方面,基于用户应用程序的容错实现使原本就复杂的专用程序变得更
为复杂,用户在处理计算并行、图切分、节点通信等问题的同时还需要考虑容错,可能会引入更多的不确定性
而导致故障的发生;
(2) 面向通用大数据处理作业的容错.这一阶段以 MapReduce [27] 的提出为标志,通用大数据处理框架(即通
用分布式数据流框架)开始蓬勃发展,用户基于通用大数据处理框架,如 Hadoop、Spark 等提供的数据流算子实
现计算逻辑,同时,通用大数据处理框架在设计伊始便考虑到容错这一问题,其容错技术往往与框架的功能结构
紧密耦合 [27,28,4345] ,如 Spark 的弹性分布式数据集(RDD)和血统(lineage),能够基于较细粒度的数据或者任务进
行冗余状态管理,从而减少性能开销.图计算作业作为大数据处理作业中相当重要的一部分,其容错也受益于这
样的设计,但同时也受限于框架通用性的考量,难以针对图计算作业任务粒度细、任务间的依赖关系复杂、容
错需求多样等特点进一步优化;
(3) 面向分布式图计算作业的容错.随着对图数据和图计算的日益重视,这一阶段以第 1 个专用分布式图计
[4]
算框架——Pregel 的提出为分界点,用户开始借助分布式图计算框架提供的编程抽象更方便地实现了分布式
图计算作业的计算逻辑.相应地,其容错的数据粒度从 MapReduce 中的任务和 RDD 中的分区等进一步细化到了
顶点状态和顶点间消息,并且,随着研究人员对分布式图计算框架、图计算作业鲁棒性和失效特征的深入认识
和分析,容错在多个方向上进行了个性化的优化和发展.目前,面向分布式图计算作业容错的优势在于,其一方