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

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

是在作业正常运行期间,记录任务的非确定性事件,如在 GraphX(Spark)中记录 RDD 分区间转换操作的 Lineage;
在失效恢复时,通过日志完成失效任务从最近快照状态至失效前最新状态的重播,而未失效任务则不用回滚重
新计算,实现受限恢复.另外,在实际使用中,由于采用异步调度机制的分布式图计算作业计算过程的非确定性,
日志记录是高消耗和不必要的,因此基于日志的容错技术多用于确定性更高的采用同步调度机制的分布式图
计算作业.在文献[4]中,Pregel 基于 BSP 同步调度机制对作业中的顶点任务进行调度运算.从顶点任务的角度来
看,每个任务接收的消息都是非确定性事件,但从计算节点的角度来看,由于同一计算节点上顶点任务之间的消
息在恢复期间会重新产生并且是确定性的,因此仅需在每个超步对来自其他节点的消息进行记录即可,然后在
失效恢复时,幸存节点向重启或新启的节点重新发送保存的消息.此外,由于受限恢复的原因,基于日志的容错
技术天然地支持对任意数量的级联失效的恢复,当新的级联失效发生时,正在恢复的节点 M i 暂停恢复,并联合其
他迭代进度大于 M i 的节点对新的失效节点进行受限恢复,直至将其恢复至与 M i 同样的迭代进度,然后将两者从
逻辑上看作一个整体,继续进行恢复,从而实现逐步恢复.
在现有的研究工作中,基于日志的容错可以分为基于并行受限恢复方法的容错和基于轻量级日志保存方
法的容错.下文结合具体的研究工作对这两种技术进行详细的分析和比较.
4.2.1 基于并行受限恢复的容错
一方面,由于图计算作业中任务间相互依赖关系复杂,失效发生后,幸存节点无法继续计算,计算资源被闲
置;另一方面,传统的重启或新启节点的恢复方法会导致失效恢复过程存在单点瓶颈,从而增加失效恢复的时间,
进而造成了集群中计算资源更长时间的闲置.因此,快速的恢复方法是必要的.一种直觉的方法是利用闲置的计
算资源进行并行受限恢复,文献[54,55]实现了基于失效图分区重调度的快速并行恢复方法.该方法基于 master
生成的重调度方案,将失效节点上的多个图分区重调度至被选中的幸存节点上,实现并行恢复,其中,重调度方案
质量的好坏会直接影响恢复的效率.于是,为了生成一个高质量的重调度方案,该方法在作业正常运行期间,
worker 节点会统计每个超步中各图分区的计算成本和图分区间的通信成本,并在全局同步栅期间,将相关统计
数据汇总到 master 节点;然后,Lu 和 Shen 等人 [54,55] 提出了一种综合考虑了计算和通信成本、可启发式地快速遍
历生成综合成本“最小”的重调度方案的算法;在失效恢复期间,master 基于收集到的数据和启发式算法快速生成
重调度方案,并基于此,管理失效恢复过程.最终,采用快速并行受限恢复方法的日志容错机制结合检查点容错机
制,相比单独的检查点容错技术在恢复速度上提升了 12~30 倍,但同时,日志的 I/O 也给系统正常运行带来了较大
的性能开销;并行恢复方法相比重启或新启节点的恢复方法,在恢复效率上也有大幅提高,但在系统正常运行阶
段,收集统计数据的行为也给作业性能带来一定的影响.
上述工作在基于 Vertex-Centric 编程模型和消息传递通信机制的分布式图计算作业中实现受限恢复是十分
自然的,其工作重点也更多地集中在了并行恢复的“快速”上.然而,该方法并不适用于基于数据流通信机制的分
布式图计算作业.在这种作业中,仅记录 join 操作产生的用于 groupBy 的消息是不能实现受限恢复的,aggregation
操作产生的分区间宽依赖关系将引入 shuffle 操作,使得幸存节点上的分区同样参与运算,导致完全恢复
(complete recovery).于是,文献[50,51]提出一种通过数据一致分区(co-partioned)和日志相结合的容错方法以实
现快速的受限恢复.在正常执行期间,每个计算节点保存在 groupBy 操作中向其他节点发送的消息,记作 Log;失
效恢复阶段,如图 12 所示,图中 Vertex 的第 1 列是顶点索引、第 2 列是顶点值,而 Message 和 Log 的第 1 列是目
标顶点索引,第 2 列是传递的消息.该图展示了失效节点上的分区(包含顶点 3、9、6)在幸存节点上进行 groupBy
操作时利用本地保存的消息进行并行受限恢复的过程.其中,丢失的 Vertex 和 Edge 可以分别通过最近快照和可
靠存储中的原始图数据构建,因此,join 操作不会导致完全恢复,而对 aggregation 操作来说,为了不引入宽依赖关
系,需要将 Vertex 和 Neighbor 进行一致分区,从而将其转化为窄依赖关系.至此,才实现了基于数据流通信机制的
分布式图计算作业的受限恢复.而该方法的“快速”主要体现在两个方面:一是受限恢复过程的并行化,二是将宽
依赖转化为窄依赖后,节省了节点间数据交换的时间.最终,该方法相比完全恢复,节省了 48%~81%的失效恢复
时间,显著提升了失效恢复效率.