分布式定理之CAP

# CAP定理

在理论计算机科学中，CAP定理（CAP theorem），又被称作布鲁尔定理（Brewer's theorem），这个定理起源于加州大学柏克莱分校（University of California, Berkeley）的计算机科学家埃里克·布鲁尔在2000年的分布式计算原理研讨会（PODC）上提出的一个猜想。在2002年，麻省理工学院（MIT）的赛斯·吉尔伯特和南希·林奇发表了布鲁尔猜想的证明，使之成为一个定理。它指出对于一个分布式计算系统来说，不可能同时满足以下三点：

# 一致性（Consistency）

所有节点在同一时间具有相同的数据视图。在分布式系统中，如果一个节点对数据进行了修改，那么其他节点读取数据时应该能够立即看到这个修改（强一致性）。

而在分布式系统中一致性又有如下模型分类：

强一致性

当更新操作完成之后，任何多个后续进程或者线程的访问都会返回最新的更新过的值，直到这个数据被其他数据更新为止。

但是这种实现对性能影响较大，因为这意味着，只要上次的操作没有处理完，就不能让用户读取数据（同步阻塞）。
弱一致性

系统并不保证进程或者线程的访问都会返回最新更新过的值。系统在数据写入成功之后，不承诺立即可以读到最新写入的值，也不会具体的承诺多久之后可以读到。但会尽可能保证在某个时间级别（比如秒级别）之后，可以让数据达到一致性状态。
最终一致性

最终一致性也是弱一致性的一种，它无法保证数据更新后，所有后续的访问都能看到最新数值，而是需要一个时间，在这个时间之后可以保证这一点，而在这个时间内，数据也许是不一致的，这个系统无法保证强一致性的时间片段被称为：不一致窗口。不一致窗口的时间长短取决于很多因素，比如备份数据的个数、网络传输延迟速度、系统负载等。

最终一致性在实际应用中又有多种变种（参考：分布式系统的一致性协议之 2PC 和 3PC (opens new window)）：
- 因果一致性
- 读你所写一致性
- 会话一致性
- 单调读一致性
- 单调写一致性

一致性模型关系

# 可用性（Availability）

每个非故障节点在有限时间内能够返回合理的响应。即系统对于用户的请求能够保证在有限时间内得到响应，不会因为某个节点故障而导致整个系统不可用。

# 分区容错性（Partition Tolerance）

即使系统出现网络分区（节点之间无法直接通信），系统仍然能够继续工作。分区容错性是分布式系统必须具备的基本特性，因为在真实的网络环境中，节点之间的通信可能会失败。我们需要知道**分区（Partition）**这个概念（各个节点之间可能由于网络故障或其他原因导致无法直接通信的情况）。

# 白话CAP理论

假设现在我们拥有一个分布式系统（指由多台计算机通过网络连接，协同工作来完成一个共同的任务的系统）；
计算机被称为节点（nodes），它们可以位于同一地点或全球范围内的不同地方并且网络相互连通，但是由于分区的缘故导致互相无法协同对外提供服务，会出现如下情况：
- 部分节点不可用，部分节点可用，可用节点任然能正常接收外部请求，但是由于分布式系统是由多个节点协同完成一个任务，可能刚好可用节点的调用了一个不可用的节点，就会导致系统超时或者抛出不可预见的异常，导致系统不可用，所以这种情况就需要**可用性（Availability）**的理论支持，有了理论我们就需要根据这个理论做一些增强系统可用性的操作例如：
  - 系统设计层面
    - 负载均衡
    - 自动化故障检测和恢复
    - 容器化和微服务
    - 服务降级
  - 系统运维层面
    - 灰度发布
    - 监控和警报系统
    - 冗余和备份
    - 网络优化
    - 容灾计划
- 当可用节点在进行业务数据的存储操作时只存在了当前节点，由于分区缘故导致其他其他可用节点无法访问到当前节点的数据这将是一个灾难，所以分布式系统中必定会将数据分布式存储（将数据分布式地存储在多个节点上的一种方式）数据在不同节点相互拷贝备份使其具备一致性（Consistency），分区会导致不同节点访问同一份数据会出现不一致的情况；
从上述描述我们可以看出，不管怎么样分布式系统分区容错性（Partition Tolerance）是必不可少的，而由于如果需要更高的可用性（Availability），我们需要在有限时间内能够返回合理的响应，如果这个合理的响应返回的是脏数据（不同节点返回数据不一致的情况）等同于不可用，但是防止数据不一致，我们就需要保证一致性（Consistency），然而更高的一致性会导致接口效率变低，从而有可能打破了**可用性（Availability）**有限时间的范围，所以可以看出，在保证分区容错的前提下，一致性（Consistency）和可用性Availability）是矛盾的。

# CAP模型应用场景

CAP

# CA模型

保证了系统的一致性和可用性，却违背了分布式系统的分区容错性。实际上分区是不可避免的，严格上CA指的是允许分区后各子系统依然保持CA。

常见的技术组件：

集群数据库（传统的关系性数据库（Mysql,Oracle等），一些分布式关系型数据库（Google Spanner））。

# CP模型

保证了系统的一致性和分区容错性，但用户的体验较差，即当系统宕机时，需要等待所有结点的数据一致时，用户才可访问系统。

常见的技术组件：

Apache ZooKeeper：用于分布式协调和一致性。
HBase（在一些配置中）：分布式列存数据库，通常被归类为CP系统。
MongoDB 在一些特定情况下可以体现CP模型，即强一致性和分区容忍性。
Redis 在默认配置下更倾向于满足分区容错性（Partition Tolerance，P）和可用性（Availability，A），而在某些情况下，可能牺牲了强一致性（Consistency，C）。因此，Redis 更接近于 AP 模型，但也有一些特性可以使其在一些场景下体现 CP 特性（数据复制和持久性配置，分片和分区，丢失部分数据）。

# AP模型

保证了系统的可用性和分区容错性，但是结点之间的数据会出现不一致的现象。

常见的技术组件：

Amazon DynamoDB：分布式键值存储服务，强调高可用性和分区容忍性。
Couchbase：分布式NoSQL数据库，强调可用性和分区容忍性。
Cassandra：分布式、高度可伸缩的NoSQL数据库，支持分区容忍性和可用性。
Redis：分布式内存缓存系统，强调高性能和可用性。可以配置为支持分区容忍性。
Apache Kafka： 分布式流处理平台，具有高可用性和分区容忍性，用于实现事件驱动架构。
Elasticsearch： 分布式搜索引擎，支持大规模数据索引和搜索，具有高可用性和分区容忍性。
Kubernetes： 开源容器编排系统，用于自动部署、扩展和管理容器化应用，具有高可用性和分区容忍性。
Apache Spark： 分布式计算框架，用于大规模数据处理和分析，支持高可用性和分区容忍性。

# CAP实际应用中的算法和协议

在实际应用中，有一些协议和算法被设计用来处理CAP问题，其中一些主要的协议包括：

名称	描述	特点	应用
Two-Phase Commit，2PC	两阶段提交协议是一种分布式事务协议，用于确保分布式系统中执行的事务能够保持一致性。它涉及一个协调者（Coordinator）和多个参与者（Participants）。	简单性，一致性，阻塞问题。	2PC在一些分布式数据库系统和事务处理系统中得到了广泛应用。
Three-Phase Commit，3PC	三阶段提交协议是一种分布式事务协议，是对两阶段提交协议（2PC）的改进。与2PC相比，3PC引入了额外的PreCommit阶段，以解决2PC可能导致的长时间阻塞问题。3PC的核心目标是提高分布式事务的鲁棒性，减轻对协调者的单点故障敏感性。	引入PreCommit阶段，减轻单点故障敏感性，减轻单点故障敏感性。	三阶段提交协议在一些分布式系统和数据库中得到应用。它通常在对一致性要求较高的场景下使用，如金融系统、电信系统等
Paxos	Paxos是一种分布式一致性算法（Paxos常被误称为“一致性算法”。但是“一致性（consistency）”和“共识（consensus）”并不是同一个概念。Paxos是一个共识（consensus）算法。Paxos算法 (opens new window)），用于解决分布式系统中的一致性问题。	Paxos强调一致性，但在网络分区时可能牺牲可用性。	用于构建一致性分布式系统，例如分布式数据库。
Raft	Raft是一种相对于Paxos更容易理解的一致性算法，用于解决分布式系统中的一致性问题。	Raft强调一致性，但在网络分区时可能牺牲可用性。	用于构建一致性分布式系统，类似于Paxos的应用场景。
ZooKeeper Atomic Broadcast (ZAB)	ZooKeeper是一个分布式协调服务，其底层使用了ZAB协议。	ZAB强调一致性，但在网络分区时可能牺牲可用性。	用于分布式系统中的协调和一致性需求。