“知其然，知其所以然”。

现在很多开发人员可能都了解分布式，俗话说：”没吃过猪肉，也见过猪跑“。那么分布式的理论基础是什么呢？为什么开源的中间件或者框架会这样做出设计呢？设计依据是什么呢？

别着急，我们今天一起聊聊分布式的相关理论以及一些一致性算法。

image-1671199381691

分布式理论

CAP 理论

image-1671178279647

CAP 理论/定理起源于 2000 年，由加州大学伯克利分校的 Eric Brewer 教授在分布式计算原理研讨会（PODC）上提出，因此CAP定理又被称作布鲁尔定理（Brewer’s theorem）。

2 年后，麻省理工学院的 Seth Gilbert 和 Nancy Lynch 发表了布鲁尔猜想的证明，CAP 理论正式成为分布式领域的定理。

CAP 也就是 Consistency（一致性）、Availability（可用性）、Partition Tolerance（分区容错性） 这三个单词首字母组合。

一致性（Consistency） : 所有节点访问同一份最新的数据副本

可用性（Availability）: 非故障的节点在合理的时间内返回合理的响应（不是错误或者超时的响应）。

分区容错性（Partition tolerance） : 分布式系统出现网络分区的时候，仍然能够对外提供服务。

当发生网络分区的时候，如果我们要继续服务，那么强一致性和可用性只能 2 选 1。也就是说当网络分区之后 P 是前提，决定了 P 之后才有 C 和 A 的选择。也就是说分区容错性（Partition tolerance）我们是必须要实现的。

简而言之就是：CAP 理论中分区容错性 P 是一定要满足的，在此基础上，只能满足可用性 A 或者一致性 C。

为啥无同时保证 CA 呢？

举个例子：若系统出现“分区”，系统中的某个节点在进行写操作。为了保证 C， 必须要禁止其他节点的读写操作，这就和 A 发生冲突了。如果为了保证 A，其他节点的读写操作正常的话，那就和 C 发生冲突了。

因此，分布式系统理论上不可能选择 CA 架构，只能选择 CP 或者 AP 架构。

BASE 理论

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

BASE 是 Basically Available（基本可用） 、Soft-state（软状态）和 Eventually Consistent（最终一致性） 三个短语的缩写。

image-1671180063029

BASE 理论是对 CAP 中一致性 C 和可用性 A 权衡的结果，其来源于对大规模互联网系统分布式实践的总结，是基于 CAP 定理逐步演化而来的，它大大降低了我们对系统的要求。

BASE 理论本质上是对 CAP 的延伸和补充，更具体地说，是对 CAP 中 AP 方案的一个补充。

基本可用 Basically Available

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

什么叫允许损失部分可用性呢？

1：响应时间上的损失: 正常情况下，处理用户请求需要 0.5s 返回结果，但是由于系统出现故障，处理用户请求的时间变为 3 s。

2：系统功能上的损失：正常情况下，用户可以使用系统的全部功能，但是由于系统访问量突然剧增，系统的部分非核心功能无法使用。

软状态 Soft state

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

最终一致性 Eventually Consitent

最终一致性强调的是系统中所有的数据副本，在经过一段时间的同步后，最终能够达到一个一致的状态。因此，最终一致性的本质是需要系统保证最终数据能够达到一致，而不需要实时保证系统数据的强一致性。

一致性

在分布式系统中，各个节点之间需要进行通信来保持数据的一致性，而通信的实现方式有共享内存和消息传递两种模型。

基于消息传递通信模型的分布式系统，不可避免的会发生下面的错误：机器宕机，进程可能会慢、被杀死或者重启，消息可能会延迟、丢失、重复。那么在这种复杂的情况下该如何保证一致性呢？

人们便试图通过算法来解决这一问题。一致性一般分为两类：强一致性，弱一致性。

强一致性的代表如下：

  • Paxos

  • Raft（muti-paxos）

  • ZAB（muti-paxos）

弱一致性的代表如下：

  • DNS

  • Gossip协议

Paxos 算法

Paxos算法是什么？

Paxos 算法是 基于消息传递 且具有 高效容错特性 的一致性算法，目前公认的解决 分布式一致性问题 最有效的算法之一。

Paxos算法产生背景？

  1. 拜占庭将军问题

拜占庭是古代东罗马帝国的首都，由于地域宽广，守卫边境的多个将军（系统中的多个节点）需要通过信使来传递消息，达成某些一致的决定。但由于信使中可能存在叛徒（系统中节点出错），这些叛徒将努力向不同的将军发送不同的消息，试图会干扰一致性的达成。

  1. Paxos算法由来

故事背景是古希腊 Paxos 岛上的多个法官在一个大厅内对一个议案进行表决，如何达成统一的结果。他们之间通过服务人员来传递纸条，但法官可能离开或进入大厅，服务人员可能偷懒去睡觉。

  1. 产生背景

在常见的 分布式系统 中，总会发生 节点宕机 或 网络异常 (包括消息的 重复、丢失、延迟、乱序、网络分区) 等情况。

Paxos 算法主要就是解决如何在一个 发生如上故障 的分布式系统中，快速正确的在集群内对某个值达成一致，并且保证 整个系统的一致性。

  1. 算法描述

Paxos算法的目标：布式环境下确定一个值，这个值被所有节点承认。

角色

Paxos将系统中的角色分为提议者 (Proposer)，决策者 (Acceptor)，和最终决策学习者 (Learner)。

Proposer: 提出提案 (Proposal)。Proposal信息包括提案编号 (Proposal ID) 和提议的值 (Value)。

Acceptor: 参与决策，回应Proposers的提案。收到Proposal后可以接受提案，若Proposal获得多数Acceptors的接受，则称该Proposal被批准。

Learner: 不参与决策，从Acceptors学习最新达成一致的提案(Value)。

  1. 算法的过程

第一阶段: Prepare准备阶段

Proposer： Proposer生成全局唯一且递增的提案编号N,，向所有Acceptor发送Prepare请求，这里无需携带提案内容，只携带提案编号即可, 即发送 Proposer(N, null)。

Acceptor： Acceptor收到Prepare请求后，有两种情况：

如果Acceptor首次接收Prepare请求, 设置ResN=N， 同时响应ok

如果Acceptor不是首次接收Prepare请求，则：

若请求过来的提案编号N小于等于上次持久化的提案编号ResN，则不响应或者响应error。

若请求过来的提案编号N大于上次持久化的提案编号ResN, 则更新ResN=N，同时给出响应。响应的结果有两种，如果这个Acceptor此前没有接受过提案， 只返回ok。否则如果这个Acceptor此前接收过提案，则返回ok和上次接受的提案编号AcceptN, 接收的提案AcceptV。

第二阶段: Accept接受阶段

Proposer： Proposer收到响应后，有两种情况：

如果收到了超过半数响应ok, 检查响应中是否有提案，如果有的话，取提案V=响应中最大AcceptN对应的AcceptV，如果没有的话，V则有当前Proposer自己设定。最后发出accept请求，这个请求中携带提案V。

如果没有收到超过半数响应ok, 则重新生成提案编号N, 重新回到第一阶段，发起Prepare请求。

Acceptor： Acceptor收到accept请求后，分为两种情况：

如果发送的提案请求N大于此前保存的RespN,接受提案，设置AcceptN = N, AcceptV=V, 并且回复ok。

如果发送的提案请求N小于等于此前保存的RespN，不接受，不回复或者回复error。

Proposer： Proposer收到ok超过半数，则V被选定，否则重新发起Prepare请求。

image-1671194375988

第三阶段: Learn学习阶段

Learner: Proposer收到多数Acceptor的Accept后，决议形成，将形成的决议发送给所有Learner。

Raft 算法

Paxos算法不容易实现，Raft算法是对Paxos算法的简化和改进。

Raft算法将一致性问题分解为两个的子问题，Leader选举和状态复制。

算法角色

  • Leader领导节点，负责发出提案

  • Follower追随者节点，负责同意Leader发出的提案

  • Candidate候选人，负责争夺Leader

算法过程

  1. 启动时，所有的节点都是follower，在election timeout内没有收到来自leader的心跳，就会发起投票。

  2. 首先是把自己切换成Candidate，然后投自己一票，然后发送给其他节点，等待它们的回复。

  3. 此后将有三种可能
    如果收到大多数的投票（含自己的一票），则赢得选举，切换成leader角色。
    如果收到别的节点当选，则切换回follower角色。
    如果一段时间内没有收到majority投票，则保持candidate状态，重新发出选举。

  4. 在任期内的Leader会不断发送心跳给其他节点证明自己还活着，其他节点受到心跳以后就清空自己的计时器并回复Leader的心跳。这个机制保证其他节点不会在Leader任期内参加Leader选举。

ZAB 协议

ZAB 协议全称：Zookeeper Atomic Broadcast（Zookeeper 原子广播协议）。

Zab协议是为分布式协调服务Zookeeper专门设计的一种支持崩溃恢复的原子广播协议 ，是Zookeeper保证数据一致性的核心算法。Zab借鉴了Paxos算法，但又不像Paxos那样，是一种通用的分布式一致性算法。它是特别为Zookeeper设计的支持崩溃恢复的原子广播协议。

整个 Zookeeper 就是在"崩溃恢复"和"原子广播"两个模式之间切换。 当 Leader 服务可以 正常使用，就进入消息广播模式，当 Leader 不可用时，则进入崩溃恢复模式。

角色

leader 集群中唯一的写请求处理者 ，能够发起投票

follower 能够接收客户端的请求，如果是读请求则可以自己处理，如果是写请求则要转发给 Leader 。在选举过程中会参与投票，有选举权和被选举权

observer 就是没有选举权和被选举权的 Follower

原子广播

  1. 所有客户端写入数据都是写入到Leader节点，然后，由 Leader广播给follower 发起票选。

  2. 如果 Follower(含leader自己的ack) 有一半以上返回 Ack 信息 就可以执行提交，大大减小了同步阻塞。也提高了可用性。

崩溃恢复

在 ZAB 协议中，为了保证程序的正确运行，整个恢复过程结束后需要选举出一个新的Leader，为了使 leader 挂了后系统能正常工作，需要解决以下两个问题：

  1. 已经被处理的消息不能丢失

  2. 被丢弃的消息不能再次出现

要明白什么不能丢，首先要明白什么时候会出现事务请求被丢失呢？

当 leader 收到合法数量 follower 的 ACKs 后，就向各个 follower 广播 COMMIT 命令，同时也会在本地执行 COMMIT 并向连接的客户端返回「成功」。但是如果在各个 follower 在收到 COMMIT 命令前 leader 就挂了，导致剩下的服务器并没有执行都这条消息。

如何解决 已经被处理的事务请求（proposal）不能丢（commit的）呢？

1、选举拥有 proposal 最大值（即 zxid 最大） 的节点作为新的 leader：由于所有提案被 COMMIT 之前必须有合法数量的 follower ACK，即必须有合法数量的服务器的事务日志上有该提案的 proposal，因此，zxid最大也就是数据最新的节点保存了所有被 COMMIT 消息的 proposal 状态。

2、新的 leader 将自己事务日志中 proposal 但未 COMMIT 的消息处理。

3、新的 leader 与 follower 建立先进先出的队列， 先将自身有而 follower 没有的 proposal 发送给 follower，再将这些 proposal 的 COMMIT 命令发送给 follower，以保证所有的 follower 都保存了所有的 proposal、所有的 follower 都处理了所有的消息。通过以上策略，能保证已经被处理的消息不会丢。

被丢弃的消息不能再次出现的场景是：

当 leader 接收到消息请求生成 proposal 后就挂了，其他 follower 并没有收到此 proposal，因此经过恢复模式重新选了 leader 后，这条消息是被跳过的。 此时，之前挂了的 leader 重新启动并注册成了 follower，他保留了被跳过消息的 proposal 状态，与整个系统的状态是不一致的，需要将其删除。