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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings of the 13th USENIX Conference on File and Storage Technologies, FAST 2015
PublisherUSENIX Association
Pages45-58
Number of pages14
ISBN (Electronic)9781931971201
StatePublished - 2015
Event13th USENIX Conference on File and Storage Technologies, FAST 2015 - Santa Clara, United States
Duration: Feb 16 2015Feb 19 2015

Publication series

NameProceedings of the 13th USENIX Conference on File and Storage Technologies, FAST 2015

Conference

Conference13th USENIX Conference on File and Storage Technologies, FAST 2015
Country/TerritoryUnited States
CitySanta Clara
Period2/16/152/19/15

ASJC Scopus subject areas

  • Hardware and Architecture
  • Computer Networks and Communications
  • Software

Fingerprint

Dive into the research topics of 'FlashGraph: Processing billion-node graphs on an array of commodity SSDs'. Together they form a unique fingerprint.

Cite this