协议感知恢复：分布式存储系统中的容错机制

ACM Transactions on Storage，Vol.号143、第二十一条。出版日期：2018年10月基于协议的分布式存储恢复RAMNATTHAN ALAGAPPAN和AISHWARYA GANESAN，21威斯康星大学埃里克·李，德克萨斯大学威斯康星大学麦迪逊分校德克萨斯大学奥斯汀分校安德里亚角ARPACI-DUSSEAU和REMZI H. 阿帕西-杜索，威斯康星大学我们引入协议感知恢复（PAR），一种新的方法，利用协议特定的知识，正确地恢复分布式系统中的存储故障我们证明了效率的PAR通过设计和实现的corruption-tolerant复制（CTR l），PAR机制特定于复制状态机（RSM）系统。我们的实验表明，两个系统，LogCabin和ZooKeeper的CTR l版本，安全地从存储故障中恢复，并提供高可用性，而未经修改的版本可能会丢失数据或变得不可用。我们还表明，CTR L版本实现这种可靠性，性能开销很小。CCS概念：·通用和参考→可靠性;·信息系统→分布式存储;• 计算机系统组织→Reddit; ·软件及其工程→文件系统管理;其他关键词和短语：存储故障、数据损坏、容错、共识ACM参考格式：Ramnatthan Alagappan，Aishwarya Ganesan，Eric Lee，Aws Albarghouthi，Vijay Chidambaram，Andrea C. Arpaci-Dusseau和Remzi H.阿尔帕西-迪索2018.基于磁盘的分布式存储的协议感知恢复。ACM Trans.存储14，3，第21条（2018年10月），30页。https://doi.org/10.1145/3241062本材料得到了NSF资助CNS-1421033和CNS-1218405、DOE资助DE-SC 0014935以及EMC、华为、Microsoft和VMware的捐款的支持本材料中表达的任何观点、发现、结论或建议均为作者的观点，可能不反映NSF、DOE或其他机构的观点。本文是Alagappan等人的FAST '18论文的扩展版本这里的附加材料包括关于如何将PAR应用于其他系统的讨论，为什么崩溃和损坏总是无法解决的证明，总结整个恢复协议的概述图，新的性能实验，解释领导者启动的快照的新数据，以及许多其他小更新。作者Alagappan和A.Ganesan，1210 W.代顿街，Madison，WI 53706;电子邮件：{ra，ag}@cs.wisc.edu;E. 李，2317赛道，奥斯汀，得克萨斯州78712;电子邮件：ericlee123@utexas.edu; A。Albarghouthi，1210 W.代顿街，Madison，WI 53706;电子邮件：aws@cs.wisc.edu; V.奇丹巴拉姆，2317赛道，奥斯汀，得克萨斯州78712;电子邮件：vijay@cs.utexas.edu; A。C. Arpaci-Dusseau 和 R. H. 阿 尔 帕 西 - 迪 索 ， 1210 W 。 代 顿 街 ， 麦 迪 逊 ， 威 斯 康 星 州 53706; 电 子 邮 件 ：dusseau@cs.wisc.edu，remzi@cs.wisc.edu。允许免费制作本作品的全部或部分的数字或硬拷贝，以供个人或课堂使用，前提是制作或分发副本的目的不是为了盈利或商业利益，并且副本的第一页上有本声明和完整的引用。本作品的版权归ACM以外的其他人所有，必须予以尊重。允许使用学分进行摘要。以其他方式复制、重新发布、在服务器上发布或重新分发到列表中，需要事先获得特定许可和/或付费。从permissions@acm.org请求权限。© 2018计算机协会。1553-3077/2018/10-ART21 $15.00https://doi.org/10.1145/3241062ACM Transactions on Storage，Vol.号143、第二十一条。出版日期：2018年10月第二十一R. Alagappan等人1介绍使用冗余的故障恢复是提高分布式系统可靠性的核心[15，23，33，37，65，71]。分布式系统使用多个节点上的数据和功能副本从节点崩溃和网络故障中恢复[7，49，59]。同样，一个节点上的坏数据或损坏的数据应该从冗余副本中恢复。在静态设置中，所有节点始终保持可访问，并且客户端不主动更新数据，从副本中恢复损坏的数据是简单的;在这种设置中，节点可以通过简单地从任何其他节点获取数据来修复其状态然而，在现实中，分布式系统是一个动态的环境，经常处于不断变化的状态。在这样的环境下，正确安排恢复是非常困难的。举一个简单的例子，考虑一个基于法定人数的系统，其中一个节点上的一段数据被损坏。当节点尝试恢复其数据时，一些节点可能失败并且不可达，并且一些节点可能最近已经从故障中恢复并且因此缺少所需的数据或保持陈旧的版本。如果没有足够的注意，节点可能会为了正确地恢复损坏的数据在分布式系统中的冗余副本，我们建议，恢复方法应该是协议感知的。基于分布式系统如何执行对其复制数据的更新、选举领导者等，精心设计了协议感知恢复（PAR例如，在前面的示例中，PAR机制将认识到，故障节点必须查询至少R个（读仲裁）其他节点以安全且快速地恢复其数据。在本文中，我们将PAR应用于复制状态机（RSM）系统。我们关注RSM系统有两个原因。首先，正确实现恢复对于RSM系统来说是最具挑战性的，因为它们提供了强大的一致性和持久性保证[62];可能会违反保证。其次，RSM系统的可靠性至关重要：许多系统将其关键数据委托给RSM系统[47]。例如，Bigtable，GFS和其他系统[8，28]将其元数据存储在RSM系统上，如Chronze [17]或ZooKeeper [5]。因此，保护RSM系统免受存储故障（如数据损坏）的影响将提高许多依赖系统的可靠性。我们首先通过开发RSM恢复分类来描述处理存储故障的不同方法，通过对先前研究提出的实际系统和方法进行实验和定性分析（第2节）。我们的分析表明，目前部署的系统所采用的大多数方法不使用任何协议级的知识来执行恢复，导致灾难性的结果，如数据丢失和不可用。因此，为了提高RSM系统对存储故障的弹性，我们设计了一种新的协议感知恢复方法，我们称之为容错复制或CTR l（第3节）。CTR l由两部分组成：本地存储层和分布式恢复协议;当存储层可靠地检测故障时，分布式协议从冗余副本中恢复故障数据这两个组件都仔细利用RSM特定的知识来确保安全性（例如，无数据丢失）和高可用性。CTR l应用了几种新颖的技术来实现安全性和高可用性。例如，存储层中的崩溃损坏解纠缠技术将崩溃引起的损坏与磁盘故障区分开来;如果没有这种技术，可能会导致安全违规或不可用。接下来，分布式恢复中的全局提交确定协议将已提交项与未提交项分开;这种分离是至关重要的：虽然恢复错误的已提交项对于安全性是必要的，但快速丢弃未提交项对于可用性至关重要。最后，一个新的领导者发起的快照机制，使相同的快照跨节点，大大简化了恢复。协议感知恢复第二十一ACM Transactions on Storage，Vol.号143、第二十一条。出版日期：2018年10月我们在两个基于不同共识算法的存储系统中实现了CTRl：LogCabin [45]（基于Raft[53]）和ZooKeeper [5]（基于ZAB [41]）（第4节）。通过实验，我们表明，CTR l版本提供安全性和高可用性的存储故障的存在下，而原来的系统仍然不安全或不可用，在许多情况下，我们还表明，CTR l诱导最小的性能开销（第5节）。2背景和动机我们首先提供存储故障和RSM系统的背景。然后，我们提出了不同的方法来处理RSM系统中的存储故障的分类。2.1分布式系统中的存储故障闪存和闪存设备表现出微妙而复杂的故障模型：几个数据块可能无法访问或被悄悄损坏[9，10，34，63]。虽然这种存储故障与整机故障相比是罕见的，但在大规模分布式系统中，即使是罕见的故障也会变得普遍[64，66]。因此，可靠地检测存储故障并从存储故障中恢复至关重要。存储故障的发生有几个原因：介质错误[11]，程序/读取干扰[64]，固件[10]，设备驱动程序[70]和文件系统[29，30]中的错误存储故障以两种方式表现：块错误和损坏。当设备内部检测到块的问题并在访问时抛出错误时，就会对闪存[35，64]和硬盘[11，63]的研究由于设备可能无法检测到丢失和错误定向的写入，因此可能会发生损坏。研究[10，54]和轶事证据[38，39，61]显示了现实世界中数据腐败的普遍性。许多本地文件系统在遇到存储故障时，简单地将故障传播到应用程序[12，57，68]。例如，如果底层设备块被损坏，ext4会默默地返回损坏的数据。相反，一些文件系统会将一个潜在的错误转换成另一个错误;例如，如果被访问的块在设备上损坏，btrfs会向应用程序返回一个错误。在任何一种情况下，构建在本地文件系统上的存储系统都应该处理损坏的数据和存储错误，以保持端到端的数据完整性。解决存储故障的一种方法是使用类似RAID的存储在每个节点上维护多个数据副本。然而，许多分布式部署希望使用廉价的磁盘[23，33]。考虑到分布式系统中的数据本质上是复制的，在每个节点上存储多个副本是浪费的。因此，对于分布式系统来说，使用固有的冗余来从存储故障中恢复是很重要的。2.2基于RSM的存储系统我们的目标是加强RSM系统的存储故障。在RSM系统中，一组节点通过在状态机（每个节点上的内存数据结构）上执行命令来计算相同的状态[62]。通常，客户端与单个节点（leader）交互以在状态机上执行操作在接收到命令时，领导者将命令持久地写入磁盘日志并将其复制到跟随者。当大多数节点在其日志中持久保存命令时，leader将命令应用于其状态机并将结果返回给客户端;此时，命令已提交。日志中的命令必须按顺序应用于状态机。丢失或拒绝提交的命令会违反状态机的安全属性复制的日志通过一个共识协议（如Paxos [43]，ZAB [41]或Raft [53]）在节点之间保持一致由于日志可以无限增长并耗尽磁盘空间，因此会定期将内存中状态机的快照写入磁盘，并对日志进行垃圾收集。当节点在崩溃后重新启动时，它会通过读取最新的磁盘快照和日志来恢复系统状态节点第二十一R. Alagappan等人ACM Transactions on Storage，Vol.号143、第二十一条。出版日期：2018年10月图1.一、 示例场景。 该图显示了当前方法失败的示例场景。 羽毛是有条纹的. 崩溃和滞后节点分别显示为灰色和空框还恢复其关键元数据（例如，日志开始索引）。因此，每个节点维护三个关键的持久数据结构：日志、快照和元信息。这些持久性数据结构可能由于存储故障而损坏。实际系统试图安全地恢复数据，并在这种故障下保持可用[16，18]。然而，正如我们将要展示的，目前没有一种方法可以正确地从存储故障中恢复，这就需要一种新的方法。2.3RSM恢复分类为了理解处理RSM系统中存储故障的不同可能方法，我们分析了广泛的方法。我们通过两种方式进行这种分析：首先，我们使用我们开发的故障注入框架（第5节）分析实际系统，包括ZooKeeper，LogCabin等[27]和基于Paxos的系统[26];其次，我们分析先前研究提出的技术或专有系统中使用的技术[16，18]。通过我们的分析，我们将这些方法分为两类：协议无关和协议感知。不经意的方法不使用任何协议级的知识来执行恢复。在检测到故障时，这些方法在故障节点上本地采取恢复动作;这些动作以不安全的方式与分布式协议交互，导致数据丢失。协议感知的方法使用一些特定于RSM的知识来恢复;然而，它们没有正确地使用这些知识，从而导致不期望的结果。我们的分类法并不完整，因为可能还有其他技术;然而，据我们所知，除了我们的分类法之外，我们还没有观察到其他方法。为了说明这些问题，我们使用图1。在所有情况下，提交日志条目11、2和3丢失这些物品将违反安全规定。表1显示了每种方法在图1的如表中所示，所有当前方法都导致违反安全性（例如，数据丢失）、低可用性或两者。有效使用冗余的恢复机制应该在所有情况下都是安全和可用的。表1还比较了其他方面的方法，如性能、维护开销（干预和额外节点）、恢复时间和复杂性。尽管图1只显示了日志中的错误，但该分类法适用于其他结构，包括快照和元信息。无检测。对存储故障最简单的反应是根本没有：信任存储堆栈中的每一层都能可靠地工作。例如，一些基于Paxos的原型系统[26]不对磁盘上的数据使用校验和;同样，LogCabin也不使用校验和保护其快照。NoDetection轻微地违反了安全性;损坏的数据可以被遗忘地提供给客户端。但是，部署的系统确实对大多数磁盘上的数据使用校验和其他完整性策略。1日志条目包含状态机命令和数据。协议感知恢复第二十一ACM Transactions on Storage，Vol.号143、第二十一条。出版日期：2018年10月意识表1. 恢复分类类方法安全可用性性能不干预无额外节点快速恢复低复杂度（一）（二）（三）（四）（五）（六）协议无感知无检测崩溃截断删除重建√×××√√×√√√√√√√√×√×√√√√√nana××√√√√√EUCCECLEUCCECLEULLEULL议定书标记非投票重新配置拜占庭金融时报√×√√××√×√√×√×√×√××n×a√√√×UUUCCCUUUCCUUUUUUUCT rlCCCCCCE-返回损坏，L-数据丢失，U-不可用，C-正确。该表显示了不同方法在图1场景中的表现。虽然所有方法都不安全或不可用，但CTR l确保了安全性和高可用性。图二、 安全违规案例该图显示了使用截断方法暴露安全违规的事件序列。个碰撞测试更好的策略是使用校验和并处理I/O错误，并在检测到故障时使节点崩溃。崩溃似乎是一个很好的策略，因为它旨在防止故障节点可能对系统造成的任何损害。我们的实验表明，Crash方法是常见的：LogCabin，ZooKeeper和etcd有时会在日志出错时崩溃此外，ZooKeeper在快照损坏时会崩溃。虽然Crash保留了安全性，但它存在严重的不可用性。假设节点可能由于其他故障而不可用，即使是单个存储故障也会导致不可用，如图1（i）所示。类似地，单个故障即使在数据的不同部分上也是大多数（例如，图1（v））使系统不可用。请注意，简单地重新启动节点并没有帮助;与其他故障不同，存储故障可能是持久性的：节点将遇到相同的故障并再次崩溃，直到手动干预，这很容易出错并可能导致数据丢失。因此，希望自动恢复。截断。更复杂的操作是截断（可能有错误的）部分数据并继续操作。Truncate背后的直觉是，如果错误数据被丢弃，节点可以继续运行（与Crash不同），从而提高可用性。但是，我们发现截断可能会导致违反安全性（数据丢失）。考虑图2所示的场景，其中条目1在S1上损坏;S4、S5滞后并且没有任何条目。第二十一R. Alagappan等人ACM Transactions on Storage，Vol.号143、第二十一条。出版日期：2018年10月假设S2是领导者。当S1读取其日志时，它检测到损坏;然而，S1截断其日志，丢失损坏的条目和所有后续条目（图2（ii））。与此同时，S2（领导者）和S3崩溃.S1、S4和S5形成多数，并选举S1为领导者。现在，系统不知道已提交的条目1、2和3，从而导致静默数据丢失。系统还提交新条目x、y和z来代替1、2和3（图2（iii））。最后，当S2和S3恢复时，它们遵循S1总之，尽管故障节点检测到损坏，但它会截断其日志，从而丢失本地数据。当这个节点与其他落后的节点一起形成多数时，数据会悄悄地丢失，从而违反安全性。我们在ZooKeeper和LogCabin中发现了这种安全违规行为此外，Truncate遭受低效率的恢复。例如，在图1（i）中，S1在故障后截断其现在要修复S1ZooKeeper和LogCabin都存在恢复缓慢的问题。删除重建。另一个常用的操作是手动删除故障节点上的所有数据并重新启动该节点。不幸的是，与Truncate类似，DeleteRebuild可能会违反安全性：数据被删除的节点可能会与落后的节点一起形成多数，从而导致无声的数据丢失。令人惊讶的是，管理员经常使用这种方法，希望通过从其他节点获取数据来“简单地修复”故障节点DeleteRebuild也遭受类似于Truncate的恢复缓慢问题。MarkNonVoting. 在Google基于Paxos的系统中使用的这种方法中，故障节点删除其故障上的所有数据，并将自己标记为无投票权的成员;节点不参与选举，直到它观察到一轮共识并从其他节点重建其数据。通过将故障节点标记为无表决，可以避免图2中的安全违规。然而，MarkNonVoting有时会违反安全性，正如先前的工作所指出的那样[74]。不安全的根本原因是损坏的节点删除其所有状态，包括给予领导者的承诺2。一旦一个错误节点失去了给新领导者的承诺，它就可以接受来自旧领导者的条目然而，新领导者仍然相信它有来自故障节点的承诺，因此可以覆盖先前由旧领导者提交的条目此外，这种方法的缺点是不可用。例如，当只有大多数节点存活时，单个故障可能导致不可用，因为故障节点不能投票;其他节点现在不能选举领导者。重新配置在这种方法中，删除一个故障节点并添加一个新节点。但是，要更改配置，配置条目需要由多数人提交。因此，系统在许多情况下仍然不可用（例如，当大多数节点存活但一个节点的数据被破坏时）。虽然在实际系统中不使用重新配置来解决存储故障，但先前的研究已经提出了[16，46]。BFT。一种极端的方法是使用拜占庭容错算法，该算法在理论上应该容忍存储故障。然而，BFT在实际存储系统中的使用成本很高;具体而言，BFT只能实现容错协议所能实现的吞吐量的一半[22]。此外，BFT需要3个f+ 1节点来容忍f个故障[1]，因此在图1中的大多数场景中保持不可用。[2]在Paxos中，对编号为p的提议的承诺是由跟随者（接受者）向领导者（提议者）做出的保证，保证它将来不会接受编号小于p的提议协议感知恢复第二十一ACM Transactions on Storage，Vol.号143、第二十一条。出版日期：2018年10月Taxonomy Summary. 目前的方法都没有有效地使用冗余来从存储故障中恢复。大多数方法不使用任何协议级别的知识来恢复;例如，Truncate和DeleteRebuild在故障节点上本地采取行动，因此以不安全的方式与分布式协议交互，导致全局数据丢失。虽然一些方法（例如，MarkNonVoting）使用一些特定于RSM的知识，他们没有正确地这样做，导致数据丢失或不可用。因此，为了确保安全性和高可用性，恢复方法应该通过利用特定于协议的知识来有效地使用冗余。此外，避免诸如手动干预和缓慢恢复的其他问题是有益的。我们的协议感知方法CTR l旨在实现这些目标。3容错复制设计正确的恢复机制需要仔细了解系统的底层协议。例如，恢复机制应该知道如何对复制的数据执行更新以及如何选举领导者。我们将CTR l领导者为基础。单个节点充当领导者;对复制数据的所有数据更新都只通过领导者。时代。RSM系统将时间划分为称为epoch的逻辑单元。在任何一个特定的时代，只有一个领导者是保证存在的。每个数据项都与它被追加的时期及其在日志中的索引相关联。由于条目只能由领导者提出，并且对于一个历元只能存在一个领导者，因此（历元，索引）对唯一地标识日志条目。领导者的完整性如果一个节点拥有比候选者更多的最新数据，它将不会投票给候选者。由于提交的数据至少存在于大多数节点中，并且需要多数投票才能赢得选举，因此保证领导者拥有所有提交的数据。虽然在一些协议中没有明确规定，但如先前研究所证实的，大多数系统都满足此属性[3，53]。上面列出的属性对于大多数RSM系统实现是通用的。CTR l利用这些常见的协议级属性来正确地从存储故障中恢复。然而，CTR 1不能容易地应用于少数共识方法。例如，Paxos [50]的一些实现允许更新同时流经多个leader。我们相信CTR 1也可以扩展到与这样的RSM变体一起工作。我们将此扩展作为今后工作的一个途径。CTR l将恢复责任划分为两个组件：本地存储层和分布式恢复协议;存储层可靠地检测节点上的错误数据，而分布式协议则从冗余副本中恢复数据。这两个组件都使用特定于RSM的知识来执行其功能。在本节中，我们首先描述CTR l然后我们描述本地存储层（3.3节）。最后，我们将分两部分描述CTR l3.1故障模型我们的故障模型包括容错RSM系统所做的标准故障假设：节点可能在任何时候崩溃，稍后恢复，节点可能由于网络故障而无法访问[22，44，53]。我们的模型增加了另一个现实的故障场景，其中各个节点上的持久数据可能被损坏或无法访问。表2显示了我们的存储故障模型的摘要我们的模型包括用户数据和文件系统元数据块中的错误第二十一R. Alagappan等人ACM Transactions on Storage，Vol.号143、第二十一条。出版日期：2018年10月表2.存储故障模型故障结果可能原因数据损坏的数据错误定向并丢失了ext中的写入不可访问数据LSE，在RAID和btrfsFS元数据缺少文件/目录目录项损坏，fsck可能会删除错误的inode取消文件/目录inode损坏后，健全性检查失败，权限位损坏文件与更多或更少的字节inode中的i_size字段已损坏文件系统只读日志损坏; fsck未运行文件系统不可安装超级块损坏; fsck未运行该表显示了我们的模型中包含的存储故障以及导致故障结果的可能原因实现系统持久结构的文件中的用户数据块可能会受到错误或损坏的影响。如研究所示，许多（可能是连续的）数据块可能是错误的[13，63]。此外，块的几个比特/字节可能被损坏。根据所使用的本地文件系统，损坏的数据可能会被立即返回或转换为错误。文件系统元数据块也可能受到故障的影响;例如，日志文件的inode可能已损坏。我们的故障模型考虑了以下可能由文件系统元数据故障引起的结果：文件/目录可能丢失，文件/目录可能无法安装，文件可能以更少或更多的字节出现，文件系统可能以只读方式安装，以及在最坏的情况下，文件系统可能无法安装。一些文件系统，如Linux，可能会掩盖应用程序的大部分上述结果[76];然而，我们的模型包括这些错误的结果，因为它们实际上可能发生在提供较弱的防损坏保护的其他文件系统上（例如，ext2/3/4）。通过故障注入测试，我们已经验证了表2所示的元数据故障结果确实发生在ext4上。3.2安全性和可用性保证CTR l保证，如果提交的数据项至少存在一个正确的副本，它将被恢复或系统将等待该项目被修复;提交的数据将永远不会丢失。在不太可能的情况下，提交项的所有副本都有错误，系统将正确地保持不可用。CTR l还保证系统将尽可能早地对未提交的错误项做出决定，从而确保高可用性。3.3CTRL本地存储层为了可靠地恢复，存储层（Cls toRE）需要满足三个关键要求。首先，Cls torRE必须能够可靠地检测存储故障。第二，Cls toRE必须正确区分崩溃和损坏;否则会违反安全性第三，Cls toRE必须识别出哪些数据是错误的;只有当Cls toRE识别出哪些数据受到了影响，分布式协议才能恢复这些数据。3.3.1持久结构概述。 正如我们所讨论的，RSM系统维护三个持久化结构：日志、快照和元信息。CLs使用特定于RSM的关于如何使用和更新这些结构的知识来执行其功能。例如，Cls可以根据RSM数据结构以不同的粒度检测故障：日志中的故障是以各个条目的粒度检测的，而快照中的故障是以块的粒度检测的类似地，Cls toRE使用特定于RSM的知识，即日志条目是唯一限定的通过其（epoch，index）对来识别错误日志条目。协议感知恢复第二十一ACM Transactions on Storage，Vol.号143、第二十一条。出版日期：2018年10月图3.第三章。 日志格式。（a）示出了典型的RSM系统中的日志的格式和用于更新日志的协议;（b）示出了Cls tore的相同格式。Log. 日志是一组包含一系列条目的文件。典型的RSM日志格式如图3（a）所示。日志在关键路径中同步更新;因此，对日志格式所做的更改不应影响其更新性能。Cls toRE使用如图3（b）中所示的修改后的格式来实现这一目标。损坏的日志以单个条目的粒度恢复。快照。内存中状态机定期写入快照。由于快照可能很大，Cls会将它们拆分为块;错误快照会以单个块的粒度恢复。Metainfo。元信息的特殊之处在于不能从其他节点恢复故障元信息。这是因为元信息包含对节点唯一的信息（例如，它当前的时代，给予候选者的投票）;从其他节点恢复遗忘的元信息可能违反安全性。Cls要正确地使用这些知识，因此在本地维护元信息的两个副本;如果一个副本有缺陷，另一个副本被使用。幸运的是，元信息只有几十个字节因此，维持两份副本不会产生很大的管理费用。3.3.2检测故障数据。 Cls toRE使用众所周知的检测技术：不可访问通过捕捉返回码来检测数据（例如，EIO），并且通过校验和不匹配检测损坏的数据。ClstoRE假设如果一个项目及其校验和一致，则该项目没有错误。在日志中，每个条目都受到校验和的保护;类似地，快照中的每个块和整个元信息都经过校验和。clstore还处理文件系统元数据错误。通过打开时处理错误代码来检测丢失和未恢复的文件/目录。具有较少或较多字节的日志和元信息文件很容易被检测到，因为这些文件是预先分配的，并且具有固定大小;快照大小单独存储，Cl会将存储的大小与文件系统报告的大小进行交叉检查，以检测差异。只读/不可挂载文件系统相当于丢失的数据目录。在大多数文件系统元数据错误的情况下，Cls会使节点崩溃在元数据故障时可靠地崩溃可以保持安全性，但会影响可用性。然而，我们认为这是一个可以接受的行为，因为数据块比元数据块多得多;因此，元数据的错误概率明显低于数据块。3.3.3解开日志中的崩溃和损坏。当检测日志中的损坏时，出现了一个有趣的挑战。日志项的校验和不匹配可能由两种不同的情况引起。首先，系统可能在更新过程中崩溃;在这种情况下，条目将被部分写入，从而导致不匹配。第二，条目可以安全地持久化，但在以后会被破坏。大多数基于日志的系统将这两种情况混为一谈：第二十一R. Alagappan等人ACM Transactions on Storage，Vol.号143、第二十一条。出版日期：2018年10月一个不匹配的崩溃[32]。如果不匹配，它们将丢弃损坏的条目和所有后续条目，从而丢失数据。由于这种合并而丢弃条目可能会导致全局数据丢失（如前面的图2所示）。请注意，如果不匹配确实是由于崩溃造成的，那么丢弃部分写入的条目是安全的。它是安全的，因为节点不会向任何外部实体确认它已写入条目。然而，如果条目被破坏，则不能简单地丢弃该条目，因为它可以被全局提交。此外，如果可以正确地将不匹配归因于崩溃，则可以在本地快速丢弃错误条目，从而避免分布式恢复。因此，本地存储层区分这两种情况很重要。为了表示一个操作的完成，许多系统会写一个提交记录[14，19]。类似地，Cls toRE在写入条目ei之后写入持久记录pi。现在，假设ei在pi之前排序，即，附加条目ei的步骤序列是write（ei）、f sync（）、write（pi）、f sync（）。在ei的校验和不匹配时，如果pi不存在，我们可以得出结论，系统在更新期间崩溃。相反，如果pi存在，我们可以得出结论，不匹配是由于损坏而不是由于崩溃造成的。P1是校验和的，并且非常小;它可以原子地写入，因此不会由于崩溃而如果除了ei之外，pi也被损坏，我们可以得出结论，这是一个损坏而不是崩溃。当ei在pi之前排序时，上述逻辑有效。但是，这种排序在关键路径中需要（额外的）昂贵的fsync，从而影响日志更新性能。由于这个原因，Cls toRE不会将ei排序在pi之前;因此，append协议是t1：write（ei），t2：write（pi），t3：f sync（）。3给定此更新序列，假设对于ei发生校验和不匹配。如果pi不存在，则Cls toRE可以断定它是崩溃（在t2之前）并且丢弃ei。因此，如果pi存在，则有两种可能性：ei可能在t3之后受到损坏的影响，或者可能在t2和t3之间发生崩溃，其中pi击中磁盘，而ei仅被部分写入。第二种情况是可能的，因为文件系统可以在两个fsync操作之间重新排序写入，并且ei可以跨越多个扇区[3，20，55，56]。如果存在ei+1或pi+1，则Cls torRE但是，如果ei是最后一个条目，那么我们无法确定它是崩溃还是损坏。这一主张的证据可以在附录A中找到。当最后一个条目的持久化记录存在时，不能解开它并不是Cls所特有的，而是基于日志的系统中的一个基本限制。例如，在ext4即使可以解决崩溃和损坏，单机系统也几乎无法恢复损坏的数据。但是，在分布式系统中，可以使用冗余副本进行恢复。因此，当最后一个条目不能被解开时，Cls将安全地将该条目标记为损坏的，并将其留给分布式恢复来基于全局提交来修复或丢弃该条目纠缠问题不会出现快照或元信息。这些文件首先被写入一个临时文件，然后原子地重命名。如果在重命名之前发生崩溃，则部分写入的临时文件将被丢弃。因此，系统将永远不会看到由于崩溃而损坏的快照或元信息;如果这些结构损坏，则是由于存储损坏。3.3.4识别故障数据。一旦检测到有故障的物品，就必须对其进行识别;只有当Cls torRE可以识别出有故障的物品时，分布式层才可以恢复该物品。为此目的，Cls冗余地存储与项目本身分开的项目的标识符;仅复制标识符而不是整个项目避免了（2×）存储和性能开销。然而，在这方面，3最终的fsync是持久性所必需的。协议感知恢复第二十一ACM Transactions on Storage，Vol.号143、第二十一条。出版日期：2018年10月（）下一页（）下一页图四、 分布式日志恢复 图中显示了C语言的日志恢复操作。除非明确提及，否则所有条目都附加在epoch 1中。 对于附加在其他历元中的条目，历元编号显示在上标中。显示为条纹框的产品有缺陷。一个节点周围的灰色方框表示它是下降或非常慢。领导人在左边标有L日志索引显示在顶部。将标识符存储在项目附近的用处不大;错误定向的写入可能会损坏项目及其标识符[10，11]。因此，标识符与它们所标识的物项在物理上是分开的。epoch，index对用作日志条目的标识符，并单独存储在日志的头部，如图3（b）所示。条目的偏移量也被存储为标识符的一部分，以允许遍历故障上的后续条目。日志条目的标识符也方便地用作其持久记录。类似地，对于快照块，snap-index，chunk#对用作标识符;snap-index和快照大小存储在与快照文件不同的文件中。标识符具有标称存储开销（日志条目为32字节，快照为12字节），可以原子地写入，并且还受校验和保护。物品及其标识符都有故障的可能性很小，因为它们在物理上是分开的[10，11，13，63]。在这种不太可能和不幸的情况下，Cls会使节点崩溃以保护安全。表3（第二列）总结了Cls toRE3.4CTRL分布式日志恢复本地存储层检测错误数据项并将其标识符传递给分布式恢复层。我们现在描述分布式层如何使用特定于RSM的知识从冗余副本中恢复已识别的故障项我们首先描述如何恢复日志条目，然后描述快照恢复。正如我们所讨论的，metainfo文件是在本地恢复的，因此我们不再进一步讨论它们我们使用图4来说明日志恢复是如何朴素的方法：领导者限制。 RSM系统不允许日志不完整的节点成为领导者。从存储故障中恢复的一种简单方法可能是对选举施加额外的约束：如果一个节点的日志包含一个错误的条目，则。朴素方法背后的直觉如下：由于leader保证拥有所有提交的数据，并且我们的新限制确保leader没有错误，因此可以使用leader上的相应条目来修复其他节点上的错误日志条目案件（a）㈠第二十一R. Alagappan等人ACM Transactions on Storage，Vol.号143、第二十一条。出版日期：2018年10月（）下一页（）下一页（）下一页图4中的（a）（ii）显示了朴素方法可以选出领导者的场景。在（a）（i）中，只有S1可以成为领导者，因为其他节点要么落后，要么至少有一个错误条目。假设S1也是情况（a）（ii）中的领导者。修复追随者的错误。当领导者没有错误的条目时，修复追随者是直接的。例如，在情况（a）（i）中，跟随者通知S1他们的错误条目;S1然后提供正确条目。然而，有时候领导者可能不知道追随者正在查询的条目。例如，在情况（a）（ii）中，S5在索引3处具有错误条目，但是具有不同的时期。这种情况是可能的，因为S5可能是epoch 2的领导者，并在添加条目后立即崩溃。如前所述，条目由其历元索引唯一标识;因此，当查询错误条目时，节点除了其索引之外还需要指定条目的历元。因此，S5通知领导者其进入时期：2，索引：3是错误的。但是，S1在其日志中没有这样的条目.如果leader没有follower拥有的条目，则该条目必须是未提交的条目，因为leader保证拥有所有已提交的数据;因此，leader指示S5截断错误条目，并复制正确条目。虽然朴素的方法保证了安全性，但它存在可用性问题。在（b）所示的情况下，该系统将无法使用：由于日志的活动节点是故障或滞后的。请注意，即使是单个存储故障也可能导致不可用，如（b）（i）所示精心设计的恢复协议可以在这些情况下提供更好的可用性具体而言，由于存在所有提交条目的至少一个完整副本，因此可以共同重建日志。3.4.1安全解除限制。为了从图4（b）中的场景中恢复过来，我们删除了对选举的额外约束。具体地说，任何具有更新日志的节点现在都可以被选为领导者，即使它有错误的条目。这种放松提高了可用性;然而，出现了两个关键问题：第一，什么时候错误的领导者可以继续接受新的命令？第二，也是更重要的一点，选举一个有故障的节点作为领导节点是否安全？要接受新命令，leader必须将命令附加到日志中，复制它，并将它应用到状态机。但是，在应用新命令之前，必须应用所有以前具体地说，错误的命令不能被跳过并在修复后应用;这种无序的应用将违反安全性。因此，在leader可以接受新命令之前，它需要修复其错误条目。因此，为了提高可用性，leader需要尽早修复其错误条目。为了确保安全，恢复的关键部分是使用followers上的冗余副本修复leader的日志。在诸如（b）（i）和（b）（ii）的简单情况下，领导者S1可以使用来自跟随者的正确条目来修复其错误条目epoch：1，index然而，在一些场景中，领导者不能立即恢复其错误条目;例如，可到达的跟随者中没有一个可能知道要恢复的条目，或者要恢复的条目也可能在跟随者上有错误。3.4.2确定承诺。安全快速修复leader错误日志的主要见解此外，立即丢弃未提交的错误条目对于可用性至关重要。例如，在情况（c）（i）中，S1上的错误条目不能被修复，因为没有它的副本;等待修复该条目会导致不确定的不可用。有时，一个条目可能被部分复制，但仍然未提交;例如，在情况（c）（ii）中，S1上的错误条目被部分复制，但没有被提交。协议感知恢复第二十一ACM Transactions on Storage，Vol.号143、第二十一条。出版日期：2018年10月（）下一页（）下一页（）下一页（）下一页忠诚虽然有可能从另一个节点（S2）恢复这个条目，但这不是安全所必需的;对于领导者来说，丢弃这个未提交的条目是完全安全的为了确定错误条目的提交，leader询问followers。如果大多数追随者回应他们没有条目（否定确认），那么领导者得出结论，条目是未提交的。在这种情况下，leader安全地丢弃该条目和所有后续条目;丢弃后续条目是安全的，因为条目仅按顺序提交（即，如果索引i处的条目是未提交条目，则i之后的所有条目也必须是未提交条目）。相反，如果条目被提交，那么大多数节点中至少