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

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

算库.在这类框架内,虽然高层图计算库,如 GraphX 和 Gelly 可以提供不同的编程模型、支持不同的图切分方式以
及调度机制,但是底层的数据交换仍然是基于数据流的——图计算的迭代过程被抽象成 join-groupBy-aggregation
的数据流模版(pattern),而数据交换则发生在 shuffle 过程中.相较消息传递和共享内存机制,基于数据流机制的
分布式图计算框架在灵活性和可扩展性上较差,但具有更好的通用性,帮助用户在同一个框架内完成多种数据
处理任务,如预处理、模型构建、图计算等.而从容错的角度看,通信机制对容错机制的设计和实现有着重要的
影响,例如基于日志的容错技术就更适合应用于采用消息传递机制的作业,一方面,在实现逻辑上更为简单和直
接,保存传递的消息即可;另一方面,消息传递机制的众多优化功能,如为了提高网络吞吐率的 Combiner,同样也
能提高基于日志容错技术的恢复效率.

Fig.3 Examples of graph-cut methods and communication modes
图 3 图切分方法和通信方式示意图
以上介绍了分布式图计算框架的四大组件及其各自的技术类型,并简要介绍了各种组件特点能够为容错
机制优化提供的可能性,详细内容将在第 4 节结合具体内容进一步加以论述.
1.2 分布式图计算作业
分布式图计算作业由输入、计算过程和输出构成,其输入通常是一个由顶点、边及其值构成的有向图,其
计算过程可被描述成一个基于用户定义的计算逻辑(user defined function,简称 UDF)在图上多次迭代直至达到
终止条件(如收敛)的过程,而其输出则视作业情况而定,可以是更新后的图、顶点及其值的集合或者统计数字等,
不一而足.以 PageRank 作业为例,输入是一个顶点带有 rank 值的有向图;用户定义的计算逻辑是每个顶点接收
其入边方向邻居顶点传来的 rank 值后,更新自身的 rank 值,然后再沿出边方向,向邻居顶点发送更新后的 rank
值;而作业的计算过程就是在每个迭代中使图中的每个顶点都执行上述逻辑,然后多次迭代,直到图中所有顶点
的 rank 值更新幅度均小于某一阈值后,迭代收敛,计算过程结束;输出是图中的所有顶点及其更新后的 rank 值.
上述过程可以建模成一个由图中顶点值和边值构成的全局状态的演变过程.在同步调度机制中,作业基于
当前全局状态在一个超步内对全部的顶点或边完成值的更新,随后进入到下一个全局状态;而在异步调度机制
中,作业基于当前全局状态往往仅能依据具体的调度策略对一部分的顶点或边完成更新,即进入到下一个全局
状态.在作业运行过程中,失效的发生将导致全局状态部分损坏或丢失,作业面临状态不一致的问题.容错中的
失效恢复就是对全局状态进行“修复”的过程.因为分布式图计算作业不同的运行特点和对运行结果不同的准
确度需求,容错机制可以在失效恢复中对全局状态进行不同程度的“修复”,如图 4 所示.基于此,分布式图计算作
业可分为 4 类,分别是自稳定作业、可矫正作业、全局一致作业和近似作业.
为了方便后续对各类作业进行详细的解释,这里对图 4 中的相关状态进行了定义.首先,图中顶点和边的值