探究分布式架构的理论基石—CAP定理

前言

在生活充满互联网应用的今天，我们每一次点击的背后可能都是个庞大且复杂的系统，像是抢票系统如何确保大家可以有快速地抢到票，而且不会重复出售同一张票，或是银行系统如何确保你的余额，不会因为连到不同的机房就显示不同的数字等等，这些系统为了同时服务大量的客户，都需要依靠分布式系统以突破单机的瓶颈。

CAP 定理决定了分布式系统天生上的限制，通过 CAP 定理我们可以理解为什么共识机制如此复杂，以及系统如何在强一致性与最终一致性间做取舍。本篇会从分布式系统的挑战开始，介绍 CAP 定理，以及 CAP 中的三元取舍，希望读者阅读后可以对分布式系统有个思考框架。

分布式有多难？

不管设计什么架构，我们都希望满足 高性能 且 高可用 的系统，为了突破性能的瓶颈，我们从单核走向了多核，从单机走向了多机；为了防止意外造成系统无法运作，我们通过「备份」来对抗各种天灾人祸。分布式的目的就在于 突破单机的性能瓶颈 并 建立不间断的服务 ，而分布式设计带来的好处，恰恰也是分布式设计的困难点。

试想一个情境，我们使用了某银行的网络支付转帐给朋友，恰巧就在此时，因为某个路段在修路把银行北京机房对上海机房的光纤网络挖断了，造成北京机房已经有这笔转帐记录，但上海没有（如图一），雪上加霜的是，此时北京机房对外的网络也意外被切断了，所以使用者查看转帐结果时，被导向了上海机房，造成使用者以为转帐没有成功再转了一笔（如图二），最后光纤网络修复后，使用者才发现原来有两笔转帐的纪录（如图三）。

上述情况只是分布式可能面临的其中一种情况，就算网线没有被挖断，系统还是会因为网络延迟造成数据短暂的不一致，现实中有各种不同的意外情况要应对，此时如果我们有一个可以帮助我们思考分布式系统的思想框架，将会有助于我们设计分布式系统。

分布式的思考框架 — CAP 定理介绍

Eric Brewer 最早于 1998 年有 CAP 理论的构想，在 2000 年的 PODC^[1] 会议上发表这个猜想，2002 年时由 Seth Gilbert 及 Nancy Lynch 证实^[2] 了这个猜想，因此 CAP 定理（CAP theorem）又被称作 Brewer’s theorem。

CAP 定理由一致性（Consistency）、可用性（Availability）及分区容错性（Partition tolerance）组成，不过由于作者当初提出时，并没有给这三者明确的定义，因此不同的人对于 CAP 的定义有些分歧，像是 IBM Cloud^[3] 上的定义跟 Wiki^[4] 的就有些出入。这里我们使用 Robert Greiner^[5] 给的定义，不过光是 Robert Greiner 就定义过两次 CAP，这里我们选择新的定义^[6] 解释，因为作者已经把旧的定义^[7] 标上 Outdated 了，读者可以自行比较两次定义的差异。

CAP 定理

In a distributed system (a collection of interconnected nodes that share data. ), you can only have two out of the following three guarantees across a write/read pair: Consistency, Availability, and Partition Tolerance — one of them must be sacrificed.

首先 Robert 定义适用于 CAP 定理的系统，这个系统必须是一个分布式系统，不过分布式系统有很多种，像是有些系统只涉及逻辑运算，但不涉及数据保存，而有些系统则是两者都有，因此作者特别表明是要有「共享数据」的分布式系统。在这个系统内依据 CAP 定理，我们的每一次读写顶多 只能满足 Consistency、Availability 或是 Partition Tolerance 三者中的两个 。后面我们会在说明为什么只能满足其中的两项，这里我们先看定义。

Consistency

A read is guaranteed to return the most recent write for a given client.

对于一致性，Robert 的定义是：系统必须保证客户端的读操作会取得最近更新的数据。作者选择从用户的角度而不是从系统的角度描述，原因是每一次事务（Transaction）发生的过程，系统都处于不一致的状态，所以从系统的角度看，系统是不可能随时保持一致性的。从用户的角度，我们可以通过一些设计，像是 Quorum NWR，每一次用户读取都至少从 R 个节点读取，并从中选出最新的数据返回，以此来达成对用户的一致性。

Availability

A non-failing node will return a reasonable response within a reasonable amount of time (no error or timeout) .

对于可用性，Robert 的定义是：一个健康的节点必须在合理的时间内返回合理的回应。作者使用「合理的」而不是「正确的」来描述回应，原因是系统会面临各种不能控制的风险，但只要系统设计合适，在意外发生的情况下还是可以给出合理的回应，那这个系统就具有可用性。

Partition tolerance

The system will continue to function when network partitions occur.

对于分区容错性，Robert 的定义是 — 在网络分区的情况下，系统依然能够继续运作。在网络发达的今天，我们的手机几乎随时都处于连接的状态，所以网络分区对一般用户比较难想像。

对机房来说，不同机房之间的连接通常是用专门的网线，为了确保机房的网络稳定及安全性，这些网线是不对外公开的，如果这些网线如果被挖断，对于机房来说，等于机房跟机房之间的网络就断了，所以机房与机房就会产生分区，而在分区的情况下，不同的机房还是可以对外继续运作的能力，就叫分区容错性。

在实际设计上，分区容错代表的不仅是分区的情况下还要继续运作，还包括连接恢复后，如何同步及修正两个分区的数据差异，才算完整的达到分区容错性。

分布式的不可能三角 — CAP 三元取舍

CAP 定理乍看之下，三个任取两个都可以，但在现实世界中，网络是最无法被保证的，所以分区容错性（P）是一定要被保障的，所以实际设计系统时，我们要在一致性（C）跟可用性（A）之间做取舍。

强一致性 — CP 与 ACID

ACID 是关系型数据库的基石，代表每次事务（Transaction）需要满足原子性（Atomicity）、一致性（Consistency）、隔离性（Isolation）及持久性（Durability）。CAP 定理是对于系统的描述，而 ACID 是对于事务（Transaction）的描述，虽然两种对于不同层面描述的理论不应该被放在一起讨论，但这里想强调的是 ACID 是强一致性的描述，如果在分布式情况下满足了，也等于满足了 CP 模型。

分布式要在系统层面满足强一致性，通常会使用两阶段提交（Two-Phase Commit, 2PC），通常步骤如下：

使用者向协调者（Coordinator）发起一个写操作
准备阶段（Prepare Phase）: 协调者向其他所有节点询问是否可以进行此操作
执行阶段（Commit Phase）: 若所有节点都回复可以执行操作，则协调者向所有节点发送执行此操作

设计两阶段提交时要注意，在准备阶段（Prepare Phase），节点如果回复「允许」进行操作，那么不管发生什么意外，节点都要能保证在执行阶段（Commit Phase）进行此操作，即使准备阶段后，节点因意外关机，节点也要在意外恢复后，也需要依据协调者的指令完成准备阶段答应的操作。另外因为是强一致性的关系，所以协调者会在执行阶段（Commit Phase）结束才回复使用者，因为如果协调者在准备阶段（Prepare Phase）结束就回复给使用者，那可能因为协调者还没发送执行信息给其他节点前，就意外关机，造成使用者接收到的信息与整个集群不一致。

两阶段操作被应用在许多分布式算法及系统中，比较出名的像是 MySQL XA^[8] 、 Raft^[9] 等。在更复杂的情况，使用三阶段提交（Three-Phase Commit, 3PC）来解决。

高可用性 — AP 与 BASE

BASE 代表的是基础可用（Basically Available）、最终一致性（Eventually Consistent）及软状态（Soft State），从字面意义就能发现，BASE 以可用性为主，对一致性的要求则比较低，只要最终状态是一致性即可，所以满足了 BASE，基本上就符合 AP 模型。

对于互联网的用户来说，如果一个系统不可用，那即使应用内部的状态有多么的一致，对用户来说都是坏掉的，所以我们很常在互联网应用中看到基础可用（Basically Available）的手法，以微博点赞数为例，热门的贴文刚发表时，就会涌入一堆人按赞，每一次按赞对系统来说都是一次写入，如果系统为了强一致性让一部份人暂时无法写入的话，那大家一定会觉得是不是系统坏掉了，所以微博并不需要急著统计出一个精确的数字，因为对大多数人来说 8 个赞跟 10 个赞没什么区别，只要系统可以在最后保持最终一致性即可。

不过只满足了基础可用，系统还是要有方法可以恢复最终一致性（Eventually Consistent），常见的做法有读时修复（Read Repair）、写时修复（Write Repair）以及反熵（Anti-Entropy）。读时修复在读取时同时到多个节点读取，并以最新的节点为主；写时修复，同时写入多个节点，若发现有写入失败则记录下来，定时重传，直到写入成功，或是有新的写入为止；最后反熵则是定期检查状态是否一致，如果不一致则通过特定的修复顺序，修正每个节点的数据，详细步骤会在之后讲 Gossip 协议时提到。

总结

这次我们介绍了 CAP 定理，以及 CAP 定理应用的模型，如果想对 CAP 定理有进一步的认识，可以看 Eric Brewer 在 2012 年写的文章 — CAP 定理 12 年来的回顾^[10] 。使用 CAP 定理有两个要注意的地方：

首先虽然系统分区（P）的情况并不常发生，但我们一定要为了分区容错性做准备；反之在没有分区的情况下，我们要尽力同时达成一致性跟可用性。
第二是虽然我们以 CAP 来描述整个系统，但其实系统内可以设计成敏感的数据满足 CP 模型，不重要的数据则满足 AP 模型，所以 CAP 定理是可以拉到数据层面来思维的。

最后，理解 CAP 定理是理解分布式的重要入门，更是了解区块链共识机制的基本观念，少了 CAP 的概念，可能只能在方法与步骤上层面上理解共识机制，但有了 CAP 的概念，则可以进一步的探讨，算法如何在一致性与可用性之间做取舍。

以上是我对于 CAP 定理的分享，也欢迎大家分享你们如何理解及应用 CAP 定理！下一篇我们会从近代的共识机制 Raft 算法说起。