Kanva: A Lock-free Learned Search Data Structure
Authors: 
Gaurav Bhardwaj, Bapi Chatterjee, Abhinav Sharma, Sathya Peri, Siddharth NayakAuthors Info & Claims
Pages 252 - 261
Abstract
Lock-free concurrent data structures offer throughput with scalability and guarantees for the completion of operations on multicore computers. Recently, queries using machine learning models trained to predict the data distribution have gained remarkable attention. Yet, to our knowledge, no existing lock-free data structure employs them. This paper introduces a lock-free search structure that supports concurrent updates, membership, and range queries accelerated by a shallow hierarchy of lightweight machine learning models. The proposed approach significantly outperforms the current state-of-the-art lock-free data structures in many workload and data distribution settings. Ours is the first provably linearizable learned lock-free concurrent range search index.
References
[1]
18th August, 2022. Amazon sales rank data for print and kindle books.https://www.kaggle.com/datasets/ucffool/amazon-sales-rank-data-for-print-and-kindle-books/.
[2]
18th August, 2022. Wikimedia. https://dumps.wikimedia.org/.
[3]
M. Arbel-Raviv and T. Brown. 2018. Harnessing epoch-based reclamation for efficient range queries. ACM SIGPLAN Notices 53, 1 (2018), 14–27.
[4]
M. Arbel-Raviv, T. Brown, and A. Morrison. 2018. Getting to the root of concurrent binary search tree performance. In USENIX. 295–306.
[5]
Anastasia Braginsky and Erez Petrank. 2012. A lock-free B+ tree. In 24th annual ACM SPAA. 58–67.
[6]
Trevor Brown. 2017. Techniques for Constructing Efficient Lock-free Data Structures. CoRR abs/1712.05406 (2017). arXiv:1712.05406http://arxiv.org/abs/1712.05406
[7]
Trevor Brown, Faith Ellen, and Eric Ruppert. 2014. A general technique for non-blocking trees. In 19th ACM SIGPLAN PPOPP. 329–342.
[8]
Trevor Brown and Joanna Helga. 2011. Non-blocking k-ary search trees. In OPODIS. Springer, 207–221.
[9]
Trevor Brown, Aleksandar Prokopec, and Dan Alistarh. 2020. Non-blocking interpolation search trees with doubly-logarithmic running time. In 25th ACM PPOPP. 276–291.
[10]
Trevor Brown, William Sigouin, and Dan Alistarh. 2022. PathCAS: an efficient middle ground for concurrent search data structures. In 27th ACM SIGPLAN PPOPP. 385–399.
[11]
Trevor Alexander Brown. 2015. Reclaiming memory for lock-free data structures: There has to be a better way. In PODC. 261–270.
[12]
Bapi Chatterjee. 2017. Lock-free linearizable 1-dimensional range queries. In Proceedings of the 18th ICDCN. 1–10.
[13]
Bapi Chatterjee, Nhan Nguyen, and Philippas Tsigas. 2014. Efficient lock-free binary search trees. In 2014 ACM PODC. 322–331.
[14]
Brian F Cooper, Adam Silberstein, Erwin Tam, Raghu Ramakrishnan, and Russell Sears. 2010. Benchmarking cloud serving systems with YCSB. In 1st ACM SOCC. 143–154.
[15]
Andrew Crotty. 2021. Hist-Tree: Those Who Ignore It Are Doomed to Learn. In CIDR.
[16]
Jialin Ding, Umar Farooq Minhas, Jia Yu, Chi Wang, Jaeyoung Do, Yinan Li, Hantian Zhang, Badrish Chandramouli, Johannes Gehrke, Donald Kossmann, 2020. ALEX: an updatable adaptive learned index. In 2020 ACM SIGMOD. 969–984.
[17]
F. Ellen, P. Fatourou, E. Ruppert, and F. van Breugel. 2010. Non-blocking binary search trees. In 29th ACM SIGACT-SIGOPS. 131–140.
[18]
Paolo Ferragina and Giorgio Vinciguerra. 2020. The PGM-index: a fully-dynamic compressed learned index with provable worst-case bounds. Proceedings of the VLDB Endowment 13, 8 (2020), 1162–1175.
[19]
Alex Galakatos, Michael Markovitch, Carsten Binnig, Rodrigo Fonseca, and Tim Kraska. 2019. Fiting-tree: A data-aware index structure. In 2019 ACM SIGMOD. 1189–1206.
[20]
Timothy L. Harris. 2001. A Pragmatic Implementation of Non-blocking Linked-Lists. In DISC 2021, Lisbon, Portugal, October 3-5, 2001, Proceedings. 300–314.
[21]
M. Herlihy, Y. Lev, V. Luchangco, and N. Shavit. 2006. A provably correct scalable concurrent skip list. In OPODIS. 103.
[22]
M. P. Herlihy and J. M. Wing. 1990. Linearizability: A correctness condition for concurrent objects. ACM TOPLAS 12, 3 (1990), 463–492.
[23]
S. V. Howley and J. Jones. 2012. A non-blocking internal binary search tree. In 24th annual ACM SPAA. 161–171.
[24]
A. Kipf, R. Marcus, A. van Renen, M. Stoian, A. Kemper, T. Kraska, and T. Neumann. 2019. SOSD: A benchmark for learned indexes. arXiv preprint arXiv:1911.13014 (2019).
[25]
A. Kipf, R. Marcus, A. van Renen, M. Stoian, A. Kemper, T. Kraska, and T. Neumann. 2020. RadixSpline: a single-pass learned index. In In 3rd aiDM. 1–5.
[26]
Tadeusz Kobus, Maciej Kokociński, and Paweł T Wojciechowski. 2022. Jiffy: a lock-free skip list with batch updates and snapshots. In 27th ACM PPOPP. 400–415.
[27]
Tim Kraska, Alex Beutel, Ed H Chi, Jeffrey Dean, and Neoklis Polyzotis. 2018. The case for learned index structures. In ACM SIGMOD. 489–504.
[28]
Pengfei Li, Yu Hua, Jingnan Jia, and Pengfei Zuo. 2021. FINEdex: a fine-grained learned index scheme for scalable and concurrent memory systems. Proceedings of the VLDB Endowment 15, 2 (2021), 321–334.
[29]
Aravind Natarajan and Neeraj Mittal. 2014. Fast concurrent lock-free binary search trees. In 19th ACM SIGPLAN PPOPP. 317–328.
[30]
Aravind Natarajan, Arunmoezhi Ramachandran, and Neeraj Mittal. 2020. FEAST: a lightweight lock-free concurrent binary search tree. ACM TOPC 7, 2 (2020), 1–64.
[31]
Jacob Nelson, Ahmed Hassan, and Roberto Palmieri. 2021. Bundled references: an abstraction for highly-concurrent linearizable range queries. In Proceedings of the 26th SPAA. 448–450.
[32]
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.
[33]
Varun Pandey, Andreas Kipf, Thomas Neumann, and Alfons Kemper. 2018. How good are modern spatial analytics systems?Proceedings of the VLDB Endowment 11, 11 (2018), 1661–1673.
[34]
Benjamin Recht, Christopher Re, Stephen Wright, and Feng Niu. 2011. Hogwild!: A lock-free approach to parallelizing stochastic gradient descent. NIPS 24 (2011).
[35]
Gali Sheffi, Pedro Ramalhete, and Erez Petrank. 2023. EEMARQ: Efficient Lock-Free Range Queries with Memory Reclamation. In 26th OPODIS.
[36]
Anubhav Srivastava and Trevor Brown. 2022. Elimination (a, b)-trees with fast, durable updates. In 27th ACM PPOPP. 416–430.
[37]
Mihail Stoian, Andreas Kipf, Ryan Marcus, and Tim Kraska. 2021. PLEX: Towards Practical Learned Indexing. arXiv preprint arXiv:2108.05117 (2021).
[38]
Chuzhe Tang, Youyun Wang, Zhiyuan Dong, Gansen Hu, Zhaoguo Wang, Minjie Wang, and Haibo Chen. 2020. XIndex: a scalable learned index for multicore data storage. In 25th PPOPP. 308–320.
[39]
Peter Van Sandt, Yannis Chronis, and Jignesh M Patel. 2019. Efficiently Searching In-Memory Sorted Arrays: Revenge of the Interpolation Search?. In 2019 SIGMOD. 36–53.
[40]
Z. Wang, A. Pavlo, H. Lim, V. Leis, H. Zhang, M. Kaminsky, and D. G. Andersen. 2018. Building a bw-tree takes more than just buzz words. In ACM SIGMOD. 473–488.
[41]
Yuanhao Wei, Naama Ben-David, Guy E Blelloch, Panagiota Fatourou, Eric Ruppert, and Yihan Sun. 2021. Constant-time snapshots with applications to concurrent data structures. In PPoPP. 31–46.
[42]
Jiacheng Wu, Yong Zhang, Shimin Chen, Jin Wang, Yu Chen, and Chunxiao Xing. 2021. Updatable learned index with precise positions. Proceedings of the VLDB Endowment 14, 8 (2021), 1276–1288.
[43]
Q. Xie, C. Pang, X. Zhou, X. Zhang, and K. Deng. 2014. Maximum error-bounded piecewise linear representation for online stream approximation. The VLDB journal 23, 6 (2014), 915–937.
Index Terms
- Kanva: A Lock-free Learned Search Data Structure
Index terms have been assigned to the content through auto-classification.
Recommendations
Brief Announcement: Lock-free Learned Search Data Structure
SPAA '24: Proceedings of the 36th ACM Symposium on Parallelism in Algorithms and ArchitecturesThis paper introduces a lock-free linearizable search structure that supports concurrent updates, membership, and range queries accelerated by a shallow hierarchy of lightweight machine learning (ML) models. The proposed approach significantly ...
Lock-Free Data-Structure Iterators
DISC 2013: Proceedings of the 27th International Symposium on Distributed Computing - Volume 8205Concurrent data structures are often used with large concurrent software. An iterator that traverses the data structure items is a highly desirable interface that often exists for sequential data structures but is missing from almost all concurrent data-...
Lock-Free Transactional Transformation for Linked Data Structures
Special Issue on SPAA 2016Nonblocking data structures allow scalable and thread-safe access to shared data. They provide individual operations that appear to execute atomically. However, it is often desirable to execute multiple operations atomically in a transactional manner. ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
August 2024
1279 pages
ISBN:9798400717932
DOI:10.1145/3673038
Copyright © 2024 Owner/Author.
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives International 4.0 License.
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 12 August 2024
Check for updates
Author Tags
Qualifiers
- Research-article
- Research
- Refereed limited
Conference
ICPP '24
ICPP '24: the 53rd International Conference on Parallel Processing
August 12 - 15, 2024
Gotland, Sweden
Acceptance Rates
Overall Acceptance Rate 91 of 313 submissions, 29%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 190Total Downloads
- Downloads (Last 12 months)190
- Downloads (Last 6 weeks)53
Reflects downloads up to 25 Dec 2024
Other Metrics
Citations
View Options
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderHTML Format
View this article in HTML Format.
HTML FormatLogin options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in