PaperlayerView exact revision on arXiv

Source-linked AI summary

FlashGraph: Processing Billion-Node Graphs on an Array of Commodity SSDs

Da Zheng, Disa Mhembere, Randal Burns, Joshua Vogelstein, Carey E. Priebe, Alexander S. Szalay

arXiv:1408.0500v3cs.DC

TL;DR

Massive graph analysis is difficult because random edge accesses traditionally require large aggregate memory and impose costly storage-system demands. FlashGraph keeps vertex state in memory, places edge lists on SSDs, and overlaps computation with selective, merged I/O through a user-space filesystem. It achieves performance comparable to in-memory engines across diverse algorithms, processes billion-vertex graphs on one machine, and significantly outperforms PowerGraph.

  • Problem

    Random graph reads and writes traditionally require in-memory execution, while large graphs often exceed a single machine’s memory and distributed systems require clustered resources.

  • Method

    FlashGraph uses semi-external memory: vertex state remains in RAM, edge lists reside on SSDs, and SAFS supports selective asynchronous I/O, overlap, and message-passing vertex programs.

  • Results

    FlashGraph achieves performance comparable to in-memory engines across diverse algorithms, processes 3.4 billion vertices and 129 billion edges using 22 GB of memory, and significantly outperforms PowerGraph.

  • Takeaways & Limitations

    FlashGraph provides a practical single-commodity-machine alternative for processing massive graphs that otherwise require large clusters.

  • Takeaways & Limitations

    The semi-external model requires algorithmic vertex state to remain a small constant so it can fit in memory, and FlashGraph avoids writing data to SSDs during execution.

Abstract

from arXiv · show

Graph analysis performs many random reads and writes, thus, these workloads are typically performed in memory. Traditionally, analyzing large graphs requires a cluster of machines so the aggregate memory exceeds the graph size. We demonstrate that a multicore server can process graphs with billions of vertices and hundreds of billions of edges, utilizing commodity SSDs with minimal performance loss. We do so by implementing a graph-processing engine on top of a user-space SSD file system designed for high IOPS and extreme parallelism. Our semi-external memory graph engine called FlashGraph stores vertex state in memory and edge lists on SSDs. It hides latency by overlapping computation with I/O. To save I/O bandwidth, FlashGraph only accesses edge lists requested by applications from SSDs; to increase I/O throughput and reduce CPU overhead for I/O, it conservatively merges I/O requests. These designs maximize performance for applications with different I/O characteristics. FlashGraph exposes a general and flexible vertex-centric programming interface that can express a wide variety of graph algorithms and their optimizations. We demonstrate that FlashGraph in semi-external memory performs many algorithms with performance up to 80% of its in-memory implementation and significantly outperforms PowerGraph, a popular distributed in-memory graph engine.

1 Introduction

FlashGraph addresses the difficulty of processing massive graphs whose random edge traversals strain disk and distributed-memory systems. Its semi-external design keeps vertex state in memory, stores edge lists on SSDs, and achieves near in-memory performance on very large graphs.

  • Power-law graph structure induces many small random I/Os because edges connect non-local vertices and graphs are difficult to partition effectively.
  • Disk-based graph engines scan entire datasets to avoid random I/O, wasting work when algorithms access only subsets of vertices.Breadth-first search processes frontiers, while PageRank can narrow to fewer active vertices over time.
  • FlashGraph stores vertex state in RAM and edge lists on SSDs, increasing scalability according to the graph’s edge-to-vertex ratio while enabling selective edge-list access.For the largest graph, the ratio exceeds 35 times.
  • FlashGraph uses SAFS to address SSD latency, non-uniform performance, and CPU overhead by overlapping computation with I/O and adapting caching to applications.SAFS provides a user-space SSD filesystem with asynchronous user-task I/O and lightweight caching.
  • FlashGraph selectively accesses and conservatively merges I/O requests to reduce bandwidth and CPU overhead while supporting varied algorithm access patterns.
  • A breadth-first search processed 3.4 billion vertices and 129 billion edges using 22 GB of memory on one machine.

2 Related Work

Prior graph systems use MapReduce, linear algebra, distributed vertex-centric execution, or disk scans, each fitting some workloads but limiting others. FlashGraph combines selective SSD access with a flexible vertex-centric model to broaden single-machine graph processing.

  • MapReduce-based PEGASUS expresses graph algorithms as generalized sparse matrix-vector multiplication, working relatively well for PageRank and label propagation but poorly for traversal.
  • Linear-algebra frameworks represent graphs with sparse adjacency matrices and vertex-state vectors, targeting users who can formulate problems algebraically.
  • Pregel provides distributed vertex-centric programs with bulk-synchronous processing, hiding distributed-memory complexity while running user code across a cluster.
  • GraphLab and PowerGraph use shared memory and asynchronous execution, while FlashGraph supports both SSD pulls and message-passing pushes.
  • Ligra optimizes graph traversal but is less general than several other engines and is limited by one machine’s memory capacity.
  • GraphChi and X-stream scan complete graph datasets each iteration, favoring all-vertex computation but producing suboptimal traversal performance.
  • TurboGraph selectively reads vertices and overlaps I/O with computation, but its sparse-matrix focus makes applications such as triangle counting difficult to implement.

3 Design

FlashGraph is designed to match in-memory performance while scaling beyond RAM through SSD-resident edge lists and a flexible interface. Its design prioritizes reducing data movement, exploiting parallel SSD I/O, and avoiding writes.

  • Storage model: FlashGraph stores vertex state in memory and edge lists on fast storage, using SAFS to support high IOPS and lightweight caching on SSD arrays.
  • Design goals: The design targets in-memory-like performance, semi-external scalability, and a concise interface for expressing diverse graph algorithms and optimizations.
  • I/O principles: FlashGraph reduces I/O through compact data structures, cache-hit maximization, and selective edge-list access.
  • SSD lifetime: The semi-external execution model avoids writing data to SSDs, an important design choice because repeated writes contribute to SSD wearout.
  • I/O principles: FlashGraph prioritizes reducing bytes read over sequential I/O because current SSD random I/O throughput is only two or three times lower than sequential throughput.
  • SAFS: SAFS is a user-space filesystem for high-speed SSD arrays in NUMA machines, implemented as a library in the application’s address space.
  • SAFS: SAFS’s asynchronous user-task interface lets computation run inside the filesystem and access cached data directly, avoiding buffer allocation and copying.

3.2 The architecture of FlashGraph

FlashGraph executes vertex programs iteratively over active vertices, coordinating partition workers, SSD access, and message passing. Its architecture overlaps computation and storage operations while limiting active work per thread.

  • I/O integration: FlashGraph issues SSD requests for vertex programs and pushes part of their computation into SAFS to overlap computation with I/O.
  • Execution: FlashGraph runs vertex programs in iterations, processing vertices activated in the previous iteration until no vertices remain active.
  • Execution: The graph is partitioned across worker threads, each maintaining an active-vertex queue and running scheduled vertex programs.
  • Scheduling: The scheduler controls active-vertex execution order and limits the number of running vertices in each thread.
  • Vertex states: Vertices communicate through message passing while moving among running, active, and inactive states.

3.4 Programming model

FlashGraph uses a flexible vertex-centric interface in which vertices maintain state, request edge lists explicitly, communicate through messages, and respond to events. This design overlaps computation with I/O and supports algorithms requiring communication beyond direct neighbors.

  • Vertices maintain algorithmic state and execute user-defined tasks, while affecting other vertices through messages and activation.
  • The run method executes once per active vertex and requires explicit edge-list requests, avoiding I/O for vertices that perform no computation.
  • Event-driven methods notify vertices when edge lists or messages arrive and when an iteration ends, enabling computation and I/O overlap.
  • Explicit edge-list requests and unconstrained communication let FlashGraph reduce memory traffic and express algorithms such as Louvain clustering.
  • Message passing: Message passing avoids concurrent updates to other vertices and can bundle messages to reduce synchronization overhead.
  • Message passing: FlashGraph buffers messages and uses multicast to reduce memory consumption and avoid duplicating identical messages across recipients.

3.5 Data representation in FlashGraph

FlashGraph keeps vertex-related state and graph indexing information in memory while storing edge data on SSDs. Compact, selectively organized representations reduce memory use and SSD traffic for diverse graph algorithms.

  • FlashGraph uses compact in-memory and SSD representations so larger graphs fit and more edge lists can be transferred per unit time.
  • The engine stores graph indexes, vertex state, vertex status, and per-thread message queues in memory, computing some metadata at runtime.
  • Degree-based indexing computes edge-list sizes and locations instead of storing full location and size metadata for every vertex.
  • Vertex state remains in memory and is constrained to a small constant size; breadth-first search uses one byte per vertex, while many algorithms use at most eight bytes.
  • FlashGraph stores edges and attributes in one reusable external-memory structure, keeping the representation compact because SSDs are slower than RAM.
  • For directed graphs, in-edge and out-edge lists are stored separately, while edge attributes are separated from edges to avoid unnecessary reads.

3.6 Edge list access on SSDs

FlashGraph selectively reads only requested edge lists and merges nearby I/O requests to exploit SSD random-I/O performance while limiting bandwidth and CPU overhead.

  • Graph algorithms have diverse access patterns, including own-edge-list access, whole-graph iteration, traversal, and multi-vertex edge-list requests.
  • Selective access avoids the wasted bandwidth of engines that scan every edge list during each iteration.
  • FlashGraph merges I/O requests because many active vertices are likely to request nearby edge lists during an iteration.
  • For vertices requesting their own edge lists, FlashGraph globally sorts requests and merges those targeting the same or adjacent SSD pages.
  • In the illustrated example, four requested edge lists become two I/O requests when lists share or occupy adjacent pages.
  • When vertices request multiple other vertices’ edge lists, observing more requests increases opportunities for merging and cache hits, but only a small request set can be observed.

3.7 Vertex scheduling

FlashGraph’s vertex scheduler is designed to improve both algorithm convergence and SSD access by ordering active vertices and maintaining enough concurrent work for I/O merging.

  • Vertex scheduling can accelerate convergence and improve I/O performance, with customizable schedulers for application-specific access patterns.
  • Each thread independently schedules vertices in its partition while keeping multiple vertices active so their I/O requests can be observed and merged.
  • The default scheduler orders vertices by ID to maximize merging because SSD edge lists are also ordered by vertex ID.

3.8 Graph partitioning

FlashGraph partitions graphs horizontally for parallel vertex processing and vertically for flexible edge-list access and load balancing. These runtime schemes improve locality, cache reuse, and handling of high-degree vertices.

  • Partitioning design: FlashGraph uses horizontal partitioning for all applications and flexible vertical edge-list partitioning within each horizontal partition.Horizontal partitions assign vertices for parallel processing; vertical partitions split edge lists at runtime.
  • Partitioning design: Each horizontal partition is assigned to a worker thread associated with a hardware processor, localizing vertex-state accesses.This partitioning scheme maximizes memory-access locality within each processor.
  • Horizontal partitioning: Range partitioning uses range id = vid >> r and partition id = range id % n, with tunable range size controlled by r.The parameter n denotes the number of partitions, and all vertices in a partition share one worker thread.
  • Horizontal partitioning: Adjacent edge-list placement lets per-thread scheduling issue larger I/O requests, and FlashGraph works well on graphs exceeding 100 million vertices when r is between 12 and 18.Range partitioning improves spatial locality for disk I/O; the reported r range applies to the stated large-graph observation.
  • Vertical partitioning: Vertical partitioning replicates state into vertex parts, allowing applications to split large vertices and request edge lists independently at runtime.The default scheduler executes active vertex parts by vertical partition in sequence.
  • Vertical partitioning: Vertical partitioning improves cache reuse for neighbor-access workloads and helps balance computation when a few high-degree vertices dominate.A vertex’s parts can be moved to multiple threads while avoiding simultaneous computation on the same vertex state.
  • Load balancing: A dynamic load balancer steals active vertices from other threads after finishing a thread’s own partition, continuing until the iteration has no active vertices.This addresses computational skew in scale-free graphs.

4 Applications

FlashGraph evaluates basic and complex graph algorithms spanning distinct I/O access patterns. The application set includes traversal, propagation, ranking, connectivity, triangle-counting, and scan-statistics workloads.

  • Evaluation workload: FlashGraph evaluates basic and complex graph algorithms whose I/O access patterns differ from the framework’s perspective.The varied patterns provide a comprehensive evaluation of FlashGraph.
  • Traversal and centrality: BFS activates neighbors from a single active vertex each iteration and requires only out-edge lists.The process continues until no active vertices remain.
  • Traversal and centrality: Betweenness centrality performs BFS followed by back propagation from a single source and requires both in-edge and out-edge lists.The evaluation uses one source vertex for performance measurement.
  • Propagation and ranking: PageRank sends each vertex’s latest update delta to neighbors, with a maximum of 30 iterations and progressively fewer active vertices as convergence proceeds.PageRank requires only out-edge lists.
  • I/O access patterns: BFS and betweenness centrality generate many random I/Os, PageRank and connected components are initially more sequential, and triangle counting and scan statistics are more I/O intensive.The categories reflect which vertices and edge lists each algorithm accesses during iterations.

5 Experimental Evaluation

Experiments compare FlashGraph with in-memory and external-memory engines on large real-world graphs, including a 3.4-billion-vertex, 129-billion-edge page graph. Semi-external execution retains substantial performance while enabling single-machine scale.

  • Experimental setup: The evaluation compares semi-external FlashGraph with its in-memory implementation, Galois, PowerGraph, GraphChi, and X-Stream.Experiments use large real-world graphs and measure performance loss from SSD-resident edge lists.
  • Experimental setup: The largest evaluated graph has 3.4 billion vertices and 129 billion edges, while the smallest has 42 million vertices and 1.5 billion edges.The page graph is clustered by domain, producing good cache-hit rates for some algorithms.
  • FlashGraph versus in-memory execution: Up to 80% of in-memory performance is preserved by semi-external FlashGraph with a 1GB cache, while worst-case BFS and triangle counting exceed 40% on the subdomain Web graph.BC, WCC, and PageRank show the best performance with only small degradation in external memory.
  • Resource utilization: Most applications saturate CPU before I/O, and PageRank and WCC are completely CPU-bottlenecked because their I/O is highly sequential.The observation uses an SSD array delivering around a million IOPS.
  • FlashGraph versus in-memory engines: Both FlashGraph modes perform comparably to Galois and significantly outperform PowerGraph.FlashGraph is weaker than Galois on BFS and betweenness centrality because Galois uses an algorithm that traverses fewer edges.
  • FlashGraph versus external-memory engines: FlashGraph outperforms GraphChi and X-Stream by one or two orders of magnitude by avoiding unnecessary computation and data access.GraphChi and X-Stream sequentially read the entire graph dataset multiple times.
  • Billion-scale evaluation: FlashGraph can process the billion-node page graph on a single multicore machine with a relatively small memory footprint.The page graph is described as the largest graph used to evaluate a graph-processing engine at the time, contrasting with Pregel’s 300-machine evaluation.
  • Scalability: FlashGraph’s hardware configuration can store graphs with over one trillion edges, and its small footprint suggests processing graphs with tens of billions of vertices.The stated capacity assumes attaching 24 1TB SSDs to a machine with half a terabyte of RAM.

6 Conclusions

FlashGraph combines semi-external storage, asynchronous I/O, selective edge-list access, and vertex-centric messaging to process massive graphs on a single commodity machine. These designs support varied I/O patterns while approaching in-memory performance and extending SSDs as a practical complement to RAM.

  • FlashGraph overlaps computation with I/O through an asynchronous user-task interface, reducing filesystem-access overhead.
  • Conservative I/O-request merging and vertex-processing scheduling increase throughput, reduce CPU consumption, and improve page-cache hit rates.
  • A large SSD array can deliver enough I/Os to saturate the CPU, making CPU and RAM optimization important in large-scale graph systems.
  • FlashGraph’s vertex-centric interface expresses diverse algorithms while localizing computation and avoiding concurrent access to algorithmic vertex state.
  • Selective edge-list access reduces unnecessary data movement and computation compared with streaming entire graphs.FlashGraph reads only data required by graph applications, increasing the I/O access rate to SSDs.
  • FlashGraph processes graphs with billions of vertices and hundreds of billions of edges on a single commodity machine, offering an alternative to large clusters.Its small memory footprint supports the prospect of handling still larger graphs on one machine.
Loading 1408.0500v3…