以图结构表示的数据广泛存在于各类应用场景,大规模图分析挖掘需要利用分布式图处理系统。图处理算法一般都是迭代的,且执行时间长。在此过程中,系统中节点出现故障是常见的现象。通常,分布式图处理系统利用检查点来处理故障。在正常执行期间,系统需要周期性地写入检查点。特别地,在写入检查点时,一些系统会暂停计算过程,即阻塞式写检查点。显然,这种阻塞式写检查点方法带来了额外的运行时开销。与此不同,非阻塞式写检查点方法容许检查点的写入和计算过程同时进行,有利于降低额外开销。无论是采用阻塞式写检查点方法还是非阻塞式写检查点方法,一旦发生故障,系统读取最新的检查点处并进行回滚,以实现故障恢复。这种恢复方式要求系统在故障发生前周期性地写入检查点,因而被称为悲观恢复。与悲观恢复不同,乐观恢复并不要求系统写入任何检查点,一旦故障发生,该方式会重新载入输入数据,并通过顶点副本或用户定义的补偿函数来恢复丢失顶点的值。一般来说,上述容错技术都能有效地处理故障,然而这些技术也存在局限性。对于非阻塞式写检查点方法而言,其降低了写检查点带来的运行时开销,但可能导致资源竞争,因为检查点的写入和计算是并行的。进一步地,资源竞争会延长执行时间以及检查点的写入时间。而对于乐观恢复而言,其恢复时需重载输入数据并通过重分区来重新构建丢失的顶点和边,这会带来显著的恢复开销。为实现更为高效的容错技术,本文针对上述容错技术存在的局限性进行了研究。首先,本文关注了非阻塞式写检查点方法带来的资源竞争,说明了可通过限制系统最大并发写入的检查点数量来缓解资源竞争,并重点考虑了限制检查点写入数量后存在的积压检查点的选择问题。然后,本文研究了如何利用悲观恢复的检查点来降低乐观恢复的恢复开销,并重点关注了如何降低检查点的运行时开销以及如何选择检查点的写入时机等问题。最后,本文研发了一个原型系统,用于验证研究过程中提出的容错技术的有效性。围绕上述研究内容,本文的主要贡献如下:·提出了采用优先权的非阻塞式写检查点方法,缓解了并发写入多个非阻塞检查点导致的资源竞争。采用优先权的非阻塞式写检查点方法包括排队策略和跳跃机制两项技术。其中,排队策略用于缓解资源竞争,该策略通过用户设定的k值以及一个队列来限制系统最大并发写入的检查点数量。一旦系统并发写入的检查点数量达到k,后续的检查点便会被插入到队列中。进一步地,跳跃机制用于解决队列中积压检查点的选择问题,该机制利用了队列中检查点存在的两个特性:（i）队列中越靠后的检查点保存的状态更新,因而对系统更有益（陈旧度）;（ii）队列中写入时间越短的检查点对系统越有益（迟缓度）。在挑选检查点时,该机制优先从队列中挑选出迟缓度最小的检查点,然后再从中挑选出陈旧度最低的检查点。本文的实验表明采用优先权的非阻塞式写检查方法相比于原生的非阻塞式写检查点方法减少了 41.5%的执行时间。·设计了基于混合策略的故障恢复方式,降低了无检查点的乐观恢复方式引起的恢复开销。在乐观恢复的基础上,混合策略要求系统在载入数据后像悲观恢复一样写入一个检查点用以保存各个节点上的顶点和边。特别地,为了避免多次写入检查点带来的高昂开销,混合策略仅会写入一次检查点。此外,为了使检查点尽快可用,该策略要求系统在初始迭代处进行检查点的写入。一旦故障发生,该策略从检查点中而不是输入数据中恢复故节点上丢失的顶点和边,由此达到减少恢复开销的目的。本文的实验表明,基于混合策略的恢复方式相比于悲观恢复和乐观恢复分别减少了 5 0%和39%的执行时间。·实现了采取上述写检查点方法和故障恢复方式的分布式图处理原型系统,并针对典型图处理应用进行了容错技术演示。本文在开源的分布式图处理系统Giraph中完成了上述写检查点方法和故障恢复方式的具体技术实现,并阐述了对应原型系统的设计思路。最终,本文基于连通分量这一典型的图处理应用对本文所提出的容错技术进行了展示。综上所述,本文重点研究了现有容错技术中非阻塞式写检查点方法和乐观恢复中分别存在的资源竞争和高昂恢复开销问题。针对这两个问题,本文分别设计了采用优先权的非阻塞式写检查点方法以及基于混合策略的故障恢复方式,并最终构建了一个原型系统用于对上述写检查点方法和故障恢复方式进行展示。理论分析和实验结果表明本文的研究工作有效地缓解了非阻塞式写检查点方法带来的资源竞争,并降低了乐观恢复方式的恢复开销。