Dynamic Repartitioning Based Workload Optimization Mechanism On Distributed Graph Processing System

With the development of computer and network technology, more and more interesting problems require processing graph data for real-world applications. Since the traditional single processing mode no longer fit large-scale graph computing task. Therefore, many special distributed graph processing systems have been appeared, such as Pregel, Giraph, and Graphlab. Graph partitioning plays an important role in distributed graph processing systems for achieving high efficiency on Cloud. Most of the existing distributed graph systems adopt a static partitioning to balance workload across computational nodes. Since the runtime workload may be different in each iteration for different algorithms, a static graph partitioning alone cannot keep all graph algorithms efficient for a long time in parallel on Cloud.Dynamic repartitioning is a method to handle runtime workload imbalance for achieving workload optimization. The main idea of dynamic repartitioning is automatically migrating workload from overloaded computational nodes to underloaded nodes based on runtime workload monitor. The main jobs include: first, analyzing graph behaviors by exploring the changes of active vertices, which are the vertices that a graph algorithm really needs to access in parallel computing, and then dividing graph algorithm into two categories: Stationary and Non-stationary; secondly, based on a graph's behaviors, a workload monitor will be added on each computational node to trace real-time workload for each iteration, then at the end of a iteration, every node will exchange traced workload information with other nodes; finally, according to all collected workload information, a vertex migration will be executed to reduce workload on an overloaded node.We build our evaluation on numerous real-world graph dataset and six graph algorithms to test the dynamic repartitioning mechanism's performance. According the experimental results, our method is effective to reduce imbalanced runtime workload when compared with graph system without dynamic repartitioning, and also get 50% promotion in processing graph with acceptable additional overhead. Specially, compared with stationary graph algorithm, the dynamic repartitioning is more effective in non-stationary graph algorithm.