skip to main content
10.1145/2611462.2611471acmconferencesArticle/Chapter ViewAbstractPublication PagespodcConference Proceedingsconference-collections
research-article

Concurrent updates with RCU: search tree as an example

Published: 15 July 2014 Publication History

Abstract

Read copy update (RCU) is a novel synchronization mechanism, in which the burden of synchronization falls completely on the updaters, by having them wait for all pre-existing readers to finish their read-side critical section. This paper presents citrus, a concurrent binary search tree (BST) with a wait-free Contains operation, using RCU synchronization and fine-grained locking for synchronization among updaters. This is the first RCU-based data structure that allows concurrent updaters. While there are methodologies for using RCU to coordinate between readers and updaters, they do not address the issue of coordination among updaters, and indeed, all existing RCU-based data structures rely on coarse-grained synchronization between updaters.
Experimental evaluation shows that \citrus beats previous RCU-based search trees, even under mild update contention, and compares well with the best-known concurrent dictionaries.

References

[1]
Y. Afek, H. Kaplan, B. Korenfeld, A. Morrison, and R. E. Tarjan. CBTree: A practical concurrent self-adjusting search tree. DISC 2012, pp. 1--15.
[2]
H. Attiya, R. Guerraoui, and E. Ruppert. Partial snapshot objects. SPAA 2008, pp. 336--343.%
[3]
%R. Bayer and M. Schkolnick. Concurrency of operations on b-trees. In M. Stonebraker (ed.), Readings in database systems, pages% 129--139. Morgan Kaufmann, 1988.
[4]
A. Braginsky and E. Petrank. A lock-free B+ tree. SPAA 2012, pp. 58--67, 2012.
[5]
N. G. Bronson, J. Casper, H. Chafi, and K. Olukotun. A practical concurrent binary search tree. PPoPP 2010, pp. 257--268.
[6]
T. Brown, F. Ellen, and E. Ruppert. A general technique for non-blocking trees. PPoPP 2014, pp. 329--342.
[7]
A. T. Clements, M. F. Kaashoek, and N. Zeldovich. Scalable address spaces using RCU balanced trees. ASPLOS 2012, pp. 199--210.
[8]
T. Crain, V. Gramoli, and M. Raynal. A contention-friendly binary search tree. Euro-Par 2010, pp. 229--240.
[9]
M. Desnoyers, P. McKenney, A. Stern, M. Dagenais, and J. Walpole. User-level implementations of Read-Copy Update. IEEE Transactions on Parallel and Distributed Systems, 23(2):375--382, 2012.
[10]
D. Drachsler, M. Vechev, and E. Yahav. Practical concurrent binary search trees via logical ordering. PPoPP 2014, pp. 343--356.
[11]
F. Ellen, P. Fatourou, E. Ruppert, and F. van Breugel. Non-blocking binary search trees. PODC 2010, pp. 131--140.%
[12]
K. P. Eswaran, J. N. Gray, R. A. Lorie, and I. L. Traiger. The notions of consistency and predicate locks in a database system. Commun. ACM, 19(11):624--633, Nov. 1976.
[13]
K. Fraser. Practical lock-freedom. PhD thesis, University of Cambridge, 2003.
[14]
A. Gotsman, N. Rinetzky, and H. Yang. Verifying concurrent memory reclamation algorithms with grace. ESOP 2013, pp. 249--269.
[15]
D. Guniguntala, P. E. McKenney, J. Triplett, and J. Walpole. The read-copy-update mechanism for supporting real-time applications on shared-memory multiprocessor systems with Linux. IBM Systems Journal, 47(2):221--236, May 2008.
[16]
S. Heller, M. Herlihy, V. Luchangco, M. Moir, W. N. Scherer III, and N. Shavit. A lazy concurrent list-based set algorithm. OPODIS 2006, pp. 3--16.
[17]
M. Herlihy, Y. Lev, V. Luchangco, and N. Shavit. A simple optimistic skiplist algorithm. SIROCCO 2007, pp. 124--138.
[18]
M. Herlihy and J. E. B. Moss. Transactional memory: architectural support for lock-free data structures. SIGARCH Comput. Archit. News, 21(2):289--300, May 1993.
[19]
M. P. Herlihy and J. M. Wing. Linearizability: a correctness condition for concurrent objects. ACM Trans. Program. Lang. Syst., 12(3):463--492, July 1990.
[20]
P. W. Howard, and J. Walpole. A case for relativistic programming. In ACM workshop on Relaxing Synchronization for Multicore and Manycore Scalability, pp. 33--38, 2012.
[21]
P. W. Howard and J. Walpole. Relativistic red-black trees. Concurrency & Computation: Practice & Experience, 2013.
[22]
S. V. Howley and J. Jones. A non-blocking internal binary search tree. SPAA 2012, pp. 161--171.
[23]
P. E. McKenney. RCU Linux usage. http://www.rdrop.com/users/paulmck/RCU/linuxusage.html.
[24]
P. E. McKenney. Exploiting Deferred Destruction: An Analysis of Read-Copy-Update Techniques in Operating System kernels. PhD thesis, Oregon State University, 2004.
[25]
P. E. McKenney and J. D. Slingwine. Read-copy update: Using execution history to solve concurrency problems. Parallel and Distributed Computing and Systems, pp. 509--518, 1998.
[26]
A. Natarajan and N. Mittal. Fast concurrent lock-free binary search trees. PPoPP 2014, pp. 317--328.
[27]
E. Petrank and S. Timnat. Lock-free data-structure iterators. DISC 2013, pp. 224--238.
[28]
A. Silberschatz and Z. Kedem. Consistency in hierarchical database systems. J. ACM, 27(1):72--80, 1980.
[29]
J. Triplett, P. E. McKenney, and J. Walpole. Scalable concurrent hash tables via relativistic programming. SIGOPS Oper. Syst. Rev., 44(3):102--109, Aug. 2010.
[30]
J. Triplett, P. E. McKenney, and J. Walpole. Resizable, scalable, concurrent hash tables. USENIX Annual Technical Conference, 2011.

Cited By

View all
  • (2023)FrozenHot Cache: Rethinking Cache Management for Modern HardwareProceedings of the Eighteenth European Conference on Computer Systems10.1145/3552326.3587446(557-573)Online publication date: 8-May-2023
  • (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
  • (2023)Lock-based or Lock-less: Which Is Fresh?IEEE INFOCOM 2023 - IEEE Conference on Computer Communications10.1109/INFOCOM53939.2023.10229077(1-10)Online publication date: 17-May-2023
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
PODC '14: Proceedings of the 2014 ACM symposium on Principles of distributed computing
July 2014
444 pages
ISBN:9781450329446
DOI:10.1145/2611462
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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 15 July 2014

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. internal search tree
  2. read-copy-update
  3. shared memory

Qualifiers

  • Research-article

Conference

PODC '14
Sponsor:

Acceptance Rates

PODC '14 Paper Acceptance Rate 39 of 141 submissions, 28%;
Overall Acceptance Rate 740 of 2,477 submissions, 30%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)36
  • Downloads (Last 6 weeks)4
Reflects downloads up to 06 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2023)FrozenHot Cache: Rethinking Cache Management for Modern HardwareProceedings of the Eighteenth European Conference on Computer Systems10.1145/3552326.3587446(557-573)Online publication date: 8-May-2023
  • (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
  • (2023)Lock-based or Lock-less: Which Is Fresh?IEEE INFOCOM 2023 - IEEE Conference on Computer Communications10.1109/INFOCOM53939.2023.10229077(1-10)Online publication date: 17-May-2023
  • (2023)Locksynth: Deriving Synchronization Code for Concurrent Data Structures with ASPTheory and Practice of Logic Programming10.1017/S1471068423000303(1-20)Online publication date: 1-Sep-2023
  • (2023)Compiler‐driven approach for automating nonblocking synchronization in concurrent data abstractionsConcurrency and Computation: Practice and Experience10.1002/cpe.793536:5Online publication date: 24-Oct-2023
  • (2022)Performance Analysis of RCU-Style Non-Blocking Synchronization Mechanisms on a Manycore-Based Operating SystemApplied Sciences10.3390/app1207345812:7(3458)Online publication date: 29-Mar-2022
  • (2022)Bundling linked data structures for linearizable range queriesProceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming10.1145/3503221.3508412(368-384)Online publication date: 2-Apr-2022
  • (2021)Verifying concurrent multicopy search structuresProceedings of the ACM on Programming Languages10.1145/34854905:OOPSLA(1-32)Online publication date: 15-Oct-2021
  • (2021)Sharing non‐cache‐coherent memory with bounded incoherenceConcurrency and Computation: Practice and Experience10.1002/cpe.641434:2Online publication date: Jun-2021
  • (2021)RCU‐HTM: A generic synchronization technique for highly efficient concurrent search treesConcurrency and Computation: Practice and Experience10.1002/cpe.617433:10Online publication date: 12-Jan-2021
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media