LiveGraph
Autor: | Xiaowei Zhu, Lei Xie, Xiaosong Ma, Ashraf Aboulnaga, Wenguang Chen, Jiping Yu, Guanyu Feng, Marco Serafini |
---|---|
Rok vydání: | 2020 |
Předmět: |
FOS: Computer and information sciences
Graph analytics Theoretical computer science business.industry Computer science Locality General Engineering Databases (cs.DB) 020206 networking & telecommunications 02 engineering and technology Data structure Concurrency control Computer Science - Databases Transactional leadership 020204 information systems Computer data storage 0202 electrical engineering electronic engineering information engineering Graph (abstract data type) Adjacency list business MathematicsofComputing_DISCRETEMATHEMATICS |
Zdroj: | Proceedings of the VLDB Endowment. 13:1020-1034 |
ISSN: | 2150-8097 |
DOI: | 10.14778/3384345.3384351 |
Popis: | The specific characteristics of graph workloads make it hard to design a one-size-fits-all graph storage system. Systems that support transactional updates use data structures with poor data locality, which limits the efficiency of analytical workloads or even simple edge scans. Other systems run graph analytics workloads efficiently, but cannot properly support transactions. This paper presents LiveGraph, a graph storage system that outperforms both the best graph transactional systems and the best solutions for real-time graph analytics on fresh data. LiveGraph achieves this by ensuring that adjacency list scans, a key operation in graph workloads, are purely sequential: they never require random accesses even in presence of concurrent transactions. Such pure-sequential operations are enabled by combining a novel graph-aware data structure, the Transactional Edge Log (TEL), with a concurrency control mechanism that leverages TEL's data layout. Our evaluation shows that LiveGraph significantly outperforms state-of-the-art (graph) database solutions on both transactional and real-time analytical workloads. |
Databáze: | OpenAIRE |
Externí odkaz: |