Research And Implementation Of An Efficient Key-Value Storage System With Hybrid Tree Index Structure Based On Non-Volatile Memory

With its high performance,high availability,and high scalability,key-value storage systems have become the main storage technology in current data centers,which can meet the data storage requirements in big data environments.In the other hand,Non-Volatile Memory(NVM)is a new type of storage medium with the characteristics of non-volatile data,high storage density,high performance,and high concurrency.The emergence of new storage materials has also brought opportunities and challenges to the efficient storage systems research.The key-value storage system based on Log-Structured Merged-Tree(LSM-Tree)is designed for hard disks.Due to serious read and write amplification problem,it cannot take full advantage of NVM media characteristics.In the NVM related research,Radix-Tree based index structure has better performance than B-Tree type based index structure but also has a serious problem of space waste.To avoid above two problems,a hybrid-tree index structure named HybridTree is proposed.HybridTree combines Radix-Tree and B+Tree to present a hierarchical structure as a whole.The upper layer is composed of prefix index nodes similar to Radix-Tree,which is indexed by the prefix of the key to speed up data locating,and providing multi-threaded support;The lower layer consists of variable-length adaptive B+Tree nodes organizing key-value data to reduce space waste caused by node sparseness.It effectively improves the space utilization of the index structure while using NVM device characteristics to ensure high performance of the system.Finally,using NVM CPU's direct access and byte addressing characteristics,a high-performance NVM key storage system HybridKV is designed based on HybridTree.By storing HybridTree directly on NVM,the problem of read and write amplification of the hierarchical structure of the LSM-Tree is avoided.HybridKV is implemented based on the open source LevelDB and evaluating HybridTree and HybridKV on a real NVM devices(Intel Optane DC Persistent Memory).According to the results,HybridTree's random write performance is 1.2x to 1.62x compared to Fast & Fair and 1.11x to 1.52x compared to NV-Tree,with 54% space utilization reduced compared to WORT.In the other hand,HybridKV can improve random write performance by 7.5x compared to LevelDB and 3.23x compared to RocksDB.In addition,the random read performance of HybridKV is 7x compared to NoveLSM.