Pregel: A System for Large-Scale Graph Processing
📜 Abstract
Many practical computing problems concern large graphs. Standard examples include the Web graph and various social networks. The scale of these graphs—in some cases billions of vertices, trillions of edges—poses challenges to their efficient processing. In this paper we present a computational model suitable for this task. Programs are expressed as a sequence of iterations, in each of which a vertex can receive messages sent in the previous iteration, send messages to other vertices, and modify its own state and that of its outgoing edges or mutate graph topology. This vertex-centric approach is flexible enough to express a broad set of algorithms. The model has been designed for efficient, scalable and fault-tolerant implementation on clusters of thousands of commodity computers, and its implied synchronicity makes reasoning about programs easier. Distribution-related details are hidden behind an abstract API. The result is a framework for processing large graphs that is expressive and easy to program.
✨ Summary
Summary
Pregel introduces a distributed, vertex-centric model for large-scale graph processing. Computation proceeds through synchronized supersteps: each active vertex reads messages produced during the preceding superstep, updates its local value and outgoing edges, sends messages, and may vote to halt. This design isolates users from most distribution concerns while providing deterministic iteration boundaries and avoiding the data races and deadlocks associated with less structured asynchronous execution.
The system represents a directed graph whose vertices and edges carry user-defined values. Its C++ API supports message passing, user-defined combiners for reducing communication, aggregators for global statistics and coordination, topology mutations, and pluggable input/output formats. Graphs are partitioned across workers by vertex identifier. Workers execute vertex computations in parallel, exchange messages asynchronously in batches, and use checkpointing to recover from worker failures. The paper also describes confined recovery, which recomputes only failed partitions when the algorithm is deterministic.
The authors demonstrate the model with PageRank, single-source shortest paths, randomized bipartite matching, and semi-clustering. Experiments on up to 300 multicore commodity machines show approximately tenfold speedup when increasing worker tasks from 50 to 800 for a one-billion-vertex binary tree. Runtime increases approximately linearly with graph size in the reported low-degree experiments; a one-billion-vertex random graph with mean out-degree 127.1 was processed in slightly more than ten minutes. The results are intended to demonstrate practical scalability with relatively little implementation effort rather than optimal performance for every algorithm.
Influence
Pregel established a widely reused vertex-centric, bulk-synchronous approach for distributed graph computation. Apache Giraph explicitly describes itself as an open-source counterpart to Pregel and extended the model with features including master computation, sharded aggregators, and out-of-core processing. (giraph.apache.org) GraphX later provided graph-parallel operators expressive enough to implement the Pregel and PowerGraph abstractions, integrating this style of computation with data-parallel processing. (arxiv.org) Subsequent systems and studies, including X-Pregel and surveys of distributed graph processing, continued to treat Pregel-like vertex-centric computation as a major design point for large-scale graph analytics. (research.ibm.com) Google also described Pregel as production infrastructure for mining very large graphs, including web-scale data. (research.google)