Document Open Access Logo

Lock-Free Search Data Structures: Throughput Modeling with Poisson Processes

Authors Aras Atalar, Paul Renaud-Goud, Philippas Tsigas

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2018.9.pdf
  • Filesize: 0.54 MB
  • 16 pages

Document Identifiers

Author Details

Aras Atalar
  • Chalmers University of Technology, S-41296 Göteborg, Sweden
Paul Renaud-Goud
  • Informatics Research Institute of Toulouse, F-31062 Toulouse, France
Philippas Tsigas
  • Chalmers University of Technology, S-41296 Göteborg, Sweden

Cite As Get BibTex

Aras Atalar, Paul Renaud-Goud, and Philippas Tsigas. Lock-Free Search Data Structures: Throughput Modeling with Poisson Processes. In 22nd International Conference on Principles of Distributed Systems (OPODIS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 125, pp. 9:1-9:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.OPODIS.2018.9

Abstract

This paper considers the modeling and the analysis of the performance of lock-free concurrent search data structures. Our analysis considers such lock-free data structures that are utilized through a sequence of operations which are generated with a memoryless and stationary access pattern. Our main contribution is a new way of analyzing lock-free concurrent search data structures: our execution model matches with the behavior that we observe in practice and achieves good throughput predictions.
Search data structures are formed of basic blocks, usually referred to as nodes, which can be accessed by two kinds of events, characterized by their latencies; (i) CAS events originated as a result of modifications of the search data structure (ii) Read events that occur during traversals. An operation triggers a set of events, and the running time of an operation is computed as the sum of the latencies of these events. We identify the factors that impact the latency of such events on a multi-core shared memory system. The main challenge (though not the only one) is that the latency of each event mainly depends on the state of the caches at the time when it is triggered, and the state of caches is changing due to events that are triggered by the operations of any thread in the system. Accordingly, the latency of an event is determined by the ordering of the events on the timeline.
Search data structures are usually designed to accommodate a large number of nodes, which makes the occurrence of an event on a given node rare at any given time. In this context, we model the events on each node as Poisson processes from which we can extract the frequency and probabilistic ordering of events that are used to estimate the expected latency of an operation, and in turn the throughput. We have validated our analysis on several fundamental lock-free search data structures such as linked lists, hash tables, skip lists and binary trees.

Subject Classification

ACM Subject Classification
  • Theory of computation → Concurrency
Keywords
  • Lock-free
  • Search Data Structures
  • Performance
  • Modeling
  • Analysis

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Dan Alistarh, Keren Censor-Hillel, and Nir Shavit. Are lock-free concurrent algorithms practically wait-free? In David B. Shmoys, editor, STOC, pages 714-723. ACM, June 2014. Google Scholar
  2. Aras Atalar, Paul Renaud-Goud, and Philippas Tsigas. Analyzing the Performance of Lock-Free Data Structures: A Conflict-Based Model. In DISC, pages 341-355. Springer, 2015. Google Scholar
  3. Aras Atalar, Paul Renaud-Goud, and Philippas Tsigas. How Lock-free Data Structures Perform in Dynamic Environments: Models and Analyses. In OPODIS, pages 23:1-23:17, 2016. Google Scholar
  4. Aras Atalar, Paul Renaud-Goud, and Philippas Tsigas. Lock-Free Search Data Structures: Throughput Modelling with Poisson Processes. CoRR, abs/1805.04794, 2018. URL: http://arxiv.org/abs/1805.04794.
  5. Hagit Attiya and Arie Fouren. Algorithms adapting to point contention. JACM, 50(4):444-468, 2003. Google Scholar
  6. Vlastimil Babka and Petr Tuma. Investigating Cache Parameters of x86 Family Processors. In SPEC Benchmark Workshop, pages 77-96. Springer, 2009. Google Scholar
  7. A.D. Barbour and T.C. Brown. Stein’s method and point process approximation. Stochastic Process. Appl., 43(1):9-31, 1992. Google Scholar
  8. Naama Ben-David and Guy E. Blelloch. Analyzing Contention and Backoff in Asynchronous Shared Memory. In PoDC, pages 53-62, 2017. Google Scholar
  9. Timothy C. Brown, Graham V. Weinberg, and Aihua Xia. Removing logarithms from Poisson process error bounds. Stochastic Process. Appl., 87(1):149-165, 2000. Google Scholar
  10. Hao Che, Ye Tung, and Zhijun Wang. Hierarchical Web caching systems: modeling, design and experimental results. IEEE Communications Society Press, 20(7):1305-1314, 2002. Google Scholar
  11. Tudor David, Rachid Guerraoui, and Vasileios Trigonakis. Asynchronized Concurrency: The Secret to Scaling Concurrent Search Data Structures. In ASPLOS, pages 631-644. ACM, 2015. Google Scholar
  12. Luc Devroye. A note on the height of binary search trees. JACM, 33(3):489-498, 1986. Google Scholar
  13. Cynthia Dwork, Maurice Herlihy, and Orli Waarts. Contention in shared memory algorithms. JACM, 44(6):779-805, 1997. Google Scholar
  14. James D. Fix. The set-associative cache performance of search trees. In SODA, pages 565-572, 2003. Google Scholar
  15. Philippe Flajolet, Danièle Gardy, and Loÿs Thimonier. Birthday Paradox, Coupon Collectors, Caching Algorithms and Self-Organizing Search. Discrete Applied Mathematics, 39(3):207-229, 1992. Google Scholar
  16. Mikhail Fomitchev and Eric Ruppert. Lock-free linked lists and skip lists. In PoDC, pages 50-59. ACM, 2004. Google Scholar
  17. Christine Fricker, Philippe Robert, and James Roberts. A versatile and accurate approximation for LRU cache performance. CoRR, abs/1202.3974, 2012. Google Scholar
  18. Vincent Gramoli. More than you ever wanted to know about synchronization: synchrobench, measuring the impact of the synchronization on concurrent algorithms. In PPoPP, pages 1-10. ACM, 2015. Google Scholar
  19. Timothy L. Harris. A Pragmatic Implementation of Non-blocking Linked-Lists. In DISC, volume 2180 of Lecture Notes in Computer Science, pages 300-314. Springer, 2001. Google Scholar
  20. Maurice Herlihy. A Methodology for Implementing Highly Concurrent Objects. TOPLAS, 15(5):745-770, 1993. Google Scholar
  21. Peter Kirschenhofer and Helmut Prodinger. The Path Length of Random Skip Lists. Acta Informatica, 31(8):775-792, 1994. Google Scholar
  22. John D. C. Little. A proof for the queuing formula: L= λ W. Operations research, 9(3):383-387, 1961. Google Scholar
  23. Aravind Natarajan and Neeraj Mittal. Fast concurrent lock-free binary search trees. In PPoPP, pages 317-328. ACM, 2014. Google Scholar
  24. Raimund Seidel and Cecilia R. Aragon. Randomized Search Trees. Algorithmica, 16(4/5):464-497, 1996. Google Scholar
  25. Håkan Sundell and Philippas Tsigas. Fast and lock-free concurrent priority queues for multi-thread systems. J. Parallel Distrib. Comput., 65(5):609-627, 2005. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact