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

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

[7]
scatter-gather(SG)模型(也称为 signal/collect 模型 [29] )以及 3 段的 gather-apply-scatter(GAS)模型 等.在 SG 模型
中,用户需要在 Scatter 接口方法中实现顶点产生要发往其他顶点的消息的计算逻辑,在 Gather 接口方法中实现
利用接收到的消息更新自身顶点值的计算逻辑;在 GAS 模型中,用户需要在 Gather 接口方法中实现在顶点的边
和邻居顶点的子集上产生局部值的计算逻辑,在 Apply 接口方法中实现累加 Gather 阶段并行产生的多个局部值
并更新自身顶点值的计算逻辑,最后在 Scatter 接口方法中实现依据更新后的顶点值更新边值的计算逻辑.虽然
不同的编程模型有不同的适用场景,但总的来说,友好的编程模型大大简化了用户对分布式图计算作业的实现.
亦受益于此,相较于在需要用户自己处理计算并行、数据切分、节点通信等问题的专用程序上实现用户应用程
序级的容错机制 [30,31] ,基于采用以上编程模型的用户应用程序加以实现更为简单和便利.
其次,在分布式图计算作业提交后需要加载数据进行计算,而图分区(partitioning)则是数据加载的第 1 步,
选择将图划分成多少个分区,并决定哪些边或顶点属于一个分区.而如何将图切开(cut),则是图分区面临的第 1
个问题,目前图分区主要基于 3 种图切分(cut)方法,分别是边切分(edge-cut)、顶点切分(vertex-cut)和混合切分
(hybrid-cut).其中,边切分是指在分区过程中把边“剪断”,从而可以将顶点分配在不同的机器上,如图 3(b)所示,图
中的顶点 A、B 和 C 与顶点 D、E 和 F 分别分配在了机器 M1 和 M2 上.然而边切分对高度(high-degree)顶点是
不合适的.在计算过程中,高度顶点需要和大量分布在其他机器上的邻居节点通信,这会造成网络负载的不均
衡,从而影响计算性能,而顶点切分则能改善这一问题.如图 3(d)所示,在分区过程中将顶点“切开”,将边分配在不
同的机器上,并从被切成多份的顶点中选择一份作为 master,其余作为 mirror.搭配 GAS 编程模型,在计算过程
中,mirror 在各自机器上完成局部计算,将结果汇总至 master 进行更新后,再将更新结果同步至 mirror 上.但是,
采用顶点切分对低度(low-degree)顶点是不合适的,master 与 mirror 之间的汇总-同步过程反而带来了额外的开
销,因此低度顶点更适合边切分,于是混合切分方法应运而生.通过设置合理的阈值将图中顶点分为高度和低度
两类,混合切分方法对高度顶点采用顶点切分,对低度顶点采用边切分,综合了边切分和顶点切分的优势,从而
提高了作业的整体性能.从容错的角度看,图切分的重要意义在于其在系统中为大量顶点创建了副本,实现了状
态冗余,虽然图切分方法和图分区策略通常会极力减少冗余,但这并不容易,充分利用已有的状态冗余是面向分
布式图计算作业的容错技术的一个重要的优化方向.
接着,在数据加载进内存后,用户编写的计算逻辑结合输入数据实例化成一组互相依赖的任务.作业的执行
过程就是对这些任务进行迭代、反复调度执行的过程.任务调度(scheduling)组件采用不同的调度机制将任务按
照一定的顺序调度到 CPU 上进行计算,目前主流的任务调度机制有同步调度机制和异步调度机制.同步调度机
制一般基于整体同步并行(bulk synchronous parallel,简称 BSP)计算模型实现,作业计算的整个过程按照迭代轮
次被全局同步栅划分成多个超步,每个超步开始的时候,所有任务均处于同一个迭代轮次.同步调度机制设计简
单、可扩展性强,但在并行计算中全局同步栅引入了相当的性能开销.而在异步调度中,每个任务所能使用的数
据可以是其他任务迭代产生的最新结果,这样计算快的任务无需等待落后任务即可继续进行计算,从而提升了
作业整体的执行效率.然而,异步调度机制为了保证数据的一致性,避免读写冲突,需要引入额外的控制机制,如
版本控制、分布式锁机制等,这增加了分布式图计算框架设计的复杂性,也为计算引入了额外开销.从容错的角
度来看,调度机制是面向分布式图计算作业容错技术优化时的重要考量,一方面,调度机制会影响容错机制对作
业状态的管理,例如借助同步调度机制的全局同步栅可以方便地获得作业的全局一致状态;另一方面,调度机制
也一定程度地反映了作业对结果准确度的需求程度.例如,一般基于异步调度机制的作业仅需要近似准确的结
果,容错机制可以借此实现更高效的近似恢复.
最后,通信(communication)组件负责任务间的数据交换,目前,主流的通信机制包括消息传递(massage-passing)、
共享内存(shared-memory)和数据流(dataflow)这 3 种.其中,消息传递机制主要利用网络通信协议在任务间交换
消息完成数据的交换,如图 3(b)所示,其天然地契合边切分;共享内存机制则是通过将每个任务所需要的数据以
共享变量的方式保存在本地机器上,从而实现直接的本地读写以避免远程读写,其结合异步调度机制可以实现
更高的计算效率,如图 3(d)所示,其天然地契合顶点切分;当结合边切分使用时,如图 3(c)所示,需要在本地机器上
为远程邻居顶点创建 ghost 顶点实现本地读写;数据流机制主要是应用在基于通用分布式数据流框架的高层图计