PaperlayerView exact revision on arXiv

Source-linked AI summary

Thinking Like a Vertex: a Survey of Vertex-Centric Frameworks for Distributed Graph Processing

Robert Ryan McCune, Tim Weninger, Gregory Madey

arXiv:1507.04405v1cs.DC

TL;DR

Large-scale graph processing exposes limits in centralized and general-purpose distributed systems, especially for iterative algorithms. This survey analyzes TLAV frameworks through four components, reviews implementations, and characterizes their scalability, trade-offs, and scope.

  • Problem

    Iterative graph algorithms and billion-node graphs are poorly suited to popular Big Data systems that lack adequate graph-processing support.

  • Method

    The paper surveys vertex-centric graph processing, decomposes TLAV frameworks into timing, communication, execution-model, and partitioning components, and categorizes implementations.

  • Results

    The survey finds that TLAV frameworks provide scalable, local, and relatively simple distributed graph processing, while their performance depends on synchronization, communication, execution, and partitioning choices.

  • Takeaways & Limitations

    TLAV frameworks suit appropriately large, iterative graph problems, while subgraph-centric approaches can improve performance by broadening computation beyond individual vertices.

  • Takeaways & Limitations

    Vertex-centric algorithms are less expressive than centralized algorithms and can incur substantial synchronization and message-traffic overhead.

Abstract

from arXiv · show

The vertex-centric programming model is an established computational paradigm recently incorporated into distributed processing frameworks to address challenges in large-scale graph processing. Billion-node graphs that exceed the memory capacity of standard machines are not well-supported by popular Big Data tools like MapReduce, which are notoriously poor-performing for iterative graph algorithms such as PageRank. In response, a new type of framework challenges one to Think Like A Vertex (TLAV) and implements user-defined programs from the perspective of a vertex rather than a graph. Such an approach improves locality, demonstrates linear scalability, and provides a natural way to express and compute many iterative graph algorithms. These frameworks are simple to program and widely applicable, but, like an operating system, are composed of several intricate, interdependent components, of which a thorough understanding is necessary in order to elicit top performance at scale. To this end, the first comprehensive survey of TLAV frameworks is presented. In this survey, the vertex-centric approach to graph processing is overviewed, TLAV frameworks are deconstructed into four main components and respectively analyzed, and TLAV implementations are reviewed and categorized.

I. INTRODUCTION

Large-scale graph workloads expose limitations in centralized and MapReduce-style systems, especially for iterative algorithms. TLAV frameworks address these challenges by expressing computation locally at vertices and organizing execution through distributed components surveyed in this paper.

  • Motivation: Iterative graph and matrix algorithms often perform poorly on conventional distributed Big Data systems.Graph interdependencies and out-of-memory partitioning further make large-scale processing difficult.
  • TLAV approach: TLAV frameworks iteratively execute user-defined programs over vertices using adjacent-vertex or incoming-edge data and communicate results along outgoing edges.The first published TLAV framework, Pregel, uses synchronous execution based on BSP.
  • Execution model: BSP repeatedly performs local computation and communication in synchronized supersteps separated by global barriers.BSP uses message passing to avoid high-latency reads, deadlocks, and race conditions.
  • Model comparison: TLAV frameworks specialize the broader BSP model around vertex-centric computation, while some implementations use asynchronous execution that can improve performance in some cases.MapReduce does not natively support iterative algorithms, and iterative graph extensions can incur substantial network overhead.
  • Survey scope: The survey analyzes four principal TLAV design components, reviews distributed-system and single-machine techniques, and compares vertex-, subgraph-, and hybrid scopes.The four-component analysis identifies implementation trade-offs and provides data-driven discussion.

II. OVERVIEW

TLAV reframes graph algorithms as local vertex programs whose repeated execution can produce global results. A shortest-path example illustrates how the framework handles parallel execution and messaging while reducing the user-written computation.

  • Motivation: Centralized graph algorithms assume the entire graph is randomly accessible in memory, an assumption that fails as graph size exceeds one machine’s capacity.TLAV instead uses local, bottom-up computation within distributed algorithms.
  • Vertex-centric model: A TLAV vertex program receives a vertex’s data plus adjacent-vertex and incident-edge data, executes synchronously or asynchronously, and halts after convergence or a fixed iteration count.This local computation can nevertheless produce a global result.
  • Scalability: TLAV frameworks provide a common interface that abstracts parallel vertex-program execution and can scale linearly with the number of vertices.Pregel runtime has been shown to scale linearly with vertices on 300 machines.
  • Example: For single-source shortest path, each vertex passes the minimum incoming value to outgoing edges during each superstep, while the framework manages synchronization and parallel execution.The user writes only the vertex-program portion of the algorithm.
  • Example: The shortest-path execution activates vertices when messages arrive, updates distances from the smallest received value, and leaves vertices inactive when no new messages are received.Figure 3 depicts this message-driven progression across supersteps.

III. FOUR PILLARS OF TLAV FRAMEWORKS

TLAV frameworks are organized around interdependent design pillars that determine how vertex programs are scheduled, communicate, executed, and distributed across worker memory. The survey introduces these pillars alongside a synchronized shortest-path example.

  • Framework structure: A TLAV framework supports iterative execution of user-defined vertex programs, with component choices jointly influencing execution and system performance.The survey emphasizes that the components are tightly integrated rather than independent.
  • Running example: The synchronized shortest-path algorithm initializes distances, activates the source, and repeatedly processes vertices in parallel under BSP-style barriers.The algorithm’s input is a graph G=(V,E), and inactive vertices become active when messages arrive.
  • Four pillars: The four principal pillars are timing, communication, execution model, and partitioning.They respectively address scheduling, data accessibility, execution flow, and distribution of graph data.
  • Implementation concerns: Partitioning places graph vertices across worker-machine memory, while execution-model choices determine how computation and data flow use the underlying hardware.The survey treats partitioning and execution as connected design decisions.

A. Timing

TLAV timing may be synchronous, asynchronous, or hybrid. Synchronous execution offers determinism and scalability but can lose efficiency when synchronization waits for stragglers or when neighbor coordination prevents convergence.

  • Timing models: TLAV timing determines how active vertices are scheduled and may be synchronous, asynchronous, or hybrid.The timing policy is separate from the logic of the vertex program.
  • Synchronous timing: Synchronous execution organizes parallel vertex computation into supersteps separated by global barriers that restrict each step to data from the previous one.Vertices within a processing unit may execute in fixed or random order without changing program state.
  • Synchronous timing: Synchronous systems are deterministic, conceptually simple, scalable, and often exhibit runtime that increases linearly with the number of vertices.Batch messaging can improve efficiency in synchronous systems.
  • Trade-offs: Over 80% of total running time was attributed to synchronization in one highly partitioned shortest-path instance.Synchronous supersteps also wait for the slowest vertex, making them sensitive to stragglers and workload imbalance.
  • Trade-offs: Synchronous execution may fail to converge for some neighbor-coordination algorithms unless extra logic is added to the vertex program.Graph coloring is given as an example in which neighboring vertices can continually exchange colors.

2. Asynchronous

Asynchronous execution removes global barriers and adapts scheduling to uneven workloads, often improving performance, but it increases scheduling and consistency complexity. Hybrid and adaptive designs seek to balance synchronization costs with redundant computation and changing workload conditions.

  • Asynchronous execution: Asynchronous execution lets active vertices run when resources are available, eliminating explicit barriers and the straggler problem.Execution order can be dynamically generated by the scheduler.
  • Performance trade-offs: Asynchronous systems generally outperform synchronous systems on imbalanced workloads, while synchronous execution better accommodates I/O-bound algorithms.Asynchronous execution suits CPU-bound algorithms with large and variable workloads, but cannot use batch messaging optimizations.
  • Performance trade-offs: PageRank shows asymmetric convergence: most vertices converge within one superstep, while only 3% require more than 10 supersteps.Prioritized computation can focus early on the more challenging vertices.
  • Limitations: Asynchronous execution may perform unnecessary vertex updates and redundant communication when neighboring values remain unchanged.These inefficiencies can arise particularly with pull-based execution.
  • Limitations: Asynchronous systems require additional scheduling and consistency mechanisms, including protection against data races and user-selected consistency models.GraphLab users may need to consider low-level concurrency issues when selecting a consistency model.
  • Hybrid execution: Hybrid designs reduce synchronization costs by separating global communication from local computation or by combining bounded asynchronous execution with synchronous rounds.GraphHP, P++, and KLA trade expensive global synchronization against potentially redundant asynchronous computation.
  • Hybrid execution: GRACE prioritizes vertices and selectively receives messages within a synchronous round, achieving runtime comparable to asynchronous models with better single-machine multithreaded scaling.Its scheduling operates inside a single synchronous superstep.
  • Adaptive execution: PowerSwitch adaptively switches execution modes using throughput heuristics and online sampling, with reported improvements in runtime across algorithms and system configurations.The reported results indicate accurate throughput prediction and well-timed switching.

B. Communication

TLAV frameworks communicate vertex data through message passing or shared memory, with implementations differing in routing, synchronization, caching, and partitioning. Message passing offers consistency and batching, while shared memory can reduce communication overhead but introduces consistency, partitioning, and scalability challenges.

  • Communication models: TLAV communication uses message passing or shared memory to exchange data between vertex programs.Message passing exchanges data through messages, whereas shared memory exposes data directly between processes.
  • Communication models: Figure 4 compares Pregel, GraphLab, PowerGraph, and GRE communication patterns on a graph partitioned across two machines.Vertices A, B, and C are assigned to p1, while D, E, and F are assigned to p2, with exceptions for the vertex-cut layouts.
  • Message passing: Message passing sends local vertex data to recipient vertex IDs, with outgoing edges typically providing the destination IDs.Worker processes route messages either to local queues or remote-machine buffers.
  • Message passing: Synchronous message passing guarantees data consistency, enables batch messaging, and can significantly outperform asynchronous execution for I/O-bound algorithms such as PageRank.Messages sent in superstep S are received in superstep S + 1.
  • Shared memory: Shared memory directly exposes vertex data, avoiding message overhead and intermediate worker processing, but distributed implementations must maintain consistency.Shared memory is often used in single-machine TLAV frameworks because remote consistency is difficult.
  • Shared memory: Shared-memory frameworks use locking or serializable schedules to manage races, and GiraphX converges 35% faster than Giraph on PageRank over a large Web Graph.GraphLab uses cached ghost vertices, while PowerGraph maintains consistency across mirrors of cut vertices.
  • Shared memory: Ghost vertices can proliferate when high-degree vertices make scale-free graphs difficult to partition.This is a disadvantage of shared-memory frameworks using neighboring remote-vertex copies.
  • Shared memory: Asynchronous shared memory may improve speed through prioritized execution and low communication overhead, but locking costs can challenge scalability as partitions increase.More machines and partitions can require additional time and resources for locking protocols.

3. Active Messages

Active messages bring computation to data by combining message contents with their operators, while GRE’s Agent-Graph reduces inter-machine messaging. These techniques can improve runtime and network efficiency, but optimization benefits depend on message structure and algorithmic assumptions.

  • Active Messages: Active messages combine data with the operator applied at the destination vertex, executing asynchronously upon receipt.In GRE, this removes separate message queues and intermediate state.
  • Agent-Graph: GRE’s Agent-Graph adds combiner and scatter vertices so a source can send one network message that is redistributed locally.This reduces inter-machine messaging by moving distribution to an internal scatter vertex.
  • Message Passing Optimizations: Message-reduction strategies target costly network communication through combiners, receiver-side scatter, and algorithm-specific restructuring.Combiners require commutative and associative computation, while receiver-side scatter requires identical messages independent of adjacency lists.
  • Message Passing Optimizations: A ten-fold reduction in network traffic from receiver-side scatter produced a 1.5 times speedup in Pregel.The survey notes that receiver-side scatter is effective but not guaranteed to improve performance.

C. Execution Model

TLAV execution models specify how vertex functions compute and move data, ranging from one-, two-, and three-phase vertex programs to edge-centric processing. These choices can interact with other framework components and graph characteristics to affect performance.

  • One Phase: One-phase vertex programming accesses input data, computes a new vertex value, and distributes the update.Pregel exemplifies this model through a single compute function operating on incoming messages.
  • Two Phase: Two-phase Scatter-Gather separates distributing vertex values from collecting inputs and applying vertex updates.GRE’s Scatter-Combine model is a related two-phase design using active messages.
  • Three Phase: PowerGraph’s three-phase Gather-Apply-Scatter model combines inputs, updates the central vertex, and distributes the result along outgoing edges.The gather operation performs a generic commutative, associative summation.
  • Edge-Centric: X-Stream uses an edge-centric two-phase model that iterates over edges while operating on source and target vertices.Its edge-centric design uses streaming edge data rather than vertex iteration.
  • Push and Pull: Push mode sends updates outward from active vertices, whereas pull mode reads neighboring data inward at the active vertex.Some frameworks allow users to choose between these modes, and Ligra dynamically switches based on a threshold.
  • Delta-Caching: Delta-caching tracks accumulator changes to avoid activating neighbors for small updates and reduced PageRank runtime on Twitter by 45%.The optimization requires a commutative, associative apply function with an inverse.

D. Partitioning

TLAV partitioning places large graphs across distributed memory while balancing workload and limiting inter-partition edges. The survey contrasts costly centralized methods with scalable streaming and distributed heuristics.

  • Partitioning Goals: Effective partitioning balances vertices across partitions while minimizing inter-partition edges, but k-way graph partitioning is NP-complete.Poor partitioning can increase network traffic and processing cost.
  • Centralized Partitioning: METIS provides near-optimal partitions but becomes impractical for medium-size graphs because of preprocessing cost and whole-graph random-access requirements.Its communication and runtime benefits are more applicable to smaller graphs.
  • Streaming Partitioning: Streaming partitioning assigns graph data in a single pass during graph loading, making it efficient for placing vertices onto cluster workers.The centralized graph loader decides each vertex’s final worker placement as it reads the stream.
  • Streaming Heuristics: LDG assigns vertices to partitions using neighbor connectivity weighted by a penalty for remaining partition capacity.It is identified as one of two top-performing greedy streaming heuristics.
  • Streaming Heuristics: FENNEL can produce high-quality partitions that are sometimes comparable with near-optimal METIS partitions.Both FENNEL and LDG have also been adapted to restreaming partitioning.

3. Vertex Cuts

Vertex cuts partition edges rather than vertices, allowing high-degree vertices to span machines and reducing imbalance in power-law graphs. Dynamic repartitioning addresses changing active-vertex workloads, but its overhead often limits practical gains.

  • Vertex Cuts: Vertex cuts assign edges to machines while allowing vertices to span multiple machines, communicating changes to cut-vertex values rather than edges.This approach targets balanced edge cuts in power-law graphs.
  • PowerGraph: PowerGraph combines vertex cuts with Gather-Apply-Scatter, using master and mirror copies to coordinate updates across machines.Mirrors send gathered values to a master, which applies the update and returns it before scattering.
  • Vertex-Cut Frameworks: GraphX’s adoption of vertex cuts demonstrated an 8-fold decrease in communication cost.Vertex-cut strategies were also incorporated into GraphBuilder and other frameworks.
  • Edge Partitioning: Edge partitioning was empirically shown to outperform vertex partitioning, with a streaming least-marginal-cost heuristic outperforming PowerGraph’s greedy heuristic.The comparison concerns expected partitioning costs and empirical performance.
  • Partitioning Limits: Centralized hypergraph partitioning is NP-hard, and exact algorithms and centralized heuristics are too expensive for large-scale graphs.This motivates distributed approaches for large-scale edge partitioning.
  • Dynamic Repartitioning: Dynamic repartitioning migrates vertices between workers when active-vertex counts become imbalanced during computation.The strategy must address vertex selection, migration timing, and locating reassigned vertices.
  • Dynamic Repartitioning: Dynamic repartitioning often provides minor or negative runtime improvements because migration overhead can outweigh network-I/O reductions.Reported evaluations found GPS detrimental in all tested cases, though PageRank is a poor test because all vertices remain active.

IV. IMPLEMENTATION

TLAV implementations combine distributed architecture, execution coordination, partitioning, and fault tolerance to process large graphs across workers. Their designs range from master-slave coordination and synchronous checkpointing to alternative recovery mechanisms.

  • Architecture: TLAV frameworks generally use a master-slave architecture in which the master initializes workers, coordinates execution, and often loads and partitions the graph.The master also stores global values such as aggregators; loading and partitioning may be parallelized with a network filesystem.
  • Architecture: XPregel is a notable exception that uses X10’s asynchronous partitioned global address space, while still implementing a master-slave structure.Its runtime provides local “places” that support distributed and parallel programming.
  • Execution: Multi-core TLAV systems improve resource use through multi-threading, including XPregel subpartitions and scheduler-based or specialized thread designs.Pregel-style systems may assign one partition per core, whereas multi-threading divides work more finely.
  • Partitioning: Dynamic repartitioning addresses active-vertex imbalance caused by topology changes, algorithm execution, or both, and the surveyed implementations are synchronous.Strategies select vertices for reassignment, locate reassigned vertices, and should avoid densification.
  • Fault tolerance: Checkpointing protects distributed computation by saving immutable graph states, allowing Pregel to roll back and reload partitions after failure.Pregel checkpoints between supersteps and resumes the entire system from the latest saved point.
  • Fault tolerance: Alternative fault-tolerance designs replicate vertices or redistribute checkpointed partitions to accelerate recovery and balance load.The Imitator uses vertex replicas, while partition-based recovery can reassign partitions across new and healthy nodes.

D. Single Machine Architectures

Single-machine graph systems trade distributed infrastructure for specialized memory and storage techniques that make large-scale processing feasible. Their designs emphasize compact layouts, sequential or asynchronous I/O, and alternative computational scopes.

  • Motivation: Single-machine TLAV systems are easier to manage and program, but commodity machines lack enough memory for many large-scale graphs.Processing therefore depends on substantial memory or efficient out-of-memory access.
  • Storage: Compressed sparse row layouts organize outgoing adjacency sets for fast edge lookup and are common in shared-memory graph processors.Novel data layouts are central because out-of-memory performance depends on efficient graph reads and writes.
  • Frameworks: GraphChi uses Parallel Sliding Window to partition vertices into intervals whose incoming edges are stored in balanced, source-sorted shards.The layout supports large-scale processing on a commodity desktop.
  • Frameworks: X-Stream uses streaming edge data and an edge-centric Scatter-Gather model, reporting processing of a 64-billion-edge graph on one machine with two 3TB disks.Its testbed found disk streaming 500 times faster than random access.
  • Frameworks: FlashGraph combines asynchronous message passing, vertex-centric programming, and semi-external memory, with vertices and algorithmic state in RAM and edges stored externally.It outperformed GraphChi and XStream by orders of magnitude in the cited experiments, including when their data was placed in RAM-disk.
  • Alternative scope: TLAV systems scale broadly, but subgraph-centric systems may provide better performance by reducing the scope of sequential algorithms without losing distributed scalability.This reflects a trade-off between computational scope and scalability.
  • Alternative scope: Subgraph-centric frameworks can improve performance by fitting subgraphs in memory while exchanging messages across their boundaries.Block-based GRACE improved locality and cache hits while reducing memory access time for computationally light algorithms such as PageRank.

B. Other Scopes: Paths and Sets

Graph systems can use computational scopes larger or differently structured than individual vertices, including traversal paths, vertex subsets, serial finishing, and single-pivot processing. These alternatives address expressiveness, messaging, or convergence costs, while the survey also distinguishes TLAV systems from databases and MapReduce.

  • Paths: PathGraph partitions graphs into forward and reverse traversal trees and exposes path-centric scatter and gather functions.The model targets traversal-heavy algorithms such as PageRank and Bellman-Ford shortest path.
  • Sets: Ligra uses a vertex-subset interface with a global graph view and dynamically switches between sparse and dense edge representations.The representation choice affects whether push or pull operations are used.
  • Optimizations: Finishing Computation Serially switches to a single-machine computation when the remaining active graph fits in memory after slow convergence.The optimization targets algorithms with a shrinking active-vertex set.
  • Optimizations: Single Pivot reduces messaging for breadth-first-search-based algorithms by selecting one random vertex instead of starting BFS from every vertex.The approach relies on most graphs having one large connected component alongside many smaller ones.
  • Related systems: Graph databases focus on transactional processing and local or online queries, whereas TLAV systems iteratively process entire graphs offline in batch.The distinction remains despite both treating vertices as first-class entities and facing partitioning problems.
  • Related systems: MapReduce abstracts distributed programming but does not directly address iterative or graph processing, and filesystem I/O makes repeated computation inefficient.Extensions support iteration but remain agnostic to graph-processing challenges.
  • Survey scope: The survey compares TLAV framework components because changing them affects performance and runtime characteristics without generally changing algorithm design or results.It presents TLAV systems as platforms for executing vertex-centric algorithms while hiding lower-level cluster details.

VII. CONCLUSIONS

TLAV frameworks reduce graph computation to local-neighborhood updates, supporting scalable distributed processing through communication among workers. The survey concludes that computational scope creates a scalability–expressiveness trade-off and that subgraph-centric methods may offer better performance for suitable problems.

  • Conclusions: Vertex-centric computation reduces each update to immediate-neighbor data and allows workers to obtain remote data directly rather than relying on central coordination.The survey identifies timing, communication, execution model, and partitioning as four pillars of the model.
  • Conclusions: Reducing computational scope increases scalability, but vertex-centric algorithms are less expressive and require many relatively slow messages.Centralized algorithms require too much memory, while subgraph-centric methods occupy an intermediate scope.
  • Conclusions: Subgraph-centric processing can retain scalability while executing sequential algorithms on subgraphs small enough to fit in memory.Its effectiveness depends closely on large-scale graph partitioning, including streaming and distributed approaches.
  • Conclusions: TLAV frameworks are appropriate for some large-scale graph problems because they are simple to program and easy to distribute, but not every graph or problem requires distributed iterative processing.The conclusion presents subgraph-centric frameworks as a further performance step beyond vertex-centric systems.
Loading 1507.04405v1…