[toc]

原文

摘要

当设计分布式的 web 服务时, 有三个经常考虑到的属性: 一致性 (consistency), 可用性(availability)和分区容错性(partition tolerance). 三者是不可能同时达到的. 在这个文章里, 我们将会在一个异步网络模型中证明这个猜想, 然后在部分同步模型中讨论解决这个问题的方案.

1 Introduction

Brewer 受邀在 PODC 2000 上讲话时发表了一个猜想: 在一个(分布式)的 web 服务中是不可能同时保证以下三点的:

  • 一致性
  • 可用性
  • 分区容错性

这三点是真实的 web 服务所关注而且所期望的. 在这个文章中, 我们先会讨论 Brewer 在这个猜想中想表达什么; 然后我们会具体化这些概念并证明猜想; 最后我们将描述并尝试正式确定一些针对此实际困难的现实解决方案.

当今大多数的 web 服务尝试提供强一致性的数据. 在设计 ACID 数据库这方面已经有足够的研究了, 而且大多数 web 服务的新框架都是依赖与这些数据库的. Web 服务之间的交互都被期望是以一种事务的(transactional)方式进行: 操作在提交时要么全部成功要么全部失败(原子性), 提交过的事务能够被以后所有的事务看到(一致性), 未提交的事务之间是相互隔离的(隔离性), 一旦事务被提交它应该是永久的(持久性). 这显然是很重要的， 例如账单信息和商业交易记录保持强一致性.

同样, web 服务也被期望是高可用的. 每个请求都应该会成功而且能够收到一个响应. 当服务 down 掉了, 它会产生一些很明显的现实世界问题: 典型的例子是如果一个网上交易的网站 down 了, 那么它会有一些潜在的法律上困难问题. 如果一个网站在最需要它是却不能访问, 那么这个问题会更加恶化. 当今大多数的 web 服务的目标都是像他们使用的网络那样可靠: 只要任意一个服务是可用的, 那么整个 web 服务就是可访问的.

最后, 在一个高度分布式的网络中, 需要提供一定的容错能力. 当一些节点崩溃或者连接失败时, 服务能够照常工作是非常重要的. 能够在网络被分为多个部分时仍然能够 survive, 是理想的容错能力. 在这个文章中不会谈论到 stopping failures, 尽管有些情况下可以把 stopping failures 比做存在于分区自身唯一组件中的节点.

2 Formal Model

在这节中, 我们会正式定义单词一致性, 可用性和分区容错性的含义.

2.1 Atomic Data Objects

具体化一个一致性服务最自然的方式是原子数据对象(atomic data object). 原子性或者线性化、一致性是当今大多数 web 服务所期望的. 为了保证一致性, 对于所有的操作必须有一个全局的顺序, 就像所有的操作看上去在一个实例上完成的. 这等等效于要求分布式的请求分享内存, 像在同一个节点上执行, 每次响应一个操作. 原子读/写共享内存的一个重要属性是, 在写操作完成之后开始的任何读操作都必须返回该值, 或以后写操作的结果.(为什么是还能是 or the result of a later write operation ?) 通常来说, 这是用户最容易理解的, 能提供一致性保证的模型. 对于尝试设计使用分布式服务的客户端应用程序的用户而言, 这是最方便的。

2.2 Available Data Objects

为了使一个分布式系统持续式可用, 系统中非故障节点受到的每个请求都必须产生响应. 也就是说, 服务使用的任何额算法都最终都必须中止. 在某些情况下有一种可用性的弱定义: 不对这个算法在中止之前放入运行时之间做限制, 因此允许无限制的计算. 从另一方面来说, 为了满足分区容错, 这可以被看作是可用性的强定义: 即使发生了严重的网络错误, 每个请求都应该获得中止(有响应).

2.3 Partition Tolerance

上面关于可用性和原子性的定义都是为了满足分区容错. 为了建模分区容错, 网络可能会随意丢掉任意数量从一个节点发往另一个节点的消息. 当网络发生了分区, 所有的从某一个分区的某个节点发往另一个分区的某个节点的消息都会丢失. (任意形式的消息丢失都可以建模为, 在消息丢失的瞬间将通信节点分开的临时分区)

原子性(2.1)意味着每个响应都必须是原子的, 即使算法中的有些消息不会被传递. 可用性(2.2)意味着所有收到的请求都必须有响应, 即使有些消息可能会丢失. 注意这和一个纯共享内存系统中的的非等待中止(wait-free termination)有点像: 即使网络中的其他节点都失败了(这个节点再在他自己唯一的网络分区里), 也必须产生一个合法的响应. 除了网络完全失败之外, 不允许系统出现不正确的响应.

3 Asynchronous Networks

3.1 Impossibility Result

为了证明这个猜想, 我们将使用异步网络模型, 如 Lynch 在 [7] 中描述的一般. 在异步网络模型中, 没有时钟, 节点职能通过收到的消息和本地的计算来作出决定.

定理 1 在异步网络模型中, 不可能实现一个读/写的数据对象, 在全部都是对等运算时(包括那些消息可能会丢失的情况), 都满足下面的特性:

  • 可用性 Availability
  • 原子一致性 Atomic consistency

证明: 我们使用反证法. 假设一个算法 A 存在, 能够满足三个准则: atomicity, availability 和 partition tolerance. 我们将构建一次 A 的执行, 其中存一个返回不一致响应的请求. 证明的方法类似于 Attiya [1] 等人和 Lynch [8] 用过的方法. 假设网络至少由两个节点组成. 因此网络可以被划分成两个不相交的非空集合: ${G_1,G_2}$. 证明这个问题的核心思路是假设在 $G_1$ 和 $G_2$ 之间的消息全部丢失. 然后有一个 $write$ 操作在 $G_1$ 上发生, 然后有一个 $read$ 操作在 $G_2$ 上发生, 然后 $read$ 操作并不能返回稍早前 $write$ 操作的结果.

更正式一点, 使某个原子对象(atomic object)的初始值为 $v_0$. 使 $\alpha_1$