FlashGraph: Processing Billion-Node Graphs on an Array of Commodity SSDs
FlashGraph: Processing Billion-Node Graphs on an Array of Commodity SSDs
复制标题
DOI：
--
复制
发表时间：
2014-08
期刊：
影响因子：
--
通讯作者：
Da Zheng;Disa Mhembere;R. Burns;J. Vogelstein;C. Priebe;A. Szalay
中科院分区：
文献类型：
--
作者：
Da Zheng;Disa Mhembere;R. Burns;J. Vogelstein;C. Priebe;A. Szalay
图分析执行许多随机读取和写入，因此，这些工作负载通常在内存中执行。传统上，分析大型图需要一组机器，因此聚合内存超过了图的大小。我们证明，多核服务器可以利用商用 SSD 以最小的性能损失处理具有数十亿个顶点和数千亿个边的图形。为此，我们在专为高 IOPS 和极端并行性而设计的用户空间 SSD 文件系统之上实现图形处理引擎。我们的半外部内存图形引擎（称为 FlashGraph）将顶点状态存储在内存中，并将边列表存储在 SSD 上。它通过与 I/O 重叠计算来隐藏延迟。为了节省I/O带宽，FlashGraph仅从SSD访问应用程序请求的边缘列表；为了增加 I/O 吞吐量并减少 I/O 的 CPU 开销，它会保守地合并 I/O 请求。这些设计最大限度地提高了具有不同 I/O 特性的应用程序的性能。 FlashGraph 公开了一个通用且灵活的以顶点为中心的编程接口，可以表达各种图形算法及其优化。我们证明，半外部存储器中的 FlashGraph 可以执行许多算法，其性能高达其内存中实现的 80%，并且显着优于 PowerGraph（一种流行的分布式内存中图形引擎）。
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.