Mizan: A System for Dynamic Load Balancing in Large-scale Graph Processing

, , , , and
ACM EuroSys
Prague, Czech Republic,
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.
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}