Document Open Access Logo

EEMARQ: Efficient Lock-Free Range Queries with Memory Reclamation

Authors Gali Sheffi, Pedro Ramalhete, Erez Petrank

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2022.5.pdf
  • Filesize: 0.95 MB
  • 22 pages

Document Identifiers

Author Details

Gali Sheffi
  • Department of Computer Science, Technion, Haifa, Israel
Pedro Ramalhete
  • Cisco Systems, Zürich, Switzerland
Erez Petrank
  • Department of Computer Science, Technion, Haifa, Israel

Funding

This work was supported by the Israel Science Foundation Grant No. 1102/21.

Cite AsGet BibTex

Gali Sheffi, Pedro Ramalhete, and Erez Petrank. EEMARQ: Efficient Lock-Free Range Queries with Memory Reclamation. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 5:1-5:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.OPODIS.2022.5

Abstract

Multi-Version Concurrency Control (MVCC) is a common mechanism for achieving linearizable range queries in database systems and concurrent data-structures. The core idea is to keep previous versions of nodes to serve range queries, while still providing atomic reads and updates. Existing concurrent data-structure implementations, that support linearizable range queries, are either slow, use locks, or rely on blocking reclamation schemes. We present EEMARQ, the first scheme that uses MVCC with lock-free memory reclamation to obtain a fully lock-free data-structure supporting linearizable inserts, deletes, contains, and range queries. Evaluation shows that EEMARQ outperforms existing solutions across most workloads, with lower space overhead and while providing full lock freedom.

Subject Classification

ACM Subject Classification
  • Software and its engineering → Memory management
  • Theory of computation → Concurrency
Keywords
  • safe memory reclamation
  • lock-freedom
  • snapshot
  • concurrency
  • range query

Metrics

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

Related Versions

Supplementary Materials

References

  1. Yehuda Afek, Hagit Attiya, Danny Dolev, Eli Gafni, Michael Merritt, and Nir Shavit. Atomic snapshots of shared memory. Journal of the ACM (JACM), 40(4):873-890, 1993. Google Scholar
  2. Panagiotis Antonopoulos, Peter Byrne, Wayne Chen, Cristian Diaconu, Raghavendra Thallam Kodandaramaih, Hanuma Kodavalla, Prashanth Purnananda, Adrian-Leonard Radu, Chaitanya Sreenivas Ravella, and Girish Mittur Venkataramanappa. Constant time recovery in azure sql database. Proceedings of the VLDB Endowment, 12(12):2143-2154, 2019. Google Scholar
  3. Maya Arbel-Raviv and Trevor Brown. Harnessing epoch-based reclamation for efficient range queries. ACM SIGPLAN Notices, 53(1):14-27, 2018. Google Scholar
  4. Hagit Attiya, Rachid Guerraoui, and Eric Ruppert. Partial snapshot objects. In Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, pages 336-343, 2008. Google Scholar
  5. Hillel Avni, Nir Shavit, and Adi Suissa. Leaplist: lessons learned in designing tm-supported range queries. In Proceedings of the 2013 ACM symposium on Principles of distributed computing, pages 299-308, 2013. Google Scholar
  6. Daniel Bartholomew. MariaDB cookbook. Packt Publishing Ltd, 2014. Google Scholar
  7. 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, pages 357-369, 2017. Google Scholar
  8. Naama Ben-David, Guy E Blelloch, Panagiota Fatourou, Eric Ruppert, Yihan Sun, and Yuanhao Wei. Space and time bounded multiversion garbage collection. arXiv preprint arXiv:2108.02775, 2021. Google Scholar
  9. Philip A Bernstein and Nathan Goodman. Concurrency control algorithms for multiversion database systems. In Proceedings of the first ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, pages 209-215, 1982. Google Scholar
  10. Philip A Bernstein and Nathan Goodman. Multiversion concurrency control—theory and algorithms. ACM Transactions on Database Systems (TODS), 8(4):465-483, 1983. Google Scholar
  11. Jan Böttcher, Viktor Leis, Thomas Neumann, and Alfons Kemper. Scalable garbage collection for in-memory mvcc systems. Proceedings of the VLDB Endowment, 13(2):128-141, 2019. Google Scholar
  12. Nathan G Bronson, Jared Casper, Hassan Chafi, and Kunle Olukotun. A practical concurrent binary search tree. ACM Sigplan Notices, 45(5):257-268, 2010. Google Scholar
  13. Trevor Brown and Hillel Avni. Range queries in non-blocking k-ary search trees. In International Conference On Principles Of Distributed Systems, pages 31-45. Springer, 2012. Google Scholar
  14. Trevor Brown, Faith Ellen, and Eric Ruppert. A general technique for non-blocking trees. In Proceedings of the 19th ACM SIGPLAN symposium on Principles and practice of parallel programming, pages 329-342, 2014. Google Scholar
  15. Trevor Alexander 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, pages 261-270, 2015. Google Scholar
  16. Bapi Chatterjee. Lock-free linearizable 1-dimensional range queries. In Proceedings of the 18th International Conference on Distributed Computing and Networking, pages 1-10, 2017. Google Scholar
  17. Andreia Correia, Pedro Ramalhete, and Pascal Felber. Orcgc: automatic lock-free memory reclamation. In Proceedings of the 26th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pages 205-218, 2021. Google Scholar
  18. David L Detlefs, Paul A Martin, Mark Moir, and Guy L Steele Jr. Lock-free reference counting. Distributed Computing, 15(4):255-271, 2002. Google Scholar
  19. Cristian Diaconu, Craig Freedman, Erik Ismert, Per-Ake Larson, Pravin Mittal, Ryan Stonecipher, Nitin Verma, and Mike Zwilling. Hekaton: Sql server’s memory-optimized oltp engine. In Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data, pages 1243-1254, 2013. Google Scholar
  20. Faith Ellen, Panagiota Fatourou, Eric Ruppert, and Franck van Breugel. Non-blocking binary search trees. In Proceedings of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing, pages 131-140, 2010. Google Scholar
  21. Franz Färber, Norman May, Wolfgang Lehner, Philipp Große, Ingo Müller, Hannes Rauhe, and Jonathan Dees. The sap hana database-an architecture overview. IEEE Data Eng. Bull., 35(1):28-33, 2012. Google Scholar
  22. Panagiota Fatourou, Elias Papavasileiou, and Eric Ruppert. Persistent non-blocking binary search trees supporting wait-free range queries. In The 31st ACM Symposium on Parallelism in Algorithms and Architectures, pages 275-286, 2019. Google Scholar
  23. Sérgio Miguel Fernandes and Joao Cachopo. Lock-free and scalable multi-version software transactional memory. ACM SIGPLAN Notices, 46(8):179-188, 2011. Google Scholar
  24. Keir Fraser. Practical lock-freedom. Technical report, University of Cambridge, Computer Laboratory, 2004. Google Scholar
  25. Theo Härder. Observations on optimistic concurrency control schemes. Information Systems, 9(2):111-120, 1984. Google Scholar
  26. Timothy L Harris. A pragmatic implementation of non-blocking linked-lists. In International Symposium on Distributed Computing, pages 300-314. Springer, 2001. Google Scholar
  27. Maurice Herlihy, Victor Luchangco, Paul Martin, and Mark Moir. Nonblocking memory management support for dynamic-sized data structures. ACM Transactions on Computer Systems (TOCS), 23(2):146-196, 2005. Google Scholar
  28. Maurice Herlihy, Nir Shavit, Victor Luchangco, and Michael Spear. The art of multiprocessor programming. Newnes, 2020. Google Scholar
  29. Maurice P Herlihy and Jeannette M Wing. Linearizability: A correctness condition for concurrent objects. ACM Transactions on Programming Languages and Systems (TOPLAS), 12(3):463-492, 1990. Google Scholar
  30. Nikolaos D Kallimanis and Eleni Kanellou. Wait-free concurrent graph objects with dynamic traversals. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016. Google Scholar
  31. Idit Keidar and Dmitri Perelman. Multi-versioning in transactional memory. In Transactional Memory. Foundations, Algorithms, Tools, and Applications, pages 150-165. Springer, 2015. Google Scholar
  32. Alfons Kemper and Thomas Neumann. Hyper: A hybrid oltp&olap main memory database system based on virtual memory snapshots. In 2011 IEEE 27th International Conference on Data Engineering, pages 195-206. IEEE, 2011. Google Scholar
  33. Jongbin Kim, Hyunsoo Cho, Kihwang Kim, Jaeseon Yu, Sooyong Kang, and Hyungsoo Jung. Long-lived transactions made less harmful. In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data, pages 495-510, 2020. Google Scholar
  34. Jongbin Kim, Kihwang Kim, Hyunsoo Cho, Jaeseon Yu, Sooyong Kang, and Hyungsoo Jung. Rethink the scan in mvcc databases. In Proceedings of the 2021 International Conference on Management of Data, pages 938-950, 2021. Google Scholar
  35. Priyanka Kumar, Sathya Peri, and K Vidyasankar. A timestamp based multi-version stm algorithm. In International Conference on Distributed Computing and Networking, pages 212-226. Springer, 2014. Google Scholar
  36. Juchang Lee, Hyungyu Shin, Chang Gyoo Park, Seongyun Ko, Jaeyun Noh, Yongjae Chuh, Wolfgang Stephan, and Wook-Shin Han. Hybrid garbage collection for multi-version concurrency control in sap hana. In Proceedings of the 2016 International Conference on Management of Data, pages 1307-1318, 2016. Google Scholar
  37. Li Lu and Michael L Scott. Generic multiversion stm. In International Symposium on Distributed Computing, pages 134-148. Springer, 2013. Google Scholar
  38. Alexander Matveev, Nir Shavit, Pascal Felber, and Patrick Marlier. Read-log-update: a lightweight synchronization mechanism for concurrent programming. In Proceedings of the 25th Symposium on Operating Systems Principles, pages 168-183, 2015. Google Scholar
  39. Paul E McKenney and John D Slingwine. Read-copy update: Using execution history to solve concurrency problems. In Parallel and Distributed Computing and Systems, volume 509518, 1998. Google Scholar
  40. Maged M Michael. Hazard pointers: Safe memory reclamation for lock-free objects. IEEE Transactions on Parallel and Distributed Systems, 15(6):491-504, 2004. Google Scholar
  41. AB MySQL. Mysql, 2001. Google Scholar
  42. Aravind Natarajan and Neeraj Mittal. Fast concurrent lock-free binary search trees. In Proceedings of the 19th ACM SIGPLAN symposium on Principles and practice of parallel programming, pages 317-328, 2014. Google Scholar
  43. Jacob Nelson-Slivon, Ahmed Hassan, and Roberto Palmieri. Bundling linked data structures for linearizable range queries. In Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pages 368-384, 2022. Google Scholar
  44. Yiannis Nikolakopoulos, Anders Gidenstam, Marina Papatriantafilou, and Philippas Tsigas. A consistency framework for iteration operations in concurrent data structures. In 2015 IEEE International Parallel and Distributed Processing Symposium, pages 239-248. IEEE, 2015. Google Scholar
  45. Yiannis Nikolakopoulos, Anders Gidenstam, Marina Papatriantafilou, and Philippas Tsigas. Of concurrent data structures and iterations. In Algorithms, Probability, Networks, and Games, pages 358-369. Springer, 2015. Google Scholar
  46. Christos H Papadimitriou. The serializability of concurrent database updates. Journal of the ACM (JACM), 26(4):631-653, 1979. Google Scholar
  47. Christos H Papadimitriou and Paris C Kanellakis. On concurrency control by multiple versions. ACM Transactions on Database Systems (TODS), 9(1):89-99, 1984. Google Scholar
  48. Dmitri Perelman, Anton Byshevsky, Oleg Litmanovich, and Idit Keidar. Smv: Selective multi-versioning stm. In International Symposium on Distributed Computing, pages 125-140. Springer, 2011. Google Scholar
  49. Dmitri Perelman, Rui Fan, and Idit Keidar. On maintaining multiple versions in stm. In Proceedings of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing, pages 16-25, 2010. Google Scholar
  50. Erez Petrank and Shahar Timnat. Lock-free data-structure iterators. In International Symposium on Distributed Computing, pages 224-238. Springer, 2013. Google Scholar
  51. Hasso Plattner. A common database approach for oltp and olap using an in-memory column database. In Proceedings of the 2009 ACM SIGMOD International Conference on Management of data, pages 1-2, 2009. Google Scholar
  52. Behandelt PostgreSQL. Postgresql. Web resource: http://www. PostgreSQL. org/about, 1996. Google Scholar
  53. Aleksandar Prokopec. Snapqueue: lock-free queue with constant time snapshots. In Proceedings of the 6th ACM SIGPLAN Symposium on Scala, pages 1-12, 2015. Google Scholar
  54. Aleksandar Prokopec, Nathan Grasso Bronson, Phil Bagwell, and Martin Odersky. Concurrent tries with efficient non-blocking snapshots. In Proceedings of the 17th ACM SIGPLAN symposium on Principles and Practice of Parallel Programming, pages 151-160, 2012. Google Scholar
  55. Pedro Ramalhete and Andreia Correia. Brief announcement: Hazard eras-non-blocking memory reclamation. In Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures, pages 367-369, 2017. Google Scholar
  56. G Satyanarayana Reddy, Rallabandi Srinivasu, M Poorna Chander Rao, and Srikanth Reddy Rikkula. Data warehousing, data mining, olap and oltp technologies are essential elements to support decision-making process in industries. International Journal on Computer Science and Engineering, 2(9):2865-2873, 2010. Google Scholar
  57. Gali Sheffi, Guy Golan-Gueta, and Erez Petrank. A scalable linearizable multi-index table. In 2018 IEEE 38th International Conference on Distributed Computing Systems (ICDCS), pages 200-211. IEEE, 2018. Google Scholar
  58. Gali Sheffi, Maurice Herlihy, and Erez Petrank. VBR: Version Based Reclamation. In Seth Gilbert, editor, 35th International Symposium on Distributed Computing (DISC 2021), volume 209 of Leibniz International Proceedings in Informatics (LIPIcs), pages 35:1-35:18, Dagstuhl, Germany, 2021. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.DISC.2021.35.
  59. Gali Sheffi, Maurice Herlihy, and Erez Petrank. Vbr: Version based reclamation. In Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures, pages 443-445, 2021. Google Scholar
  60. Gali Sheffi, Pedro Ramalhete, and Erez Petrank. Eemarq: Efficient lock-free range queries with memory reclamation. arXiv preprint arXiv:2210.17086, 2022. Google Scholar
  61. Ajay Singh, Trevor Brown, and Ali Mashtizadeh. Nbr: neutralization based reclamation. In Proceedings of the 26th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pages 175-190, 2021. Google Scholar
  62. Daniel Solomon and Adam Morrison. Efficiently reclaiming memory in concurrent search data structures while bounding wasted memory. In Proceedings of the 26th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pages 191-204, 2021. Google Scholar
  63. Alexander Spiegelman, Guy Golan-Gueta, and Idit Keidar. Transactional data structure libraries. ACM SIGPLAN Notices, 51(6):682-696, 2016. Google Scholar
  64. Alexander Thomasian and In Kyung Ryu. Performance analysis of two-phase locking. IEEE Transactions on Software Engineering, 17(5):386, 1991. Google Scholar
  65. Yuanhao Wei, Naama Ben-David, Guy E Blelloch, Panagiota Fatourou, Eric Ruppert, and Yihan Sun. Constant-time snapshots with applications to concurrent data structures. In Proceedings of the 26th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pages 31-46, 2021. Google Scholar
  66. Haosen Wen, Joseph Izraelevitz, Wentao Cai, H Alan Beadle, and Michael L Scott. Interval-based memory reclamation. ACM SIGPLAN Notices, 53(1):1-13, 2018. Google Scholar
  67. Kjell Winblad, Konstantinos Sagonas, and Bengt Jonsson. Lock-free contention adapting search trees. ACM Transactions on Parallel Computing (TOPC), 8(2):1-38, 2021. Google Scholar
  68. Yingjun Wu, Joy Arulraj, Jiexi Lin, Ran Xian, and Andrew Pavlo. An empirical evaluation of in-memory multi-version concurrency control. Proceedings of the VLDB Endowment, 10(7):781-792, 2017. Google Scholar
  69. Yoav Zuriel, Michal Friedman, Gali Sheffi, Nachshon Cohen, and Erez Petrank. Efficient lock-free durable sets. Proceedings of the ACM on Programming Languages, 3(OOPSLA):1-26, 2019. 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 Imprint Privacy Contact