Write-optimized and high-performance hashing index scheme for persistent memory

摘要: Non-volatile memory (NVM) as persistent is expected to substitute or complement DRAM in hierarchy, due the strengths of non-volatility, high density, and near-zero standby power. However, requirement data consistency hardware limitations NVM, traditional indexing techniques originally designed for become inefficient memory. To efficiently index memory, this paper proposes a write-optimized high-performance hashing scheme, called level hashing, with low-overhead guarantee cost-efficient resizing. Level provides sharing-based two-level hash table, which achieves constant-scale search/insertion/deletion/update time complexity worst case rarely incurs extra NVM writes. low overhead, leverages log-free schemes insertion, deletion, resizing operations, an opportunistic scheme update operation. cost-efficiently resize inplace that only needs rehash 1/3 buckets instead entire thus significantly reducing number rehashed improving performance. Experimental results demonstrate 1:4×-3:0× speedup insertions, 1:2×-2:1× updates, over 4:3× resizing, while maintaining search deletion performance, compared state-of-the-art schemes.