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

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

4.3 基于复制的容错
复制(replication)是指多个任务副本(task replicas)同时运行在不同的资源上以保证任务运行成功的方
法 [56] .在追求支持处理更复杂的失效类型或更高效的失效恢复的情景下,基于复制的容错是基于检查点容错的
良好替代,但其同样也存在着天然不足——副本数量限制了可以处理的失效同时发生的最大数量.基于复制的
容错包括主动复制容错和被动复制容错.前者要求多个任务副本接收同样的输入,并分别独立运行输出,比较输
出结果,并利用投票或者重运行等方式检测失效并容错,而后者则仅要求主任务接收输入进行计算和输出,副本
任务通过与主任务之间保持状态同步来备份主任务,当主任务失效时,副本任务可以恢复或直接替换主任务,保
证作业继续运行.下文结合具体的研究工作对两种复制容错技术进行详细的分析和对比.
4.3.1 被动复制容错
全局一致检查点技术对大量状态的写操作以及不均衡的全局同步栅,给系统正常运行带来大量开销,通常
是一个迭代时长的 8~31 倍 [57] .而失效恢复时,全局一致检查点容错需要回滚幸存节点重新计算,以及加载全局
一致快照时带来的大量 I/O 操作和单节点恢复的 I/O 瓶颈,导致失效恢复效率低.而在现有的分布式图计算框架
中,由于图分区,尤其是基于 edge-cut(搭配 ghost,如图 3(c)所示)或基于 vertex-cut(如图 3(d)所示)的图切分方法,
导致系统中存在大量天然的顶点副本.此外,文献[57]发现,有些图计算作业仅需要近似准确的结果,且图数据中
度越大的顶点一般对图计算作业的结果贡献越大,而图分区对计算和通信负载均衡的内在要求导致度越大的
顶点其副本越多,从而越不容易在失效后完全丢失状态,进而降低了对结果准确度的影响.上述因素为被动复制
容错机制替代检查点容错机制提供了充足的动机和条件.于是,文献[57]提出了仅利用幸存节点上的副本恢复
失效节点的方法.首先对失效节点上存在天然副本的边界顶点进行恢复,而对没有副本的内部节点则重新初始
化,并且在 GAS 模型中,Scatter 阶段失效节点内更新的状态丢失了,需要执行局部的 Scatter 操作同步状态.最终,
由于该方法未在作业正常运行期间做任何额外的容错准备,所以其正常运行期间带来的性能开销为 0;而在失
效恢复上,由于仅利用幸存的状态直接重构失效节点的状态,并且局部的 Scatter 操作所需要的时间也远小于一
个完整超步的时间,所以失效恢复所需的时间极短.但是,当同时失效节点数增多时,一方面,后恢复运行时间可
能随之增长,另一方面,结果的准确度也可能随之降低,所以,该容错方法仅能对多点失效和级联失效提供有限
的支持.
而文献[58,59]则通过对多个图数据集和图算法进行分析后发现,图顶点中没有天然副本的仅占一小部分,并
且还有一部分是“自私(selfish vertex)”顶点,这些“自私”顶点在图拓扑结构上体现为没有出边,在计算过程中体现
为不参与其他任何顶点的计算更新.因此,仅需要为很小一部分没有天然副本的非“自私”顶点创建额外的容错副
本即可.图 13 展示了在不同的图数据集中没有天然副本的顶点所占比例和额外创建的容错副本所占比例.于是,
Wang 和 Chen 等人 [58,59] 扩展消息传递机制,在正常运行的每个超步对顶点和其副本(包括天然副本和容错副本)间
状态进行同步;并且在每次全局同步栅前后进行快速失效检测,若失效,则通过分布在多个幸存节点上的副本并行
地恢复丢失的节点状态.最终,该方法相对全局一致检查点方法在正常运行期间带来的性能开销显著减少,仅消耗
了少量内存和通信,在实验中,该方法的性能开销仅为 0.6%~3.7%;在失效恢复阶段,由于失效节点上的顶点副本分
布在不同的幸存节点上,所以通过多个幸存节点并行地重构失效节点的状态也极为快速,在实验中,该方法在 3.4s
内将超过 100 万个顶点的作业从失效中恢复,并且相比文献[57],该方法重构的失效状态与失效前状态一样,所以
也不会增加作业的后恢复运行时间.但是,该方法仅能支持指定数量的多点失效,并且随着指定数量的增加,内存和
通信开销也会随之增加.
4.3.2 主动复制容错
在生产环境中,除了故障停止失效外,分布式图计算作业还面临着大量的拜占庭失效,这类失效很难通过简
单的心跳机制或者全局同步栅检测到.为了检测并处理一定程度的拜占庭失效,文献[60]提出了一种基于 f +1副
本的重试容错方法.首先,在加载图分区时,为每个分区创建 f+1 个副本(容忍每次超步计算出现 f 个故障),并将分
区副本放在不同的节点上运行;接着,每个超步完成计算后,各个 worker 节点将每个分区副本的状态映射成哈希
码,并将其发送给 master 节点;最后由 master 节点比较分区副本间的哈希码是否相同,若相同,则进入下一个超