论文部分内容阅读
随着“大数据时代”的到来,各种处理海量数据的技术应运而生,其中以Hadoop为代表的传统MapReduce模型正在逐渐成为行业的标准。然而,本质上,MapReduce模型的处理方式还是一种批处理的流程,所以,并非所有结构的数据都能高效的在传统MapReduce模型上进行处理,尤其是具有图结构类型的数据集,这就需要一种可以高效处理该类数据的计算模型。本文首先简要讨论了一种分布式迭代计算模型。通过对DPark(一种分布式迭代计算框架,由豆瓣公司开发,是Spark的Python版本,并加入自身特色)的研究,了解其工作原理以及核心技术RDD(弹性分布式数据集)。其次,由于许多实际应用问题中都涉及到大型的图算法,比如网页链接关系和社会关系图等,这些图都有相同的特点:规模超大,常常达到数十亿的顶点和上万亿的边。这么大的规模,给需要在其上进行高效计算的应用提出了巨大的难题。对此,Google提出了Pregel图计算模型,但目前为止国内还没有完全实现Pregel的图计算引擎,所以本文主要在对分布式迭代模型研究的基础上,根据Google关于Pregel的论文,研究并实现一种高效的图计算引擎PyGel,该引擎主要使用Python开发,基于DPark这一分布式迭代计算框架,可用于类似图遍历(BFS)、单源最短路径(SSSP)、PageRank等图算法方面的计算。然后,选取代表性的PageRank这一图算法,分别在传统分布式计算模型与基于分布式迭代模型的PyGel上实现,通过对比二者的计算效率来验证最终结论,并给出相关的比较数据。最后,通过研究当前分布式迭代计算模型以及Pregel图计算模型的概念和具体实现,指出其中可能存在的不足,以及可能的改进方式,并明确以后的工作方向。