A High Performance Dynamic Graph Processing Data Structure For Non-volatile Memory Systems

In the past ten years,the information of graph from the Web and social network has been increasing rapidly,and the demand of dynamic graphs for real-time storage,analysis and processing is getting higher and higher.Emerging Non-volatile Memory(NVM)storage technologies have the advantages of high density,high scalability and near-zero standby power,consequently,they are considered as potential candidates to replace DRAM due to features such as byte-addressing.They can meet the rapidly increasing storage and processing requirements of dynamic graph information.However,the current state-of-the-art data structures for dynamic graph processing rely on static graph representation models such as adjacency list of edge blocks when updating graphs.They either have high latency in data query in NVM environments or have serious data movement overheads,which lead to poor update throughput.In order to solve the issues of dynamic graph data structures in the NVM environment,Level Merge Sorted Array(LMSA)is proposed,which is a dynamic graph data structure and can support the optimization of read and write performance.It employs a hierarchical array to store dynamic graph edges to improve the speed of query and to reduce the times of writing caused by maintenance of dynamic graph data structure properties.To guarantee the consistency with low overheads,LMSA leverages log-free consistency schemes for insertion,deletion,and update operations.Based on the experimental results conducted on the machine equipped with DCPMM(Intel Optane DC Persistent Memory Module),LMSA provides a 4.3-12.6x insertions throughput improvement of Stinger and 1.4-4.35 x of Graph Tinker;it also provides a 5.7-20.1x deletions throughput improvement of Stinger and 1.4-4.58 x of Graph Tinker where both are the state-of-the-art dynamic graph data structures.