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

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

作为一种建模对象间关系的常用数据结构,图(graph)通常由顶点 V(即对象)、边 E(即对象间关系)和标签
L(即顶点或边的属性)这 3 个要素构成,其数据种类丰富、分布广泛.一方面,天然的图数据广泛存在于社会生活
的方方面面,如社交网络、交易网络、物联网、交通运输网和供电网络等;另一方面,图数据也从各种任务的建
模中产生,如商品推荐中的矩阵分解(消费者、商品及之间的购买关系)和文本分类中的 LDA(latent Dirichlet
allocation)主题模型(文档、单词及之间的包含关系)等.对这些图数据的处理分析,即图计算(graph processing)任
务,广泛应用于欺诈和威胁检测、社交网络分析、个性化推荐和自然语言处理等诸多领域,创造了重要的社会
和经济价值.
然而,一方面,图计算要处理的图数据规模十分庞大,大图普遍存在并被广泛使用.一项针对企业从业者和
科研人员的调研报告 [1,2] 指出,有 22.5%的任务需使用和处理超过十亿边的大图,有 4.5%的任务甚至使用超过一
万亿边的超大图;另一方面,图计算任务种类丰富且计算复杂,统计数据 [1,2] 表明,除了常用的 SSSP(单源最短路
径)和 PageRank 等图算法以外,有超过 68.5%的任务在图上应用了各种机器学习算法.因此,单机往往无法满足
[3]
图计算作业的存储和计算需求,图计算的分布化成为目前的主流趋势 .
图计算作业在运行过程中面临着分布式图计算系统内外各
种来源的非确定性所带来的严峻的可靠性问题:在系统内,
(1) 分布式图计算系统的复杂性给图计算作业的运行带来更多
的不确定性.为了帮助用户专注于作业逻辑,现有的分布式图计
算框架(distributed graph processing framework)——专用分布式
图计算框架 [48] 和基于通用分布式数据流框架(general-purpose
distributed dataflow framework)的高层图计算库 [9,10] ,均具有较高
的抽象层次,如图 1 所示,系统的复杂性高,故障可能在硬件、操
作系统、数据流框架等底层发生;(2) 图计算作业数据驱动的计
算过程导致集群节点间负载不均衡,增加了作业运行的不确定

性.数据驱动的计算过程导致难以在作业提交前通过对数据和
Fig.1 Abstract level of distributed graph
计算任务的均衡切分来均衡各节点的计算负载和节点间的通信
processing framework
负载,并且图计算作业运行过程中负载动态变化,进一步加剧了
图 1 分布式图计算框架所处的抽象层
负载均衡的实现难度,而集群中负载的不均衡是导致故障发生
的重要原因之一;在系统外,(3) 分布式图计算作业运行集群规模庞大,集群可靠性低.即使集群中单节点平均无
失效时间(mean time between failure,简称 MTBF)可达 100 万小时,随着集群规模的增加,集群整体 MTBF 则呈
指数级降低 [11] .极端情况下,集群中每时每刻都会有节点失效;(4) 云计算环境的异构、多租户等特性也威胁着
作业运行的可靠性.异构性加剧了图计算作业负载难以均衡的问题,多租户特性使得图计算作业的性能受到环
境中其他作业的干扰 [1214] ,甚至由其他作业产生的故障会导致图计算作业的失效.而分布式图计算作业任务间
的依赖较为复杂,故障传播快、影响大:在分布式图计算作业运行期间,每个任务都需要从其他顶点(通常是邻居
顶点)接收或读取数据来更新其自身的顶点值,这导致任务间的依赖关系复杂化,一旦有任务发生故障,错误会
迅速在任务间传播,进而导致整个作业运行失败,或者当集群中一个节点失效,幸存节点因为无法读取失效节点
的数据,使得幸存节点上的任务无法继续进行,导致整个作业运行中断,严重影响作业性能.上述原因导致分布
式图计算作业面临着故障发生频率高、传播快、影响大等技术挑战,因此,如何对分布式图计算作业和系统进
行有效的容错,使其在实际应用场景下仍能保持稳定的性能是亟待解决的核心问题.
随着分布式图计算作业处理的图数据日益庞大、计算日益复杂,其对容错机制的性能开销、恢复效率等提
出了更高的要求.传统的基于硬件 [15,16] 、操作系统 [1720] 、运行时库 [2124] 的容错机制只能对作业进行粗粒度的
状态管理,如进程复制、计算节点备份等,性能开销极大,无法满足分布式图计算作业对性能的需求.基于此,面向
分布式图计算作业的容错技术应运而生.面向分布式图计算作业的容错技术主要从两方面进行优化,一方面通
过与分布式图计算框架、分布式图计算作业进行紧密耦合,实现容错质量更好、恢复效率更高且容错成本更低