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

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

4.4.1 内置补偿算法容错
与前文的局部一致检查点容错机制所面临的情况一样,全局一致检查点阻塞进程保存快照,性能开销大,与
分布式图计算框架为追求性能而采用的异步调度机制的初衷相悖;而且现有的日志容错技术,无论是 GraphX
基于 RDD 的 Lineage,还是 Pregel 的基于消息的日志容错技术,均不适合细粒度的异步计算过程,无法实现高效
的受限恢复.文献[36,37]观察到,在 Maiter 框架上可实现一类能够改写成基于增量(delta-based)累加计算过程的
分布式图计算作业 [49] ,在这类作业中,图中每个顶点的状态被初始化为两部分:顶点值和增量值,顶点值在迭代
的过程中根据入边传来的邻居顶点的增量值进行更新,而自身顶点值则沿着出边向外传播.这一过程具体为:顶
点沿出边向邻居顶点发送增量值后将自身增量值重置为初始顶点值,之后接收入边方向传来的增量值并累加
更新自身的增量值,接着用更新后的增量值和顶点当前值对顶点值进行更新,最后顶点再将增量值沿出边发送
出去,异步地迭代以上过程,直至顶点值收敛至一个固定点,作业达到终止条件.文献[36,37]通过分析这类图计算
作业,发现并证明:在迭代过程中,失效顶点的增量值已经沿着边传播在了整张图上,幸存的顶点上包含部分失
效顶点的信息,所以,当失效顶点的状态丢失后,可用幸存顶点来恢复.具体是通过重新初始化失效顶点值、利用
入边方向邻居顶点的值来计算得到失效顶点的增量值,最终自动地构建了一个失效顶点的特殊状态(弱有效状
态),基于该状态继续计算,最终可以得到几乎完全准确的作业结果.最终,该方法在成本方面实现了零性能开销
和零人力成本,在恢复效率方面,幸存节点不回滚不等待,恢复效率极为可观.
4.4.2 自定义补偿算法容错
虽然上述内置补偿算法的容错无需用户参与,但其所支持的作业范围相当狭窄,且其最终只能得到近似准
确的结果,于是在文献[32]中,Phoenix 按照失效后图计算作业对恢复状态的需求将图计算作业分为 4 类:自稳定
作业、局部可矫正作业、全局可矫正作业和全局一致作业.Dathathri 等人 [32] 对这 4 类作业的特点进行了详细的
分析和归纳,并举例说明了前 3 类作业的容错思路,并为这 3 类作业分别提供了相应的失效恢复 API,以便于用
户自己实现补偿算法进行容错.对于自稳定作业,API 以初始化函数作为输入并更新顶点状态;对于局部可矫
正作业,API 以初始化函数作为输入,同时更新顶点状态和作业中的任务工作列表;对于全局校正算法,API 通
过将初始化、重新初始化和重新计算的函数作为输入,并同时更新顶点状态和工作列表.虽然失效恢复过程
是基于 BSP 同步调度机制的,其至少需要经历一轮计算和通信从而完成失效状态的修复,然而,作业本身采用
同步或异步调度机制均可.最终,基于 Phoenix API 的用户应用程序级的容错机制在作业正常运行时无性能开
销;而在后恢复运行期间,当失效发生的迭代越早、失效节点越少时,容错机制对作业运行有加速效果;反之,
有减速效果.此外,用户在自定义实现补偿算法时,作业的类别也会影响用户需要付出的人力成本.当实现诸
如 SSSP 之类的局部可矫正作业的容错逻辑时,仅需 30 行代码,而实现诸如 k-core 和 PageRank 等全局可矫正
作业的容错逻辑时,需要 150~300 行代码,需要花费 1 人日左右的编程时间.此外,文献[61]也采用了类似的思
路,其通过扩展数据流编程模型,增添了用户自定义补偿算法的方法接口,该方法只在失效发生时执行.然而,
该方法仅支持自稳定作业和局部可矫正作业.
4.4.3 基于算法补偿的容错对比分析
表 4 列举了上述工作的优化对基于算法补偿的容错在成本、效率和质量这 3 个维度 6 个指标上的影响,并
进行了对比.从表中可以看到,在这 6 个指标上,内置补偿算法容错和自定义补偿算法容错有 4 个都是一样的,这
在一定程度上体现了基于算法补偿的容错的一些共性.首先关于零性能开销和快速恢复的特性就不再赘述了,
第 3 个共性是后恢复运行时间的不确定,因为这段时间受失效发生的时机、失效节点的数量等因素共同决定,
一般来说,当失效发生的时机越晚、失效节点的数量越多时,则失效丢失的状态越重要、越多,从而导致作业需
要更多轮次的迭代来重新计算这些丢失的状态,反之亦然.第 4 个共性是都仅能处理多点失效,而不能处理级联
失效,因为这些基于算法补偿的容错技术对失效状态的“修复”机制决定了当其遭遇级联失效时,不得不重启“修
复”机制以保证“修复”的正确性,但是,由于其快速恢复的特性,“修复”机制通过重启将级联失效当作多点失效处
理也不会耗费太多时间,于是,在实际使用中,基于算法补偿的容错能不能处理级联失效变得无关紧要.至此,内
置补偿算法容错和自定义补偿算法容错仅有两个指标是不同的,而在这两者上的权衡和取舍,产生了前后这两