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

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

Fig.11 Recovery of multi-node failure [52]
图 11 多点失效的恢复过程 [52]
4.1.3 基于检查点的容错对比分析
表 1 给出上述工作的优化对基于检查点的容错在成本、效率和质量这 3 个维度 6 个指标上的影响(以
Pregel、GraphLab 和 PowerGraph 中的全局一致检查点容错 [46] 为基准),并进行了对比.从整体上看,基于检查点
的容错机制都只支持对任意数量的多点失效的恢复,而不支持对级联失效的逐步恢复(recovery progressively),
当级联失效发生时已部分恢复(partially recovered)的计算会再次丢失,这一问题会在后文基于日志的容错技术
中给出解决办法;然后发现相关工作中全局一致检查点容错的优化重点集中在其性能开销的降低;而局部一致
检查点容错的优化重点则在其恢复效率的提高.具体而言,在全局一致检查点容错技术中,文献[41,4749]分别
利用了作业的运行时特性——负载动态变化和作业的编程模型——将顶点更新和消息生成解耦,实现了性能
开销的大幅度降低,但其代价则是失效恢复时间的相应增加,并且在文献[48]中还额外增加了一定的人力成本;
而文献[50,51]则通过将快照保存过程与数据流计算过程的重合,小幅度地降低了检查点的性能开销,并且未带
来其他副作用.而在局部一致检查点中,文献[52]利用异步调度机制的特性,不用将失效状态恢复至全局一致状
态,从而显著提高了失效恢复和后恢复运行的效率,并且,该方法的一个副产物是小幅降低了检查点的性能开
销,然而其代价是容错质量的降低,无法对全局一致作业和全局可矫正作业提供容错支持.
Table 1 Comparison of fault tolerance based on checkpointing
表 1 基于检查点的容错机制对比
成本 效率 质量
名称 文献 后恢复 可支持的 可处理的
性能开销 用户参与度 失效恢复时间
运行时间 作业类型(≤) 失效类型(≤)
任意数量的
[41,47,49] 显著降低 对用户透明 增加 不变 全局一致作业
多点失效
全局一致 任意数量的
检查点容错 [48] 显著降低 需用户少量参与 增加 不变 全局一致作业 多点失效
任意数量的
[50,51] 降低 对用户透明 不变 不变 全局一致作业
多点失效
局部一致 任意数量的
检查点容错 [52] 降低 对用户透明 (合计)显著减少 局部可矫正作业 多点失效

4.2 基于日志的容错

基于分段确定性假设(piecewise deterministic assumption),一个任务的执行可以被建模成一个状态间隔
(state intervals)序列,每个间隔序列从一个非确定性事件开始.日志(logging)是保存非确定性事件决定性因素
(the determinants of the nondeterministic event)的过程 [53] .通常,基于日志的容错与基于检查点的容错是正交的,
前者是对后者的重要补充,前者避免了幸存节点的回滚(空间维度上),后者避免了作业从头重新运行(时间维度
上),于是在很多面向分布式图计算作业的容错工作中,这两种机制搭配使用.其中,基于日志的容错的基本思路