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

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

的容错机制;另一方面通过深入分析理解不同的分布式图计算作业的容错需求,实现容错机制在容错的“不可能
三角”——成本、效率和质量之间更为灵活、准确地权衡和取舍.例如,针对仅需近似准确结果的作业而言,在失
效恢复时将其恢复至全局一致状态是不必要的,可以通过快速地近似恢复实现高效率.
本文第 1 节介绍分布式图计算框架、分布式图计算作业以及分布式图计算中的故障和失效模型等背景知
识.第 2 节分析面向分布式图计算作业的容错技术的优化目标和面临的挑战,进而提出对容错机制进行评估的
框架和指标.第 3 节从分布式计算框架发展的角度梳理分布式图计算容错技术的发展阶段.第 4 节总结归纳 4
种分布式图计算容错机制,分别基于检查点、日志、复制和算法补偿,并结合相关工作进行详细的分析、比较
和评估.最后,在第 5 节总结现有工作的不足并对未来的研究方向加以展望.

1 背景概述

分布式图计算框架的异构性和复杂性一方面给图计算作业的运行带来了大量的不确定性,另一方面也为
容错机制的设计提供了优化空间,同时图计算作业本身的鲁棒性和作业可能面临的失效类型对容错机制的设
计也有重要影响.本节首先对分布式图计算框架作了总结介绍,然后从失效及恢复的角度对分布式图计算作业
进行了分类,最后对分布式图计算中的故障和失效类型以及容错框架进行了分析和总结.
1.1 分布式图计算框架
[4]
自 2010 年第一个分布式图计算框架 Pregel 提出以来,分布式图计算框架在近 10 年来被不断地研究、发
展和提出.据不完全统计 [25] ,截止 2017 年,先后有不下 40 种分布式图计算框架被提出.大体上,分布式图计算框架
由 4 个相互依赖的组件构成,分别是编程抽象(programming abstraction)、图分区(partitioning)、任务调度
(scheduling)和通信(communication).这 4 个组件共同驱动了图计算作业的分布式执行,并共同决定了作业执
行的性能 [26] ,如图 2 所示.

Fig.2 Distributed graph processing framework components and their types
图 2 分布式图计算框架组件及其类型

首先,编程抽象(programming abstraction)往往是用户感知最为敏感的组件,它向用户提供了一个输入图数
[4]
据的局部视图(顶点视图应用最为广泛)和一组在此视图上进行操作的方法接口(即编程模型).例如,Pregel 向
用户提供了一个顶点视图和在此顶点上进行操作的 compute()方法接口,用户在 compute()内实现接收消息、更
新顶点值和发送消息的计算逻辑,而图上的每个顶点都将按照该逻辑进行计算.从容错的角度来看,顶点视图为
容错提供了更细粒度的容错单元.相较于节点备份、进程复制、基于数据块的 task 重试(MapReduce) [27] 、基于
RDD 分区的重播(Spark) [28] 等粗粒度的容错方法,基于顶点的细粒度容错方法天然地有更小的性能开销.此外,
编程抽象中除了有采用 compute()方法接口的单段 Vertex-Centric 编程模型以外,应用较为广泛的还有两段的