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

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

值计算得出,而不依赖于顶点之前收到的消息.基于此,在保存快照时仅需要保存顶点值 a (i–1) (v)和顶点激活状态
on (i–1) (v)而无需保存消息 M i (),v 缩小了快照体积.同时在失效恢复时,容错机制可以更快地加载所需快照,而所
in
需的消息则可以根据加载的顶点值计算得出.最终,基于 LWCP 方法,PageRank 作业每次检查点保存快照所需时
间在 WebUK 数据集上从 65.18s 减少到 2.14s,在 WebBase 数据集上,从 27.45s 减少到 2.16s,检查点操作性能提
升 10 余倍,但在失效恢复过程中,由于加载最近的快照后需要额外生成消息,这个过程所需时间分别增加了 35s
和 15s 左右,考虑到作业运行过程中失效频率一般小于检查点操作频率,为了保障作业的整体运行性能,牺牲一
部分的失效恢复效率是值得的.此外,LWCP 在使用时需要用户少量参与,一方面,用户需要在实现 compute()方
法时将顶点更新逻辑和消息生成逻辑分开,另一方面,用户需编写用户自定义方法 LWCPable()对作业运行中少
数不适宜采用 LWCP 的超步进行筛选.同样的轻量级检查点技术也应用在文献[49]中的 Seraph 框架,并且因为
Seraph 的 SG 编程模型本身就提供了 compute()和 generate()两个接口分别实现顶点更新逻辑和消息生成逻辑,
因此在用 Seraph 框架实现的分布式图计算作业中,轻量级检查点容错机制对用户是透明的.
然而,上述全局一致检查点需要阻塞作业的正常运行,待全局一致快照保存结束后作业才能继续计算,这种
阻塞式的检查点给分布式图计算作业的正常运行带来了较大的性能开销;而现有的非阻塞检查点仅适用于保
存不变(immutable)数据,例如 Spark 中对 RDD 的非阻塞保存 [28] .于是,文献[50,51]通过对基于数据流机制通信的
分布式图计算作业进行分析,发现在迭代执行 join-groupBy-aggregation 数据流模版的过程中,每轮迭代更新后
的顶点值并不是立即就被消费使用了,于是提出了将检查点写快照的过程与超步结束时顶点更新生成的过程
重叠(overlap)并行的尾部检查点(tail checkpointing),即一边更新顶点状态一边保存快照和与超步开始时顶点被
消费使用的过程重叠并行的头部检查点(head checkpointing),即一边消费顶点状态一边保存快照.若检查点操
作未能提前于顶点更新生成过程或顶点被消费过程结束之时完成,仍要进行阻塞以完成快照保存,但该方法仍
然有效地减少了检查点操作带来的性能开销,尤其是头部检查点相较阻塞式检查点将性能开销从 33%降到了
13%.
4.1.2 局部一致检查点容错
上述全局一致检查点容错与基于同步调度机制的图计算作业是契合的.而基于异步调度机制的图计算作
业的计算过程本质上是非确定性的(non-deterministic)——即使是从同一个全局一致状态开始计算,结果通常
也会存在些许差异,这降低了失效恢复中作业恢复至最近全局一致快照的必要性;而且全局一致检查点需要集
群中各计算节点将快照在同一时间段内保存至可靠存储中,这增加了峰值带宽利用率,容易造成网络争用和性
能下降.文献[52]提出一种基于局部一致快照进行异步保存和失效恢复的方法.首先,文献发现异步调度机制对
读写依赖的放松导致分布式图计算作业无需保持全局一致性而只需保持 PR 一致性(progressive reads
consistent)即可保证结果的正确.于是,在正常执行过程中,由各计算节点自身决定保存内部状态的时机,这减少
了同时保存的快照数量,从而减少了网络争用.同时,由于局部一致快照节点内状态一致而节点间状态不一致的
特点,master 节点需要依据快照间的依赖关系保存 PR 顺序,用于在多点失效情况下决定失效节点逐次恢复的顺
f
序.基于此,如图 11 所示,在失效恢复阶段,所有失效节点需从 S 分别加载其最近的局部一致快照,然后按照 PR
顺序对失效节点逐点恢复:(1) 对第 1 个失效节点 a 用快照 s a 初始化;(2) 用其他节点上的边界顶点值(包括剩余
cf
f
失效节点的快照 S –s a 和所有幸存节点的状态 E )更新其子图状态(图中虚线);(3) 在该节点上进行局部计算至
收敛,使更新后的边界值传播至该节点内的非边界顶点上,至此,该失效节点与其他节点保持了 PR 一致性;
(4) 接着将节点 a 和在 PR 顺序中紧随其后的失效节点 b 看作一个整体,重复以上对失效节点 a 的恢复过程,直
至图中所有节点均满足 PR 一致性,多点失效的恢复过程结束.最终,在实验中局部一致的异步检查点相较全局
一致检查点的峰值带宽利用率降低了 22%~51%,减少了对作业正常运行造成的性能开销;并且在失效恢复阶
段,该方法可以实现受限恢复,幸存节点不用回滚,失效恢复及后恢复运行阶段较基于全局一致检查点的全局回
滚恢复方法加速了 1.5~3.2 倍;然而,该方法的容错质量较全局一致检查点容错方法有所降低,仅能支持自稳定
作业、近似作业和局部可矫正作业,不能支持全局可矫正作业和全局一致作业.