2021-11-19

分布式-CAP理论

CAP 理论

CAP理论在互联网界有着广泛认知度，大家会将其作为衡量系统设计的标准。大家都能够清楚地讲出CAP理论：任何分布式系统在可用性、一致性、分区容错性方面，不能兼得，最多只能三选二，因此任何分布式系统设计只能在三者中进行不同取舍。

1. CAP历史

2000年， Eric Brewer教授在PODC研讨会上提出一个猜想[1]：一致性、可用性和分区容错性三者无法在分布式系统中被同时满足，并且最多只能满足其中两个！

这个猜想首次把一致性、可用性和分区容错三个因素提炼出来作为系统设计的重要特征，断言用此三者可以划分所有的分布式系统，并指明这三个特征之间的不可能性关系。

Brewer教授当时想象的分布式场景是webservice，一组webservice后台运行众多server，对service的读写会反应到后台的server集群，并且对CAP进行定义：

Strong consistency: means single-copy ACID consistency;
High availability: 通过冗余（比如副本）提供高可用。如果特定数据消费者能够一直访问一些副本，那么数据被认为是高可用。
Partition-resilience: 当出现数据副本分区时，系统可以存活。

Strong CAP Principle：Strong Consistency, High Availability, Partition-resilience：最多选择两个。

CAP猜想清晰表达在设计分布式应用的取舍，

CA without P：在没有网络分区的情况下，数据库提供分布式事务语义。
CP without A：有网络分区下，在分区恢复之前，更多的ACID数据库的事务都会被阻塞，从而避免引入合并冲突，并带来不一致。
AP without C: 出现分区时，数据出现不一致。通常，任何分布式数据问题可以通过基于过期的caching来获得AP，或多数选举获得PC（少数人群是不可用的）。

Weak CAP Principle: 保证CAP的两个更强，那么意味着另外一个更弱。

2. CAP被上升为定理，

2002年，Lynch与其他人[2]证明了Brewer猜想，从而把CAP上升为一个定理。但是只是证明了CAP三者不可能同时满足，并没有证明任意二者都可满足的问题，所以，该证明被认为是一个收窄的结果。

Lynch的证明采用反证法：如果三者同时满足，则因为P的存在，那么一定存在Server之间丢包，那么就不能保证C，证明简洁而严谨。

在该证明中，CAP进行更明确的声明：

C：一致性被称为原子对象，任何读写都应该看起来是原子的，又叫线性化。写后面的读一定能读到前面写的内容。所有的读写请求都好像被全局排序。
A：对任何非失败节点都应该在有限时间内给出响应。（请求的可终止性）
P：允许节点之间丢失任意多的消息，当网络分区发生时，节点之间的消息可能会完全丢失。

3. CAP的质疑

CAP理论考虑的场景很少，提供的是一个大的思路；不同论文/文章针对具体场景去质疑时，总能够指出CAP不合理的地方。

但一个比较重要的地方就是不要真的只是进行三选二。比如在没有网络分区时，一致性和可用性也只能二选一。

以下是几篇论文和文章对CAP的质疑，有兴趣的可以了解一下

3.1 质疑1：

文章[8]中对CAP有一系列描述，没太明白在说什么。

3.2 质疑2：不要快速丢弃掉C

在[3]中，其质疑的主张是：CAP必须放弃某一个目标。从错误中恢复有很多维度要考虑，该文章解释了很多种错误。结论是：不要轻易放弃C。因为分区容错在局域网中很少发生，在广域网中也有各种备选方案。

3.3 质疑3 构建不可避免模型避免CAP的复杂性

文章[4]的标题是锤死CAP。
作者认为CAP困境在于允许数据变更，每次变更都得数据同步，保持一致性，他认为数据是客观存在的，维护增删操作（译注：我个人认为是LSM log-structured message tree的理念）。
作者认为数据模型可以抽象为Query=Function(all data)，完全抛弃CAP中繁琐且模糊的定义。

我个人觉得：这篇文章只是换了一个角度来说明分布式系统，与CAP没啥关系。

4. 对质疑的回应

面对大量的质疑，Brewer和Lynch进行重申，

Brewer在2012你那重申[5]:

3选2这个表述是不准确的，在某些分区极少发生的情况下，三者能顺畅在一起配合。没有P时是CA，发生P时是PC或PA
CAP不仅仅发生在整个系统中，可能是发生在某个子系统或系统的某个阶段
CAP中每一个都是连续取值，而不是0-1关系。

Lynch在10年后的2012年重写了论文[9]，该论文主要做了几件事：

一致性场景不会引入用户agent，只发生在后台集群之内
引入了活性(liveness)和安全属性(safety)，在一个更抽象的概念下研究分布式系统，并认为CAP是活性与安全熟悉之间权衡的一个特例。其中的一致性属于liveness，可用性属于safety
把分区容错归结为一个对网络环境的陈述，而非之前一个独立条件。这实际上就是更加明确了概念
把CAP的研究推到一个更广阔的空间：网络存在同步、部分同步；一致性性的结果也从仅存在一个到存在N个（部分一致）；引入了通信周期round，并引用了其他论文，给出了为了保证N个一致性结果，至少需要通信的round数。也介绍了其他人的一些成果，这些成果分别都对CAP的某一个方面做出了特殊的贡献！

其实Lynch论文主要做了两件事：

缩小CAP适用的定义，消除质疑的场景；
展示了CAP在非单一一致性结果下的广阔研究成果！并顺便暗示CAP定理依旧正确！

5. 很多系统既不是线性化也不是CAP-Available [6]

基于严格的CAP定义，很多系统既不是线性化、也不是CAP-Available。

举例，考虑单主的多副本数据库，这是大多数关系型数据库创建副本的标准方式。在这种配置下，如果一个client与leader分离，那么它就不能再向数据库写入数据。即使可以从follower读取数据，但已经不能写入，这就不符合CAP-Avaible。当然这种配置常常被叫做“高可用性”。

如果单主复制不是CAP-Avaible，那么是不是CP呢？并不一定是。如果运行应用从follower读取数据，并且复制是异步的，那么副本可能会落后于leader，这时候读取就不是线性的，不符合CAP-consistent。

所以这些系统既不是CAP-consistent，也不是CAP-avaible。他们只是P。

以Zookeeper为例：

zookeeper使用consensus algorithm，所以人们常常将其看做是选择一致性高于可用性的例子，但事实上，zk默认是不提供线性读取。连接到数据库某个节点的client，读取的是该节点上的数据，即时最新的数据在其他节点。默认Zookeeper不满足CAP中的C。

关于Zookeeper的Availablility？

zk采用法定人数的方式实现共识。那么多数节点是可用的，而少数节点的集群是不能写入的，不符合ZK的CAP-available。

6. 该如何看待CAP

当我们提到CAP的时候，首先我们指的是严格的CAP定义；
首先肯定的是，CAP并不适合再作为一个适应任何场景的定理，它的正确性更适合基于原子读写的NoSQL场景
无论如此，C、A、P三个概念始终存在于任何分布式系统，只是不同模型会有不同呈现；一个系统的不同子模块会有不同关系；
- 在没有出现P（分区时），可以实现CA；
- 在出现P时，CA二选一，或者实现的是 C+HA
当我们分析一个系统的时候，要从多个维度去分析，比如etcd是CP+HA [10]
有一个CAP理论的扩展叫PACELC理论