本文由宋雾代翻译自Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services
本文首发于https://www.jianshu.com/p/2f80b89471dd 转载请注明出处

引言

  在设计分布式web服务时，有三种特性都是我们希望达到的：Consistency 数据一致性、Availability 服务可用性、Partition tolerance 分区容错性。但是同时达到这三种特性是不可能的。在这篇文章中我们会试着在异步网络模型中证明这个CAP猜想，然后讨论一个在部分同步模型中的解决方案来尝试摆脱这种困境。

1 简介

  在2000年的PODC会议上，Brewer在一次受邀讲话^[2]中做了如下的猜想：对于一个web应用服务无法同时满足如下三种特性：

• C（Consistency 数据一致性）
• A（Availability 服务可用性）
• P（Partition tolerance 分区容错性）

  所有以上三种特性都是我们在实际web应用中渴望实现的。在本文中我们会首先搞清楚Brewer的猜想到底是什么意思，然后我们会形成一个完整的概念尝试证明这个猜想。最后我们会尝试阐述一些实际的解决方案来一定程度上解决这个困境。

  如今几乎所有的应用服务都会提供强一致性的数据。许多有重大意义的研究也是关于如何设计一个符合ACID的数据库的，大多数基于分布式Web服务的框架也是基于这些数据库的。与web服务的交互也都通常基于如下的准则：操作整体提交成功或者失败（Atomic 原子性），提交成功的事务对于后续交易都是可见的（Consistent 一致性），尚未提交的操作之间互相隔离互不影响（Isolated 隔离性），以及一旦交易提交成功记录将被永久保存（Durable 持久性）。很显然这些对于一个系统非常重要，举个例子，对于账务系统和金融交易系统的交易记录通常都是要求强一致性的。

  Web服务通常也希望高可用性。对于每个请求都希望获得响应。当一个web服务不幸宕机以后，可能对我们的现实世界造成巨大的影响。例如一个电子贸易网站突然服务不可用可能导致潜在的法律风险。而最悲惨的是当你在最着急的时候，这个网站却怎么也无法访问。所以如今大多数web服务的目标就是只要网络没有问题，我们的服务就是可用的。只要在网上其他服务可用，那我的服务也必须是可用的。

  最后对于一个完全分布式的网络，对于容错性是有一定需求的。当一些节点宕机，一些网络连接中断，系统仍然能够正常提供服务就显得尤为重要。一个理想的容错特性指的是系统从网络错误而导致的多个分区中恢复。在本文中我们暂且不考虑节点宕机的情况，因为我们可以将宕机的节点视作为节点将自己隔离成一个独立的网络分区。

2 规范模型

  在这个章节，我们会正式的定义什么是一致性、可用性和分区容错性。

2.1 原子化数据对象

  一致性服务最为经典的就是原子化数据对象。原子^[5]一致性或者我们称为线性^[4]一致性是当今web服务的基本要求。根据一致性的要求，所有的操作必须如同在一个单独的实例中一样按照一个线性的顺序依次执行。这也就相当于要求对于分布式共享存储的请求必须一个请求一个响应如同访问一个独立节点一样。一个最重要的特性就是，对于一个支持原子化读写请求的共享存储，当一个读请求在一个写请求成功以后到达，读请求的返回值必须反映出前面写请求所更新的数据。正是这种一致性的约束，提供了让使用者可以理解的最简单的模型。同时对于那些尝试设计使用分布式服务的客户端应用程序的用户来说也是最方便的。可以参看附录中[6]获取更多信息。

2.2 可用性数据对象

  对于一个分布式系统来说所谓的持续可用就是指对于每个请求只要节点没有宕机都应该返回一个应答。换句话说，任何服务执行的程序必须要有一个终态。在某些方面来说，以上对于可用性的定义要求并不高：对于程序需要执行多久到终态没有一个界限，因此允许程序无限期的执行下去。然而，当我们同时考虑到系统同时具备分区容错性时，这个要求又变的很高：即使当分布式服务内部的网络崩溃了，每个请求仍然需要一个应答。

2.3 分区容错性

  以上关于原子性和可用性的定义都是基于系统具备分区容错性的基础上的。为了解释什么是分区容错性，首先节点之间的网络传输是允许存在许多随机的消息丢失的。所谓的网络分区就是指，处在一个分区的节点发往另外一个分区的服务节点的消息都会丢失。（如果仅仅丢失部分消息则可以认为在消息丢失的那一刻，网络形成了一个临时的网络分区）。因此，对于原子性要求 (§2.1) 意味着每个响应都将是原子的，即使作为程序执行的一部分而发送的任意消息可能无法传递。可用性要求 (§2.2) 意味着接收来自客户端的请求的每个节点都必须响应，即使发送的任意消息可能会丢失。你可能会发现这类似于要求一个运行在纯内存共享的系统中完成wait-free的程序直到终止：即使网络中的每个其他节点都出现故障 (即节点位于其自身的分区唯一组件中)，也必须生成有效的 (原子) 响应。不允许少于总网络故障的一组故障导致系统响应不正确。

3 异步网络

3.1 不可能的结果

  为了证明CAP猜想，我们将使用由Lynch ^[7]提出的异步网络模型。在异步模型中，是不存在时钟的，所以节点只能通过获得的信息和本地计算来决定执行什么逻辑。

定理 1 在异步网络模型中，不可能实现一个同时保证以下属性的读写数据对象：

• 可用性
• 原子一致性
  在所有正常的处理过程中（包括那些在传输过程中消息丢失的过程）。

证明：
  我们用反证法来证明这个定理。假设我们存在一个算法A同时满足三条要求：原子性，可用性和分区容错性。我们来创建一个基于算法A的执行过程对于一个存在的request其返回是不一致的。证明的方法类似于Attiya的方法^[1]和Lynch的方法^[8]。我们假设这个网络拥有至少2个节点，那么它将至少被拆成两个子网，我们用一个非空集合来表示{G₁,G₂}。证明的最基本思想就是假设G₁和G₂之间的消息全部丢失，那么当一个写操作在G₁成功提交以后，那之后在G₂有一个读操作，那么这个读操作无法返回包含最近所有写操作的结果集。
  具体证明如下：
假设：

• v₀ 是一个原子对象的初始值。
• a₁ 是算法A的一个方法用来执行一个写操作将G₁中的 v₀ 值更新成为一个非 v₀ 值，在写执行完成后方法运行进入终态。
• 除此之外没有其他来自客户端的请求访问到G₁或者G₂。
• 没有任何消息可以从G₁传输到G₂或者从G₂传输到G₁。

因为：算法A支持可用性。
所以：对于写请求完成以后一定有个响应表示操作成功。

假设：

• a₂ 是算法A的一个方法用来执行一个读操作获取 G₂ 中的值。
• 在a₂ 方法执行完成后方法运行进入终态之前没有其他来自客户端的请求。
• 在a₂方法执行完成之前没有任何消息可以从 G₁ 传输到 G₂ 或者从 G₂ 传输到 G₁。

因为：算法A支持可用性。
所以：a₂ 方法完成以后一定有个响应返回结果。
因为：a₂ 方法不包含任何写操作。
所以：返回的值一定是 v₀

假设：

• 方法 a 是一个先执行 a₁ 再执行 a₂ 的方法。

因为：没有任何消息可以从 G₁ 传输到 G₂ 或者从 G₂ 传输到 G₁，同时方法 a₁ 不包含任何发往 G₂ 的请求。
所以：对于 G₂ 来说无法分辨方法 a 和方法 a₂
所以：当方法 a 执行时，调用方法 a₂ 的读操作返回的仍然是 v₀。
因为：在方法 a 中，a₂ 的读操作是在 a₁ 的写操作执行完成之后执行的。
所以：与该算法A支持原子性定义相冲突，所以证明不存在该算法A。

推论 1.1 在异步网络模型中不存在一个支持读写的数据模型同时满足如下约束：

• 可用性，对于所有正常的执行过程
• 原子一致性，对于所有正常的没有任何信息的丢失的执行过程
  证明：
    主要思路是对于一个异步模型不存在一个算法可以分辨消息是丢失了还是因为某些随机原因被堵在通讯队列里。因此如果存在一个算法可以在没有任何信息的丢失的执行过程中支持原子性，那么一定存在一个算法可以支持原子性哪怕在执行过程中有信息丢失。然而这将违反定理1。
    具体证明如下：
  假设:

• 存在一种算法 a，该算法始终能终止，并且只要收到所有消息，那么正常执行中能保证原子一致性。

因为：基于定理1我们已经证明算法A无法在所有的正常的执行过程中都保证原子一致性。
所以：在算法A中一定存在一些正常的执行过程 a，其返回结果不是原子性的。
所以：在某些有限的节点会执行过程 a，从而使算法A的返回是非原子性的。

假设：

• a' 是方法 a 的一个预处理，其返回一个未校验的结果。
• 扩展 a' 使其成为一个正常完整的处理过程 a''，同时所有消息都接收到。
  因为：执行过程 a'' 是非原子性的。
  所以：不存在这样一个算法A。

3.2 在异步模型中的解决方案

  虽然我们无法同时满足这三个约束：原子性，可用性和分区容错性，但是我们可以同时满足其中任意两个约束。

3.2.1 原子性和分区容错性

  如果不要求可用性，那么达到原子性和分区容错性将会非常简单。这个毫无意义的系统只要无视掉任何请求就可以了。当然我们可以在加一条强一点的有弹性的约束：如果在执行过程中所有消息都接收到，那么系统必须是可用的而且所有操作都会有个终态。一个简单的中心化算法就符合如上要求：一个单独的指定的节点应用就能实现上面的需求。当一个节点收到一个请求，它会把请求推送给这个指定的节点，然后由这个指定的节点会给一个响应。当节点收到这个来自这个指定节点的认可以后，节点再回复客户端。
  许多分布式数据库都是提供这种类型的保证的。尤其是基于分布式锁和分布式互斥的算法：如果出现某些故障模式，则可用性被削弱，服务不再返回响应。如果没有失败，那么可用性是有保证的。

3.2.2 原子性和可用性

  如果不存在分区，很显然一致性和可用性是可以保证的。事实上在3.2.1章节中提到的中心化算法就符合这个要求。运行在内部网络或者局域网的系统就是这种算法的一个例子。

3.2.3 可用性和分区一致性

  如果不要求原子一致性，那么要实现高可用和分区容错性也是可行的。如果没有一致性要求，那么系统可以对于每个请求都毫无意义的返回初始值 v₀。当然在一个可用同时分区容错的系统中也可以提供一个较弱版本的一致性。Web caches就是支持较弱版本一致性的范例。在4.3章节我们会讨论一些其他的弱一致性版本的解决方案。

4 部分同步网络

4.1 部分同步模型

  试图规避定理1中不可能的结果最明显的方法是认识到，在现实世界中，大多数网络并不是纯异步的。如果允许网络中的每个节点都有一个时钟，则可以构建更强大的服务。
  在本文的余下部分中，我们将讨论一个部分同步模型，其中每个节点都有一个时钟，所有时钟都设置为相同的速率。但是时钟本身并不同步，因为它们可能会在相同的时间显示不同的值。实际上，时钟充当计时器的作用：进程可以观察这个局部变量，用以测量经过了多少时间。本地计时器可用于设定在其他步骤之后的某个时间间隔内执行操作。此外，假设每个消息要么在给定的已知时间内进行传递: t_msg，否则则认为丢失。此外，每个节点在给定的已知时间内处理接收到的消息: t_local ，同时假设本地处理所需的时间为零。这样可以抽象化为Lynch [9] 定义的一般定时自动机模型的一个特例。

4.2 不可能的结果

  当任意消息可能丢失时，即使在部分同步模型中，仍然不可能有一个始终可用的，原子数据对象。也就是说，和定理1相似的也有以下定理:

定理 2 在部分同步网络模型中，不可能实现一个同时保证以下属性的读写数据对象：

• 可用性
• 原子一致性
  在所有正常的处理过程中（包括那些在传输过程中消息丢失的过程）。

证明：
  这个证明与定理1的证明相当相似。我们将遵循相同的方法：将网络划分为两个组件{G₁,G₂}，并构造一个可操作的执行，其中一个组件中发生写入操作，然后在另一个组件中执行读取操作。此读取操作可能返回不一致的数据。
  具体证明如下：

1. 构建执行过程 a₁ 定义如同定理 1：执行一个写操作将 G₁ 中的 v₀值更新成为一个非 v₀ 值，在写执行完成后方法运行进入终态。
2. 定义 a'₂ 需要在很长的时间之后执行，而且期间没有其他来自客户端的请求。
3. a'₂ 在执行前的那段等待的时间足够 a₁ 完成写操作
4. 在 a'₂ 之后接着执行 a₂（定义如同定理 1）：执行一个读操作在G₂上的读操作。
5. 除此之外没有其他来自客户端的请求访问到 G₁ 或者 G₂。
6. 没有任何消息可以从 G₁ 传输到 G₂ 或者从 G₂ 传输到 G₁。
7. 构建一个执行过程a包含 a₁ 和 a'₂。
   因为：a₂ 执行前的那段等待时间保证了 a₁ 已经将数据更新。
   又因为：根据定理1 a₂，这条读请求返回的是初始值而不是写操作更新的新值。
   所以：违背原子一致性。

4.3 部分同步模型中的解决方案

  但是，在部分同步模型中并不存在类似推论1.1的推论。事实上，这一推论的证明取决于节点不知道消息何时丢失。在部分同步网络的算法中，当所有消息都已传递时，执行过程最后返回原子数据 (即系统已经从分区中恢复)，仅当在消息丢失时返回不一致 (尤其是陈旧) 的数据。这种算法的一个例子是3.2.1 章节中描述的集中协议，其中当消息超时，直接认为消息已丢失。在读 (或写) 请求上， 将向中心节点发送一条消息。如果收到来自中心节点的响应，则该节点将提供请求的数据 (或确认)。如果在 2 t_msg + t_local 内没有收到任何响应，则节点的结论是消息丢失。然后向客户端发送响应: 本地节点的已知最佳值或确认。在这种情况下，原子一致性可能会被违反。

4.4 弱一致性条件

  虽然在所有消息都正确转递的执行中返回原子数据是很有用的，但当某些消息丢失以后，执行过程中我们该如何处理也同样重要。在本节中，我们将讨论一个可能较弱的一致性条件，该条件允许在存在分区时返回过时的数据，但仍对返回的陈旧数据的质量提出了正式要求。这种一致性保证将要求在不会丢失任何消息的情况下，在执行中保证可用性和原子一致性。根据推论1.1，这一点在纯异步模型中是无法保证的。
  在部分同步模型中，算法需要知道多少时间以后需要纠正状态从而满足基本约束。此一致性模型可确保在所有消息都传递完以后，最终在某种意义上来说恢复了原子性。
  在原子执行中，我们将定义读和写操作的部分顺序。当一个操作在另一个操作结束后才能开始，则在这部分顺序中前者不会在后者之前执行。我们将定义一个较弱的约束：延时 t 一致性。以类似的方式定义一个部分顺序，但只要求一个操作不在另一个操作之前执行，在这两个操作之间有个间隔用以传递所有的消息。

定义 3 在以下情况下, 读写对象的定时执行可以达成延时 t 一致:

1. P 是一个部分顺序，这个顺序中所有读操作都是在接收到写操作的回执以后才进行的。
2. 每个读操作的返回值都是在顺序 P 中其前序的写操作写入的值。（或者为初始值，如果在顺序 P 中这个读操作前面没有写操作的话。）
3. P 中的读写请求顺序与向节点提交的读写请求顺序一致。
4. （原子性）如果在执行过程中所有信息都已经传递，并且操作 θ 在操作 φ 开始之前完成，那么在 P 的顺序中 φ 不能出现在 θ 之前。
5. （弱一致性）假定存在比 t 更长的时间间隔，其中不会丢失任何消息。此外，假设一个操作 θ 在间隔开始之前完成，另一个操作 *φ *在间隔结束后开始。那么在 P 的顺序中 φ 不能出现在 θ 之前。

  此约束允许在消息丢失时出现一些陈旧的数据，但在分区合并恢复以后，此不一致可以持续多长时间提供了限制。这与数据的最终一致的想法有关，可以参考 Fekete 的文章^[3]。在这里我们希望有一个明确的时间限制，即数据需要多长时间才能变得一致。
  第4.3 章节中描述的集中式算法的一个变体就是延迟 t 一致的。假定节点 C 是集中节点。该算法的行为如下:

• 在节点 A 上执行读操作
  1. A 发送一个请求到节点 C 获取最新的数据。
  2. 如果节点 A 得到了节点 C 的响应，那么存下最新数据并返回给客户端。
  3. 如果节点 A 推断消息已经丢失（比如说消息超时），那么则返回曾经从节点 C 获得序列号最高的值（具体参见下面），或者初始值（如果没有从节点 C 获得过任何值）。
• 在节点 A 上执行写操作
  1. 节点 A 发送一个包含最新值得请求到节点 C 。
  2. 如果节点 A 得到了节点 C 的成功响应，那么节点 A 返回一个成功响应给客户端。
  3. 如果节点 A 推断消息已经丢失（比如说消息超时），那么节点 A 返回一个成功响应给客户端。
  4. 如果节点 A 仍然未得到节点 C 的成功响应，那么节点 A 再次发送一个包含最新值得请求到节点 C 。
  5. 如果节点 A 推断消息已经丢失（比如说消息超时），那么节点 A 每隔 t-4*t_timeout 秒重新执行步骤4。
• 节点 C 获取新的值
  1. 节点 C 将其序列号增加1。
  2. 节点 C 将最新值和它的序列号向其他所有节点进行广播。
  3. 如果节点 C 推断消息已经丢失（比如说消息超时），那么节点 C 每隔 t-2*t_timeout 秒重新向丢失消息的节点发送最新值和它的序列号。
  4. 重复执行步骤3直到所有节点都确认更新了值。

定理 4 以上修改过的中心化算法是延迟 t 一致的。
证明：所有数据写入操作的顺序是客户端写入操作后通知集中节点的顺序。集中式节点为每个操作分配一个序列号，这将确定所有写入操作的总顺序。每个读取操作都在其返回的值的写入操作之后进行。如果执行中的所有消息都已传递，那么此算法是原子的：集中式节点序列化所有请求，并确保正确地遵循部分顺序。如果一个操作已完成，则集中节点一定能收到通知，因此之后进行的操作不会颠倒顺序在完成操作之前进行。
  另一方面, 如果某些消息丢失, 则生成的执行可能不是原子的。假设写入发生在节点 A_w ，之后将在一个时间间隔中传递所有消息。到时间间隔结束时，A_w 将新值同步给中心节点，并且中心节点将同步此新值到所有其他节点。因此，在此间隔之后的操作不会出现在该写入操作之前。
  假设经过一段时间间隔，在这段时间内所有消息都已经被传递，有一个读取操作发生在节点 B_r。B_r 一定从中心节点 C 获取值，或者获取之前写入到节点 B_r 上的值。在前一种情况下，到此间隔结束时， C 将确保每个节点都收到的值至少与 B_r 返回的值一样新。在后一种情况下，到间隔结束时，B_r将向 C 发送最新值, C 将其转发到其他每个节点。因此，在此时间间隔之后，不会有其它操作能够插入到这个读操作之前。

5 结语

  在本文中，我们已经证明当网络中存在分区时，不可能提供兼顾可用性和原子一致的数据。但是实现这三个属性中的任意两个属性都是可行的：一致性、可用性和分区容错性。在异步模型中当没有时钟可用时，不可能的结果是相当强的：不可能提供一致的数据，甚至无法在消息丢失时返回陈旧的数据。但是在部分同步模型中，可以在一致性和可用性之间达成实际的妥协。特别是今天大多数实际的应用都被迫以返回“大部分数据, 大部分时间”来解决。形式化这一想法并研究实现这一想法的算法是未来理论研究的一个有趣的课题。

附录

[1] Attiya, Bar-Noy, Dolev, Koller, Peleg, and Reischuk. Achievable cases in an asynchronous environment. In 28th Annual Symposium on Foundations of Computer Science, pages 337–346, Los Angeles, California, October 1987.
[2] Eric A. Brewer. Towards robust distributed systems. (Invited Talk) Principles of Distributed Computing, Portland, Oregon, July 2000.
[3] Alan Fekete, David Gupta, Victor Luchangco, Nancy Lynch, and Alex Shvartsman. Eventually-serializable data services. Theoretical Computer Science, 220(1):113–156, June 1999.
[4] Maurice P. Herlihy and Jeannette M. Wing. Linearizability: A correctness condition for concurrent objects. ACM Transactions on Programming Languages and Systems, 12(3):463–492, July 1990.
[5] Leslie Lamport. On interprocess communication – parts i and ii. Distributed Computing, 1(2):77–101, April 1986.
[6] Nancy Lynch. Distributed Algorithms, pages 397–350. Morgan Kaufman, 1996.
[7] Nancy Lynch. Distributed Algorithms, pages 199–231. Morgan Kaufman, 1996.
[8] Nancy Lynch. Distributed Algorithms, page 581. Morgan Kaufman, 1996.
[9] Nancy Lynch. Distributed Algorithms, pages 735–770. Morgan Kaufman, 1996.