| HAL-Inria | Publications, software ... of Inria's scientists |
Journal articles
Cost-Aware Partitioning for Efficient Large Graph Processing in Geo-Distributed Datacenters
Abstract : Graph processing is an emerging computation model for a wide range of applications and graph partitioning is important for optimizing the cost and performance of graph processing jobs. Recently, many graph applications store their data on geo-distributed datacenters (DCs) to provide services worldwide with low latency. This raises new challenges to existing graph partitioning methods, due to the multi-level heterogeneities in network bandwidth and communication prices in geo-distributed DCs. In this paper, we propose an efficient graph partitioning method named Geo-Cut, which takes both the cost and performance objectives into consideration for large graph processing in geo-distributed DCs.Geo-Cut adopts two optimization stages. First, we propose a cost-aware streaming heuristic and utilize the one-pass streaming graph partitioning method to quickly assign edges to different DCs while minimizing inter-DC data communication cost. Second, we propose two partition refinement heuristics which identify the performance bottlenecks of geo-distributed graph processing and refine the partitioning result obtained in the first stage to reduce the inter-DC data transfer time while satisfying the budget constraint. Geo-Cut can be also applied to partition dynamic graphs thanks to its lightweight runtime overhead. We evaluate the effectiveness and efficiency of Geo-Cut using real-world graphs with both real geo-distributed DCs and simulations. Evaluation results show that Geo-Cut can reduce the inter-DC data transfer time by up to 79% (42% as the median) and reduce the monetary cost by up to 75% (26% as the median) compared to state-of-the-art graph partitioning methods with a low overhead.
Cited literature [37 references]
https://hal.inria.fr/hal-02389120
Contributor : Shadi Ibrahim <>
Submitted on : Tuesday, December 3, 2019 - 2:14:41 PM
Last modification on : Tuesday, January 5, 2021 - 4:26:24 PM
Long-term archiving on: : Wednesday, March 4, 2020 - 7:33:48 PM
Contributor : Shadi Ibrahim <>
Submitted on : Tuesday, December 3, 2019 - 2:14:41 PM
Last modification on : Tuesday, January 5, 2021 - 4:26:24 PM
Long-term archiving on: : Wednesday, March 4, 2020 - 7:33:48 PM
File
graphLong_main.pdf
Files produced by the author(s)