High-Performance Graph Processing on NVMe SSDs via Chunk-Based Representation and Access
TL;DR
This paper introduces a novel chunk-based graph representation model, featuring classified and hierarchical vertex storage and chunk layout optimization, to improve I/O utilization and presents a latency-optimized access mechanism featuring user-space asynchronous I/O execution and hotness-aware chunk caching management to accelerate I/O and boost cache efficiency.
Abstract
Existing external graph processing systems struggle with low I/O efficiency, high computational overhead, and substantial development costs on modern NVMe SSDs, due to their reliance on complex loading and computing models that transform random I/Os into sequential access. While in-memory graph systems with general-purpose memory-storage caches (like OS page cache or TriCache) offer improved support for fine-grained I/Os and simplified programming, they often fail to leverage specific graph access patterns, resulting in suboptimal performance. This paper aims to enhance the I/O efficiency of large-scale graph processing on NVMe SSDs. We first introduce a novel chunk-based graph representation model, featuring classified and hierarchical vertex storage and chunk layout optimization, to improve I/O utilization. Additionally, we present a latency-optimized access mechanism featuring user-space asynchronous I/O execution and hotness-aware chunk caching management to accelerate I/O and boost cache efficiency. Our prototype, ChunkGraph, enables flexible graph algorithm implementation and efficient execution. Experiments demonstrate ChunkGraph significantly outperforms existing external graph systems and in-memory graph systems using general-purpose cache subsystems, delivering several-fold speedups on overall performance and superior I/O efficiency.