前言

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

到了近十年，分散式系统已经打破组织的边界，2009 年第一条区块链问世，从此开始个人与个人之间的分散式体系；2016 年，区块链更进一步突破组织间的藩篱，企业与企业之间的联盟链开始蓬勃发展。区块链的出现为分散式带来了更多挑战，但不管这些基于分散式的应用如何改变，还是都离不开分散式系统的理论框架 — CAP 定理（Consistency-Availability-Partition Tolerance theorem）。

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

本系列会从介绍 CAP 定理开始，介绍一系列分散式相关的算法，像是 Raft, Gossip, Quorum NWR 等等，也欢迎读者在留言区分享你认识的分散式算法，互相交流！

分散式有多难？

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

试想一个情境，我们使用了某银行的行动支付转账给朋友，恰巧就在此时，因为某个路段在修路把银行台北机房对高雄机房的光纤网络挖断了，造成台北机房已经有这笔转账记录，但高雄没有（如图一），雪上加霜的是，此时台北机房对外的网络也意外被切断了，所以使用者查看转账结果时，被导向了高雄机房，造成使用者以为转账没有成功再转了一笔（如图二），最后光纤网络修复后，使用者才发现原来有两笔转账的纪录（如图三）。上述情况只是分散式可能面临的其中一种情况，就算网络线没有被挖断，系统还是会因为网络延迟造成资料短暂的不一致，现实中有各种不同的意外要应付，此时如果我们有一个可以帮助我们思考分散式系统的思想框架，将会有助于我们设计分散式系统。

图一：A 透过台北机房汇钱给 B

图二：A 透过高雄机房汇钱给 B

图三：节点之间连线修复

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

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

CAP 定理由一致性（Consistency）、可用性（Availability）及分区容错性（Partition tolerance）组成，不过由于作者当初提出时，并没有给这三者明确的定义，因此不同的人对于 CAP 的定义有些分歧，像是 IBM Cloud 上的定义跟 Wiki 的就有些出入。这里我们使用 Robert Greiner 给的定义，不过光是 Robert Greiner 就定义过两次 CAP，这里我们选择新的定义解释，因为作者已经把旧的定义标上 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），通常步骤如下：

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

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

Prepare Phase

Commit Phase

两阶段操作被应用在许多分散式算法及系统中，比较出名的像是 MySQL XA、Raft 等。在更复杂的情况，像是需要拜占庭容错（Byzantine Fault Tolerance, BFT）的区块链里，甚至还进一步使用三阶段提交（Three-Phase Commit, 3PC）来防止节点作恶，详细可以参考 PBFT。

高可用性 — AP 与 BASE

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

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

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

总结

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

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

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

区块客致力于发掘和整理各种与区块链技术有关的内容，只要与区块链或区块客网站有关的合作和／或建议，我们都非常欢迎。请您发电邮至 [email protected] 与我们联系。