Social Graph Analytics applications are very often built using off-the-shelf analytics frameworks. These, however, are profiled and optimized for the general case and have to perform for all kinds of graphs. This paper investigates how knowledge of the application and the dataset can help optimize performance with minimal effort. We concentrate on the impact of partitioning strategies on the performance of computations on social graphs. We evaluate six graph partitioning algorithms on a set of six social graphs, using four standard graph algorithms by measuring a set of five partitioning metrics. We analyze the performance of each partitioning strategy with respect to (i) the properties of the graph dataset, (ii) each analytics computation,of partitions. We discover that communication cost is the best predictor of performance for most -but not all- analytics computations. We also find that the best partitioning strategy for a particular kind of algorithm may not be the best for another, and that optimizing for the general case of all algorithms may not select the optimal partitioning strategy for a given graph algorithm. We conclude with insights on selecting the right data partitioning strategy, which has significant impact on the performance of large graph analytics computations; certainly enough to warrant optimization of the partitioning strategy to the computation and to the dataset.
Apache GraphX implements the Bulk Synchronous Processing (BSP) model @cite_11 for graph processing. BSP was first used for large-scale graph analytics in Pregel @cite_7 introduced by Except for GraphX, there are several other Pregel-like systems for graph analytics, such as Giraph, GPS @cite_2 , Mizan @cite_1 and GraphLab. As these graph analytics frameworks aim to be generic and support any algorithm, they are often forced to generalize their design over all graph computations, resulting in sub-optimal performance compared to a hand-crafted implementation of each algorithm. @cite_23 demonstrate a huge performance gap between all the state-of-the-art graph processing frameworks and the best hand-crafted implementation, which they call the ninja gap.''
@cite_7 @cite_1 @cite_23 @cite_2 @cite_11
2281494333 217817341 1602474204 2221846841
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. 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 Bulk Synchronous Parallel (BSP) model, which divides a graphing algorithm into multiple supersteps, has become extremely popular in distributed graph processing systems. However, the high number of network messages exchanged in each superstep of the graph algorithm will create a long period of time. We refer to this as a communication delay. Furthermore, the BSP's global synchronization barrier does not allow computation in the next superstrep to be scheduled during this communication delay. This communication delay makes up a large percentage of the overall processing time of a superstep. While most recent research has focused on reducing number of network messages, but communication delay is still a deterministic factor for overall performance. In this paper, we add a runtime communication and computation scheduler into current graph BSP implementations. This scheduler will move some computation from the next superstep to the communication phase in the current superstep to mitigate the communication delay. Finally, we prototyped our system, Zebra, on Apache Hama, which is an open source clone of the classic Google Pregel. By running a set of graph algorithms on an in-house cluster, our evaluation shows that our system could completely eliminate the communication delay in the best case and can achieve average 2X speedup over Hama. 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.