NVGraph: Enforcing Crash Consistency of Evolving Network Analytics in NVMM Systems
Lists
Only you see this
Abstract
Many complex networks can be modeled as evolving graphs. Existing in-memory graph data structures are designed for DRAM. Thus, they cannot effectively exploit the current and ongoing adoption of emerging non-volatile main memory (NVMM) for two reasons. (1) Ephemeral graph data structures are not crash-consistent for NVMM. (2) NVMM writes and reads and may incur higher latency than DRAM. In this article, we propose a novel persistent evolving graph data structure, named NVG <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">RAPH</sub> , for both computing and in-memory storage of evolving graphs in NVMM. We devise NVG <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">RAPH</sub> as a multi-version data structure, wherein a minimum of one version of its data is stored in NVMM to provide the desired durability at runtime for failure recovery, and another version is stored in both DRAM and NVMM to reduce the NVMM-induced memory latency. NVG <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">RAPH</sub> is also a partitioned data structure. We dynamically transform the layout of NVG <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">RAPH</sub> (e.g., changing the size of its partition in DRAM) exploiting network properties and data access patterns of workloads. For the evaluation of NVG <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">RAPH</sub> , we implement four representative real-world graph applications: pagerank, BFS, influence maximization, and rumor source detection. The experimental results show that the performance of NVG <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">RAPH</sub> is comparable to other in-memory data structure (e.g., CSR and LLAMA) while using 70 percent less DRAM. It scales well up to 10 billion edges and 201 snapshots and supports crash consistency. It offers up to the 21X speedup of execution time compared to the scale-up graph computation approaches (e.g., GraphChi and X-stream).
BibTeX
@article{lim2020nvgraph,
author = {Soklong Lim and Tyler Coy and Zaixin Lu and Bin Ren and Xuechen Zhang},
title = {{NVGraph: Enforcing Crash Consistency of Evolving Network Analytics in NVMM Systems}},
journal = {IEEE Trans. Parallel Distributed Syst.},
year = {2020},
url = {https://openreview.net/forum?id=jINEMKnqym},
}Loading related content...