Brewer的猜想和一致性、可用性、分区容忍性的Web服务的可行性外文翻译资料

Brewers Conjecture and the Feasibility of Consistent, Available,

Partition-Tolerant Web Services

Seth Gilbert and Nancy Lynch

Laboratory for Computer Science

Massachusetts Institute of Technology

Cambridge, MA 02139

sethgcopy;mit, edu, lynchcopy;theory. Ics. mit. edu

Abstract

When designing distributed web services, there are three properties that are commonly desired: consistency, availability, and partition tolerance. It is impossible to achieve all three. In this note, we prove this conjecture in the asynchronous network model, and then discuss solutions to this dilemma in the partially synchronous model.

1 Introduction

At PODC 2000, Brewer , in an invited talk , made the following conjecture: it is impossible for a web service to provide the following three guarantees:

bull; Consistency

bull; Availability

bull; Partition-tolerance

All three of these properties are desirable - and expected - from real-world web services. In this note, we will first discuss what Brewer meant by the conjecture; next we will formalize these concepts and prove the conjecture; finally, we will describe and attempt to formalize some real-world solutions to this practical difficulty.

Most web services today attempt to provide strongly consistent data. There has been significant research designing ACID databases, and most of the new frameworks for building distributed web services depend on these databases. Interactions with web services are expected to behave in a transactional manner: operations commit or fail in their entirety (atomic), transactions never observe or result in inconsistent data (consistent), uncommitted transactions are isolated from each other (isolated), and once a transaction is committed it is permanent (durable). It is clearly important, for example, that billing information and commercial transaction records be handled with this type of strong consistency.

Web services are similarly expected to be highly available. Every request should succeed and receive a response. When a service goes down, it may well create significant real-world problems; the classic example of this is the potential legal difficulties should the E-Trade web site go down. This problem is exacerbated by the fact that a web-site is most likely to be unavailable when it is most needed. The goal of most web services today is to be as available as the network on which they run: if any service on the network is available, then the web service should be accessible.

Finally, on a highly distributed network, it is desirable to provide some amount of faulttolerance. When some nodes crash or some communication links fail, it is important that the service still perform as expected. One desirable fault tolerance property is the ability to survive a network partitioning into multiple components. In this note we will not consider stopping failures, though in some cases a stopping failure can be modeled as a node existing in its own unique component of a partition.

2 Formal Model

In this section, we will formally define what is meant by the terms consistent, available, and partition tolerant.

2.1 Atomic Data Objects

The most natural way of formalizing the idea of a consistent service is as an atomic data object. Atomic , or linearizable , consistency is the condition expected by most web services today. Under this consistency guarantee, there must exist a total order on all operations such that each operation looks as if it were completed at a single instant. This is equivalent to requiring requests of the distributed shared memory to act as if they were executing on a single node, responding to operations one at a time. This is the consistency guarantee that generally provides the easiest model for users to understand, and is most convenient for those attempting to design a client application that uses the distributed service. See Chapter 13 of for a more complete definition of atomic consistency.

2.2 Available Data Objects

For a distributed system to be continuously available, every request received by a non-failing node in the system must result in a response. That is, any algorithm used by the service must eventually terminate. In some ways this is a weak definition of availability: it puts no bound on how long the algorithm may run before terminating, and therefore allows unbounded computation. On the other hand, when qualified by the need for partition tolerance, this can be seen as a strong definition of availability: even when severe network failures occur, every request must terminate.

2.3 Partition Tolerance

The above definitions of availability and atomicity are qualified by the need to tolerate partitions. In order to model partition tolerance, the network will be allowed to lose arbitrarily many messages sent from one node to another. When a network is partitioned, all messages sent from nodes in one component of the partition to nodes in another component are lost. (And any pattern of message loss can be modeled as a temporary partition separating the communicating nodes at the exact inst ant the message is lost.) The atomicity requirement (sect;2.1) therefore implies that every response will be atomic, even though arbitrary messages sent as part of the algorithm might not be delivered. The availability requirement (sect;2.2) implies that every node receiving a request from a client must respond, even though arbitrary messages that are sent may be lost. Note that this is similar to wait-free termination in a pure shared-memory system: even if every other node in the network fails (i.e. the node is in its own unique component of the partition), a valid (atomic) response m

剩余内容已隐藏，支付完成后下载完整资料

Brewer的猜想和一致性、可用性、分区容忍性的Web服务的可行性

Seth Gilbert，Nancy Lynch

摘要：

在设计分布式Web服务时，通常要求三个属性：一致性，可用性和分区容忍性。同时实现三个属性是不可能的。在本文中，我们会在异步网络模型中证明这个猜想，然后讨论在部分同步模型中这个困境的解决方案。

1简介

在PODC 2000上，Brewer在一篇受邀的演讲中做出了以下推测：一个Web服务不可能提供以下三个保证：

bull;一致性

bull; 可用性

bull;分区容忍性

所有这三个属性都是现实世界的Web服务所期望的。在这篇文章中，我们将首先讨论Brewer 猜测表达了什么意思;接下来我们将正式化这些概念并证明猜想；最后，我们将描述和尝试正式化一些现实世界的解决方案来解决这个实际困难。

当今的大多数web服务试图提供强一致的数据。已有大量研究设计ACID数据库，大多数用于构建分布式Web服务的新框架都依靠这些数据库。与Web服务的交互预期以事务方式表现：操作完全提交或失败（原子），事务从未观察到或导致不一致的数据（一致），未提交的事务彼此隔离（隔离），并且一旦事务提交，则它是永久的（持久）。显然重要的是，例如，用这种强一致性来处理计费信息和商业交易记录。

类似地，Web服务也希望高度可用。每个请求应该发送成功并接收响应。当服务下降时，可能会产生重大的现实问题;典型例子是电子贸易网站倒闭时的潜在法律困难。这个问题因网站在高访问量下奔溃的事实而加剧。当今大多数web服务的目标是像在其上运行的网络一样可用：如果网络上的任何服务可用，则web服务应该是可访问的。

最后，在高度分布式网络上，期望提供一定量的故障容忍度。当一些节点崩溃或一些通信链路失败时，重要的是服务仍然如预期那样进行。一个令人满意的容错性质是经受网络分割成多个组件的能力。在本文中，我们不会考虑停止故障，虽然在某些情况下，停止故障可以被建模为存在于其自己的分区的唯一组件中的节点。

2形式模型

在本节中，我们将正式定义术语一致，可用和分区容忍的含义。

2.1原子数据对象

将一致性服务的想法形式化的最自然的方式是作为原子数据对象。原子或线性化，一致性是当今大多数Web服务所期望的条件。 在此一致性保证下，必须在所有操作上存在总的操作次序，以使每个操作看起来好像是在单个时刻完成。这等效于要求分布式共享存储器的请求好像它们在单个节点上执行一样，一次响应一个操作。这是一致性保证，通常提供最简单的模型供用户理解，并且对于那些试图使用分布式服务客设计客户端应用程序的人来说是最方便的。有关原子一致性的更完整定义，请参见第13章。

2.2可用数据对象

为了使分布式系统能够持续可用，系统中的非故障节点接收的每个请求都必须产生响应。也就是说，服务使用的任何算法必须最终终止。在某些方面，这是可用性的弱定义：它不限制算法可以在终止之前运行多长时间，因此允许无限计算。另一方面，当由需要分区容性限定时，这可以被视为可用性的强定义：即使发生严重的网络故障，每个请求必须终止。

2.3分区容差

上述可用性和原子性的定义由允许分区的需求限定。为了塑造分区容忍性，网络将允许丢失从一个节点发送到另一个节点的任意多个消息。当网络被分区时，从分区的一个组件中的节点发送到另一个组件中的节点的所有消息都将丢失。（并且消息丢失的任何模式可以被建模为临时分区，其在消息被丢失的确切时刻分隔通信节点）。因此，原子性要求（sect;2.1）意味着每个响应将是原子的，即使任意消息作为算法的一部分发送可能不会传送。可用性要求（sect;2.2）意味着，从客户端接收请求的每个节点必须响应，即使发送的任意消息可能丢失。注意，这类似于纯共享内存系统中的无等待终止：即使网络中的每个其他节点都失败（即，节点在其自己的分区的唯一分量中），有效（原子）响应必须是生成。不允许任何小于总网络故障的故障导致系统响应不正确。

3异步网络

3.1不可能结果

在证明这一推测，我们将使用异步网络模型，正如Lynch在第8章中所定义的。在异步模型中，没有时钟，并且节点必须仅基于接收的消息和本地计算做出决定。

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

bull; 可用性

bull;原子一致性

在所有公平执行中（包括消息丢失的那些）。

证明：我们通过矛盾来证明这一点。假设存在满足三个标准的算法A：原子性，可用性和分区容忍性。我们构造一个存在返回不一致响应请求的执行A。该方法类似于Attiya等人的证明和林奇（定理17.6）。假设网络由至少两个节点组成。因此，它可以被分成两个不相交的非空集合：{G1，G2}。证明的基本思想是假设G1和G2之间的所有消息都丢失。如果在G1中发生写操作，并且稍后在G2中发生读操作，则读操作不能返回早先写操作的结果。

更正式地说，让v0是原子对象的初始值。令alpha;1是A的执行的前缀，其中在G1中发生不等于v0的值的单次写入，以写操作的终止结束。假设在G1或G2中没有发生其他客户端请求。此外，假设在G2中没有接收到来自G1的消息，并且在G1中没有接收到来自G2的消息。我们知道，根据可用性要求，此写入完成。类似地，假设a2是其中在G2中发生单个读取的执行的前缀，并且没有其他客户端请求发生，以读取操作的终止结束。在alpha;2期间，在G1中没有接收到来自G2的消息，并且在G2中没有接收到来自G1的消息。再次，我们知道读取按可用性要求返回一个值。此执行返回的值必须为v0，因为在alpha;2中没有发生写操作。

令alpha;是以a1开头并以alpha;2继续的执行。对于G2中的节点，alpha;与alpha;2不可区分，因为从G1到G2的所有消息丢失（在a1和a2中，它们一起构成a），并且a1不包括对G2中的节点的任何客户端请求。因此，在alpha;执行中，读请求（从alpha;2）仍然必须返回v0。然而，读请求不会开始，直到写请求（从alpha;1）完成之后。因此，这与原子性属性相矛盾，证明没有这样的算法存在。

推论1.1在异步网络模型中不可能实现保证以下属性的读/写数据对象：

bull;可用性，在所有公平执行中，

bull;原子一致性，公平执行中不丢失任何消息。

证明：主要思想是在异步模型中，算法无法确定消息是否已经丢失，或者已经在传输信道中被任意地延迟。因此，如果存在保证在没有消息丢失的执行中的原子一致性的算法，则将存在保证所有执行中的原子一致性的算法。这将违反定理1。

更正式地，为了矛盾，假设存在总是终止的算法A，并且保证在传递所有消息的公平执行中的原子一致性。此外，定理1意味着A不保证所有公平执行中的原子一致性，因此存在一些公平执行v，其中一些响应不是原子的。

在执行中的某个有限点alpha;，算法A返回不是原子的响应。令alpha;是以无效响应结束的前缀。接下来，将alpha;扩展到公平执行alpha;rsquo;rsquo;，其中递送所有消息。执行alpha;rsquo;rsquo;现在是公平的执行，其中所有消息被递送。但是这个执行不是原子的。因此，不存在这样的算法A.

3.2异步模型中的解决方案

虽然不可能提供所有三种性质：原子性，可用性和分区容差，但是可以实现这三种性质中的任意两种。

3.2.1原子，分区容限

如果不需要可用性，那么很容易实现原子数据和分区容忍性。忽略所有请求的平凡系统满足的这些要求。然而，我们可以提供更强的活跃性标准：如果执行中的所有消息都被传递，则系统可用并且所有操作终止。一个简单的集中式算法满足这些要求：单个指定节点维护对象的值。接收请求的节点将该请求转发到指定的节点，该节点发送响应。当接收到确认时，节点向客户端发送响应。

许多分布式数据库提供这种类型的保证，特别是基于分布式锁定或仲裁的算法：如果发生某些故障模式，则活跃性条件被削弱，并且服务不再返回响应。如果没有故障，则保证活性。

3.2.2原子，可用

如果没有分区，则显然可以提供原子的，可用的数据。事实上，第3.2.1节中描述的集中式算法满足这些要求。在内部网和LAN上运行的系统是这些类型的算法的示例。

3.2.3可用，分区容忍

如果不需要原子一致性，则可以提供高可用性和分区容限。如果没有一致性要求，则服务可以平滑地返回v0，初始值，以响应每个请求。然而，可以在可用的，分区容忍设置中提供弱化的一致性。 Web缓存是弱一致性网络的一个示例。在第4.4节中，我们考虑可能较弱的一致性条件之一。

4部分同步网络

4.1部分同步模型

试图规避定理1的不可能性结果的最明显的方法是实现在现实世界中，大多数网络不是纯异步的。如果允许网络中的每个节点都有时钟，则可以构建更强大的服务。

对于本文的其余部分，我们假设一个部分同步模型，其中每个节点都有一个时钟，并且所有时钟以相同的速率增加。然而，时钟本身不同步，因为它们可以在相同的实时显示不同的值。实际上，时钟用作定时器：过程可以观察以测量已经过去了多少时间的局部状态变量。本地定时器可以用于调度在某些其它事件之后的某个时间间隔内发生的动作。此外，假设每个消息在给定的已知时间tmsg内递送，或者它丢失。此外，每个节点在给定的已知时间内处理接收的消息：tlocal，并且本地处理花费零时间。这可以被形式化为由Lynch在第23章中描述的通用定时自动机模型的特殊情况。

4.2不可能结果

当任意消息可能丢失时，即使在部分同步模型中，仍然不可能具有始终可用的原子数据对象。也就是说，定理I的以下类似定理成立：

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

bull; 可用性

bull;原子一致性

在所有执行（即使那些消息丢失）。

证明：这个证明与定理1的证明非常相似。我们将遵循相同的方法：将网络分成两个组件（G1〜G2），并构造一个可接受的执行，其中在一个组件中发生写，随后在另一个组件中执行读操作，这个读操作可以显示为返回不一致的数据。

更正式地说，在定理1中构造执行alpha;1与前面一样：在G1中发生单个写入请求和确认，并且两个分量（G1，G2}之间的所有消息都丢失，我们将构造第二个执行alpha;2，使得alpha;2是以长时间间隔开始的执行，在该时间间隔期间没有客户端请求发生，该间隔必须至少与整个alpha;1的持续时间一样长，然后将alpha;2的事件附加到alpha;2 ，如上面定理1中定义的：在G2中的单个读取请求和响应，再次假设两个组件之间的所有消息都丢失。最后，通过叠加两个执行alpha;1和alpha;2构造alpha;，alpha;2中的时间间隔确保读操作开始前写操作已经完成。但是，如在定理1中，读请求返回初始值，而不是由写请求写入的新值，违反原子一致性。

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

然而，在部分同步模型中，推论1.1的类似性不成立。这个推论的证明事实上取决于节点不知道消息何时丢失。存在部分同步算法，当执行中的所有消息被递送时（即，没有分区）将返回原子数据，并且当消息丢失时将仅返回不一致的（并且特别是过时的）数据。这种算法的一个示例是在3.2.1节中描述的集中协议，被修改为超时丢失消息。在读（或写）请求时，向中央节点发送消息。如果接收到来自中央节点的响应，则节点递送所请求的数据（或确认）。如果在2 * tmsg tlocal内没有收到响应，则节点断定消息已丢失。然后，向客户端发送响应：本地节点的最佳已知值（用于读取操作）或确认（用于写入操作）。在这种情况下，可能违反原子一致性。

4.4较弱的一致性条件

虽然保证原子数据将在所有消息被传递的执行中返回（在一定时间范围内）是有用的，但同样重要的是指定在执行中发生的一些消息丢失的情况。在本节中，我们将讨论一个可能较弱的一致性条件，它允许在存在分区时返回陈旧的数据，但仍然对返回的陈旧数据的质量提出形式要求。这种一致性保证将要求在没有消息丢失的执行中的可用性和原子一致性，并且因此不可能保证在异步模型中作为推论1.1的结果。

定义3读写对象的定时执行a是t-Connected如果两个条件成立，则一致。首先，在没有消息丢失的执行中，执行是原子的。其次，在消息丢失的执行中，在v_中的操作上存在部分顺序P，使得：

1.定义所有写操作，并命令所有与写操作有关的读操作。

2.每次读操作返回的值正好是P中上一次写操作写入的值，如果在P中没有这样的先前写操作，则为初始值。

3.P中的顺序与在每个节点处提交的读取和写入请求的顺序一致。

4.假设存在长于t的时间间隔，其中没有消息丢失。此外，假设操作theta;在间隔开始之前完成，并且另一操作cent;在间隔结束之后开始。那么cent;不在部分阶数P中的theta;之前。

此保证在消息丢失时允许一些陈旧的数据，但是一旦分区恢复，提供了一致性返回所需的时间限制。这个定义当然可以被推广以在仅连接一些节点时以及当连接仅在一些时间可用时提供一致性保证。这些概括将在未来的工作中进一步研究。

第4.3节中描述的集中式算法的变体是t连接一致。假设节点C是集中式节点。算法的行为如下：lt;

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[140868]，资料为PDF文档或Word文档，PDF文档可免费转换为Word