Mizan

TLDR

Pregel is a scalable graph mining system that relies on graph partitioning to balance computation across nodes, but existing implementations focus mainly on this preprocessing step. This paper investigates Pregel’s runtime behavior and proposes an adaptive load‑balancing approach, introducing Mizan to better adapt to changing computational demands. Mizan monitors runtime characteristics and performs fine‑grained vertex migration without assuming prior knowledge of graph structure or algorithm behavior. The study shows that graph partitioning alone is insufficient and that Mizan yields up to 84 % performance gains on highly dynamic workloads.

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.