Title: Write-Optimized and High-Performance Hashing Index Scheme for Persistent Memory.


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