Michal Friedman
Erez Petrank
Pedro Ramalhete
ABSTRACT
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 complex and error-prone as caches and machine registers are still volatile and the data residing in memory after a crash might not reflect a consistent view of the program state. This complex setting has often led to durable data structures being inefficient or incorrect, especially in the concurrent setting.
In this paper, we present Mirror -- a simple, general automatic transformation that adds durability to lock-free data structures, with a low performance overhead. Moreover, in the current non-volatile main memory configuration, where non-volatile memory operates side-by-side with a standard fast DRAM, our mechanism exploits the hybrid system to substantially improve performance. Evaluation shows a significant performance advantage over NVTraverse, which is the state-of-the-art general transformation technique, and over Intel's concurrent lock-based key-value datastore. Unlike some previous transformations, Mirror does not require any restriction on the lock-free data structure format.
- AMD. [n.d.]. AMD64 Architecture Programmer’s Manual.. https://www.amd.com/system/files/TechDocs/24594.pdfGoogle Scholar
- ARM. 2018. ARM Architecture Reference Manual ARMv8. https://static.docs.arm.com/ddi0487/da/DDI0487D_a_armv8_arm.pdfGoogle Scholar
- Hillel Avni and Trevor Brown. 2016. Persistent Hybrid Transactional Memory for Databases. Proc. VLDB Endow., 10, 4 (2016), Nov., 409–420. issn:2150-8097 https://doi.org/10.14778/3025111.3025122 Google ScholarDigital Library
- H. Alan Beadle, Wentao Cai, Haosen Wen, and Michael L. Scott. 2020. Nonblocking Persistent Software Transactional Memory. In Proceedings of the 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP ’20). Association for Computing Machinery, New York, NY, USA. 429–430. isbn:9781450368186 https://doi.org/10.1145/3332466.3374506 Google ScholarDigital Library
- Kumud Bhandari, Dhruva R. Chakrabarti, and Hans-J. Boehm. 2016. Makalu: Fast Recoverable Allocation of Non-volatile Memory. In Proceedings of the 2016 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA 2016). ACM, New York, NY, USA. 677–694. isbn:978-1-4503-4444-9 https://doi.org/10.1145/2983990.2984019 Google ScholarDigital Library
- C++. [n.d.]. Std::atomic Library. https://en.cppreference.com/w/cpp/atomicGoogle Scholar
- Wentao Cai, Haosen Wen, H. Alan Beadle, Chris Kjellqvist, Mohammad Hedayati, and Michael L. Scott. 2020. Understanding and Optimizing Persistent Memory Allocation. In Proceedings of the 2020 ACM SIGPLAN International Symposium on Memory Management (ISMM 2020). 60–73.Google ScholarDigital Library
- Dhruva R. Chakrabarti, Hans-J. Boehm, and Kumud Bhandari. 2014. Atlas: Leveraging Locks for Non-volatile Memory Consistency. In Proceedings of the 2014 ACM International Conference on Object Oriented Programming Systems Languages & Applications (OOPSLA ’14). ACM, New York, NY, USA. 433–452. isbn:978-1-4503-2585-1 https://doi.org/10.1145/2660193.2660224 Google ScholarDigital Library
- 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 Sixteenth International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS XVI). Association for Computing Machinery, New York, NY, USA. 105–118. isbn:9781450302661 https://doi.org/10.1145/1950365.1950380 Google ScholarDigital Library
- Nachshon Cohen, Rachid Guerraoui, and Igor Zablotchi. 2018. The Inherent Cost of Remembering Consistently. In Proceedings of the 30th Symposium on Parallelism in Algorithms and Architectures. 259–269.Google ScholarDigital Library
- Brian F. Cooper, Adam Silberstein, Erwin Tam, Raghu Ramakrishnan, and Russell Sears. 2010. Benchmarking Cloud Serving Systems with YCSB.Google Scholar
- Andreia Correia, Pascal Felber, and Pedro Ramalhete. 2020. Persistent Memory and the Rise of Universal Constructions. In Proceedings of the Fifteenth European Conference on Computer Systems (EuroSys ’20). Association for Computing Machinery, New York, NY, USA. Article 5, 15 pages. isbn:9781450368827 https://doi.org/10.1145/3342195.3387515 Google ScholarDigital Library
- Tudor David, Aleksandar Dragojević, Rachid Guerraoui, and Igor Zablotchi. 2018. Log-Free Concurrent Data Structures. In Proceedings of the 2018 USENIX Conference on Usenix Annual Technical Conference (USENIX ATC ’18). USENIX Association, USA. isbn:9781931971447Google ScholarDigital Library
- Tudor David, Rachid Guerraoui, and Vasileios Trigonakis. 2015. Asynchronized Concurrency: The Secret to Scaling Concurrent Search Data Structures.Google ScholarDigital Library
- Facebook. [n.d.]. RocksDB. https://github.com/facebook/rocksdbGoogle Scholar
- Keir Fraser. 2003. Practical lock-freedom.Google Scholar
- 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 (PLDI 2020). Association for Computing Machinery, New York, NY, USA. 377–392. isbn:9781450376136 https://doi.org/10.1145/3385412.3386031 Google ScholarDigital Library
- 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, Andreas Krall and Thomas R. Gross (Eds.). ACM, 28–40. https://doi.org/10.1145/3178487.3178490 Google ScholarDigital Library
- Google. [n.d.]. LevelDB. https://github.com/google/leveldbGoogle Scholar
- Jinyu Gu, Qianqian Yu, Xiayang Wang, Zhaoguo Wang, Binyu Zang, Haibing Guan, and Haibo Chen. 2019. Pisces: A Scalable and Efficient Persistent Transactional Memory. In Proceedings of the 2019 USENIX Conference on Usenix Annual Technical Conference (USENIX ATC ’19). USENIX Association, USA. 913–928. isbn:9781939133038Google Scholar
- Timothy L Harris. 2001. A pragmatic implementation of non-blocking linked-lists. 300–314.Google Scholar
- Maurice P Herlihy and Jeannette M Wing. 1990. Linearizability: A correctness condition for concurrent objects. 12, 3 (1990), 463–492.Google Scholar
- Intel. [n.d.]. Developers Intel64 and IA-32 Architectures Software Manuals Combined. https://software.intel.com/content/www/us/en/develop/articles/intel-sdm.htmlGoogle Scholar
- Intel. [n.d.]. Intel Architecture Instruction Set Extensions Programming Reference. https://software.intel.com/content/www/us/en/develop/download/intel-architecture-instruction-set-extensions-programming-reference.htmlGoogle Scholar
- Intel. [n.d.]. Persistent Memory Library. https://pmem.io.Google Scholar
- Intel. [n.d.]. pmemkv-bench.. https://github.com/pmem/pmemkv-benchGoogle Scholar
- Joseph Izraelevitz, Hammurabi Mendes, and Michael L Scott. 2016. Linearizability of persistent memory objects under a full-system-crash failure model. In International Symposium on Distributed Computing. 313–327.Google ScholarCross Ref
- A. Joshi, V. Nagarajan, M. Cintra, and S. Viglas. 2018. DHTM: Durable Hardware Transactional Memory. In 2018 ACM/IEEE 45th Annual International Symposium on Computer Architecture (ISCA). 452–465. issn:2575-713X https://doi.org/10.1109/ISCA.2018.00045 Google ScholarDigital Library
- Aasheesh Kolli, Steven Pelley, Ali Saidi, Peter M. Chen, and Thomas F. Wenisch. 2016. High-Performance Transactions for Persistent Memories. In Proceedings of the Twenty-First International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS ’16). Association for Computing Machinery, New York, NY, USA. 399–411. isbn:9781450340915 https://doi.org/10.1145/2872362.2872381 Google ScholarDigital Library
- Mengxing Liu, Mingxing Zhang, Kang Chen, Xuehai Qian, Yongwei Wu, Weimin Zheng, and Jinglei Ren. 2017. DudeTM: Building durable transactions with decoupling for persistent memory. In Proceedings of the Twenty-Second International Conference on Architectural Support for Programming Languages and Operating Systems. 329–343.Google ScholarDigital Library
- Virendra J. Marathe, Achin Mishra, Amee Trivedi, Yihe Huang, Faisal Zaghloul, Sanidhya Kashyap, Margo Seltzer, Tim Harris, Steve Byan, Bill Bridge, and Dave Dice. 2018. Persistent Memory Transactions. CoRR, abs/1804.00701 (2018), arxiv:1804.00701. arxiv:1804.00701Google Scholar
- Amirsaman Memaripour, Anirudh Badam, Amar Phanishayee, Yanqi Zhou, Ramnatthan Alagappan, Karin Strauss, and Steven Swanson. 2017. Atomic In-Place Updates for Non-Volatile Main Memories with Kamino-Tx. In Proceedings of the Twelfth European Conference on Computer Systems (EuroSys ’17). Association for Computing Machinery, New York, NY, USA. 499–512. isbn:9781450349383 https://doi.org/10.1145/3064176.3064215 Google ScholarDigital Library
- Amirsaman Memaripour, Joseph Izraelevitz, and Steven Swanson. 2020. Pronto: Easy and Fast Persistence for Volatile Data Structures. In Proceedings of the Twenty-Fifth International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS ’20). Association for Computing Machinery, New York, NY, USA. 789–806. isbn:9781450371025 https://doi.org/10.1145/3373376.3378456 Google ScholarDigital Library
- Aravind Natarajan and Neeraj Mittal. 2014. Fast Concurrent Lock-free Binary Search Trees.Google Scholar
- Azalea Raad, John Wickerson, Gil Neiger, and Viktor Vafeiadis. 2019. Persistency Semantics of the Intel-X86 Architecture. Proc. ACM Program. Lang., 4, POPL (2019), Article 11, 31 pages.Google Scholar
- Azalea Raad, John Wickerson, and Viktor Vafeiadis. 2019. Weak Persistency Semantics from the Ground up: Formalising the Persistency Semantics of ARMv8 and Transactional Models. Proc. ACM Program. Lang., 3, OOPSLA (2019), Article 135.Google ScholarDigital Library
- Pedro Ramalhete, Andreia Correia, Pascal Felber, and Nachshon Cohen. 2019. OneFile: A Wait-Free Persistent Transactional Memory. In 2019 49th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN). 151–163.Google Scholar
- Steve Scargall. 2020. pmemkv: A Persistent In-Memory Key-Value Store. Apress, Berkeley, CA. 141–153. isbn:978-1-4842-4932-1 https://doi.org/10.1007/978-1-4842-4932-1_9 Google ScholarCross Ref
- 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 (ASPLOS XVI). Association for Computing Machinery, New York, NY, USA. 91–104. isbn:9781450302661 https://doi.org/10.1145/1950365.1950379 Google ScholarDigital Library
- Haris Volos, Andres Jaan Tack, and Michael M. Swift. 2011. Mnemosyne: Lightweight Persistent Memory. SIGPLAN Not., 46, 3 (2011), March, 91–104. issn:0362-1340 https://doi.org/10.1145/1961296.1950379 Google ScholarDigital Library
- Yoav Zuriel, Michal Friedman, Gali Sheffi, Nachshon Cohen, and Erez Petrank. 2019. Efficient Lock-Free Durable Sets.Google Scholar
Index Terms
- Mirror: making lock-free data structures persistent
Recommendations
NVTraverse: in NVRAM data structures, the destination is more important than the journey
PLDI 2020: Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and ImplementationThe recent availability of fast, dense, byte-addressable non-volatile memory has led to increasing interest in the problem of designing durable data structures that can recover from system crashes. However, designing durable concurrent data structures ...
A persistent lock-free queue for non-volatile memory
PPoPP '18: Proceedings of the 23rd ACM SIGPLAN Symposium on Principles and Practice of Parallel ProgrammingNon-volatile memory is expected to coexist with (or even displace) volatile DRAM for main memory in upcoming architectures. This has led to increasing interest in the problem of designing and specifying durable data structures that can recover from ...
A persistent lock-free queue for non-volatile memory
PPoPP '18Non-volatile memory is expected to coexist with (or even displace) volatile DRAM for main memory in upcoming architectures. This has led to increasing interest in the problem of designing and specifying durable data structures that can recover from ...
Comments