Zuhair Khayyat, Karim Awara, Amani Alonazi, Hani Jamjoom, Dan Williams and Panos Kalnis
ACM EuroSys
Prague, Czech Republic, April 2013
Abstract. Pregel was recently introduced as a scalable graph mining
system that can provide significant performance
improvements over traditional MapReduce
implementations. Existing implementations focus
primarily on graph partitioning as a preprocessing
step to balance computation across compute nodes. In
this paper, we examine the runtime characteristics
of a Pregel system. We show that graph partitioning
alone is insufficient for minimizing end-to-end
computation. Especially where data is very large or
the runtime behavior of the algorithm is unknown, an
adaptive approach is needed. To this end, we
introduce Mizan, a Pregel system that achieves
efficient load balancing to better adapt to changes
in computing needs. Unlike known implementations of
Pregel, Mizan does not assume any a priori knowledge
of the structure of the graph or behavior of the
algorithm. Instead, it monitors the runtime
characteristics of the system. Mizan then performs
efficient fine-grained vertex migration to balance
computation and communication. We have fully
implemented Mizan; using extensive evaluation we
show that—especially for highly-dynamic workloads—
Mizan provides up to 84% improvement over techniques
leveraging static graph pre-partitioning.
Bibtex.
@inproceedings{jamjoom-eurosys13,
author = {Zuhair and Khayyat and Karim and Awara and Amani and Alonazi and Hani and Jamjoom and Dan and Williams and Panos and Kalnis},
title = {{Mizan: A System for Dynamic Load Balancing in Large-scale Graph Processing}},
booktitle = {ACM EuroSys},
address = {Prague, Czech Republic},
month = {April},
year = {2013}
}