More Web Proxy on the site http://driver.im/

research-article

Open access

Bundling linked data structures for linearizable range queries

Authors:

Jacob Nelson-Slivon,

Roberto PalmieriAuthors Info & Claims

PPoPP '22: Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming

Pages 368 - 384

https://doi.org/10.1145/3503221.3508412

Published: 28 March 2022 Publication History

Abstract

We present bundled references, a new building block to provide linearizable range query operations for highly concurrent lock-based linked data structures. Bundled references allow range queries to traverse a path through the data structure that is consistent with the target atomic snapshot. We demonstrate our technique with three data structures: a linked list, skip list, and a binary search tree. Our evaluation reveals that in mixed workloads, our design can improve upon the state-of-the-art techniques by 1.2x-1.8x for a skip list and 1.3x-3.7x for a binary search tree. We also integrate our bundled data structure into the DBx1000 in-memory database, yielding up to 40% gain over the same competitors.

References

[1]

Atul Adya. 1999. Weak Consistency: A Generalized Theory and Optimistic Implementations for Distributed Transactions. Ph.D. Dissertation. Massachusetts Institute of Technology.

[2]

Yehuda Afek, Hillel Avni, and Nir Shavit. 2011. Towards consistency oblivious programming. In International Conference On Principles Of Distributed Systems. Springer, 65--79.

Digital Library

[3]

Maya Arbel and Hagit Attiya. 2014. Concurrent updates with RCU: search tree as an example. In ACM Symposium on Principles of Distributed Computing, PODC '14, Paris, France, July 15--18, 2014. ACM, 196--205.

Digital Library

[4]

Maya Arbel-Raviv and Trevor Brown. 2018. Harnessing epoch-based reclamation for efficient range queries. In Proceedings of the 23rd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2018, Vienna, Austria, February 24--28, 2018. 14--27.

Digital Library

[5]

Hillel Avni, Nir Shavit, and Adi Suissa. 2013. Leaplist: lessons learned in designing tm-supported range queries. In ACM Symposium on Principles of Distributed Computing, PODC '13, Montreal, QC, Canada, July 22--24, 2013. ACM, 299--308.

Digital Library

[6]

Dmitry Basin, Edward Bortnikov, Anastasia Braginsky, Guy Golan-Gueta, Eshcar Hillel, Idit Keidar, and Moshe Sulamy. 2017. KiWi: A Key-Value Map for Scalable Real-Time Analytics. In Proceedings of the 22nd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, Austin, TX, USA, February 4--8, 2017. ACM, 357--369. http://dl.acm.org/citation.cfm?id=3018761

Digital Library

[7]

Naama Ben-David, Guy E Blelloch, Yihan Sun, and Yuanhao Wei. 2019. Multiversion concurrency with bounded delay and precise garbage collection. In The 31st ACM Symposium on Parallelism in Algorithms and Architectures. 241--252.

Digital Library

[8]

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

[9]

Nathan Grasso Bronson, Jared Casper, Hassan Chafi, and Kunle Olukotun. 2010. A practical concurrent binary search tree. In Proceedings of the 15th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP 2010, Bangalore, India, January 9--14, 2010. ACM, 257--268.

Digital Library

[10]

Trevor Brown and Hillel Avni. 2012. Range Queries in Non-blocking k-ary Search Trees. In Principles of Distributed Systems, 16th International Conference, OPODIS 2012, Rome, Italy, December 18--20, 2012. Proceedings (Lecture Notes in Computer Science, Vol. 7702). Springer, 31--45.

[11]

Trevor Alexander Brown. 2015. Reclaiming Memory for Lock-Free Data Structures: There has to be a Better Way. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC 2015, Donostia-San Sebastián, Spain, July 21 - 23, 2015. 261--270.

Digital Library

[12]

Bapi Chatterjee. 2017. Lock-free linearizable 1-dimensional range queries. In Proceedings of the 18th International Conference on Distributed Computing and Networking. 1--10.

Digital Library

[13]

Shu-Yao Chien, Vassilis J Tsotras, and Carlo Zaniolo. 2001. Efficient management of multiversion documents by object referencing. In VLDB, Vol. 1. 291--300.

[14]

Tyler Crain, Vincent Gramoli, and Michel Raynal. 2013. A contention-friendly binary search tree. In European Conference on Parallel Processing. Springer, 229--240.

Digital Library

[15]

Tudor David, Rachid Guerraoui, and Vasileios Trigonakis. 2015. Asynchronized concurrency: The secret to scaling concurrent search data structures. ACM SIGARCH Computer Architecture News 43, 1 (2015), 631--644.

Digital Library

[16]

James R Driscoll, Neil Sarnak, Daniel Dominic Sleator, and Robert Endre Tarjan. 1986. Making data structures persistent. In Proceedings of the eighteenth annual ACM symposium on Theory of computing. 109--121.

Digital Library

[17]

Robert Escriva, Bernard Wong, and Emin Gün Sirer. 2012. HyperDex: a distributed, searchable key-value store. In ACM SIGCOMM 2012 Conference, SIGCOMM '12, Helsinki, Finland - August 13 - 17, 2012, Lars Eggert, Jörg Ott, Venkata N. Padmanabhan, and George Varghese (Eds.). ACM, 25--36.

Digital Library

[18]

Facebook. 2020. RocksDB: a persistent key-value store for fast storage environments. https://rocksdb.org/.

[19]

Yotam M. Y. Feldman, Artem Khyzha, Constantin Enea, Adam Morrison, Aleksandar Nanevski, Noam Rinetzky, and Sharon Shoham. 2020. Proving Highly-Concurrent Traversals Correct. Proc. ACM Program. Lang. 4, OOPSLA, Article 128 (nov 2020), 29 pages.

Digital Library

[20]

Sergio Miguel Fernandes and João P. Cachopo. 2011. Lock-free and scalable multi-version software transactional memory. In Proceedings of the 16th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP 2011, San Antonio, TX, USA, February 12--16, 2011, Calin Cascaval and Pen-Chung Yew (Eds.). ACM, 179--188.

[21]

Keir Fraser. 2004. Practical lock-freedom. Ph.D. Dissertation. University of Cambridge, UK.

[22]

Michal Friedman, Naama Ben-David, Yuanhao Wei, Guy E. Blelloch, and Erez Petrank. 2020. NVTraverse: In NVRAM Data Structures, the Destination is More Important than the Journey. In Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation (London, UK) (PLDI 2020). Association for Computing Machinery, New York, NY, USA, 377--392.

Digital Library

[23]

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

[24]

Ahmed Hassan, Roberto Palmieri, and Binoy Ravindran. 2014. On Developing Optimistic Transactional Lazy Set. In Principles of Distributed Systems - 18th International Conference, OPODIS 2014, Cortina d'Ampezzo, Italy, December 16--19, 2014. Proceedings (Lecture Notes in Computer Science, Vol. 8878). Springer, 437--452.

[25]

Steve Heller, Maurice Herlihy, Victor Luchangco, Mark Moir, William N. Scherer III, and Nir Shavit. 2005. A Lazy Concurrent List-Based Set Algorithm. In Principles of Distributed Systems, 9th International Conference, OPODIS 2005, Pisa, Italy, December 12--14, 2005, Revised Selected Papers (Lecture Notes in Computer Science, Vol. 3974). Springer, 3--16.

Digital Library

[26]

Maurice Herlihy, Yossi Lev, Victor Luchangco, and Nir Shavit. 2007. A Simple Optimistic Skiplist Algorithm. In Structural Information and Communication Complexity, 14th International Colloquium, SIROCCO 2007, Castiglioncello, Italy, June 5--8, 2007, Proceedings (Lecture Notes in Computer Science, Vol. 4474). Springer, 124--138.

[27]

Maurice Herlihy and Jeannette M. Wing. 1990. Linearizability: A Correctness Condition for Concurrent Objects. ACM Trans. Program. Lang. Syst. 12, 3 (1990), 463--492.

Digital Library

[28]

Rich Hickey. 2008. The Clojure programming language. In Proceedings of the 2008 symposium on Dynamic languages. 1--1.

Digital Library

[29]

Gui Huang, Xuntao Cheng, Jianying Wang, Yujie Wang, Dengcheng He, Tieying Zhang, Feifei Li, Sheng Wang, Wei Cao, and Qiang Li. 2019. X-Engine: An optimized storage engine for large-scale E-commerce transaction processing. In Proceedings of the 2019 International Conference on Management of Data. 651--665.

Digital Library

[30]

Ankita Kejriwal, Arjun Gopalan, Ashish Gupta, Zhihao Jia, Stephen Yang, and John K. Ousterhout. 2016. SLIK: Scalable Low-Latency Indexes for a Key-Value Store. In USENIX Annual Technical Conference. USENIX Association, 57--70.

[31]

Masoomeh Javidi Kishi, Sebastiano Peluso, Henry F Korth, and Roberto Palmieri. 2019. SSS: Scalable Key-value Store with External Consistent and Abort-free Read-only Transactions. In 2019 IEEE 39th International Conference on Distributed Computing Systems (ICDCS). IEEE, 589--600.

[32]

Per-Åke Larson, Spyros Blanas, Cristian Diaconu, Craig Freedman, Jignesh M Patel, and Mike Zwilling. 2011. High-performance concurrency control mechanisms for main-memory databases. arXiv preprint arXiv:1201.0228 (2011).

[33]

Doug Lea. 2005. The java.util.concurrent synchronizer framework. Sci. Comput. Program. 58, 3 (2005), 293--309.

Digital Library

[34]

Hyeontaek Lim, Michael Kaminsky, and David G Andersen. 2017. Cicada: Dependably fast multi-core in-memory transactions. In Proceedings of the 2017 ACM International Conference on Management of Data. 21--35.

Digital Library

[35]

Yandong Mao, Eddie Kohler, and Robert Tappan Morris. 2012. Cache craftiness for fast multicore key-value storage. In European Conference on Computer Systems, Proceedings of the Seventh EuroSys Conference 2012, EuroSys '12, Bern, Switzerland, April 10--13, 2012, Pascal Felber, Frank Bellosa, and Herbert Bos (Eds.). ACM, 183--196.

Digital Library

[36]

Alexander Matveev, Nir Shavit, Pascal Felber, and Patrick Marlier. 2015. Read-log-update: a lightweight synchronization mechanism for concurrent programming. In Proceedings of the 25th Symposium on Operating Systems Principles, SOSP 2015, Monterey, CA, USA, October 4--7, 2015. 168--183.

Digital Library

[37]

Paul E McKenney and John D Slingwine. 1998. Read-copy update: Using execution history to solve concurrency problems. In Parallel and Distributed Computing and Systems. 509--518.

[38]

Jacob Nelson, Ahmed Hassan, and Roberto Palmieri. 2021. POSTER: Bundled references: an abstraction for highly-concurrent linearizable range queries. In PPoPP '21: 26th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, Virtual Event, Republic of Korea, February 27- March 3, 2021, Jaejin Lee and Erez Petrank (Eds.). ACM, 448--450.

Digital Library

[39]

Jacob Nelson, Ahmed Hassan, and Roberto Palmieri. 2022. Technical Report: Bundling Linked Data Structures for Linearizable Range Queries. Technical Report. https://arxiv.org/abs/2201.00874

[40]

Thomas Neumann, Tobias Mühlbauer, and Alfons Kemper. 2015. Fast serializable multi-version concurrency control for main-memory database systems. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data. 677--689.

Digital Library

[41]

Chris Okasaki. 1999. Purely functional data structures. Cambridge University Press.

Digital Library

[42]

Sebastiano Peluso, Pedro Ruivo, Paolo Romano, Francesco Quaglia, and Luis Rodrigues. 2015. GMU: Genuine Multiversion Update-serializable Partial Data Replication. IEEE Transactions on Parallel and Distributed Systems 27, 10 (2015), 2911--2925.

Digital Library

[43]

Erez Petrank and Shahar Timnat. 2013. Lock-Free Data-Structure Iterators. In Distributed Computing - 27th International Symposium, DISC 2013, Jerusalem, Israel, October 14--18, 2013. Proceedings (Lecture Notes in Computer Science, Vol. 8205). Springer, 224--238.

Digital Library

[44]

Aleksandar Prokopec, Nathan Grasso Bronson, Phil Bagwell, and Martin Odersky. 2012. Concurrent tries with efficient non-blocking snapshots. In Proceedings of the 17th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP 2012, New Orleans, LA, USA, February 25--29, 2012. ACM, 151--160.

Digital Library

[45]

Pandian Raju, Rohan Kadekodi, Vijay Chidambaram, and Ittai Abraham. 2017. PebblesDB: Building Key-Value Stores using Fragmented Log-Structured Merge Trees. In SOSP. ACM, 497--514.

[46]

Matthew Rodriguez and Michael Spear. 2020. Optimizing Linearizable Bulk Operations on Data Structures. In ICPP 2020:49th International Conference on Parallel Processing, Edmonton, AB, Canada, August 17--20, 2020, José Nelson Amaral, Lizy Kurian John, and Xipeng Shen (Eds.). ACM, 24:1--24:10.

Digital Library

[47]

Konstantinos Sagonas and Kjell Winblad. 2015. Efficient Support for Range Queries and Range Updates Using Contention Adapting Search Trees. In Languages and Compilers for Parallel Computing - 28th International Workshop, LCPC 2015, Raleigh, NC, USA, September 9--11, 2015, Revised Selected Papers (Lecture Notes in Computer Science, Vol. 9519). Springer, 37--53.

Digital Library

[48]

Neil Sarnak and Robert E Tarjan. 1986. Planar point location using persistent search trees. Commun. ACM 29, 7 (1986), 669--679.

Digital Library

[49]

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 '21: 26th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, Virtual Event, Republic of a Korea, February 27- March 3, 2021, Jaejin Lee and Erez Petrank (Eds.). ACM, 31--46.

Digital Library

[50]

Yingjun Wu, Joy Arulraj, Jiexi Lin, Ran Xian, and Andrew Pavlo. 2017. An empirical evaluation of in-memory multi-version concurrency control. Proceedings of the VLDB Endowment 10, 7 (2017), 781--792.

Digital Library

[51]

Xiangyao Yu, George Bezerra, Andrew Pavlo, Srinivas Devadas, and Michael Stonebraker. 2014. Staring into the Abyss: An Evaluation of Concurrency Control with One Thousand Cores. PVLDB 8, 3 (2014), 209--220.

Digital Library

Cited By

Miller dHassan APalmieri RAgrawal KPetrank E(2024)Brief Announcement: LIT: Lookup Interlocked Table for Range QueriesProceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3626183.3660266(69-71)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3626183.3660266
Wei YBlelloch GFatourou PRuppert EDehnavi MKulkarni MKrishnamoorthy S(2023)Practically and Theoretically Efficient Garbage Collection for MultiversioningProceedings of the 28th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming10.1145/3572848.3577508(66-78)Online publication date: 25-Feb-2023
https://dl.acm.org/doi/10.1145/3572848.3577508
Assa GCorreia ARamalhete PSchiavoni VFelber PDehnavi MKulkarni MKrishnamoorthy S(2023)TL4xProceedings of the 28th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming10.1145/3572848.3577495(245-259)Online publication date: 25-Feb-2023
https://dl.acm.org/doi/10.1145/3572848.3577495
Show More Cited By

Index Terms

Bundling linked data structures for linearizable range queries
1. Computing methodologies
  1. Concurrent computing methodologies
    1. Concurrent algorithms
2. Information systems
  1. Data management systems
    1. Data structures

Recommendations

Lock-free Contention Adapting Search Trees
SPAA '18: Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures

Concurrent key-value stores with range query support are crucial for the scalability and performance of many applications. Existing lock-free data structures of this kind use a fixed synchronization granularity. Using a fixed synchronization granularity ...
Lock-free Linearizable 1-Dimensional Range Queries
ICDCN '17: Proceedings of the 18th International Conference on Distributed Computing and Networking

Efficient concurrent data structures that support range queries are highly sought-after in a number of application areas. For example, the contemporary big-data processing platforms employ them as in-memory index structures for fast and scalable real-...
Lock-Free Transactional Transformation for Linked Data Structures
Special Issue on SPAA 2016

Nonblocking 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

cover image ACM Conferences

PPoPP '22: Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming

April 2022

495 pages

ISBN:9781450392044

DOI:10.1145/3503221

General Chair:
Jaejin Lee
Seoul National University
,
Program Chairs:
Kunal Agrawal
Washington University
,
Michael Spear
Lehigh University

Copyright © 2022 Owner/Author.

This work is licensed under a Creative Commons Attribution International 4.0 License.

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 28 March 2022

Check for updates

Badges

Author Tags

Qualifiers

Research-article

Funding Sources

National Science Foundation

Conference

PPoPP '22

Sponsor:

PPoPP '22: 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming

April 2 - 6, 2022

Seoul, Republic of Korea

Acceptance Rates

Overall Acceptance Rate 230 of 1,014 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
565
Total Downloads

Downloads (Last 12 months)204
Downloads (Last 6 weeks)13

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Miller dHassan APalmieri RAgrawal KPetrank E(2024)Brief Announcement: LIT: Lookup Interlocked Table for Range QueriesProceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3626183.3660266(69-71)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3626183.3660266
Wei YBlelloch GFatourou PRuppert EDehnavi MKulkarni MKrishnamoorthy S(2023)Practically and Theoretically Efficient Garbage Collection for MultiversioningProceedings of the 28th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming10.1145/3572848.3577508(66-78)Online publication date: 25-Feb-2023
https://dl.acm.org/doi/10.1145/3572848.3577508
Assa GCorreia ARamalhete PSchiavoni VFelber PDehnavi MKulkarni MKrishnamoorthy S(2023)TL4xProceedings of the 28th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming10.1145/3572848.3577495(245-259)Online publication date: 25-Feb-2023
https://dl.acm.org/doi/10.1145/3572848.3577495
Grimes ONelson-Slivon JHassan APalmieri R(2023)Opportunities and Limitations of Hardware Timestamps in Concurrent Data Structures2023 IEEE International Parallel and Distributed Processing Symposium (IPDPS)10.1109/IPDPS54959.2023.00068(624-634)Online publication date: May-2023
https://doi.org/10.1109/IPDPS54959.2023.00068
Sela GPetrank E(2022)Concurrent sizeProceedings of the ACM on Programming Languages10.1145/35633006:OOPSLA2(345-372)Online publication date: 31-Oct-2022
https://dl.acm.org/doi/10.1145/3563300

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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

Media

Figures

Other

Tables

View Table of Contents