Spinner: Scalable Graph Partitioning in the Cloud

In this paper, we present a graph partitioning algorithm to partition graphs with trillions of edges. To achieve such scale, our solution leverages the vertex-centric Pregel abstraction provided by Giraph, a system for large-scale graph analytics. We designed our algorithm to compute partitions with high locality and fair balance, and focused on the characteristics necessary to reach wide adoption by practitioners in production. Our solution can (i) scale to massive graphs and thousands of compute cores, (ii) efficiently adapt partitions to changes to graphs and compute environments, and (iii) seamlessly integrate in existing systems without additional infrastructure. We evaluate our solution on the Facebook and Instagram graphs, as well as on other large-scale, real-world graphs. We show that it is scalable and computes partitionings with quality comparable, and sometimes outperforming, existing solutions. By integrating the computed partitionings in Giraph, we speedup various real-world applications by up to a factor of 5.6 compared to default hash-partitioning.


Published in:
2017 Ieee 33Rd International Conference On Data Engineering (Icde 2017), 1083-1094
Presented at:
IEEE 33rd International Conference on Data Engineering (ICDE), San Diego, CA, APR 19-22, 2017
Year:
2017
Publisher:
New York, Ieee
ISSN:
1084-4627
ISBN:
978-1-5090-6543-1
Laboratories:




 Record created 2017-07-10, last modified 2018-09-13


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)