research-article

HiLSM: an LSM-based key-value store for hybrid NVM-SSD storage systems

Authors:

Yungang BaoAuthors Info & Claims

CF '20: Proceedings of the 17th ACM International Conference on Computing Frontiers

Pages 208 - 216

https://doi.org/10.1145/3387902.3392621

Published: 23 May 2020 Publication History

Abstract

In order to ensure data durability and crash consistency, the LSM-tree based key-value stores suffer from high WAL synchronization overhead. Fortunately, the advent of NVM offers an opportunity to address this issue. However, NVM is currently too expensive to meet the demand of massive storage systems. Therefore, the hybrid NVM and SSD storage system provides a more cost-efficient solution. This paper proposes HiLSM, a key-value store for hybrid NVM-SSD storage systems. According to the characteristics of hybrid storage mediums, HiLSM adopts hybrid data structures consisting of the log-structured memory and the LSM-tree. Aiming at the issue of write stalls in write intensive scenario, a fine-grained data migration strategy is proposed to make the data migration start as early as possible. Aiming at the performance gap between NVM and SSD, a multi-threaded data migration strategy is proposed to make the data migration complete as soon as possible. Aiming at the LSM-tree's inherent issue of write amplification, a data filtering strategy is proposed to make data updates be absorbed in NVM as much as possible. We compare HiLSM with the state-of-the-art key-value stores via extensive experiments and the results show that HiLSM achieves 1.3x higher throughput for write, 10x higher throughput for read and 79% less write traffic under the skewed workload.

References

[1]

Apache. [n.d.]. Cassandra. http://cassandra.apache.org/

[2]

Apache. [n.d.]. HBase. https://hbase.apache.org/

[3]

Oana Balmau, Diego Didona, Rachid Guerraoui, Willy Zwaenepoel, Huapeng Yuan, Aashray Arora, Karan Gupta, and Pavan Konka. 2017. {TRIAD}: Creating Synergies Between Memory, Disk and Log in Log Structured Key-Value Stores. In 2017 {USENIX} Annual Technical Conference ({USENIX} {ATC} 17). 363--375.

[4]

Oana Balmau, Rachid Guerraoui, Vasileios Trigonakis, and Igor Zablotchi. 2017. FloDB: Unlocking memory in persistent key-value stores. In Proceedings of the Twelfth European Conference on Computer Systems. ACM, 80--94.

Digital Library

[5]

Doug Beaver, Sanjeev Kumar, Harry C Li, Jason Sobel, Peter Vajgel, et al. 2010. Finding a Needle in Haystack: Facebook's Photo Storage. In OSDI, Vol. 10. 1--8.

Digital Library

[6]

Philip A Bernstein and Nathan Goodman. 1983. Multiversion concurrency control-theory and algorithms. ACM Transactions on Database Systems (TODS) 8, 4 (1983), 465--483.

Digital Library

[7]

Burton H Bloom. 1970. Space/time trade-offs in hash coding with allowable errors. Commun. ACM 13, 7 (1970), 422--426.

Digital Library

[8]

Helen HW Chan, Chieh-Jan Mike Liang, Yongkun Li, Wenjia He, Patrick PC Lee, Lianjie Zhu, Yaozu Dong, Yinlong Xu, Yu Xu, Jin Jiang, et al. 2018. HashKV: Enabling Efficient Updates in {KV} Storage via Hashing. In 2018 {USENIX} Annual Technical Conference ({USENIX} {ATC} 18). 1007--1019.

[9]

Fay Chang, Jeffrey Dean, Sanjay Ghemawat, Wilson C Hsieh, Deborah A Wallach, Mike Burrows, Tushar Chandra, Andrew Fikes, and Robert E Gruber. 2008. Bigtable: A distributed storage system for structured data. ACM Transactions on Computer Systems (TOCS) 26, 2 (2008), 4.

Digital Library

[10]

Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein. 2009. Introduction to algorithms. MIT press. 259--260 pages.

[11]

Giuseppe DeCandia, Deniz Hastorun, Madan Jampani, Gunavardhan Kakulapati, Avinash Lakshman, Alex Pilchin, Swaminathan Sivasubramanian, Peter Vosshall, and Werner Vogels. 2007. Dynamo: amazon's highly available key-value store. In ACM SIGOPS operating systems review, Vol. 41. ACM, 205--220.

[12]

Facebook. [n.d.]. RocksDB. https://rocksdb.org/

[13]

Caixin Gong, Shuibing He, Yili Gong, and Yingchun Lei. 2019. On Integration of Appends and Merges in Log-Structured Merge Trees. In Proceedings of the 48th International Conference on Parallel Processing. ACM, 103.

Digital Library

[14]

Google. [n.d.]. LevelDB. https://github.com/google/leveldb.

[15]

Yiming Huai et al. 2008. Spin-transfer torque MRAM (STT-MRAM): Challenges and prospects. AAPPS bulletin 18, 6 (2008), 33--40.

[16]

PR Intel. 2015. Intel and micron produce breakthrough memory technology. Intel Newsroom, http://newsroom.intel.com/community/intel_newsroom/blog/2015/07/28/intel-and-micron-producebreakthrough-memory-technology (accessed Apr 30, 2018) (2015).

[17]

Joseph Izraelevitz, Jian Yang, Lu Zhang, Juno Kim, Xiao Liu, Amirsaman Memaripour, Yun Joon Soh, Zixuan Wang, Yi Xu, Subramanya R Dulloor, et al. 2019. Basic performance measurements of the intel optane DC persistent memory module. arXiv preprint arXiv:1903.05714 (2019).

[18]

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). 191--205.

[19]

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). 993--1005.

[20]

Hyojun Kim, Sangeetha Seshadri, Clement L Dickey, and Lawrence Chiu. 2013. Phase change memory in enterprise storage systems: silver bullet or snake oil?. In Proceedings of the 1st Workshop on Interactions of NVM/FLASH with Operating Systems and Workloads. 1--8.

Digital Library

[21]

Martin Kleppmann. 2017. Designing data-intensive applications: The big ideas behind reliable, scalable, and maintainable systems. " O'Reilly Media, Inc.".

[22]

Youngjin Kwon, Henrique Fingler, Tyler Hunt, Simon Peter, Emmett Witchel, and Thomas Anderson. 2017. Strata: A cross media file system. In Proceedings of the 26th Symposium on Operating Systems Principles. ACM, 460--477.

Digital Library

[23]

Jianhong Li, Andrew Pavlo, and Siying Dong. 2017. NVMRocks: RocksDB on non-volatile memory systems.

[24]

Lanyue Lu, Thanumalayan Sankaranarayana Pillai, Andrea C Arpaci-Dusseau, and Remzi H Arpaci-Dusseau. 2016. Wisckey: Separating keys from values in ssd-conscious storage. In 14th {USENIX} Conference on File and Storage Technologies ({FAST} 16). 133--148.

[25]

Patrick O'Neil, Edward Cheng, Dieter Gawlick, and Elizabeth O'Neil. 1996. The log-structured merge-tree (LSM-tree). Acta Informatica 33, 4 (1996), 351--385.

Digital Library

[26]

John Ousterhout, Arjun Gopalan, Ashish Gupta, Ankita Kejriwal, Collin Lee, Behnam Montazeri, Diego Ongaro, Seo Jin Park, Henry Qin, Mendel Rosenblum, et al. 2015. The RAMCloud storage system. ACM Transactions on Computer Systems (TOCS) 33, 3 (2015), 7.

Digital Library

[27]

Pandian Raju, Rohan Kadekodi, Vijay Chidambaram, and Ittai Abraham. 2017. Pebblesdb: Building key-value stores using fragmented log-structured merge trees. In Proceedings of the 26th Symposium on Operating Systems Principles. ACM, 497--514.

Digital Library

[28]

Stephen M Rumble, Ankita Kejriwal, and John Ousterhout. 2014. Log-structured memory for DRAM-based storage. In Proceedings of the 12th {USENIX} Conference on File and Storage Technologies ({FAST} 14). 1--16.

Digital Library

[29]

Roshan Sumbaly, Jay Kreps, Lei Gao, Alex Feinberg, Chinmay Soman, and Sam Shah. 2012. Serving large-scale batch computed data with project voldemort. In Proceedings of the 10th USENIX conference on File and Storage Technologies. USENIX Association, 18--18.

Digital Library

[30]

Haris Volos, Guilherme Magalhaes, Ludmila Cherkasova, and Jun Li. 2015. Quartz: A lightweight performance emulator for persistent memory software. In Proceedings of the 16th Annual Middleware Conference. 37--49.

Digital Library

[31]

H-S Philip Wong, Simone Raoux, SangBum Kim, Jiale Liang, John P Reifenberg, Bipin Rajendran, Mehdi Asheghi, and Kenneth E Goodson. 2010. Phase change memory. Proc. IEEE 98, 12 (2010), 2201--2227.

[32]

Fei Xia, Dejun Jiang, Jin Xiong, and Ninghui Sun. 2017. HiKV: a hybrid index key-value store for DRAM-NVM memory systems. In 2017 {USENIX} Annual Technical Conference ({USENIX} {ATC} 17). 349--362.

[33]

Jun Yang, Qingsong Wei, Cheng Chen, Chundong Wang, Khai Leong Yong, and Bingsheng He. 2015. NV-Tree: reducing consistency cost for NVM-based single level systems. In 13th {USENIX} Conference on File and Storage Technologies ({FAST} 15). 167--181.

[34]

Yinliang Yue, Bingsheng He, Yuzhe Li, and Weiping Wang. 2016. Building an efficient put-intensive key-value store with skip-tree. IEEE Transactions on Parallel and Distributed Systems 28, 4 (2016), 961--973.

Digital Library

[35]

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). 461--476.

Cited By

Yu QGuo CZhuang JThakkar VWang JCao Z(2024)CaaS-LSM: Compaction-as-a-Service for LSM-based Key-Value Stores in Storage Disaggregated InfrastructureProceedings of the ACM on Management of Data10.1145/36549272:3(1-28)Online publication date: 30-May-2024
https://dl.acm.org/doi/10.1145/3654927
Kim DLee JLim KHeo JHam TLee J(2024)An LSM Tree Augmented with B+ Tree on Nonvolatile MemoryACM Transactions on Storage10.1145/363347520:1(1-24)Online publication date: 30-Jan-2024
https://dl.acm.org/doi/10.1145/3633475
Wang ZShao Z(2023)MirrorKV: An Efficient Key-Value Store on Hybrid Cloud Storage with Balanced Performance of Compaction and QueryingProceedings of the ACM on Management of Data10.1145/36267361:4(1-27)Online publication date: 12-Dec-2023
https://dl.acm.org/doi/10.1145/3626736
Show More Cited By

Index Terms

HiLSM: an LSM-based key-value store for hybrid NVM-SSD storage systems
1. Information systems
  1. Data management systems
    1. Database management system engines
      1. Parallel and distributed DBMSs
        Key-value stores

Recommendations

PebblesDB: Building Key-Value Stores using Fragmented Log-Structured Merge Trees
SOSP '17: Proceedings of the 26th Symposium on Operating Systems Principles

Key-value stores such as LevelDB and RocksDB offer excellent write throughput, but suffer high write amplification. The write amplification problem is due to the Log-Structured Merge Trees data structure that underlies these key-value stores. To remedy ...
HyperDB: a Novel Key Value Store for Reducing Background Traffic in Heterogeneous SSD Storage
ICPP '24: Proceedings of the 53rd International Conference on Parallel Processing

Log-structured merge tree (LSM-tree) has been widely adopted by modern key-value stores. Deploying LSM-tree across heterogeneous SSD storage which combines the fast but expensive NVMe storage tier with the slow but economical SATA storage tier has ...
Prism: Optimizing Key-Value Store for Modern Heterogeneous Storage Devices
ASPLOS 2023: Proceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 2

As data generation has been on an upward trend, storing vast volumes of data cost-effectively as well as efficiently accessing them is paramount. At the same time, today's storage landscape continues to diversify, from high-bandwidth storage devices ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CF '20: Proceedings of the 17th ACM International Conference on Computing Frontiers

May 2020

298 pages

ISBN:9781450379564

DOI:10.1145/3387902

General Chairs:
Maurizio Palesi
University of Catania, IT
,
Gianluca Palermo
Politecnico di Milano, IT
,
Program Chairs:
Cat Graves
Hewlett Packard Labs
,
Eishi Arima
ITC University of Tokyo, JP

Copyright © 2020 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]

Sponsors

SIGMICRO: ACM Special Interest Group on Microarchitectural Research and Processing

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 May 2020

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

CF '20

Sponsor:

SIGMICRO

CF '20: Computing Frontiers Conference

May 11 - 13, 2020

Sicily, Catania, Italy

Acceptance Rates

Overall Acceptance Rate 273 of 785 submissions, 35%

Upcoming Conference

CF '25

Sponsor:
sigmicro

22nd ACM International Conference on Computing Frontiers

May 28 - 30, 2025

Cagliari , Italy

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

18
Total Citations
View Citations
796
Total Downloads

Downloads (Last 12 months)81
Downloads (Last 6 weeks)8

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Yu QGuo CZhuang JThakkar VWang JCao Z(2024)CaaS-LSM: Compaction-as-a-Service for LSM-based Key-Value Stores in Storage Disaggregated InfrastructureProceedings of the ACM on Management of Data10.1145/36549272:3(1-28)Online publication date: 30-May-2024
https://dl.acm.org/doi/10.1145/3654927
Kim DLee JLim KHeo JHam TLee J(2024)An LSM Tree Augmented with B+ Tree on Nonvolatile MemoryACM Transactions on Storage10.1145/363347520:1(1-24)Online publication date: 30-Jan-2024
https://dl.acm.org/doi/10.1145/3633475
Wang ZShao Z(2023)MirrorKV: An Efficient Key-Value Store on Hybrid Cloud Storage with Balanced Performance of Compaction and QueryingProceedings of the ACM on Management of Data10.1145/36267361:4(1-27)Online publication date: 12-Dec-2023
https://dl.acm.org/doi/10.1145/3626736
Wang ZYin S(2023)RBC: A bandwidth controller to reduce write-stalls and tail latencyProceedings of the 52nd International Conference on Parallel Processing10.1145/3605573.3605601(213-222)Online publication date: 7-Aug-2023
https://dl.acm.org/doi/10.1145/3605573.3605601
Raina ALu JCidon AFreedman MAamodt TJerger NSwift M(2023)Efficient Compactions between Storage Tiers with PrismDBProceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 310.1145/3582016.3582052(179-193)Online publication date: 25-Mar-2023
https://dl.acm.org/doi/10.1145/3582016.3582052
Park CLiu CKang KKandemir MChoi W(2023)Design of a High-Performance, High-Endurance Key-Value SSD for Large-Key WorkloadsIEEE Computer Architecture Letters10.1109/LCA.2023.328227622:2(149-152)Online publication date: Jul-2023
https://doi.org/10.1109/LCA.2023.3282276
Huang ZFan HCheng CWu SJin H(2023)Duo: Improving Data Sharing of Stateful Serverless Applications by Efficiently Caching Multi-Read Data2023 IEEE International Parallel and Distributed Processing Symposium (IPDPS)10.1109/IPDPS54959.2023.00092(875-885)Online publication date: May-2023
https://doi.org/10.1109/IPDPS54959.2023.00092
Chen LChen RYang CHan YZhang RZhou XJin PQian W(2023)Workload-Aware Log-Structured Merge Key-Value Store for NVM-SSD Hybrid Storage2023 IEEE 39th International Conference on Data Engineering (ICDE)10.1109/ICDE55515.2023.00171(2207-2219)Online publication date: Apr-2023
https://doi.org/10.1109/ICDE55515.2023.00171
Zhao JPan YZhang HLin MLuo XXu Z(2023)InPlaceKV: in-place update scheme for SSD-based KV storage systems under update-intensive WorklaodsCluster Computing10.1007/s10586-023-04031-927:2(1527-1540)Online publication date: 28-May-2023
https://doi.org/10.1007/s10586-023-04031-9
Cai TMa YLiu PNiu DLi L(2022)A New NVM Device Driver for IoT Time Series DatabaseMicromachines10.3390/mi1303038513:3(385)Online publication date: 27-Feb-2022
https://doi.org/10.3390/mi13030385
Show More Cited By

View Options

Get Access

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