Zookeeper理论基础

来源：99网

1、Zookeeper简介

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

2、Zookeeper的一致性

特点：

顺序一致性
从同一个客户端发起的多个事务请求（写操作请求），最终会被严格按照发起顺序记录到 zk 中。
原子性
所有事务请求的结果在集群中所有主机上的应用结果都是一致的。要么都应用成功，要么都失败。
单一视图
无论 Client 连接的是 zk 集群中的哪台主机，其看到的数据模型都是一致的。
可靠性
一旦 zk 主机成功应用了某个事务，则其所引发的服务器状态变化会被一直保留下来，直到另一个事务将其改变。
最终一致性
一旦一个事务被成功应用，zk 可以保证在一段很短的时间后，客户端最终可以从任意的 zk 主机上读取到最新的数据。但不能保证实时读到。

3、Paxos 算法

Paxos 算法是莱斯利·兰伯特(Leslie Lamport)1990 年提出的一种基于消息传递的、具有高容错性的一致性算法。

Paxos 算法是一种公认的晦涩难懂的算法，并且工程实现上也具有很大难度。较有名的 Paxos 工程实现有 Google Chubby、ZAB、微信的 PhxPaxos 等。

3.1、Paxos 与拜占庭将军问题

拜占庭将军问题是由 Paxos 算法作者莱斯利·兰伯特提出的点对点通信中的基本问题。该问题要说明的含义是，在不可靠信道上试图通过消息传递的方式达到一致性是不可能的。所以，Paxos 算法的前提是不存在拜占庭将军问题，即信道是安全的、可靠的，集群节点间传递的消息是不会被篡改的。

一般情况下，分布式系统中各个节点间采用两种通讯模型：共享内存（Shared Memory）、消息传递（Messages Passing）。而 Paxos 是基于消息传递通讯模型的。

3.2、算法描述

3.2.1、三种角色

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

Proposer（提议者）:提出提案 (Proposal)，其中包括提案编号 (Proposal ID) 和提议的值 (Value)。
Acceptor（决策者）:参与决策，审批Proposers的提案，收到Proposal后对其进行选择，若Proposal获得多数Acceptors的接受，则称该Proposal被批准。
Learner（最终决策学习者）:不参与决策，从Proposers/Acceptors学习最新达成一致的提案和被批准的值(Value) ，在一个Paxos算法实例中，只会批准一个Value。

3.2.2、 Paxos 算法的一致性

每个提案者在提出提案时都会首先获取到一个具有全局唯一性的、递增的提案编号 N，即在整个集群中是唯一的编号 N，然后将该编号赋予其要提出的提案。
每个表决者在 accept 某提案后，会将该提案的编号 N 记录在本地，这样每个表决者中保存的已经被 accept 的提案中会存在一个编号最大的提案，其编号假设为 maxN。每个表决者仅会 accept 编号大于自己本地 maxN 的提案。
在众多提案中最终只能有一个提案被选定。
一旦一个提案被选定，则其它服务器会主动同步(Learn)该提案到本地。
没有提案被提出则不会有提案被选定。

3.2.3、算法过程描述

Paxos 算法的执行过程划分为两个阶段：准备阶段 prepare 与接受阶段 accept。
A、prepare 阶段 ：
Acceptors接收请求、产生判断、并向对应的Proposer返回承诺，Proposer依据返回的承诺决定是否继续更新数据而进入下一阶段的请求：

B、accept 阶段
Acceptors接受更新请求并完成多副本更新：

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

3.2.3、Paxos算法中决议的传播

区别于一般选举逻辑，Paxos算法中每个Proposer不是执着于让自己的提议通过，而是要让提议尽快达成一致意见。例如，存在两个提议者PA和PB，如果PA在询问时发现某个Acceptor已经接受过先于其进行询问的PB的提议，即PA询问得到的是Acceptor对PB的诺言，这时PA会把自己的提议改为PB的提议。

基于上述示例可能存在一种情况是，PA收到了其发出提议的法定集合中多个Acceptor的返回意见，且这些返回意见中存在多个接受者对于其他提议者的诺言。这时，PA需要处理接受与拒绝的问题，要在它们之间做出选择，当PA收到接受者的诺言是，一般接受者会告知已承诺的提案和该被接受提案的ID编号两项信息，PA基于此选择ID编号较大的诺言作为自己的提案。

3.2.4、Paxos 算法的活锁问题

Proposal编号除了在产生过程中存在问题，在其更新过程中也有需要解决的冲突。当某Proposer提交的Proposal被拒绝时，可能存在因为Acceptor承诺返回了更大编号的Proposal，该Proposer提高Proposal编号继续提交的情况。一旦出现这种情况，两个Proposer都发现自己的编号过低转而提出更高编号的Proposal，显而易见。这会导致死循环，该现象被称为活锁。用一句通俗的话来描述活锁现象：你编号高，我再比你更高，反复如此，算法永远无法结束。

Paxos算法中给出的解决活锁的办法是选举出一个Proposer作Leader，所有的Proposal都通过Leader来提交，当Leader宕机时马上再选举其他的Leader。通过Leader选举相当于把一个分布式问题转化为一个单点问题，而单点的正确性和健壮性由选举机制保证。Leader通过控制提交的进度来解决活锁现象：如果之前的Proposal还没有结果，之后的Proposal就稍微等待，而不是急于提高编号再次提交。

Paxos算法在实际工程应用过程中，根据不同的实际需求存在诸多不便之处，所以也就出现了很多对于基本 Paxos 算法的优化算法，以对 Paxos 算法进行改进，例如，Multi Paxos、Fast Paxos、EPaxos。

例如，Paxos 算法存在“活锁问题”，Fast Paxos 算法对 Paxos 算法进行了改进：只允许一个进程提交提案，即该进程具有对 N 的唯一操作权。该方式解决了“活锁”问题。

4、ZAB 协议

ZAB（Zookeeper Atomic Broadcast）：zk 原子消息广播协议，是专为 ZooKeeper 设计的一种支持崩溃恢复的原子广播协议。在 Zookeeper 中，主要依赖 ZAB 协议来实现分布式数据一致性。

Zookeeper 使用一个单一主进程来接收并处理客户端的所有事务请求，即写请求。当服务器数据的状态发生变更后，集群采用 ZAB 原子广播协议，以事务提案 Proposal 的形式广播到所有的副本进程上。ZAB 协议能够保证一个全局的变更序列，即可以为每一个事务分配一个全局的递增编号 xid。

当 Zookeeper 客户端连接到 Zookeeper 集群的一个节点后，若客户端提交的是读请求，那么当前节点就直接根据自己保存的数据对其进行响应；如果是写请求且当前节点不是Leader，那么节点就会将该写请求转发给 Leader，Leader 会以提案的方式广播该写操作，只要有超过半数节点同意该写操作，则该写操作请求就会被提交。然后 Leader 会再次广播给所有订阅者，即 Learner，通知它们同步数据。

4.1、 ZAB 与 Paxos 的关系

ZAB 协议是 Paxos 算法的一种工业实现算法。但两者的设计目标不太一样。ZAB 协议主要用于构建一个高可用的分布式数据主从系统，即 Follower 是 Leader 的从机，Leader 挂了，马上就可以选举出一个新的 Leader，但平时它们都对外提供服务。而 Fast Paxos 算法则是用于构建一个分布式一致性状态机系统，确保系统中各个节点的状态都是一致的。

另外，ZAB 还使用 Google 的 Chubby 算法作为分布式锁的实现，而 Google 的 Chubby 也是 Paxos 算法的应用。

4.2、三类角色

为了避免 Zookeeper 的单点问题，zk 也是以集群的形式出现的。zk 集群中的角色主要有以下三类：

Leader：接收和处理客户端的读请求；zk 集群中事务请求的唯一处理者，并负责发起决议和投票，然后将通过的事务请求在本地进行处理后，将处理结果同步给集群中的其它主机。
Follower：接收和处理客户端的读请求; 将事务请求转给 Leader；同步 Leader 中的数据；当 Leader 挂了，参与 Leader 的选举（具有选举权与被选举权）。
Observer：就是没有选举权与被选举权，且没有投票权的 Follower（临时工）。若 zk 集群中的读压力很大，则需要增加 Observer，最好不要增加 Follower。因为增加 Follower将会增大投票与统计选票的压力，降低写操作效率，及 Leader 选举的效率。

这三类角色在不同的情况下又有一些不同的名称：
Learner = Follower + Observer
QuorumServer = Follower + Leader

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

Leader 中对于 Observer 存在两个列表：all（包含所有 Observer 主机）、service（每发生一次事务更新，service 列表就会发生一次变化）。
service <= all {all – service} 心跳
Leader 中对于 Follower 也存在两个列表：all（包含所有 Follower 主机）、service（每发生一次事务更新，service 列表就会发生一次变化）。
若 service <= all/2 ，则说明同步失败，则 Leader 重新广播，Follower 重新同步。
{all – service}

4.3、三个数据

zxid：是一个位长度的 Long 类型。其中高 32 位表示 epoch，低 32 表示 xid。
epoch：每个 Leader 都会具有一个不同的 epoch，用于区分不同的时期。
xid：事务 id，是一个流水号

4.4、三种模式

ZAB 协议中对 zkServer 的状态描述有三种模式。这三种模式并没有十分明显的界线，它们相互交织在一起。

恢复模式：当集群启动时，或 Leader 挂了，系统需要进入恢复模式，以恢复系统对外提供服务的能力。其中包含两个很重要的阶段：Leader 的选举与初始化同步。
广播模式：分为两类，初始化广播与更新广播。
同步模式：分为两类，初始化同步与更新同步。

4.5、四种状态

zk 集群中的每一台主机，在不同的阶段会处于不同的状态。每一台主机具有四种状态。

LOOKING：选举状态
LEADING：Leader 的正常工作状态，Leader 广播数据更新的状态
FOLLOWING：Follower 的正常工作状态，从 Leader 同步数据的状态
OBSERVING：Observer 的正常工作状态，从 Leader 同步数据的状态

4.6、同步模式与广播模式

初始化同步

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

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

消息广播算法

Leader 接收到事务请求后，为事务赋予一个全局唯一的位自增 id，即 zxid，通过zxid 的大小比较即可实现事务的有序性管理，然后将事务封装为一个 Proposal。
Leader 根据 Follower 列表获取到所有 Follower，然后再将 Proposal 通过这些 Follower 的队列将提案发送给各个 Follower。
当 Follower 接收到提案后，会先将提案的 zxid 与本地记录的事务日志中的最大的 zxid进行比较。若当前提案的 zxid 大于最大 zxid，则将当前提案记录到本地事务日志中，并向 Leader 返回一个 ACK。
当 Leader 接收到过半的 ACK 后，Leader 就会向所有 Follower 的队列发送 COMMIT消息，向所有 Observer 的队列发送 Proposal。
当 Follower 收到 COMMIT 消息后，就会将日志中的事务正式更新到本地。当 Observer收到 Proposal 后，会直接将事务更新到本地。
无论是 Follower 还是 Observer，在同步完成后都需要向 Leader 发送成功 ACK。

4.7、恢复模式的两个原则

当集群正在启动过程中，或 Leader 与超过半数的主机断连后，集群就进入了恢复模式。
对于要恢复的数据状态需要遵循两个原则：

已被处理过的消息不能丢
当 Leader 收到超过半数 Follower 的 ACKs 后，就向各个 Follower 广播 COMMIT 消息，批准各个 Server 执行该写操作事务。当各个 Server 在接收到 Leader 的 COMMIT 消息后就会在本地执行该写操作，然后会向客户端响应写操作成功。
但是如果在非全部 Follower 收到 COMMIT 消息之前 Leader 就挂了，这将导致一种后果：部分 Server 已经执行了该事务，而部分 Server 尚未收到 COMMIT 消息，所以其并没有执行该事务。当新的 Leader 被选举出，集群经过恢复模式后需要保证所有 Server 上都执行了那些已经被部分 Server 执行过的事务。
被丢弃的消息不能再现
当在 Leader 新事务已经通过，其已经将该事务更新到了本地，但所有 Follower 还都没有收到 COMMIT 之前，Leader 宕机了，此时，所有 Follower 根本就不知道该 Proposal 的存在。当新的 Leader 选举出来，整个集群进入正常服务状态后，之前挂了的 Leader 主机重新启动并注册成为了 Follower。若那个别人根本不知道的 Proposal 还保留在那个主机，那么其数据就会比其它主机多出了内容，导致整个系统状态的不一致。所以，该 Proposa 应该被丢弃。类似这样应该被丢弃的事务，是不能再次出现在集群中的，应该被清除。

4.8、Leader 选举

恢复模式中最重要的阶段就是 Leader 选举。

myid
这是 zk 集群中服务器的唯一标识，称为 myid。例如，有三个 zk 服务器，那么编号分别是 1,2,3。
逻辑时钟
逻辑时钟，Logicalclock，是一个整型数，该概念在选举时称为 logicalclock，而在选举结束后称为 epoch。即 epoch 与 logicalclock 是同一个值，在不同情况下的不同名称。
zk 状态
zk 集群中的每一台主机，在不同的阶段会处于不同的状态。每一台主机具有四种状态。
LOOKING
FOLLOWING
OBSERVING
LEADING

4.8.1、 Leader 选举算法

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

集群启动中的 Leader 选举
若进行 Leader 选举，则至少需要两台主机，这里以三台主机组成的集群为例。

当第二台服务器 Server2 启动时，此时两台机器可以相互通信，每台机器都试图找到Leader，选举过程如下：

每个 Server 发出一个投票。此时 Server1 的投票为(1, 0)，Server2 的投票为(2, 0)，然后各自将这个投票发给集群中其他机器。
接受来自各个服务器的投票。集群的每个服务器收到投票后，首先判断该投票的有效性，如检查是否是本轮投票、是否来自 LOOKING 状态的服务器。
处理投票。针对每一个投票，服务器都需要将别人的投票和自己的投票进行 PK，PK规则如下：

优先检查 ZXID。ZXID 比较大的服务器优先作为 Leader。
如果 ZXID 相同，那么就比较 myid。myid 较大的服务器作为 Leader 服务器。
对于 Server1 而言，它的投票是(1, 0)，接收 Server2 的投票为(2, 0)。其首先会比较两者
的 ZXID，均为 0，再比较 myid，此时 Server2 的 myid 最大，于是 Server1 更新自己的投票为
(2, 0)，然后重新投票。对于 Server2 而言，其无须更新自己的投票，只是再次向集群中所有
主机发出上一次投票信息即可。

统计投票。每次投票后，服务器都会统计投票信息，判断是否已经有过半机器接受到
相同的投票信息。对于 Server1、Server2 而言，都统计出集群中已经有两台主机接受了(2, 0)
的投票信息，此时便认为已经选出了新的 Leader，即 Server2。
改变服务器状态。一旦确定了 Leader，每个服务器就会更新自己的状态，如果是
Follower，那么就变更为 FOLLOWING，如果是 Leader，就变更为 LEADING。
添加主机。在新的 Leader 选举出来后 Server3 启动，其想发出新一轮的选举。但由于
当前集群中各个主机的状态并不是 LOOKING，而是各司其职的正常服务，所以其只能是以
Follower 的身份加入到集群中。
宕机后的 Leader 选举
在 Zookeeper 运行期间，Leader 与非 Leader 服务器各司其职，即便当有非 Leader 服务器宕机或新加入时也不会影响 Leader。但是若 Leader 服务器挂了，那么整个集群将暂停对外服务，进入新一轮的 Leader 选举，其过程和启动时期的 Leader 选举过程基本一致。

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

5、CAP 定理

CAP 原则又称 CAP 定理，指的是在一个分布式系统中，Consistency（一致性）、Availability（可用性）、Partition tolerance（分区容错性），三者不可兼得。

一致性（C）：分布式系统中多个主机之间是否能够保持数据一致的特性。即，当系统数据发生更新操作后，各个主机中的数据仍然处于一致的状态。
可用性（A）：系统提供的服务必须一直处于可用的状态，即对于用户的每一个请求，系统总是可以在有限的时间内对用户做出响应。
分区容错性（P）：分布式系统在遇到任何网络分区故障时，仍能够保证对外提供满足一致性和可用性的服务。

对于分布式系统，网络环境相对是不可控的，出现网络分区是不可避免的，因此系统必须具备分区容错性。但其并不能同时保证一致性与可用性。

CAP 原则对于一个分布式系统来说，只可能满足两项，即要么 CP，要么 AP。

5.1、BASE 理论

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

基本可用：
基本可用是指分布式系统在出现不可预知故障的时候，允许损失部分可用性。
软状态：
是指允许系统数据存在的中间状态，并认为该中间状态的存在不会影响系统的整体可用性，即允许系统主机间进行数据同步的过程存在一定延时。
软状态，其实就是一种灰度状态，过渡状态。
最终一致性：
需要系统保证最终数据能够达到一致，而不需要实时保证系统数据的强一致性

5.2、ZK 与 CP

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

5.3、zk 可能会存在脑裂

在多机房部署中，若出现了网络连接问题，形成多个分区，则可能会出现脑裂问题，可能会导致数据不一致。

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文