Design And Implementation Of Hotspot-Aware B+tree For Non-Volatile Memory

Skewed data accesses are very common in real-world workloads.Therefore,reducing the read/write latency of hot data is critical to improving the overall service quality of the system.B+tree is a widely used index structure,and the emerging non-volatile memory(NVM)provides a new design decision for the B+tree to deal with data hotspots.However,existing B+tree works designed for NVM do not distinguish between hot data and cold data,which makes them fail to serve the skewed workload.This paper aims to design a hotspot-aware B+tree in NVM.To accelerate the access to the hotspots in B+tree,this paper proposes a non-leaf node cache(NLNC)strategy that leverages the wasted DRAM space due to the selective persistence scheme in the existing NVM-based B+tree.Different from traditional caching solutions that require extra storage space and cache accesses overhead,NLNC uses the empty entries of non-leaf nodes in the B+tree to cache the hot data which shortens the critical path of the access to the hot data,thus avoiding additional space consumption and achieving low-overhead cache accesses.To enable NLNC to obtain stable cache space,this paper proposes a cache reservation mechanism and allows users to adjust reading speed,memory usage,and writing efficiency as needed.To reduce B+tree performance degradation caused by thread competition for tree nodes under skewed write-intensive workloads,a request handover mechanism(RHM)is designed to release the service capacity of blocked threads and optimizes the write performance of the tree structure.To further improve the service speed of the write thread to the request handover queue,a batch service algorithm is proposed by leveraging the spatial locality of the requests in the handover queue and the idea of batch service.The batch service algorithm significantly reduces the consistency overhead and lock acquisition by performing requests from other threads in batches,thus improving the ability of B+tree to write hotspot data areas.Based on the above schemes,a B+tree(NLNC-RHM Tree,NRTree)optimized for reading and writing hot data on NVM is designed and implemented.For skewed workloads,NRTree gains improvement of 1.41-2.36 times and 1.56-3.72 times in read throughput and write throughput compared with state-of-the-art NVM-optimized B+tree,respectively.When facing uniform workloads,the read performance of NRTree is similar to that of state-of-the-art research,and the write performance is slightly better.