有道云笔记链接译文
摘要
我们介绍了一致性感知持久性性或CAD，这是分布式存储中一种新的持久性方法，它可以在提供高性能的同时实现强一致性。我们通过设计跨客户端的单调读取来展示这种方法的有效性，它是一种新颖的强一致性属性，它在基于领导者的系统中提供跨故障和会话的单调读取。我们构建了ORCA，这是ZooKeeper的一个修改版本，实现了CAD和跨客户端单调读取。我们的实验表明，ORCA在提供强一致性的同时，与弱一致性的ZooKeeper的性能紧密匹配。同强一致性的ZooKeeper相比，ORCA显著性地提供了更高的吞吐量(1.8–3.3×)，并显著降低了延迟，有时在地理分布的环境下，延迟降低了一个数量级。1 介绍
分布式存储研究和实践的一个主要焦点是系统提供的一致性模型。许多模型，从线性化[20]到最终的一致性[16]，中间有几个点[27，29，30，48-50]，都已经被提出、研究过了，并且相当好理解。
尽管进行了多年的研究，但很少有人注意到分布式系统的底层持久性模型，对一致性和性能都有很大影响。在一个极端的情况下，同步持久性要求在确认之前在许多节点上进行复制和坚持写操作。这种模型经常被用来实现强一致性。例如，为了防止过时的读取，一个可线性化的系统(如LogCabin[28])会同步地使写持久化；否则，一个已确认的更新可能会丢失，在后续的读中暴露出过时的值。同步持久性避免了这种情况，但代价很高：性能差。即使是在性能增强的情况下，如批处理，也会迫使写入被复制和持久化，从而重新降低吞吐量，并大幅增加延迟。
另一个极端是异步持久性：每一次写入都只是被动地复制和持久化，也许只是在一个节点的内存中缓冲之后。异步持久性被用在一致性模型较弱的系统中（如Redis[42]）；通过快速确认写入，实现了高性能，但这种模型会导致弱语义，将过时和失序的数据暴露给应用程序。
在本文中，我们提出以下问题：对于持久层来说，是否可能实现强一致性，同时也提供高性能？我们表明，如果精心设计持久性层，特别是考虑到系统打算实现的一致性模型，就有可能实现这一目标。我们将这种方法称为一致性感知持久性或CAD。我们展示了如何通过让持久性层感知到这个模型来实现高性能的跨客户端单调性读取，这是一种新的强一致性属性。如果没有一致性感知层，跨客户端单调性就无法高效实现：同步持久性可以实现它，但速度很慢；异步耐久性后根本无法实现。在本文中，我们在基于领导者的复制系统中实现了CAD和跨客户端单调性读取。
跨客户端单调读取保证了从客户端读取的状态至少与之前从任何客户端读取时返回的状态是一样新的，不管是否有故障，也不管是否跨会话。为了有效地实现这一特性，CAD将持久性的点从写转移到读：数据在读之前被复制和持久化。通过延迟写的持久性，CAD实现了高性能；但是，通过在读之前使数据持久化，CAD实现了跨故障的单调读。CAD不会在每次读取时产生开销；对于许多工作负载，可以在应用程序读取数据之前在后台使数据持久化。虽然实现了强一致性，但CAD并不能保证完全不丢失数据；如果出现故障，最近写的一些尚未读取的项目可能会丢失。然而，考虑到许多被广泛使用的系统采用异步持久性，从而满足于较弱的一致性[32，43，44]，CAD为这些系统提供了一条在不影响性能的情况下实现更强一致性的路径。
现有的可线性化系统确实提供了跨客户端单调读取。然而，为了做到这一点，除了使用同步持久性之外，大多数系统还将读取限制在领导者身上[23，34，38]。这样就限制了读取吞吐量，并且阻止客户端从附近的副本中读取，增加了延迟。相反，我们展示了一个存储系统如何在允许从多副本处读取的同时实现这一特性。这样的系统可以实现从附近副本的低延迟读取，使其特别适合于地理分布式设置。此外，这样的系统在边缘计算用例中也是有益的，在这些用例中，客户端可能会在应用生命周期内连接到不同的服务器（例如，由于移动性[41]），但仍然可以在这些会话中接收单调的读取。
我们通过修改ZooKeeper[3]，在一个名为ORCA的系统中实现了CAD和跨客户端单调读取。ORCA应用了许多新颖的技术来实现高性能和强保证。例如，持久性检查机制有效地将读取非持久性项目的请求和访问持久性项目的请求分开。其次，基于租约的主动集技术保证了单调的读取，同时允许在许多节点进行读取。最后，两步断租机制有助于正确管理活动集成员。
我们的实验表明，带有CAD的ZooKeeper比同步持久的ZooKeeper（经过批处理优化）速度要快得多，同时在许多工作负载上接近异步持久的ZooKeeper的性能。即使对于主要是读取最近写入数据的工作负载，CAD的开销也很小（只有8%）。通过允许在许多副本处进行读取，ORCA与强一致ZooKeeper（strong-ZK）相比，提供了显著更高的吞吐量（1.8-3.3×）。在地理分布式的环境中，通过允许在附近的副本上进行读取，ORCA在很多情况下比strong-ZK低14倍的延迟，同时提供强大的保证。ORCA也与弱一致性ZooKeeper（weak-ZK）的性能接近。我们通过严格的测试表明，ORCA在由故障注入器产生的数百个故障序列下提供跨客户端单调读取；相反，weak-ZK在许多情况下返回非单调状态。我们还演示了ORCA提供的保证如何在两个应用场景中发挥作用。
2 动机
在本节中，我们将讨论强一致性如何要求同步持久性，并且如何才能在异步持久性之上建立弱一致性。2.1 同步持久性之上的强一致性
实现强一致性需要同步的持久性。例如，考虑线性化，这是复制系统能够提供的最强保证。一个可线性化的系统在读取时提供了两个特性。首先，它可以防止客户端看到非单调的状态：系统不会在某一时刻为客户端提供一个更新的状态，随后为任何客户端提供一个旧的状态。其次，保证读取时能看到最新的更新：陈旧的数据永远不会暴露。然而，为了在读时提供如此强大的保证，可线性化系统必须同步复制和持久化写[25]；否则，系统会在故障时丢失数据，从而暴露出不一致的状态。例如，在基于多数派的可线性化系统中(例如，LogCabin)，领导者同步复制到多数派，而节点则刷新到磁盘(例如，通过发出fsync)。有了这样的同步持久性，即使在所有服务器崩溃和恢复时，可线性化系统也能保持可用，并提供强有力的保证。
不幸的是，这样的强保障是以性能为代价的。如表1所示，具有同步多数复制和持久性的Redis比完全异步配置（其中写入只在领导者的内存上缓冲）慢10倍。虽然在某些系统中，批处理并发请求可能会提高吞吐量，但同步持久性从根本上讲会受到高延迟的影响。 表1：同步写入成本。该表显示了Redis中5个复制和8个客户端的同步写入的开销。箭头显示了与异步持久性相比的吞吐量下降。副本间通过10-Gbps链接连接，并使用SSD进行持久化。
同步持久性，虽然是必要的，但不足以防止非单调读取和过时的读却；需要额外的机制来保证。例如，除了使用同步的持久性，许多实用的线性化系统重新严格地将读取限制在领导者上[23，28，34，38]。然而，这样的限制严重限制了读取吞吐量；此外，它还阻止客户端从最近的副本读取，增加了读取延迟（尤其是在地理分布式环境中）。
2.1 异步持久性之上的弱一致性
考虑到同步持久化的成本，许多系统更喜欢异步持久化，其中的写入是被复制和持久化的。事实上，在广泛使用的系统中，这样的异步配置是默认的[32，44]（例如，Redis，Mon- goDB）。然而，通过采用异步持久性，正如我们接下来讨论的那样，这些系统满足于较弱的一致性。
大多数系统使用两种异步-持久化配置。在第一种情况下，系统同步复制，但延迟持久化数据（例如，ZooKeeper的forceSync[4]被禁用）。第二种，系统同时异步执行复制和持久化（例如，默认的Redis，它只在领导者的内存上缓冲更新）。
在异步持久化的情况下，系统会丢失数据，导致一致性差。令人惊讶的是，虽然数据复制在许多节点的内存中，当只有一个节点崩溃时，也会出现这种情况。考虑ZooKeeper的异步持久化，如图1(i)所示。一开始，大多数节点(S1、S2和S3)已经提交了一个项目b，在内存中缓冲；两个节点(S4和S5)操作缓慢，所以还没有看到b。当多数派节点(S3)崩溃并恢复时，它失去了b，然后S3与尚未看到b的节点形成多数派，并被选为领导者。【虽然丢失了数据的节点可以被排除在加入集群之外（比如在Viewstamped Replication[26]中），但这样的解决方案会影响可用性，实际系统不会采用这样的策略。】因此，系统默默地丢失了已提交的项目b，所以之前读取包含项目a和b的状态的客户端现在可能会注意到一个只包含a的旧状态，这就构成了非单调的读取。S1和S2上的完好副本也被新的领导者所取代。类似的情况在完全异步系统中也会出现，如图1(ii)所示。 图1：异步持久性之上差的一致性。(i)显示了异步持久化的系统发生故障时，非单调读取的结果。(ii)显示了异步复制和持久化系统的相同情况。灰色显示的数据项表示它们被持久化了。
从本质上讲，建立在异步持久性基础上的系统无法在故障的情况下实现强一致性特性。这样的系统可以在故障前服务于一个较新的状态，但在恢复后服务于一个较旧的状态，从而暴露出非单调性的读取。只有弱于线性化的模型，如因果一致性，才能建立在异步持久性之上；这种模型只有在没有故障的情况下，并且在单个客户端会话内提供单调读。如果客户端连接的服务器崩溃并恢复，客户端必须建立一个新的会话，在这个新的会话中，它可能会看到比上一个会话中看到的状态更旧的状态[30]。
弱一致性系统会暴露出非单调的状态，还因为它们通常允许在许多节点上进行读取[14]。例如，客户端在断开连接后可以重新连接到不同的服务器，如果有几个更新还没有复制到这个服务器上，可能会在新的会话中读取一个旧的状态。出于同样的原因，来自同一个应用程序的两个不同服务器的两个会话可能会收到非单调的状态。虽然上述情况在定义上并不违反因果一致性（因为是不同的会话），但却会导致应用的语义不佳。
总结我们到目前为止的讨论，同步持久性可以实现强一致性，但成本高的让人望而却步。异步持久性提供了高性能，但只能建立在弱一致性之上。接下来，我们将讨论如何通过精心设计存储系统的持久性层，在存储系统中同时实现强一致性和高性能这两个看似冲突的目标。
3 有CAD的强大且高效的一致性
我们在本文中的目标是设计一种持久性基元，在提供高性能的同时实现强一致性。为此，我们首先观察到异步持久性会在故障时任意丢失数据，因此阻止了非陈旧性和单调性读的实现。虽然防止陈旧性数据需要在每次写入时进行昂贵的同步持久性，但我们注意到，跨故障的单调读在许多场景下是有用的，并且可以有效地实现。我们设计了一致性感知持久性或CAD，这是一种新的持久性基元，可以实现这种高性能的强属性。
CAD的主要思想是允许异步完成写入，但在读取时强制执行持久性：数据在被客户端读取之前被复制和持久化。通过延迟写入的持久性，CAD实现了高性能。然而，通过确保数据在被读取之前是持久的，CAD可以实现单调的读取，甚至跨越故障。读取数据时，CAD并不总是产生开销。首先，对于许多工作负载来说，CAD可以在应用程序读取数据之前就在后台使数据持久化。此外，只有第一次读取非持久化的数据才会触发同步复制和持久化，后续的读取速度很快。因此，如果客户端在写完数据后不立即读取数据（这对许多工作负载来说是很自然的），CAD可以实现异步持久化的高性能，但可以实现更强的一致性。在客户端确实在写完后立即读取数据的情况下，CAD会产生开销，但能保证较强的一致性。
在CAD之后，我们实现了跨客户端单调读取，这是一个强大的一致性属性。这个属性保证了从一个客户端读取的状态，无论服务器和客户端是否故障，总是会返回一个至少和之前从任何客户端读取的状态一样新的状态，而且是跨会话的。线性化提供了这个属性，但性能不高。建立在异步持久性之上的较弱的一致性模型不能提供这个属性。请注意，与传统的只在一个会话内和没有故障的情况下保证单调性[10，30，49]的单调读取相比，跨客户端的单调性是一个更强的保证。
跨客户端单调读取在很多场景下都是有用的。举一个简单的例子，考虑一个服务托管的视频的观看次数；这样的计数器应该只是单调地增加。然而，在一个可能丢失已读取数据的系统中，客户端可能会注意到计数器的值似乎在倒退。作为另一个例子，在位置共享服务中，用户可能会错误地注意到另一个用户在路线上向后退了，而实际上，这种差异是由服务于更新位置的底层存储系统造成的，系统丢失了新位置的数据，因此后来又恢复到了一个旧的位置。提供跨客户端单调读取的系统可以避免这样的情况，提供更好的语义。
为了确保跨客户端的单调读取，大多数现有的可线性化系统将读取限制在领导者身上，影响了扩展能力并增加了延迟。相比之下，一个系统在提供这一特性的同时，允许在多个副本上进行读取，在许多用例中提供了有吸引力的性能和一致性特征。首先，它将负载分布在各个副本上，并使客户机能够从附近的副本读取，在地理分布的环境中提供低延迟的读取。其次，与可线性化系统类似，它提供了单调的读取，无论故障与否，是否跨客户端和会话，这对边缘的应用很有用[36]。边缘的客户端可能会经常断开连接，并连接到不同的服务器，但仍然可以在这些会话中获得单调的读取。
4 ORCA设计
我们现在描述ORCA，一个基于领导者的多数系统，它实现了一致性感知的持久性和跨客户端单调读取。我们首先对基于领导者的系统进行简要概述（§4.1），并概述ORCA的保证（§4.2）。然后，我们描述了CAD的基础机制（§4.3）。接下来，我们解释了我们如何实现跨客户端单调读取，同时允许在许多节点上读取（§4.4）。最后，我们解释ORCA如何正确地确保跨客户端单调读取（§4.5），并描述我们的实现（§4.6）。4.1 基于领导者的多数系统
在基于领导者的系统（如ZooKeeper）中，所有的更新都通过领导者来进行，领导者通过将更新存储在日志中，然后将更新复制给跟随者，从而建立了单一的更新顺序[21，39]。领导者与一个任期相关联：一个时间片，其中最多可以存在一个领导者[6,39]。每一次更新都是由它被附加的任期和它被添加在日志中的位置来唯一识别的。领导者不断向追随者发送心跳；如果追随者一段时间内没有收到领导者的消息，他们就会选出一个新的领导者。对于同步持久性，只有在大多数复制体(即n节点系统中的【n/2】（向下取整）+1节点)持久化更新后，领导者才会确认更新。对于异步持久性，在确认之前，更新要么只被缓冲在领导者的内存中（异步复制和持久化），要么在大多数节点上（异步持久化）。
当使用同步持久性并将读取限制在领导者上时，系统提供了线性化：保证读取能看到最新的更新并接收单调的状态。在异步持久性的情况下，当允许在所有节点上进行读取时，这些系统只提供顺序一致性[8]，即存在一个全局的操作顺序，但如果服务器崩溃和恢复，或者客户端从不同的服务器读取，读取可能是陈旧的和非单调的[8，38]。
4.2 故障模型和保证
与许多基于多数派的系统类似，ORCA打算只容忍故障恢复故障，而不是拜占庭故障[24]。在故障恢复模型中，节点可能在任何时候发生故障，并在稍后的时间点恢复。节点失败有两种方式，第一，它们可能会崩溃（例如，由于电源故障）；第二，它们可能会由于网络故障而分区。当一个节点从崩溃中恢复时，它失去了它的易失性状态，只剩下磁盘上的状态。在分区过程中，一个节点的易失性状态保持完整，但它可能没有看到其他节点的数据。保证。ORCA保留了基于领导者的系统使用异步持久性的特性，即它提供了顺序一致性。然而，除此之外，它还提供了在所有故障情况下（例如，即使所有副本崩溃并恢复），以及跨会话的跨客户端单调读取。ORCA与可线性化系统不同的是，它并不能保证读取永远不会看到陈旧的数据。例如，如果在写入数据后但在读取数据前出现故障，ORCA可能会丢失一些最近的更新，因此后续的读取可能会得到一个旧的状态。基于多数的系统只要多数节点正常工作，就能保持可用[7，39]；ORCA保证了同样的可用性水平。 图2：CAD持久性检查。该图展示了CAD的工作原理。灰色显示的数据项表示数据持久化。在(i)中，基线是完全异步的；在(ii)中，基线同步复制，但异步持久。一开始，当项目a是持久的，read(a)通过持久检查。然后，项目b和c被追加。读(b)的检查失败；因此，领导使状态持久后，它为b服务。 4.3 CAD持久层
在本节的剩余部分，我们使用异步持久性作为基线来强调CAD与它的不同之处。CAD的目标是与这个基线表现相似，但能实现更强的一致性。现在，我们提供关于CAD如何工作的直觉，并解释其机制；我们使用图2来实现。
4.3.1 更新
CAD保留了基线异步系统的更新路径，因为它的目的是在写入过程中提供相同的性能。因此，如果基线采用异步复制和持久化，那么CAD也会异步执行复制和持久化，将数据缓冲在领导者的内存中，如图2（i）所示。同理，如果基线同步复制但异步持久化，那么CAD在写入时也是如此，如图2(ii)所示。在CAD中，在保留更新路径的同时，领导者在后台不断复制更新，节点定期向磁盘刷新。接下来我们讨论CAD如何处理读操作。4.3.2 状态持久性保证
当一个项目i的读取被服务时，CAD保证直到修改i的最后一次更新的整个状态（即，甚至对其他项目的写入）是持久的。例如，考虑一个日志，如[a,b1,c,b2,d]；每个条目表示对某项的（非持久）更新，下标显示对某项进行了多少次更新。当项目b被读取时，CAD保证在服务b之前，至少到b2的所有更新都被做持久。因为CAD的目的是保存领导者建立的更新顺序（如基础系统所做的那样），所以CAD使整个状态持久，而不仅仅是项目。
当CAD在任何故障(包括所有副本崩溃和恢复的情况)以及在群集的所有连续视图中都可以恢复数据时，它认为该状态是持久的。基于多数的系统要求至少有多数节点形成新的视图（即选出一个领导者）并为客户提供服务。因此，如果CAD在至少大多数节点上安全地持久化数据，那么即使在故障后，任何大多数中的至少一个节点将拥有所有已被持久化的所有数据（即被客户端读取的数据），从而将存活到新视图中。因此，CAD认为当数据至少在大多数节点的磁盘上被持久化时，数据才是持久的。
4.3.3 处理读操作：持久性检查
当一个项目i的读取请求到达节点时，如果对i的所有更新都已经持久化了，节点可以立即从其内存中为i服务（如图2，对项目a的读取）；否则，节点必须采取额外的步骤使数据持久化。因此，节点首先需要能够确定对i的所有更新是否已经持久。
执行这种检查的一个朴素的方法是为每个项目维护有多少节点持久化了这个项目；如果至少有大多数节点持久化了一个项目，那么系统就可以为它服务。这种方法的缺点是，跟随者必须在每次响应中告知领导者他们已经持久化的项目集合，领导者必须在每次确认时更新集合中所有项目的计数。
CAD通过利用领导者建立的更新顺序来简化这个过程。这样的排序是许多基于多数派的系统所共有的属性；例如，ZooKeeper的领导者在将每一个更新追加到日志之前，都会用一个单调增加的epoch-counter对来标记它[5]。在CAD中，每次响应时，跟随者只向领导者发送一个称为persisted-index的单一索引，它是他们写到磁盘上的最后一次更新的epoch-counter。领导者也只维护一个叫做durable-index的索引，这个索引是至少大多数节点已经持久化的索引；领导者通过在至少大多数节点（包括自己）中找到最高的persisted-index来计算durable-index。
当一个项目i的读取到达领导者时，它将i的update-index（修改i的最新更新的epoch-counter）与系统的durable-index进行比较。如果durable-index 大于 update-index，那么对 i 的所有更新都已经是持久的，所以领导会立即为 i服务；否则，领导会采取额外的步骤（如下所述）使数据成为持久的。如果读取到达一个跟随者，它也会执行同样的检查（使用领导者在心跳中发送的durable-index）。如果检查通过，它就为读服务；否则，它就将请求重定向到leader，再由leader使数据持久化。
4.3.4 使数据持久化
如果持久性检查失败，CAD需要在服务于读之前，使状态（到最新更新的被读项目）同步持久。领导者会对检查失败的读进行特殊处理。首先，如果被读项的update-index之前的所有更新还没有被复制，则领导会同步复制这些更新。领导者还通知跟随者，他们必须在响应这个请求之前将日志刷新到磁盘。
当跟随者收到这样的请求时，会同步追加更新，并将日志刷新到磁盘上并做出响应。在这样的刷新过程中，之前缓冲的所有写操作也会被写入磁盘，确保整个状态直到最新更新的被读项目是持久的。幸运的是，周期性的后台刷新减少了这种前台刷新期间需要写入的数据量。节点作为对该请求的响应所报告的persisted-index至少与项的update-index一样高。当刷新完成对大多数人的刷新时，durable-index将被更新，从而可以服务于数据项。图2的第四列显示了这个程序的工作原理。如图所示，当项目b被读取时，持久性检查失败；因此节点会刷新所有更新到索引2，因此durable-index提高；然后项目被服务。
作为一种优化，ORCA也会持久化写入被读项目最后一次更新之后的内容。考虑图2中的日志[a,b,c]；当客户端读取b时，持久性检查失败。现在，虽然持久化b之前的条目就够了，但CAD还刷新了更新c，避免了将来读c时的同步刷新，如图中最后一列所示。
综上所述，CAD使得数据在读取时具有持久性，因此保证了即使服务器崩溃和恢复，已经读取的状态也不会丢失。接下来我们讨论一下，在这个持久性基元上，我们如何构建跨客户端单调读取。
4.4 跨客户端单调读取
如果许多可线性化系统都采用了读取只限于领导者的这种设计，那么跨客户端单调读取就很容易被CAD提供；不需要额外的机制。考虑到更新只经过领导者，领导者将拥有最新的数据，它将在读取时为其服务（如果需要，在服务前使其持久）。此外，如果当前领导者失败，新的视图将包含被读取的状态。因此，保证了在失败时的单调读取。
然而，限制只对领导者的读取限制了读取的可扩展性，并阻止客户端在附近的副本处读取。大多数实用的系统(如MongoDB，Redis)，出于这个原因，允许在许多节点进行读取[31，33，45]。然而，当允许在跟随者处读取时，仅靠CAD无法确保跨客户端的单调读取。考虑图3中的场景。领导者S1在使版本a1和a2在多数节点上持久化之后，已经服务于版本a1和a2。然而，跟随者S5是分区的，所以还没有看到a2。当一个读后来到S5时，S5有可能服务a1；虽然S5检查a1是持久化的，但它不知道a已经被其他人更新和服务了，暴露了非单调状态。因此，需要额外的机制，我们接下来会介绍。 图3：非单调性读数。该图显示了在跟随者上读取时，非单调状态如何在CAD上面暴露。 4.4.1 活动集的可扩展读数
解决图3所示问题的一个天真的方法是，在服务于领导者的读取之前，先让数据在所有跟随者上持久化。然而，这样的方法会导致性能不佳，更重要的是，降低了可用性：除非所有节点都可用，否则读取无法被服务。相反，ORCA使用一个活动集来解决这个问题。活动集至少包含大多数节点。ORCA对活动集执行以下规则。
R1：当领导者打算使一个数据项持久化时（在服务于读之前），它确保数据被活动集中的所有成员持久化和应用。
R2: 只有活动集中的节点才被允许服务于读取。
以上两个规则共同确保客户端永远不会看到非单调状态。R1确保活动集中的所有节点都包含所有已经被客户端读取的数据。R2确保只有包含之前已经被读取的数据的节点才能为读取服务；其他不包含已经服务的数据的节点（例如图3中的S5）被排除在服务读取之外，防止非单调读取。现在的关键挑战是如何正确维护活动集。
4.4.2 使用租约的成员
领导者不断地(通过心跳和请求)通知追随者，判断他们是否是活动集的一部分。活动集成员信息是领导者提供给跟随者的租约[12，18]：如果追随者F认为自己是活动集的一部分，则保证在F没有持久化和应用数据的情况下，不会向客户端提供数据。当跟随者一段时间内没有收到领导者的消息时，租约就会中断。一旦租约中断，跟随者就不能再为读取服务。领导者也会将跟随者从活动集中移除，使数据在已经更新（减少）的活动集上持久化，从而使领导者能够为读服务。
为了确保正确性，一个跟随者必须在领导者将其从活动集中移除之前将自己标记出来。考虑图4(i)中的场景，它显示了如果领导者匆忙地从活动集中移除一个断开的跟随者，非单调状态是如何暴露的。最初，活动集包含所有的节点，因此在读取时，领导者试图在所有节点上使a2持久化；然而，跟随者S5被分区了。现在，如果领导者移除S5（在S5标记自己出来之前）并服务a2，那么S5有可能在之后服务a1，暴露出失序状态。因此，为了安全起见，领导者必须等待S5将自己标记出来，然后才将S5从活动集中移除，使读成功。 图4：活动集和租约。(i)显示了匆忙移除一个跟随者如何暴露非单调状态；(ii)显示了ORCA如何打破租约。
ORCA使用两步机制打破租约：首先，一个断开的跟随者将自己从活动集中标记出来；然后领导者将跟随者从活动集中移除。ORCA通过两个超时来实现这两步机制：标记超时(mt)和移除超时(rt)；一旦mt过后，跟随者将自己标记出；一旦rt过后，领导者将跟随者从活动集中移除。ORCA设置rt明显大于mt(如rt>=5∗mt)，mt设置为与心跳间隔相同的值。图4(ii)说明了ORCA中的两步机制如何工作。当领导者等待从活动集中删除一个失败的跟随者时，性能影响最小。具体来说，只有访问（最近写入的）尚未耐久的项目的读必须等待活动集的更新；其他绝大部分读可以在没有任何延迟的情况下完成。
像任何基于租赁的系统一样，ORCA要求非故障时钟具有有界漂移[18]。在领导者通过rt时，跟随者必须通过mt；否则，可能会返回非单调状态。然而，这是极不可能的，因为我们将rt设置为mt的倍数；从属者的时钟运行太慢或领导者的时钟运行太快，不可能出现领导者通过了rt而从属者没有通过mt的情况。在许多部署中，两台服务器之间的最坏情况下的时钟漂移低至30 µs/秒[17]，这远远低于ORCA的预期。请注意，ORCA只要求有界漂移，而不是同步时钟。
当一个失败的跟随者恢复时（从崩溃或分区中恢复），领导者会将该跟随者添加到活动集中。但是，领导者在将节点添加到活动集之前，要确保恢复的节点已经持久化，并应用了所有的durable-index之前的条目。有时，领导者可能会打破一个跟随者G的租约，即使它不断收到G的消息，但G的运行速度很慢（可能是由于链路或磁盘慢），当持久性检查失败时，增加了刷新的延迟。在这种情况下，领导者可能会通知追随者需要将自己标记出来，然后领导者也会将该追随者从活动集中移除。
活动集的大小在可扩展性和延迟性之间存在着权衡。如果活动集中有许多节点，则可以从所有节点上为读提供服务，提高了可扩展性；但是，访问最近写入的非持久化数据的读可能会产生更多的延迟，因为数据必须在许多节点上复制和持久化。相比之下，如果活动集包含基本多数，那么数据可以快速变得持久，但读只能由多数人服务。
被罢免的领导。需要处理的一个微妙的情况是，当一个领导被新的领导废黜，但老领导还不知道这件事。旧的领导可能会服务一些旧的数据，而这些数据被另一个分区更新和服务，导致客户端看到非单调的状态。ORCA用上述基于租赁的机制解决了这个问题。当跟随者没有收到当前领导者的消息时，他们会选出一个新的领导者，但要在等待一定的超时后才会选出。这个时候，旧的领导者意识到自己已经不是领导者了，就会下台，停止服务读取。
4.5 正确性
ORCA永远不会返回非单调状态，也就是说，从客户端读取的状态总是至少返回任何客户端之前读取的最新状态。我们现在提供一个证明草图，说明ORCA如何在所有情况下保证正确性。
首先，当现在的领导是可以提供服务的，如果读取一个非持久项（其update-index为L），ORCA会确保在服务于读取之前，至少到L的状态被持久化在活动集的所有节点上。因此，在活动集中的任何节点上执行的读取将至少返回之前读取的最新状态（即截至L）。不存在于活动集中的跟随者可能是滞后的，但不允许对它们进行读取，从而防止它们服务于一个较旧的状态。当一个跟随者被添加到活动集中时，ORCA会确保该跟随者至少包含到L的状态；因此，对被添加的跟随者的任何后续读取都将至少返回之前读取的最新状态，确保正确性。当领导者删除一个跟随者时，ORCA确保在领导者返回任何数据之前，跟随者通过在新的缩减集上提交数据来标记自己，从而防止跟随者返回任何旧的状态。
在当前领导者失败时，ORCA必须确保被客户读取的最新状态存活到新的视图中。我们认为，这一点是由ORCA（以及许多基于多数派的系统）中的选举工作方式所保证的。假设最新读取的状态已经看到了索引L以内的状态。当领导者失败，随后形成新的视图时，系统必须恢复至少到L以内的所有条目以保证正确性；如果没有，新视图中可能会返回一个旧的状态。追随者在领导者失败时，成为候选人，竞争成为下一个领导者。候选人必须获得至少大多数人（可能包括自己）的投票才能成为领导者。当请求投票时，候选人指定其日志中最后一个条目的索引。响应节点会将传入的索引（P）与自己日志中最后一条记录的索引（Q）进行比较。如果节点在其日志中的最新数据比候选者更多（即Q>P），那么节点就不会把票投给候选者。这是许多基于多数派的系统[2，6，39]所保证的特性，ORCA保留了这一特性。
由于ORCA在活动集的所有节点上持久保存数据，并且鉴于活动集至少包含多数节点，任何多数节点中至少有一个节点在其磁盘上的状态将达到L。因此，只有状态至少达到L的候选者才能获得多数派的投票，成为领袖。在新的视图中，节点遵循新的领导者的状态。鉴于保证领导者的状态至少达到L，所以到目前为止所有被服务过的数据都会存活到新的视图中，确保正确性。
4.6 实现
我们通过修改ZooKeeper(v3.4.12)建立了ORCA。我们有两个基线。第一，同步复制但异步持久化的ZooKeeper（即禁用ForceSync的ZooKeeper）。第二，ZooKeeper的异步复制；我们修改了ZooKeeper来获得这个基线。
在ZooKeeper中，写操作要么创建新的键值对，要么更新现有的键值对。正如我们所讨论的，ORCA在这些操作上遵循基线的相同代码路径。另外，ORCA在后台不断地复制和持久化更新。读取操作返回给定键的值。在读取时，ORCA会执行持久性检查（通过比较键的update-index和系统的durable-index），如果需要的话，会强制执行持久性。
与未修改的ZooKeeper相比，ORCA在执行持久性检查时几乎不产生元数据开销。具体来说，ZooKeeper已经为每一个项目维护了最后更新的索引（作为项目本身的一部分[9]），ORCA会重复使用。因此，ORCA只需要额外维护大小为8字节的durable-index。然而，有些系统可能不会维护更新索引；在这种情况下，与未修改的系统相比，CAD需要为每个项目额外维护8个字节，这是为性能优势付出的一个小代价。
在ZooKeeper中，执行持久性检查是很简单的，因为在请求中明确指定了一个请求将读取什么项目。然而，在一个支持范围查询或"获取特定位置的所有用户"等查询的系统中做这种检查可能需要额外的一个小步骤。系统需要先试探性地执行查询，并确定所有项目将返回什么；然后，如果一个或多个项目还没有持久化，系统将强制执行持久化。
我们将复制请求和响应修改如下。跟随者在响应中包含persisted-index，领导者在请求或心跳中向跟随者发送durable-index。这些消息也被用来维护活动集租约。我们将 durable-index设置为活动集中所有节点都已坚持并应用的最大索引。我们将跟随者mark-out超时设置为与心跳间隔相同的值（在我们的实现中为100ms）。我们将移除超时设置为500 ms。
5 评估 图5：只写工作负载：延迟与吞吐量。该图通过改变不同持久性层的只写工作负载的客户端数量，绘制了平均延迟与吞吐量的对比图。
在评估中，我们提出以下问题。CAD与同步和异步持久性相比表现如何？ 与弱一致性ZooKeeper和强一致性ZooKeeper相比，ORCA的表现如何？ ORCA是否能保证在故障情况下的跨客户端单调读取？ ORCA是否为应用提供了更好的保证？
我们进行一系列实验来回答这些问题。我们用五个副本来运行我们的性能实验。每个副本都是一台20核英特尔Xeon CPU E5-2660机器，256GB内存，运行Linux 4.4，使用480-GB SSD来存储数据。这些副本通过10-Gbps的网络连接。我们使用了六个YCSB工作负载[15]，它们具有不同的读写比例和访问模式。W（只写），A（w:50%，r:50%），B（w:5%，r:95%），C（只读），D（读最新，w:5%，r:95%），F（读-修改-写:50%，r:50%）。我们没有运行YCSB-E，因为ZooKeeper不支持范围查询。报告的数字是五次运行的平均值。5.1 CAD性能
我们首先孤立地评估持久性层的性能；我们将CAD与同步持久性和异步持久性进行比较。在异步耐久性和CAD的情况下，系统同时执行异步复制和持久化。在同步持久性下，系统对关键路径中的大部分进行复制和持久化写入（使用fsync）；它采用批处理来提高性能。5.1.1 只写微基准
我们首先比较只写工作负载的性能。直观地讲，对于这样的工作负载，CAD的性能应该优于同步持久性，并与异步持久性的性能相匹配。图5显示了结果：我们绘制了客户端看到的平均延迟与闭环客户端数量从1到100变化时获得的吞吐量。我们展示了同步持久性的两种变体：一种是有批处理，另一种是无批处理。我们展示无批处理的变体只是为了说明它太慢，我们不使用这个变体进行比较；在整个评估过程中，我们只与采用批处理的优化的同步持久性变体进行比较。
我们从图中观察到以下三点。首先，带有批处理的同步持久性提供了比无批处理变体更好的吞吐量；然而，即使在100个客户机上进行积极的批处理，它也无法达到CAD的高吞吐量水平。其次，与同步持久性相比，CAD中的写入产生的延迟显著降低；例如，在约25 Kops/s（同步耐久性实现的最大吞吐量）时，CAD的延迟降低了7倍。最后，CAD的吞吐量和延迟特性与异步持久性非常相似。 表2：CAD性能。该表比较了三个持久性层的吞吐量；第3列和第4列括号中的数字是比同步持久性改进的因素。最后一列是CAD中触发同步持久性的读数百分比。
5.1.2 YCSB 宏观基准
现在我们比较一下四种YCSB工作负载的性能，这些负载有读和写的混合。A、B和F有一个zipfian访问模式（大多数操作都是访问流行的项目）；D有一个最新的访问模式（大多数读是对最近修改的数据）。我们用10个客户端运行这个实验。由于我们只评估耐久性层，所以我们限制所有三个系统的读取只针对领导者。表2显示了结果。
与批处理的同步持久性相比，CAD的性能明显更好。对于重读工作负载（B和D）和重写工作负载（A和F），CAD分别比同步持久性快约1.6倍和3倍。
CAD必须理想地匹配异步持久性的性能。首先，CAD中写的性能应该与异步持久性相同；使数据在读上持久化不应影响写。图6(a)显示了YCSB-A的这方面情况；其他工作负载的结果也是类似的。
其次，CAD中的大多数读操作必须经历与异步持久性中的读类似的延迟。然而，访问非持久性项目的读可能会触发同步复制和持久性，导致性能降低。这种影响可以从图6(b)和6©所示的读延迟分布中看出。如图所示，一部分读（取决于工作负载）会触发同步持久性，从而产生更高的延迟。然而，如表2所示，对于YCSB中的各种工作负载，这个部分很小。因此，与异步持久性相比，CAD的性能下降很小（2%-8%）。
对于CAD来说，一个不好的工作负载是主要读取最近写入的项目。即使对于这样的工作负载来说，由于之前的读取使状态持久化和CAD中的周期性后台刷新，实际触发同步持久化的读取比例也很小。例如，对于YCSB-D，虽然90%的读访问最近写的项目，但其中只有4.32%的请求会触发同步复制和持久化；因此，与异步持久化相比，CAD的开销很小（只有8%）。
CAD性能总结。CAD的速度明显快于同步持久（就是用批处理优化的），同时在很多工作负载上与异步持久的性能相匹配。即使对于主要读取最近修改的项目的工作负载，CAD的开销也很小。 图6：操作延迟。(a)显示了YCSB-A中三个持久性层的写入延迟分布。(b)和©显示了YCSB-B和YCSB-D中异步和CAD的读延迟；特写内的注释显示了CAD中触发同步持久性的读的百分比。 图7：ORCA性能。(a)通过改变三个系统的只读工作负载的客户端数量，绘制出平均延迟与吞吐量的对比图。(b)比较了三个系统在不同YCSB工作负载下的吞吐量。在(b)(i)中，weak-ZK和ORCA异步复制和持久化；在(b)(ii)中，它们同步复制但懒惰地持久化数据。每个条形图顶部的数字显示了归一化后的性能与强-ZK的性能。
5.2 ORCA系统性能
我们现在评估ORCA对ZooKeeper的两个版本的性能：强ZK和弱ZK。strong-ZK是ZooKeeper的同步持久性(批处理)，读取限制在领导者身上；strong-ZK提供了线性化，因此跨客户端单调读取。弱-ZK异步复制和持久化写入，并允许在所有副本处读取；弱-ZK不能保证跨客户端单调读取。ORCA使用CAD持久性层，读可以由活动集的所有复制体服务；我们在实验中配置活动集包含四个复制体。5.2.1 只读微基准
我们首先用一个只读的基准来证明允许在许多副本上读的好处。图7(a)绘制了三个系统在客户端数量从1到100变化时的平均延迟与读取吞吐量的关系。强-ZK限制对领导者的读取，以提供强有力的保证，因此它的吞吐量在一个点后达到饱和；在许多并发客户端的情况下，读取会产生高延迟。Weak-ZK允许在许多许多复制处进行读取，因此可以支持许多并发客户端，导致高吞吐量和低延迟；然而，代价是我们很快就会显示出较弱的保证（§5.3）。相比之下，ORCA提供了强保证，同时允许在许多复制处读取，从而实现高吞吐量和低延迟。弱-ZK和ORCA的吞吐量可以扩展到100个客户端以上，但我们没有在图中显示。5.2.2 YCSB宏观基准
现在，我们比较ORCA与弱ZK和强ZK在不同YCSB工作负载下10个客户端的性能。图7(b)显示了结果。
在图7(b)(i)中，weak-ZK和ORCA同时进行复制和持久化，速度很慢；而在7(b)(ii)中，weak-ZK和ORCA同步复制，但持久化到存储的速度很慢，即它们在后台发出fsync-s。如图7(b)(i)所示，ORCA的速度明显快于强-ZK(3.04- 3.28×，用于写重工作负载，1.75 - 1.97×，用于读重工作负载)。ORCA表现良好有两个原因。首先，它避免了写入过程中同步复制和持久化的成本。第二，它允许在许多副本处进行读取，从而实现更好的读取吞吐量。ORCA也非常接近弱ZK的性能：ORCA平均只慢了11%左右。这种降低的原因是，访问非持久化项目的读取必须在活动集的所有节点上持久化数据（与CAD中的大多数节点相反）；此外，在跟随者处访问非持久化数据的读取会产生额外的往返，因为它们被重定向到领导者。图7(b)(ii)中异步持久化基线也可以看到类似的结果和趋势。 图8：地理分布式延迟。(i)显示了源于领导者附近的操作的延迟分布；(ii)显示了源于跟随者附近的请求的延迟分布。客户端与其最近的副本之间的ping延迟为<2ms；客户端与广域网上的副本之间的ping延迟同样为∼35ms。
我们现在分析ORCA在地理复制环境下的性能，将副本放置在三个数据中心(横跨美国)，没有一个数据中心拥有大部分的副本。跨数据中心的副本通过广域网连接。我们用24个客户端运行实验，每个副本附近大概有5个客户端。在弱-ZK和ORCA中，读是在最近的副本处服务的；在强-ZK中，读只送到领导者处。在这三个系统中，写只在领导者处进行。
图8显示了不同工作负载的操作延迟分布。我们将两种请求区分开来：源于领导者附近的请求（图中最上面一行）和源于跟随者附近的请求（最下面一行）。如图8(a)(i)所示，对于只读工作负载，在所有的系统中，源于领导者附近的读取都是在本地完成的，因此经历了低延迟(2毫秒)。如图8(a)(ii)所示，源自跟随者附近的请求，在强ZK中会产生一个广域网RTT(∼33毫秒)来到达领导者；相比之下，弱ZK和ORCA可以从最近的副本服务于此类请求，因此产生14倍的低延迟。
对于只写的工作负载，在强-ZK中，除了一个本地RTT到达领导者外，源自领导者附近的写必须产生一个WAN RTT（复制到大多数）和磁盘写。相比之下，在弱-ZK和ORCA中，这种更新可以在领导者的内存中缓冲后得到满足，减少了14×的延迟。在强-ZK中，源于跟随者附近的写入会产生两个WAN RTT（一个到达领导者，另一个用于多数复制）和磁盘延迟；相反，在弱-ZK和ORCA中，这种请求可以在一个WAN RTT中完成，减少了2×的延迟。
图8©和8(d)显示了读写混合的工作负载的结果。如图所示，在强-ZK中，大多数操作都会产生高延迟；即使是源于领导者附近的读，有时也会经历高延迟，因为它们被排在缓慢的同步写后面，如图8©(i)所示。总的来说，ORCA和弱ZK中的大多数请求都可以在本地完成，因此延迟很低，除了源于跟随者附近的写入需要一个广域网RTT，这是基于领导者的系统的固有成本（例如，图8(d)(ii)中50%的操作）。ORCA中的一些请求会产生较高的延迟，因为它们读取的是最近修改的数据。然而，如图8(d)(i)所示，只有一小部分请求经历了这种较高的延迟。
ORCA性能总结。通过避免写入过程中的同步复制和持久化成本，并允许在许多副本处读取，ORCA提供了比强ZK更高的吞吐量（1.8-3.3×）和更低的延迟。在地理分布式环境中，ORCA通过允许在附近的副本上进行读取，并通过异步写入隐藏广域网延迟，显著降低了大多数操作的延迟（14倍）。ORCA也近似于弱ZK的性能。然而，正如我们接下来所展示的那样，ORCA在做到这一点的同时，还能实现弱ZK无法提供的强大一致性保证。 图9：一个示例的失败序列。该图显示了我们的测试框架生成的一个示例序列。
5.3 OCRA的一致性
我们现在检查ORCA的实现是否正确地保证了在故障情况下的跨客户端单调读取，同时也测试了故障下弱ZK和强ZK的保证。为此，我们开发了一个框架，可以通过注入崩溃和恢复事件来驱动集群进入不同的状态。图9显示了一个示例序列。一开始，所有节点都活着；然后节点1,3崩溃；1恢复；2崩溃；3恢复；最后，2恢复。除了崩溃，我们还随机选择一个节点，并给它引入延迟，这样的滞后节点可能没有见过几次更新。例如，12345→245→1245→145→1345→12345显示了节点1、2、5在几个状态下的延迟情况。
我们在每个阶段插入新的项目，并在非延迟节点上执行读取。然后，我们在延迟节点上执行读取，触发节点返回旧数据，从而暴露出非单调状态。每次执行读取时，我们都会检查返回的结果是否至少与之前任何一次读取的结果一样最新。利用该框架，我们生成了500个类似于图9的随机序列。我们对生成的序列进行弱-ZK、强-ZK和ORCA的测试。 表3：ORCA的正确性。这些表格显示了ORCA如何提供跨客户端的单调读取。在（a）中，弱ZK和ORCA使用异步持久化；在（b）中，复制和持久化都是异步的。
表3(a)显示了弱-ZK和ORCA同步复制但异步持续时的结果。在弱-ZK的情况下，83%的序列中出现了非单调读，原因有两个。首先，读数据在许多情况下由于崩溃失败而丢失，暴露了非单调读数。第二，延迟的跟随者在其他节点服务于更新的状态后，忘情地服务于旧数据。Strong-ZK，通过使用同步持久性和限制读到领导者，在所有情况下都避免了非单调读。需要注意的是，虽然同步持久性可以避免由于数据丢失造成的非单调读取，但它并不足以保证跨客户端的单调读取。具体来说，如表所示，sync-ZK-all，这种使用同步持久性但允许在所有节点进行读取的配置，并不能防止滞后的跟随者服务旧数据，暴露出非单调状态。与弱-ZK相反，ORCA不会返回非单调状态。在大多数情况下，在非延迟节点上执行的读取也会将延迟跟随者上的数据持久化，返回延迟跟随者的最新数据。在少数情况下(约13%)，领导者从活动集中删除了跟随者(因为跟随者正在经历延迟)。在这种情况下，延迟的跟随者拒绝读取(因为它不在活动集中);然而，一段时间后重新尝试会返回最新的数据，因为领导者将跟随者添加回活动集。在表3(b)中可以看到类似的结果，当弱ZK和ORCA异步复制和持久化写入时。
5.4 应用案例学习
我们现在展示ORCA提供的保证如何在两个应用场景中发挥作用。第一个是位置共享应用，其中一个用户更新他们的位置（例如，a → b →c），另一个用户跟踪位置。为了提供有意义的语义，存储系统必须保证读取器的单调状态，否则，读取器可能会错误地看到用户向后走。虽然提供会话级保证的系统可以在一个会话内确保这个属性，但它们不能跨会话（例如，当读取器关闭应用程序并重新打开时，或者当读取器断开连接并重新连接时）。而跨客户端单调读取则可以不分会话和失败，提供这种保证。 表4：案例研究。位置跟踪和Retwis。该表显示了应用程序如何通过弱-ZK、强-ZK和ORCA看到不一致（非单调）、一致（旧的或最新的）状态。
我们通过构建一个简单的位置跟踪应用来测试这个场景。一组用户在stor-age系统上更新他们的位置，而另一组用户读取这些位置。客户端可以在应用的生命周期内连接到不同的服务器。表4显示了结果。如表所示，弱-ZK在13%的读取中存在不一致(非单调)的位置，在39%的读取中存在一致但老旧(陈旧)的位置。与弱-ZK相比，ORCA可以防止非单调位置，提供更好的语义。此外，它还减少了陈旧性，因为先前的读取使状态持久。正如预期的那样，强-ZK从不暴露非单调或旧位置。
第二个应用类似于Retwis，一个开源的Twitter克隆[46]。用户既可以发布推文，也可以阅读他们的时间线（即阅读他们关注的用户的推文）。如果时间线不是单调的，那么用户可能会看到一些帖子，这些帖子可能会从时间线上消失，提供混乱的语义[14]。跨客户端单调阅读避免了这个问题，为这个应用提供了更强的语义。
这个应用中的工作负载以读为主：大多数请求检索时间线，而少数请求发布新内容。因此，我们使用了以下的工作负载组合：70%获取-时间线，30%发布，导致存储系统总共有95%的读和5%的写。结果与之前的案例研究类似。Weak-ZK在8%和20%的get-timeline操作中返回非单调和陈旧的时间线，重谱。ORCA完全避免了非单调的时间线，减少了陈旧性，为客户提供了更好的语义。
6 讨论
在本节中，我们将讨论CAD如何对当前的许多系统和部署有益，以及如何在其他类系统（如无领导的系统）中实现。应用使用。正如我们所讨论的，大多数广泛使用的系统都倾向于性能，因此采用异步耐久性。CAD的主要目标是改善这类系统的保证。通过使用CAD，这些系统和在它们之上的应用可以实现更强的语义，而不会放弃异步的性能优势。此外，在应用程序代码中几乎不需要修改或不需要修改就能获得CAD提供的好处。
少数应用，如配置存储[19]，不能容忍任何数据丢失，因此要求每次写入时立即同步持久性。虽然CAD可能不适合这种用例，但实现CAD的存储系统可以支持这种应用。例如，在ORCA中，应用程序可以通过在写入请求中指定一个标志来选择性地请求立即的持久性（当然，是以性能为代价的）。CAD在其他类系统中的应用。虽然我们在本文中把CAD应用于基于领导者的系统，但这个思想也适用于其他不建立或只建立更新因果顺序的系统。然而，与我们对基于领导者的系统的实现相比，可能需要做一些改变。首先，考虑到没有单一的更新顺序，系统可能需要为每个项目维护元数据，表示它是否持久（而不是单一的持久指数）。此外，当一个非持久项x被读取时，系统可能只对x或与x持久相关的因果关系进行更新，而不是使整个状态变得持久。我们把这种扩展作为未来工作的一个途径。
7 相关工作
一致性模型。之前的工作已经提出了一系列一致性模型，并研究了它们的保证、可用性和性能[10, 19, 27, 29, 30,48-50]。而我们的工作则专注于研究一致性如何受到底层持久性模型的影响。Lee等人，确定并描述了实现线性化的持久性要求[25]。相比之下，我们探索如何设计一个持久性基元，以实现高性能的强一致性。
持久性语义。CAD的持久性语义与一些本地文件系统有类似的味道。Xsyncfs[37]将写入磁盘的数据延迟到写入数据外部化，实现了高性能，同时提供了强有力的保证。同样，文件系统开发者也提出了O_RSYNC标志[22]，它提供了类似CAD的保证。尽管许多内核没有实现[22]，但当在open中指定时，这个标志会阻止读取调用，直到读取的数据被持久化到磁盘上。BarrierFS的fbarrier[52]和OptFS的osync[13]提供了与CAD相似的延迟持久性语义；然而，与CAD不同的是，这些文件系统并不能保证应用程序读取的数据在崩溃后仍然具有耐久性。之前的大部分工作都是在一个简单得多的单节点环境和文件系统内解决了持久性和性能之间的紧张关系。据我们所知，我们的工作是第一个在复制系统和复杂故障（如分区）存在的情况下这样做的。
提高分布式系统的性能。已经提出了几种使用推测[19，51]、利用换向性[35]和网络排序[40]来提高复制系统性能的方法。然而，这些先前的方法并没有关注解决持久性的开销，而持久性是存储系统中的一个重要问题。ORCA通过分离一致性和新鲜度来避免耐久性开销：读可以是陈旧的，但永远不会失序。Lazy-Base[14]将类似的思想应用于分析处理系统，其中读取只访问已经完全摄取和索引的旧版本。然而，这样的方法往往比弱一致系统返回的结果更陈旧。相比之下，ORCA永远不会比弱一致系统返回更陈旧的数据；此外，ORCA通过在读取时将数据持久化在许多节点上，减少了与弱系统相比的陈旧性（如我们的实验所示）。SAUCR降低了普通情况下的持久性开销，但在极少数情况下（例如，在许多同时发生故障的情况下），为了强持久性而在可用性上做出了妥协[1]。ORCA做了相反的权衡：它提供了更好的可用性，但在故障时可能会丢失一些最近的更新。
跨客户端单调读数。据我们所知，跨客户端单调读数仅由线性化提供[25，38]。然而，线性化系统需要同步的持久性，并且大多数系统防止在跟随者处进行读取。ORCA提供了这一特性，而不需要同步持久性，同时允许在许多节点进行读取。Gaios[11]提供了强大的一致性，同时允许从许多副本处读取。虽然Gaios将读分布在各个副本上，但请求仍然会通过leader进行跳转，因此到达leader会产生额外的延迟。领导者还需要一次额外的往返来检查它是否真的是领导者，进一步增加了延迟。相比之下，ORCA允许客户端直接从最近的副本中读取，既能实现负载分配，又能实现低延迟。ORCA通过使用租约避免了额外的往返（验证领导力）。ORCA使用租约来提供强一致性并不是什么新鲜事，例如，分布式文件系统中的缓存一致性的早期工作就已经这样做了[18]。
8 结论
在本文中，我们展示了分布式系统的底层持久性模型如何对其一致性和性能产生强烈影响。我们提出了一致性感知持久性（CAD），这是一种新的持久性方法，它可以实现强一致性和高性能。我们展示了如何跨客户端单调读取，强一致性保证可以在CAD上高效实现。在实现更强一致性的同时，CAD可能并不适合少数不能容忍任何数据丢失的应用。然而，它为许多目前使用异步持久性的系统提供了一个新的、有用的中间地带，在不影响性能的情况下实现更强的语义。