research-article

TONE: cutting tail-latency in learned indexes

Authors:

Oana BalmauAuthors Info & Claims

CHEOPS '22: Proceedings of the Workshop on Challenges and Opportunities of Efficient and Performant Storage Systems

Pages 16 - 23

https://doi.org/10.1145/3503646.3524295

Published: 05 April 2022 Publication History

Abstract

Low memory footprint and tail latency are important in indexing for data management systems. Learned indexes have been gaining popularity in recent years due to their low memory overhead, and adaptability to fluctuations in workloads. However, state-of-the-art learned indexes are optimized for read-heavy workloads where the key access distribution is relatively stable, and thus exhibit high tail latency for insertions.

Our main observation is that high insertion tail latency stems from structural modification operations in the index, such as node expansions and splits. Based on this insight, we propose a new tail-latency optimized learned index we call TONE. TONE has a novel node layout for leaves and adaptable policies for triggering structural modification operations. Moreover, TONE provides a shard-based mechanism to boost parallelism, while minimizing contention.

We evaluate the insertion tail-latency and overall throughput of TONE and provide a comprehensive comparison to state-of-the-art indexes such as skiplists (used in RocksDB) and existing learned indexes. We show that TONE reduces the 99p write tail-latency up to one order of magnitude and has a low memory use.

References

[1]

Facebook. [n.d.]. RocksDB: A Persistent Key-value Store for Fast Storage Environments, 2019. https://rocksdb.org/.

[2]

Xindex repository. https://ipads.se.sjtu.edu.cn:1312/opensource/xindex, 2021.

[3]

Oana Balmau, Florin Dinu, Willy Zwaenepoel, Karan Gupta, Ravishankar Chandhiramoorthi, and Diego Didona. Silk: Preventing latency spikes in log-structured merge key-value stores. In 2019 USENIX Annual Technical Conference (USENIX ATC 19), 2019.

[4]

Zhichao Cao, Siying Dong, Sagar Vemuri, and David HC Du. Characterizing, modeling, and benchmarking rocksdb key-value workloads at facebook. In 18th USENIX Conference on File and Storage Technologies (FAST 20), 2020.

Digital Library

[5]

Youmin Chen, Youyou Lu, Kedong Fang, Qing Wang, and Jiwu Shu. utree: a persistent b+-tree with low tail latency. VLDB Endowment, 13 (12), 2020.

Digital Library

[6]

Douglas Comer. Ubiquitous b-tree. ACM Computing Surveys (CSUR), 11(2), 1979.

[7]

Brian F Cooper, Adam Silberstein, Erwin Tam, Raghu Ramakrishnan, and Russell Sears. Benchmarking cloud serving systems with ycsb. In Proceedings of the 1st ACM symposium on Cloud computing, 2010.

Digital Library

[8]

Jialin Ding, Umar Farooq Minhas, Jia Yu, Chi Wang, Jaeyoung Do, Yinan Li, Hantian Zhang, Badrish Chandramouli, Johannes Gehrke, Donald Kossmann, et al. Alex: an updatable adaptive learned index. In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data, 2020.

Digital Library

[9]

Paolo Ferragina and Giorgio Vinciguerra. The pgm-index: a fully-dynamic compressed learned index with provable worst-case bounds. VLDB, 13(8), 2020.

Digital Library

[10]

Fedor V Fomin and Petteri Kaski. Exact exponential algorithms. Communications of the ACM, 56(3), 2013.

[11]

Alex Galakatos, Michael Markovitch, Carsten Binnig, Rodrigo Fonseca, and Tim Kraska. Fiting-tree: A data-aware index structure. In Proceedings of the 2019 International Conference on Management of Data, 2019.

Digital Library

[12]

Tim Kraska, Alex Beutel, Ed H Chi, Jeffrey Dean, and Neoklis Polyzotis. The case for learned index structures. In Proceedings of the 2018 International Conference on Management of Data, 2018.

Digital Library

[13]

Baotong Lu, Jialin Ding, Eric Lo, Umar Farooq Minhas, and Tianzheng Wang. Apex: A high-performance learned index on persistent memory. arXivpreprint arXiv:2105.00683, 2021.

[14]

Sara McAllister, Benjamin Berg, Julian Tutuncu-Macias, Juncheng Yang, Sathya Gunasekar, Jimmy Lu, Daniel S Berger, Nathan Beckmann, and Gregory R Ganger. Kangaroo: Caching billions of tiny objects on flash. In Proceedings of the ACM SIGOPS 28th Symposium on Operating Systems Principles, 2021.

Digital Library

[15]

Vikram Nathan, Jialin Ding, Mohammad Alizadeh, and Tim Kraska. Learning multi-dimensional indexes. In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data, 2020.

Digital Library

[16]

Chuzhe Tang, Youyun Wang, Zhiyuan Dong, Gansen Hu, Zhaoguo Wang, Minjie Wang, and Haibo Chen. Xindex: a scalable learned index for multicore data storage. In Proceedings of the 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, 2020.

Digital Library

[17]

Zhaoguo Wang, Haibo Chen, Youyun Wang, Chuzhe Tang, and Huan Wang. The concurrent learned indexes for multicore data storage. ACM Transactions on Storage (TOS), 18(1), 2022.

[18]

Jiacheng Wu, Yong Zhang, Shimin Chen, Jin Wang, Yu Chen, and Chunxiao Xing. Updatable learned index with precise positions. arXiv preprint arXiv:2104.05520, 2021.

[19]

Yuehai Xu, Eitan Frachtenberg, Song Jiang, and Mike Paleczny. Characterizing facebook's memcached workload. IEEE Internet Computing, 18(2), 2013.

Cited By

Ge JZhang HShi BLuo YGuo YChai YChen YPan A(2023)SALI: A Scalable Adaptive Learned Index Framework based on Probability ModelsProceedings of the ACM on Management of Data10.1145/36267521:4(1-25)Online publication date: 12-Dec-2023
https://dl.acm.org/doi/10.1145/3626752
Maharjan SZhao SZhong CJiang S(2023)From LeanStore to LearnedStore: Using a Learned Index to Improve Database Index Search2023 International Conference on High Performance Big Data and Intelligent Systems (HDIS)10.1109/HDIS60872.2023.10499467(162-169)Online publication date: 6-Dec-2023
https://doi.org/10.1109/HDIS60872.2023.10499467

Index Terms

TONE: cutting tail-latency in learned indexes
1. Information systems
  1. Information storage systems
    1. Storage management

Recommendations

X-FIST: Extended flood index for efficient similarity search in massive trajectory dataset
Abstract
Similarity search tasks in big trajectory datasets often require tree-based indices to shorten the query time through early pruning of dissimilar trajectories early. However, tree-based indices have been outperformed by the learned ...
LIVAK: A High-Performance In-Memory Learned Index for Variable-Length Keys
DAC '24: Proceedings of the 61st ACM/IEEE Design Automation Conference

In-memory learned index has been an efficient approach supporting in-memory fast data access. However, existing learned indexes are inefficient in supporting variable-length keys. To address this issue, we propose a new in-memory learned index called ...
DiffLex: A High-Performance, Memory-Efficient and NUMA-Aware Learned Index using Differentiated Management
ICPP '23: Proceedings of the 52nd International Conference on Parallel Processing

Learned indexes that utilize machine learning models can offer significant performance advantages over traditional indexes. However, existing learned indexes suffer from space-performance tradeoffs and they cannot scale well in multiple NUMA-nodes ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

CHEOPS '22: Proceedings of the Workshop on Challenges and Opportunities of Efficient and Performant Storage Systems

April 2022

44 pages

ISBN:9781450392099

DOI:10.1145/3503646

Conference Chairs:
Michael Kuhn
Otto von Guericke University Magdeburg (OVGU), Germany
,
Kira Duwe
Otto von Guericke University Magdeburg (OVGU), Germany
,
Jean-Thomas Acquaviva
DataDirect Networks (DDN) Storage, France
,
Konstantinos Chasapis
DataDirect Networks (DDN) Storage, France
,
Jalil Boukhobza
National Institute of Advanced Technologies of Brittany (ENSTA Bretagne), France

Copyright © 2022 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

SIGOPS: ACM Special Interest Group on Operating Systems

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 April 2022

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

EuroSys '22

Sponsor:

SIGOPS

EuroSys '22: Seventeenth European Conference on Computer Systems

April 5, 2022

Rennes, France

Acceptance Rates

Overall Acceptance Rate 6 of 8 submissions, 75%

Upcoming Conference

EuroSys '25

Sponsor:
sigops

Twentieth European Conference on Computer Systems

March 30 - April 3, 2025

Rotterdam , Netherlands

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
275
Total Downloads

Downloads (Last 12 months)33
Downloads (Last 6 weeks)1

Reflects downloads up to 28 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ge JZhang HShi BLuo YGuo YChai YChen YPan A(2023)SALI: A Scalable Adaptive Learned Index Framework based on Probability ModelsProceedings of the ACM on Management of Data10.1145/36267521:4(1-25)Online publication date: 12-Dec-2023
https://dl.acm.org/doi/10.1145/3626752
Maharjan SZhao SZhong CJiang S(2023)From LeanStore to LearnedStore: Using a Learned Index to Improve Database Index Search2023 International Conference on High Performance Big Data and Intelligent Systems (HDIS)10.1109/HDIS60872.2023.10499467(162-169)Online publication date: 6-Dec-2023
https://doi.org/10.1109/HDIS60872.2023.10499467

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