定义

2000年7月，加州大学伯克利分校的Eric Brewer教授在ACM PODC会议上提出CAP猜想。2年后，麻省理工学院的Seth Gilbert和Nancy Lynch从理论上证明了CAP。之后，CAP理论正式成为分布式计算领域的公认定理。



Consistency 一致性



一致性指“all nodes see the same data at the same time”，即所有节点在同一时间的数据完全一致。

一致性是因为多个数据拷贝下并发读写才有的问题，因此理解时一定要注意结合考虑多个数据拷贝下并发读写的场景。

对于一致性，可以分为从客户端和服务端两个不同的视角。



• 客户端

从客户端来看，一致性主要指的是多并发访问时更新过的数据如何获取的问题。



• 服务端

从服务端来看，则是更新如何分布到整个系统，以保证数据最终一致。



对于一致性，可以分为强/弱/最终一致性三类

从客户端角度，多进程并发访问时，更新过的数据在不同进程如何获取的不同策略，决定了不同的一致性。

• 强一致性

对于关系型数据库，要求更新过的数据能被后续的访问都能看到，这是强一致性。



• 弱一致性

如果能容忍后续的部分或者全部访问不到，则是弱一致性。



• 最终一致性

如果经过一段时间后要求能访问到更新后的数据，则是最终一致性。



Availability 可用性



可用性指“Reads and writes always succeed”，即服务在正常响应时间内一直可用。

好的可用性主要是指系统能够很好的为用户服务，不出现用户操作失败或者访问超时等用户体验不好的情况。可用性通常情况下可用性和分布式数据冗余，负载均衡等有着很大的关联。

Partition Tolerance分区容错性



分区容错性指“the system continues to operate despite arbitrary message loss or failure of part of the system”，即分布式系统在遇到某节点或网络分区故障的时候，仍然能够对外提供满足一致性或可用性的服务。



一个分布式系统最多只能同时满足一致性（Consistency）、可用性（Availability）和分区容错性（Partition tolerance）这三项中的两项。



证明

CAP的证明



上图是我们证明CAP的基本场景，网络中有两个节点N1和N2，可以简单的理解N1和N2分别是两台计算机，他们之间网络可以连通，N1中有一个应用程序A，和一个数据库V，N2也有一个应用程序B2和一个数据库V。现在，A和B是分布式系统的两个部分，V是分布式系统的数据存储的两个子数据库。



在满足一致性的时候，N1和N2中的数据是一样的，V0=V0。在满足可用性的时候，用户不管是请求N1或者N2，都会得到立即响应。在满足分区容错性的情况下，N1和N2有任何一方宕机，或者网络不通的时候，都不会影响N1和N2彼此之间的正常运作。



上图是分布式系统正常运转的流程，用户向N1机器请求数据更新，程序A更新数据库Vo为V1，分布式系统将数据进行同步操作M，将V1同步的N2中V0，使得N2中的数据V0也更新为V1，N2中的数据再响应N2的请求。



这里，可以定义N1和N2的数据库V之间的数据是否一样为一致性；外部对N1和N2的请求响应为可用性；N1和N2之间的网络环境为分区容错性。



这是正常运作的场景，也是理想的场景，然而现实是残酷的，当错误发生的时候，一致性和可用性还有分区容错性，是否能同时满足，还是说要进行取舍呢？



作为一个分布式系统，它和单机系统的最大区别，就在于网络，现在假设一种极端情况，N1和N2之间的网络断开了，我们要支持这种网络异常，相当于要满足分区容错性，能不能同时满足一致性和响应性呢？还是说要对他们进行取舍。



假设在N1和N2之间网络断开的时候，有用户向N1发送数据更新请求，那N1中的数据V0将被更新为V1，由于网络是断开的，所以分布式系统同步操作M，所以N2中的数据依旧是V0；这个时候，有用户向N2发送数据读取请求，由于数据还没有进行同步，应用程序没办法立即给用户返回最新的数据V1，怎么办呢？



有二种选择，第一，牺牲数据一致性，响应旧的数据V0给用户；第二，牺牲可用性，阻塞等待，直到网络连接恢复，数据更新操作M完成之后，再给用户响应最新的数据V1。



这个过程，证明了要满足分区容错性的分布式系统，只能在一致性和可用性两者中，选择其中一个。



P是必须的，怎么提高可用性？

1、通过复制来提高可用性

通过复制来提高可用性，这是分布式系统设计的首要原则。从复制类型来看，复制可以分为主动复制和被动复制。

在主动复制中，每个客户端请求都由所有服务器处理。这要求由服务器托管的进程是确定性的-给定相同的初始状态和请求序列，所有过程将产生相同的响应序列，并且最终处于相同的最终状态。为了使所有的服务器接收到相同的操作序列，一般都使用原子广播协议。原子广播协议保证所有服务器都接收到消息或没有消息，并且它们都以相同的顺序接收消息。

主动复制的主要缺点是实际上大多数真实世界的服务器都是非确定性的。

在被动复制中，只有一个服务器（称为主服务器）处理客户机请求。处理请求后，主服务器更新其它（备份）服务器上的状态，并将响应发送回客户端。如果主服务器发生故障，则其中一台备份服务器就会接管它。被动复制可以用于非确定性过程。被动复制与主动复制相比的主要缺点是在失败的情况下，客户端的响应会被延迟。



从进程与系统交互角度来看，复制分为同步复制和异步复制。

同步复制 - 通过原子写入操作来保证“零数据丢失”，即完全写入。在本地和远程副本存储的确认之前，写入不被认为是完整的。

异步复制 - 本地存储确认后，写入即被认为是完整的。远程存储已更新，但可能滞后很小。系统性能会因异步复制而大大提高。但在丢失本地存储的情况下，远程存储不能保证具有当前的数据副本，并且最近的数据可能会丢失。

关于复制技术，目前有三大模型：事务复制、Paxos复制和虚拟同步。事务复制、Paxos复制讨论的已经比较多，虚拟同步则较少看到有产品采用。

复制的分类方式可根据节点组织关系分为以下三种：Master/Slave复制、Paxos复制和链式复制。



2、使用CAP理论指导分布式系统设计



复制技术是产生一致性问题的根源。

CP系统是牺牲可用性的系统。复制同步的协议一般使用严格的法定数协议 (Paxos、Raft、ZAB)或者2PC协议。CP类型的系统有MongoDB、HBase、 Zookeeper等。



AP系统是牺牲一致性的系统。复制同步的协议一般使用非严格的法定数协议。AP类型的系统有 Couch DB、Cassandra、Amazon Dynamo等。



P是一个自然的事实，CA是强需求。三者并不对等

提高P（分区容忍能力）是通过提高基础设施的稳定性来获得的，而不是通过降低C和A来获得的。也就说牺牲C和A也不能提高P。

放弃C不是为了获得A，而是为了低延迟（延迟是包含在可用性的范围内的，不可用就是延迟的极大极限值）。

系统无论如何要保证一致性，无论在事前还是事后，这是系统设计的最大不变性约束。在这个前提下，再去了解A，进而以可用性的程度来解决现实中的问题。

ACID伴随数据库的诞生定义了系统基本设计思路，所谓先入为主。2000年左右，随着互联网的发展，高可用的话题被摆上桌面，所以提出了BASE。从此C和A的取舍消长此起彼伏，其结晶就是CAP理论。





从ACID和BASE来说，ACID是为了保证一致性而诞生，因而侧重一致性；BASE是为了高可用系统的设计而诞生，因而侧重可用性。

CAP并不与ACID中的A（原子性）冲突，值得讨论的是ACID中的C（一致性）和I（隔离性）。ACID的C指的是事务不能破坏任何数据库规则，如键的唯一性。与之相比，CAP的C仅指单一副本这个意义上的一致性，因此只是ACID一致性约束的一个严格的子集。如果系统要求ACID中的I（隔离性），那么它在分区期间最多可以在分区一侧维持操作。事务的可串行性（serializability）要求全局的通信，因此在分区的情况下不能成立。



3、注册中心举例

数据的一致性，目前来看基本可以归为两家：一种是基于Leader的非对等部署的单点写一致性，一种是对等部署的多写一致性。当我们选用服务注册中心的时候，并没有一种协议能够覆盖所有场景，例如当注册的服务节点不会定时发送心跳到注册中心时，强一致协议看起来是唯一的选择，因为无法通过心跳来进行数据的补偿注册，第一次注册就必须保证数据不会丢失。而当客户端会定时发送心跳来汇报健康状态时，第一次的注册的成功率并不是非常关键（当然也很关键，只是相对来说我们容忍数据的少量写失败），因为后续还可以通过心跳再把数据补偿上来，此时Paxos协议的单点瓶颈就会不太划算了，这也是Eureka为什么不采用Paxos协议而采用自定义的Renew机制的原因。



这两种数据一致性协议有各自的使用场景，对服务注册的需求不同，就会导致使用不同的协议。在这里可以发现，Zookeeper在Dubbo体系下表现出的行为，其实采用Eureka的Renew机制更加合适，因为Dubbo服务往Zookeeper注册的就是临时节点，需要定时发心跳到Zookeeper来续约节点，并允许服务下线时，将Zookeeper上相应的节点摘除。Zookeeper使用ZAB协议虽然保证了数据的强一致，但是它的机房容灾能力的缺乏，无法适应一些大型场景。



Nacos因为要支持多种服务类型的注册，并能够具有机房容灾、集群扩展等必不可少的能力，在1.0.0正式支持AP和CP两种一致性协议并存。1.0.0重构了数据的读写和同步逻辑，将与业务相关的CRUD与底层的一致性同步逻辑进行了分层隔离。然后将业务的读写（主要是写，因为读会直接使用业务层的缓存）抽象为Nacos定义的数据类型，调用一致性服务进行数据同步。在决定使用CP还是AP一致性时，使用一个代理，通过可控制的规则进行转发。



目前的一致性协议实现，一个是基于简化的Raft的CP一致性，一个是基于自研协议Distro的AP一致性。Raft协议不必多言，基于Leader进行写入，其CP也并不是严格的，只是能保证一半所见一致，以及数据的丢失概率较小。Distro协议则是参考了内部ConfigServer和开源Eureka，在不借助第三方存储的情况下，实现基本大同小异。Distro重点是做了一些逻辑的优化和性能的调优。



怎样选择？

CAP定理是一个高度抽象的概括，而不是”三选二“的公式，不要过分简单化各性质之间的相互关系。

CAP三种性质都可以在程度上衡量，并不是非黑即白的有或无。可用性显然是在0%到100%之间连续变化的，一致性分很多级别，连分区也可以细分为不同含义，如系统内的不同部分对于是否存在分区可以有不一样的认知。



架构设计的总纲—：抽象—分解（分层、分治）—演化。无论碰到什么问题都需要系统抽象地思考，首先确定域问题对象的属性，是针对服务器（node）、还是针对数据，P既然是绕不开的永恒，可以从A和C入手，C分几种程度，A又分为几个层次，因为CAP定理随着时代的发展，定义也会随着不同场景有所变化。

在通信网络中，最重要的两个属性是带宽和延迟。由于光速无法超越，则延迟必然存在。延迟的存在，即时性和全球性的一致性是不可能的



1. CAP中的三个因素并不对等，P是基础，CA之间需要tradeoff。系统设计不是三选二的取舍。

2. 延迟作为可用性的指标和体现，系统设计通常需要在C和延迟之间tradeoff。

3. CAP真正的trade-off在CA之间，系统设计需要细心分解C和A，不同的系统有不同的需求。本文在对CAP分解的基础上，提供了系统设计的一些思考方法。未来系统的设计必然是要满足多种一致性模型和多种可用性需求（例如微软的cosmos DB声称支持多种一致性模型）。



reference

https://dbaplus.cn/news-159-1917-1.html

https://developer.aliyun.com/article/698930