Document Open Access Logo

Faster Concurrent Range Queries with Contention Adapting Search Trees Using Immutable Data

Author Kjell Winblad

PDF
Thumbnail PDF

File

OASIcs.ICCSW.2017.7.pdf
  • Filesize: 8.21 MB
  • 13 pages

Document Identifiers

Author Details

Kjell Winblad

Cite As Get BibTex

Kjell Winblad. Faster Concurrent Range Queries with Contention Adapting Search Trees Using Immutable Data. In 2017 Imperial College Computing Student Workshop (ICCSW 2017). Open Access Series in Informatics (OASIcs), Volume 60, pp. 7:1-7:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/OASIcs.ICCSW.2017.7

Abstract

The need for scalable concurrent ordered set data structures with linearizable range query support is increasing due to the rise of multicore computers, data processing platforms and in-memory databases. This paper presents a new concurrent ordered set with linearizable range query support. The new data structure is based on the contention adapting search tree and an immutable data structure.
Experimental results show that the new data structure is as much as three times faster compared to related data structures. The data structure scales well due to its ability to adapt the sizes of its immutable parts to the contention level and the sizes of the range queries.

Subject Classification

Keywords
  • linearizability
  • concurrent data structures
  • treap

Metrics

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

References

  1. Flurry analytics. https://developer.yahoo.com/flurry/docs/analytics/. Accessed: 2017-07-26.
  2. Hillel Avni, Nir Shavit, and Adi Suissa. Leaplist: lessons learned in designing tm-supported range queries. In Panagiota Fatourou and Gadi Taubenfeld, editors, ACM Symposium on Principles of Distributed Computing, PODC '13, Montreal, QC, Canada, July 22-24, 2013, pages 299-308. ACM, 2013. URL: http://dx.doi.org/10.1145/2484239.2484254.
  3. Dmitry Basin, Edward Bortnikov, Anastasia Braginsky, Guy Golan-Gueta, Eshcar Hillel, Idit Keidar, and Moshe 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. URL: http://dx.doi.org/10.1145/3018743.3018761.
  4. Nathan Grasso Bronson, Jared Casper, Hassan Chafi, and Kunle Olukotun. A practical concurrent binary search tree. In R. Govindarajan, David A. Padua, and Mary W. Hall, editors, Proceedings of the 15th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP 2010, Bangalore, India, January 9-14, 2010, pages 257-268. ACM, 2010. URL: http://dx.doi.org/10.1145/1693453.1693488.
  5. Trevor Brown and Hillel Avni. Range queries in non-blocking k-ary search trees. In Roberto Baldoni, Paola Flocchini, and Binoy Ravindran, editors, Principles of Distributed Systems, 16th International Conference, OPODIS 2012, Rome, Italy, December 18-20, 2012. Proceedings, volume 7702 of Lecture Notes in Computer Science, pages 31-45. Springer, 2012. URL: http://dx.doi.org/10.1007/978-3-642-35476-2_3.
  6. Trevor Brown and Joanna Helga. Non-blocking k-ary search trees. In Antonio Fernández Anta, Giuseppe Lipari, and Matthieu Roy, editors, Principles of Distributed Systems - 15th International Conference, OPODIS 2011, Toulouse, France, December 13-16, 2011. Proceedings, volume 7109 of Lecture Notes in Computer Science, pages 207-221. Springer, 2011. URL: http://dx.doi.org/10.1007/978-3-642-25873-2_15.
  7. Bapi 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. URL: http://dx.doi.org/10.1145/3007748.3007771.
  8. Keir Fraser. Practical lock-freedom. PhD thesis, University of Cambridge Computer Laboratory, 2004. Google Scholar
  9. Maurice Herlihy. A methodology for implementing highly concurrent data structures. In David A. Padua, editor, Proceedings of the Second ACM SIGPLAN Symposium on Princiles & Practice of Parallel Programming (PPOPP), Seattle, Washington, USA, March 14-16, 1990, pages 197-206. ACM, 1990. URL: http://dx.doi.org/10.1145/99163.99185.
  10. Maurice Herlihy and Jeannette M. Wing. Linearizability: A correctness condition for concurrent objects. ACM Trans. Program. Lang. Syst., 12(3):463-492, 1990. URL: http://dx.doi.org/10.1145/78969.78972.
  11. Christoph Lameter. Effective synchronization on Linux/NUMA systems. In Proc. of the Gelato Federation Meeting, 2005. URL: http://www.kde.ps.pl/mirrors/ftp.kernel.org/linux/kernel/people/christoph/gelato/gelato2005-paper.pdf.
  12. Maged M. Michael. High performance dynamic lock-free hash tables and list-based sets. In SPAA, pages 73-82, 2002. URL: http://dx.doi.org/10.1145/564870.564881.
  13. Aravind Natarajan and Neeraj Mittal. Fast concurrent lock-free binary search trees. In José E. Moreira and James R. Larus, editors, ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP '14, Orlando, FL, USA, February 15-19, 2014, pages 317-328. ACM, 2014. URL: http://dx.doi.org/10.1145/2555243.2555256.
  14. Chris Okasaki. Purely functional data structures. Cambridge University Press, 1999. Google Scholar
  15. Erez Petrank and Shahar Timnat. Lock-free data-structure iterators. In Yehuda Afek, editor, Distributed Computing - 27th International Symposium, DISC 2013, Jerusalem, Israel, October 14-18, 2013. Proceedings, volume 8205 of Lecture Notes in Computer Science, pages 224-238. Springer, 2013. URL: http://dx.doi.org/10.1007/978-3-642-41527-2_16.
  16. Aleksandar Prokopec, Nathan Grasso Bronson, Phil Bagwell, and Martin Odersky. Concurrent tries with efficient non-blocking snapshots. In J. Ramanujam and P. Sadayappan, editors, Proceedings of the 17th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP 2012, New Orleans, LA, USA, February 25-29, 2012, pages 151-160. ACM, 2012. URL: http://dx.doi.org/10.1145/2145816.2145836.
  17. Callum Robertson. Implementing contention-friendly range queries in non-blocking key-value stores. Bachelor thesis, The University of Sydney, 2014. Google Scholar
  18. Konstantinos Sagonas and Kjell Winblad. Contention adapting search trees. In Daniel Grosu, Hai Jin, and George Papadopoulos, editors, 14th International Symposium on Parallel and Distributed Computing, ISPDC 2015, Limassol, Cyprus, June 29 - July 2, 2015, pages 215-224. IEEE Computer Society, 2015. URL: http://dx.doi.org/10.1109/ISPDC.2015.32.
  19. Konstantinos Sagonas and Kjell Winblad. Efficient support for range queries and range updates using contention adapting search trees. In Xipeng Shen, Frank Mueller, and James Tuck, editors, Languages and Compilers for Parallel Computing - 28th International Workshop, LCPC 2015, Raleigh, NC, USA, September 9-11, 2015, Revised Selected Papers, volume 9519 of Lecture Notes in Computer Science, pages 37-53. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-319-29778-1_3.
  20. Konstantinos Sagonas and Kjell Winblad. A contention adapting approach to concurrent ordered sets. Journal of Parallel and Distributed Computing, Forthcoming. Google Scholar
  21. Raimund Seidel and Cecilia R. Aragon. Randomized search trees. Algorithmica, 16(4/5):464-497, 1996. URL: http://dx.doi.org/10.1007/BF01940876.
  22. Ori Shalev and Nir Shavit. Split-ordered lists: Lock-free extensible hash tables. J. ACM, 53(3):379-405, 2006. URL: http://dx.doi.org/10.1145/1147954.1147958.
  23. Jeff Shute, Radek Vingralek, Bart Samwel, Ben Handy, Chad Whipkey, Eric Rollins, Mircea Oancea, Kyle Littlefield, David Menestrina, Stephan Ellner, John Cieslewicz, Ian Rae, Traian Stancescu, and Himani Apte. F1: A distributed SQL database that scales. Proceedings of the VLDB Endowment, 6(11):1068-1079, 2013. URL: http://dx.doi.org/10.14778/2536222.2536232.
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