Scale-up Graph Processing: A Storage-centric View

The determinant of performance in scale-up graph process-ing on a single system is the speed at which the graph can be fetched from storage: either from disk into memory or from memory into CPU-cache. Algorithms that follow edges per-form random accesses to the storage medium for the graph and this can often be the determinant of performance, re-gardless of the algorithmic complexity or runtime efficiency of the actual algorithm in use. A storage-centric viewpoint would suggest that the solution to this problem lies in recog-nizing that graphs represent a unique workload and there-fore should be treated as such by adopting novel ways to access graph structured data. We approach this problem from two different aspects and this paper details two dif-ferent efforts in this direction. One approach is specific to graphs stored on SSDs and accelerates random access us-ing a novel prefetcher called RASP. The second approach takes a fresh look at how graphs are accessed and suggests that trading off the low cost of random access for the ap-proach of sequentially streaming a large set of (potentially unrelated) edges can be a winning proposition under certain circumstances: leading to a system for graphs stored on any medium (main-memory, SSD or magnetic disk) called X-stream. RASP and X-stream therefore take- diametrically opposite- storage centric viewpoints of the graph processing problem. After contrasting the approaches and demonstrat-ing the benefit of each, this paper ends with a description of planned future development of an online algorithm that selects between the two approaches, possibly providing the best of both worlds. 1