Study Of Dynamic Hashing Based On Non-volatile Memory

In the past,memory technology was mainly based on DRAM(Dynamic Random Access Memory).As massive data puts forward higher storage requirements,non-volatile memory(NVM)technology,also known as persistent memory(PM)emerges.Due to access latency close to DRAM and the advantage of being inherently byte-addressable,non-volatile memory bypasses the block-based interface and can be accessed directly over the memory bus using CPU(Central Processing Unit)load and store instructions.Existing persistent memory devices have high storage density,strong scalability,and can persist data,making them a strong competitor to DRAM.The emergence of NVM technology has brought about great changes in computer storage architecture.Therefore,existing traditional indexes need to be adjusted to better adapt to NVM device characteristics.Numerous existing works have improved non-volatile memory-based index structures,such as tree-based WORT(Write Optimal Radix Tree)and FAST ? FAIR(Failure-Atomic Shif T and Failure-Atomic In-place Rebalance),and hash table based Path Hashing and Level Hashing.Dynamic hash indexes,on the other hand,have received little attention.The most recent breakthrough research on dynamic hash indexing based on non-volatile memory is CCEH(Cacheline-Conscious Extendible Hashing).Although the performance of CCEH has been significantly improved compared with other hash indexes,there are still many problems: low space utilization;data redundancy;low degree of concurrency.These phenomena seriously affect the system performance.In response to these problems,this thesis proposes a dynamic hash indexing scheme based on non-volatile memory,Hy DH(Hyper spatial-optimized Dynamic Hashing).To solve the problem of low load factor,Hy DH indexing scheme proposes a new insertion method: virtual vicinity insertion.This method temporarily stores the current hash collision data in adjacent logical spaces,which can appropriately increase the space utilization and reduce the frequency of hash expansion without adding too much extra overhead.Furthermore,Hy DH proposes migratory deletion: the location of deleted data will be filled with data in its "virtual vicinity".This is because the "virtual vicinity" insertion will increase the average linear detection length,and the migration deletion can reduce the average linear detection length of subsequent operations to reduce the read operation latency.In order to eliminate data redundancy,Hy DH index also combines data fingerprints and bitmaps to record valid data stored in buckets.In this way,data consistency can be achieved through the atomic operation of the hardware,and the overhead of data consistency can be reduced.Further,Hy DH uses bucket-level optimistic locking to improve the concurrent read performance of the system under multi-threading.After conducting experiments on various operations of the Hy DH indexing scheme,the experimental results show that the operational performance of Hy DH indexing is better than that of CCEH.Among them,the data query performance is the best.Its throughput is 23.7% higher than that of CCEH.Even the most time-consuming data-insertion operation improves by 4.7% compared to CCEH.