Research On Non-Volatile Memory Based Efficient Index Scheme And Application

Modern computer systems need larger memory capacities under the background of big data era.Traditional DRAM-based memory system is facing serious challenges due to reaching the limitation of the fabrication technology and leakage power dissipation.With the development of materials technology,several non-volatile memory(NVM)technologies emerge,such as Phase Change Memory(PCM)and Resistive Random-Access Memory(RRAM).The new NVM technologies have many prominent features,such as non-volatility,byte-addressability,fast access speed,high density and low power dissipation.These desirable features allow NVMs to be directly placed on the memory bus along with traditional DRAM,or even replace DRAM in the future.Efficient index structures are necessary in NVM-based memory systems to improve the data index and space management efficiency.However,traditional index structures which are designed for DRAM fail to perform efficiently in NVMs because they neither consider the NVM device limitations nor satisfy the data consistency requirement.To this end,this thesis studies the NVM-based index structures in-depth,proposes two solutions in the aspect of point query and range scan to address the NVM device limitations and data consistency issues,and gives an application scenario from the perspective of file system.The research contents and contributions of this thesis are as follows.Traditional index structures which are designed for DRAM fail to perform efficiently in NVMs due to neglecting the NVM device limitations and the data consistency requirement.To address this problem,this thesis proposes a high-performance and consistent hashing index scheme,called group hashing.Group hashing consists of three major contributions:(1)Group hashing uses 8-byte failure-atomic write to guarantee the data consistency of insert and delete operations,which eliminates the duplicate copy writes to NVMs,thus reducing the consistency cost of the hashing index structure.(2)In order to improve CPU Cache efficiency,group hashing leverages a novel technique called group sharing,which divides the hash table into groups and deploys a contiguous memory space in each group to deal with hash collisions,thus reducing CPU Cache misses to obtain higher performance in terms of request latency.(3)To reduce the searching latency inside a group,group hashing adopts an in-group rehash scheme,which locates each collision cell to a unique position,thus further improving the request performance.Extensive experimental results demonstrate that group hashing achieves low request latency as well as high CPU Cache efficiency,compared with state-of-the-art NVM-based hashing schemes.Existing NVM-based index structures focus on designing and optimizing a certain structure.However,a single index structure fails to efficiently support point query and range scan at the same time.To address this problem,this thesis proposes an NVM-based hybrid index structure,called HSHI.The basic idea behind HSHI is constructing a hybrid index structure which consists of hashing index and skiplist.HSHI fully exploits the different merits of hashing index and skiplist.HSHI builds and persists hashing index in NVM to utilize its inherent property of constant-scale lookup time complexity.To support range scan and reduce NVM writes for maintaining data consistency of the two indexes,HSHI builds skiplist in DRAM.To reduce the write latency of the hybrid index structure,HSHI uses asynchronous updates for skiplist in DRAM.HSHI adopts 8-byte failure-atomic write to guarantee the data consistency,which reduces the consistency cost of the hybrid index.Furthermore,HSHI employs a fine-grained locking scheme to support differential concurrency.Evaluation results demonstrate that HSHI outperforms state-of-the-art NVM-based index structures in both single-threaded and multi-threaded workloads.File system is an important application scenario of index structure.Current journaling file systems suffer from performance decrease due to the extra journal writes.Simply replacing slow HDDs with fast NVMs in building journaling storage device seems to be a solution.However,existing journaling schemes,which are designed for HDDs,fail to perform efficiently in NVMs due to neglecting the prominent features and limitations of NVMs.To address this problem,this thesis proposes an NVM-based journaling scheme,called NJS.In order to decrease the amount of journal writes,NJS only needs to write the file system metadata and over-write data to NVM as write-ahead logging,thus alleviating the slow write and endurance limitation of NVM.NJS adopts a wear aware strategy for NVM journal block allocation in which each block can be evenly worn out,thus further extending the lifetime of NVM.To fully exploit the unique byte-accessibility characteristic of NVM,NJS proposes a novel journaling update scheme in which journal data blocks can be updated in the byte-granularity based on the difference of the old and new versions of journal blocks.NJS includes a garbage collection mechanism that absorbs the redundant journal updates,and actively delays the checkpointing to the file system.Evaluation results show that Ext4 with NJS outperforms Ext4 with a ramdisk-based journaling device by 57.1 percent on average in different workloads.