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.
Pregel has spawned Apache Giraph @cite_8 as an open source implementation, and other optimizations to its programming and execution models. Giraph++ @cite_22 , Blogel @cite_3 and our own work on GoFFish @cite_9 coarsen the programming model to operate on partitions or subgraphs, with Giraph++ using partitions, GoFFish on subgraphs (weakly connected components, WCC) and Blogel on either vertices or blocks (WCC). This gives users more flexible access to graph components that can lead to faster convergence, and also reduces fine-grained vertex-level communication. This paper aims to use elastic Cloud VMs for such component-centric systems.
@cite_9 @cite_22 @cite_3 @cite_8
2221846841 217817341 2281494333 2064635301
Distributed graph processing platforms have helped emerging application domains use commodity clusters and Clouds to analyze large graphs. Vertex-centric programming models like Google Pregel, and their subgraph-centric variants, specify data-parallel application logic for a single vertex or component that execute iteratively. The locality and balancing of components within partitions affects the performance of such platforms. We propose three partitioning strategies for a subgraph-centric model, and analyze their impact on CPU utilization, communication, iterations, and makespan. We analyze these using Breadth First Search and PageRank algorithms on powerlaw and spatio-planar graphs. They are validated on a commodity cluster using our GoFFish subgraph-centric platform, and compared against Apache Giraph vertex-centric platform. Our experiments show upto 8 times improvement in utilization resulting to upto 5 times improvement of overall makespan for flat and hierarchical partitioning over the default strategy due to improved machine utilization. Further, these also exhibit better horizontal scalability relative to Giraph. To meet the challenge of processing rapidly growing graph and network data created by modern applications, a number of distributed graph processing systems have emerged, such as Pregel and GraphLab. All these systems divide input graphs into partitions, and employ a "think like a vertex" programming model to support iterative graph computation. This vertex-centric model is easy to program and has been proved useful for many graph algorithms. However, this model hides the partitioning information from the users, thus prevents many algorithm-specific optimizations. This often results in longer execution time due to excessive network messages (e.g. in Pregel) or heavy scheduling overhead to ensure data consistency (e.g. in GraphLab). To address this limitation, we propose a new "think like a graph" programming paradigm. Under this graph-centric model, the partition structure is opened up to the users, and can be utilized so that communication within a partition can bypass the heavy message passing or scheduling machinery. We implemented this model in a new system, called Giraph++, based on Apache Giraph, an open source implementation of Pregel. We explore the applicability of the graph-centric model to three categories of graph algorithms, and demonstrate its flexibility and superior performance, especially on well-partitioned data. For example, on a web graph with 118 million vertices and 855 million edges, the graph-centric version of connected component detection algorithm runs 63X faster and uses 204X fewer network messages than its vertex-centric counterpart. The introduction of Google's Pregel generated much interest in the field of large-scale graph data processing, inspiring the development of Pregel-like systems such as Apache Giraph, GPS, Mizan, and GraphLab, all of which have appeared in the past two years. To gain an understanding of how Pregel-like systems perform, we conduct a study to experimentally compare Giraph, GPS, Mizan, and GraphLab on equal ground by considering graph and algorithm agnostic optimizations and by using several metrics. The systems are compared with four different algorithms (PageRank, single source shortest path, weakly connected components, and distributed minimum spanning tree) on up to 128 Amazon EC2 machines. We find that the system optimizations present in Giraph and GraphLab allow them to perform well. Our evaluation also shows Giraph 1.0.0's considerable improvement since Giraph 0.1 and identifies areas of improvement for all systems. 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.