Distributed graph platforms like Pregel have usedvertex-centric programming models to process the growing cor-pus of graph datasets using commodity clusters. However, theirregular structure of graphs causes load imbalances acrossmachines, and this is exacerbated for non-stationary graphalgorithms where not all parts of the graph are active at thesame time. As a result, such graph platforms do not make efficientuse of distributed resources. In this paper, we decouple graphpartitioning from placement on hosts, and introduce strategiesfor elastic placement of graph partitions on Cloud VMs to reducethe cost of execution compared to a static placement, even aswe minimize the increase in makespan. These strategies areinnovative in modeling the graph algorithm's non-stationarybehavior a priori using a metagraph sketch. We validate ourstrategies for several real-world graphs, using runtime tracesfor approximate Betweenness Centrality (BC) algorithm on oursubgraph-centric GoFFish graph platform. Our strategies areable to reduce the cost of execution by up to 54 , comparedto a static placement, while achieving a makespan that is within25 of the optimal.
However, unlike stationary algorithms @cite_2 like PageRank where all vertices are active on all supersteps, non-stationary traversal algorithms like BFS have a varying frontier set of vertices that are active in each iteration. This results in an uneven workload across different machines. We address the lack of compute balancing for non-stationary algorithms here, and the associated suboptimal Cloud costs.
@cite_2
2064635301
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.