Research On Hash Index Structure Based On NVM

Today,the growth rate of data volume is significantly higher than that of storage medium density,and the main memory database is facing the challenges of power consumption,capacity and performance.The emergence of Non-Volatile Memory(NVM)has changed the computer architecture,and its byte addressable,non-volatile,large capacity features solve the problems of the current memory database.The performance of the index structure largely determines the performance of the database,so the research of hash index structure based on NVM can help us make better use of the dividend brought by NVM.However,the performance characteristics of DCPMM,the only commercially available persistent memory released in reality,are quite different from the previous estimation of NVM,so we need to design the index structure for the underlying architecture of DCPMM.In this paper,we first reproduce some hash index structures based on DCPMM,and demonstrate their main disadvantages through experiments(mainly including: the contradiction between load factor and index structure performance,not making full use of DCPMM bandwidth,extra overhead when storing atomic writable key value pairs,and so on).We also propose our goal of designing hash index structure based on DCPMM.Based on this,this paper proposes the following optimization for the hash index structure based on DCPMM:(1)Adjust the size of the bucket to make full use of the bandwidth of DCPMM,avoid premature delay wall effect,and improve the load factor of the index structure.(2)By setting high bit fingerprint metadata,the number of cache rows exchanged between DCPMM and CPU is reduced,and the unnecessary random reading overhead is reduced.(3)This paper proposes a mechanism similar to the three times handshake in computer network to realize the lock free operation and reduce the extra cost of storing the atomic writable key value pairs.(4)Using Intel's SIMD instruction set to optimize the performance of index structure.In this paper,we test the index structure based on DCPMM and get the following results:(1)The load factor is 10% to 45% higher than the previous index structure.(2)When storing key value pairs of variable length,compared with Clevel Hashing which composes fingerprint,LFP?hash improves search performance by 12% to 36%,insert performance by11%,and update performance by 20%.(3)Using SIMD instruction set for optimization can further improve LFP?hash search operation performance improved by 7% to 11%.(4)When storing atomically writable key value pairs,the multithreading performance of LFP?hash proposed in this paper is 1.4 to 3.3 times of that of Clevel Hashing with fingerprint under real load.The experimental results verify the effectiveness of the proposed optimization method.