Document Open Access Logo

Space and Time Bounded Multiversion Garbage Collection

Authors Naama Ben-David, Guy E. Blelloch, Panagiota Fatourou, Eric Ruppert, Yihan Sun, Yuanhao Wei

PDF
Thumbnail PDF

File

LIPIcs.DISC.2021.12.pdf
  • Filesize: 0.79 MB
  • 20 pages

Document Identifiers

Author Details

Naama Ben-David
  • VMware Research, Palo Alto, CA, USA
Guy E. Blelloch
  • Carnegie Mellon University, Pittsburgh, PA, USA
Panagiota Fatourou
  • FORTH ICS and University of Crete, Heraklion, Greece
Eric Ruppert
  • York University, Toronto, Canada
Yihan Sun
  • University of California, Riverside, CA, USA
Yuanhao Wei
  • Carnegie Mellon University, Pittsburgh, PA, USA

Funding

Guy E. Blelloch and Yuanhao Wei: NSF CCF-1901381, CCF-1910030, and CCF-1919223. Eric Ruppert: NSERC Discovery Grant. Yihan Sun: NSF grant CCF-2103483. Panagiota Fatourou: EU Horizon 2020, Marie Sklodowska-Curie GA No 101031688.

Acknowledgements

We thank the anonymous referees for their helpful comments and suggestions.

Cite AsGet BibTex

Naama Ben-David, Guy E. Blelloch, Panagiota Fatourou, Eric Ruppert, Yihan Sun, and Yuanhao Wei. Space and Time Bounded Multiversion Garbage Collection. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 12:1-12:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.DISC.2021.12

Abstract

We present a general technique for garbage collecting old versions for multiversion concurrency control that simultaneously achieves good time and space complexity. Our technique takes only O(1) time on average to reclaim each version and maintains only a constant factor more versions than needed (plus an additive term). It is designed for multiversion schemes using version lists, which are the most common. Our approach uses two components that are of independent interest. First, we define a novel range-tracking data structure which stores a set of old versions and efficiently finds those that are no longer needed. We provide a wait-free implementation in which all operations take amortized constant time. Second, we represent version lists using a new lock-free doubly-linked list algorithm that supports efficient (amortized constant time) removals given a pointer to any node in the list. These two components naturally fit together to solve the multiversion garbage collection problem - the range-tracker identifies which versions to remove and our list algorithm can then be used to remove them from their version lists. We apply our garbage collection technique to generate end-to-end time and space bounds for the multiversioning system of Wei et al. (PPoPP 2021).

Subject Classification

ACM Subject Classification
  • Theory of computation → Concurrent algorithms
  • Theory of computation → Data structures design and analysis
Keywords
  • Lock-free
  • data structures
  • memory management
  • snapshot
  • version lists

Metrics

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

Related Versions

References

  1. Dan Alistarh, Patrick Eugster, Maurice Herlihy, Alexander Matveev, and Nir Shavit. StackTrack: An automated transactional approach to concurrent memory reclamation. In Proc. 9th European Conference on Computer Systems, pages 25:1-25:14, 2014. URL: https://doi.org/10.1145/2592798.2592808.
  2. Daniel Anderson, Guy E Blelloch, and Yuanhao Wei. Concurrent deferred reference counting with constant-time overhead. In Proc. 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation, pages 526-541, 2021. Google Scholar
  3. James Aspnes, Hagit Attiya, and Keren Censor. Max registers, counters, and monotone circuits. In Proc. 28th ACM Symposium on Principles of Distributed Computing, pages 36-45, 2009. Google Scholar
  4. Hagit Attiya and Arie Fouren. Adaptive and efficient algorithms for lattice agreement and renaming. SIAM Journal on Computing, 31(2):642-664, 2001. Google Scholar
  5. Hagit Attiya and Eshcar Hillel. Built-in coloring for highly-concurrent doubly-linked lists. Theory of Computing Systems, 52(4):729-762, 2013. Google Scholar
  6. Henry G. Baker. List processing in real time on a serial computer. Commun. ACM, 21(4):280–294, 1978. URL: https://doi.org/10.1145/359460.359470.
  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. ACM Trans. Parallel Comput., 7(3):16:1-16:28, June 2020. URL: https://doi.org/10.1145/3399718.
  8. Naama Ben-David, Guy E. Blelloch, Panagiota Fatourou, Eric Ruppert, Yihan Sun, and Yuanhao Wei. Space and time bounded multiversion garbage collection, 2021. Available from URL: https://arxiv.org/abs/2108.02775.
  9. Jon Louis Bentley and Andrew Chi-Chih Yao. An almost optimal algorithm for unbounded searching. Information Processing Letters, 5(3):82-86, 1976. Google Scholar
  10. Philip A. Bernstein and Nathan Goodman. Multiversion concurrency control-theory and algorithms. ACM Trans. Database Syst., 8(4):465-483, December 1983. URL: https://doi.org/10.1145/319996.319998.
  11. Guy E. Blelloch and Perry Cheng. On bounding time and space for multiprocessor garbage collection. In Proc. ACM Conf. on Programming Language Design and Implementation, pages 104-117, 1999. URL: https://doi.org/10.1145/301618.301648.
  12. Guy E. Blelloch, Jeremy T. Fineman, Yan Gu, and Yihan Sun. Optimal parallel algorithms in the binary-forking model. In Proc. ACM Symp. on Parallelism in Algorithms and Architectures, pages 89-102, 2020. URL: https://doi.org/10.1145/3350755.3400227.
  13. Guy E. Blelloch and Yuanhao Wei. LL/SC and atomic copy: Constant time, space efficient implementations using only pointer-width CAS. In Proc. 34th International Symposium on Distributed Computing, volume 179 of LIPICS, pages 5:1-5:17, 2020. Google Scholar
  14. 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
  15. Trevor Alexander Brown. Reclaiming memory for lock-free data structures: There has to be a better way. In Proc. ACM Symposium on Principles of Distributed Computing, pages 261-270, 2015. URL: https://doi.org/10.1145/2767386.2767436.
  16. Andreia Correia, Pedro Ramalhete, and Pascal Felber. Orcgc: automatic lock-free memory reclamation. In Proc. of the 26th ACM Symp. on Principles and Practice of Parallel Programming, pages 205-218, 2021. Google Scholar
  17. David L. Detlefs, Paul A. Martin, Mark Moir, and Guy L. Steele. Lock-free reference counting. In Proc. 20th ACM Symposium on Principles of Distributed Computing, pages 190-199, 2001. URL: https://doi.org/10.1145/383962.384016.
  18. Aleksandar Dragojević, Maurice Herlihy, Yossi Lev, and Mark Moir. On the power of hardware transactional memory to simplify memory management. In Proc. 30th ACM Symposium on Principles of Distributed Computing, pages 99-108, 2011. URL: https://doi.org/10.1145/1993806.1993821.
  19. Faith Ellen, Panagiota Fatourou, Eric Ruppert, and Franck van Breugel. Non-blocking binary search trees. In Proc. 29th ACM Symposium on Principles of Distributed Computing, pages 131-140, 2010. URL: https://doi.org/10.1145/1835698.1835736.
  20. Panagiota Fatourou and Nikolaos D Kallimanis. Highly-efficient wait-free synchronization. Theory of Computing Systems, 55(3):475-520, 2014. Google Scholar
  21. Panagiota Fatourou, Elias Papavasileiou, and Eric Ruppert. Persistent non-blocking binary search trees supporting wait-free range queries. In Proc. 31st ACM Symposium on Parallelism in Algorithms and Architectures, pages 275-286, 2019. URL: https://doi.org/10.1145/3323165.3323197.
  22. Sérgio Miguel Fernandes and João Cachopo. Lock-free and scalable multi-version software transactional memory. In Proc. 16th ACM Symposium on Principles and Practice of Parallel Programming, pages 179-188, 2011. URL: https://doi.org/10.1145/1941553.1941579.
  23. Keir Fraser. Practical lock-freedom. Technical report, University of Cambridge, Computer Laboratory, 2004. Google Scholar
  24. Michael Greenwald. Two-handed emulation: how to build non-blocking implementations of complex data-structures using DCAS. In Proc. 21st ACM Symposium on Principles of Distributed Computing, pages 260-269, 2002. Google Scholar
  25. Rachid Guerraoui, Alex Kogan, Virendra J Marathe, and Igor Zablotchi. Efficient multi-word compare and swap. In 34th International Symposium on Distributed Computing. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020. Google Scholar
  26. Timothy L Harris. A pragmatic implementation of non-blocking linked-lists. In Proc. International Symposium on Distributed Computing, pages 300-314. Springer, 2001. Google Scholar
  27. Timothy L Harris, Keir Fraser, and Ian A Pratt. A practical multi-word compare-and-swap operation. In International Symposium on Distributed Computing, pages 265-279. Springer, 2002. Google Scholar
  28. Maurice Herlihy, Victor Luchangco, Paul Martin, and Mark Moir. Nonblocking memory management support for dynamic-sized data structures. ACM Trans. Comput. Syst., 23(2):146-196, 2005. URL: https://doi.org/10.1145/1062247.1062249.
  29. Idit Keidar and Dmitri Perelman. Multi-versioning in transactional memory. In Transactional Memory. Foundations, Algorithms, Tools, and Applications, volume 8913 of LNCS, pages 150-165. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-14720-8_7.
  30. Jaeho Kim, Ajit Mathew, Sanidhya Kashyap, Madhava Krishnan Ramanathan, and Changwoo Min. MV-RLU: Scaling read-log-update with multi-versioning. In Proc. 24th International Conference on Architectural Support for Programming Languages and Operating Systems, pages 779-792, 2019. URL: https://doi.org/10.1145/3297858.3304040.
  31. Priyanka Kumar, Sathya Peri, and K. Vidyasankar. A timestamp based multi-version STM algorithm. In Proc. Int. Conference on Distributed Computing and Networking, pages 212-226, 2014. Google Scholar
  32. 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 Proc. International Conference on Management of Data, page 1307–1318, 2016. URL: https://doi.org/10.1145/2882903.2903734.
  33. Li Lu and Michael L Scott. Generic multiversion STM. In Proc. International Symposium on Distributed Computing, pages 134-148. Springer, 2013. Google Scholar
  34. M.M. Michael. Hazard pointers: safe memory reclamation for lock-free objects. IEEE Transactions on Parallel and Distributed Systems, 15(6):491-504, 2004. URL: https://doi.org/10.1109/TPDS.2004.8.
  35. Jacob Nelson, Ahmed Hassan, and Roberto Palmieri. Poster: Bundled references: An abstraction for highly-concurrent linearizable range queries. In Proc. ACM Symposium on Principles and Practice of Parallel Programming, pages 448-450, 2021. Google Scholar
  36. Thomas Neumann, Tobias Mühlbauer, and Alfons Kemper. Fast serializable multi-version concurrency control for main-memory database systems. In Proc. ACM SIGMOD International Conference on Management of Data, pages 677-689, 2015. Google Scholar
  37. Ruslan Nikolaev and Binoy Ravindran. Snapshot-free, transparent, and robust memory reclamation for lock-free data structures. In Proceedings of the 42nd ACM International Conference on Programming Language Design and Implementation, pages 987-1002, 2021. Google Scholar
  38. Christos H Papadimitriou and Paris C Kanellakis. On concurrency control by multiple versions. ACM Transactions on Database Systems, 9(1):89-99, 1984. Google Scholar
  39. Dmitri Perelman, Anton Byshevsky, Oleg Litmanovich, and Idit Keidar. SMV: Selective multi-versioning STM. In Proc. International Symposium on Distributed Computing, pages 125-140, 2011. Google Scholar
  40. Dmitri Perelman, Rui Fan, and Idit Keidar. On maintaining multiple versions in STM. In Proc. ACM Symposium on Principles of Distributed Computing, pages 16-25, 2010. Google Scholar
  41. Pedro Ramalhete and Andreia Correia. Brief announcement: Hazard eras-non-blocking memory reclamation. In Proc. 29th ACM Symp. on Parallelism in Algorithms and Architectures, pages 367-369, 2017. URL: https://doi.org/10.1145/3087556.3087588.
  42. D. Reed. Naming and synchronization in a decentralized computer system. Technical Report LCS/TR-205, EECS Dept., MIT, 1978. Google Scholar
  43. Niloufar Shafiei. Non-blocking doubly-linked lists with good amortized complexity. In Proc. 19th Int. Conference on Principles of Distributed Systems, volume 46 of LIPIcs, pages 35:1-35:17, 2015. Google Scholar
  44. Julian Shun, Yan Gu, Guy E. Blelloch, Jeremy T. Fineman, and Phillip B. Gibbons. Sequential random permutation, list contraction and tree contraction are highly parallel. In Proc. 26th ACM-SIAM Symposium on Discrete Algorithms, pages 431-448, 2015. Google Scholar
  45. Ajay Singh, Trevor Brown, and Ali Mashtizadeh. NBR: Neutralization based reclamation. In Proc. 26th ACM Symp. on Principles and Practice of Parallel Programming, pages 175-190, 2021. URL: https://doi.org/10.1145/3437801.3441625.
  46. H. Sundell. Wait-free reference counting and memory management. In Proc. 19th IEEE Symposium Parallel and Distributed Processing, 2005. URL: https://doi.org/10.1109/IPDPS.2005.451.
  47. Håkan Sundell and Philippas Tsigas. Lock-free deques and doubly linked lists. J. Parallel and Distributed Computing, 68(7):1008-1020, 2008. Google Scholar
  48. John D. Valois. Lock-free linked lists using compare-and-swap. In Proc. 14th ACM Symposium on Principles of Distributed Computing, pages 214-222, 1995. Google Scholar
  49. 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 Proc. ACM Symposium on Principles and Practice of Parallel Programming, pages 31-46, 2021. A full version is available from URL: https://arxiv.org/abs/2007.02372.
  50. Haosen Wen, Joseph Izraelevitz, Wentao Cai, H. Alan Beadle, and Michael L. Scott. Interval-based memory reclamation. In Proc. 23rd ACM Symp. on Principles and Practice of Parallel Programming, pages 1-13, 2018. URL: https://doi.org/10.1145/3178487.3178488.
  51. Yingjun Wu, Joy Arulraj, Jiexi Lin, Ran Xian, and Andrew Pavlo. An empirical evaluation of in-memory multi-version concurrency control. Proc. of the VLDB Endowment, 10(7):781-792, 2017. 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