区块链前哨战1：分布式架构的限制理论— CAP定理

前言

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

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

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

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

分布式有多难？

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

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

分布式的思考框架— 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），通常步骤如下：

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

设计两阶段提交时要注意，在准备阶段（Prepare Phase），节点如果回覆「允许」进行操作，那么不管发生什么意外，节点都要能保证在执行阶段（Commit Phase）进行此操作，即使准备阶段后，节点因意外关机，节点也要在意外恢复后，依据协调者的指令完成准备阶段答应的操作。另外因为是强一致性的关系，所以协调者会在执行阶段（Commit Phase）结束才回覆使用者，因为如果协调者在准备阶段（Prepare 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 协议时提到。