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

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

步,否则,回滚重新计算,直到副本哈希码相同或判定作业运行失败.最终,该方法为拜占庭失效提供了一定程度
的容错能力,但其代价是严重的性能开销和低效率的失效恢复.

Fig.13 The percent of vertices without replicas, including normal and selfish vertex (left)
and the percent of extra replicas for fault tolerance (right) [59,59]
图 13 无天然副本的顶点所占比例和额外创建的容错副本所占比例 [58,59]
4.3.3 基于复制的容错对比分析
表 3 列举了上述工作的优化对基于复制的容错在成本、效率和质量这 3 个维度 6 个指标上的影响(以 Pregel
[4]
中的全局一致检查点容错 为基准),并进行了对比.整体来看,基于复制的容错均只用于采用同步调度机制的分
布式图计算作业,并且在容错能力上均受到了副本数量的限制,所以均只支持处理有限数量的失效,而且随着
副本数量的增加,付出的相应代价也随之增加——在文献[57]中是后恢复时间的增长和结果准确度的降低,
在文献[58,59]中是内存和通信开销的成倍增长,在文献[60]中则是性能开销和失效恢复时间的急剧增长.而分
开来看,则是被动复制容错技术和主动复制容错技术所要应用的场景不同,因此导致了两者在成本、效率和质
量三者权衡上迥然不同的选择,前者对作业的整体性能极为看重,为此可以牺牲一定的容错质量,而后者对作业
的结果准确度有极高的要求,为此可以付出极高的资源成本并接受极低的容错效率.
Table 3 Comparison of fault tolerance based on replication
表 3 基于复制的容错机制对比
成本 效率 质量
名称 文献 用户 失效恢复 后恢复 可支持的作业 可处理的失效
性能开销
参与度 时间 运行时间 类型(≤) 类型(≤)
被动 [57] 零性能开销 对用户透明 显著减少 不确定 近似作业 有限数量的级联失效
复制容错 [58,59] 少量内存和通信开销 对用户透明 显著减少 不变 全局一致作业 有限数量的多点失效
主动复制 [60] 显著增加 对用户透明 显著增加 不变 全局一致作业 有限数量的拜占庭失效
容错

4.4 基于算法补偿的容错

算法补偿(algorithmic compensation)是针对特定类型的图计算作业,在故障发生后,使用预定义的补偿算法
直接生成丢失的状态的过程.基于算法补偿的容错均建立在对图计算作业特性的深入分析和理解的基础上.在
正常运行阶段,不对任何状态和值做冗余备份,从而实现对作业正常运行的零性能开销;当失效发生后,按照预
定义的补偿算法,直接生成丢失顶点的状态(往往不会是全局一致状态),幸存节点不回滚,作业继续运行.按照预
定义的补偿算法的存在形式可将基于算法补偿的容错分为内置补偿算法容错和自定义补偿算法容错.前者将
补偿算法嵌在分布式图计算框架之内,用以支持一类图计算作业,当用户实现这类作业时,补偿算法对其是透明
的;而后者则是对为用户提供了编程范式,类似于一种异常处理框架,其内部具体的处理逻辑需要用户自己根据
图计算作业的需要加以实现.下文结合具体的研究工作对这两种基于算法补偿的容错技术进行详细的分析和
对比.