分布式多维大图迭代计算性能优化方法

大规模图的复杂挖掘算法通常需要高频迭代分析,而在计算与存储方面扩展性良好的分布式计算是提高处理效率的有效方案.然而,图顶点之间存在自由分布的边关系,会在分布式计算任务之间产生大量消息,由此在迭代过程中产生的巨大通信开销严重制约性能收益.已有工作在传统消息推送框架下采用合并和备份等技术降低通信代价,但主要面向结构简单、易优化的单维消息类算法,并不适用于结构复杂的多维消息类算法,也难以与当前最先进的消息按需拉取框架兼容.因此提出一种新型轻量级顶点备份机制,通过备份顶点的按需同步以及本地消息的按需生成,可完美继承拉取框架在容错和内存管控等方面的系统优势,同时显著降低通信代价.此外,通过考虑通信收益与负载偏斜代价,可计算最优阈值以提高整体性能.最后在大量真实数据集上验证了相关技术的有效性.

面向Flink迭代计算的高效容错处理技术

迭代计算是相同逻辑的重复执行,在各种机器学习和数据挖掘方法中被广泛使用.在大数据的处理与分析领域中,分布式迭代计算更是当前的热点研究问题之一.容错机制是分布式系统高可用性的必要保证.现有分布式系统的容错机制虽然在高可用性上表现良好,但忽略了面向迭代计算的容错效率问题.本文针对批流混合大数据计算系统Apache Flink的迭代容错效率问题,进行了系统的研究.执行流处理任务时,Flink采用“分布式快照”的检查点机制来完成容错.对于海量数据的迭代分析,检查点增加了不必要的延迟.执行批处理任务时,Flink采用从头执行任务的方式来实现容错,该方式虽然实现简单,但带来了很大的时间开销.针对以上问题,本文首先提出了一种基于补偿函数的乐观迭代容错机制.该容错机制在迭代任务发生故障时采用乐观补偿的思想恢复任务,在迭代执行过程中不采用任何额外的容错手段(不会引入额外的容错开销),采用用户自定义的补偿函数收集健康节点上的迭代数据,并结合初始的迭代数据对故障节点上丢失的分区数据进行恢复,继续执行至迭代收敛状态,保证了迭代任务的高效顺利执行.由于乐观迭代容错机制并不保证得到的结果与无故障执行得到的结果完全一致,因此针对精度要求较高的迭代任务,本文结合Flink系统的迭代数据流模型,进一步提出一种基于头尾检查点悲观迭代容错机制.与传统的阻塞检查点(阻塞下游操作符)的工作方式不同,该容错机制以非阻塞的方式编写检查点,充分结合Flink迭代数据流的特点,将可变数据集的检查点注入迭代流本身.通过设计迭代感知,简化了系统架构,降低了检查点成本和故障恢复时间.本文基于Flink系统,在大量的真实数据集和模拟数据集上,从增量迭代和全量迭代两方面对提出的两种容错机制进行了全面的实验研究,验证了本文提出的迭代容错优化技术的高效性.实验结果证实,本文基于Flink系统提出的乐观容错机制和悲观容错机制在计算效率上均优于现有的分布式迭代容错机制.前者在全量迭代计算任务中运行时间最高可提升22.8%,在增量迭代计算任务中最高可提升33.8%;后者在全量迭代任务中最高可节省15.3%的时间开销,在增量迭代任务中最高可节省18.5%的时间开销.