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

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

在某一刻所构成的全局状态可以表示为状态向量 s,向量的元素即顶点或边的值.其中,作业开始运行时由顶点
和边的初始值所构成的全局状态记作初始状态(initial state)向量 s i ;当失效发生后,顶点和边的值所构成的全局
状态记作故障状态(faulty state)向量 s e ;当作业运行结束得到完全准确的结果时,顶点和边的值所构成的全局状
态记作最终状态(final state)向量 s f ;当运行结束得到近似准确的结果时,顶点和边的值所构成的全局状态则记作
近似最终状态(approximate final state)向量 s a .其次,图中顶点和边的所有可取值的笛卡尔积所构成的状态空间,
记作全部状态(all states)集合 S;作业从初始状态 s i 开始正常执行所能达到的所有状态的集合,记作全局一致状
态(globally consistent states)集合 S GC ;介于这两者之间的包括强有效状态(strong valid states)集合 S SV 和弱有效
状态(weak valid states)集合 S WV ,当作业从某一强有效状态开始正常执行,最终能够产生完全准确的结果 [32] ,而
当作业从某一弱有效状态开始正常执行时,最终仅能产生近似准确的结果.最后,全部状态、弱有效状态、强有
效状态和全局一致状态依次是包含关系,即 SS WV S SV S GC .

Fig.4 Changes of global states in distributed graph processing jobs during failure-free execution and after failure
图 4 分布式图计算作业正常运行时和失效发生后全局状态的变化
当失效发生后,自稳定作业从任意状态开始重新计算均可到达最终状态 s f 得到完全准确的结果,典型的有
信念传播作业、图着色作业等.该类作业一般采用随机初始化图中顶点值或边值的方式开始计算,并且计算的
结果与顶点值和边值无关,因此对这类作业来说,任何状态都是强有效状态,即 S GC S SV =S WV =S.可矫正作业要求
容错机制将全局状态从失效后的故障状态 s e “修复”至某一强有效状态(图 4 中 R 2 过程)后继续计算才能最终到
达最终状态 s f (图 4 中 PR 2 过程),并得到完全准确的结果,典型的有广度优先遍历作业、单源最短路径作业和隐
式狄利克雷分布作业等.该类作业重新开始计算的强有效状态虽然不属于全局一致状态,即 S GC S SV S WV S,但
作业自身的计算逻辑能够保证最终达到最终状态 s f .此外,在分布式集群环境中,可矫正作业又被分为局部可矫
正作业和全局可矫正作业,前者在“修复”至强有效状态的过程中仅修改失效节点上的状态,而后者则涉及修改
幸存节点上的状态.全局一致作业则要求容错机制必须将全局状态从失效后的故障状态 s e “修复”至某一全局
一致状态(图 4 中 R 1 过程)后继续计算才能最终到达最终状态 s f (图 4 中 PR 1 过程),进而得到完全准确的结果,
例如,中间中心度(betweenness centrality) [33] 作业.该类作业的任一强有效状态都是全局一致状态,即 S GC =S SV 
S WV S.最后,近似作业仅需要得到近似的结果即可,例如图模式挖掘作业 [34] 、基于增量累积迭代的 PageRank 作
业 [3537] 等.该类作业不要求得到每个顶点或边的准确值,只需要一个近似的统计值或者排序,所以这类作业发生
失效后仅需要容错机制将故障状态 s e “修复”至某一弱有效状态(图 4 中 R 3 过程)后继续计算即可最终到达近似
最终状态 s a (图 4 中 PR 3 过程),并得到近似准确的结果.一般来说,自稳定作业、近似作业、局部可矫正作业、全