research-article

Open access

TurboHash: A Hash Table for Key-value Store on Persistent Memory

Authors:

Xingsheng Zhao,

Song JiangAuthors Info & Claims

SYSTOR '23: Proceedings of the 16th ACM International Conference on Systems and Storage

Pages 35 - 48

https://doi.org/10.1145/3579370.3594766

Published: 22 June 2023 Publication History

Abstract

Major efforts on the design of persistent hash table on a non-volatile byte-addressable memory focus on efficient support of crash consistency with fence/flush primitives as well on non-disruptive table rehashing operations. When a data entry in a hash bucket cannot be updated with one atomic write, out-of-place update, instead of in-place update, is required to avoid data corruption after a failure. This often causes extra fences/flushes. Meanwhile, when open addressing techniques, such as linear probing, are adopted for high load factor, the scope of search for a key can be large. Excessive use of fence/flush and extended key search paths are two major sources of performance degradation with hash tables in persistent memory.

To address the issues, we design a persistent hash table, named TurboHash, for building high-performance key-value store. Turbo-Hash has a number of much desired features all in one design. (1) It supports out-of-place update with a cost equivalent to that of an in-place write to provide lock-free reads. (2) Long-distance linear probing is minimized (only when necessary). (3) It conducts only shard resizing for expansion and avoids expensive directory-level rehashing; And (4) it exploits hardware features for high I/O and computation efficiency, including Intel's Optane DC's performance characteristics and Intel AVX instructions. We have implemented TurboHash on the Optane persistent memory and conducted extensive evaluations. Experiment results show that TurboHash improves state-of-the-arts by 2-8 times in terms of throughput and latency.

References

[1]

[n.d.]. Diablo Memory Channel Storage. https://www.vladan.fr/ssd-storage-closer-to-cpu-thats-memory-channel-storage-by-diablo-technologies/.

[2]

[n.d.]. SanDisk ULLtraDIMM. https://en.wikipedia.org/wiki/ULLtraDIMM.

[3]

[n.d.]. Viking Technology SATADIMM. https://www.prnewswire.com/news-releases/viking-technology-satadimm-increases-ssd-capacity-in-solidfires-storage-system-219244711.html.

[4]

Austin Appleby. 2008. Murmurhash. https://sites.google.com/site/murmurhash/.

[5]

Alex D. Breslow, Dong Ping Zhang, Joseph L. Greathouse, Nuwan Jayasena, and Dean M. Tullsen. 2016. Horton Tables: Fast Hash Tables for In-Memory Data-Intensive Computing. In 2016 USENIX Annual Technical Conference (USENIX ATC 16). USENIX Association, Denver, CO, 281--294. https://www.usenix.org/conference/atc16/technical-sessions/presentation/breslow

[6]

Zhangyu Chen, Yu Huang, Bo Ding, and Pengfei Zuo. 2020. Lock-free Concurrent Level Hashing for Persistent Memory. In 2020 USENIX Annual Technical Conference (USENIX ATC 20). USENIX Association, online, 799--812. https://www.usenix.org/conference/atc20/presentation/chen

[7]

Brian F. Cooper, Adam Silberstein, Erwin Tam, Raghu Ramakrishnan, and Russell Sears. 2010. Benchmarking Cloud Serving Systems with YCSB. In Proceedings of the 1st ACM Symposium on Cloud Computing (Indianapolis, Indiana, USA) (SoCC '10). Association for Computing Machinery, New York, NY, USA, 143--154.

Digital Library

[8]

Tudor David, Rachid Guerraoui, and Vasileios Trigonakis. 2015. Asynchronized concurrency: The secret to scaling concurrent search data structures. ACM SIGARCH Computer Architecture News 43, 1 (2015), 631--644.

Digital Library

[9]

Biplob Debnath, Alireza Haghdoost, Asim Kadav, Mohammed G. Khatib, and Cristian Ungureanu. 2015. Revisiting Hash Table Design for Phase Change Memory. In Proceedings of the 3rd Workshop on Interactions of NVM/FLASH with Operating Systems and Workloads (Monterey, California) (INFLOW '15). Association for Computing Machinery, New York, NY, USA, Article 1, 9 pages.

Digital Library

[10]

Biplob Debnath, Sudipta Sengupta, and Jin Li. 2010. FlashStore: High Throughput Persistent Key-Value Store. Proc. VLDB Endow. 3, 1--2 (Sept. 2010), 1414--1425.

Digital Library

[11]

Ronald Fagin, Jurg Nievergelt, Nicholas Pippenger, and H. Raymond Strong. 1979. Extendible Hashing---a Fast Access Method for Dynamic Files. ACM Trans. Database Syst. 4, 3 (Sept. 1979), 315--344.

Digital Library

[12]

Bin Fan, David G. Andersen, and Michael Kaminsky. 2013. MemC3: Compact and Concurrent MemCache with Dumber Caching and Smarter Hashing. In 10th USENIX Symposium on Networked Systems Design and Implementation (NSDI 13). USENIX Association, Lombard, IL, 371--384. https://www.usenix.org/conference/nsdi13/technical-sessions/presentation/fan

[13]

Keir Fraser. 2004. Practical lock-freedom. Technical Report UCAM-CL-TR-579. University of Cambridge, Computer Laboratory.

[14]

H. Gao, J.F. Groote, and W.H. Hesselink. 2004. Almost wait-free resizable hashtables. In 18th International Parallel and Distributed Processing Symposium, 2004. Proceedings. 50--.

[15]

Maurice Herlihy, Nir Shavit, and Moran Tzafrir. 2008. Hopscotch Hashing. In Distributed Computing, Gadi Taubenfeld (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg, 350--364.

[16]

Daokun Hu, Zhiwen Chen, Jianbing Wu, Jianhua Sun, and Hao Chen. 2021. Persistent Memory Hash Indexes: An Experimental Evaluation. Proc. VLDB Endow. 14, 5 (Jan. 2021), 785--798.

Digital Library

[17]

Intel. [n.d.]. Persistent Memory Development Kit (PMDK). https://pmem.io/pmdk/.

[18]

Intel. 2021. Intel Optane Persistent Memory. https://www.intel.com/content/www/us/en/products/memory-storage/optane-dc-persistent-memory.html.

[19]

Olzhas Kaiyrakhmet, Songyi Lee, Beomseok Nam, Sam H. Noh, and Young ri Choi. 2019. SLM-DB: Single-Level Key-Value Store with Persistent Memory. In 17th USENIX Conference on File and Storage Technologies (FAST 19). USENIX Association, Boston, MA, 191--205. https://www.usenix.org/conference/fast19/presentation/kaiyrakhmet

[20]

Sudarsun Kannan, Nitish Bhat, Ada Gavrilovska, Andrea Arpaci-Dusseau, and Remzi Arpaci-Dusseau. 2018. Redesigning LSMs for Nonvolatile Memory with NoveLSM. In 2018 USENIX Annual Technical Conference (USENIX ATC 18). USENIX Association, Boston, MA, 993--1005. https://www.usenix.org/conference/atc18/presentation/kannan

Digital Library

[21]

Don Knuth. 1963. Notes On "Open" Addressing.

[22]

Donald E. Knuth. 1998. The Art of Computer Programming, Volume 3: (2nd Ed.) Sorting and Searching. Addison Wesley Longman Publishing Co., Inc., USA.

[23]

R. Madhava Krishnan, Wook-Hee Kim, Xinwei Fu, Sumit Kumar Monga, Hee Won Lee, Minsung Jang, Ajit Mathew, and Changwoo Min. 2021. TIPS: Making Volatile Index Structures Persistent with DRAM-NVMM Tiering. In 2021 USENIX Annual Technical Conference (USENIX ATC 21). USENIX Association, 773--787. https://www.usenix.org/conference/atc21/presentation/krishnan

[24]

Se Kwon Lee, Jayashree Mohan, Sanidhya Kashyap, Taesoo Kim, and Vijay Chidambaram. 2019. Recipe: Converting Concurrent DRAM Indexes to PersistentMemory Indexes. In Proceedings of the 27th ACM Symposium on Operating Systems Principles (Huntsville, Ontario, Canada) (SOSP '19). Association for Computing Machinery, New York, NY, USA, 462--477.

Digital Library

[25]

Baotong Lu, Xiangpeng Hao, Tianzheng Wang, and Eric Lo. 2020. Dash: Scalable Hashing on Persistent Memory. Proc. VLDB Endow. 13, 8 (April 2020), 1147--1161.

Digital Library

[26]

Tobias Maier, Peter Sanders, and Roman Dementiev. 2019. Concurrent Hash Tables: Fast and General(?)! 5, 4 (2019).

Digital Library

[27]

Moohyeon Nam, Hokeun Cha, Young ri Choi, Sam H. Noh, and Beomseok Nam. 2019. Write-Optimized Dynamic Hashing for Persistent Memory. In 17th USENIX Conference on File and Storage Technologies (FAST 19). USENIX Association, Boston, MA, 31--44. https://www.usenix.org/conference/fast19/presentation/nam

[28]

Fan Ni and Song Jiang. 2019. RapidCDC: Leveraging Duplicate Locality to Accelerate Chunking in CDC-Based Deduplication Systems. In Proceedings of the ACM Symposium on Cloud Computing (Santa Cruz, CA, USA) (SoCC '19). Association for Computing Machinery, New York, NY, USA, 220--232.

Digital Library

[29]

Jesper Puge Nielsen and Sven Karlsson. 2016. A Scalable Lock-Free Hash Table with Open Addressing. 51, 8 (2016).

Digital Library

[30]

Rajesh Nishtala, Hans Fugal, Steven Grimm, Marc Kwiatkowski, Herman Lee, Harry C. Li, Ryan McElroy, Mike Paleczny, Daniel Peek, Paul Saab, David Stafford, Tony Tung, and Venkateshwaran Venkataramani. 2013. Scaling Memcache at Facebook. In 10th USENIX Symposium on Networked Systems Design and Implementation (NSDI 13). USENIX Association, Lombard, IL, 385--398. https://www.usenix.org/conference/nsdi13/technical-sessions/presentation/nishtala

[31]

Ismail Oukid, Johan Lasperas, Anisoara Nica, Thomas Willhalm, and Wolfgang Lehner. 2016. FPTree: A Hybrid SCM-DRAM Persistent and Concurrent B-Tree for Storage Class Memory. In Proceedings of the 2016 International Conference on Management of Data (San Francisco, California, USA) (SIGMOD '16). Association for Computing Machinery, New York, NY, USA, 371--386.

Digital Library

[32]

Rasmus Pagh and Flemming Friche Rodler. 2004. Cuckoo Hashing. J. Algorithms 51, 2 (May 2004), 122--144.

Digital Library

[33]

Prashant Pandey, Michael A Bender, Alex Conway, Martín Farach-Colton, William Kuszmaul, Guido Tagliavini, and Rob Johnson. 2022. IcebergHT: High Performance PMEM Hash Tables Through Stability and Low Associativity. arXiv preprint arXiv:2210.04068 (2022).

[34]

Swapnil Patil and Garth Gibson. 2011. Scale and Concurrency of GIGA+: File System Directories with Millions of Files. In 9th USENIX Conference on File and Storage Technologies (FAST 11), Vol. 11. USENIX Association, San Jose, CA, 13--13. https://www.usenix.org/conference/fast11/scale-and-concurrency-giga-file-system-directories-millions-files

[35]

Frank Schmuck and Roger Haskin. 2002. GPFS: A Shared-Disk File System for Large Computing Clusters. In Proceedings of the 1st USENIX Conference on File and Storage Technologies (Monterey, CA) (FAST '02). USENIX Association, USA, 19--es.

Digital Library

[36]

Qing Wang, Youyou Lu, Junru Li, and Jiwu Shu. 2021. Nap: A Black-Box Approach to NUMA-Aware Persistent Memory Indexes. In 15th USENIX Symposium on Operating Systems Design and Implementation (OSDI 21). USENIX Association, 93--111. https://www.usenix.org/conference/osdi21/presentation/wang-qing

[37]

Xingbo Wu, Fan Ni, and Song Jiang. 2017. Search Lookaside Buffer: Efficient Caching for Index Data Structures. In Proceedings of the 2017 Symposium on Cloud Computing (Santa Clara, California) (SoCC '17). Association for Computing Machinery, New York, NY, USA, 27--39.

Digital Library

[38]

Lingfeng Xiang, Xingsheng Zhao, Jia Rao, Song Jiang, and Hong Jiang. 2022. Characterizing the Performance of Intel Optane Persistent Memory: A Close Look at Its on-DIMM Buffering. In Proceedings of the Seventeenth European Conference on Computer Systems (Rennes, France) (EuroSys '22). Association for Computing Machinery, New York, NY, USA, 488--505.

Digital Library

[39]

Baoyue Yan, Xuntao Cheng, Bo Jiang, Shibin Chen, Canfang Shang, Jianying Wang, Kenry Huang, Xinjun Yang, Wei Cao, and Feifei Li. 2021. Revisiting the Design of LSM-tree Based OLTP Storage Engine with Persistent Memory. Proc. VLDB Endow. 14, 10 (2021), 1872--1885. http://www.vldb.org/pvldb/vol14/p1872-yan.pdf

Digital Library

[40]

Jian Yang, Juno Kim, Morteza Hoseinzadeh, Joseph Izraelevitz, and Steve Swanson. 2020. An Empirical Guide to the Behavior and Use of Scalable Persistent Memory. In 18th USENIX Conference on File and Storage Technologies (FAST 20). USENIX Association, Santa Clara, CA, 169--182. https://www.usenix.org/conference/fast20/presentation/yang

Digital Library

[41]

Ting Yao, Yiwen Zhang, Jiguang Wan, Qiu Cui, Liu Tang, Hong Jiang, Changsheng Xie, and Xubin He. 2020. MatrixKV: Reducing Write Stalls and Write Amplification in LSM-tree Based KV Stores with Matrix Container in NVM. In 2020 USENIX Annual Technical Conference (USENIX ATC 20). USENIX Association, online, 17--31. https://www.usenix.org/conference/atc20/presentation/yao

[42]

Lu Zhang and Steven Swanson. 2019. Pangolin: A Fault-Tolerant Persistent Memory Programming Library. In 2019 USENIX Annual Technical Conference (USENIX ATC 19). USENIX Association, Renton, WA, 897--912. https://www.usenix.org/conference/atc19/presentation/zhang-lu

[43]

Wenhui Zhang, Xingsheng Zhao, Song Jiang, and Hong Jiang. 2021. ChameleonDB: A Key-Value Store for Optane Persistent Memory. In Proceedings of the Sixteenth European Conference on Computer Systems (Online Event, United Kingdom) (EuroSys '21). Association for Computing Machinery, New York, NY, USA, 194--209.

Digital Library

[44]

Pengfei Zuo and Yu Hua. 2018. A Write-Friendly and Cache-Optimized Hashing Scheme for Non-Volatile Memory Systems. IEEE Transactions on Parallel and Distributed Systems 29, 5 (2018), 985--998.

[45]

Pengfei Zuo, Yu Hua, and Jie Wu. 2018. Write-Optimized and High-Performance Hashing Index Scheme for Persistent Memory. In 13th USENIX Symposium on Operating Systems Design and Implementation (OSDI 18). USENIX Association, Carlsbad, CA, 461--476. https://www.usenix.org/conference/osdi18/presentation/zuo

[46]

Pengfei Zuo, Jiazhao Sun, Liu Yang, Shuangwu Zhang, and Yu Hua. 2021. Onesided RDMA-Conscious Extendible Hashing for Disaggregated Memory. In 2021 USENIX Annual Technical Conference (USENIX ATC 21). USENIX Association, 15--29. https://www.usenix.org/conference/atc21/presentation/zuo

[47]

Yoav Zuriel, Michal Friedman, Gali Sheffi, Nachshon Cohen, and Erez Petrank. 2019. Efficient Lock-Free Durable Sets. Proc. ACM Program. Lang. 3, OOPSLA, Article 128 (Oct. 2019), 26 pages.

Digital Library

Cited By

Katsarakis AGavrielatos VNtarmos NMencagli GDazzi PLowenthal DBadia R(2024)DLHT: A Non-blocking Resizable Hashtable with Fast Deletes and Memory-awarenessProceedings of the 33rd International Symposium on High-Performance Parallel and Distributed Computing10.1145/3625549.3658682(186-199)Online publication date: 3-Jun-2024
https://dl.acm.org/doi/10.1145/3625549.3658682
Zhong CZhou QChen YZhao XHe KPan AJiang S(2024)IndeXY: A Framework for Constructing Indexes Larger than Memory2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00046(516-529)Online publication date: 13-May-2024
https://doi.org/10.1109/ICDE60146.2024.00046

Index Terms

TurboHash: A Hash Table for Key-value Store on Persistent Memory

Recommendations

Revisiting persistent hash table design for commercial non-volatile memory
DATE '20: Proceedings of the 23rd Conference on Design, Automation and Test in Europe

Emerging non-volatile memory technologies bring evolution to storage systems and durable data structures. Among them, a proliferation of researches on persistent hash table employ NVM as the storage layer for both fast access and efficient persistence. ...
A read-efficient and write-optimized hash table for Intel Optane DC Persistent Memory
Abstract
Emerging non-volatile memory technologies are driving the next generation of storage systems and durable data structures. Among them, many hash table proposals employ NVM as the storage layer for both fast access and efficient persistence. Most ...
Highlights
- A cached table-inclined read mechanism speeds up search requests.
- A log-free atomic write mechanism minimizes overhead for write requests.
- An efficient shadowing synchronization mechanism enables fast data synchronization.
- A ...
A scalable and persistent key-value store using non-volatile memory
SAC '19: Proceedings of the 34th ACM/SIGAPP Symposium on Applied Computing

Non-volatile random-access memory¹ has gained recent attention because of its guaranteed data persistence and low data access latency. In-memory key-value stores generally operate by storing log files, which generate disk I/O to prevent data loss from ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SYSTOR '23: Proceedings of the 16th ACM International Conference on Systems and Storage

June 2023

168 pages

ISBN:9781450399623

DOI:10.1145/3579370

Chair:
Yosef Moatti,
General Chair:
Ofer Biran
IBM Research - Haifa, Israel
,
Program Chairs:
Yossi Gilad
Hebrew University of Jerusalem, Israel
,
Dejan Kostic
KTH Royal Institute of Technology, Sweden

Copyright © 2023 Owner/Author(s).

This work is licensed under a Creative Commons Attribution International 4.0 License.

Sponsors

SIGOPS: ACM Special Interest Group on Operating Systems

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 June 2023

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SYSTOR '23

Sponsor:

SIGOPS

SYSTOR '23: 16th ACM International Conference on Systems and Storage

June 5 - 7, 2023

Haifa, Israel

Acceptance Rates

SYSTOR '23 Paper Acceptance Rate 12 of 30 submissions, 40%;

Overall Acceptance Rate 108 of 323 submissions, 33%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
621
Total Downloads

Downloads (Last 12 months)390
Downloads (Last 6 weeks)39

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Katsarakis AGavrielatos VNtarmos NMencagli GDazzi PLowenthal DBadia R(2024)DLHT: A Non-blocking Resizable Hashtable with Fast Deletes and Memory-awarenessProceedings of the 33rd International Symposium on High-Performance Parallel and Distributed Computing10.1145/3625549.3658682(186-199)Online publication date: 3-Jun-2024
https://dl.acm.org/doi/10.1145/3625549.3658682
Zhong CZhou QChen YZhao XHe KPan AJiang S(2024)IndeXY: A Framework for Constructing Indexes Larger than Memory2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00046(516-529)Online publication date: 13-May-2024
https://doi.org/10.1109/ICDE60146.2024.00046

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents