FlashGraph: processing billion-node graphs on an array of commodity SSDs
Da Zhong Zheng, Disa Mhembere, Randal C. Burns, Joshua T Vogelstein, Carey E. Priebe, Alexander S. Szalay · 2015
Abstract—Graph analysis performs many random reads and writes, thus these workloads are typically performed in mem-ory. Traditionally, analyzing large graphs requires a cluster of machines so the aggregate memory exceeds the size of the graph. We demonstrate that a multicore server can process graphs of billions of vertices and hundreds of billions of edges, utilizing commodity SSDs without much performance loss. We do so by implementing a graph-processing engine within a user-space SSD file system designed for high IOPS and extreme parallelism. This allows us to localize computation to cached data in a non-uniform memory architecture and hide latency by overlapping computation with I/O. Our semi-external memory graph engine, called FlashGraph, stores vertex state in memory and adjacency lists on SSDs. FlashGraph exposes a general and flexible programming interface that can express a variety of graph algorithms and their optimizations. FlashGraph in semi-external memory performs many algorithms up to 20 times faster than PowerGraph, a general-purpose, in-memory graph engine. Even breadth-first search, which generates many small random I/Os, runs significantly faster in FlashGraph. I.