research-article

Detectable recovery of lock-free data structures

Authors:

Ohad Ben-Baruch,

Panagiota Fatourou,

Eleftherios KosmasAuthors Info & Claims

PPoPP '22: Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming

Pages 262 - 277

https://doi.org/10.1145/3503221.3508444

Published: 28 March 2022 Publication History

Abstract

This paper presents a generic approach for deriving detectably recoverable implementations of many widely-used concurrent data structures. Such implementations are appealing for emerging systems featuring byte-addressable non-volatile main memory (NVMM), whose persistence allows to efficiently resurrect failed threads after crashes. Detectable recovery ensures that after a crash, every executed operation is able to recover and return a correct response, and that the state of the data structure is not corrupted.

Our approach, called Tracking, amends descriptor objects used in existing lock-free helping schemes with additional fields that track an operation's progress towards completion and persists these fields in order to ensure detectable recovery. Tracking avoids full-fledged logging and tracks the progress of concurrent operations in a per-thread manner, thus reducing the cost of ensuring detectable recovery.

We have applied Tracking to derive detectably recoverable implementations of a linked list, a binary search tree, and an exchanger. Our experimental analysis introduces a new way of analyzing the cost of persistence instructions, not by simply counting them but by separating them into categories based on the impact they have on the performance. The analysis reveals that understanding the actual persistence cost of an algorithm in machines with real NVMM, is more complicated than previously thought, and requires a thorough evaluation, since the impact of different persistence instructions on performance may greatly vary. We consider this analysis to be one of the major contributions of the paper.

References

[1]

Hagit Attiya, Ohad Ben-Baruch, Panagiota Fatourou, Danny Hendler, and Eleftherios Kosmas. 2020. Tracking in Order to Recover - Detectable Recovery of Lock-Free Data Structures (SPAA '20). Association for Computing Machinery, New York, NY, USA, 503--505.

Digital Library

[2]

Hagit Attiya, Ohad Ben-Baruch, Panagiota Fatourou, Danny Hendler, and Eleftherios Kosmas. 2022. Tracking in Order to Recover: Detectable Recovery of Lock-Free Data Structures. arXiv:1905.13600 [cs.DC]

[3]

Hagit Attiya, Ohad Ben-Baruch, and Danny Hendler. 2018. Nesting-Safe Recoverable Linearizability: Modular Constructions for Non-Volatile Memory. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC 2018, Egham, United Kingdom, July 23--27, 2018. 7--16.

Digital Library

[4]

Greg Barnes. 1993. A Method for Implementing Lock-Free Shared-Data Structures. In Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA '93, Velen, Germany, June 30 - July 2, 1993. 261--270.

Digital Library

[5]

Ohad Ben-Baruch, Danny Hendler, and Matan Rusanovsky. 2020. Upper and Lower Bounds on the Space Complexity of Detectable Objects. In Proceedings of the 39th Symposium on Principles of Distributed Computing (Virtual Event, Italy) (PODC '20). Association for Computing Machinery, New York, NY, USA, 11--20.

Digital Library

[6]

Naama Ben-David, Guy E Blelloch, Michal Friedman, and Yuanhao Wei. 2019. Delay-free concurrency on faulty persistent memory. In The 31st ACM Symposium on Parallelism in Algorithms and Architectures. 253--264.

Digital Library

[7]

Kumud Bhandari, Dhruva R. Chakrabarti, and Hans-J. Boehm. 2016. Makalu: Fast Recoverable Allocation of Non-volatile Memory. SIGPLAN Not. 51, 10 (Oct. 2016), 677--694.

Digital Library

[8]

Trevor Brown, Faith Ellen, and Eric Ruppert. 2014. A General Technique for Non-blocking Trees. In Proc. 19th ACM Symposium on Principles and Practice of Parallel Programming. 329--342.

Digital Library

[9]

Andreas Chatzistergiou, Marcelo Cintra, and Stratis D. Viglas. 2015. REWIND: Recovery Write-Ahead System for In-Memory Non-Volatile Data-Structures. PVLDB 8, 5 (2015), 497--508.

Digital Library

[10]

Shimin Chen and Qin Jin. 2015. Persistent B+-Trees in Non-Volatile Main Memory. PVLDB 8, 7 (2015), 786--797.

Digital Library

[11]

Ping Chi, Wang-Chien Lee, and Yuan Xie. 2014. Making B⁺-tree efficient in PCM-based main memory. In International Symposium on Low Power Electronics and Design, ISLPED'14, La Jolla, CA, USA, August 11--13, 2014. 69--74.

Digital Library

[12]

Joel Coburn, Adrian M. Caulfield, Ameen Akel, Laura M. Grupp, Rajesh K. Gupta, Ranjit Jhala, and Steven Swanson. 2011. NV-Heaps: making persistent objects fast and safe with next-generation, non-volatile memories. In Proceedings of the 16th International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS 2011, Newport Beach, CA, USA, March 5--11, 2011. 105--118.

Digital Library

[13]

Nachshon Cohen, Michal Friedman, and James R. Larus. 2017. Efficient logging in non-volatile memory by exploiting coherency protocols. PACMPL 1, OOPSLA (2017), 67:1--67:24.

Digital Library

[14]

Nachshon Cohen, Rachid Guerraoui, and Igor Zablotchi. 2018. The Inherent Cost of Remembering Consistently. In Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures, SPAA 2018, Vienna, Austria, July 16--18, 2018. 259--269.

Digital Library

[15]

Andreia Correia, Pascal Felber, and Pedro Ramalhete. 2018. Romulus: Efficient Algorithms for Persistent Transactional Memory. In Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures, SPAA 2018, Vienna, Austria, July 16--18, 2018. 271--282.

Digital Library

[16]

Andreia Correia, Pascal Felber, and Pedro Ramalhete. 2020. Persistent memory and the rise of universal constructions. In EuroSys '20: Fifteenth EuroSys Conference 2020, Heraklion, Greece, April 27--30, 2020, Angelos Bilas, Kostas Magoutis, Evangelos P. Markatos, Dejan Kostic, and Margo Seltzer (Eds.). ACM, 5:1--5:15.

Digital Library

[17]

Tudor David, Aleksandar Dragojevic, Rachid Guerraoui, and Igor Zablotchi. 2018. Log-Free Concurrent Data Structures. In 2018 USENIX Annual Technical Conference, USENIX ATC 2018, Boston, MA, USA, July 11--13, 2018. 373--386. https://www.usenix.org/conference/atc18/presentation/david

[18]

Faith Ellen, Panagiota Fatourou, Joanna Helga, and Eric Ruppert. 2014. The amortized complexity of non-blocking binary search trees. In ACM Symposium on Principles of Distributed Computing, PODC '14, Paris, France, July 15--18, 2014. 332--340.

Digital Library

[19]

Faith Ellen, Panagiota Fatourou, Eric Ruppert, and Franck van Breugel. 2010. Non-blocking binary search trees. In Proceedings of the 29th Annual ACM Symposium on Principles of Distributed Computing, PODC 2010, Zurich, Switzerland, July 25--28, 2010. 131--140.

Digital Library

[20]

Panagiota Fatourou, Nikolaos D. Kallimanis, and Eleftherios Kosmas. 2021. Brief Announcement: Persistent Software Combining. In 35th International Symposium on Distributed Computing (DISC 2021) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 209), Seth Gilbert (Ed.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 56:1--56:4.

[21]

Panagiota Fatourou, Nikolaos D. Kallimanis, and Eleftherios Kosmas. 2022. The Performance Power of Software Combining in Persistence. In Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (Seoul, South Korea) (PPoPP '22). Association for Computing Machinery, New York, NY, USA, to appear.

Digital Library

[22]

Panagiota Fatourou, Elias Papavasileiou, and Eric Ruppert. 2019. Persistent Non-Blocking Binary Search Trees Supporting Wait-Free Range Queries. In Proc. 31st ACM on Symposium on Parallelism in Algorithms and Architectures. 275--286.

Digital Library

[23]

Steven Feldman, Carlos Valera-Leon, and Damian Dechev. 2016. An efficient wait-free vector. IEEE Transactions on Parallel and Distributed Systems 27, 3 (2016), 654--667.

Digital Library

[24]

Michal Friedman, Naama Ben-David, Yuanhao Wei, Guy E. Blelloch, and Erez Petrank. 2020. NVTraverse: In NVRAM Data Structures, the Destination is More Important than the Journey. In Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation (London, UK) (PLDI 2020). Association for Computing Machinery, New York, NY, USA, 377--392.

Digital Library

[25]

Michal Friedman, Maurice Herlihy, Virendra J. Marathe, and Erez Petrank. 2018. A persistent lock-free queue for non-volatile memory. In Proceedings of the 23rd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2018, Vienna, Austria, February 24--28, 2018. 28--40.

Digital Library

[26]

Michal Friedman, Erez Petrank, and Pedro Ramalhete. 2021. Mirror: Making Lock-Free Data Structures Persistent. In Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation (Virtual, Canada) (PLDI 2021). Association for Computing Machinery, New York, NY, USA, 1218--1232.

Digital Library

[27]

Wojciech M. Golab and Danny Hendler. 2017. Recoverable Mutual Exclusion in Sub-logarithmic Time. In Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC 2017, Washington, DC, USA, July 25--27, 2017. 211--220.

Digital Library

[28]

Wojciech M. Golab and Aditya Ramaraju. 2016. Recoverable Mutual Exclusion. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC 2016, Chicago, IL, USA, July 25--28, 2016. 65--74.

Digital Library

[29]

Timothy L. Harris. 2001. A Pragmatic Implementation of Non-blocking Linked-Lists. In Distributed Computing, 15th International Conference, DISC 2001, Lisbon, Portugal, October 3--5, 2001, Proceedings. 300--314.

[30]

Maurice Herlihy and Nir Shavit. 2008. The art of multiprocessor programming. Morgan Kaufmann.

[31]

Intel. 2016. Intel® 64 and IA-32 Architectures Developer's Manual: Vol. 3A. Available at https://www.intel.com/content/www/us/en/architecture-and-technology/64-ia-32-architectures-sottware-developer-vol-3a-part-1-manual.html (September 2016).

[32]

Joseph Izraelevitz, Hammurabi Mendes, and Michael L. Scott. 2016. Linearizability of Persistent Memory Objects Under a Full-System-Crash Failure Model. In Distributed Computing - 30th International Symposium, DISC 2016, Paris, France, September 27--29, 2016. Proceedings. 313--327.

[33]

Joseph Izraelevitz, Hammurabi Mendes, and Michael L. Scott. 2016. Linearizability of Persistent Memory Objects Under a Full-System-Crash Failure Model. In Proceedings of the 30th International Symposium of Distributed Computing (Vienna, Austria) (DISC '16, Vol. LNCS 9888). Springer, 313--327.

[34]

Prasad Jayanti and Anup Joshi. 2017. Recoverable FCFS Mutual Exclusion with Wait-Free Recovery. In 31st International Symposium on Distributed Computing, DISC 2017, October 16--20, 2017, Vienna, Austria. 30:1--30:15.

[35]

Qingrui Liu, Joseph Izraelevitz, Se Kwon Lee, Michael L. Scott, Sam H. Noh, and Changhee Jung. 2018. IDO: Compiler-Directed Failure Atomicity for Nonvolatile Memory. In Proceedings of the 51st Annual IEEE/ACM International Symposium on Microarchitecture (Fukuoka, Japan) (MICRO-51). IEEE Press, 258--270.

Digital Library

[36]

Baotong Lu, Xiangpeng Hao, Tianzheng Wang, and Eric Lo. 2020. Dash: Scalable Hashing on Persistent Memory. Proc. VLDB Endow. 13, 8 (apr 2020), 1147--1161.

Digital Library

[37]

Iulian Moraru, David G Andersen, Michael Kaminsky, Nathan Binkert, Niraj Tolia, Reinhard Munz, and Parthasarathy Ranganathan. 2012. Persistent, protected and cached: Building blocks for main memory data stores. CMU Parallel Data Lab Trechnical Report, CMU-PDL-11-114 (Dec. 2011) (2012).

[38]

Aravind Natarajan, Arunmoezhi Ramachandran, and Neeraj Mittal. 2020. FEAST: a lightweight lock-free concurrent binary search tree. ACM Transactions on Parallel Computing 7, 2 (May 2020).

Digital Library

[39]

Matej Pavlovic, Alex Kogan, Virendra J. Marathe, and Tim Harris. 2018. Brief Announcement: Persistent Multi-Word Compare-and-Swap. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC 2018, Egham, United Kingdom, July 23--27, 2018. 37--39.

Digital Library

[40]

PMDK. [n.d.]. The Persistent Memory Development Kit. https://github.com/pmem/pmdk/. https://github.com/pmem/pmdk/

[41]

Pedro Ramalhete, Andreia Correia, Pascal Felber, and Nachshon Cohen. 2019. OneFile: A Wait-Free Persistent Transactional Memory. In 49th Annual IEEE/IFIP International Conference on Dependable Systems and Networks, DSN 2019, Portland, OR, USA, June 24--27, 2019. IEEE, 151--163.

[42]

Matan Rusanovsky, Hagit Attiya, Ohad Ben-Baruch, Tom Gerby, Danny Hendler, and Pedro Ramalhete. 2021. Flat-Combining-Based Persistent Data Structures for Non-volatile Memory. In Stabilization, Safety, and Security of Distributed Systems, Colette Johnen, Elad Michael Schiller, and Stefan Schmid (Eds.). Springer International Publishing, Cham, 505--509.

[43]

William N Scherer III, Doug Lea, and Michael L Scott. 2005. A scalable elimination-based exchange channel. SCOOL 05 (2005), 83.

[44]

Gal Sela and Erez Petrank. 2021. Durable Queues: The Second Amendment. Association for Computing Machinery, New York, NY, USA, 385--397.

Digital Library

[45]

Shahar Timnat and Erez Petrank. 2014. A practical wait-free simulation for lock-free data structures. In ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP '14, Orlando, FL, USA, February 15--19, 2014. 357--368.

Digital Library

[46]

Shivaram Venkataraman, Niraj Tolia, Parthasarathy Ranganathan, and Roy H. Campbell. 2011. Consistent and Durable Data Structures for Non-Volatile Byte-Addressable Memory. In 9th USENIX Conference on File and Storage Technologies, San Jose, CA, USA, February 15--17, 2011. 61--75. http://www.usenix.org/events/fast11/tech/techAbstracts.html#Venkataraman

Digital Library

[47]

Haris Volos, Andres Jaan Tack, and Michael M. Swift. 2011. Mnemosyne: Lightweight Persistent Memory. In Proceedings of the Sixteenth International Conference on Architectural Support for Programming Languages and Operating Systems (Newport Beach, California, USA) (ASPLOS XVI). Association for Computing Machinery, New York, NY, USA, 91--104.

Digital Library

[48]

Ivan Walulya and Philippas Tsigas. 2017. Scalable Lock-Free Vector with Combining. In 2017 IEEE International Parallel and Distributed Processing Symposium, IPDPS 2017, Orlando, FL, USA, May 29 - June 2, 2017. 917--926.

[49]

Tianzheng Wang, Justin J. Levandoski, and Per-Åke Larson. 2018. Easy Lock-Free Indexing in Non-Volatile Memory. In 34th IEEE International Conference on Data Engineering, ICDE 2018, Paris, France, April 16--19, 2018. 461--472.

[50]

Yi Xu, Joseph Izraelevitz, and Steven Swanson. 2021. Clobber-NVM: Log Less, Re-Execute More. In Proceedings of the 26th ACM International Conference on Architectural Support for Programming Languages and Operating Systems (Virtual, USA) (ASPLOS 2021). Association for Computing Machinery, New York, NY, USA, 346--359.

Digital Library

[51]

Wenting Zheng, Stephen Tu, Eddie Kohler, and Barbara Liskov. 2014. Fast Databases with Fast Durability and Recovery Through Multicore Parallelism. In 11th USENIX Symposium on Operating Systems Design and Implementation (OSDI 14). 465--477.

[52]

Yoav Zuriel, Michal Friedman, Gali Sheffi, Nachshon Cohen, and Erez Petrank. 2019. Efficient Lock-Free Durable Sets. Proc. ACM Program. Lang. 3, OOPSLA, Article 128 (oct 2019), 26 pages.

Digital Library

Cited By

Zhu ZNi NHuang YSun YJia ZKim NWitchel E(2024)Lupin: Tolerating Partial Failures in a CXL PodProceedings of the 2nd Workshop on Disruptive Memory Systems10.1145/3698783.3699377(41-50)Online publication date: 3-Nov-2024
https://dl.acm.org/doi/10.1145/3698783.3699377
Fatourou P(2024)Parallel and Distributed Data Series Processing on Modern and Emerging HardwareManagement of Digital EcoSystems10.1007/978-3-031-51643-6_29(399-407)Online publication date: 2-Feb-2024
https://doi.org/10.1007/978-3-031-51643-6_29
Cho KJeon SRaad AKang J(2023)Memento: A Framework for Detectable Recoverability in Persistent MemoryProceedings of the ACM on Programming Languages10.1145/35912327:PLDI(292-317)Online publication date: 6-Jun-2023
https://dl.acm.org/doi/10.1145/3591232
Show More Cited By

Index Terms

Detectable recovery of lock-free data structures

Recommendations

The performance power of software combining in persistence
PPoPP '22: Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming

The availability of Non-Volatile Main Memory (known as NVMM) enables the design of recoverable concurrent algorithms. We study the power of software combining in achieving recoverable synchronization and designing persistent data structures. Software ...
Mirror: making lock-free data structures persistent
PLDI 2021: Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation

With the recent launch of the Intel Optane memory platform, non-volatile main memory in the form of fast, dense, byte-addressable non-volatile memory has now become available. Nevertheless, designing crash-resilient algorithms and data structures is ...
Lock-Free Data-Structure Iterators
DISC 2013: Proceedings of the 27th International Symposium on Distributed Computing - Volume 8205

Concurrent data structures are often used with large concurrent software. An iterator that traverses the data structure items is a highly desirable interface that often exists for sequential data structures but is missing from almost all concurrent data-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PPoPP '22: Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming

April 2022

495 pages

ISBN:9781450392044

DOI:10.1145/3503221

General Chair:
Jaejin Lee
Seoul National University
,
Program Chairs:
Kunal Agrawal
Washington University
,
Michael Spear
Lehigh University

Copyright © 2022 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 28 March 2022

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Badges

Author Tags

Qualifiers

Research-article

Conference

PPoPP '22

Sponsor:

PPoPP '22: 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming

April 2 - 6, 2022

Seoul, Republic of Korea

Acceptance Rates

Overall Acceptance Rate 230 of 1,014 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
454
Total Downloads

Downloads (Last 12 months)107
Downloads (Last 6 weeks)10

Reflects downloads up to 23 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhu ZNi NHuang YSun YJia ZKim NWitchel E(2024)Lupin: Tolerating Partial Failures in a CXL PodProceedings of the 2nd Workshop on Disruptive Memory Systems10.1145/3698783.3699377(41-50)Online publication date: 3-Nov-2024
https://dl.acm.org/doi/10.1145/3698783.3699377
Fatourou P(2024)Parallel and Distributed Data Series Processing on Modern and Emerging HardwareManagement of Digital EcoSystems10.1007/978-3-031-51643-6_29(399-407)Online publication date: 2-Feb-2024
https://doi.org/10.1007/978-3-031-51643-6_29
Cho KJeon SRaad AKang J(2023)Memento: A Framework for Detectable Recoverability in Persistent MemoryProceedings of the ACM on Programming Languages10.1145/35912327:PLDI(292-317)Online publication date: 6-Jun-2023
https://dl.acm.org/doi/10.1145/3591232
Assa GCorreia ARamalhete PSchiavoni VFelber PDehnavi MKulkarni MKrishnamoorthy S(2023)TL4xProceedings of the 28th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming10.1145/3572848.3577495(245-259)Online publication date: 25-Feb-2023
https://dl.acm.org/doi/10.1145/3572848.3577495
Fatourou PKosmas EPalpanas TPaterakis G(2023)FreSh: A Lock-Free Data Series Index2023 42nd International Symposium on Reliable Distributed Systems (SRDS)10.1109/SRDS60354.2023.00029(209-220)Online publication date: 25-Sep-2023
https://doi.org/10.1109/SRDS60354.2023.00029
Delporte-Gallet CFatourou PFauconnier HRuppert EMilani AWoelfel P(2022)When is Recoverable Consensus Harder Than Consensus?Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing10.1145/3519270.3538418(198-208)Online publication date: 20-Jul-2022
https://dl.acm.org/doi/10.1145/3519270.3538418

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents