GraphSSD: graph semantics aware SSD

ABSTRACT

Graph analytics play a key role in a number of applications such as social networks, drug discovery, and recommendation systems. Given the large size of graphs that may exceed the capacity of the main memory, application performance is bounded by storage access time. Out-of-core graph processing frameworks try to tackle this storage access bottleneck through techniques such as graph sharding, and sub-graph partitioning. Even with these techniques, the need to access data across different graph shards or sub-graphs causes storage systems to become a significant performance hurdle. In this paper, we propose a graph semantic aware solid state drive (SSD) framework, called GraphSSD, which is a full system solution for storing, accessing, and performing graph analytics on SSDs. Rather than treating storage as a collection of blocks, GraphSSD considers graph structure while deciding on graph layout, access, and update mechanisms. GraphSSD replaces the conventional logical to physical page mapping mechanism in an SSD with a novel vertex-to-page mapping scheme and exploits the detailed knowledge of the flash properties to minimize page accesses. GraphSSD also supports efficient graph updates (vertex and edge modifications) by minimizing unnecessary page movement overheads. GraphSSD provides a simple programming interface that enables application developers to access graphs as native data in their applications, thereby simplifying the code development. It also augments the NVMe (non-volatile memory express) interface with a minimal set of changes to map the graph access APIs to appropriate storage access mechanisms.

Our evaluation results show that the GraphSSD framework improves the performance by up to 1.85 × for the basic graph data fetch functions and on average 1.40×, 1.42×, 1.60×, 1.56×, and 1.29× for the widely used breadth-first search, connected components, random-walk, maximal independent set, and page rank applications, respectively.

References

1. Anurag Acharya, Mustafa Uysal, and Joel Saltz. Active Disks: Programming Model, Algorithms and Evaluation. In Proceedings of the 8th International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS '98, pages 81--91, New York, NY, USA, 1998. ACM.
2. Junwhan Ahn, Sungpack Hong, Sungjoo Yoo, Onur Mutlu, and Kiyoung Choi. A Scalable Processing-in-memory Accelerator for Parallel Graph Processing. In Proceedings of the 42Nd Annual International Symposium on Computer Architecture, ISCA '15, pages 105--117, New York, NY, USA, 2015. ACM.
3. Simona Boboila, Youngjae Kim, Sudharshan S. Vazhkudai, Peter Desnoyers, and Galen M. Shipman. Active Flash: Out-of-core data analytics on flash storage. In IEEE 28th Symposium on Mass Storage Systems and Technologies, MSST '12, pages 1--12, April 2012.
4. Raymond Cheng, Ji Hong, Aapo Kyrola, Youshan Miao, Xuetian Weng, Ming Wu, Fan Yang, Lidong Zhou, Feng Zhao, and Enhong Chen. Kineograph: Taking the Pulse of a Fast-changing and Connected World. In Proceedings of the 7th ACM European Conference on Computer Systems, EuroSys '12, pages 85--98, New York, NY, USA, 2012. ACM.
5. Sangyeun Cho, Chanik Park, Hyunok Oh, Sungchan Kim, Youngmin Yi, and Gregory R. Ganger. Active Disk Meets Flash: A Case for Intelligent SSDs. In Proceedings of the 27th International ACM Conference on International Conference on Supercomputing, ICS '13, pages 91--102, New York, NY, USA, 2013. ACM.
6. Brian F Cooper, Adam Silberstein, Erwin Tam, Raghu Ramakrishnan, and Russell Sears. Benchmarking cloud serving systems with YCSB. In Proceedings of the 1st ACM symposium on Cloud computing, pages 143--154. ACM, 2010.
7. Jaeyoung Do, Yang-Suk Kee, Jignesh M. Patel, Chanik Park, Kwanghyun Park, and David J. DeWitt. Query Processing on Smart SSDs: Opportunities and Challenges. In Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data, SIGMOD '13, pages 1221--1230, New York, NY, USA, 2013. ACM.
8. D. Ediger, R. McColl, J. Riedy, and D. A. Bader. STINGER: High performance data structure for streaming graphs. In 2012 IEEE Conference on High Performance Extreme Computing, pages 1--5, Sept 2012.
9. Boncheol Gu, Andre S. Yoon, Duck-Ho Bae, Insoon Jo, Jinyoung Lee, Jonghyun Yoon, Jeong-Uk Kang, Moonsang Kwon, Chanho Yoon, Sangyeun Cho, Jaeheon Jeong, and Duckhyun Chang. Biscuit: A Framework for Near-data Processing of Big Data Workloads. In Proceedings of the 43rd International Symposium on Computer Architecture, ISCA '16, pages 153--165, Piscataway, NJ, USA, 2016. IEEE Press.
10. Tae Jun Ham, Lisa Wu, Narayanan Sundaram, Nadathur Satish, and Margaret Martonosi. Graphicionado: A high-performance and energy-efficient accelerator for graph analytics. In 2016 49th Annual IEEE/ACM International Symposium on Microarchitecture, MICRO '16, pages 1--13, Oct 2016.
11. Wentao Han, Youshan Miao, Kaiwei Li, Ming Wu, Fan Yang, Lidong Zhou, Vijayan Prabhakaran, Wenguang Chen, and Enhong Chen. Chronos: A Graph Engine for Temporal Graph Analysis. In Proceedings of the Ninth European Conference on Computer Systems, EuroSys '14, pages 1:1--1:14, New York, NY, USA, 2014. ACM.
12. Wook-Shin Han, Sangyeon Lee, Kyungyeol Park, Jeong-Hoon Lee, Min-Soo Kim, Jinha Kim, and Hwanjo Yu. TurboGraph: A Fast Parallel Graph Engine Handling Billion-scale Graphs in a Single PC. In Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '13, pages 77--85, New York, NY, USA, 2013. ACM.
13. Amber Huffman. NVM Express, 2013.
14. Yanqin Jin, Hung-Wei Tseng, Yannis Papakonstantinou, and Steven Swanson. Kaml: A flexible, high-performance key-value ssd. In HPCA, pages 373--384. IEEE, 2017.
15. Sang-Woo Jun, Andy Wright, Sizhuo Zhang, Shuotao Xu, and Arvind. GraFBoost: Accelerated Flash Storage for External Graph Analytics. ISCA, 2018.
16. Sang-Woo Jun, Andy Wright, Sizhuo Zhang, Shuotao Xu, et al. BigSparse: High-performance external graph analytics. arXiv preprint arXiv:1710.07736, 2017.
17. Yangwook Kang, Yang suk Kee, Ethan L. Miller, and Chanik Park. Enabling cost-effective data processing with smart SSD. In IEEE 29th Symposium on Mass Storage Systems and Technologies, MSST '14, pages 1--12, May 2013.
18. Jin-Yong Kim, Sang-Hoon Park, Hyeokjun Seo, Ki-Whan Song, Sungroh Yoon, and Eui-Young Chung. NAND Flash Memory With Multiple Page Sizes for High-Performance Storage Devices. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 24(2):764--768, Feb 2016.
19. Gunjae Koo, Kiran Kumar Matam, Te I, H. V. Krishna Giri Narra, Jing Li, Hung-Wei Tseng, Steven Swanson, and Murali Annavaram. Summarizer: Trading Communication with Computing Near Storage. In Proceedings of the 50th Annual IEEE/ACM International Symposium on Microarchitecture, MICRO-50 '17, pages 219--231, New York, NY, USA, 2017. ACM.
20. Aapo Kyrola. Drunkardmob: billions of random walks on just a pc. In Proceedings of the 7th ACM conference on Recommender systems, pages 257--264. ACM, 2013.
21. Aapo Kyrola, Guy Blelloch, and Carlos Guestrin. GraphChi: Large-scale Graph Computation on Just a PC. In Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation, OSDI '12, pages 31--46, Berkeley, CA, USA, 2012. USENIX Association.
22. Jinho Lee, Heesu Kim, Sungjoo Yoo, Kiyoung Choi, H Peter Hofstee, Gi-Joon Nam, Mark R Nutter, and Damir Jamsek. ExtraV: boosting graph processing near storage with a coherent accelerator. Proceedings of the VLDB Endowment, 10(12):1706--1717, 2017.
23. Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection.
24. Michael Luby. A simple parallel algorithm for the maximal independent set problem. SIAM journal on computing, 15(4):1036--1053, 1986.
25. Steffen Maass, Changwoo Min, Sanidhya Kashyap, Woonhak Kang, Mohan Kumar, and Taesoo Kim. Mosaic: Processing a trillion-edge graph on a single machine. In Proceedings of the Twelfth European Conference on Computer Systems, pages 527--543. ACM, 2017.
26. Peter Macko, Virendra J Marathe, Daniel W Margo, and Margo I Seltzer. LLAMA: Efficient graph analytics using large multiversioned arrays. In Data Engineering (ICDE), 2015 IEEE 31st International Conference on, pages 363--374. IEEE, 2015.
27. Grzegorz Malewicz, Matthew H Austern, Aart JC Bik, James C Dehnert, Ilan Horn, Naty Leiser, and Grzegorz Czajkowski. Pregel: a system for large-scale graph processing. In Proceedings of the 2010 ACM SIGMOD International Conference on Management of data, pages 135--146. ACM, 2010.
28. Kiran Kumar Matam, Hanieh Hashemi, and Murali Annavaram. PartitionedVC: Partitioned External Memory Graph Analytics Framework for SSDs. arXiv e-prints, page arXiv:1905.04264, May 2019.
29. Alan Mislove. Online Social Networks: Measurement, Analysis, and Applications to Distributed Information Systems. PhD thesis, Rice University, Department of Computer Science, May 2009.
30. Lifeng Nai, Yinglong Xia, Ilie G Tanase, Hyesoon Kim, and Ching-Yung Lin. GraphBIG: understanding graph computing in the context of industrial solutions. In High Performance Computing, Networking, Storage and Analysis, 2015 SC-International Conference for, pages 1--12. IEEE, 2015.
31. OpenSSD. Open-Source Solid-State Drive Project for Research and Education. http://openssd.io.
32. Muhammet Mustafa Ozdal, Serif Yesil, Taemin Kim, Andrey Ayupov, John Greth, Steven Burns, and Ozcan Ozturk. Energy Efficient Architecture for Graph Analytics Accelerators. In Proceedings of the 43rd International Symposium on Computer Architecture, ISCA '16, pages 166--177, Piscataway, NJ, USA, 2016. IEEE Press.
33. Pagerank application. https://github.com/GraphChi/graphchi-cpp/blob/master/example_apps/streaming_pagerank.cpp.
34. Erik Riedel, Christos Faloutsos, Garth A. Gibson, and David Nagle. Active Disks for Large-Scale Data Processing. Computer, 34(6):68--74, June 2001.
35. Semih Salihoglu and Jennifer Widom. Optimizing graph algorithms on pregel-like systems. Proceedings of the VLDB Endowment, 7(7):577--588, 2014.
36. Yong Ho Song. Cosmos+ OpenSSD: A NVMe-based Open Source SSD Platform. In Flash Memory Summit 2016, Santa Clara, CA, USA, 2016.
37. Devesh Tiwari, Simona Boboila, Sudharshan S. Vazhkudai, Youngjae Kim, Xiaosong Ma, Peter J. Desnoyers, and Yan Solihin. Active Flash: Towards Energy-efficient, In-situ Data Analytics on Extreme-scale Machines. In Proceedings of the 11th USENIX Conference on File and Storage Technologies, FAST'13, pages 119--132, Berkeley, CA, USA, 2013. USENIX Association.
38. Devesh Tiwari, Sudharshan S. Vazhkudai, Youngjae Kim, Xiaosong Ma, Simona Boboila, and Peter J. Desnoyers. Reducing Data Movement Costs Using Energy Efficient, Active Computation on SSD. In Proceedings of the 2012 USENIX Conference on Power-Aware Computing and Systems, HotPower'12, Berkeley, CA, USA, 2012. USENIX Association.
39. Xilinx. Zynq-7000 All Programmable SoC Data Sheet. https://www.xilinx.com/support/documentation/data_sheets/ds190-Zynq-7000-Overview.pdf.
40. Yahoo WebScope. Yahoo! altavista web page hyperlink connectivity graph, circa 2002. http://webscope.sandbox.yahoo.com/, 2018.
41. Da Zheng, Disa Mhembere, Randal Burns, Joshua Vogelstein, Carey E. Priebe, and Alexander S. Szalay. FlashGraph: Processing Billion-Node Graphs on an Array of Commodity SSDs. In 13th USENIX Conference on File and Storage Technologies (FAST '15), FAST '15, pages 45--58, Santa Clara, CA, 2015.

Index Terms

• Hardware

  • Communication hardware, interfaces and storage

    • External storage