Research On Ring Hash Indexing Structure For Non-Volatile Memory

Non-Volatile Memory(NVMs)has been widely used.The data structures used in existing key-value storage systems do not fully exploit the characteristics of NVM,so that the traditional data structures need to be improved to deliver better performance for NVM.Due to the constant lookup time,hash index structure is widely used in the computer system.Most of the existing hashing schemes for NVM primarily focus on reducing write operations,but ignore the expensive overhead of resizing operation and guaranteeing data consistency.These costs not only reduce the throughput of hash table,but also increase write operations to NVM which reduces the lifetime of NVM.To address these problems,this paper proposes a ring hash indexing structure based on NVM called NVM-friendly Array-Mapped hashing(NAM),that is a hash scheme combining the characteristics of NVM and the traditional Hash Array Mapped Trie(HAMT)which is write-optimized and resizing-efficient.In this scheme,each item is indexed by using bits of hash value and bitmap group related to the cacheline size are used to speed access.NAM uses an in-place ring resizing scheme to expand the hash table in exponential increments,thus rehashing fewer buckets when resizing the hash table.It further uses a log-free scheme to ensure data consistency for most modification operations,while achieving non-blocking resizing and lock-free concurrency,which significantly improves the throughput of the hash index structure.Our proposed NAM reduces write operations to NVM and the latency of accessing and resizing while increasing the lifetime of NVM.Extensive evaluations by using Intel Optane DC PMM on NAM demonstrate that,NAM has better performance than the other state-of-the-art hashing schemes.