research-article

Harnessing epoch-based reclamation for efficient range queries

Authors:

Maya Arbel-Raviv,

Trevor BrownAuthors Info & Claims

ACM SIGPLAN Notices, Volume 53, Issue 1

Pages 14 - 27

https://doi.org/10.1145/3200691.3178489

Published: 10 February 2018 Publication History

Abstract

Concurrent sets with range query operations are highly desirable in applications such as in-memory databases. However, few set implementations offer range queries. Known techniques for augmenting data structures with range queries (or operations that can be used to build range queries) have numerous problems that limit their usefulness. For example, they impose high overhead or rely heavily on garbage collection. In this work, we show how to augment data structures with highly efficient range queries, without relying on garbage collection. We identify a property of epoch-based memory reclamation algorithms that makes them ideal for implementing range queries, and produce three algorithms, which use locks, transactional memory and lock-free techniques, respectively. Our algorithms are applicable to more data structures than previous work, and are shown to be highly efficient on a large scale Intel system.

Supplementary Material

Artifacts Available (range_queries.zip)

Software

Download
3.14 MB

References

[1]

Y. Afek, H. Attiya D. Dolev, E. Gafni, M. Merritt, and N. Shavit. Atomic snapshots of shared memory. J. ACM, 40(4):873--890, Sept. 1993. ISSN 0004--5411.

Digital Library

[2]

A. Agarwal, Z. Liu, E. Rosenthal, and V. Saraph. Linearizable iterators for concurrent data structures. CoRR, abs/1705.08885, 2017. URL http://arxiv.org/abs/1705.08885.

[3]

M. Arbel and H. Attiya. Concurrent updates with RCU: Search tree as an example. In Proceedings of the 2014 ACM Symposium on Principles of Distributed Computing, PODC '14, pages 196--205, New York, NY, USA, 2014. ACM. ISBN 978-1-4503-2944-6.

Digital Library

[4]

M. Arbel-Raviv and T. Brown. Reuse, don't recycle: Transforming lock-free algorithms that throw away descriptors. In Proceedings of the 31st International Symposium on Distributed Computing, DISC 2017, 2017.

[5]

H. Attiya, R. Guerraoui, and E. Ruppert. Partial snapshot objects. In Proceedings of the Twentieth Annual Symposium on Parallelism in Algorithms and Architectures, SPAA '08, pages 336--343, New York, NY, USA, 2008. ACM. ISBN 978-1-59593-973-9.

Digital Library

[6]

H. Avni, N. Shavit, and A. Suissa. Leaplist: Lessons learned in designing tm-supported range queries. In Proceedings of the 2013 ACM Symposium on Principles of Distributed Computing, PODC '13, pages 299--308, New York, NY, USA, 2013. ACM. ISBN 978-1-4503-2065-8.

Digital Library

[7]

D. Basin, E. Bortnikov, A. Braginsky, G. Golan-Gueta, E. Hillel, I. Keidar, and M. Sulamy. 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, PPoPP '17, pages 357--369, New York, NY, USA, 2017. ACM. ISBN 978-1-4503-4493-7.

Digital Library

[8]

N. G. Bronson, J. Casper, H. Chafi, and K. Olukotun. A practical concurrent binary search tree. In Proceedings of the 15th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP '10, pages 257--268, New York, NY, USA, 2010. ACM. ISBN 978-1-60558877-3.

Digital Library

[9]

T. Brown. 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 '15, pages 261--270, 2015.

Digital Library

[10]

T. Brown. Techniques for Constructing Efficient Data Structures. PhD thesis, University of Toronto, 2017.

[11]

T. Brown, F. Ellen, and E. Ruppert. A general technique for non-blocking trees. In Proceedings of the 19th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP '14, pages 329--342, New York, NY, USA, 2014. ACM. ISBN 978-1-4503-26568.

Digital Library

[12]

I. Calciu, D. Dice, Y. Lev, V. Luchangco, V. J. Marathe, and N. Shavit. Numa-aware reader-writer locks. In Proceedings of the 18th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP '13, pages 157--166, New York, NY, USA, 2013. ACM. ISBN 978-1-4503-1922-5.

Digital Library

[13]

B. Chatterjee. Lock-free linearizable 1-dimensional range queries. In Proceedings of the 18th International Conference on Distributed Computing and Networking, ICDCN '17, pages 9:1--9:10, New York, NY, USA, 2017. ACM. ISBN 978-1-4503-4839-3.

Digital Library

[14]

L. Dalessandro, M. F. Spear, and M. L. Scott. Norec: Streamlining stm by abolishing ownership records. In Proceedings of the 15th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP '10, pages 67--78, New York, NY, USA, 2010. ACM. ISBN 978-1-60558877-3.

Digital Library

[15]

T. David, R. Guerraoui, and V. Trigonakis. Asynchronized concurrency: The secret to scaling concurrent search data structures. In Proceedings of the Twentieth International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS '15, pages 631--644, New York, NY, USA, 2015. ACM. ISBN 978-1-4503-28357.

Digital Library

[16]

D. Dice, O. Shalev, and N. Shavit. Transactional locking ii. In Proceedings of the 20th International Conference on Distributed Computing, DISC'06, pages 194--208, Berlin, Heidelberg, 2006. Springer-Verlag. ISBN 3-540-44624-9, 978-3-540-44624-8.

Digital Library

[17]

F. Ellen, P. Fatourou, E. Ruppert, and F. van Breugel. Non-blocking binary search trees. In Proceedings of the 29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC '10, pages 131--140, New York, NY, USA, 2010. ACM. ISBN 978-1-60558-8889.

Digital Library

[18]

T. L. Harris, K. Fraser, and I. A. Pratt. A practical multi-word compare-and-swap operation. In Proceedings of the 16th International Conference on Distributed Computing, DISC '02, pages 265--279, 2002.

Digital Library

[19]

M. Herlihy and N. Shavit. The Art of Multiprocessor Programming. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2008. ISBN 0123705916, 9780123705914.

Digital Library

[20]

P. Jayanti. An optimal multi-writer snapshot algorithm. In Proceedings of the Thirty-seventh Annual ACM Symposium on Theory of Computing, STOC '05, pages 723--732, New York, NY, USA, 2005. ACM. ISBN 1-58113-960-8.

Digital Library

[21]

A. Matveev, N. Shavit, P. Felber, and P. Marlier. Read-log-update: A lightweight synchronization mechanism for concurrent programming. In Proceedings of the 25th Symposium on Operating Systems Principles, SOSP '15, pages 168--183, New York, NY, USA, 2015. ACM. ISBN 9781-4503-3834-9.

Digital Library

[22]

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

[23]

A. Natarajan and N. Mittal. Fast concurrent lock-free binary search trees. In Proceedings of the 19th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP '14, pages 317--328, New York, NY, USA, 2014. ACM. ISBN 978-1-4503-2656-8.

Digital Library

[24]

E. Petrank and S. Timnat. Lock-free data-structure iterators. In Proceedings of the 27th International Symposium on Distributed Computing - Volume 8205, DISC 2013, pages 224--238, New York, NY, USA, 2013. Springer-Verlag New York, Inc. ISBN 978-3-642-415265.

Digital Library

[25]

A. Prokopec, N. G. Bronson, P. Bagwell, and M. Odersky. Concurrent tries with efficient non-blocking snapshots. SIGPLAN Not., 47(8):151--160, Feb. 2012. ISSN 0362-1340.

Digital Library

[26]

K. Sagonas and K. Winblad. Efficient support for range queries and range updates using contention adapting search trees. In Revised Selected Papers of the 28th International Workshop on Languages and Compilers for Parallel Computing - Volume 9519, LCPC 2015, pages 37--53, New York, NY, USA, 2016. Springer-Verlag New York, Inc. ISBN 978-3-319-29777-4.

Digital Library

[27]

X. Yu, G. Bezerra, A. Pavlo, S. Devadas, and M. Stonebraker. Staring into the abyss: An evaluation of concurrency control with one thousand cores. Proc. VLDB Endow., 8(3):209--220, Nov. 2014. ISSN 2150--8097.

Digital Library

Cited By

Bhardwaj GChatterjee BSharma APeri SNayak S(2024)Kanva: A Lock-free Learned Search Data StructureProceedings of the 53rd International Conference on Parallel Processing10.1145/3673038.3673082(252-261)Online publication date: 12-Aug-2024
https://dl.acm.org/doi/10.1145/3673038.3673082
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
Bittencourt JCosta DPortugal PVasques F(2024)A data-driven clustering approach for assessing spatiotemporal vulnerability to urban emergenciesSustainable Cities and Society10.1016/j.scs.2024.105477108(105477)Online publication date: Aug-2024
https://doi.org/10.1016/j.scs.2024.105477
Show More Cited By

Recommendations

A marriage of pointer- and epoch-based reclamation
PLDI 2020: Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation

All pointer-based nonblocking concurrent data structures should deal with the problem of safe memory reclamation: before reclaiming a memory block, a thread should ensure no other threads hold a local pointer to the block that may later be dereferenced. ...
Harnessing epoch-based reclamation for efficient range queries
PPoPP '18: Proceedings of the 23rd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming

Concurrent sets with range query operations are highly desirable in applications such as in-memory databases. However, few set implementations offer range queries. Known techniques for augmenting data structures with range queries (or operations that ...
Design and Evaluation of an Efficient Semispace-based Memory Reclamation Scheme
IMCCC '11: Proceedings of the 2011 First International Conference on Instrumentation, Measurement, Computer, Communication and Control

Now that in language with garbage collection (GC) mechanism such as Java, the GC should be a direct impact on the performance of the program, and the requirement of real time GC is even higher in a real-time system. We proposed a memory reclamation ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 53, Issue 1

PPoPP '18

January 2018

426 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/3200691

Editor:
Matthew Fluet
Rodchester Institude of Technology

Issue’s Table of Contents

PPoPP '18: Proceedings of the 23rd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming
February 2018
442 pages
ISBN:9781450349826
DOI:10.1145/3178487
General Chair:
Andreas Krall
Vienna University of Technology, Austria
,
Program Chair:
Thomas R. Gross
ETH Zürich, Switzerland

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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 10 February 2018

Published in SIGPLAN Volume 53, Issue 1

Check for updates

Badges

Qualifiers

Research-article

Funding Sources

Israel Science Foundation
Global Affairs Canada
Natural Sciences and Engineering Research Council of Canada

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

25
Total Citations
View Citations
501
Total Downloads

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

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Bhardwaj GChatterjee BSharma APeri SNayak S(2024)Kanva: A Lock-free Learned Search Data StructureProceedings of the 53rd International Conference on Parallel Processing10.1145/3673038.3673082(252-261)Online publication date: 12-Aug-2024
https://dl.acm.org/doi/10.1145/3673038.3673082
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
Bittencourt JCosta DPortugal PVasques F(2024)A data-driven clustering approach for assessing spatiotemporal vulnerability to urban emergenciesSustainable Cities and Society10.1016/j.scs.2024.105477108(105477)Online publication date: Aug-2024
https://doi.org/10.1016/j.scs.2024.105477
Rinberg AKeidar I(2023)Intermediate Value Linearizability: A Quantitative Correctness CriterionJournal of the ACM10.1145/358469970:2(1-21)Online publication date: 22-Feb-2023
https://dl.acm.org/doi/10.1145/3584699
Bhardwaj GChatterjee BJain APeri S(2023)Wait-Free Updates and Range Search Using UruvStabilization, Safety, and Security of Distributed Systems10.1007/978-3-031-44274-2_33(435-450)Online publication date: 2-Oct-2023
https://dl.acm.org/doi/10.1007/978-3-031-44274-2_33
Bashari BWoelfel PMiller ACensor-Hillel K(2021)An Efficient Adaptive Partial Snapshot ImplementationProceedings of the 2021 ACM Symposium on Principles of Distributed Computing10.1145/3465084.3467939(545-555)Online publication date: 21-Jul-2021
https://dl.acm.org/doi/10.1145/3465084.3467939
Fatourou PPapavasileiou ERuppert EScheideler CBerenbrink P(2019)Persistent Non-Blocking Binary Search Trees Supporting Wait-Free Range QueriesThe 31st ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3323165.3323197(275-286)Online publication date: 17-Jun-2019
https://dl.acm.org/doi/10.1145/3323165.3323197
Blelloch GWei YLee IChabbi MSteuwer M(2024)VERLIB: Concurrent Versioned PointersProceedings of the 29th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming10.1145/3627535.3638501(200-214)Online publication date: 2-Mar-2024
https://dl.acm.org/doi/10.1145/3627535.3638501
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
Show More Cited By

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 Issue’s Table of Contents