A disk I/O optimized system for concurrent graph processing jobs

Abstract

In order to analyze and process the large graphs with high cost efficiency, researchers have developed a number of out-of-core graph processing systems in recent years based on just one commodity computer. On the other hand, with the rapidly growing need of analyzing graphs in the real-world, graph processing systems have to efficiently handle massive concurrent graph processing (CGP) jobs. Unfortunately, due to the inherent design for single graph processing job, existing out-of-core graph processing systems usually incur unnecessary data accesses and severe competition of I/O bandwidth when handling the CGP jobs. In this paper, we propose GraphCP, a disk I/O optimized out-of-core graph processing system that efficiently supports the processing of CGP jobs. GraphCP proposes a benefit-aware sharing execution model to share the I/O access and processing of graph data among the CGP jobs and adaptively schedule the graph data loading based on the states of vertices, which efficiently overcomes above challenges faced by existing out-of-core graph processing systems. Moreover, GraphCP adopts a dependency-based future-vertex updating model so as to reduce disk I/Os in the future iterations. In addition, GraphCP organizes the graph data with a Source-Sorted Sub-Block graph representation for better processing capacity and I/O access locality. Extensive evaluation results show that GraphCP is 20.5× and 8.9× faster than two out-of-core graph processing systems GridGraph and GraphZ, and 3.5× and 1.7× faster than two state-of-art concurrent graph processing systems Seraph and GraphSO.

Graphical abstract

Keywords

graph processing / disk I/O / concurrent jobs

References

[1] Malewicz G, Austern M H, Bik A J C, Dehnert J C, Horn I, Leiser N, Czajkowski G. Pregel: a system for large-scale graph processing. In: Proceedings of 2010 ACM SIGMOD International Conference on Management of Data. 2010, 135−146

[2] Low Y, Bickson D, Gonzalez J, Guestrin C, Kyrola A, Hellerstein J M . Distributed GraphLab: a framework for machine learning and data mining in the cloud. Proceedings of the VLDB Endowment, 2012, 5( 8): 716–727

[3] Gonzalez J E, Low Y, Gu H, Bickson D, Guestrin C. PowerGraph: distributed graph-parallel computation on natural graphs. In: Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation. 2012, 17−30

[4] Zhu X, Chen W, Zheng W, Ma X. Gemini: a computation-centric distributed graph processing system. In: Proceedings of the 12th USENIX Conference on Operating Systems Design and Implementation. 2016, 301−316

[5] Kyrola A, Blelloch G, Guestrin C. GraphChi: large-scale graph computation on just a PC. In: Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation. 2012, 31−46

[6] Roy A, Mihailovic I, Zwaenepoel W. X-stream: edge-centric graph processing using streaming partitions. In: Proceedings of the 24th ACM Symposium on Operating Systems Principles. 2013, 472−488

[7] Zhu X, Han W, Chen W. GridGraph: large-scale graph processing on a single machine using 2-level hierarchical partitioning. In: Proceedings of 2015 USENIX Conference on Usenix Annual Technical Conference. 2015, 375−386

[8] Vora K. LUMOS: dependency-driven disk-based graph processing. In: Proceedings of 2019 USENIX Conference on Usenix Annual Technical Conference. 2019, 429−442

[9] Chen R, Shi J, Chen Y, Zang B, Guan H, Chen H . PowerLyra: differentiated graph computation and partitioning on skewed graphs. ACM Transactions on Parallel Computing, 2019, 5( 3): 13

[10] Cheng Y, Wang F, Jiang H, Hua Y, Feng D, Zhang L, Zhou J . A communication-reduced and computation-balanced framework for fast graph computation. Frontiers of Computer Science, 2018, 12( 5): 887–907

[11] Zhang Y, Liao X, Jin H, Gu L, He L, He B, Liu H. Cgraph: a correlations-aware approach for efficient concurrent iterative graph processing. In: Proceedings of 2018 USENIX Conference on Usenix Annual Technical Conference. 2018, 441−452

[12] Xue J, Yang Z, Qu Z, Hou S, Dai Y. Seraph: an efficient, low-cost system for concurrent graph processing. In: Proceedings of the 23rd International Symposium on High-Performance Parallel and Distributed Computing. 2014, 227−238

[13] Xue J, Yang Z, Hou S, Dai Y . Processing concurrent graph analytics with decoupled computation model. IEEE Transactions on Computers, 2017, 66( 5): 876–890

[14] Zhao J, Zhang Y, Liao X, He L, He B, Jin H, Liu H, Chen Y. GraphM: an efficient storage system for high throughput of concurrent graph processing. In: Proceedings of International Conference for High Performance Computing, Networking, Storage and Analysis. 2019, 3

[15] Xu X, Wang F, Jiang H, Cheng Y, Feng D, Zhang Y, Fang P. GraphCP: an I/O-efficient concurrent graph processing framework. In: Proceedings of the 29th IEEE/ACM International Symposium on Quality of Service. 2021, 1−10

[16] Ai Z, Zhang M, Wu Y, Qian X, Chen K, Zheng W. Squeezing out all the value of loaded data: an out-of-core graph processing system with reduced disk I/O. In: Proceedings of 2017 USENIX Conference on Usenix Annual Technical Conference. 2017, 125−137

[17] Zhu R, Zhao K, Yang H, Lin W, Zhou C, Ai B, Li Y, Zhou J . AliGraph: a comprehensive graph neural network platform. Proceedings of the VLDB Endowment, 2019, 12( 12): 2094–2105

[18] Maleki S, Nguyen D, Lenharth A, Garzarán M, Padua D, Pingali K. DSMR: a parallel algorithm for single-source shortest path problem. In: Proceedings of 2016 International Conference on Supercomputing. 2016, 32

[19] Liao X, Zhao J, Zhang Y, He B, He L, Jin H, Gu L . A structure-aware storage optimization for out-of-core concurrent graph processing. IEEE Transactions on Computers, 2022, 71( 7): 1612–1625

[20] Liu H, Huang H H. Graphene: fine-grained IO management for graph computing. In: Proceedings of the 15th USENIX Conference on File and Storage Technologies. 2017, 285−299

[21] Liu W, Liu H, Liao X, Jin H, Zhang Y. Straggler-aware parallel graph processing in hybrid memory systems. In: Proceedings of the 21st IEEE/ACM International Symposium on Cluster, Cloud and Internet Computing. 2021, 217−226

[22] Agostini M, O’Brien F, Abdelrahman T. Balancing graph processing workloads using work stealing on heterogeneous CPU-FPGA systems. In: Proceedings of the 49th International Conference on Parallel Processing. 2020, 50

[23] Valiant L G . A bridging model for parallel computation. Communications of the ACM, 1990, 33( 8): 103–111

[24] Backstrom L, Huttenlocher D, Kleinberg J, Lan X. Group formation in large social networks: membership, growth, and evolution. In: Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2006, 44−54

[25] Kwak H, Lee C, Park H, Moon S. What is twitter, a social network or a news media? In: Proceedings of the 19th International Conference on World Wide Web. 2010, 591−600

[26] Boldi P, Vigna S. The webgraph framework I: compression techniques. In: Proceedings of the 13th International Conference on World Wide Web. 2004, 595−602

[27] Boldi P, Santini M, Vigna S . A large time-aware web graph. ACM SIGIR Forum, 2008, 42( 2): 33–38

[28] Zhou Z, Hoffmann H. GraphZ: improving the performance of large-scale graph analytics on small-scale machines. In: Proceedings of the 34th IEEE International Conference on Data Engineering. 2018, 1368−1371

[29] Chen H, Shen M, Xiao N, Lu Y. Krill: a compiler and runtime system for concurrent graph processing. In: Proceedings of International Conference for High Performance Computing, Networking, Storage and Analysis. 2021, 51

[30] Cheng J, Liu Q, Li Z, Fan W, Lui J C S, He C. VENUS: vertex-centric streamlined graph computation on a single PC. In: Proceedings of the 31st IEEE International Conference on Data Engineering. 2015, 1131−1142

[31] Chi Y, Dai G, Wang Y, Sun G, Li G, Yang H. NXgraph: an efficient graph processing system on a single machine. In: Proceedings of the 32nd IEEE International Conference on Data Engineering. 2016, 409−420

[32] Vora K, Xu G, Gupta R. Load the edges you need: a generic I/O optimization for disk-based graph processing. In: Proceedings of 2016 USENIX Conference on Usenix Annual Technical Conference. 2016, 507−522

[33] Xu X, Wang F, Jiang H, Cheng Y, Feng D, Zhang Y . A hybrid update strategy for I/O-efficient out-of-core graph processing. IEEE Transactions on Parallel and Distributed Systems, 2020, 31( 8): 1767–1782

[34] Matam K K, Hashemi H, Annavaram M. MultilogVC: efficient out-of-core graph processing framework for flash storage. In: Proceedings of 2021 IEEE International Parallel and Distributed Processing Symposium. 2021, 245−255

[35] Zhang M, Wu Y, Zhuo Y, Qian X, Huan C, Chen K . Wonderland: a novel abstraction-based out-of-core graph processing system. ACM SIGPLAN Notices, 2018, 53( 2): 608–621

[36] Pan P, Li C. Congra: towards efficient processing of concurrent graph queries on shared-memory machines. In: Proceedings of 2017 IEEE International Conference on Computer Design. 2017, 217−224

[37] Zhou L, Chen R, Xia Y, Teodorescu R. C-graph: a highly efficient concurrent graph reachability query framework. In: Proceedings of the 47th International Conference on Parallel Processing. 2018, 79

[38] Zhao J, Zhang Y, Liao X, He L, He B, Jin H, Liu H. LCCG: a locality-centric hardware accelerator for high throughput of concurrent graph processing. In: Proceedings of International Conference for High Performance Computing, Networking, Storage and Analysis. 2021, 45

RIGHTS & PERMISSIONS

Higher Education Press