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

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

复,然而故障是在第 X 超步运算过程中发生的,例如内存指针错误,这可能会导致容错机制在将作业恢复至第
X+N 超步时节点再次崩溃或者使得作业运行得到错误的结果.然而仅有文献[60]一个工作涉及到了处理拜占庭
失效,并且该工作并没有面向分布式图计算作业作进一步优化.此外,还有分布式图计算作业可能面临的性能失
效、遗漏失效和崩溃失效则完全没有工作给予讨论,相关研究一片空白.之所以是这样的现状,归结原因在于缺
乏对分布式图计算作业中故障和失效特征的深入认识.
研究分析分布式图计算作业中的故障和失效特征,不但能为相关研究提供目标指引,还能进一步打开面向
分布式图计算作业的容错技术的优化空间,使其在充分耦合分布式图计算框架、分布式图计算作业的特点之
后,也与故障和失效特征作进一步耦合,实现容错质量更好、恢复效率更高且容错成本更低的容错机制.

5.2 主被动容错协同的作业质量保障机制
现有的面向分布式图计算作业的容错技术全部采用被动容错机制,即是一类针对系统中已经发生的故障
或失效进行处理、减少故障或失效带来的负面影响的机制.但被动容错的弊端在于失效已经发生,再优秀的被
动容错技术也难以熨平失效给作业性能带来的颠簸,而颠簸会导致作业运行环境的不稳定,会给作业运行带来
更多的不确定性,作业发生失效的概率亦随之增加,使得作业质量进入了一个负反馈循环中.而主动容错作为一
类试图减少系统中故障发生概率,从而避免和阻止失效发生的机制,为减少和避免作业性能颠簸提供了可能,例
如基于失效预测的预迁移技术 [62,63] ,其中失效预测是该技术的核心,典型的失效预测方法通常需要人为地划分
时间段作为预测窗口,然后基于日志(log)、监控(monitor)或追踪(track)数据进行预测 [40] .而在分布式图计算领域
中,一方面,由于作业迭代计算的特性,天然地存在预测窗口(超步),为失效预测提供了便利;但另一方面,由于分
布式图计算对性能的追求,可能缺乏充足的日志、监控和追踪数据,给准确地预测失效带来了挑战.
此外,被动容错仅能处理由于系统瞬时故障导致的失效,而主动容错则有机会对程序 bug 导致的永久故障
进行处理,例如自修复(self-healing)和软件重生(rejuvenation)技术等 [62] ,前者能够使系统自动感知自身是否处于
错误状态,并在无人工干预的情况下进行必要的调整以恢复正常,避免失效.从原理上看,这种技术更适合具有
较强鲁棒性的分布式图计算作业;而后者则是定期对软件进行重启,从而清理掉内部的状态,进而避免错误在系
统内部的累积.从原理上来看,这种技术与图计算作业的迭代计算特性相得益彰.
然而,目前尚无研究将主动容错尝试应用于面向分布式图计算作业的容错机制之中.随着分布式图计
算在各行各业的广泛应用,保障图计算作业质量的需求也会水涨船高,研究主被动容错协同的作业质量保
证机制能够充分利用主动容错机制和被动容错机制的优势,在保障作业正常执行的情况下,尽量提高作业
运行质量.
5.3 面向复杂图计算作业的容错技术
目前,面向分布式图计算作业的容错技术相关研究主要集中在对基于静态图的分析作业的容错.基于静态
图的分析作业具有计算会遍历访问整张图和多轮迭代计算直至收敛的特点,典型的有 PageRank、图着色(graph
coloring)、图模式挖掘(graph pattern mining)和 K-core 等作业.然而,图计算作业正在变得愈发复杂,原因主要来
自于两方面:(1) 动态图、流式图变得愈发普遍,图数据变得更为复杂,导致作业的计算模式发生改变 [6468] .其中,
动态图相比于静态图而言,图中的属性值或拓扑结构会随着时间发生变化,而流式图则在图上进一步引入了流
的特性,一是流式图是无界的,作业无法访问到整个图.另一方面,流式图的传输速率可能会非常高,导致图更新
的速度会非常快.目前,基于动态图和流失图的作业计算模式主要有基于快照的批量计算(batch computation of
each snapshot)和增量计算(incremental computation),前者对不同时刻的图进行快照,然后在每个快照上进行分
析;而后者则是将图的变动建模进计算过程中,需要对计算模型进行特殊设计;(2) 算法自身变得更为复杂,例如
顶点/图分类、链接预测等作业.这些与深度学习相结合的图计算作业——图神经网络 [6971] ,主要包括图卷积网
络、图循环神经网络和图注意力网络,其基本的计算模式是通过图结构进行信息传播,利用神经网络来进行顶
点更新,并且在模型训练阶段,需要批量执行和利用反向传播更新神经网络参数.相比传统的基于静态图的分析
作业,图神经网络无论是在编程实现还是在任务调度方面均有很大的不同.近年来,各大开源图计算项目也在陆