Document Open Access Logo

Detectable Sequential Specifications for Recoverable Shared Objects

Authors Nan Li, Wojciech Golab

PDF
Thumbnail PDF

File

LIPIcs.DISC.2021.29.pdf
  • Filesize: 0.92 MB
  • 19 pages

Document Identifiers

Author Details

Nan Li
  • Department of Electrical and Computer Engineering, University of Waterloo, Canada
Wojciech Golab
  • Department of Electrical and Computer Engineering, University of Waterloo, Canada

Funding

  • Golab, Wojciech: Author supported by an Ontario Early Researcher Award, a Google Faculty Research Award, as well as the Natural Sciences and Engineering Research Council (NSERC) of Canada.

Cite AsGet BibTex

Nan Li and Wojciech Golab. Detectable Sequential Specifications for Recoverable Shared Objects. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 29:1-29:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.DISC.2021.29

Abstract

The recent commercial release of persistent main memory by Intel has sparked intense interest in recoverable concurrent objects. Such objects maintain state in persistent memory, and can be recovered directly following a system-wide crash failure, as opposed to being painstakingly rebuilt using recovery state saved in slower secondary storage. Specifying and implementing recoverable objects is technically challenging on current generation hardware precisely because the top layers of the memory hierarchy (CPU registers and cache) remain volatile, which causes application threads to lose critical execution state during a failure. For example, a thread that completes an operation on a shared object and then crashes may have difficulty determining whether this operation took effect, and if so, what response it returned. Friedman, Herlihy, Marathe, and Petrank (DISC'17) recently proposed that this difficulty can be alleviated by making the recoverable objects detectable, meaning that during recovery, they can resolve the status of an operation that was interrupted by a failure. In this paper, we formalize this important concept using a detectable sequential specification (DSS), which augments an object’s interface with auxiliary methods that threads use to first declare their need for detectability, and then perform detection if needed after a failure. Our contribution is closely related to the nesting-safe recoverable linearizability (NRL) framework of Attiya, Ben-Baruch, and Hendler (PODC'18), which follows an orthogonal approach based on ordinary sequential specifications combined with a novel correctness condition. Compared to NRL, our DSS-based approach is more portable across different models of distributed computation, compatible with several existing linearizability-like correctness conditions, less reliant on assumptions regarding the system, and more flexible in the sense that it allows applications to request detectability on demand. On the other hand, application code assumes full responsibility for nesting DSS-based objects. As a proof of concept, we demonstrate the DSS in action by presenting a detectable recoverable lock-free queue algorithm and evaluating its performance on a multiprocessor equipped with Intel Optane persistent memory.

Subject Classification

ACM Subject Classification
  • Theory of computation → Shared memory algorithms
  • Computer systems organization → Reliability
Keywords
  • persistent memory
  • concurrency
  • fault tolerance
  • correctness
  • detectability

Metrics

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

References

  1. Marcos K. Aguilera, Naama Ben-David, Irina Calciu, Rachid Guerraoui, Erez Petrank, and Sam Toueg. Passing messages while sharing memory. In Proc. of the 37th ACM Symposium on Principles of Distributed Computing (PODC), pages 51-60, 2018. Google Scholar
  2. Marcos K. Aguilera and S. Frølund. Strict linearizability and the power of aborting. Technical Report HPL-2003-241, Hewlett-Packard Labs, 2003. Google Scholar
  3. Joy Arulraj, Justin J. Levandoski, Umar Farooq Minhas, and Per-Åke Larson. BzTree: A high-performance latch-free range index for non-volatile memory. Proc. VLDB Endow., 11(5):553-565, 2018. Google Scholar
  4. Hagit Attiya, Ohad Ben-Baruch, Panagiota Fatourou, Danny Hendler, and Eleftherios Kosmas. Tracking in order to recover: Recoverable lock-free data structures. CoRR, abs/1905.13600, 2019. URL: http://arxiv.org/abs/1905.13600.
  5. Hagit Attiya, Ohad Ben-Baruch, and Danny Hendler. Nesting-safe recoverable linearizability: Modular constructions for non-volatile memory. In Proc. of the 37th ACM Symposium on Principles of Distributed Computing (PODC), pages 7-16, 2018. Google Scholar
  6. Ohad Ben-Baruch, Danny Hendler, and Matan Rusanovsky. Upper and lower bounds on the space complexity of detectable objects. In Proc. of the 39th ACM Symposium on Principles of Distributed Computing (PODC), pages 11-20, 2020. Google Scholar
  7. Naama Ben-David, Guy E. Blelloch, Michal Friedman, and Yuanhao Wei. Delay-free concurrency on faulty persistent memory. In Proc. of the 31st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 253-264, 2019. Google Scholar
  8. Ryan Berryhill, Wojciech Golab, and Mahesh Tripunitara. Robust shared objects for non-volatile main memory. In Proc. of the 19th International Conference on Principles of Distributed Systems (OPODIS), pages 20:1-20:17, 2016. Google Scholar
  9. Trevor Brown and Hillel Avni. Phytm: Persistent hybrid transactional memory. Proc. VLDB Endow., 10(4):409-420, 2016. Google Scholar
  10. 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 Proc. of the 16th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), pages 105-118, 2011. Google Scholar
  11. Nachshon Cohen, Rachid Guerraoui, and Igor Zablotchi. The inherent cost of remembering consistently. In Proc. of the 30th on Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 259-269, 2018. Google Scholar
  12. Jeremy Condit, Edmund B. Nightingale, Christopher Frost, Engin Ipek, Benjamin C. Lee, Doug Burger, and Derrick Coetzee. Better I/O through byte-addressable, persistent memory. In Proc. of the 22nd ACM Symposium on Operating Systems Principles (SOSP), pages 133-146, 2009. Google Scholar
  13. Intel Corporation. Persistent memory faq, 2020. [last accessed 2/17/2021]. URL: https://software.intel.com/content/www/us/en/develop/articles/persistent-memory-faq.html.
  14. Andreia Correia, Pascal Felber, and Pedro Ramalhete. Romulus: Efficient algorithms for persistent transactional memory. In Proc. of the 30th on Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 271-282, 2018. Google Scholar
  15. Andreia Correia, Pascal Felber, and Pedro Ramalhete. Persistent memory and the rise of universal constructions. In Proc. of the 15th EuroSys Conference, pages 5:1-5:15, 2020. Google Scholar
  16. Tudor David, Aleksandar Dragojevic, Rachid Guerraoui, and Igor Zablotchi. Log-free concurrent data structures. In Proc. of the USENIX Annual Technical Conference (USENIX ATC), pages 373-386, 2018. Google Scholar
  17. Keir Fraser. Practical Lock-Freedom. PhD thesis, University of Cambridge, 2004. Computer Laboratory. Google Scholar
  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 Proc. of the 41st ACM SIGPLAN International Conference on Programming Language Design and Implementation (PLDI), pages 377-392, 2020. Google Scholar
  19. Michal Friedman, Maurice Herlihy, Virendra J. Marathe, and Erez Petrank. Brief announcement: A persistent lock-free queue for non-volatile memory. In Proc. of the 31st International Symposium on Distributed Computing (DISC), volume 91, pages 50:1-50:4, 2017. Google Scholar
  20. Michal Friedman, Maurice Herlihy, Virendra J. Marathe, and Erez Petrank. A persistent lock-free queue for non-volatile memory. In Proc. of the 23rd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), pages 28-40, 2018. Google Scholar
  21. Wojciech Golab. The recoverable consensus hierarchy. In Proc. of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 281-291, 2020. Google Scholar
  22. Wojciech Golab, Lisa Higham, and Philipp Woelfel. Linearizable implementations do not suffice for randomized distributed computation. In In Proc. of the 43rd ACM Symposium on Theory of Computing (STOC), pages 373-382, 2011. Google Scholar
  23. Wojciech Golab and Aditya Ramaraju. Recoverable mutual exclusion. In Proc. of the 35th ACM Symposium on Principles of Distributed Computing (PODC), pages 65-74, 2016. Google Scholar
  24. Rachid Guerraoui and Ron R. Levy. Robust emulations of shared memory in a crash-recovery model. In Proc. of the 24th International Conference on Distributed Computing Systems (ICDCS), pages 400-407, 2004. Google Scholar
  25. John V. Guttag, James J. Horning, and Jeannette M. Wing. The larch family of specification languages. IEEE Software, 2(5):24-36, 1985. Google Scholar
  26. M. Herlihy and J. M. Wing. Linearizability: A correctness condition for concurrent objects. ACM Transactions on Programming Languages and Systems, 12(3):463-492, 1990. Google Scholar
  27. Maurice Herlihy. Wait-free synchronization. ACM Transactions on Programming Languages and Systems, 13(1):124-149, 1991. Google Scholar
  28. Maurice Herlihy and J. Eliot B. Moss. Transactional memory: Architectural support for lock-free data structures. In Proc. of the 20th Annual International Symposium on Computer Architecture (ISCA), pages 289-300, 1993. Google Scholar
  29. Joseph Izraelevitz, Terence Kelly, and Aasheesh Kolli. Failure-atomic persistent memory updates via JUSTDO logging. In Proc. of the 21s International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), pages 427-442, 2016. Google Scholar
  30. Joseph Izraelevitz, Hammurabi Mendes, and Michael L. Scott. Linearizability of persistent memory objects under a full-system-crash failure model. In Proc. of the 30th International Symposium on Distributed Computing (DISC), pages 313-327, 2016. Google Scholar
  31. Wook-Hee Kim, Jinwoong Kim, Woongki Baek, Beomseok Nam, and Youjip Won. Nvwal: Exploiting nvram in write-ahead logging. ACM SIGPLAN Notices, 51(4):385-398, 2016. Google Scholar
  32. L. Lamport. On interprocess communication, Part I: Basic formalism and Part II: Algorithms. Distributed Computing, 1(2):77-101, June 1986. Google Scholar
  33. Se Kwon Lee, Jayashree Mohan, Sanidhya Kashyap, Taesoo Kim, and Vijay Chidambaram. Recipe: converting concurrent DRAM indexes to persistent-memory indexes. In Proc. of the 27th ACM Symposium on Operating Systems Principles (SOSP), pages 462-477, 2019. Google Scholar
  34. Lucas Lersch, Xiangpeng Hao, Ismail Oukid, Tianzheng Wang, and Thomas Willhalm. Evaluating persistent memory range indexes. Proc. VLDB Endow., 13(4):574-587, 2019. Google Scholar
  35. Mengxing Liu, Mingxing Zhang, Kang Chen, Xuehai Qian, Yongwei Wu, Weimin Zheng, and Jinglei Ren. Dudetm: Building durable transactions with decoupling for persistent memory. ACM SIGPLAN Notices, 52(4):329-343, 2017. Google Scholar
  36. Maged M. Michael and Michael L. Scott. Simple, fast, and practical non-blocking and blocking concurrent queue algorithms. In Proc. of the 15th ACM Symposium on Principles of Distributed Computing (PODC), pages 267-275, 1996. Google Scholar
  37. Faisal Nawab, Dhruva R. Chakrabarti, Terence Kelly, and Charles B. Morrey III. Procrastination beats prevention: Timely sufficient persistence for efficient crash resilience. In Proc. of the 18th International Conference on Extending Database Technology (EDBT), pages 689-694, 2015. Google Scholar
  38. Faisal Nawab, Joseph Izraelevitz, Terence Kelly, Charles B. Morrey III, Dhruva R. Chakrabarti, and Michael L. Scott. Dalí: A periodically persistent hash map. In Proc. of the 31st International Symposium on Distributed Computing (DISC), pages 37:1-37:16, 2017. Google Scholar
  39. 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 Proc. of the 2016 International Conference on Management of Data (SIGMOD), pages 371-386. ACM, 2016. Google Scholar
  40. Steven Pelley, Peter M. Chen, and Thomas F. Wenisch. Memory persistency: Semantics for byte-addressable nonvolatile memory technologies. IEEE Micro, 35(3):125-131, 2015. Google Scholar
  41. Andy Rudoff. Persistent memory programming. login Usenix Mag., 42(2), 2017. Google Scholar
  42. Andy Rudoff and the Intel PMDK Team. Persistent memory development kit, 2020. [last accessed 2/11/2021]. URL: https://pmem.io/pmdk/.
  43. Shivaram Venkataraman, Niraj Tolia, Parthasarathy Ranganathan, and Roy H Campbell. Consistent and durable data structures for non-volatile byte-addressable memory. In FAST, volume 11, pages 61-75, 2011. Google Scholar
  44. Haris Volos, Andres Jaan Tack, and Michael M. Swift. Mnemosyne: lightweight persistent memory. In Proc. of the 16th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), pages 91-104, 2011. Google Scholar
  45. Tianzheng Wang, Justin J. Levandoski, and Per-Åke Larson. Easy lock-free indexing in non-volatile memory. In Proc. of the 34th IEEE International Conference on Data Engineering (ICDE), pages 461-472, 2018. Google Scholar
  46. Jun Yang, Qingsong Wei, Chundong Wang, Cheng Chen, Khai Leong Yong, and Bingsheng He. Nv-tree: A consistent and workload-adaptive tree structure for non-volatile memory. IEEE Trans. Computers, 65(7):2169-2183, 2016. 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