Robust Synchronization Primitives for Non-Volatile Main Memory

由于生产力和收入损失，计划外停机和数据丢失每年给加拿大企业造成 $17B 的损失。虽然硬件故障（例如断电或组件故障）是许多停机事件的根本原因，但随后的软件恢复造成的经济损失却是巨大的。这是因为现代数据驱动的软件系统大量使用主内存来缓存关键数据集，并且必须从速度较慢的辅助存储中恢复这些数据集。 新兴的非易失性主存储器 (NVRAM) 介质将辅助存储的持久性与主存储器的性能相结合，缓解了这一问题。 软件系统必须重新设计才能抓住这个独特的机会。本研究旨在通过开发基于 NVRAM 的可恢复数据结构的低级构建块来加速应用程序恢复。为此，该项目将实现以下技术目标：（O1）为各种同步原语设计高效且容错的实现，而不依赖于简化有关环境的假设； (O2) 建立新颖实现的理论正确性属性和性能限制； (O3) 使用实现的原语来改进可由应用程序直接使用的可恢复数据结构的设计。成功完成这些目标后，该研究计划将生成同步原语和可恢复数据结构的软件原型，使软件开发人员能够在关键软件应用程序和服务中释放 NVRAM 的性能优势。这项工作产生的分析和实证结果将通过定义新颖的算法和理论基础，以及阐明可恢复数据结构的微妙性能权衡和基本限制来推进计算机科学。

Unplanned downtime and data loss cost Canadian enterprises $17B annually due to lost productivity and revenues. While hardware malfunction (e.g., loss of electrical power or component failure) is the root cause of many downtime events, the economic losses due to consequent software recovery are extensive. This is because modern data-driven software systems use main memory heavily to cache critical data sets, and must restore these data sets from slower secondary storage. Emerging non-volatile main memory (NVRAM) media offer relief from this problem by combining the persistence of secondary storage with the performance of main memory. Software systems must be redesigned to seize this unique opportunity.The proposed research aims to speed up application recovery by developing low-level building blocks of NVRAM-based recoverable data structures. To that end, the project will address the following technical objectives: (O1) design efficient and fault-tolerant implementations for a variety of synchronization primitives without relying on simplifying assumptions regarding the environment; (O2) establish theoretical correctness properties and performance limits of the novel implementations; and (O3) use implemented primitives to improve the design of recoverable data structures that can be used directly by applications. Upon successful completion of these objectives, the research program will generate software prototypes of both synchronization primitives and recoverable data structures that will allow software developers to unleash the performance benefits of NVRAM in critical software applications and services. Analytical and empirical results arising from this work will advance computer science by defining novel algorithms and theoretical foundations, as well as by elucidating subtle performance trade-offs and fundamental limitations of recoverable data structures.