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

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

[4]
Pregel 是采用该容错技术的典型代表,而异步调度机制由于没有全局同步栅帮助容错机制获取全局一致
[6]
[7]
快照,GraphLab 和 PowerGraph 便以一定的时间间隔挂起所有计算节点同步保存全局一致快照,或是基于
Chandy-Lamport 异步保存的方法获得全局一致快照.相较全局一致检查点容错,局部一致检查点容错技术应用
得较少,但后者也有其独特的优势.下文结合具体的研究工作对这两种检查点容错机制进行更为详细的分析和
对比.
4.1.1 全局一致检查点容错
首先,图计算作业运行过程中的工作负载会动态变化,例如一个 PageRank 作业的大多数顶点在前 10 轮迭
代过程中就基本收敛了,后续的迭代运算仅有少量顶点参加 [41] .而基于预先指定的固定间隔的检查点技术可能
导致失效恢复的开销小于一次快照保存的开销,这对系统整体性能来说是不划算的.对这个问题有两种解决思
路:一是随着计算负载的变化动态地调整检查点间隔,随着间隔的变大,失效恢复的开销也随之变大;二是调整
检查点保存快照的大小,当计算负载变小时,降低检查点保存快照的开销.于是,针对第 1 种解决思路,文献[41]提
出了基于作业运行时信息动态调整快照保存间隔的检查点容错机制.在采用同步调度机制的分布式图计算框
架中,作业计算过程被全局同步栅分割成一个超步序列.在作业正常运行时,master 节点分别收集并记录每次超
步的计算时长和每次检查点的快照写入保存时长,并在每次进入新的超步后,比较自最新快照至当前迭代的累
积计算时长和历史快照的平均保存时长(用于估计当前快照的保存时长),当前者大于后者时,认为此后若是发
生失效,则其失效恢复的开销将大于保存一次快照的开销,master 节点指示 worker 节点保存全局一致快照;否则,
不保存.最终,基于动态间隔的检查点容错机制相比基于静态间隔的检查点容错机制,使得作业正常运行
(failure-free)的性能最高提升了 8.5 倍,而付出的代价仅仅是失效恢复时间略微延长.针对第 2 种解决思路,文献
[47]提出了一种增量检查点容错机制.当作业中参与运算的顶点规模小于一定阈值时,检查点操作时不再保存
包含所有顶点状态的全量快照,而是保存仅发生改变的顶点状态的增量快照;在失效恢复阶段,加载最新的全量
快照和之后的所有增量快照进行合并,并基于合并后的快照状态继续恢复作业状态并继续计算.最终,该增量检
查点容错机制由于要对全量快照和增量快照进行合并,导致失效恢复效率降低,但增量快照减少了检查点的性
能开销,作业的整体性能大幅提升.
其次,在进行全局一致检查点操作时,快照的大小也会影响作业正常执行的性能.在类 Pregel 分布式图计算
系统中,每次检查点操作在当前迭代开始计算前保存:每个顶点 v 的状态 π (i–1) (v),包括顶点值 a (i–1) (v)、顶点激活
状态 on (i–1) (v)、甚至是顶点邻接表 (i–1) (v)(拓扑结构)和每个顶点 v 收到的消息 M in i ().v 其中,消息的数量是与图
中边的数量正相关的,并且,由于边的数量通常远远大于顶点数量,因此在检查点操作时保存消息会极大地占用
磁盘 I/O 和网络通信资源,严重影响作业的正常执行性能.文献[48]提出一种轻量级的检查点容错机制 LWCP
(lightweight checkpointing),其利用 MPI-3 标准中的弹性扩展 ULFM(user-level failure mitigation)在不改变 Vertex
Centric 编程模型的情况下,将顶点更新和消息生成逻辑解耦.如图 10 所示.

Fig.10 Decoupling of vertex update and message generation [48]
图 10 顶点更新和消息生成逻辑解耦 [48]

i
i
i
, )
顶点更新 π (v)和消息生成 M out ()v 的逻辑从单段式的  i (vM out (v  )   f  (1)i (vM in i (v  ) 转换成了双段式
, )
的  i ()v   g  (1)i (),v M i in (v  ); i ( )v   g  ( 1)i (),v M in i (v  );M out ()v   h  i ()v  , 即新的消息可以仅依赖更新后的顶点
i