现代分布式存储系统设计中“一致性”的取舍

CAP定理对现代分布式数据库系统设计的影响比我们预想的要小。相反，一致性和延迟之间取舍 - 对几个主流DDBS产生了更为直接的影响。本文提出的新理论PACELC，将这种权衡与CAP结合起来, 以便对分布式数据系统的设计权衡更加系统全面。

尽管学术界几十年前就开始对分布式数据库系统进行研究，但直到最近，某些行业才开始广泛使用DDBS。这种趋势的出现有两个主要驱动因素，首先，现代应用程序需要增加数据和事务吞吐量，这导致了对弹性可伸缩数据库系统的需求。其次，全球化和业务拓展的加快要求将数据放在遍布全球的客户附近。过去10年中试图实现高可扩展性或全球可访问性(或两者兼有)的DDBS示例包括SimpleDB/Dynamo/DynamoDB，Cassandra，Voldemort(Http://projectvoldemort.com)，Sherpa/PNUTS，Riak (http://wiki.basho.com)，HBase/BigTable，mongoDB(www.monGodb.org)，VoltDB/H-Store和Megastore.

DDBS很复杂，构建它们很困难。因此，任何帮助设计人员理解创建DDBS所涉及的权衡的工具都是有益的。特别是CAP定理在帮助设计师推理所提出的系统能力以及揭露许多商业DDBS的夸大营销炒作方面非常有用。然而，自从最初的正式证明以来，CAP已经变得越来越被误解和误用。特别是，许多设计者错误地断定该定理在正常系统操作期间对DDBS施加了某些限制，因此实现了不必要的系统约束。实际上，CAP仅在面对某些类型的故障时附加了限制，而在正常操作期间不会对系统能力产生任何约束和限制。

尽管如此，在正常操作期间抑制DDBS能力的基本权衡影响了主流系统的不同设计选择。实际上，在一致性和延迟之间的一个特定权衡 - 可以说对DDBS设计的影响比CAP理论更大。两组权衡都很重要; 将CAP和一致性/延迟权衡统一到一个理论中 - PACELC中可以相应地使得对现代DDBS的设计进行更深入的理解。

CAP IS FOR FAILURES 

CAP表明，在构建DDBS时，设计人员可以选择三个理想属性中的两个：一致性(C)，可用性(A)和分区容忍性(P)。因此，只有CA系统(一致且高可用，但不能容忍分区)，CP系统(一致和分区容错，但不高可用)和AP系统(高可用性和分区容忍但不一致)是可能的。

许多现代DDBS(包括SimpleDB/Dynamo，Cassandra，Voldemort，Sherpa/PNUTS和Riak)默认不保证CAP定义的一致性。 (虽然这些系统中的一些系统的一致性在初始版本发布后变得可调，但重点在于它们的原始设计。)在他们的CAP证明中，Seth Gilbert和Nancy Lynch使用了原子/线性化一致性的定义：“必须在所有操作中存在一个全局顺序，使得每个操作看起来好像是在一个瞬间完成的。这相当于要求分布式共享内存的请求就像它们在单个节点上执行一样，一次响应一个操作。”

鉴于早期的DDBS研究侧重于一致系统，因此很自然地认为CAP是对现代系统架构师的主要影响，他们在定理证明之后的时期内构建了越来越多的系统来实现简化的一致性模型。这种假设背后的原因是，因为任何DDBS都必须容忍网络分区，所以根据CAP，系统必须在高可用性和一致性之间进行选择。对于高可用性非常重要的任务关键型应用程序，它别无选择，只能牺牲一致性。

但是，这种逻辑存在缺陷，与CAP实际所说的不一致。不仅仅是分区容忍需要在一致性和可用性之间进行权衡; 相反，它们是以下两点的组合：

• 分区容忍

• 网络分区本身的存在

该定理简单地指出网络分区导致系统必须在降低可用性或一致性之间做出决定。网络分区的概率高度依赖于系统实现的各种细节：它是通过广域网(WAN)还是仅通过本地集群分布的？什么样的硬件质量？有哪些流程可以确保仔细执行对网络配置参数的更改？冗余程度如何？尽管如此，一般而言，网络分区比较罕见，并且通常不如DDBS中其他严重类型的故障事件一样频繁发生。

基于CAP的决策而在没有任何分区发生的情况下降低一致性的DDBS是错误的。

由于CAP在基线情况下没有规定系统限制，因此假设在没有任何分区的情况下降低一致性的DDBS是错误的。事实上，CAP允许系统在没有分区时提供完整的ACID(原子性，一致性，隔离和持久性)保证以及高可用性。因此，该定理并不能完全证明降低一致性的DDBS的默认配置(通常还有其他一些ACID保证)

CONSISTENCY/LATENCY TRADEOFF

要了解现代DDBS设计，重要的是要实现这些系统的构建背景。亚马逊最初设计的Dynamo用于向其电子商务平台(例如购物车)中的核心服务提供数据。 Facebook构建了Cassandra以支持其收件箱搜索功能。 LinkedIn创建了Voldemort，通过其网站上的各种写密集功能处理在线更新。雅虎构建了PNUTS，用于存储可在每个网页视图中读取或写入的用户数据，存储Yahoo购物页面的列表数据，以及存储数据以服务其社交网络应用程序。

在每种情况下，系统通常为即时构建并发送给活动网站用户的网页提供数据，并接收在线更新。研究表明，延迟是在线互动的一个关键因素：小到100毫秒的增加，就可能大大降低客户未来继续互动或返回的可能性

不幸的是，在一致性，可用性和延迟之间存在着根本的权衡。 (请注意，可用性和延迟可以说是相同的：不可用的系统本质上提供了极高的延迟。为了讨论的目的，我认为延迟大于典型请求超时的系统，例如几秒钟就意味着不可用；延迟小于请求超时，但仍然接近几百毫秒的情况为“高延迟”。但是，我最终会放弃这种区别，并允许低延迟要求包含两种情况。因此，权衡实际上只是在一致性和延迟之间，正如本文的标题所示。)

即使没有网络分区，这种权衡也存在，因此与CAP描述的权衡完全分开。尽管如此，它是设计上述系统的关键因素。 (与此讨论无关，是否将单个机器故障视为特殊类型的网络分区。)

权衡的原因是高可用性要求意味着系统必须复制数据。如果系统运行的时间足够长，系统中至少有一个组件最终会失败。发生此故障时，除非系统在故障之前复制了另一版本的数据，否则组件控制的所有数据都将变为不可用。因此，即使在没有故障本身的情况下，故障的可能性也意味着可用性要求在正常系统操作期间需要一定程度的数据复制。 (注意这种权衡和CAP权衡之间的重要区别：虽然失败的发生导致CAP权衡，但失败的可能性本身会导致这种权衡。)

为了实现尽可能高的可用性，DDBS必须通过WAN复制数据，以防止整个数据中心因例如飓风，恐怖袭击而发生故障，或者像2011年4月著名的Amazon EC2云中断一样，单个网络配置错误。上面提到的五个降低一致性系统的设计具有极高的可用性，通常用于通过WAN进行复制。

DATA REPLICATION

一旦DDBS复制数据，就会出现一致性和延迟之间的权衡。发生这种情况是因为实现数据复制只有三种选择：系统同时向所有副本发送数据更新，首先向某个一致的主节点发送数据更新，或者首先向单个(任意)节点发送数据更新。系统可以以各种方式实现这些情况中的每一种; 但是，每个实现都带有一致性/延迟权衡。

• (1) Data updates sent to all replicas at the same time

如果更新没有首先通过预处理层或其他协议协议，则可能会出现副本分歧 - 明显缺乏一致性(假设系统的多个更新同时提交，例如，来自不同的客户端)，因为每个副本可能选择应用更新的不同顺序。 (即使所有更新都是可交换的 - 这样每个副本最终都会变得一致，尽管副本可能会以不同的顺序应用更新 — 但以Gilbert和Lynch对一致性的严格定义来衡量，这任然不是一个一致性的系统。但是，广义的Paxos可以通过一次RTT的代价提供一致的复制。)

另一方面，如果更新首先通过预处理层或者写入过程中协调所有节点来决定操作的顺序，那么可以确保所有副本就更新的顺序达成一致。但是，这会导致延迟增加。比如使用协议的情况下，协议本身是延迟的来源之一。

在预处理的情况下，有两个延迟源。首先，通过附加系统组件(预处理模块)路由更新会增加延迟。其次，预处理模块由多台机器或一台机器组成。在前一种情况下，需要一个协议来决定整个机器的操作顺序。在后一种情况下，即使另一个数据副本更接近更新发起位置，系统也会强制所有更新，无论它们在何处发起 - 可能在世界的任何地方 - 首先一直路由到单个预处理模块。

• (2) Data updates sent to an agreed-upon location first

我将这个商定的位置称为“主节点”(不同的数据项可以有不同的主节点)。此主节点解析所有更新数据项的请求，并且它选择执行这些更新的顺序决定了所有副本执行更新的顺序。主节点解析更新后，会将它们复制到所有副本位置。

一旦DDBS复制数据，就会出现一致性和延迟之间的权衡。

有三种复制选项: 

1. 复制是同步的：主节点等待，直到所有更新都进入副本。这确保了副本保持一致，但是由于需要在这些实体之间传递消息以及延迟受最慢实体限制的事实，跨独立实体(尤其是WAN)的同步操作会增加延迟。

2. 复制是异步的：系统将更新视为在复制之前完成更新。通常，在更新的发起者获知它已完成复制之前(如果主节点发生故障)，更新至少已经在某处持久化存储，但不保证系统已传播更新。在这种情况下，一致性/延迟权衡取决于系统如何处理读取:
   i. 如果系统将所有读取路由到主节点并从那里提供服务，则不会降低一致性。但是，这种方法存在两个延迟问题:
   1. 即使有一个靠近读取请求发起者的副本，系统仍然必须将请求路由到主节点，这可能在物理上更远
   2. 如果主节点因其他请求过载或发生故障，则无法从其他节点提供读取服务。相反，请求必须等待主节点变为空闲或恢复。换句话说，缺乏负载平衡选项会增加潜在延迟

3. ii. 如果系统可以从任何节点提供读取，则读取延迟要好得多，但这也会导致 同一数据项的读取不一致，因为不同位置在系统仍在传播更新时具有不同版本的数据项，并且可以向任何这些位置发送读取。尽管可以通过跟踪更新序列号并使用它们来实现顺序/时序一致性或读写一致性来限制一致性降低的程度，但这些仍然是一种残次的一致性模型。此外，如果写操作的主节点在地理上远离写请求者，则写延迟可能很高

4.  (a)和(b)的组合是可能的：系统同步地向副本的某个子集发送更新，而其余的异步发送。在这种情况下，一致性/延迟权衡再次取决于系统如何处理读取：

     i. 如果它将读取路由到至少一个已同步更新的节点 - 例如，当Quorum协议中的R + W> N时，其中R是同步读取中涉及的节点数，W是节点数参与同步写入，N是副本的数量 - 然后可以保持一致性。然而，(a)，(b)(i)(1)和(b)(i)(2)的等待时间问题都存在，尽管程度稍低，因为同步中涉及的节点数量更小，并且多个节点可以提供读取请求。
ii. 如果系统有可能从尚未同步更新的节点提供读取，例如，当R +W≤N时，则可能存在不一致的读取，如(b)(ii)中所示。从技术上讲，简单地使用Quorum协议并不足以保证Gilbert和Lynch定义标准的一致性。但是，确保完全一致性所需的附加协议在此处不相关，因为即使没有这些附加条件，延迟也是Quorum协议中固有的。

• (3) Data updates sent to an arbitrary location first

这种情况与(2)之间的区别在于系统为特定数据项发送更新的位置并不总是相同的。例如，可以同时在两个不同位置发起针对特定数据项的两个不同更新。一致性/延迟权衡再次取决于两个选项

a. 如果复制是同步的，则存在(2)(a)的延迟问题。另外，该系统可能产生额外的延迟，以检测和解决在两个不同位置发起的同一数据项的同时更新的情况
b. 如果复制是异步的，则存在类似于(1)和(2)(b)的一致性问题

TRADEOFF EXAMPLES

无论DDBS如何复制数据，显然它必须权衡一致性和延迟。对于短距离精心控制的复制，存在合理的选项，如(2)(a)，因为本地数据中心的网络通信延迟很小;但是，对于通过WAN进行复制，无法绕过一致性/延迟权衡。

为了更全面地理解这种权衡，考虑四个DDBS为达到极高的可用性，是如何设计的 — Dynamo，Cassandra，PNUTS和Riak。由于这些系统是为与活动WEB客户端的低延迟交互而设计的，因此每个系统都牺牲了一致性以降低延迟。 

Dynamo，Cassandra和Riak使用(2)(c)和(3)的组合。特别是，系统将更新发送到同一节点，然后将这些更新同步传播到其他W节点 - 即情况(2)(c)。系统同步向R节点发送读取，R + W通常设置为小于或等于N的数字，导致读取不一致的可能性。但是，系统并不总是将更新发送到特定数据项的同一节点 - 例如，这可能发生在各种故障情况下，或者由于负载均衡器的重新路由。这导致了(3)中描述的情况以及可能更大的一致性缺陷。 PNUTS使用选项(2)(b)(ii)，在降低一致性的情况下实现更好的延迟。 

Jun Rao，Eugene Shekita和Sandeep Tata最近的一项研究进一步证明了这些系统基线实施的一致性/延时权衡。研究人员通过实验评估了Cassandra一致性/延迟权衡中的两个选项。第一个选项“弱读取”允许系统为任何副本的读取提供服务，即使该副本尚未收到数据项的所有未完成更新。第二个选项“Quorum读取”要求系统在读取数据之前明确检查多个副本之间的不一致性。相对于第一种选择，第二种选择显然是以延迟为代价而增加了一致性。这两个选项之间的延迟差异可达四倍或更多。

Hiroshi Wada及其同事的另一项研究似乎与此结果相矛盾。这些研究人员发现，相对于默认(可能不一致)的读取选项，在SimpleDB中请求一致读取不会显着增加延迟。然而，研究人员在Amazon某个Zone(美国西部)内部进行了实验，他们推测SimpleDB使用主从复制，如果复制发生在短距离内，则可以以适度的延迟成本实现。特别是，Wada及其同事得出结论，SimpleDB强制所有一致读取都要由master执行。只要读取请求来自物理上靠近master的位置，并且只要主设备没有过载，那么一致读取的额外延迟是不可见的(这些条件在他们的实验中都是正确的)

如果SimpleDB跨Amazon区域复制数据，并且读取请求来自与master位置不同的区域，则一致性读取的延迟成本将更加明显。即使没有跨区域复制(SimpleDB目前不支持跨区域复制)，官方的亚马逊文档也会警告用户延迟增加并降低吞吐量以实现一致性读取。

所有四个DDBS都允许用户更改默认参数以换取更好的一致性和更大的延时 - 例如，通过在Quorum类型系统中使R + W大于N.尽管如此，即使在没有网络分区的情况下，在正常系统操作期间也会发生一致性/等待时间权衡。如果通过WAN进行数据复制，则权衡会被放大。显而易见的结论是，一致性降低可归因于运行时延迟，而不是CAP。 PNUTS提供了最有力的证据表明：CAP不是这些系统中降低一致性水平的主要原因。在PNUTS中，主节点拥有每个数据项。系统将对该数据项的更新路由到主节点，然后通过WAN将这些更新异步传播到副本。 PNUTS可以从任何副本提供读取，这将系统置于类别(2)(b)(ii)中：它降低了一致性以实现更好的延迟。但是，在网络分区的情况下，主节点在少数分区内变得不可用，系统默认使数据项不可用于更新。换句话说，PNUTS默认配置实际上是CP：在分区的情况下，系统选择一致性以避免解决在不同主节点处发起的冲突更新的问题。

因此，降低基线情况一致性的选择更明显地归因于持续的一致性/等待时间权衡，而不是CAP中的一致性/可用性权衡，这仅在网络分区上发生。 当然，PNUTS在基线情况下一致性不友好的缺陷，在网络分区情况下也许很有用，因为在不可用分区中的数据仍然可以读取。

CAP对其他三个系统产生更大的影响可能更大一些。如果发生网络分区，Dynamo，Cassandra和Riak会更充分地切换到数据复制选项(3)，并使用在检测到副本差异时运行的特殊协调代码来处理产生的一致性问题。因此，可以合理地假设这些系统的设计考虑了网络分区的可能性。因为这些是AP系统，所以从一开始就将协调代码和切换到(3)的能力内置到代码中。但是，一旦该代码存在，就可以方便地重用一些灵活的一致性模型来选择基线一致性/延迟权衡中的一个点。这个论点比声称这些系统的设计者选择完全降低CAP的一致性(忽略延迟因子)更合乎逻辑。

忽略复制系统的一致性/延迟权衡是一个大问题，因为它在系统运行期间始终存在。

总之，CAP只是现代DDBS降低一致性的两个主要原因之一。忽略复制系统的一致性/等待时间折衷是一个大问题，因为它在系统操作期间始终存在，而CAP仅与可能极少的网络分区情况相关。实际上，前者的权衡可能更有影响力，因为它对系统的基线操作有更直接的影响。

PACELC

通过将CAP重写为PACELC(发音为“pass-elk”)可以实现对DDBS潜在一致性权衡空间的更完整描述：如果存在分区(P)，系统如何权衡可用性和一致性(A 和C); 否则(E)，当系统在没有分区的情况下正常运行时，系统如何权衡延迟(L)和一致性(C)？

请注意，延迟/一致性权衡(ELC)仅适用于复制数据的系统。否则，系统会遇到任何类型的故障或节点过载时的可用性问题。由于此类问题只是极端延迟的实例，因此ELC权衡的延迟部分可以包含是否复制数据的选择。

Dynamo，Cassandra和Riak的默认版本是PA/EL系统：如果发生分区，它们会选择可用性而放弃一致性，在正常操作下，它们会放弃一致性以降低延迟。放弃PACELC中的两个C使设计更简单; 一旦系统配置为处理不一致，就有选择放弃一致性而提供更好的可用性和较低的延迟。然而，这些系统具有用户可调整的设置以改变ELC权衡 - 例如，通过增加R + W，它们以延迟为代价获得更高的一致性(尽管它们无法实现Gilbert和Lynch定义的完全一致性，即使R + W> N)。

完全ACID系统(如VoltDB/H-Store和Megastore)是PC/EC：它们拒绝放弃一致性，并将支付实现它的可用性和延迟成本。 BigTable和相关系统(如HBase)也是PC/EC。

MongoDB可以归类为PA/EC系统。在基线情况下，系统保证读取和写入一致。但是，MongoDB使用数据复制选项(2)，如果主节点发生故障或与系统的其余部分分区，则它会存储已发送到主节点但尚未复制到本地回滚目录中的所有写入。同时，系统的其余部分选择一个新的主服务器以保持可读和写入状态。因此，旧主服务器的状态和新主服务器的状态变得不一致，直到系统修复故障并使用回滚目录来协调状态，这个过程目前是手动的。 (从技术上讲，当发生分区时，根据CAP的可用性定义，MongoDB不可用，因为少数分区不可用。但是，在PACELC的上下文中，因为分区导致比可用性问题更多的一致性问题，MongoDB可以归类为PA/EC系统。)

PNUTS是一个PC/EL系统。在正常操作中，它选择更好的延时而放弃了一致性; 但是，如果发生分区，它会放弃可用性以保持一致性。这无疑令人困惑：据PACELC称，PNUTS似乎在网络分区上更加一致。但是，不应以这种方式解释PC/EL。 PC并不表示系统完全一致; 相反，它表示当发生网络分区时，系统不会降低超出基准一致性级别的一致性 - 相反，它会降低可用性

构建分布式数据库系统所涉及的权衡是复杂的，CAP和PACELC都无法解释它们。尽管如此，将一致性/延迟权衡结合到现代DDBS设计考虑中是非常重要的，以保证使权衡更接近架构讨论的最前沿。