research-article

Iterator Interface Extended LSM-tree-based KVSSD for Range Queries

Authors:

Anand Sivasubramaniam,

Youngjae KimAuthors Info & Claims

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

Pages 60 - 70

https://doi.org/10.1145/3579370.3594775

Published: 22 June 2023 Publication History

Abstract

Key-Value SSD (KVSSD) has shown great potential for several important classes of emerging data stores due to its high throughput and low latency. When designing a key-value store with range queries, an LSM-tree is considered a better choice than a hash table due to its key ordering. However, the design space for range queries in LSM-tree-based KVSSDs has yet to be explored, despite range queries being one of the most demanding features. In this paper, we investigate the design constraints in LSM-tree-based KVSSDs from the perspective of range queries and propose three design principles. Based on these principles, we present IterKVSSD, an Iterator interface extended LSM-tree-based KVSSD for range queries. We implement IterKVSSD on OpenSSD Cosmos+, and our evaluation shows that it increases range query throughput by up to 4.13× and 7.22× for random and sequential key distributions, respectively, compared to existing KVSSDs.

References

[1]

Berk Atikoglu, Yuehai Xu, Eitan Frachtenberg, Song Jiang, and Mike Paleczny. 2012. Workload Analysis of A Large-scale Key-Value Store. In Proceedings of the 12th ACM SIGMETRICS/PERFORMANCE joint international conference on Measurement and Modeling of Computer Systems. ACM, 53--64.

Digital Library

[2]

Janki Bhimani, Jingpei Yang, Ningfang Mi, Changho Choi, and Manoj Saha. 2021. Fine-grained Control of Concurrency within KV-SSDs. In Proceeding of the 14th ACM International System and Storage Conference (SYSTOR '21). ACM, Association for Computing Machinery, 1--12.

Digital Library

[3]

Zhichao Cao, Siying Dong, Sagar Vemuri, and David H.C. Du. 2020. Characterizing, Modeling, and Benchmarking RocksDB Key-Value Workloads at Facebook. In Proceedings of the 18th USENIX Conference on File and Storage Technologies (FAST '20). 209--223.

[4]

Helen H. W. Chan, Yongkun Li, Patrick P. C. Lee, and Yinlong Xu. 2018. HashKV: Enabling Efficient Updates in KV Storage via Hashing. In 2018 USENIX Annual Technical Conference (USENIX ATC 18). 1007--1019.

[5]

Fay Chang, Jeffrey Dean, Sanjay Ghemawat, Wilson C. Hsieh, Deborah A. Wallach, Mike Burrows, Tushar Chandra, Andrew Fikes, and Robert E. Gruber. 2006. Bigtable: A Distributed Storage System for Structured Data. In Proceedings of the USENIX Symposium on Operating Systems Design and Implementation (OSDI '06). 1--15.

[6]

Chanwoo Chung, Jinhyung Koo, Junsu Im, Arvind, and Sungjin Lee. 2019. LightStore: Software-Defined Network-Attached Key-Value Drives. In Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS '19). 939--953.

Digital Library

[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 (SoCC '10). 143--154.

Digital Library

[8]

Facebook. 2021. RocksDB. http://rocksdb.org

[9]

Facebook. 2021. RocksDB Database Benchmark Tool. https://github.com/facebook/rocksdb/wiki/Benchmarking-tools

[10]

Meta. Facebook. 2022. RocksDB v7.2.2 Release. https://github.com/facebook/rocksdb/releases/tag/v7.2.2.

[11]

Google. 2017. LevelDB. https://github.com/google/leveldb.

[12]

Junsu Im, Jinwook Bae, Chanwoo Chung, Arvind, and Sungjin Lee. 2020. PinK: High-speed In-storage Key-value Store with Bounded Tails. In Proceedings of the USENIX Annual Technical Conference (ATC '20). 173--187.

[13]

Yanqin Jin, Hung-Wei Tseng, Yannis Papakonstantinou, and Steven Swanson. 2017. KAML: A Flexible, High-performance Key-value SSD. In Proceedings of the IEEE International Symposium on High Performance Computer Architecture (HPCA '17). 373--384.

[14]

Yangwook Kang, Rekha Pitchumani, Pratik Mishra, Yang-suk Kee, Francisco Londono, Sangyoon Oh, Jongyeol Lee, and Daniel DG Lee. 2019. Towards Building A High-performance, Scale-in Key-Value Storage System. In Proceedings of the 12th ACM International Conference on Systems and Storage (SYSTOR '19). 144--154.

Digital Library

[15]

Yang Seok Ki. 2017. Key Value SSD Explained-Concept, Device, System, and Standard. In Storage Developer Conference.

[16]

Jinhyung Koo, Junsu Im, Jooyoung Song, Juhyung Park, Eunji Lee, Bryan S. Kim, and Sungjin Lee. 2021. Modernizing File System through In-Storage Indexing. In Proceedings of the 15th USENIX Symposium on Operating Systems Design and Implementation (OSDI '21). 75--92.

[17]

Jaewook Kwak, Sangjin Lee, Kibin Park, Jinwoo Jeong, and Yong Ho Song. 2020. Cosmos+ OpenSSD: Rapid Prototype for Flash Storage Systems. ACM Trans. Storage, Article 15 (July 2020), 35 pages.

[18]

Avinash Lakshman and Prashant Malik. 2010. Cassandra: A Decentralized Structured Storage System. SIGOPS Oper. Syst. Rev. 44, 2 (2010), 35--40.

Digital Library

[19]

Chang-Gyu Lee, Hyeongu Kang, Donggyu Park, Sungyong Park, Youngjae Kim, Jungki Noh, Woosuk Chung, and Kyoung Park. 2019. iLSM-SSD: An Intelligent LSM-Tree Based Key-Value SSD for Data Analytics. In Proceedings of the IEEE International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems (MASCOTS '19). 384--395.

[20]

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 Proceedings of the USENIX Conference on File and Storage Technologies (FAST '16). 133--148.

[21]

Chen Luo and Michael J Carey. 2020. LSM-based storage techniques: a survey. The VLDB Journal 29, 1 (2020), 393--418.

Digital Library

[22]

Donghyun Min and Youngjae Kim. 2021. Isolating namespace and performance in key-value SSDs for multi-tenant environments. In Proceedings of the 13th ACM Workshop on Hot Topics in Storage and File Systems (HotStorage '21). 8--13.

Digital Library

[23]

Inc NVM Express. 2021. NVM Express Key Value Command Set Specification. https://nvmexpress.org/developers/nvme-specification/

[24]

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

[25]

Manoj P. Saha, Adnan Maruf, Bryan S. Kim, and Janki Bhimani. 2021. KV-SSD: What Is It Good For?. In Proceedings of the 58th ACM/IEEE Design Automation Conference (DAC). 1105--1110.

Digital Library

[26]

SK hynix and Los Alamos National Laboratory. 2022. Los Alamos National Laboratory and SK hynix to demonstrate first-of-a-kind ordered Key-value Store Computational Storage Device. https://discover.lanl.gov/news/0728-storage-device.

[27]

SNIA. 2020. Key Value Storage API Specification. https://www.snia.org/keyvalue

[28]

Sung-Ming Wu, Kai-Hsiang Lin, and Li-Pin Chang. 2018. KVSSD: Close Integration of LSM Trees and Flash Translation Layer for Write-efficient KV Store. In Proceeding of the 2018 Design, Automation & Test in Europe Conference & Exhibition (DATE '18). IEEE, 563--568.

[29]

Wenshao Zhong, Chen Chen, Xingbo Wu, and Song Jiang. 2021. REMIX: Efficient Range Query for LSM-trees. In Proceedings of the 19th USENIX Conference on File and Storage Technologies (FAST '21). 51--64.

Cited By

Park YPark JPark JKhan AKim KPark SKim Y(2024)OctoFAS: A Two-Level Fair Scheduler That Increases Fairness in Network-Based Key-Value StorageElectronics10.3390/electronics1303061913:3(619)Online publication date: 1-Feb-2024
https://doi.org/10.3390/electronics13030619
Park JLee CHwang SYang SNoh JChung WLee JKim Y(2024)BandSlim: A Novel Bandwidth and Space-Efficient KV-SSD with an Escape-from-Block ApproachProceedings of the 53rd International Conference on Parallel Processing10.1145/3673038.3673064(1187-1196)Online publication date: 12-Aug-2024
https://dl.acm.org/doi/10.1145/3673038.3673064

Index Terms

Iterator Interface Extended LSM-tree-based KVSSD for Range Queries
1. Computer systems organization
  1. Embedded and cyber-physical systems
    1. Embedded systems
      1. Firmware
2. Information systems
  1. Information storage systems
    1. Storage management

Recommendations

Design of LSM-tree-based Key-value SSDs with Bounded Tails
Key-value store based on a log-structured merge-tree (LSM-tree) is preferable to hash-based key-value store, because an LSM-tree can support a wider variety of operations and show better performance, especially for writes. However, LSM-tree is difficult ...
RHIK: Re-configurable Hash-based Indexing for KVSSD
HPDC '23: Proceedings of the 32nd International Symposium on High-Performance Parallel and Distributed Computing

Key-Value Solid State Drive (KV-SSD), a key addressable SSD technology, promises to simplify storage management for unstructured data and improve system performance with minimal host-side intervention. However, we find that the current state-of-the-art ...
Scalability Analysis of Declustering Methods for Multidimensional Range Queries

Efficient storage and retrieval of multiattribute data sets has become one of the essential requirements for many data-intensive applications. The Cartesian product file has been known as an effective multiattribute file structure for partial-match and ...

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 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 the author(s) 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

SIGOPS: ACM Special Interest Group on Operating Systems

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 June 2023

Permissions

Request permissions for this article.

Request Permissions

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

2
Total Citations
View Citations
192
Total Downloads

Downloads (Last 12 months)105
Downloads (Last 6 weeks)11

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Park YPark JPark JKhan AKim KPark SKim Y(2024)OctoFAS: A Two-Level Fair Scheduler That Increases Fairness in Network-Based Key-Value StorageElectronics10.3390/electronics1303061913:3(619)Online publication date: 1-Feb-2024
https://doi.org/10.3390/electronics13030619
Park JLee CHwang SYang SNoh JChung WLee JKim Y(2024)BandSlim: A Novel Bandwidth and Space-Efficient KV-SSD with an Escape-from-Block ApproachProceedings of the 53rd International Conference on Parallel Processing10.1145/3673038.3673064(1187-1196)Online publication date: 12-Aug-2024
https://dl.acm.org/doi/10.1145/3673038.3673064

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