春水煎茶
图片来自 rockbridgeinvest

分布式的CAP定理和一致性模型

· · 源自博客「春水煎茶」

CAP定理是分布式领域中闻名遐迩的一个基石定理, 它表达了一个「鱼和熊掌不可兼得」的遗憾事实: 我们必须从一致性、可用性和分区容忍性中选择两个。 事实上,现实中我们只能从一致性和可用性中选择一个, 因为分区容忍性不可舍弃。 然而,人们对于CAP定理的诸多概念和描述都是颇为模糊的, 比如:「分区容忍性」这个CAP中最不好理解的性质究竟是什么, 我们常说的一致性和CAP定理中的一致性是一回事吗? 大家声称的「高可用」是指什么? 带着这些问题,本文将详细讨论以下内容:

  • 从一个例子看为什么CAP定理是成立的
  • CAP定理的内容 – 我们要抠概念
  • 一致性 – 一致性和一致性的强弱模型、代价。
  • 可用性 – 可用性的强弱、高可用和故障转移
  • 分区容忍性 – 分区现象和分区容忍性

§ 从设计一个数据存储系统开始

首先,我们从一个数据存储系统的设计开始讨论。

我们希望设计一个数据存储系统,它具有以下美好的性质:

  1. 可用性: 收到请求总会响应。
  2. 一致性: 两次读请求,总会返回一致的结果。

这两条性质看上去如此简单,却蕴含了人们对分布式系统的无限追求。

对于单节点的系统来说,想要达到这两条性质或许并不难。 我们可以把客户端的请求用队列做线性化处理, 例如下面的图1.1:

图1.1 - 单节点的数据存储系统

上面的图1.1中,横向黑色实线是物理时间轴, 红色长条是写操作,蓝色长条是读操作。

图中的事件顺序是线性化的,也就是「先收到一定先返回」:

  1. $W_{1}$ 请求把数据 $a$ 写为 $1$。
  2. $R_{1}$ 请求读取 $a$ 的值,此时 $W_{1}$ 仍未处理结束。
  3. $W_{1}$ 执行完成,返回 $ok$。
  4. 处理 $R_{1}$, 并返回 $1$ 。
  5. 收到并处理 $R_{2}$ ,返回 $1$ 。

下面图1.2是稍复杂些的单节点系统,包含了「并发读写」和「并发写」的情况。 可以看到,采用线性化方式处理请求的单节点系统是具备一致性的。

图1.2 - 单节点系统+线性化处理

然而,单节点系统有以下问题:

  1. 服务能力有限。
  2. 单点风险: 一旦这个节点故障,整个系统将不可用。

更一般地,我们要讨论多节点的分布式系统。 下面的图1.3中是一个由 $P_{1}$ 和 $P_{2}$ 构成的两节点分布式系统。

图1.3 - 两节点分布式系统

可以注意到,为了 $R_{1}$ 可以在 $W_{1}$ 写入完成后返回正确的查询结果 $1$, 那么 $P_{1}$ 和 $P_{2}$ 之间必然有数据同步。 我们先不论具体的数据同步机制是怎样的, 而是先考虑一个问题:这个网络同步是否可靠?

现实中,网络同步必然有丢包、甚至中断的情况,也就是一定会存在某个时刻, $P_{1}$ 和 $P_{2}$ 是无法网络连通的, 也就是发生了分区现象

图1.4 - $P_{1}$ 和 $P_{2}$ 发生网络分区的示意图

当分区发生时,我们结合下面的图1.5,得出以下结论:

  1. 如果系统要具有可用性, $R_{1}$ 就必须返回, 由于未同步到副本数据,它只能返回 $0$ , 这和 $R_{2}(a) \rightarrow 1$ 的结果是不一致的。
  2. 如果 $R_{1}$ 拒绝服务, 即放弃 $P_{2}$ 的可用性, 客户端只能查询另一个节点 $P_{1}$ 拿到一致性的结果。
图1.5 - 可用性和一致性不可兼得

我们似乎认识到,在网络发生分区的情况下,我们必须在可用性和一致性之间做出选择

§ 读写同一节点,可以避开分区影响吗?

思路延伸一下,如果我们要求客户端的读写请求全部走同一个节点 $P_{1}$ 呢, 这样 $P_{2}$ 是否得到及时同步就不重要了。

这种情况下, 形成了一种主备结构,$P_{1}$ 叫做主节点, $P_{2}$ 叫做备节点。 只有主节点面向客户端提供服务, 备节点一般不提供服务,只作为数据备份。

貌似这样摆脱了网络分区的影响,但是对于 $P_{1}$ 来讲,面临着和前面讨论的单节点系统完全相同的问题: 服务能力有限、存在单点风险。

即便 $P_{2}$ 可以在 $P_{1}$ 故障后进化成为新的主节点, 来消除单点风险。 但是,网络分区一旦出现, $P_{1}$故障前瞬间的写请求仍然不可同步到 $P_{2}$, 就会造成数据丢失以及后续请求的不一致性。

图2.1 - 主备结构的$P_{1}$ 和 $P_{2}$

§ 数据同步的两种方式

我们有说 “节点间必然有数据同步的机制, 不然无法读取到跨节点的写更新”。

数据同步的方式可以分为:

  1. 同步: 所有节点写入完成后,返回写入成功。
  2. 异步: 先返回写入成功,再同步到其他节点。

下面的图3.1是两种数据同步方式的示例,紫色长条表示数据备份:

图3.1 - $P_{1}$ 和 $P_{2}$ 的数据同步方式

当然,同步和异步的方式并不是绝对的, 我们可以设计出先同步写 $N$ 个节点,回复客户端,再异步写入其他节点的方式。

不过,我们稍加分析即可以发现, 网络分区发生的时候,无论同步还是异步的方式,如果不放弃可用性,都不能保证一致性。

图3.2 - $P_{1}$ 和 $P_{2}$ 的数据同步 - 网络分区发生的时候

§ CAP定理

经过前面的一番讨论之后,所谓「CAP定理」已经呼之欲出了。

CAP定理又叫做布鲁斯定理, 该定理源于埃里克·布鲁尔在2000年的分布式计算原理研讨会上提出的一个猜想, 在2002年麻省理工学院的Gilbert和Lynch发表了证明[1],使之成为一个定理:

分布式系统不可能同时保证 一致性(Consistency)可用性(Availability)分区容忍性(Partition tolerance)

这就是所谓「CAP」的名字由来,我们只能在 $C$、$A$、$P$ 中三个性质中选两个。

这个定理也可以表达为:在网络分区发生的情况下,分布式系统不能同时保证一致性和可用性。 除非是单节点系统, 否则无法同时保证$CA$。

这个结论已经在分布式领域已经耳熟能详, 不过, 关于CAP定理,需要特别注意搞清楚以下两点:

  1. CAP定理范畴下的一致性、可用性、分区的概念都是非常狭义的
    • CAP所说的一致性其实是线性一致性。
    • CAP所说的可用性其实是非常高的可用性。
  2. 分区现象在现实网络中不可避免,也就是说,现实中我们只能在 $C$ 和 $A$ 中做选择。

CAP其实在说强一致性和高可用性,二者择其一。 至此,我们或许仍然不能深刻地理解CAP定理, 这需要进一步分别讨论这三个性质。

§ 分区容忍性 | Partition tolerance

在前面的讨论中,我们曾多次提到「分区现象」, 正是这个问题导致我们无法同时具备一致性和可用性上。 要了解分区容忍性,就要先了解什么是分区现象。

当两个节点之间的网络不再连通,相当于分成了几块分区,所以叫做分区现象

下面的图4.1是一个网络分区现象的示意图, 图中出现了三个分区:

图4.1 - 分区现象示意图

分区所强调的是节点间的不连通问题,即使每个节点都可以工作。 简单来说,Partition != Crash。 节点故障一般会造成节点的无响应,导致分区出现, 但是分区的出现不一定代表节点真的故障(宕机)了。

CAP定理中对分区的定义[1]是相对狭义的, 比连通性更广义的分区界定是按通信时限的说法: 如果不能在通信时限内达成数据一致,就意味着发生了分区。 例如下面图4.2中,数据同步的消息多次重试后,两个节点没有在一定时限内达成数据一致,此时即认为发生了分区。

图4.2 - 分区现象示意图

分区现象的概念清楚了后,我们看分区容忍性:

在分布式系统中, 分区容忍性是指即使分区现象发生,系统仍然可以工作的性质

Continues to function even if there is a “partition”.

换句话说,系统不能在分区发生的时候,选择停机来躲过分区影响的时段。

分区容忍性没有要求分区发生时返回数据的正确性,也没有要求不能回复客户端错误消息, 只有一个约束,就是「不能在分区时停机」。 我们回头看下上面的图4.2,在分区发生时, $W_{1}$ 最终返回了错误消息 $Timedout$, 即放弃可用性,保证一致性。

现实中的分布式网络,丢包、延迟、中断都是存在的, 所以在实际的系统设计中,分区容忍性是必选的。 也就是说,我们只能在可用性和一致性这两个性质中做选择。

§ 可用性 | Availability

先用最直观地方式理解下其含义:

在分布式系统中,可用性是指每次请求都能获取到非错的响应的性质

Availability = Reads and writes always succeed.

下面的图5.1中, 左边的 $S_{1}$ 具有可用性; 右边的 $S_{2}$ 则不具有可用性。 因为在 $S_{2}$ 中, 由于系统设计的原因,并发写和并发读写导致了带有错误的回复消息。

图5.1 - 可用性是指读写都必须无错响应

可用性并没有要求读到的数据的正确性,只描述了系统可以总可以非错的工作的能力

同样,我们看一下,CAP定理的证明者Gilbert和Lynch的描述[1]

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.

如果客户端发送一个请求给分布式系统中的一个无故障的节点, 这个节点必须回复请求。

就是,系统所用的任何算法都必须最终结束。

网络分区发生可能持续任意长时间, 如果被请求的节点在一定时间内无法响应, 或者直接简单地响应一个超时或者拒绝服务的错误, 都是不具备可用性的。

图5.2 - 响应错误 或者 长时间后再响应,都不具备可用性

那么,节点故障时,我们是否可以仍然保证可用性?

方法是故障转移: 把故障节点的负载转移给备份节点负责。 下面的图5.3演示了主备结构下的故障转移:

图5.3 - 故障转移

我们注意到,CAP定理对可用性的定义存在一个non-failing的限定语。 也就是说,在CAP的范畴下,如果一个系统没有做好故障转移的逻辑, 那么这个系统不具备可用性

CAP定理中的可用性的定义,可以说很强,也可以说很弱:

  1. 很强,是因为要求必须响应100%的请求。
  2. 很弱,是因为并没有要求响应的时限,只需要最终返回。

而通常我们对系统的响应时限是有要求的, 所以说CAP定理中的可用性的条件很强, 在CAP范畴下,没有「可用性的强弱程度」一说。

综合看来, CAP定理中对可用性的定义是狭义的

在实际中,可用性却不是一个非黑即白的简单判定, 和工程上对一致性的概念类似,存在不同可用性高低之分的说法。 我们常说的高可用性 high availability, 一般是指部分节点损失后整个系统仍可以正常工作。 要达成高可用性,就必须做好故障转移。 所以我们也可以说,CAP定理中的可用性其实是我们所说的高可用性 (而且是最高的可用性)

下面我们列举两种保可用性的方法,都是万变不离其宗地围绕着「故障转移」这个出发点。

一个方式是通过代理完成故障转移, 这就是工程上熟知的基于代理方式的负载均衡 (注:负载均衡的主要目的虽然是合理分配负载,但可用性也是其带来的好处之一)。

下面图5.4是一个例子。 当 $P_{1}$ 故障时,代理服务可以发现并暂时把 $P_{1}$ 从代理列表里踢出。 把后续的请求转发到健康的 $P_{2}$ 上去。

图5.4 - 通过代理完成故障转移

还有一种方式,我们甚至可以 配合客户端完成故障转移。 这就是另外一个工程上常用的负载均衡方案, 叫做「客户端侧的负载均衡」。 下面图5.5是一个例子, 客户端可以通过监测目标系统的服务器健康情况, 来决定向哪一个节点发起请求。

图5.5 - 配合客户端完成故障转移

此外,实践中,还可以通过减少人工维护造成的系统宕机、 gracefully-shutdown、添加系统报警等手段来提高系统的可用性。

可用性的度量方式,通常是系统可用时间和总运行时间的比值。 在技术运营上,可用性指标一般是系统运营的核心目标(所谓N个9标准)。

§ 一致性 | Consistency

简单直观地理解是: 分布式系统中多个节点的数据返回始终一致的性质

Consistency = two reads return the same value.

下面的图6.1中, 我们可以这样讲:左边的 $S_{1}$ 具有一致性, 右边的 $S_{2}$ 则不具有一致性。

图6.1 - 一致性是指两次读返回的结果一致

一致性可以理解为「正确性」。 具有一致性的系统, 在读写逻辑上并不会给客户端带来”惊讶”

下面列举的情形,都是不具备一致性的表现:

Gilbert和Lynch对一致性的描述是这样的[1]

any read operation that begins after a write operation completes must return that value, or the result of a later write operation.

在一个具有一致性的分布式系统中,一旦一个对任一节点的写入返回成功, 后续对这个系统中其他任意节点的读操作都应该可以返回这个更新的值。

Gilbert和Lynch的话, 换一个简单的理解方式说:

All nodes see the same data at the same time.

所有节点在同一时刻的看到的数据是一样的。

可以看到, CAP定理中的一致性,要求所有节点都可以看到最新修改的数据。 其实这个要求是非常强的, 我们接下来会讨论一致性的模型, CAP中的C就是强一致性中的线性一致性

§ 一致性的分类

实际中,一致性也不是非黑即白的性质, 而是有强弱之分。 人们对一致性的研究和实践中, 按照强弱程度建立了一致性模型。 一致性按强弱程度可以分为三类:

下面的图6.2给出了一致性分类的示例:

图6.2 - 一致性的分类

§ 事件先后和并发

在进一步讨论这些一致性模型之间,需要先了解全序和偏序关系[2]

偏序和全序是序理论中常用的两种序关系, 举例来说:

简短说:偏序是部分可比较的序关系,全序是全部可比较的序关系。 关于全序和偏序更多的信息,可以看这里:逻辑时钟-如何刻画分布式中的事件顺序#全序和偏序

在分布式系统中, 事件的先后关系通常用「happened before」的关系符, 比如 $W_1 \rightarrow W_2$ 表示 $W_1$ 在 $W_2$ 之前发生。 如果两个事件无法比较先后,我们说两个事件是并发的, 记作 $W_1 \parallel W_2$。

假设节点之间的物理时钟是精确对齐的, 那么我们完全可以根据事件发生的时间戳来判定事件先后关系。 这就是一种全序关系。 然而因为网络延迟的不确定, 时钟精确同步的这种假设是不符合现实情况的。

不同的分布式协调算法,对事件先后的判定逻辑也是不同的。 但是我们一定知道以下先后关系是确定的:

观察下面图7.1, 我们可以推导出来一些先后关系和并发关系。

图7.1 - 事件先后示意

在分布式的事件顺序的理解上,我们一定要清楚事件的先后是具有相对性的。 我们无法在系统中创造一个上帝视角观察到全局情况, 只能通过每个节点对系统的局部感知来推导全局的事件顺序是怎样的, 这取决于我们的一致性协调算法是如何构建的, 而且我们甚至可能无法推导出全序关系, 只能推导出部分事件的偏序关系。 (更多看这里: 逻辑时钟-如何刻画分布式中的事件顺序#事件先后的相对性。)

§ 一致性模型

下图8.1中是一种一致性分类 更为精细、严格的一致性模型:

图8.1 - 更为精细严格的一致性模型

我们接下来详细讨论几个常见的一致性模型, 请注意从事件顺序的角度去观察它们之间的区别:

现在可以从事件顺序的角度总结下这几个一致性模型:

  1. 严格一致性: 依赖绝对的全局物理时钟, 无法实现。
  2. 线性一致性: 要求达成事件顺序的全序一致, 且和物理时钟上的事件顺序一致。
  3. 顺序一致性: 要求达成事件顺序的全序一致。
  4. 因果一致性: 要求达成事件顺序的偏序一致,不必协调因果无关事件的顺序。

不同强弱的一致性模型,其实现的难易程度、和带来的代价也是不同的。

§ 一致性的代价 - 响应时长

回头看下CAP定理关于可用性的定义, 其中并没有对响应时限做出约束。 如果一个客户端请求的响应非常非常慢,但是最终得到了响应,在CAP的范畴下,这仍然是具有可用性的。

更广义的可用性, 应该是在约定时限的要求下做出响应。 现实中,人们往往是非常关心响应时间的。 我们将看到, 强一致性的代价就是相对高的响应时长

在理论计算机科学中,除了为人熟知的CAP定理之外,还有一个叫做PACELC的定理, 这个定理是CAP定理的一个扩展定理。

PACELC定理的命名方式和CAP如出一辙,我们来看下这个定理的含义[4]

当分区(Partition)发生的时候, 必须在可用性(Availability) 和 一致性(Consistency) 中做选择; 否则(Else),当分区不发生时, 必须在响应时长(Latency) 和 一致性(Consistency)中做选择。

前半句的意思,就是CAP定理本身。 后半句则指出了:无分区的情况下,要追求更强的一致性, 就要接受更高的响应时长

这是个非常酷的结论, 它把可用性的概念广义化到了响应时长。 我们不做理论证明, 而是通过简单的示例分析来解释下为什么会有这样的结论。

在前面的「§数据同步的两种方式」章节中, 有提到节点间两种数据同步方式: 同步和异步。 再次回顾图3.1中两种节点间数据同步的方式可以显然地看到: 同步的方式对客户端的响应时长更高

图3.1 - $P_{1}$ 和 $P_{2}$ 的数据同步方式

我们接下来可以通过一个小图例来看到, 异步的节点间数据同步方式会降低系统的一致性强度

观察下面的图9.1, 左边的 $S_1$ 中写请求会在其他节点完成数据同步后再回复客户端写入完成, 也就是同步方式。 右边的 $S_2$ 中写请求会直接响应客户端,异步地对其他节点进行数据同步。 在左右两个图中, 假如我们在$P_2$未完成数据副本同步之前的这个时间窗内, 从不同的节点分别去读$a$, 在$S_1$ 中会得到一致性的结果, 而在 $S_2$ 则会得到不一致的结果。 也就是异步的数据副本同步方式会降低系统的一致性强度

综合来看,我们就可以(不严格地)得到这个结论,要做到更强的一致性,就要接受更高的响应时长。

在论文《A Critique of the CAP Theorem》有总结不同的一致性模型下的读写响应时长和网络延迟 $d$ 之间的关系[3], 其中 $O(d)$ 是一种类似复杂度的表示方法, $O(d)$ 表示请求是网络延迟时长敏感的, $O(1)$ 表示请求是和网络延迟无关的。

一致性(consistency) 写响应时长(write latency) 读响应时长(read latency)
线性一致性 $O(d)$ $O(d)$
顺序一致性 $O(d)$ $O(1)$
因果一致性 $O(1)$ $O(1)$

可以通过这个研究小结中看出, 三个常见的一致性模型的读写请求对网络延迟的敏感程度。 也清晰地看到了: 更强地一致性的代价是更高的响应时长。

§ 「CP 或者 AP」 并不是绝对的选择题

在本文即将结尾的时候, 我们回头再看一下CAP定理: 在实际的分布式系统设计中,我们无法同时达成强一致性和高可用性。

CAP定理是我们在设计一个分布式系统之初时的一个有益参考, 它让我们在设计系统的时候不必浪费时间去寻求理论上都达不成的目标。

CAP范畴下的一致性和可用性的定义其实是非常狭义的、非常精确的, 它所讨论的是非常极限的情况, CAP只否定了我们没办法同时达成最强的一致性和最高的可用性。 在实际中,一个分布式系统根本不可能完全放弃C、或者完全放弃A, 我们要做的是选择哪个多一点

没有绝对的选择和放弃,只有更偏好哪个和弱化哪个的说法。

话说, 我们可以做到CAP定理下的CA吗? – 单节点能 :)

Scaling is hard.

§ 链接 & 脚注

  1. Gilbert and Lynch. Brewer’s conjecture and the feasibility of consistent, available, partition-tolerant web services.
  2. Chao’s blog. 逻辑时钟 - 如何刻画分布式中的事件顺序
  3. Martin Kleppmann. A Critique of the CAP Theorem
  4. Daniel J Abadi. Consistency tradeoffs in modern distributed database system design.

– 毕「分布式的CAP定理和一致性模型」

评论 · 打赏 · 分享
正在加载disqus...