「译」CAP理论的FAQ

The CAP FAQ

Posted by S.L on December 1, 2018

译者注

英文原文相对难以理解,很多词汇使用的比较模糊,表达句式相对含蓄,这里翻译成中文本,欢迎交流指正。

Where did the CAP Theorem come from?

Dr. Eric Brewer在2000年的Principles of Distributed Computing会议上做了一个演讲,名为「Towards Robust Distributed Systems」,在这里他提出了CAP理论。但当时并未被证明。

两年以后,Seth Gilbert和Nancy Lynch教授(来自MIT的分布式系统领域学者)将Brewer的观点加以证明,并写了一篇论文「Brewer’s conjecture and the feasibility of consistent, available, partition-tolerant web services」。

What is a ‘read-write storage’?

CAP理论具体关注在一个理论上构建出来的模型——register。它是一个具有两个操作的数据结构:set(X)get()

而一个key-value存储设备可以理解为一系列的register组成的介质。虽然看起来很简单,但是它却表示了大多数分布式系统要做的事情:写数据和读出来。

What does atomic (or linearizable ) mean?

原子性或者说线性化的一致性,是用来保证调用get()操作时返回什么样的value是正确的。这个观点强调register对于所有的客户端来说看起来好像就是运行在一台机器上一样,并且返回的数据跟它收到的顺序的值是一样的。

考虑一个并发执行的场景,大量的clients同时请求。这些读取的操作的结果必须满足在原子性一致性下,和在一个串行的请求里发送所有这些请求的结果保持一致。

这个保证非常强,在最终一致性下,你会得到

set(10), set(5) , get() = 10

但是这个执行结果在原子性一致性下是非法的。

原子性一致性还保证关于register的值的外部通信是repected的。即,如果我读取到了X,然后告诉你我读到了X,你可以去调用寄存器的读取操作,然后也获取到X。在比较弱的保证下可能不是真的。

下面的操作中我们以A:表示A执行了:后面的操作

第一个例子就是原子的历史,B和A读取的值是一样的。

B: set(5), A:set(10), A:get() = 10, B:get() = 10

第二个例子就不是不是原子的历史,B读取的仍然是老的值,尽管此时已经更新了。

B:set(5), A:set(10), A:get() = 10, B:get() = 5

尽管它和下面的串行历史一样

B:set(5), B:get() = 5, A:set(10), A:get() = 10

在第二个例子中,如果A告诉B它从register读取到了10,B将会错误的认为可能有第三方已经在A:get()B:get()之间重新写了新的值5。如果不允许外部通信,B将不会知道A:set,所以认为看到的是一致性的结果,就好像B:get()真的是在A:set之前发生。

What does asynchronous mean?

一个异步网络指的是,在这里一个消息被传递多久或者被机器处理多久都是没有限定的。这个特性的一个后果是,我们无法区分机器失败了还是消息的传递被延迟了。

What doest available mean?

仅在所有的get或set请求最终返回一个「正确」的结果时才能说一个data store是available的。这里不允许「错误」的响应,因为一个系统只返回错误时不能被认为是真正的available。

但是对于响应的返回时间也没有限定,所以系统可以使用任意长的时间来处理请求。但是系统最终必须要返回结果才可以。

注意到available是一个很强也很弱的要求。说它强是因为100%的请求都必须返回响应,说它弱是因为对于响应时间并不做限制(但是不能是无限的时间)。

What is a partition?

网络分区指的是网络无法将消息传递给一个或多个节点,最终只能丢弃。注意,延迟传递并不是网络分区。

这个术语有时候指一段时间,在这段时间里没有消息可以成功的在两组节点间传递。这是一个更有限制性的失败模型。我们称其为total partition

CAP理论的验证依赖于total partition。事实上,这些是非常有可能发生的,因为所有的消息都可能从一个组件内传递出去,如果这个组件失败了,那么在两个节点之间将不会有任何消息传递,因为所有消息丢被丢弃了。

Why is CAP true?

一个client在一个partition的一端执行写操作之后,在另一端任何读操作都无法确定它们读取的数据是否来自最新的写操作。所以我们面临一个选择:是将可能是老旧的信息返回给读操作呢还是等待(可能一直等待)一直到另一端的写操作的数据同步过来呢?

其实这个是一构建验证,即我们构建一个单一的场景,在这个场景里一个系统不可能同时是一致的和可用的。CAP收到一些压力的原因一个是,这个构建的场景并不是完全不实际的。如果网络设备全部坏了,那么一个totoal partition的发生也是挺常见的。

When does a system have to give up C or A?

CAP理论仅保证了可能会有一些情况导致一个系统必须放弃C或者A。我们称这种场景为「critical condition」。CAP理论并没有描述这种场景出现的可能性有多大。但C和A都是强保证的:它们在所有操作都符合它们的要求的前提下是100%正确的。一个单一的不一致读取或者不可用的写操作,使得C或者无效。但是在这个「critical condition」来到之前,一个系统可以很好的处于一致性和可用性的状态,同时不会违背任何规则。

由于大多数分布式系统都是长期运行的,并且都会接受百万级的请求量。CAP告诉我们一定要小心:很有可能你会触碰到这个「critical condition」,所以你需要明智的知晓你的系统在不不满足A或者C的时候会如何失败。

Why do some people get annoyed when I characterise my system as CA?

虽然Brewer的演讲、Gilbert的论文和其他的实验结果声明让我们选择C/A/P中的两个。但是,这个观点一直被认为是一种误导性的表述,因为你并不能构建或者「选择」「partition tolerance」,你的系统要么已经可能是partitioned的了,或者它以后也不可能是。

我们最好将CAP理解为它是在描述一种妥协,即人们在构建一个可能受partition tolerance影响的系统时需要做的一种妥协。事实上,在分布式的世界里是不存在100%可靠的网络的。所以,至少在分布式的系统里,是不存在真实的CA的。你很可能经受partitions,因此你必须在某个时间做出妥协:C还是A。

因此将这个理论重写为下面的公式更具有启发性(虽然可以有争论):

Possibility of Partitions => Not(C and A)

也就是说,如果你的系统可能经受partitions,你不能同时选择C和A。

有些系统是不会受partitions影响的——单节点的数据库。这些系统并不是通常CAP描述其价值的范畴内的。如果你描述你的系统为CA,你一定是对一些概念产生了误解。

What about when messages don’t get lost?

Gilbert的论文中有一点比较让人吃惊的结果是没有一种原子寄存器在一个异步网络中可以随时都处于可用的状态,并且只有在没有消息丢失的前提下才可能是具有一致性的。

这个结果依赖于异构网络的特性,这里要强调的点是,由于不可能辨别出一个消息是否被丢弃了,因此一个节点不能一直无限等待响应同时还维持可用性,但是如果它响应的太早可能导致不一致的情况出现。

Is my network really asynchronous?

是的,虽然有些讨论的余地。不同的网络具有很多不同的特质。

如果你的系统满足,

  • 一些机器上没有clock或者这些clock没有做实时同步
  • 系统的处理能力会不定期的延迟对消息的投递(如重试或GC导致的停顿)

那么你的网络自然可以认为是异步的。

Are C and A ‘spectrums’?

其实并没有必要将C和A看成一个范围的两端,虽然CAP理论说这两个指标很重要,但是我们仍然可以不必纠结这两个点的非你即我来设计一个useful的系统。事实上,CAP是再告诉我们,你可以不必纠结于A或者C,甚至A和C你都可以不去考虑实现。这个责任交给开发者自己,即在设计系统的时候可以考虑在什么时候可、以什么样的程度来使用A和C的特性。

有些真实的系统选择了consistency而不是avaiability,比如zookeeper。其他系统如Amazon的DynamoDB选择了提供更高的可用性,而降低了对consistency的要求。

Is a failed machine the same a partitioned one?

不是的。一个失败的机器是不需要去响应客户端的请求的。CAP里是不允许出现失败的机器的。

Is a slow machine the same as a partitioned one?

不。慢机器最终仍然还是会收到消息,但是你永远不可能将消息传递到一个已经处于网络分割的环境中。但是,慢机器使得区分丢失消息(或者失败的机器)和机器的慢变得很困难。这一难点是为什么CAP,FLP和其他结果是正确的理论的核心点。

Have I ‘got around’ or ‘beaten’ the CAP theorem?

不。你可能设计一套并没有被CAP严重影响的系统,这就已经很好了。

Reference

  • https://www.the-paper-trail.org/page/cap-faq/

本文首次发布于 S.L’s Blog, 作者 @stuartlau , 转载请保留原文链接.