Mizan: A system for dynamic load balancing in large-scale graph processing

Zuhair Khayyat, Karim Awara, Amani AlOnazi, Hani T. Jamjoom, Daniel W. Williams, Panos Kalnis

Research output: Chapter in Book/Report/Conference proceedingConference contribution

201 Scopus citations

Abstract

Pregel [23] 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. © 2013 ACM.
Original languageEnglish (US)
Title of host publicationProceedings of the 8th ACM European Conference on Computer Systems - EuroSys '13
PublisherAssociation for Computing Machinery (ACM)
Pages169-182
Number of pages14
ISBN (Print)9781450319942
DOIs
StatePublished - 2013

Fingerprint

Dive into the research topics of 'Mizan: A system for dynamic load balancing in large-scale graph processing'. Together they form a unique fingerprint.

Cite this