论文部分内容阅读
由于图数据量的增长在图上计算提取知识变得越来越具有挑战性。现在的图数据集变的非常巨大,如FaceBook、twitter、人人网等的数据。传统的图处理工具难以完成这些计算。急需开发新的处理系统用于海量图数据的计算。Google基于BSP批量同步模型开发了Pregel大图处理系统。这为设计开发图处理系统提供了思路。而当今最为流行的云计算技术为此提供了技术支持。然而任何图处理系统都不能避免一个早已存在的问题即图分割的问题。特别是云计算环境下分布式并行处理需要对处理的数据进行划分为多个分区。数据被分割为多个分区由集群中的计算节点并行处理。如何实现一个好的划分依然是一个难点和极大的挑战。为了解决上述问题,我们借鉴分布式平行处理系统云计算编程模型Hadoop设计思路,基于BSP模型开发了一个可以进行大图处理的图处理系统。本文主要讨论系统其中数据划分模块设计与实现。本文主要贡献如下。第一,我们分析图计算特点,借鉴现有图处理系统的设计思路设计实现了数据划分模块。提供了完善的用户接口,用户可以灵活的设置。可以选择使用默认的划分策略或者根据接口定制他们自己的划分算法。已经整合到系统中并且工作良好;第二,我们实现了三个图数据划分算法,即基于MD5Hash的数据划分算法、针对取模Hash基于虚拟分区的平衡优化算法、Range划分算法;第三,我们实现了对多存储系统输入格式的支持。对比分析HDFS和HBase的存储设计的相似性,整合了HDFS及HBase输入格式并提供了统一的接口设计。提供了默认的输入格式,同时用户根据他们的需求定制自己的输入格式;第四,为图算法的实现提供了必备的支撑部件,如,基于RPC的多线程数据并行发送、环形缓冲区、全局同步及优化器等。实验结果和实际应用表明实现的大图处理系统中数据划分模块达到了系统设计的目标。具有良好的可扩展性和稳定性。我们从负载均衡、通信开销、时间开销三个方面对比分析了三种不同的数据划分算法的性能。结果表明优化的hash相对与未优化的具有较好的性能。数据集较好局部聚集特性的情况下Range划分算法性能最优。