基于非易失存储器的大规模图数据库系统关键技术研究

Large-scale graph database systems play increasingly important roles in a broad range of domains such as social computing, machine learning, and so on. The state-of-the-art graph database systems such as Pregel, GraphLab, GraphX, and GraphChi suffer from severe bottlenecks in network communications, I/O costs, energy overhead and/or price. In recent years, a broad class of new non-volatile memory (NVM) technologies has emerged, e.g., PCM, STT-MRAM, memristor, and so on. NVM offers an intriguing blend of the advantages of DRAM and external storage: NVM is byte-addressable and non-volatile, that is, data will not be lost after power shortage. NVM has read/write latency and per-bit energy overhead comparable to those of DRAM, while the capacity and the price of NVM are close to those of external storage. NVM brings new opportunities to developing next-generation graph database systems. However, the goal cannot be realized by simply replacing DRAM by NVM because many techniques adopted by the existing graph database systems are not appropriate options for NVM, which may lead to unexpected performance degradation. Moreover, the write overhead of NVM (latency and energy consumption) is much higher than the read overhead, and the endurance of NVM is several orders of magnitude lower than that of DRAM. Therefore, building graph database systems based on NVM is a challenging task. In this project, we study key techniques of NVM-based graph database systems, including data storage structures, data access methods, query processing, failure recovery, concurrency control, and develops a prototype system. The results of this project will lay theoretical and technical foundations for building next-generation graph database systems based on NVM for our country.

大规模图数据库系统在社会计算、机器学习等领域发挥着越来越重要的作用，但现有系统在网络通信、I/O、能耗、价格等方面存在严重的瓶颈。近年来出现了一类新型非易失存储器(NVM)，如PCM、STT-MRAM等。NVM融合了DRAM和外存的优点，不仅可以按字节寻址，而且断电后数据不丢失。NVM的读写延迟和能耗与DRAM接近，存储容量和价格与外存接近。NVM的优点为研制新一代图数据库系统带来了希望，但这不是将DRAM替换为NVM就能实现的，因为现有图数据库系统的很多技术并不适用于NVM，反而会降低性能。另外，NVM的写代价(延迟与能耗)比读代价高得多，且耐用性差。这给研究基于NVM的图数据库系统带来了很多挑战。本项目拟研究基于NVM的图数据库系统关键技术，包括存储结构、存取方法、查询处理、故障恢复、并发控制等，并研制基于NVM的图数据库系统原型，为我国自主研制基于NVM的新一代图数据库系统奠定基础。

图数据库系统是一类重要的NoSQL数据库系统，具有广泛的应用，但现有系统在网络通信、I/O、能耗、价格等方面存在瓶颈。近年来出现了一类新型非易失存储器（NVM），NVM融合了DRAM和外存的优点，不仅可以按字节寻址，而且断电后数据不丢失。NVM的读写延迟和能耗与DRAM接近，存储容量和价格与外存接近。NVM的优点为研制新一代图数据库系统带来了机遇，但这并不是将DRAM替换为NVM就能实现的，因为现有图数据库系统的很多技术并不适用于NVM，反而会降低性能。此外，NVM的写延迟明显高于读延迟，且耐用性差。这给研究基于NVM的图数据库系统带来了很多挑战。.本项目研究基于NVM的图数据库系统关键技术，充分利用NVM的新特性来提高图数据库系统的性能，主要研究内容包括：基于NVM的图数据库存储结构、索引结构、基本操作算法、查询与分析算法、故障恢复方法。本项目取得了以下重要结果：（1）在基于NVM的图数据库存储结构方面，我们设计了一种基于NVM+DRAM混合存储的图数据库存储结构和故障恢复方法，利用NVM按字节寻址和非易失的特点，既能对图数据基本对象进行快速访问，又能以较低代价保证图数据的一致性，并可以快速完成故障恢复。（2）在基于NVM的图数据库索引结构方面，我们设计了一种基于NVM的日志结构合并树（LSM树）和故障恢复方法，用适合NVM特性的数据结构替换SSTable文件和层级索引，显著降低了写放大，减少了NVM写次数，并可以快速完成故障恢复。（3）在基于NVM的图数据库基本操作算法方面，我们提出了基于NVM的排序算法和一系列子图匹配算法，针对NVM读写延迟不对称的问题，平衡算法的读写操作，尽可能减少算法执行的NVM写操作，提高算法的整体执行性能。（4）在基于NVM的图数据库查询与分析算法方面，我们用紧致数据结构在NVM中存储大量图数据，并设计新的查询与分析算法，发挥多核处理器的性能，解决了多层图分析等计算复杂性更高的图计算问题。.本项目发现NVM对于提升图数据库系统的性能确实有很大帮助，但需要在算法和系统两个层面对图数据库系统进行重新设计，才能使系统适应NVM的新特性，发挥NVM的性能优势，提高系统的整体性能。设计基于NVM的图数据库系统的有效方法包括：减少存储结构和索引结构的写放大；避免使用复杂的数据结构维护中间计算结果；平衡算法的读操作与写操作，尽可能减少NVM写操作。