Document Open Access Logo

Fast Nonblocking Persistence for Concurrent Data Structures

Authors Wentao Cai, Haosen Wen, Vladimir Maksimovski, Mingzhe Du, Rafaello Sanna, Shreif Abdallah, Michael L. Scott

PDF
Thumbnail PDF

File

LIPIcs.DISC.2021.14.pdf
  • Filesize: 1.01 MB
  • 20 pages

Document Identifiers

Author Details

Wentao Cai
  • University of Rochester, NY, USA
Haosen Wen
  • University of Rochester, NY, USA
Vladimir Maksimovski
  • University of Rochester, NY, USA
Mingzhe Du
  • University of Rochester, NY, USA
Rafaello Sanna
  • University of Rochester, NY, USA
Shreif Abdallah
  • University of Rochester, NY, USA
Michael L. Scott
  • University of Rochester, NY, USA

Funding

This work was supported in part by NSF grants CCF-1717712, CNS-1900803, CNS-1955498, and by a Google Faculty Research award.

Cite As Get BibTex

Wentao Cai, Haosen Wen, Vladimir Maksimovski, Mingzhe Du, Rafaello Sanna, Shreif Abdallah, and Michael L. Scott. Fast Nonblocking Persistence for Concurrent Data Structures. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 14:1-14:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.DISC.2021.14

Abstract

We present a fully lock-free variant of our recent Montage system for persistent data structures. The variant, nbMontage, adds persistence to almost any nonblocking concurrent structure without introducing significant overhead or blocking of any kind. Like its predecessor, nbMontage is buffered durably linearizable: it guarantees that the state recovered in the wake of a crash will represent a consistent prefix of pre-crash execution. Unlike its predecessor, nbMontage ensures wait-free progress of the persistence frontier, thereby bounding the number of recent updates that may be lost on a crash, and allowing a thread to force an update of the frontier (i.e., to perform a sync operation) without the risk of blocking. As an extra benefit, the helping mechanism employed by our wait-free sync significantly reduces its latency.
Performance results for nonblocking queues, skip lists, trees, and hash tables rival custom data structures in the literature - dramatically faster than achieved with prior general-purpose systems, and generally within 50% of equivalent non-persistent structures placed in DRAM.

Subject Classification

ACM Subject Classification
  • Computing methodologies → Concurrent algorithms
  • Computer systems organization → Reliability
  • Theory of computation → Parallel computing models
Keywords
  • Persistent Memory
  • Nonblocking Progress
  • Buffered Durable Linearizability

Metrics

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

Related Versions

Supplementary Materials

References

  1. H. Alan Beadle, Wentao Cai, Haosen Wen, and Michael L. Scott. Nonblocking persistent software transactional memory. In 27th Intl. Conf. on High Performance Computing, Data, and Analytics (HiPC), pages 283-293, 2020. URL: https://doi.org/10.1109/HiPC50609.2020.00042.
  2. Wentao Cai, Haosen Wen, H. Alan Beadle, Chris Kjellqvist, Mohammad Hedayati, and Michael L. Scott. Understanding and optimizing persistent memory allocation. In 19th Intl. Symp. on Memory Management (ISMM), 2020. URL: https://doi.org/10.1145/3381898.3397212.
  3. Hokeun Cha, Moohyeon Nam, Kibeom Jin, Jiwon Seo, and Beomseok Nam. B3-tree: Byte-addressable binary B-tree for persistent memory. ACM Trans. on Storage, 16(3):17:1-17:27, July 2020. URL: https://doi.org/10.1145/3394025.
  4. Dhruva R. Chakrabarti, Hans-J. Boehm, and Kumud Bhandari. Atlas: Leveraging locks for non-volatile memory consistency. In ACM Conf. on Object Oriented Programming Systems Languages & Applications (OOPSLA), pages 433-452, Portland, OR, October 2014. URL: https://doi.org/10.1145/2660193.2660224.
  5. Andreas Chatzistergiou, Marcelo Cintra, and Stratis D. Viglas. REWIND: Recovery write-ahead system for in-memory non-volatile data-structures. Proc. of the VLDB Endowment, 8(5):497-508, 2015. URL: https://doi.org/10.14778/2735479.2735483.
  6. Shimin Chen and Qin Jin. Persistent B+-trees in non-volatile main memory. Proc. of the VLDB Endowment, 8(7):786-797, February 2015. URL: https://doi.org/10.14778/2752939.2752947.
  7. Youmin Chen, Youyou Lu, Kedong Fang, Qing Wang, and Jiwu Shu. uTree: A persistent B+-tree with low tail latency. Proc. of the VLDB Endowment, 13(11):2634-2648, August 2020. URL: https://doi.org/10.14778/3407790.3407850.
  8. Zhangyu Chen, Yu Huang, Bo Ding, and Pengfei Zuo. Lock-free concurrent level hashing for persistent memory. In Usenix Annual Technical Conf. (ATC), pages 799-812, July 2020. URL: https://www.usenix.org/conference/atc20/presentation/chen.
  9. Joel Coburn, Adrian M. Caulfield, Ameen Akel, Laura M. Grupp, Rajesh K. Gupta, Ranjit Jhala, and Steven Swanson. NV-Heaps: Making persistent objects fast and safe with next-generation, non-volatile memories. In 16th Intl. Conf. on Architectural Support for Programming Languages and Operating Systems (ASPLOS), pages 105-118, Newport Beach, CA, 2011. URL: https://doi.org/10.1145/1950365.1950380.
  10. Nachshon Cohen, David T. Aksun, Hillel Avni, and James R. Larus. Fine-grain checkpointing with in-cache-line logging. In 24th Intl. Conf. on Architectural Support for Programming Languages and Operating Systems (ASPLOS), pages 441-454, Providence, RI, USA, 2019. URL: https://doi.org/10.1145/3297858.3304046.
  11. Nachshon Cohen, David T. Aksun, and James R. Larus. Object-oriented recovery for non-volatile memory. Proc. of the ACM on Programming Languages, 2(OOPSLA):153:1-153:22, October 2018. URL: https://doi.org/10.1145/3276523.
  12. Nachshon Cohen, Rachid Guerraoui, and Igor Zablotchi. The inherent cost of remembering consistently. In 30th ACM Symp. on Parallelism in Algorithms and Architectures (SPAA), page 259–269, Vienna, Austria, 2018. URL: https://doi.org/10.1145/3210377.3210400.
  13. Andreia Correia, Pascal Felber, and Pedro Ramalhete. Romulus: Efficient algorithms for persistent transactional memory. In 30th ACM Symp. on Parallel Algorithms and Architectures (SPAA), pages 271-282, Vienna, Austria, July 2018. URL: https://doi.org/10.1145/3210377.3210392.
  14. Tudor David, Aleksandar Dragojević, Rachid Guerraoui, and Igor Zablotchi. Log-free concurrent data structures. In Usenix Annual Technical Conf. (ATC), pages 373-386, Boston, MA, 2018. URL: https://www.usenix.org/conference/atc18/presentation/david.
  15. Ian Dick, Alan Fekete, and Vincent Gramoli. A skip list for multicore. Concurrency and Computation: Practice and Experience, 29(4), May 2016. Google Scholar
  16. Jason Evans. A scalable concurrent malloc (3) implementation for FreeBSD. In BSDCan Conf., Ottawa, ON, Canada, May 2006. URL: https://papers.freebsd.org/2006/bsdcan/evans-jemalloc.files/evans-jemalloc-paper.pdf.
  17. Keir Fraser. Practical Lock-Freedom. PhD thesis, King’s College, Univ. of Cambridge, 2003. Published as Univ. of Cambridge Computer Laboratory technical report #579, February 2004. URL: https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-579.pdf.
  18. Michal Friedman, Naama Ben-David, Yuanhao Wei, Guy E. Blelloch, and Erez Petrank. NVTraverse: In NVRAM data structures, the destination is more important than the journey. In 41st ACM Conf. on Programming Language Design and Implementation (PLDI), pages 377-392, 2020. URL: https://doi.org/10.1145/3385412.3386031.
  19. Michal Friedman, Maurice Herlihy, Virendra Marathe, and Erez Petrank. A persistent lock-free queue for non-volatile memory. In 23rd ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPoPP), pages 28-40, Vienna, Austria, 2018. URL: https://doi.org/10.1145/3178487.3178490.
  20. Kaan Genç, Michael D. Bond, and Guoqing Harry Xu. Crafty: Efficient, HTM-compatible persistent transactions. In 41st ACM Conf. on Programming Language Design and Implementation (PLDI), pages 59-74, June 2020. URL: https://doi.org/10.1145/3385412.3385991.
  21. Ellis R. Giles, Kshitij Doshi, and Peter Varman. SoftWrAP: A lightweight framework for transactional support of storage class memory. In 31st Symp. on Mass Storage Systems and Technologies (MSST), pages 1-14, Santa Clara, CA, May-June 2015. URL: https://doi.org/10.1109/MSST.2015.7208276.
  22. Jinyu Gu, Qianqian Yu, Xiayang Wang, Zhaoguo Wang, Binyu Zang, Haibing Guan, and Haibo Chen. Pisces: A scalable and efficient persistent transactional memory. In Usenix Annual Technical Conf. (ATC), pages 913-928, Renton, WA, July 2019. URL: https://www.usenix.org/conference/atc19/presentation/gu.
  23. Timothy L. Harris, Keir Fraser, and Ian A. Pratt. A practical multi-word compare-and-swap operation. In 16th Intl. Symp. on Distributed Computing (DISC), pages 265-279, Toulouse, France, October 2002. URL: https://doi.org/10.1007/3-540-36108-1_18.
  24. Maurice P. Herlihy and Jeannette M. Wing. Linearizability: A correctness condition for concurrent objects. ACM Trans. on Programming Languages and Systems, 12(3):463-492, July 1990. URL: https://doi.org/10.1145/78969.78972.
  25. Terry Ching-Hsiang Hsu, Helge Brügner, Indrajit Roy, Kimberly Keeton, and Patrick Eugster. NVthreads: Practical persistence for multi-threaded applications. In 12th European Conf. on Computer Systems (EuroSys), pages 468-482, Belgrade, Serbia, 2017. URL: https://doi.org/10.1145/3064176.3064204.
  26. Deukyeon Hwang, Wook-Hee Kim, Youjip Won, and Beomseok Nam. Endurable transient inconsistency in byte-addressable persistent B+-tree. In 16th Usenix Conf. on File and Storage Technologies (FAST), pages 187-200, Oakland, CA, February 2018. URL: https://www.usenix.org/conference/fast18/presentation/hwang.
  27. Joseph Izraelevitz, Terence Kelly, and Aasheesh Kolli. Failure-atomic persistent memory updates via JUSTDO logging. In 21st Intl. Conf. on Architectural Support for Programming Languages and Operating Systems (ASPLOS), pages 427-442, Atlanta, GA, 2016. URL: https://doi.org/10.1145/2872362.2872410.
  28. Joseph Izraelevitz, Hammurabi Mendes, and Michael L. Scott. Linearizability of persistent memory objects under a full-system-crash failure model. In Intl. Symp. on Distributed Computing (DISC), pages 313-327, Paris, France, September 2016. URL: https://doi.org/10.1007/978-3-662-53426-7_23.
  29. Wook-Hee Kim, Jihye Seo, Jinwoong Kim, and Beomseok Nam. clfB-tree: Cacheline friendly persistent B-tree for NVRAM. ACM Trans. on Storage, 14(1):5:1-5:17, February 2018. URL: https://doi.org/10.1145/3129263.
  30. Se Kwon Lee, K. Hyun Lim, Hyunsub Song, Beomseok Nam, and Sam H. Noh. WORT: Write optimal radix tree for persistent memory storage systems. In 15th Usenix Conf. on File and Storage Technologies (FAST), pages 257-270, Santa clara, CA, February 2017. URL: https://www.usenix.org/conference/fast17/technical-sessions/presentation/lee-se-kwon.
  31. Mengxing Liu, Jiankai Xing, Kang Chen, and Yongwei Wu. Building scalable NVM-based B+tree with HTM. In 48th Intl. Conf. on Parallel Processing (ICPP), pages 101:1-101:10, Kyoto, Japan, August 2019. URL: https://doi.org/10.1145/3337821.3337827.
  32. Mengxing Liu, Mingxing Zhang, Kang Chen, Xuehai Qian, Yongwei Wu, Weimin Zheng, and Jinglei Ren. DudeTM: Building durable transactions with decoupling for persistent memory. In 22nd Intl. Conf. on Architectural Support for Programming Languages and Operating Systems (ASPLOS), pages 329-343, Xi'an, China, April 2017. URL: https://doi.org/10.1145/3037697.3037714.
  33. Qingrui Liu, Joseph Izraelevitz, Se Kwon Lee, Michael L Scott, Sam H Noh, and Changhee Jung. iDO: Compiler-directed failure atomicity for nonvolatile memory. In 2018 51st Intl. Symp. on Microarchitecture (MICRO), pages 258-270, Fukuoka, Japan, 2018. URL: https://doi.org/10.1109/MICRO.2018.00029.
  34. Yujie Liu, Victor Luchangco, and Michael Spear. Mindicators: A scalable approach to quiescence. In IEEE 33rd Intl. Conf. on Distributed Computing Systems (ICDCS), pages 206-215, Philadelphia, PA, 2013. URL: https://doi.org/10.1109/ICDCS.2013.39.
  35. Pratyush Mahapatra, Mark D Hill, and Michael M Swift. Don't persist all: Efficient persistent data structures, 2019. arXiv preprint. URL: http://arxiv.org/abs/1905.13011.
  36. Yandong Mao, Eddie Kohler, and Robert Tappan Morris. Cache craftiness for fast multicore key-value storage. In 7th European Conf. on Computer Systems (EuroSys), pages 183-196, Bern, Switzerland, April 2012. URL: https://doi.org/10.1145/2168836.2168855.
  37. Amirsaman Memaripour, Joseph Izraelevitz, and Steven Swanson. Pronto: Easy and fast persistence for volatile data structures. In 25th Intl. Conf. on Architectural Support for Programming Languages and Operating Systems (ASPLOS), pages 789-806, March 2020. URL: https://doi.org/10.1145/3373376.3378456.
  38. Amirsaman Memaripour and Steven Swanson. Breeze: User-level access to non-volatile main memories for legacy software. In 36th Intl. Conf. on Computer Design (ICCD), pages 413-422, Hartford, CT, October 2018. URL: https://doi.org/10.1109/ICCD.2018.00069.
  39. Maged M. Michael. High performance dynamic lock-free hash tables and list-based sets. In 14th ACM Symp. on Parallelism in Algorithms and Architectures (SPAA), pages 73-82, Winnipeg, MB, Canada, 2002. URL: https://doi.org/10.1145/564870.564881.
  40. Maged M. Michael. Hazard pointers: Safe memory reclamation for lock-free objects. IEEE Trans. on Parallel and Distributed Systems, 15(6):491-504, June 2004. URL: https://doi.org/10.1109/TPDS.2004.8.
  41. Maged M. Michael and Michael L. Scott. Simple, fast, and practical non-blocking and blocking concurrent queue algorithms. In 15th ACM Symp. on Principles of Distributed Computing (PODC), pages 267-275, Philadelphia, PA, 1996. URL: https://doi.org/10.1145/248052.248106.
  42. Aravind Natarajan and Neeraj Mittal. Fast concurrent lock-free binary search trees. In 19th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPoPP), pages 317-328, Orlando, FL, USA, February 2014. URL: https://doi.org/10.1145/2555243.2555256.
  43. Faisal Nawab, Joseph Izraelevitz, Terence Kelly, Charles B. Morrey III, Dhruva R. Chakrabarti, and Michael L. Scott. Dalí: A periodically persistent hash map. In Intl. Symp. on Distributed Computing (DISC), pages 37:1-37:16, Vienna, Austria, 2017. URL: https://doi.org/10.4230/LIPIcs.DISC.2017.37.
  44. Ismail Oukid, Johan Lasperas, Anisoara Nica, Thomas Willhalm, and Wolfgang Lehner. FPTree: A hybrid SCM-DRAM persistent and concurrent B-tree for storage class memory. In Intl Conf on Management of Data (SIGMOD), pages 371-386, San Francisco, CA, 2016. URL: https://doi.org/10.1145/2882903.2915251.
  45. Matej Pavlovic, Alex Kogan, Virendra J Marathe, and Tim Harris. Brief announcement: Persistent multi-word compare-and-swap. In ACM Symp. on Principles of Distributed Computing (PODC), pages 37-39, Egham, United Kingdom, 2018. URL: https://doi.org/10.1145/3212734.3212783.
  46. Pedro Ramalhete, Andreia Correia, Pascal Felber, and Nachshon Cohen. OneFile: A wait-free persistent transactional memory. In 49th IEEE/IFIP Intl. Conf. on Dependable Systems and Networks (DSN), pages 151-163, Portland, OR, June 2019. URL: https://doi.org/10.1109/DSN.2019.00028.
  47. David Schwalb, Markus Dreseler, Matthias Uflacker, and Hasso Plattner. NVC-hashmap: A persistent and concurrent hashmap for non-volatile memories. In 3rd VLDB Workshop on In-Memory Data Management and Analytics (IMDM), pages 4:1-4:8, Kohala, HI, 2015. URL: https://doi.org/10.1145/2803140.2803144.
  48. Ori Shalev and Nir Shavit. Split-ordered lists: Lock-free extensible hash tables. Journal of the ACM, pages 379-405, May 2006. URL: https://doi.org/10.1145/1147954.1147958.
  49. Usharani Upadhyayula and Andy M. Rudoff. Introduction to Programming with Persistent Memory from Intel. https://software.intel.com/en-us/articles/introduction-to-programming-with-persistent-memory-from-intel, August 2017.
  50. Shivaram Venkataraman, Niraj Tolia, Parthasarathy Ranganathan, and Roy H. Campbell. Consistent and durable data structures for non-volatile byte-addressable memory. In 9th Usenix Conf. on File and Storage Technologies (FAST), pages 61-75, San Jose, CA, 2011. URL: http://www.usenix.org/events/fast11/tech/techAbstracts.html#Venkataraman.
  51. Haris Volos, Andres Jaan Tack, and Michael M. Swift. Mnemosyne: Lightweight persistent memory. In 16th Intl. Conf. on Architectural Support for Programming Languages and Operating Systems (ASPLOS), pages 91-104, Newport Beach, CA, 2011. URL: https://doi.org/10.1145/1950365.1950379.
  52. Chundong Wang, Qingsong Wei, Lingkun Wu, Sibo Wang, Cheng Chen, Xiaokui Xiao, Jun Yang, Mingdi Xue, and Yechao Yang. Persisting RB-Tree into NVM in a consistency perspective. ACM Trans. on Storage, 14(1):6:1-6:27, February 2018. URL: https://doi.org/10.1145/3177915.
  53. Haosen Wen, Wentao Cai, Mingzhe Du, Louis Jenkins, Benjamin Valpey, and Michael L. Scott. A fast, general system for buffered persistent data structures. In 50th Intl. Conf. on Parallel Processing (ICPP), August 2021. URL: https://oaciss.uoregon.edu/icpp21/views/includes/files/pap118s4-file2.pdf.
  54. Jun Yang, Qingsong Wei, Cheng Chen, Chundong Wang, Khai Leong Yong, and Bingsheng He. NV-Tree: Reducing consistency cost for NVM-based single level systems. In 13th Usenix Conf. on File and Storage Technologies (FAST), pages 167-181, Santa Clara, CA, February 2015. URL: https://www.usenix.org/conference/fast15/technical-sessions/presentation/yang.
  55. Yoav Zuriel, Michal Friedman, Gali Sheffi, Nachshon Cohen, and Erez Petrank. Efficient lock-free durable sets. Proc. of the ACM on Programming Languages, 3(OOPSLA):128:1-128:26, October 2019. URL: https://doi.org/10.1145/3360554.
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