zookeeper之深入理解其原理

1 zookeeper基础

1.1 基本了解

• zookeeper是一个类似hdfs的树形文件结构， zookeeper可以用来保证数据在(zk)集群之间的数据的事务性一致
• 分布、开源的应用程序协调服务,它是集群的管理者,监视着集群中各个节点的状态，根据节点的反馈进行下一步合理操作。最终，将简单易用的接口和性能高效、功能稳定的系统提供给用户。
• 主要解决分布式应用经常遇到的数据管理问题,如：统一命名服务、状态同步服务、集群管理、分布式应用配置项的管理等。
• Zookeeper 作为 Hadoop 项目中的一个子项目，是 Hadoop 集群管理的一个必不可少的模块，它主要用来控制集群中的数据，如它管理 Hadoop 集群中的 NameNode，还有 Hbase 中 Master Election、Server 之间状态同步等

1.2 角色与功能

1.2.1 角色

1.2.1.1 三种角色

• 领导者（leader），负责进行投票的发起和决议，更新系统状态
• 学习者（learner），包括跟随者（follower）和观察者（observer）
  follower用于接受客户端请求并想客户端返回结果，在选主过程中参与投票
Observer可以接受客户端连接，将写请求转发给leader，但observer不参加投票过程，只同步leader的状态
  observer的目的是为了扩展系统，提高读取速度
• 客户端（client）请求发起方：
  

1.2.1.2 为什么引入Observer

• Zookeeper需保证高可用和强一致性，为了支持更多的客户端，需要增加更多Server；
  Server增多，投票阶段延迟增大，影响性能；权衡伸缩性和高吞吐率，引入Observer
• Observer不参与投票；
• Observers接受客户端的连接，并将写请求转发给leader节点；
• 加入更多Observer节点，提高伸缩性，同时不影响吞吐率

1.2.2 角色的功能

• Leader主要功能：恢复数据、维持与Follower的心跳；接收Follower请求并判断Follower的请求消息类型
  Leader的消息类型主要有PING消息、REQUEST消息、ACK消息、REVALIDATE消息，根据不同的消息类型，进行不同的处理。
• Follower主要功能：向Leader发送请求（PING消息、REQUEST消息、ACK消息、REVALIDATE消息）；接收Leader消息并进行处理；接收Client的请求，如果为写请求，发送给Leader进行投票；返回Client结果

不同的消息类型：

• PING消息是指Leader的心跳信息；
• PROPOSAL消息：Leader发起的提案，要求Follower投票；
• COMMIT消息：服务器端最新一次提案的信息；
• REQUEST消息是Follower发送的提议信息，包括写请求及同步请求
• ACK消息是Follower的对提议的回复，超过半数的Follower通过，则commit该提议
• REVALIDATE消息是用来延长SESSION有效时间。
• UPTODATE消息：表明同步完成；
• SYNC消息：返回SYNC结果到客户端，这个消息最初由客户端发起，用来强制得到最新的更新。

1.3 zookeeper提供了什么

1.3.1 文件系统

Zookeeper提供一个多层级的节点命名空间（节点称为znode）。
与文件系统不同的是，这些节点都可以设置关联的数据，而文件系统中只有文件节点可以存放数据而目录节点不行。
Zookeeper为了保证高吞吐和低延迟，在内存中维护了这个树状的目录结构，这种特性使得Zookeeper不能用于存放大量的数据，每个节点的存放数据上限为1M

Znode分为四种类型：

• PERSISTENT：持久化目录节点（客户端与zookeeper断开连接后，该节点依旧存在）
  可以创建子节点，子节点可以临时也可以持久；不能同名
• PERSISTENT_SEQUENTIAL：持久化顺序编号目录节点。（客户端与zookeeper断开连接后，该节点依旧存在，只是Zookeeper给该节点名称进行顺序编号）
  可以创建子节点，子节点可以临时也可以持久；同名节点会在后面添加上序号
• EPHEMERAL：临时目录节点（客户端与zookeeper断开连接后，该节点被删除）
  不能创建子节点；不能同名
• EPHEMERAL_SEQUENTIAL：临时顺序编号目录节点（客户端与zookeeper断开连接后，该节点被删除，只是Zookeeper给该节点名称进行顺序编号）
  不能创建子节点；同名节点会在后面添加上序号（分布式锁使用的好处）

1.4 Zookeeper的核心及原理

1.4.1 zookeeper特性

• 一致性：client不论连接到哪个Server，展示给它都是同一个视图，这是zookeeper最重要的性能。
• 可靠性：具有简单、健壮、良好的性能，如果消息m被到一台服务器接受，那么它将被所有的服务器接受。
• 实时性：Zookeeper保证客户端将在一个时间间隔范围内获得服务器的更新信息，或者服务器失效的信息。但由于网络延时等原因，Zookeeper不能保证两个客户端能同时得到刚更新的数据，如果需要最新数据，应该在读数据之前调用sync()接口。
• 等待无关（wait-free）：慢的或者失效的client不得干预快速的client的请求，使得每个client都能有效的等待。
• 原子性：更新只能成功或者失败，没有中间状态。
• 顺序性：包括全局有序和偏序两种：全局有序是指如果在一台服务器上消息a在消息b前发布，则在所有Server上消息a都将在消息b前被发布；偏序是指如果一个消息b在消息a后被同一个发送者发布，a必将排在b前面。

1.4.2 zookeeper原理

Zookeeper的核心是原子广播，这个机制保证了各个Server之间的同步。实现这个机制的协议叫做Zab协议。
Zab协议有两种模式，它们分别是恢复模式（选主）和广播模式（同步）：

• 当服务启动或者在领导者崩溃后，Zab就进入了恢复模式，当领导者被选举出来，且大多数Server完成了和leader的状态同步以后，恢复模式就结束了。状态同步保证了leader和Server具有相同的系统状态。
• 消息广播模式：在ZooKeeper中所有的事务请求都由一个主服务器也就是Leader来处理，其他服务器为Follower，Leader将客户端的事务请求转换为事务Proposal，并且将Proposal分发给集群中其他所有的Follower，然后Leader等待Follwer反馈，当有过半数（>=N/2+1）的Follower反馈信息后，Leader将再次向集群内Follower广播Commit信息，Commit为将之前的Proposal提交。

广播模式需要保证proposal被按顺序处理，为了保证事务的顺序一致性，zookeeper采用了递增的事务id号（zxid）来标识事务。所有的提议（proposal）都在被提出的时候加上了zxid。zxid是一个64位的数字，它高32位是epoch用来标识 leader关系是否改变，每次一个leader被选出来，它都会有一个新的epoch，标识当前属于那个leader的统治时期。低32位用于递增计数。

一旦leader已经和多数的follower进行了状态同步后，他就可以开始广播消息了，即进入广播状态。这时候当一个server加入zookeeper服务中，它会在恢复模式下启动，发现leader，并和leader进行状态同步。待到同步结束，它也参与消息广播。Zookeeper服务一直维持在Broadcast状态，直到leader崩溃了或者leader失去了大部分的followers支持。

每个Server在工作过程中有三种状态：

• LOOKING：当前Server不知道leader是谁，正在搜寻。
• LEADING：当前Server即为选举出来的leader
• FOLLOWING：leader已经选举出来，当前Server与之同步

1.5 zookeeper流程

1.5.1 数据流程

1. 在Client向Follwer发出一个写的请求
2. Follwer把请求发送给Leader
3. Leader接收到以后开始发起投票并通知Follwer进行投票
4. Follwer把投票结果发送给Leader
5. Leader将结果汇总后如果超过半数需要写入，则开始写入同时把写入操作通知给Follwer，然后commit;
6. Follwer把请求结果返回给Client

1.5.2 选主流程以及算法

1.5.2.1 选举leader

当leader崩溃或者leader失去大多数的follower，这时候zk进入恢复模式，恢复模式需要重新选举出一个新的leader，让所有的server都恢复到一个正确的状态。　
每个Server启动以后都询问其它的Server它要投票给谁。
对于其他server的询问，server每次根据自己的状态都回复自己推荐的leader的id和上一次处理事务的zxid（系统启动时每个server都会推荐自己）
收到所有Server回复以后，就计算出zxid最大的哪个Server，并将这个Server相关信息设置成下一次要投票的Server
计算这过程中获得票数最多的的sever为获胜者，如果获胜者的票数超过半数，则改server被选为leader。否则，继续这个过程，直到leader被选举出来，leader就会开始等待server连接
Follower连接leader，将最大的zxid发送给leader，Leader根据follower的zxid确定同步点
完成同步后通知follower 已经成为uptodate状态
Follower收到uptodate消息后，又可以重新接受client的请求进行服务了

1.5.2.2 选举算法

Zk的选举算法有两种：一种是基于basic paxos实现的LeaderElection，另外一种是基于fast paxos算法实现的FastLeaderElection和AuthLeaderElection。系统默认的选举算法为fast paxos。

1.5.2.2.1 Basic paxos

Basic paxos：当前Server发起选举的线程,向所有Server发起询问,选举线程收到所有回复,计算zxid最大Server,并推荐此为leader，若此提议获得n/2+1票通过,此为leader，否则重复上述流程，直到leader选出。

1.5.2.2.2 Fast paxos

Fast paxos:某Server首先向所有Server提议自己要成为leader，当其它Server收到提议以后，解决epoch和 zxid的冲突，并接受对方的提议，然后向对方发送接受提议完成的消息，重复这个流程，最后一定能选举出Leader。(即提议方解决其他所有epoch和zxid的冲突,即为leader)

1.6 ZooKeeper的Watcher机制

client端会对某个znode建立一个watcher事件，当该znode发生变化时，这些client会收到zk的通知，然后client可以根据znode变化来做出业务上的改变等
ZooKeeper 的 Watcher 机制主要包括客户端线程、客户端 WatchManager 和 ZooKeeper 服务器三部分。

• ZooKeeper ：部署在远程主机上的 ZooKeeper 集群，当然，也可能是单机的。
• Client ：分布在各处的 ZooKeeper 的 jar 包程序，被引用在各个独立应用程序中。
• WatchManager ：一个接口，用于管理各个监听器，只有一个方法 materialize()，返回一个Watcher的 set。

客户端在向 ZooKeeper 服务器注册 Watcher 的同时，会将Watcher对象存储在客户端的 WatchManager 中。当ZooKeeper 服务器触发 Watcher 事件后，会向客户端发送通知，客户端线程从 WatchManager 的实现类中取出对应的 Watcher 对象来执行回调逻辑。

Watcher 特性总结

• 一次性
  无论是服务端还是客户端，一旦一个 Watcher 被触发，ZooKeeper 都会将其从相应的存储中移除。因此，在 Watcher 的使用上，需要反复注册。这样的设计有效地减轻了服务端的压力。
• 客户端串行执行
  客户端 Watcher 回调的过程是一个串行同步的过程，这为我们保证了顺序，同时，需要注意的一点是，一定不能因为一个 Watcher 的处理逻辑影响了整个客户端的Watcher回调，所以，觉得客户端 Watcher 的实现类要另开一个线程进行处理业务逻辑，以便给其他的 Watcher 调用让出时间。
• 轻量
  WatcherEvent 是 ZooKeeper 整个Watcher通知机制的最小通知单元，这个数据结构中只包含三部分内容：通知状态、事件类型和节点路径。也就是说，Watcher 通知非常简单，只会告诉客户端发生了事件，而不会说明事件的具体内容。例如针对 NodeDataChanged 事件，ZooKeeper 的Watcher 只会通知客户端指定数据节点的数据内容发生了变更，而对于原始数据以及变更后的新数据都无法从这个事件中直接获取到，而是需要客户端主动重新去获取数据——这也是 ZooKeeper 的 Watcher 机制的一个非常重要的特性

点击了解zookeeper之watcher机制实际操作

1.7 Zookeeper不适合作为注册中心

作为一个分布式协同服务，ZooKeeper非常好，但是对于Service发现服务来说就不合适了，因为对于Service发现服务来说就算是返回了包含不实的信息的结果也比什么都不返回要好。所以当向注册中心查询服务列表时，我们可以容忍注册中心返回的是几分钟以前的注册信息，但不能接受服务直接down掉不可用。

但是zk会出现这样一种情况，当master节点因为网络故障与其他节点失去联系时，剩余节点会重新进行leader选举。问题在于，选举leader的时间太长，30 ~ 120s, 且选举期间整个zk集群都是不可用的，这就导致在选举期间注册服务瘫痪。在云部署的环境下，因网络问题使得zk集群失去master节点是较大概率会发生的事，虽然服务能够最终恢复，但是漫长的选举时间导致的注册长期不可用是不能容忍的。

所以说，作为注册中心，可用性的要求要高于一致性！

在 CAP 模型中，Zookeeper整体遵循一致性（CP）原则，即在任何时候对 Zookeeper 的访问请求能得到一致的数据结果，但是当机器下线或者宕机时，不能保证服务可用性。

那为什么Zookeeper不使用最终一致性（AP）模型呢？因为这个依赖Zookeeper的核心算法是ZAB，所有设计都是为了强一致性。这个对于分布式协调系统，完全没没有毛病，但是你如果将Zookeeper为分布式协调服务所做的一致性保障，用在注册中心，或者说服务发现场景，这个其实就不合适。

2 zookeeper的作用

2.1 命名服务

在zookeeper的文件系统里创建一个目录，即有唯一的path。在我们使用tborg无法确定上游程序的部署机器时即可与下游程序约定好path，通过path即能互相探索发现。

2.2 配置管理

把应用配置放置zookeeper上去,保存在 Zookeeper 的某个目录节点中，然后所有相关应用程序对这个目录节点进行监听，一旦配置信息发生变化，每个应用程序就会收到 Zookeeper 的通知，然后从 Zookeeper 获取新的配置信息应用到系统中就好。

2.3 集群管理

节点（机器）增删及Master选取。

2.3.1 节点增删

所有机器约定在父目录GroupMembers下创建临时目录节点，然后监听父目录节点的子节点变化消息。一旦有机器挂掉，该机器与zookeeper的连接断开，其所创建的临时目录节点被删除，所有其他机器都收到通知：某个兄弟目录被删除，于是，所有人都知道：它挂了。新机器加入 也是类似，所有机器收到通知：新兄弟目录加入，highcount又有了。

2.3.1 Master节点选取

所有机器创建临时顺序编号目录节点，每次选取编号最小的机器作为master就好。
如果有多个master，每次只能有一个master负责主要的工作，其他的master作为备份，同时对负责工作的master进行监听，一旦负责工作的master挂掉了，其他的master就会收到监听的事件，从而去抢夺负责工作的权利，其他没有争夺到负责主要工作的master转而去监听负责工作的新master，简而言之：一人干，多人看

2.4 分布式锁

基于zookeeper一致性文件系统,实现锁服务。锁服务分为保存独占及时序控制两类。
点击了解redis分布式锁

2.4.1 保存独占

将zookeeper上的一个znode看作是一把锁，通过createznode的方式来实现。
所有客户端都去创建 /distribute_lock 节点，最终成功创建的那个客户端也即拥有了这把锁。
用完删除自己创建的distribute_lock 节点就释放锁。

2.4.2 时序控制

基于/distribute_lock锁，所有客户端在它下面创建临时顺序编号目录节点，和选master一样，编号最小的获得锁，用完删除，依次方便。

控制时序，就是所有试图来获取这个锁的客户端，最终都是会被安排执行，只是有个全局时序了。做法和上面基本类似，只是这里/distribute_lock 已 经 预 先 存 在 ， 客 户 端 在 它 下 面 创 建 临 是有 序 节 点 （ 这 个 可 以 通 过 节 点 的 属 性 控 制 ：CreateMode.EPHEMERAL_SEQUENTIAL 来指定）。 Zk 的父节点（/distribute_lock）维持一份 sequence,保证子节点创建的时序性，从而也形成了每个客户端的全局时序。

2.5 队列管理

分同步队列,FIFO队列（入队与出队）

2.5.1 同步队列

当一个队列的成员都聚齐时，这个队列才可用，否则一直等待所有成员到达。在约定目录下创建临时目录节点，监听节点数目是否是我们要求的数目

2.5.2 FIFO队列

FIFO队列（入队与出队）和分布式锁服务中的控制时序场景基本原理一致，入列有编号，出列按编号。

2.6 分布式与数据复制

Zookeeper作为一个集群提供一致的数据服务，必然在所有机器间做数据复制。
数据复制好处：

• 容错：一个节点出错，不致于让整个系统停止工作，别的节点可以接管它的工作。
• 提高系统的扩展能力：把负载分布到多个节点上，或者增加节点来提高系统的负载能力；
• 性能提升：让客户端本地访问就近节点,提高用户访问速度。

3 数据一致性与paxos 算法

Paxos 有点类似 2PC（两阶段提交），3PC（3阶段提交），但比这两种算法更加完善。点击此处了解2阶段提交，3阶段提交，TCC补偿机制
在很多多大厂都得到了工程实践，比如阿里的 OceanBase 的 分布式数据库， Google 的 chubby 分布式锁

3.1 Paxos算法是什么

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

3.2 Paxos工作流程

3.2.1 角色

在Paxos中有这么几个角色：

• Proposer（提议者） : 提议者提出提案，用于投票表决。
• Accecptor（接受者） : 对提案进行投票，并接受达成共识的提案。
• Learner（学习者） : 被告知投票的结果，接受达成共识的提案。

在实际中，一个节点可以同时充当不同角色。

提议者提出提案，提案=编号+value，可以表示为[M,V]，每个提案都有唯一编号，而且编号的大小是趋势递增的。

3.2.2 算法流程

Paxos算法包含两个阶段，第一阶段 Prepare(准备)、第二阶段Accept(接受)

3.2.2.1 Prepare(准备)阶段

Prepare(准备)阶段：

• 提议者提议一个新的提案 P[Mn,?]，然后向接受者的某个超过半数的子集成员发送编号为Mn的准备请求
• 如果一个接受者收到一个编号为Mn的准备请求，并且编号Mn大于它已经响应的所有准备请求的编号，那么它就会将它已经批准过的最大编号的提案作为响应反馈给提议者，同时该接受者会承诺不会再批准任何编号小于Mn的提案

总结一下，接受者在收到提案后，会给与提议者两个承诺与一个应答：

• 两个承诺：
  承诺不会再接受提案号小于或等于 Mn 的 Prepare 请求
  承诺不会再接受提案号小于Mn 的 Accept 请求
• 一个应答：
  不违背以前作出的承诺的前提下，回复已经通过的提案中提案号最大的那个提案所设定的值和提案号Mmax，如果这个值从来没有被任何提案设定过，则返回空值。如果不满足已经做出的承诺，即收到的提案号并不是决策节点收到过的最大的，那允许直接对此 Prepare 请求不予理会。

3.2.2.2 Accept(接受)阶段

Accept(接受)阶段：

• 如果提议者收到来自半数以上的接受者对于它发出的编号为Mn的准备请求的响应，那么它就会发送一个针对[Mn,Vn]的接受请求给接受者，注意Vn的值就是收到的响应中编号最大的提案的值，如果响应中不包含任何提案，那么它可以随意选定一个值。
• 如果接受者收到这个针对[Mn,Vn]提案的接受请求，只要该接受者尚未对编号大于Mn的准备请求做出响应，它就可以通过这个提案。

当提议者收到了多数接受者的接受应答后，协商结束，共识决议形成，将形成的决议发送给所有学习节点进行学习。
所以Paxos算法的整体详细流程如下：

3.3 Paxos算法缺点

前面描述的可以称之为Basic Paxos 算法，在单提议者的前提下是没有问题的，但是假如有多个提议者互不相让，那么就可能导致整个提议的过程进入了死循环。
Lamport 提出了 Multi Paxos 的算法思想。
Multi Paxos算法思想，简单说就是在多个提议者的情况下，选出一个Leader（领导者），由领导者作为唯一的提议者，这样就可以解决提议者冲突的问题

3.4 实际应用

在一个分布式数据库系统中，如果各节点的初始状态一致，每个节点都执行相同的操作序列，那么他们最后能得到一个一致的状态。
Paxos算法解决：保证每个节点执行相同的操作序列

Paxos算法通过投票来对写操作进行全局编号，同一时刻，只有一个写操作被批准，同时并发的写操作要去争取选票，只有获得过半数选票的写操作才会被 批准（所以永远只会有一个写操作得到批准），其他的写操作竞争失败只好再发起一轮投票，就这样，在日复一日年复一年的投票中，所有写操作都被严格编号排序。编号严格递增，当一个节点接受了一个编号为100的写操作，之后又接受到编号为99的写操作（因为网络延迟等很多不可预见原因），它马上能意识到自己数据不一致了，自动停止对外服务并重启同步过程。任何一个节点挂掉都不会影响整个集群的数据一致性（总2n+1台，除非挂掉大于n台）。

数据集群系统分：

• 写主（writeMaster）：对数据的修改提交给指定的节点。读无此限制，可以读取任何一个节点。这种情况下客户端需要对读与写进行区别，俗称读写分离；
• 写任意：（对数据的修改可提交给任意的节点，跟读一样。这种情况下，客户端对集群节点的角色与变化透明）对zookeeper来说，它采用的方式是写任意。通过增加机器，它的读吞吐能力和响应能力扩展性非常好，但是随着机器的增多吞吐能力肯定下降（这也是它建立observer的原因），而响应能力则取决于具体实现方式，是延迟复制保持最终一致性，还是立即复制快速响应。