1 Zookeeper 简介

​ ZooKeeper 由雅虎研究院开发，后来捐赠给了 Apache。ZooKeeper 是一个开源的分布式应用程序协调服务器，其为分布式系统提供一致性服务。其一致性是通过基于 Paxos 算法的ZAB 协议完成的。其主要功能包括：配置维护、域名服务、分布式同步、集群管理等。
​ zookeeper 的官网：http://zookeeper.apache.org

2 一致性

​ zk 是如何保证分布式系统的一致性的呢？是因为 zk 具有以下几方面的特点：
​ 顺序一致性：zk 接收到的 N 多个事务请求（写操作请求），其会被严格按照接收顺序应用到zk 中。
​ 原子性：所有事务请求的结果在 zk 集群中每一台主机上的应用情况都是一致的。要么全部应用成功，要么全部失败。
​ 单一视图：无论 Client 连接的是 zk 集群中的哪个主机，其看到的数据模型都是一致的。
​ 可靠性：一旦 zk 成功应用了某事务，那么该事务所引发的 zk 状态变更会被一直保留下来，直到另一个事务将其修改。
​ 最终一致性：一旦一个事务被成功应用，zk 可以保证在一个很短暂时间后，Client 最终能够从 zk 上读取到最新的数据状态。注意，不能保证实时读取到。

3 Paxos 算法

​ 对于zk 理论的学习，最重要也是最难的知识点就是 Paxos 算法。所以我们首先学习 Paxos算法。

3.1 算法简介

​ Paxos 算法是莱斯利·兰伯特(Leslie Lamport)1990 年提出的一种基于消息传递的、具有高容错性的一致性算法。Google Chubby 的作者 Mike Burrows 说过，世上只有一种一致性算法， 那就是 Paxos，所有其他一致性算法都是 Paxos 算法的不完整版。Paxos 算法是一种公认的晦涩难懂的算法，并且工程实现上也具有很大难度。较有名的 Paxos 工程实现有Google Chubby、ZAB、微信的 PhxPaxos 等。
​ Paxos 算法是用于解决什么问题的呢？Paxos 算法要解决的问题是，在分布式系统中如何就某个决议达成一致。

3.2 Paxos 与拜占庭将军问题

​ 拜占庭将军问题是由 Paxos 算法作者莱斯利·兰伯特提出的点对点通信中的基本问题。该问题要说明的含义是，在不可靠信道上试图通过消息传递的方式达到一致性是不可能的。所以，Paxos 算法的前提是不存在拜占庭将军问题，即信道是安全的、可靠的，集群节点间传递的消息是不会被篡改的。
​ 一般情况下，分布式系统中各个节点间采用两种通讯模型：共享内存（Shared Memory）、消息传递（Messages Passing）。而 Paxos 是基于消息传递通讯模型的。

3.3 算法描述

（1）三种角色

​ 在 Paxos 算法中有三种角色，分别具有三种不同的行为。但很多时候，一个进程可能同时充当着多种角色。
​ Proposer：提案者。
​ Acceptor：表决者。
​ Learner：学习者，同步者。

（2）Paxos 算法的一致性

​ Paxos 算法的一致性主要体现在以下几点：
​ 每个提案者在提出提案时都会首先获取到一个递增的、全局唯一的提案编号 N，然后将该编号赋予其要提出的提案。
​ 关于N 的生成，有两种方式：全局性生成器；提案者自身维护 N。
​ 每个表决者在 accept 某提案后，会将该提案的编号 N 记录在本地，这样每个表决者中保存的已经被 accept 的提案中会存在一个编号最大的提案，其编号假设为 maxN。每个表决者仅会 accept 编号大于自己本地 maxN 的提案。
​ 在众多提案中最终只能有一个提案被选定。
​ 一旦一个提案被选定，则其它学习者会主动同步(Learn)该提案到本地。
​ 没有提案被提出则不会有提案被选定。

Paxos 故事：
1、有一个叫做 Paxos 的小岛(Island)上面住了一批居民，岛上面所有的事情由一些特殊的人决定，他们叫做议员(Senator)。
2、议员的总数(SenatorCount)是确定的，不能更改。
3、岛上每次环境事务的变更都需要通过一个提议(Proposal)，每个提议都有一个编号(PID)，这个编号是一直增长的，不能倒退。
4、每个提议都需要超过半数((SenatorCount)/2+1)的议员同意才能生效。
5、每个议员只会同意大于当前编号的提议，包括已生效的和未生效的。
6、如果议员收到小于等于当前编号的提议，他会拒绝，并告知对方：你的提议已经有 人提过了。这里的当前编号是每个议员在自己记事本上面记录的编号，他不断更新这个编号。整个议会不能保证所有议员记事本上的编号总是相同的。

现在议会有一个目标：保证所有的议员对于提议都能达成一致的看法。好，现在议会开始运作，所有议员一开始记事本上面记录的编号都是 0。
有一个议员发了一个提议：
将电费设定为 1 元/度。他首先看了一下记事本，嗯，当前提议编号是 0，那么我的这个提议的编号就是 1，于是他给所有议员发消息：1 号提议，设定电费 1 元/度。其他议员收到消息以后查了一下记事本，哦，当前提议编号是 0，这个提议可接受，于是他记录下这个提议并回复：我接受你的 1 号提议，同时他在记事本上记录：当前提议编号为 1。发起提议的议员收到了超过半数的回复，立即给所有人发通知：1 号提议生效！收到的议员会修改他的记事本，将 1 好提议由记录改成正式的法令，当有人问他电费为多少时，他会查看法令并告诉对方：1 元/度。
现在看冲突的解决：
假设总共有三个议员 S1、S2 与 S3，S1 和 S2 同时发起了一个提议：设定电费，提议编号均为 1。S1 想设为 1 元/度，S2 想设为 2 元/度。此时 S3 先收到了 S1 的提议，于是他一查记事本，发现提议编号 1 大于当前的编号 0，所以同意了该提议。紧接着他又收到了 S2 的提议，结果他再查记事本，发现这个提议的编号等于当前记录的编号 1，于是他拒绝了这个提议：对不起，这个提议先前提过了。于是 S2 的提议被拒绝，S1 正式发布了提议：1 号提议生效。S2 向 S1 或者 S3 打听并更新了 1 号法令的内容，然后他可以选择继续发起 2 号提议。

Paxos 对外是如何工作的： 
情况一：
屁民甲(Client)到某个议员(ZKServer)那里询问(Get)某条法令的情况(ZNode 的数据)，议员毫不犹豫的拿出他的记事本(localStorage)，查阅法令并告诉他结果。
情况二：
屁民乙(Client)到某个议员(ZKServer)那里要求政府归还欠他的一万元钱，议员让他在办公室等着，自己到议会将这个作为一个提议发给了所有议员。多数议员表示欠屁民的钱一定要还，于是该访问从国库中拿出一万元还债，国库总资产由 100 万变成 99 万。屁民乙拿到钱回去了(Client 函数返回)。

（3）2PC 与 3PC

​ Paxos 对于提案的提交算法有两种方案，2PC 与 3PC。
​ 2PC：Two Phase Commit，即 prepare -> accept。
​ 3PC：Three Phase Commit，即 prepare -> accept -> commit。
​ 它们的区别主要就在于 accept 阶段中是否包含 commit 功能。具体看下面的描述。

3.4 3PC 算法过程描述

​ Paxos 算法的 3PC 执行过程划分为三个阶段：准备阶段 prepare、接受阶段 accept，与提交阶段 commit。

01.png

（1）prepare 阶段

​ 1) 提案者(Proposer)准备提交一个编号为 N 的提议，于是其首先向所有表决者(Acceptor)发送 prepare(N)请求，用于试探集群是否支持该编号的提议。
​ 2) 每个表决者(Acceptor)中都保存着自己曾经 accept 过的提议中的最大编号 maxN。当一个表决者接收到其它主机发送来的 prepare(N)请求时，其会比较N 与 maxN 的值。有以下几种情况：
​ a) 若 N 小于 maxN，则说明该提议已过时，当前表决者采取不回应或回应 Error 的方式来拒绝该 prepare 请求；
​ b) 若N 大于maxN，则说明该提议是可以接受的，当前表决者会首先将该 N 记录下来， 并将其曾经已经 accept 的编号最大的提案 Proposal(myid,maxN,value)反馈给提案者， 以向提案者展示自己支持的提案意愿。其中第一个参数 myid 表示该提案的提案者标识 id，第二个参数表示其曾接受的提案的最大编号 maxN，第三个参数表示该提案的真正内容value。当然，若当前表决者还未曾 accept 过任何提议，则会将Proposal(null,null,null)反馈给提案者。
​ c) 在prepare 阶段 N 不可能等于 maxN。这是由 N 的生成机制决定的。要获得 N 的值， 其必定会在原来数值的基础上采用同步锁方式增一。

（2）accept 阶段

​ 1)当提案者(Proposer)发出 prepare(N)后，若收到了超过半数的表决者(Accepter)的反馈， 那么该提案者就会将其真正的提案 Proposal(myid,N,value)发送给所有的表决者。
​ 2)当表决者(Acceptor)接收到提案者发送的 Proposal(myid,N,value)提案后，会再次拿出自己曾经 accept 过的提议中的最大编号 maxN，或曾经记录下的 prepare 的最大编号，让 N 与它们进行比较，若 N 大于等于这两个编号，则当前表决者 accept 该提案，并反馈给提案者。若 N 小于这两个编号，则表决者采取不回应或回应 Error 的方式来拒绝该提议。
​ 3)若提案者没有接收到超过半数的表决者的 accept 反馈，则有两种可能的结果产生。一是放弃该提案，不再提出；二是重新进入 prepare 阶段，递增提案号，重新提出 prepare 请求。

（3）commit 阶段

​ 若提案者接收到的反馈数量超过了半数，则其会向外广播两类信息：
​ 1)向曾 accept 其提案的表决者发送“可执行数据同步信号”，即让它们执行其曾接收到的提案；
​ 2)向未曾向其发送 accept 反馈的表决者发送“提案 + 可执行数据同步信号”，即让它们接受到该提案后马上执行。

3.5 2PC 算法过程描述

​ 2PC 与 3PC 的区别是，在提案者接收到超过半数的表决者对于 parepare 阶段的反馈后，其会向所有表决者发送真正的提案 proposal。当表决者接受到 proposal 后就直接将其同步到了本地，不用再等待 commit 消息了。
​ 那么，为什么不直接使用 2PC，而要使用 3PC 呢？是因为 2PC 中存在着较多的弊端（这里就不再展开来说了）。所以很多 Paxos 工业实现使用的都是 3PC 提交。但 2PC 提交的效率要高于 3PC 提交，所以在保证不出问题的情况下，是可以使用 2PC 提交的。

3.6 Paxos 算法的活锁问题

​ 前面所述的Paxos 算法在实际工程应用过程中，根据不同的实际需求存在诸多不便之处， 所以也就出现了很多对于基本 Paxos 算法的优化算法，以对 Paxos 算法进行改进，例如，Multi Paxos、Fast Paxos、EPaxos。
​ 例如，Paxos 算法存在“活锁问题”，Fast Paxos 算法对 Paxos 算法进行了改进：只允许一个进程提交提案，即该进程具有对 N 的唯一操作权。该方式解决了“活锁”问题。

4 ZAB 协议

4.1 ZAB 协议简介

​ ZAB ，Zookeeper Atomic Broadcast，zk 原子消息广播协议，是专为 ZooKeeper 设计的一种支持崩溃恢复的原子广播协议，在 Zookeeper 中，主要依赖 ZAB 协议来实现分布式数据一致性。
​ Zookeeper 使用一个单一主进程来接收并处理客户端的所有事务请求，即写请求。当服务器数据的状态发生变更后，集群采用 ZAB 原子广播协议，以事务提案 Proposal 的形式广播到所有的副本进程上。ZAB 协议能够保证一个全局的变更序列，即可以为每一个事务分配一个全局的递增编号 xid。
​ 当 Zookeeper 客户端连接到 Zookeeper 集群的一个节点后，若客户端提交的是读请求， 那么当前节点就直接根据自己保存的数据对其进行响应；如果是写请求且当前节点不是Leader，那么节点就会将该写请求转发给 Leader，Leader 会以提案的方式广播该写操作，只要有超过半数节点同意该写操作，则该写操作请求就会被提交。然后 Leader 会再次广播给所有订阅者，即 Learner，通知它们同步数据。

02.png

4.2 ZAB 与 Paxos 的关系

​ ZAB 协议是 Paxos 算法的一种工业实现算法。但两者的设计目标不太一样。ZAB 协议主要用于构建一个高可用的分布式数据主从系统，即 Follower 是 Leader 的从机，Leader 挂了， 马上就可以选举出一个新的 Leader，但平时它们都对外提供服务。而 Fast Paxos 算法则是用于构建一个分布式一致性状态机系统，确保系统中各个节点的状态都是一致的。
​ 另外，ZAB 还使用 Google 的 Chubby 算法作为分布式锁的实现，而 Google 的 Chubby 也是 Paxos 算法的应用。
​ zk 集群对于事务请求的处理是 Fast Paxos 算法的体现，即只允许 Leader 提出提案。其属于 3PC 提交。
​ 但 Leader 选举是 Paxos 算法的体现，因为 Leader 宕机后，所有 Follower 均可提交提案， 它们在最初都是“我选我”。其属于 2PC 提交。

4.3 三类角色

​ 为了避免 Zookeeper 的单点问题，zk 也是以集群的形式出现的。zk 集群中的角色主要有以下三类：
​ Leader：zk 集群中事务请求的唯一处理者；其也可以处理读请求。
​ Follower：处理读请求；将事务请求转发给 Leader；对 Leader 发起的提案进行表决；同步 Leader 的事务处理结果；在 Leader 的选举过程中具有选举权与被选举权
​ Observer：不具有表决权，且在 Leader 选举过程中没有选举权与被选举权的 Follower。
​ Learner：学习者，同步者。Learner = Follower + Observer QuorumPeer = Participant = Leader + Follower

4.4 三个数据

​ 在 ZAB 中有三个很重要的数据：
​ zxid：64 位长度的Long 类型，其高 32 位为 epoch，低 32 位为 xid。
​ epoch：每一个新的Leader 都会有一个新的 epoch
​ xid：其为一个流水号

4.5 三种模式

​ ZAB 协议中对zkServer 的状态描述有三种模式。这三种模式并没有十分明显的界线，它们相互交织在一起。
​ 恢复模式：其包含两个重要阶段：Leader 的选举，与初始化同步
​ 广播模式：其可以分为两类：初始化广播，与更新广播
​ 同步模式：其可以分为两类：初始化同步，与更新同步

4.6 四种状态

​ zk 集群中的每一台主机，在不同的阶段会处于不同的状态。每一台主机具有四种状态。
​ LOOKING：选举状态
​ FOLLOWING：Follower 的正常工作状态
​ OBSERVING：Observer 的正常工作状态
​ LEADING：Leader 的正常工作状态

4.7 同步模式与广播模式

（1）初始化同步

​ 前面我们说过，恢复模式具有两个阶段：Leader 选举与初始化同步。当完成 Leader 选举后，此时的 Leader 还是一个准 Leader，其要经过初始化同步后才能变为真正的 Leader。

03.png

​ 具体过程如下：
​ 1) 为了保证 Leader 向 Learner 发送提案的有序，Leader 会为每一个 Learner 服务器准备一个队列
​ 2) Leader 将那些没有被各个 Learner 同步的事务封装为Proposal
​ 3) Leader 将这些 Proposal 逐条发给各个 Learner，并在每一个 Proposal 后都紧跟一个COMMIT 消息，表示该事务已经被提交，Learner 可以直接接收并执行
​ 4) Learner 接收来自于 Leader 的 Proposal，并将其更新到本地
​ 5) 当 Learner 更新成功后，会向准 Leader 发送 ACK 信息
​ 6) Leader 服务器在收到来自 Learner 的ACK 后就会将该 Learner 加入到真正可用的Follower 列表或 Observer 列表。没有反馈 ACK，或反馈了但 Leader 没有收到的 Learner，Leader 不会将其加入到相应列表。

（2）消息广播算法

04.png

​ 当集群中的 Learner 完成了初始化状态同步，那么整个 zk 集群就进入到了正常工作模式了。
​ 如果集群中的 Learner 节点收到客户端的事务请求，那么这些 Learner 会将请求转发给Leader 服务器。然后再执行如下的具体过程：
​ 1) Leader 接收到事务请求后，为事务赋予一个全局唯一的 64 位自增 id，即 zxid，通过zxid 的大小比较即可实现事务的有序性管理，然后将事务封装为一个 Proposal。
​ 2) Leader 根据 Follower 列表获取到所有 Follower，然后再将 Proposal 通过这些 Follower 的队列将提案发送给各个 Follower。
​ 3) 当 Follower 接收到提案后，会先将提案的 zxid 与本地记录的事务日志中的最大的zxid 进行比较。若当前提案的 zxid 大于最大zxid，则将当前提案记录到本地事务日志中，并向 Leader 返回一个 ACK。（提问学员）
​ 4) 当 Leader 接收到过半的 ACKs 后，Leader 就会向所有 Follower 的队列发送 COMMIT
消息，向所有 Observer 的队列发送 Proposal。
​ 5) 当 Follower 收到 COMMIT 消息后，就会将事务正式更新到本地。当 Observer 收到
Proposal 后，会直接将事务更新到本地。
​ 6) 无论是 Follower 还是 Observer，在同步完成后都需要向 Leader 发送成功 ACK。

（3）Observer 的数量问题

​ Observer 数量并不是越多越好，一般与 Follower 数量相同。因为 Observer 数量的增多虽不会增加事务操作压力，但其需要从 Leader 同步数据，Observer 同步数据的时间是小于等于 Follower 同步数据的时间的。当 Follower 同步数据完成，Leader 的 Observer 列表中的Observer 主机将结束同步。那些完成同步的 Observer 将会进入到另一个对外提供服务的列表。那么，那些没有同步了数据无法提供服务的 Observer 主机就形成了资源浪费。
​ 所以，对于事务操作发生频繁的系统，不建议使用过多的 Observer。

Leader 中保存的 Observer 列表其实有两个：
​ all：包含所有 Observer。
​ service：已经完成了从 Leader 同步数据的任务。service <= all。其是动态的。
Leader 中保存的 Follower 列表其实也有两个：
​ all：要求其中必须有过半的 Follower 向Leader 反馈ACK
service：

4.8 Leader 选举

​ 在集群启动过程中，或 Leader 宕机后，集群就进入了恢复模式。恢复模式中最重要的阶段就是 Leader 选举。

（1）Leader 选举中的基本概念

​ A、serverId
​ 这是zk 集群中服务器的唯一标识，也称为 sid，其实质就是 zk 中配置的 myid。例如， 有三个 zk 服务器，那么编号分别是 1,2,3。
​ B、 逻辑时钟
​ 逻辑时钟，Logicalclock，是一个整型数，该概念在选举时称为 logicalclock，而在选举结束后称为epoch。即 epoch 与 logicalclock 是同一个值，在不同情况下的不同名称。

（2）Leader 选举算法

​ 在集群启动过程中的 Leader 选举过程（算法）与 Leader 断连后的 Leader 选举过程稍微有一些区别，基本相同。
A、集群启动中的 Leader 选举

05.png

​ 若进行 Leader 选举，则至少需要两台主机，这里以三台主机组成的集群为例。
​ 在集群初始化阶段，当第一台服务器 Server1 启动时，其会给自己投票，然后发布自己的投票结果。投票包含所推举的服务器的 myid 和 ZXID，使用(myid, ZXID)来表示，此时 Server1的投票为(1, 0)。由于其它机器还没有启动所以它收不到反馈信息，Server1 的状态一直属于Looking，即属于非服务状态。
​ 当第二台服务器 Server2 启动时，此时两台机器可以相互通信，每台机器都试图找到
Leader，选举过程如下：
​ (1) 每个 Server 发出一个投票。此时 Server1 的投票为(1, 0)，Server2 的投票为(2, 0)，然后各自将这个投票发给集群中其他机器。
​ (2) 接受来自各个服务器的投票。集群的每个服务器收到投票后，首先判断该投票的有效性，如检查是否是本轮投票、是否来自 LOOKING 状态的服务器。
​ (3) 处理投票。针对每一个投票，服务器都需要将别人的投票和自己的投票进行 PK，PK
规则如下：
​ 优先检查 ZXID。ZXID 比较大的服务器优先作为 Leader。
​ 如果 ZXID 相同，那么就比较 myid。myid 较大的服务器作为 Leader 服务器。
​ 对于 Server1 而言，它的投票是(1, 0)，接收 Server2 的投票为(2, 0)。其首先会比较两者的 ZXID，均为 0，再比较 myid，此时 Server2 的 myid 最大，于是 Server1 更新自己的投票为(2, 0)，然后重新投票。对于 Server2 而言，其无须更新自己的投票，只是再次向集群中所有主机发出上一次投票信息即可。
​ (4) 统计投票。每次投票后，服务器都会统计投票信息，判断是否已经有过半机器接受到相同的投票信息。对于 Server1、Server2 而言，都统计出集群中已经有两台主机接受了(2, 0)的投票信息，此时便认为已经选出了新的 Leader，即 Server2。
(5) 改变服务器状态。一旦确定了 Leader，每个服务器就会更新自己的状态，如果是Follower，那么就变更为 FOLLOWING，如果是 Leader，就变更为 LEADING。
(6) 添加主机。在新的 Leader 选举出来后 Server3 启动，其想发出新一轮的选举。但由于当前集群中各个主机的状态并不是 LOOKING，而是各司其职的正常服务，所以其只能是以Follower 的身份加入到集群中。

B、 宕机后的 Leader 选举
在 Zookeeper 运行期间，Leader 与非 Leader 服务器各司其职，即便当有非 Leader 服务器宕机或新加入时也不会影响 Leader。但是若 Leader 服务器挂了，那么整个集群将暂停对外服务，进入新一轮的 Leader 选举，其过程和启动时期的 Leader 选举过程基本一致。

06.png
假设正在运行的有 Server1、Server2、Server3 三台服务器，当前 Leader 是 Server2，若某一时刻 Server2 挂了，此时便开始新一轮的 Leader 选举了。选举过程如下：
(1) 变更状态。Leader 挂后，余下的非 Observer 服务器都会将自己的服务器状态由
FOLLOWING 变更为 LOOKING，然后开始进入 Leader 选举过程。
(2) 每个 Server 会发出一个投票，仍然会首先投自己。不过，在运行期间每个服务器上的 ZXID 可能是不同，此时假定 Server1 的 ZXID 为 111，Server3 的 ZXID 为 333；在第一轮投票中，Server1 和 Server3 都会投自己，产生投票(1, 111)，(3, 333)，然后各自将投票发送给集群中所有机器。
(3) 接收来自各个服务器的投票。与启动时过程相同。集群的每个服务器收到投票后，首先判断该投票的有效性，如检查是否是本轮投票、是否来自 LOOKING 状态的服务器。
(4) 处理投票。与启动时过程相同。针对每一个投票，服务器都需要将别人的投票和自己的投票进行 PK。对于 Server1 而言，它的投票是(1, 111)，接收 Server3 的投票为(3, 333)。其首先会比较两者的 ZXID，Server3 投票的 zxid 为 333 大于 Server1 投票的 zxid 的 111，于是Server1 更新自己的投票为(3, 333)，然后重新投票。对于 Server3 而言，其无须更新自己的投票，只是再次向集群中所有主机发出上一次投票信息即可。
(5) 统计投票。与启动时过程相同。对于 Server1、Server2 而言，都统计出集群中已经有两台主机接受了(3, 333)的投票信息，此时便认为已经选出了新的 Leader，即 Server3。
(6) 改变服务器的状态。与启动时过程相同。一旦确定了 Leader，每个服务器就会更新自己的状态。Server1 变更为 FOLLOWING，Server3 变更为 LEADING。

4.9 恢复模式的三个原则

​ 当集群正在启动过程中，或 Leader 崩溃后，集群就进入了恢复模式。对于要恢复的数据状态需要遵循三个原则。

（1）Leader 的主动出让原则

​ 若集群中 Leader 收到的 Follower 心跳数量没有过半，此时 Leader 会自认为自己与集群的连接已经出现了问题，其会主动修改自己的状态为 LOOKING，去查找新的 Leader。
​ 而其它 Server 由于有过半的主机认为已经丢失了 Leader，所以它们会发起新的 Leader选举，选出一个新的 Leader。

（2）已被处理的消息不能丢

​ 正常情况下，当 Leader 收到超过半数 Follower 的 ACKs 后，就向各个 Follower 广播COMMIT 消息，批准各个Server 执行该写操作事务。当各个Server 在接收到Leader 的COMMIT 消息后就会在本地执行该写操作，然后会向客户端响应写操作成功。
​ 但是如果在非全部 Follower 收到 COMMIT 消息之前 Leader 就挂了，这将导致一种后果：部分 Server 已经执行了该事务，而部分 Server 尚未收到 COMMIT 消息，所以其并没有执行该事务。当新的 Leader 被选举出，集群经过恢复模式后需要保证所有 Server 上都执行了那些已经被部分 Server 执行过的事务。

（3）被丢弃的消息不能再现

​ 当在 Leader 新事务已经通过，其已经将该事务更新到了本地，但所有 Follower 还都没有收到 COMMIT 之前，Leader 宕机了，此时，所有 Follower 根本就不知道该 Proposal 的存在。当新的 Leader 选举出来，整个集群进入正常服务状态后，之前挂了的 Leader 主机重新启动并注册成为了 Follower。若那个别人根本不知道的 Proposal 还保留在那个主机，那么其数据就会比其它主机多出了内容，导致整个系统状态的不一致。所以，该 Proposa 应该被丢弃。类似这样应该被丢弃的事务，是不能再次出现在集群中的，应该被清除。

5 高可用集群的容灾

5.1 服务器数量的奇数与偶数

​ 前面我们说过，无论是写操作投票，还是 Leader 选举投票，都必须过半才能通过，也就是说若出现超过半数的主机宕机，则投票永远无法通过。基于该理论，由 5 台主机构成的集群，最多只允许 2 台宕机。而由 6 台构成的集群，其最多也只允许 2 台宕机。即，6 台与5 台的容灾能力是相同的。基于此容灾能力的原因，建议使用奇数台主机构成集群，以避免资源浪费。
​ 但从系统吞吐量上说，6 台主机的性能一定是高于 5 台的。所以使用 6 台主机并不是资源浪费。

5.2 容灾设计方案

​ 对于一个高可用的系统，除了要设置多台主机部署为一个集群避免单点问题外，还需要考虑将集群部署在多个机房、多个楼宇。对于多个机房、楼宇中集群也是不能随意部署的， 下面就多个机房的部署进行分析。
​ 在多机房部署设计中，要充分考虑“过半原则”，也就是说，尽量要确保 zk 集群中有过半的机器能够正常运行。

（1）三机房部署

​ 在生产环境下，三机房部署是最常见的、容灾性最好的部署方案。三机房部署中要求每个机房中的主机数量必须少于集群总数的一半。

（2）双机房部署

​ zk 官方没有给出较好的双机房部署的容灾方案。只能是让其中一个机房占有超过半数的主机，使其做为主机房，而另一机房少于半数。当然，若主机房出现问题，则整个集群会瘫痪。

6 CAP 定理

6.1 简介

​ CAP 定理又称 CAP 原则，指的是在一个分布式系统中，Consistency（一致性）、Availability（可用性）、Partition tolerance（分区容错性），三者不可兼得。
​ 一致性（C）：分布式系统中多个主机之间是否能够保持数据一致的特性。即，当系统数据发生更新操作后，各个主机中的数据仍然处于一致的状态。
​ 可用性（A）：系统提供的服务是否一直处于可用的状态，即对于用户的每一个请求，系统是否总是可以在有限的时间内对用户做出响应。
​ 分区容错性（P）：分布式系统在遇到任何网络分区故障时，仍能够保证对外提供满足一致性和可用性的服务。
​ 分区是网络分区。
​ 对于分布式系统，网络环境相对是不可控的，出现网络分区是不可避免的，因此系统必须具备分区容错性。但其并不能同时保证一致性与可用性。CAP 原则对于一个分布式系统来说，只可能满足两项，即要么 CP，要么 AP。

6.2 BASE 理论

​ BASE 是Basically Available（基本可用）、Soft state（软状态）和 Eventually consistent（最终一致性）三个短语的简写。
​ BASE 理论的核心思想是：即使无法做到实时一致性，但每个系统都可以根据自身的业务特点，采用适当的方式来使系统达到最终一致性。

（1）基本可用

​ 基本可用是指分布式系统在出现不可预知故障的时候，允许损失部分可用性。
损失响应时间：
损失功能：

（2）软状态

​ 软状态，是指允许系统数据存在的中间状态，并认为该中间状态的存在不会影响系统的整体可用性，即允许系统主机间进行数据同步的过程存在一定延时。软状态，其实就是一种灰度状态，过渡状态。

（3）最终一致性

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

（4）总结

​ 从达到一致性的时间角度来划分，可以分为：
​ 实时一致性：单机情况下可以实现实时一致性
​ 最终一致性：经过一段时间后可以达到一致性

​ 单从客户端访问到的内容角度来划分，可以分为：
​ 强一致性（严格一致性）：
​ 弱一致性：允许客户端访问不到部分或全部更新过的数据。

6.3 ZK 与 CP

​ zk 遵循的是 CP 原则，即保证了一致性，但牺牲了可用性。体现在哪里呢？
​ 当 Leader 宕机后，zk 集群会马上进行新的 Leader 的选举。但选举时长一般在 200 毫秒内，最长不超过 60 秒，整个选举期间 zk 集群是不接受客户端的读写操作的，即 zk 集群是处于瘫痪状态的。所以，其不满足可用性。

6.4 zk 可能会存在脑裂

​ 这里说的zk 可能会引发脑裂，是指的在多机房部署中，若出现了网络连接问题，形成多个分区，则可能会出现脑裂问题，可能会导致数据不一致。
（1）情况一

07.png

（2）情况二

08.png
（3）情况三
09.png
（4）情况四
10.png

（5）情况五

11.png