分布式理论协议与算法 第一弹 CAP理论
CAP 理论，也被称为 CAP 协议，指的是在一个分布式系统中，最多只能同时满足「一致性（Consistency）」、「可用性（Availability）」和「分区容错性（Partition tolerance）」这三项中的两项，不可能三者兼顾。 本篇内容主要包括：CAP 理论相关概念概述、CAP 理论的证明、CAP 的权衡取舍
文章目录
一、CAP 理论相关概念概述
1、CAP 理论
CAP 理论，也被称为 CAP 协议，指的是在一个分布式系统中，最多只能同时满足「一致性（Consistency）」、「可用性（Availability）」和「分区容错性（Partition tolerance）」这三项中的两项，不可能三者兼顾。
2、一致性（Consistency）
在 CAP 理论中，一致性（Consistency）通常指的是：“All nodes see the same data at the same time”，即 “所有节点在同一时间的数据完全一致”。Ps：一致性问题是多个数据拷贝并发读写场景下才有的问题，因此理解时一定要注意结合考虑多个数据拷贝下并发读写的场景。
对于一致性模型划分，可以分为从「读写角度」、「客户中心-数据中心」角度进行一致性模型划分：
# 读写角度一致性划分
读写角度一致性划分，是 Werner Vogels（亚马逊 CTO）提出的基于读写响应的一致性分类，其将一致性划分强一致性、弱一致性、最终一致性。其中最终一致性是弱一致性的一种特殊情况，表示系统最终将达成一致：
- 强一致性（Strong Consistency）：系统保证某个被更新的数据在后续的读操作中都可读到更新后的新值。为达到强一致性，存储同一份数据的多个副本上的操作必须同步进行。也就是说：在执行一次更新操作时系统必须被阻塞，所有的副本在操作完成前都需被锁定；
- 弱一致性（Weak Consistency）：系统不强制要求某个被更新的数据在后续读操作中都可读到更新后的新值，即允许在更新后的一段时间内才读到新值。这里将从该数据开始更新到后续读取操作读到该数据的最新值的这段延时称为 “不一致性窗口（inconsistency window）”；
- 最终一致性（Eventual Consistency）：系统保证对某个后续不再更新的数据在一次更新后能在有限的时间内最终读取到该数据的最新值。大多数NoSQL数据库都基于最终一致性模型构建，如Redis、MongoDB等。
# 客户中心-数据中心角度，客户中心一致性划分
以客户为中心的一致性模型从用户角度出发，它将整个系统看做一个黑盒进行交互。该模型仅保证单一用户对存储数据的访问一致性。该模型并不保证不同用户的并发操作的一致性。以客户为中心的一致性模型分类可分为：单调读一致性（Monotonic Read Consistency）、单调写一致性（Monotonic Writes Consistency）、读已之所写一致性（Read Your Writes Consistency）以及 读后写一致性（Write Follows Read Consistency）。Ps：每种分类的详细内容以后介绍！
# 客户中心-数据中心角度，数据中心一致性划分
以数据为中心的一致性从服务端出发，关注副本间的同步过程及副本上操作的执行顺序。该模型考虑到并发（多个副本可能同时被更新）情景的存在并提供该种情景下的一致性模型。以数据为中心的一致性模型分类如下：弱一致性（Weak Consistency）、最终一致性（Eventual Consistency）、因果一致性（Causal Consistency）以及 顺序一致性（Sequential Consistency）。Ps：每种分类的详细内容以后介绍！
3、可用性（Availability）
在 CAP 理论中，可用性（Availability）通常指的是：“Reads and writes always succeed”，即 “服务在正常响应时间内一直可用”。好的可用性主要是指系统能够很好的为用户服务，不出现用户操作失败或者访问超时等用户体验不好的情况。可用性通常情况下可用性和分布式数据冗余，负载均衡等有着很大的关联。
4、分区容错性（Partition tolerance）
在 CAP 理论中，分区容错性（Partition tolerance）通常指的是：“The system continues to operate despite arbitrary message loss or failure of part of the system”，即 “分布式系统在遇到某节点或网络分区故障的时候，仍然能够对外提供满足一致性或可用性的服务”。
网络分区解释：比如现在有两台服务器（服务器A、服务器B），二者之间是存在通信的，但是突然间，由于位置原因，二者之间的网络链接中断，导致原本在同一个网络的「服务器A」与「服务器B」发生了网络分区，变成了「服务器A」所在的「A网络」和「服务器A」所在的「B网络」。
而所谓的分区容忍性，就是说一个数据服务的多台服务器在发生了上述情况（网络分区）的时候，依然能继续提供服务！
二、CAP 理论的证明
1、CAP 理论的证明-基本场景
接下来是对 CAP 理论的证明，下面是一个分布式系统的基本场景：网络中有两个节点 Node1 和 Node2（可以简单的理解 Node1 和 Node2 分别是两台计算机），二者之间网络可以连通，Node1 中有一个「应用程序A」和一个「数据库A」，Node2 也有一个「应用程序B」和一个「数据库B」。现在，「应用程序A」和「应用程序B」是分布式系统的两个部分，「数据库A」和「数据库B」是分布式系统的数据存储的两个子数据库。
- 在满足一致性的情况下：Node1 和 Node2 中的数据是一样的，V0=V0。
- 在满足可用性的情况下：用户不管是请求 Node1 或者 Node2，都会得到立即响应。
- 在满足分区容错性的情况下：Node1 和 Node2 有任何一方宕机，或者网络不通的时候，都不会影响Node1和Node2彼此之间的正常运作。
2、CAP 理论的证明-正常运转
下图是分布式系统正常运转的流程，用户向 Node1 机器请求数据更新，程序 A 更新数据库 V0 为 V1，分布式系统将数据进行同步操作 M，将V1 同步到 Node2 中 V0，使得 Node2 中的数据 V0 也更新为 V1，Node2 中的数据再响应 Node2 的请求。
这里，可以定义 Node1 和 Node2 的数据库 V 之间的数据是否一样为一致性；外部对 Node1 和 Node2 的请求响应为可用性；Node1 和 Node2之间的网络环境为分区容错性。
3、CAP 理论的证明-出现异常
这是正常运作的场景，也是理想的场景，然而现实是残酷的，当错误发生的时候，一致性和可用性还有分区容错性，是否能同时满足，还是说要进行取舍呢？
作为一个分布式系统，它和单机系统的最大区别，就在于网络，现在假设一种极端情况，Node1 和 Node2之间的网络断开了，我们要支持这种网络异常，相当于要满足分区容错性，能不能同时满足一致性和响应性呢？还是说要对他们进行取舍。
假设在 Node1 和 Node2 之间网络断开的时候，有用户向 Node1 发送数据更新请求，那 Node1 中的数据 V0 将被更新为 V1，由于网络是断开的，所以分布式系统同步操作 M，所以 Node2 中的数据依旧是 V0；这个时候，有用户向 Node2 发送数据读取请求，由于数据还没有进行同步，应用程序没办法立即给用户返回最新的数据 V1，怎么办呢？
有二种选择：
- 第一，牺牲数据一致性，响应旧的数据 V0 给用户；
- 第二，牺牲可用性，阻塞等待，直到网络连接恢复，数据更新操作 M 完成之后，再给用户响应最新的数据 V1。
这个过程，证明了要满足分区容错性的分布式系统，只能在一致性和可用性两者中，选择其中一个。
三、CAP 的权衡取舍
1、CAP 的权衡取舍
通过 CAP 理论，我们知道无法同时满足一致性、可用性和分区容错性这三个特性，那要舍弃哪个呢？
- CA without P：如果不要求 P（不允许分区），则 C（强一致性）和 A（可用性）是可以保证的。但其实分区不是你想不想的问题，而是始终会存在，因此 CA 的系统更多的是允许分区后各子系统依然保持 CA。
- CP without A：如果不要求 A（可用），相当于每个请求都需要在 Server 之间强一致，而 P（分区）会导致同步时间无限延长，如此CP 也是可以保证的。很多传统的数据库分布式事务都属于这种模式。
- AP wihtout C：要高可用并允许分区，则需放弃一致性。一旦分区发生，节点之间可能会失去联系，为了高可用，每个节点只能用本地数据提供服务，而这样会导致全局数据的不一致性。现在众多的 NoSQL 都属于此类。
对于多数大型互联网应用的场景，主机众多、部署分散，而且现在的集群规模越来越大，所以节点故障、网络故障是常态，而且要保证服务可用性达到 N 个 9，即保证 P 和 A，舍弃C（退而求其次保证最终一致性）。虽然某些地方会影响客户体验，但没达到造成用户流程的严重程度。
对于涉及到钱财这样不能有一丝让步的场景，C 必须保证。网络发生故障宁可停止服务，这是保证 CA，舍弃 P。貌似这几年国内银行业发生了不下 10 起事故，但影响面不大，报道也不多，广大群众知道的少。还有一种是保证 CP，舍弃 A。例如网络故障事只读不写。
2、ACID 理论
ACID 可以理解为 ACID 最重要的含义，就是 Atomicity 和 Isolation ，即强制一致性，要么全做要么不做，所有用户看到的数据一致。强调数据的可靠性, 一致性和可用性。
ACID 为 Atomicity、Consistency、Isolation and Durability，其中 ACID 分别表示为：
- 原子性（Atomicity）：事务中的操作要么都做，要么都不做；
- 一致性（Consistency）：系统必须始终处在强一致状态下；
- 隔离性（Isolation）：一个事务的执行不能被其他事务所干扰；
- 持续性（Durability）：一个已提交的事务对数据库中数据的改变是永久性的。
保证 ACID 是传统关系型数据库中事务管理的重要任务，几种事务类型为：未提交读、可提交读、可重复读、可序列化。
3、BASE 理论
BASE 理论是由 eBay 架构师提出的。BASE 是对 CAP 中一致性和可用性权衡的结果，其来源于对大规模互联网分布式系统实践的总结，是基于 CAP 定律逐步演化而来。其核心思想是即使无法做到强一致性，但每个应用都可以根据自身业务特点，才用适当的方式来使系统打到最终一致性。
BASE 理论 是 Basically Available（基本可用），Soft State（软状态）和 Eventually Consistent（最终一致性）三个短语的缩写。