Design And Implementation On Distributed Out-of-core Graph Processing System Based On One-sided RDMA

In order to cope with the growing demand for graph processing,a large number of graph processing systems based on the BSP parallel distributed computing model have been proposed.In recent years,the distributed out-of-core graph processing system has attracted more and more interests by combining the advantages from both distributed and out-of-core graph processing systems.However,current distributed out-of-core graph processing system focuses mainly on scalability.Although its performance exceeds modern out-of-core systems,it is still far behind classical distributed graph processing system.This study uses the theoretical performance model of BSP to analyze the causes of performance problem of current distributed out-of-core graph processing system,from different angles include external memory,network and load balancing.Then,by adopting RDMA one-sided transmission technology,a distributed out-of-core graph processing system OR-Graph is proposed with both resource overlapping and load balancing.First,OR-Graph proposes a graph partitioning method that considers both load balancing and locality,thus load can be balanced while enabling intermediate data to be processed in-place and transferred on time,thereby avoiding the external storage latency and network overhead of intermediate data accessing and transferring;Second,OR-Graph introduces RDMA one-sided transmission technology,and proposes the OR-GAS computation model.By overlapping computation,transferring and storage I/O,network and a part of external storage I/Os can be performed in parallel.Besides,ring communication can also be applied,further reduces network congestion and improves bandwidth utilization.Finally,OR-Graph proposes a recursive partition method by splitting graph into multiple subgraphs to ensure that the processing scale of the system is not affected.The experimental results show that the processing performance of OR-Graph is better than current distributed out-of-core graph processing systems.The performance gain on different datasets ranges from 1.5 up to 68.29 times,while still scales as good as current distributed out-of-core graph processing systems.