Write-Optimized Dynamic Hashing for Persistent Memory


Moohyeon Nam, UNIST (Ulsan National Institute of Science and Technology); Hokeun Cha, Sungkyunkwan University; Young-ri Choi and Sam H. Noh, UNIST (Ulsan National Institute of Science and Technology); Beomseok Nam, Sungkyunkwan University


Low latency storage media such as byte-addressable persistent memory (PM) requires rethinking of various data structures in terms of optimization. One of the main challenges in implementing hash-based indexing structures on PM is how to achieve efficiency by making effective use of cachelines while guaranteeing failure-atomicity for dynamic hash expansion and shrinkage. In this paper, we present Cacheline-Conscious Extendible Hashing (CCEH) that reduces the overhead of dynamic memory block management while guaranteeing constant hash table lookup time. CCEH guarantees failure-atomicity without making use of explicit logging. Our experiments show that CCEH effectively adapts its size as the demand increases under the fine-grained failure-atomicity constraint and reduces the maximum query latency by over two-thirds compared to the state-of-the-art hashing techniques.

FAST '19 Open Access Sponsored by NetApp

Open Access Media

USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.

@inproceedings {227812,
author = {Moohyeon Nam and Hokeun Cha and Young-ri Choi and Sam H. Noh and Beomseok Nam},
title = {Write-Optimized Dynamic Hashing for Persistent Memory},
booktitle = {17th {USENIX} Conference on File and Storage Technologies ({FAST} 19)},
year = {2019},
isbn = {978-1-931971-48-5},
address = {Boston, MA},
pages = {31--44},
url = {https://www.usenix.org/conference/fast19/presentation/nam},
publisher = {{USENIX} Association},