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

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

Fig.12 An example of parallel confined recovery [50,51]
图 12 并行受限恢复举例 [50,51]
4.2.2 基于轻量级日志保存的容错
由于消息的数量和边的数量呈正相关,并且每轮迭代都要进行消息记录,这会占用大量的磁盘,并且对过期
(最近检查点之前)的消息进行删除是耗时的.文献[48]在轻量级的检查点容错 LWCP 基础上提出了基于轻量级
的日志保存 LWLog(LightWeight logging)的容错.基于图 10 中同样的顶点更新和消息生成逻辑解耦方法,在正
常运行期间,LWLog 方法仅保存顶点值及标志该顶点值是否生成消息的标识位,将每个超步保存的数据量从
O(E)降到了 O(V),大大减少了磁盘占用.而在失效恢复期间,幸存节点需要在加载保存在本地的顶点值后,生成
失效节点所需的消息并发送,但是由于幸存节点生成消息的过程与失效节点的重新计算过程重叠,恢复效率也
因此未有明显下降.最终,因为磁盘占用的减少,清理过期消息的耗时也相应大幅度减少,从而显著减少了对系
统正常运行带来的性能开销.另外,出于与 LWCP 方法一样的原因,LWLog 方法也需要用户少量参与.
4.2.3 基于日志的容错对比分析
表 2 列举了上述工作的优化对基于日志的容错在成本、效率和质量这 3 个维度 6 个指标上的影响(以 Pregel
[4]
中的日志容错机制 为基准),并进行了对比.
Table 2 Comparison of fault tolerance based on logging
表 2 基于日志的容错机制对比
成本 效率 质量
名称 文献 失效恢复 后恢复 可支持的 可处理的
性能开销 用户参与度
时间 运行时间 作业类型(≤) 失效类型(≤)
任意数量的
[54,55] 略微增加 对用户透明 显著减少 不变 全局一致作业
基于并行受限 级联失效
恢复的容错 任意数量的
[50,51] 不变 对用户透明 减少 不变 全局一致作业
级联失效
基于轻量级日志 [48] 任意数量的
保存的容错 显著降低 需用户少量参与 未有明显增加 不变 全局一致作业 级联失效
首先,基于日志的容错都保持了高质量的容错,都能够支持全局一致作业并处理任意数量的级联失效.而基
于并行受限恢复的容错更侧重于对恢复效率的优化,文献[50,51,54,55]均通过利用幸存节点闲置的计算资源来
加速失效恢复过程,并充分利用不同分布式图计算框架的特点设计合适的快速受限恢复方法,以至于仅增加了
很小甚至没有额外增加性能开销.而基于轻量级日志保存的容错更侧重于降低性能开销,并且,文献[48]为了获
得更好的通用性,基于单段的 Vertex-Centric 编程模型来进行顶点更新和消息生成的解耦,因此也带来了些许人
力成本.