Design And Implementation Of A Distributed Computing System Of Graph

Graph is a kind of complicated data model.Compared with linear table and tree,graph can express more kinds of information.In real life,many scenes can be represented by graph,such as shortest path,transmission of diseases and references.Graph can also describe some new applications such as Web link relations,the composition of protein molecules,RDF data analysis and social network analysis.The size of figure data is exploding with the development of internet technology.The traditional graph data computing systems are unable to solve the storage,search,calculation and update of graph data.Therefore,designing a compact and efficient graph computing system becomes an urgently problem people needs to solve.This thesis implements the distributed computing system of graph based on the Pregel model and the Golang program language.Firstly,the local graph data-structure designed can save the graph efficiently.Meanwhile for locating the node position quickly,we propose the distributed node index structure.It can identify the unique node according to using the host ip,slave’s thread id,the hash value of node’s id and a rand number of unsigned 32-bit.It not only simplify the node storage but also improve the efficiency of query node.Secondly the structured messages,which transmit between master host and slave thread or both of slave,is put forward based on the operation object and method and implemented by RPC protocol and the communication channel.Thirdly,the operation of master and slave is dvided in the light of its business logic.Eventualy we implement the master and slave running oncurrently.The method based on Gorountine and Channel of Golang improve the system performance.Last not the least,we program the Combiner and Aggregator.The Combiner reduces the number of message passing and the Aggregator strengthens the coordination of slave.According to the above reseach and work,we implement the distributed computing system of graph.In order to verifying the validity of the system,a series of charactersistics of complex network,such as the network size,degree distribution,the max-degree,the cluster-coeffience,the assortativity coefficience and the structure entropy,are coded.Then a large number of calculation show that this system is steady and efficiently.