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

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

型容错恢复难度越高,则容错能力越强、质量越高.
2.2 难点和挑战
在实际实现面向分布式图计算作业容错机制时分别面临成本、效率和质量这 3 方面的难点和挑战.
(1) 在成本方面,图计算的并行计算过程由数据驱动,过程中节点工作负载动态变化,用户难以在作业提交
前预知其负载情况;并且,图数据的局部性差,分布式图计算作业需要占用大量通信和计算资源,对资源竞争敏
感.因此,在何时、以怎样的方式进行状态冗余备份,能够减少消耗的资源成本、减少容错机制给分布式图计算
作业正常运行带来的额外性能开销,同时又不显著提高人力成本即保持对用户的高透明度成为一个挑战;
(2) 在效率方面,分布式图计算作业任务间的依赖关系复杂,导致失效发生后,幸存节点难以继续运行,需要
挂起等待甚至回滚,造成单点恢复瓶颈以及重复计算等问题,增加了失效恢复过程的时间,大量资源被闲置和浪
费;在非全局一致作业容错过程中,失效节点上的“修复”状态和原状态 s la 的差异还可能会带来后恢复运行时间
延长的副作用.因此,如何在失效后快速恢复分布式图计算作业的状态使其继续运行,同时不显著增加后恢复运
行时长成为第 2 个挑战;
(3) 在质量方面,如前文所述,分布式集群规模庞大、图计算框架抽象层次高,加之图计算作业计算负载动态
变化且运行周期长等因素,使得分布式图计算作业面临着分布式图计算系统内外各种来源的非确定性,故障和
失效频繁、复杂且种类多样.因此,如何分辨不同的作业类型,在满足其个性化结果准确度需求的基础上支持处
理更复杂的故障和失效类型成为第 3 个挑战.

2.3 评估框架
然而,即便与分布式图计算框架的功能结构、图计算作业的运行特点进行紧密耦合,充分利用其提供的优
化空间,面向分布式图计算作业的容错技术依然难以同时在成本、效率和质量这 3 个维度优化到极致.如图 7
所示,在中心 3 个圆形相交的区域,成本、效率和质量之间构成了一个“不可能三角”,即不存在成本低、效率高
和质量好的容错机制,更多时候需要考虑和利用分布式图计算作业的具体容错需求,在成本、效率和质量这三
者之间进行权衡和取舍.

Fig.7 “Impossible Triangle” of cost, efficiency and quality of fault tolerance
图 7 成本、效率和质量的“不可能三角”

如图 7(a)中重叠区域所示,能够处理更复杂的失效类型(高质量)并消耗更少资源(低成本)的容错机制会导
致恢复效率的降低.例如,采用长间隔的检查点容错机制会减少保存快照的数量,但会导致失效后需要更长的时
间从最近快照恢复至失效前最新状态 [41] ;如图 7(b)中重叠区域所示,能够冗余更少作业状态(低成本)并提供更
高恢复效率(高效率)的容错机制会导致仅能支持相对较少的作业类型(低质量).例如,基于算法补偿的容错能够