research-article

NVC-Hashmap: A Persistent and Concurrent Hashmap For Non-Volatile Memories

Authors:

Markus Dreseler,

Matthias Uflacker,

Hasso PlattnerAuthors Info & Claims

IMDM '15: Proceedings of the 3rd VLDB Workshop on In-Memory Data Mangement and Analytics

Article No.: 4, Pages 1 - 8

https://doi.org/10.1145/2803140.2803144

Published: 31 August 2015 Publication History

Abstract

Non-volatile RAM (NVRAM) will fundamentally change in-memory databases as data structures do not have to be explicitly backed up to hard drives or SSDs, but can be inherently persistent in main memory. To guarantee consistency even in the case of power failures, programmers need to ensure that data is flushed from volatile CPU caches where it would be susceptible to power outages to NVRAM.

In this paper, we present the NVC-Hashmap, a lock-free hashmap that is used for unordered dictionaries and delta indices in in-memory databases. The NVC-Hashmap is then evaluated in both stand-alone and integrated database benchmarks and compared to a B+-Tree based persistent data structure.

References

[1]

Joy Arulraj, Andrew Pavlo, and Subramanya R. Dulloor. "Let's Talk About Storage & Recovery Methods for Non-Volatile Memory Database Systems". SIGMOD. 2015, pp. 707--722.

Digital Library

[2]

Brian N Bershad. "Practical Considerations for Non-Blocking Concurrent Objects". IEEE International Conference on Distributed Computing Systems (ICDCS). 2007, pp. 264--273.

[3]

Shimin Chen and Qin Jin. "Persistent B+-Trees in Non-Volatile Main Memory". Proceedings of the VLDB Endowment 8.7 (2015), pp. 786--797.

Digital Library

[4]

Ping Chi, Wang-Chien Lee, and Yuan Xie. "Making B+-tree Efficient in PCM-based Main Memory". International Symposium on Low Power Electronics and Design (ISLPED), pp. 69--74.

Digital Library

[5]

Subramanya R Dulloor et al. "System software for persistent memory". European Conference on Computer Systems (EuroSys). 2014, 15:1--15:15.

Digital Library

[6]

Martin Faust, David Schwalb, and Hasso Plattner. "Composite Group-Keys". International Workshop on In-Memory Data Management and Analytics (IMDM) (2014), pp. 42--54.

[7]

Martin Grund et al. "HYRISE---A Main Memory Hybrid Storage Engine". Proceedings of the VLDB 4.2 (2010), pp. 105--116.

Digital Library

[8]

Maurice Herlihy and Nir Shavit. The Art of Multiprocessor Programming. Morgan Kaufmann, 2008.

Digital Library

[9]

Maurice Herlihy and Jeannette M Wing. "Linearizability: A Correctness Condition for Concurrent Objects". ACM Transactions on Programming Languages and Systems 12.3 (1990), pp. 463--492.

Digital Library

[10]

Jian Huang, Karsten Schwan, and Moinuddin Qureshi. "NVRAM-aware Logging in Transaction Systems". Proceedings of the VLDB 8.4 (2014), pp. 389--400.

Digital Library

[11]

Intel Corporation. Intel® Architecture Instruction Set Extensions Programming Reference. 2014.

[12]

Hideaki Kimura. "FOEDUS: OLTP Engine for a Thousand Cores and NVRAM". SIGMOD. 2015, pp. 691--706.

Digital Library

[13]

Witold Litwin. "Linear Hashing: A New Tool for File and Table Addressing". VLDB. 1980, pp. 212--223.

Digital Library

[14]

Iulian Moraru et al. "Consistent, Durable, and Safe Memory Management for Byte-addressable Non Volatile Main Memory". ACM SIGOPS. 2013.

Digital Library

[15]

Dushyanth Narayanan and Orion Hodson. "Whole-System Persistence". International Conference on Architectural Support for Programming Languages and Operating Systems ASPLOS (2012), pp. 401--410.

Digital Library

[16]

Ismail Oukid et al. "Instant Recovery for Main Memory Databases". Conference on Innovative Data Systems Research (CIDR). 2015.

[17]

Vasily A Sartakov and Rüdiger Kapitza. "NV-Hypervisor: Hypervisor-based Persistence for Virtual Machines". IEEE/IFIP International Conference on Dependable Systems and Networks (2014), pp. 654--659.

Digital Library

[18]

Ori Shalev and Nir Shavit. "Split-Ordered Lists: Lock-Free Extensible Hash Tables". Journal of the ACM 53.3 (2006), pp. 397--405.

Digital Library

[19]

Shivaram Venkataraman et al. "Consistent and Durable Data Structures for Non-Volatile Byte-Addressable Memory". USENIX Conference on File and Storage Technologies FAST (2010), pp. 1--15.

Digital Library

Cited By

Wang HDai HChen SChen G(2024)Rethinking Hash Tables: Challenges and Opportunities with Compute Express Link (CXL)Proceedings of the ACM Turing Award Celebration Conference - China 202410.1145/3674399.3674418(23-27)Online publication date: 5-Jul-2024
https://dl.acm.org/doi/10.1145/3674399.3674418
Chen ZHu DChe WSun JChen H(2024)A quantitative evaluation of persistent memory hash indexesThe VLDB Journal — The International Journal on Very Large Data Bases10.1007/s00778-023-00812-133:2(375-397)Online publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1007/s00778-023-00812-1
Pandey PBender MConway AFarach-Colton MKuszmaul WTagliavini GJohnson R(2023)IcebergHT: High Performance Hash Tables Through Stability and Low AssociativityProceedings of the ACM on Management of Data10.1145/35887271:1(1-26)Online publication date: 30-May-2023
https://dl.acm.org/doi/10.1145/3588727
Show More Cited By

Recommendations

WOM-Code Solutions for Low Latency and High Endurance in Phase Change Memory
This paper describes a write-once-memory-code phase change memory (WOM-code PCM) architecture for next-generation non-volatile memory applications. Specifically, we address the long latency of the write operation in PCM—attributed to PCM SET—...
A Novel Memory Block Management Scheme for PCM Using WOM-Code
HPCC-CSS-ICESS '15: Proceedings of the 2015 IEEE 17th International Conference on High Performance Computing and Communications, 2015 IEEE 7th International Symposium on Cyberspace Safety and Security, and 2015 IEEE 12th International Conf on Embedded Software and Systems

Phase Change Memory (PCM) is a promising DRAM replacement in embedded systems due to its attractive characteristics including low static power consumption and high density. However, long write latency is one of the major drawbacks in current PCM ...
Mellow writes: extending lifetime in resistive memories through selective slow write backs
ISCA'16

Emerging resistive memory technologies, such as PCRAM and ReRAM, have been proposed as promising replacements for DRAM-based main memory, due to their better scalability, low standby power, and non-volatility. However, limited write endurance is a major ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

IMDM '15: Proceedings of the 3rd VLDB Workshop on In-Memory Data Mangement and Analytics

August 2015

63 pages

ISBN:9781450337137

DOI:10.1145/2803140

Copyright © 2015 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

In-Cooperation

SAMSUNG: SAMSUNG
VLDB Endowment: Very Large Database Endowment
Microsoft: Microsoft

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 31 August 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article
Research
Refereed limited

Conference

IMDM '15

IMDM '15: VLDB Workshop on In-Memory Data Mangement and Analytics

August 31, 2015

HI, Kohala Coast, USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

33
Total Citations
View Citations
515
Total Downloads

Downloads (Last 12 months)32
Downloads (Last 6 weeks)2

Reflects downloads up to 30 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wang HDai HChen SChen G(2024)Rethinking Hash Tables: Challenges and Opportunities with Compute Express Link (CXL)Proceedings of the ACM Turing Award Celebration Conference - China 202410.1145/3674399.3674418(23-27)Online publication date: 5-Jul-2024
https://dl.acm.org/doi/10.1145/3674399.3674418
Chen ZHu DChe WSun JChen H(2024)A quantitative evaluation of persistent memory hash indexesThe VLDB Journal — The International Journal on Very Large Data Bases10.1007/s00778-023-00812-133:2(375-397)Online publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1007/s00778-023-00812-1
Pandey PBender MConway AFarach-Colton MKuszmaul WTagliavini GJohnson R(2023)IcebergHT: High Performance Hash Tables Through Stability and Low AssociativityProceedings of the ACM on Management of Data10.1145/35887271:1(1-26)Online publication date: 30-May-2023
https://dl.acm.org/doi/10.1145/3588727
Gong CTian CWang ZWang SWang XFu QQin WQian LChen RQi JWang RZhu GYang CZhang WLi F(2022)Tair-PMemProceedings of the VLDB Endowment10.14778/3554821.355482715:12(3346-3358)Online publication date: 1-Aug-2022
https://dl.acm.org/doi/10.14778/3554821.3554827
Wang ZYao TWan JJiang HCui QTang LZhang YZhang Q(2022)ComboTree: A Persistent Indexing Structure With Universal Operational Efficiency and ScalabilityIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2021.313724733:10(2277-2290)Online publication date: 1-Oct-2022
https://doi.org/10.1109/TPDS.2021.3137247
Benson LMakait HRabl T(2021)ViperProceedings of the VLDB Endowment10.14778/3461535.346154314:9(1544-1556)Online publication date: 22-Oct-2021
https://dl.acm.org/doi/10.14778/3461535.3461543
Hu DChen ZWu JSun JChen H(2021)Persistent memory hash indexesProceedings of the VLDB Endowment10.14778/3446095.344610114:5(785-798)Online publication date: 23-Mar-2021
https://dl.acm.org/doi/10.14778/3446095.3446101
Gugnani SKashyap ALu X(2021)Understanding the idiosyncrasies of real persistent memoryProceedings of the VLDB Endowment10.14778/3436905.343692114:4(626-639)Online publication date: 22-Feb-2021
https://dl.acm.org/doi/10.14778/3436905.3436921
Lu BHao XWang TLo E(2021)Scaling Dynamic Hash Tables on Real Persistent MemoryACM SIGMOD Record10.1145/3471485.347150650:1(87-94)Online publication date: 17-Jun-2021
https://dl.acm.org/doi/10.1145/3471485.3471506
Izadpanah RPeterson CSolihin YDechev D(2021)PETRAACM Transactions on Architecture and Code Optimization10.1145/344639118:2(1-26)Online publication date: 8-Mar-2021
https://dl.acm.org/doi/10.1145/3446391
Show More Cited By

View Options

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents