Key-value Storage Engine On Non-volatile Memory

Key-value storage engine plays an increasingly important role in modern dataintensive applications such as web indexing,e-commerce,social network,and cloud storage.However,the inherent deficiencies in internal memory and external memory have become the bottleneck of key-value storage engines.With the development of memory technology,there has emerged a new class of memory called non-volatile memory,which has the advantages of internal memory on byte-addressable and low latency and the advantages of external memory on non-volatile and large capacity.Researching the key technology of key-value storage engine based on NVM promised to solve the bottleneck problem of the existing key-value storage engine.This paper firstly analyzes the system framework and operating mechanism of the external storage based key-value storage engine Level DB through the source code,and then analyzes the read latency and write amplification of Level DB through experiments,and draws an important conclusion from experiment results: on the one hand,data deserialization overhead caused by SST files and maintenance overhead of the sequential hierarchical index account for a high proportion of read latency;on the other hand,the file leveling key-value data compaction strategy caused a high write amplification,which not only reduces the data insert performance but also greatly reduces NVM's lifespan.According to this conclusion,this paper redesigns Level DB from the perspective of algorithm and engineering,and consequently realizes the key-value storage engine Nova DB based on NVM.The improvements mainly include:(1)replacing SST files and the sequential hierarchical index with persistent indexes,and designing efficient search algorithms to replace binary search;(2)replacing file leveling key-value data compaction strategy with the key-value data compaction strategy that separates index from data;(3)replacing the copy-on-write update method and log technology with persistent in-place update and failure recovery based on critical data partitioning respectively.This paper compares Nova DB and Level DB through micro-benchmark experiment and macro-benchmark experiment.The experiment results show that Nova DB's write performance is up to about 12 times that of Level DB,Nova DB's range query performance is up to 33 times that of Level DB,Nova DB's write amplification ratio is about 5.2% of Level DB and Nova DB's failure recovery speed is about 196 times that of Level DB.This paper verifies the effectiveness of these improvements by analyzing the causes of experiment results,and finally summarizes the key-value storage engine technical strategies suitable for NVM.