崩溃一致性

在崩溃情况下保持数据安全是一个根本性问题。

Ram Alagappan，Peter Alvaro 引言

“实践研究”专栏结合了数字图书馆（全球最大的计算机科学研究文库）的资源和会员的专业知识。“实践研究”专栏的共同目标是在学术界人士和他们在业界的同行之间分享阅读计算机科学研究的乐趣和实用价值。

在“实践研究”重启后的第二篇文章中，我们邀请了伊利诺伊大学厄巴纳-香槟分校的助理教授 Ram Alagappan 来调研最近关于崩溃一致性的研究——即保证应用程序数据在系统崩溃后能够幸存下来的机制。与内存一致性不同，崩溃一致性是一个端到端的问题，不仅要求系统的底层（例如，文件系统）被正确实现，还要求应用程序正确 *使用* 它们的接口。

Alagappan 选择了一系列论文，这些论文反映了这种复杂性，涵盖了从应用程序一直到硬件的整个技术栈。第一篇论文侧重于文件系统——希望提供崩溃一致性的应用程序必须依赖于文件系统——并使用错误查找技术来见证接口级保证的违规行为。第二篇论文向上移动技术栈，重新思考文件系统为应用程序员提供的接口，以使编写崩溃一致的程序更容易。最后，随着持久内存给崩溃一致性带来的新挑战，情节变得更加复杂。它探讨了如何使用缓存一致性加速器来缓解这些挑战。我从阅读这些选集中学到了很多，我相信你也会如此。

——Peter Alvaro

实践研究：崩溃一致性

Ram Alagappan

存储系统面临的一个关键挑战是如何在系统崩溃（由断电或内核错误引起）的情况下正确更新持久数据。从高层次来看，问题在于系统可能在更新其持久结构的过程中随时崩溃，从而使数据处于不一致的状态。如果存储系统能够在崩溃后将其存储的持久数据恢复到有意义的状态，则该存储系统被认为是崩溃一致的。

崩溃一致性至关重要，主要有两个原因

• 首先，系统崩溃是不可避免的。即使是管理良好的数据中心也会遭受偶尔的断电事件；此外，不断增加的软件复杂性意味着更多的错误，从而导致崩溃。因此，每个存储系统，包括本地文件系统、运行在其之上的存储应用程序和持久内存程序，都必须确保崩溃一致性。

• 其次，从用户和应用程序的角度来看，崩溃一致性至关重要。如果存储系统在崩溃时可能丢失或损坏数据，那将是灾难性的，会导致信任丧失和数百万美元的收入损失。

实现崩溃一致性具有挑战性。存储系统通常执行精心设计的修改序列，以确保它们能够在崩溃的情况下安全地从一个一致状态转移到另一个一致状态。然而，正确地做到这一点充满了细微之处，即使对于经验丰富的程序员来说也是具有挑战性的。

本文讨论了系统研究社区为改善现状而努力的三个方面：查找和修复崩溃一致性错误；开发新的抽象概念以简化崩溃一致性；以及利用新硬件来实现崩溃一致性。我选择了每个类别中的论文。这些绝不是唯一能够改进崩溃一致性的论文，甚至不是通用方法，但它们确实提供了问题和解决方案空间的一个很好的概述。

查找和修复崩溃一致性错误

Jayashree Mohan、Ashlie Martinez、Soujanya Ponnapalli、Pandian Raju、Vijay Chidambaram。《使用有界黑盒崩溃测试查找崩溃一致性错误》。第 13 届 Unix 操作系统设计与实现研讨会论文集 (OSDI 2018)。

https://www.usenix.org/system/files/osdi18-mohan.pdf

改进存储系统崩溃一致性最务实的方法也许是查找崩溃一致性代码中的错误并修复它们。Mohan 等人的这篇论文发现了本地文件系统（许多存储系统的构建块）中的崩溃一致性错误。如果文件系统能够在崩溃后安全地恢复其内部元数据（例如 inode 和位图）以及显式持久化的用户数据（使用 fsync 或类似操作），则该文件系统是崩溃一致的。

测试文件系统的崩溃一致性的一个挑战是工作负载数量众多，并且崩溃可能在工作负载期间的任何时间点发生。彻底探索此搜索空间的测试方法是不切实际的。本文通过首先研究文件系统中现有的崩溃一致性错误来解决这个问题。从这项研究中得出的一个关键观察结果是，仅包含三个或更少文件系统操作的工作负载就可以触发大多数崩溃一致性错误。

作者还意识到，仅在持久点（即，显式持久化数据的操作，例如 fsync）之后注入崩溃就足够了。这种选择使正确性标准非常明确：虽然对于未显式持久化的更新没有保证，但已持久化的更新（通过 fsync 或类似操作）必须是安全的。虽然此策略不能保证找到所有错误，但它提供了一种实用的方法来暴露严重的错误，从而使该方法非常有用。

作者根据这些见解设计了测试工具，并将这些工具应用于许多文件系统。这些工具的一个巧妙之处在于它们以黑盒方式工作：测试不需要修改文件系统代码，因此它们可以轻松应用于许多文件系统。结果表明，即使是流行的文件系统也可能在崩溃事件中丢失持久化数据。例如，Btrfs 可能会在崩溃后丢失重命名的文件。成熟系统中存在如此严重的错误表明，构建崩溃一致的系统是一项具有挑战性的任务。幸运的是，一旦发现错误，修复错误通常相当简单。例如，文件系统开发人员能够修复作者的测试工具发现的一些错误。

更好的抽象概念以简化崩溃一致性

Thanumalayan Sankaranarayana Pillai、Ramnatthan Alagappan、Lanyue Lu、Vijay Chidambaram、Andrea C. Arpaci-Dusseau、Remzi H. Arpaci-Dusseau。《使用 CCFS 的应用程序崩溃一致性和性能》。第 15 届 Usenix 文件与存储技术会议论文集 (FAST 2017)。https://www.usenix.org/system/files/conference/fast17/fast17_pillai.pdf

虽然文件系统实现了保持其内部元数据崩溃安全的机制，但它们在保护应用程序数据方面做得很少。因此，应用程序通过精心实现的更新协议（系统调用序列，例如写入、fsync 和重命名）自行完成此操作。不幸的是，虽然构建此类协议（例如，预写式日志）的高级思想已被很好地理解，但在现代文件系统上以崩溃一致的方式实现它们却出乎意料地困难。

问题在于，文件系统如何持久化已发出的操作的确切语义未明确指定。具体而言，文件系统可能会出于效率原因重新排序操作；因此，当系统从崩溃中恢复时，稍后的写入可能比之前的写入更早到达磁盘。因此，应用程序必须推理崩溃后所有可能的重新排序的磁盘状态，即使对于经验丰富的程序员来说，这也是一项艰巨的任务。

仅仅使用中等复杂度的更新协议，开发人员就必须手动推理多种状态。避免重新排序的一种方法是以应用程序发出的顺序持久化系统调用。然而，强制每个操作同步到存储的成本过高。

本文介绍了一种名为流的新抽象概念，以简化崩溃一致性更新协议的构建，而不会造成任何性能损失。关键思想是流内的写入始终以发出的顺序持久化，从而无需在恢复协议中推理重新排序。但是，来自不同流的写入可以重新排序，文件系统实现可以利用这一事实来实现更高的性能。应用程序只需进行少量代码修改即可利用流抽象：它们只需在开始时发出一个系统调用 setstream。然后在已建立的流中发出的所有更新都将按顺序持久化到存储。

CCFS（崩溃一致性文件系统）实现了流抽象。它还实现了新机制来避免跨流的虚假依赖关系。Git、LevelDB 和 Apache ZooKeeper 等多个应用程序在 CCFS 上是崩溃一致的，但当在 Linux 的日志文件系统 ext4 上运行时，它们可能会丢失或损坏数据。此外，CCFS 接近重新排序 ext4 文件系统的性能。总的来说，本文表明，新的文件系统抽象和仔细的实现可以简化应用程序的崩溃一致性，而不会牺牲性能。

利用新兴硬件实现崩溃一致性

Ankit Bhardwaj、Todd Thornley、Vinita Pawar、Reto Achermann、Gerd Zellweger、Ryan Stutsman。《用于持久内存崩溃一致性的缓存一致性加速器》。第 14 届存储和文件系统热点主题研讨会论文集 (HotStorage 2022)。

https://dl.acm.org/doi/pdf/10.1145/3538643.3539752

PM（持久内存）提供类似于 DRAM（动态随机存取存储器）的接口和性能。可以通过加载和存储指令访问它，并且其性能可以接近 DRAM 的性能。然而，与 DRAM 不同，PM 是非易失性的：存储在 PM 上的数据可以在崩溃后恢复。因此，PM 上的持久结构必须以崩溃一致的方式更新。通过缓存一致性链接（例如，CXL）连接的新兴加速器可以为 PM 提供一种实现（黑盒）崩溃一致性的新方法。

大多数现有的 PM 系统通过 WAL（预写式日志）来确保崩溃一致性。有时，开发人员会手工制作 WAL 协议；有时，它通过编译器传递或软件库（例如 Intel 的 PMDK（持久内存开发工具包））自动完成，以记录所有 PM 存储。在任何一种情况下，日志记录都会因额外的日志写入和排序约束（通过使用硬件缓存的指令）而产生开销。有时，这种更新跟踪和日志记录也可以由硬件完成（使用写保护）。然而，这种方法会产生巨大的陷阱开销，并且只能以页面粒度跟踪更新。

本文观察到，可以使用缓存一致性加速器以低开销拦截和记录 PM 更新。它设想了一个（在高层次上）按如下方式工作的系统。具有持久内存的 PAX（持久性加速器设备）通过缓存一致性互连连接到主机。进程可以使用常规的加载和存储指令来映射和访问此内存。然而，该设备会拦截来自 CPU 的缓存行请求。加载只是代理到设备上的 PM。存储更有趣，因为设备需要在存储时确保崩溃一致性。在存储时，设备会收到来自主机 CPU 的消息，告知将修改哪个缓存行。这允许设备执行撤消日志记录；特别是，设备从 PM 获取旧版本（正在修改的缓存行），并记录地址和旧值。如果发生崩溃，则可以使用撤消日志回滚到旧的（一致的）版本。所提出的设计通过使用异步日志写入和分组更新来降低日志记录成本。

这种方法提供了两个主要优点：首先，它施加的开销很低（例如，没有陷阱，以缓存行粒度跟踪）；其次，它提供了一种黑盒方法，可以将易失性数据结构转换为其崩溃一致的持久对应物，而无需更改代码。

总的来说，这是在 PM 设备中实现崩溃一致性的一个新兴且令人兴奋的方向。更广泛地说，本文提供了一个了解如何利用新兴硬件来实现存储功能的视角。

结论

在崩溃情况下保持数据安全是存储系统中的一个根本性问题。虽然对于崩溃一致性的高级思想相对容易理解，但在实践中实现它们却出乎意料地复杂且充满挑战。系统研究社区正在积极致力于解决这一挑战，本文研究的论文提供了三种解决方案。

系统社区中另一个越来越受欢迎的有前景的方法是使用软件验证来证明崩溃一致性。这种方法特别适合从头开始构建的新存储系统。看看这些方法中的哪一种——或它们的组合——将在实践中被广泛采用将是很有趣的。

Peter Alvaro 是加州大学圣克鲁兹分校的计算机科学副教授，他在那里领导 Disorderly Labs 研究小组 (disorderlylabs.github.io)。他的研究重点是使用以数据为中心的语言和分析技术来构建和推理数据密集型分布式系统，以便使它们具有可扩展性、可预测性，并且能够应对大规模分布所固有的故障和不确定性。他在加州大学伯克利分校获得博士学位，师从 Joseph M. Hellerstein。他是国家科学基金会职业奖、Facebook 研究奖、Usenix ATC 2020 最佳演示奖、SIGMOD 2021 杰出 PC 奖和 UCSC 卓越教学奖的获得者。

Ram Alagappan 是伊利诺伊大学厄巴纳-香槟分校的助理教授。他之前曾在 VMware Research 担任博士后研究员。他在威斯康星大学麦迪逊分校与 Andrea Arpaci-Dusseau 教授和 Remzi Arpaci-Dusseau 教授一起攻读博士学位。他的研究兴趣包括存储和分布式系统。他的作品已在顶级系统会议上发表，并获得了三项最佳论文奖。

最初发表于 Queue 第 20 卷，第 4 期——
在数字图书馆中评论这篇文章

更多相关文章

Ethan Miller, Achilles Benetopoulos, George Neville-Neil, Pankaj Mehra, Daniel Bittman - 远内存中的指针
有效地利用新兴的远内存技术需要考虑在父进程上下文之外操作丰富连接的数据。正在开发的操作系统技术通过公开诸如内存对象和全局不变指针之类的抽象来提供帮助，这些抽象可以由设备和新实例化的计算遍历。这些想法将允许在具有分离内存节点的未来异构分布式系统上运行的应用程序利用近内存处理来获得更高的性能，并独立扩展其内存和计算资源以降低成本。

Simson Garfinkel, Jon Stewart - 磨砺你的工具
本文介绍了我们在首次发布十年后更新高性能数字取证工具 BE (bulk_extractor) 的经验。在 2018 年至 2022 年期间，我们将程序从 C++98 更新到 C++17。我们还进行了完整的代码重构并采用了单元测试框架。DF 工具必须经常更新，以跟上其使用方式的变化。对 bulk_extractor 工具更新的描述可以作为可以而且应该做什么的示例。

Pat Helland - 自主计算
自主计算是一种商业工作模式，它使用协作来连接领地及其特使。这种基于纸质表格的模式已经使用了几个世纪。在这里，我们解释了领地、协作和特使。我们研究了特使如何在自主边界之外工作，并且在保持局外人身份的同时也很方便。我们还研究了如何启动跨不同领地的工作，长时间运行并最终完成。

Archie L. Cobbs - 持久性编程
几年前，我的团队正在为一个增强型 911 (E911) 紧急呼叫中心开展一个商业 Java 开发项目。我们试图使用传统的 Java over SQL 数据库模型来满足该项目的数据存储要求，但感到沮丧。在对项目的特定要求（和非要求）进行一番思考之后，我们深吸一口气，决定从头开始创建我们自己的自定义持久层。