Laro: Lazy repartitioning for graph workloads on heterogeneous clusters

Distributed graph processing frameworks attempt to eliminate workload imbalance among computing nodes. However, this expectation is generally challenged by underlying heterogeneous nodes and fluctuating graph workloads at runtime. This paper proposes Laro, a graph processing system using dynamic graph repartitioning that collects the actual processing times from all nodes, then reconstructs a vertices distribution with minimal migration costs in every iteration. We manifest that the Variation Coefficient of processing times is a critical metric to quantitatively characterize the workload imbalance among nodes at each iteration. Laro also presents a lazy repartitioning algorithm to improve migration efficiency. Laro has been implemented by extending GPS, a popular repartitioning-featured graph processing system. Our evaluation using real-world graphs shows that, by achieving more balanced workload distributions at runtime, Laro derives maximal speedup of 1.82x and 1.41x over the static Skewed Hash and the dynamic GPS respectively.