【作者】 高峰；

【导师】 鲍玉斌；

【作者基本信息】 东北大学 ， 计算机软件与理论， 2012， 硕士

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

【Abstract】 Extracting knowledge by performing computations on graph is becoming increasingly challenge as graphs grow in size. Modern graph datasets are huge. Such as FaceBook, twitter, RenRen, the amount of data is very huge. Traditional graph processing tools are difficult to complete these calculations in such huge data set. It is urgent that a new graph processing system be developed. Google has developed a big graph processing system based on BSP model, called Pregel. This provides a guideline for the design and development of graph processing system. The most popular cloud computing technology provides technical supports for developing such system. However, any processing system can not avoid a problem that already exists that is graph partition problem. Disributed parallel processing in the cloud computing environment data need to be divided into multiple partitions. Data set is divided into multiple partitions and processed parallelly by the computeing nodes in the cluster. How to achieve a good partition remains a difficult and a great challenge.In order to solve the above problems, we borrow the idea from cloud computing programming model Hadoop which is a distributed parallel processing to develope a big graph processing system based on the BSP model that can handle large graph dataset. This thesis mainly discusses the design and implementation of data partitioning module of the system. The main contributions of this thesis are as follows. Firstly, Analysis graph computation features design and implement the data partitioning module of the system by borrowing the design idea from the existing graph process system. Provides complete user interface that users can set flexible. The users can use the default partitioning strategies or customize their own partitioning algorithms by the provided interface. Data partitioning module is working well in the system. It is integrated into the system. Secondly, we implemente three graph data paratitioning algorithms, which are range partitioning algorithm MD5-based hash partitioning algorithm, and balanced and optimized modulo hash algorithm based on virtual paratition. Thirdly, we implements the multiple imput formats support. We compare and analysis the similarity of HDFS and HBase storage design, integrate the input formats of HDFS and HBase and provides a unified interface design. The user can customize their own input format according to their needs. Finally, in order to achieve graph algorithms, wei provide the necessary support components, such as, Multi-threaded data sending based on RPC, ring buffer, global synchronization and optimizer, etc.The experimental results and the practical applications show that the data partitioning module of the big graph processing system has been implemented and reached the design goals of the system. It has good scalability and stability. We compare the performace of the three different data partitioning algorithms from load balance, communication const, time cost by many experiments. It is concoluded that the optimized and balanced hash paratitioning method has better performance. Range partitioning algorithm has the best performance when the data sets hava good local aggregation properties.更多还原