一、CAP理论

CAP 理论/定理起源于 2000年，由加州大学伯克利分校的Eric Brewer教授在分布式计算原理研讨会（PODC）上提出，因此 CAP定理又被称作 布鲁尔定理（Brewer’s theorem）
2年后，麻省理工学院的Seth Gilbert和Nancy Lynch 发表了布鲁尔猜想的证明，CAP理论正式成为分布式领域的定理。

1. 简介

CAP 也就是 Consistency（一致性）、Availability（可用性）、Partition Tolerance（分区容错性） 这三个单词首字母组合。
相关概念 - 图1
CAP 理论的提出者布鲁尔在提出 CAP 猜想的时候，并没有详细定义 Consistency、Availability、Partition Tolerance 三个单词的明确定义。
因此，对于 CAP 的民间解读有很多，一般比较被大家推荐的是下面 👇 这种版本的解释。
在一个分布式系统中不可能同时满足一致性、可用性、分区容错性，最多满足两个。对于分布式互联网应用而言，必须保证P，所以要么满足AP模型，要么满足CP模型。

  • 一致性（Consistence） : 一致性指的是多个数据副本是否能保持一致的特性，在一致性的条件下，系统在执行数据更新操作之后能够从一致性状态转移到另一个一致性状态。对系统的一个数据更新成功之后，如果所有用户都能够读取到最新的值，该系统就被认为具有强一致性。强一致性指的是如果数据不一致，就不对外提供数据服务，保证用户读取的数据始终是一致的。数据强一致性只需要通过锁机制即可解决。
  • 可用性（Availability）: 可用性指分布式系统在面对各种异常时可以提供正常服务的能力，可以用系统可用时间占总时间的比值来衡量，4 个 9 的可用性表示系统 99.99% 的时间是可用的。在可用性条件下，要求系统提供的服务一直处于可用的状态，对于用户的每一个操作请求总是能够在有限的时间内返回结果。【其实和强一致性是存在矛盾的】
  • 分区容错性（Partition tolerance） : 分布式系统出现网络分区的时候，仍然能够对外提供服务。

    什么是网络分区？ 分布式系统中，多个节点之前的网络本来是连通的，但是因为某些故障（比如部分节点网络出了问题）某些节点之间不连通了，整个网络就分成了几块区域，这就叫网络分区。每个区域内部可以通信，但是区域之间无法通信

相关概念 - 图2

2. 不是所谓的“3 选 2”

大部分人解释这一定律时，常常简单的表述为：“一致性、可用性、分区容忍性三者你只能同时达到其中两个，不可能同时达到”。实际上这是一个非常具有误导性质的说法，而且在 CAP 理论诞生 12 年之后，CAP 之父也在 2012 年重写了之前的论文。
当发生网络分区的时候，如果我们要继续服务，那么强一致性和可用性只能 2 选 1。也就是说当网络分区之后 P 是前提，决定了 P 之后才有 C 和 A 的选择。也就是说分区容错性（Partition tolerance）我们是必须要实现的。
简而言之就是：CAP 理论中分区容错性 P 是一定要满足的，在此基础上，只能满足可用性 A 或者一致性 C。
因此，分布式系统理论上不可能选择 CA 架构，只能选择 CP 或者 AP 架构。 比如 ZooKeeper、HBase 就是 CP 架构，Cassandra、Eureka 就是 AP 架构，Nacos 不仅支持 CP 架构也支持 AP 架构。
为啥不可能选择 CA 架构呢？ 举个例子：若系统出现“分区”，系统中的某个节点在进行写操作。为了保证 C， 必须要禁止其他节点的读写操作，这就和 A 发生冲突了。如果为了保证 A，其他节点的读写操作正常的话，那就和 C 发生冲突了。
选择 CP 还是 AP 的关键在于当前的业务场景，没有定论，比如对于需要确保强一致性的场景如银行一般会选择保证 CP 。
另外，需要补充说明的一点是： 如果网络分区正常的话（系统在绝大部分时候所处的状态），也就说不需要保证 P 的时候，C 和 A 能够同时保证。

3. CAP 实际应用案例

我这里以注册中心来探讨一下 CAP 的实际应用。考虑到很多小伙伴不知道注册中心是干嘛的，这里简单以 Dubbo 为例说一说。
下图是 Dubbo 的架构图。注册中心 Registry 在其中扮演了什么角色呢？提供了什么服务呢？
注册中心负责服务地址的注册与查找，相当于目录服务，服务提供者和消费者只在启动时与注册中心交互，注册中心不转发请求，压力较小。
相关概念 - 图3
常见的可以作为注册中心的组件有：ZooKeeper、Eureka、Nacos…。

  1. ZooKeeper 保证的是 CP。 任何时刻对 ZooKeeper 的读请求都能得到一致性的结果，但是， ZooKeeper 不保证每次请求的可用性比如在 Leader 选举过程中或者半数以上的机器不可用的时候服务就是不可用的。
  2. Eureka 保证的则是 AP。 Eureka 在设计的时候就是优先保证 A （可用性）。在 Eureka 中不存在什么 Leader 节点，每个节点都是一样的、平等的。因此 Eureka 不会像 ZooKeeper 那样出现选举过程中或者半数以上的机器不可用的时候服务就是不可用的情况。 Eureka 保证即使大部分节点挂掉也不会影响正常提供服务，只要有一个节点是可用的就行了。只不过这个节点上的数据可能并不是最新的。
  3. Nacos 不仅支持 CP 也支持 AP。

    4. 总结

    在进行分布式系统设计和开发时，我们不应该仅仅局限在 CAP 问题上，还要关注系统的扩展性、可用性等等
    在系统发生“分区”的情况下，CAP 理论只能满足 CP 或者 AP。要注意的是，这里的前提是系统发生了“分区”
    如果系统没有发生“分区”的话，节点间的网络连接通信正常的话，也就不存在 P 了。这个时候，我们就可以同时保证 C 和 A 了。
    总结：如果系统发生“分区”，我们要考虑选择 CP 还是 AP。如果系统没有发生“分区”的话，我们要思考如何保证 CA 。

推荐阅读

  1. CAP 定理简化 （英文，有趣的案例）
  2. 神一样的 CAP 理论被应用在何方 （中文，列举了很多实际的例子）
  3. 请停止呼叫数据库 CP 或 AP（英文，带给你不一样的思考）

二、BASE 理论

BASE 理论起源于 2008 年， 由eBay的架构师Dan Pritchett在ACM上发表。

1. 简介

BASE 是 Basically Available（基本可用） 、Soft-state（软状态） 和 Eventually Consistent（最终一致性） 三个短语的缩写。BASE 理论是对 CAP 中一致性 C 和可用性 A 权衡的结果，其来源于对大规模互联网系统分布式实践的总结，是基于 CAP 定理逐步演化而来的，它大大降低了我们对系统的要求。

2. BASE 理论的核心思想

即使无法做到强一致性，但每个应用都可以根据自身业务特点，采用适当的方式来使系统达到最终一致性。
也就是牺牲数据的一致性来满足系统的高可用性，系统中一部分数据不可用或者不一致时，仍需要保持系统整体“主要可用”。
BASE 理论本质上是对 CAP 的延伸和补充，更具体地说，是对 CAP 中 AP 方案的一个补充。
为什么这样说呢？
CAP 理论这节我们也说过了：
如果系统没有发生“分区”的话，节点间的网络连接通信正常的话，也就不存在 P 了。这个时候，我们就可以同时保证 C 和 A 了。因此，如果系统发生“分区”，我们要考虑选择 CP 还是 AP。如果系统没有发生“分区”的话，我们要思考如何保证 CA 。
因此，AP 方案只是在系统发生分区的时候放弃一致性，而不是永远放弃一致性。在分区故障恢复后，系统应该达到最终一致性。这一点其实就是 BASE 理论延伸的地方。

3. BASE 理论三要素

image.png

3.1. 基本可用

基本可用是指分布式系统在出现不可预知故障的时候，允许损失部分可用性。但是，这绝不等价于系统不可用。
什么叫允许损失部分可用性呢？

  • 响应时间上的损失: 正常情况下，处理用户请求需要 0.5s 返回结果，但是由于系统出现故障，处理用户请求的时间变为 3 s。
  • 系统功能上的损失：正常情况下，用户可以使用系统的全部功能，但是由于系统访问量突然剧增，系统的部分非核心功能无法使用。

    3.2. 软状态

    软状态指允许系统中的数据存在中间状态（CAP 理论中的数据不一致），并认为该中间状态的存在不会影响系统的整体可用性，即允许系统在不同节点的数据副本之间进行数据同步的过程存在延时。

    3.3. 最终一致性

    最终一致性强调的是系统中所有的数据副本，在经过一段时间的同步后，最终能够达到一个一致的状态。因此，最终一致性的本质是需要系统保证最终数据能够达到一致，而不需要实时保证系统数据的强一致性。
    分布式一致性的 3 种级别：
  1. 强一致性 ：系统写入了什么，读出来的就是什么。
  2. 弱一致性 ：不一定可以读取到最新写入的值，也不保证多少时间之后读取到的数据是最新的，只是会尽量保证某个时刻达到数据一致的状态。
  3. 最终一致性 ：弱一致性的升级版，系统会保证在一定时间内达到数据一致的状态。

业界比较推崇是最终一致性级别，但是某些对数据一致要求十分严格的场景比如银行转账还是要保证强一致性。
那实现最终一致性的具体方式是什么呢? 《分布式协议与算法实战》 中是这样介绍：

  • 读时修复 : 在读取数据时，检测数据的不一致，进行修复。比如 Cassandra 的 Read Repair 实现，具体来说，在向 Cassandra 系统查询数据的时候，如果检测到不同节点 的副本数据不一致，系统就自动修复数据。
  • 写时修复 : 在写入数据，检测数据的不一致时，进行修复。比如 Cassandra 的 Hinted Handoff 实现。具体来说，Cassandra 集群的节点之间远程写数据的时候，如果写失败 就将数据缓存下来，然后定时重传，修复数据的不一致性。
  • 异步修复 : 这个是最常用的方式，通过定时对账检测副本数据的一致性，并修复。

比较推荐 写时修复，这种方式对性能消耗比较低。

4. 总结

ACID 是数据库事务完整性的理论，CAP 是分布式系统设计理论，BASE 是 CAP 理论中 AP 方案的延伸。

三、一致性协议

事务需要跨多个分布式节点时，为了保证事务的ACID特性，需要选举出一个协调者来协调分布式各个节点的调度，基于这个思想衍生出了多种一致性协议：

1. 2PC 二阶段提交

顾名思义，二阶段提交将事务的提交过程分为两个阶段：
image.png
阶段一：提交事务请求

  1. 协调者执行事务操作（未提交），并向所有参与者节点发送事务内容，询问是否可以执行事务操作，并等待其他参与者节点的反馈
  2. 各参与者节点执行事务操作（事务未提交）
  3. 各参与者反馈给协调者，事务是否可以执行

阶段二：事务提交
根据阶段一各个参与者节点反馈的ack，如果所有参与者节点反馈ack，则执行事务提交，否则中断事务

事务提交：

  1. 协调者向各个参与者节点发送commit请求
  2. 参与者节点接收到commit请求后，执行事务的提交操作
  3. 各参与者节点完成事务提交后，向协调者返回提交commit成功确认消息
  4. 协调者接受各个参与者节点的ack后，完成自身事务的commit

中断事务：

  1. 协调者向各个参与者节点发送回滚请求
  2. 各个参与者节点回滚事务
  3. 反馈给协调者事务回滚结果
  4. 协调者接收各参与者节点ack后回滚自身事务

二阶段提交存在的问题：

  • 同步阻塞：二阶段提交过程中，所有参与事务操作的节点处于同步阻塞状态，无法进行其他操作
  • 单点问题：一旦协调者出现单点故障，无法保证事务的一致性操作
  • 脑裂导致数据不一致：如果分布式节点出现网络分区，某些参与者未收到commit提交命令，则出现部分参与者完成数据提交，未收到commit命令的参与者无法完成事务提交，整个分布式系统则出现了数据不一致现象。

    2. 3PC 三阶段提交

    3PC是2PC的改进版，实质是将2PC中的阶段一提交事务请求拆分为两步，形成了CanCommit、PreCommit、doCommit三个阶段的事务一致性协议。
    image.png
    阶段一：CanCommit（类似网络通信的测试）
  1. 事务询问
  2. 各参与者节点向协调者反馈事务询问的响应

阶段二：preCommit
根据阶段一的反馈结果分为两种情况：

执行事务预提交

  1. 发送预提交请求：协调者向所有参与者节点发送preCommit请求，进入prepared阶段
  2. 事务预提交：各参与者节点接收到preCommit请求后，执行事务操作
  3. 各参与者节点向协调者反馈事务执行

中断事务
任意一个参与者节点反馈给协调者响应No时，或者在等待超时后，协调者还未收到参与者的反馈，就中断事务，中断事务分为两步

  1. 协调者向各个参与者节点发送abort请求
  2. 参与者接收到abort请求，或者等待超时时间后，中断事务

阶段三：doCommit
根据阶段二的反馈结果分为两种情况：

执行提交

  1. 发送提交请求：协调者向所有参与者节点发送doCommit请求
  2. 事务提交：各参与者节点接收到doCommit请求后，执行事务提交操作
  3. 反馈事务提交结果：各参与者节点完成事务提交以后，向协调者发送ack
  4. 事务完成：协调者接收各个参与者反馈的ack后，完成事务

中断事务

  1. 参与者接收到abort请求后，执行事务回滚
  2. 参与者完成事务回滚以后，向协调者发送ack
  3. 协调者接收回滚ack后，回滚事务


3PC相较于2PC而言，解决了其存在的同步阻塞（超时机制）与单点问题，但是仍然无法解决网络分区问题

3. Paxos算法

Paxos算法是Leslie Lamport1990年提出的一种一致性算法，该算法是一种基于消息传递，可以提高分布式系统容错性的一致性算法，解决了3PC中网络分区的问题，Paxos算法可以在节点失效、网络分区、网络延迟等各种异常情况下保证所有节点都处于同一状态（在分布式系统中，如果产生宕机或者网络异常情况，该算法可以快速正确地在集群内部对某个数据达成一致，并且不管发生任何异常，都不会破坏整个系统地一致性），同时Paxos算法引入了“过半”理念，即少数服从多数原则。

Paxos有三个版本：

  • Basic Paxos
  • Multi Paxos
  • Fast Paxos

在Paxos算法中，有四种角色，分别具有三种不同的行为，但多数情况，一个进程可能同时充当多种角色。

  • client：系统外部角色，请求发起者，不参与决策
  • proposer：提案提议者
  • acceptor：提案的表决者，即是否accept该提案，只有超过半数以上的acceptor接受了提案，该提案才被认为被“选定”
  • learners：提案的学习者，当提案被选定后，其同步执行提案，不参与决策

Paxos算法选举过程分为两个阶段：prepare阶段、accept阶段

  • prepare阶段（准备阶段）
    1. proposer提出一个提案，编号为N，发送给所有的acceptor。
    2. 每个表决者都保存自己的accept的最大提案编号maxN，当表决者收到Prepare(N)请求时，会比较N与maxN的值，若N小于maxN，则提案已过时，拒绝Prepare(N)请求。若N大于等于maxN，则接受提案，并将该表决者曾经接受过的编号最大的提案Proposal(myid,maxN,value)反馈给提议者：其中myid表示表决者acceptor的标识id，maxN表示接受过的最大提案编号maxN，value表示提案内容。若当前表决者未曾accept任何提议，会将Proposal(myid,null,nul)反馈给提议者。
  • accept阶段（同意阶段）
    1. 提议者proposer发出Prepare(N)，若收到超过半数表决者acceptor的反馈，proposer将真正的提案内容Accept(N,value)发送给所有表决者。
    2. 表决者acceptor接受提议者发送的Accept(N,value)提案后，会将自己曾经accept过的最大提案编号maxN和反馈过的prepare的最大编号，若N大于这两个编号，则当前表决者accept该提案，并反馈给提议者。否则拒绝该提议。
    3. 若提议者没有收到半数以上的表决者accept反馈，则重新进入prepare阶段，递增提案编号，重新提出prepare请求。若收到半数以上的accept，则其他未向提议者反馈的表决者称为learner，主动同步提议者的提案。

image.png
正常流程：
image.png
单点故障，部分节点失败：
image.png

proposer失败：
image.png

Basic Paxos算法还存在活锁问题（liveness）或dueling，而且较难实现，其解决方法是引入随机值，使得不同proposer提交提案的时间错开：
image.png

4. Raft算法

http://thesecretlivesofdata.com/raft/