https://www.cnblogs.com/luxiaoxun/p/4887452.html
作者：阿凡卢
ZooKeeper 简介
ZooKeeper 是一个开放源码的分布式应用程序协调服务，它包含一个简单的原语集，分布式应用程序可以基于它实现同步服务，配置维护和命名服务等。
ZooKeeper 设计目的
1. 最终一致性：client 不论连接到哪个 Server，展示给它都是同一个视图，这是 zookeeper 最重要的性能。
2. 可靠性：具有简单、健壮、良好的性能，如果消息 m 被到一台服务器接受，那么它将被所有的服务器接受。
3. 实时性：Zookeeper 保证客户端将在一个时间间隔范围内获得服务器的更新信息，或者服务器失效的信息。但由于网络延时等原因，Zookeeper 不能保证两个客户端能同时得到刚更新的数据，如果需要最新数据，应该在读数据之前调用 sync() 接口。
4. 等待无关（wait-free）：慢的或者失效的 client 不得干预快速的 client 的请求，使得每个 client 都能有效的等待。
5. 原子性：更新只能成功或者失败，没有中间状态。
6. 顺序性：包括全局有序和偏序两种：全局有序是指如果在一台服务器上消息 a 在消息 b 前发布，则在所有 Server 上消息 a 都将在消息 b 前被发布；偏序是指如果一个消息 b 在消息 a 后被同一个发送者发布，a 必将排在 b 前面。
ZooKeeper 数据模型
Zookeeper 会维护一个具有层次关系的数据结构，它非常类似于一个标准的文件系统，如图所示：
Zookeeper 这种数据结构有如下这些特点：
1）每个子目录项如 NameService 都被称作为 znode，这个 znode 是被它所在的路径唯一标识，如 Server1 这个 znode 的标识为 / NameService/Server1。
2）znode 可以有子节点目录，并且每个 znode 可以存储数据，注意 EPHEMERAL（临时的）类型的目录节点不能有子节点目录。
3）znode 是有版本的（version），每个 znode 中存储的数据可以有多个版本，也就是一个访问路径中可以存储多份数据，version 号自动增加。
4）znode 的类型：
- _Persistent _节点，一旦被创建，便不会意外丢失，即使服务器全部重启也依然存在。每个 Persist 节点即可包含数据，也可包含子节点。
_Ephemeral _节点，在创建它的客户端与服务器间的 Session 结束时自动被删除。服务器重启会导致 Session 结束，因此 Ephemeral 类型的 znode 此时也会自动删除。
_Non-sequence _节点，多个客户端同时创建同一 Non-sequence 节点时，只有一个可创建成功，其它匀失败。并且创建出的节点名称与创建时指定的节点名完全一样。
_Sequence _节点，创建出的节点名在指定的名称之后带有 10 位 10 进制数的序号。多个客户端创建同一名称的节点时，都能创建成功，只是序号不同。
5）znode 可以被监控，包括这个目录节点中存储的数据的修改，子节点目录的变化等，一旦变化可以通知设置监控的客户端，这个是 Zookeeper 的核心特性，Zookeeper 的很多功能都是基于这个特性实现的。
6）ZXID：每次对 Zookeeper 的状态的改变都会产生一个 zxid（ZooKeeper Transaction Id），zxid 是全局有序的，如果 zxid1 小于 zxid2，则 zxid1 在 zxid2 之前发生。
ZooKeeper Session
Client 和 Zookeeper 集群建立连接，整个 session 状态变化如图所示：
如果 Client 因为 Timeout 和 Zookeeper Server 失去连接，client 处在 CONNECTING 状态，会自动尝试再去连接 Server，如果在 session 有效期内再次成功连接到某个 Server，则回到 CONNECTED 状态。
注意：如果因为网络状态不好，client 和 Server 失去联系，client 会停留在当前状态，会尝试主动再次连接 Zookeeper Server。client 不能宣称自己的 session expired，session expired 是由 Zookeeper Server 来决定的，client 可以选择自己主动关闭 session。
ZooKeeper Watch
Zookeeper watch 是一种监听通知机制。Zookeeper 所有的读操作 getData(), getChildren() 和 exists() 都可以设置监视 (watch)，监视事件可以理解为一次性的触发器，官方定义如下： a watch event is one-time trigger, sent to the client that set the watch, whichoccurs when the data for which the watch was set changes。Watch 的三个关键点：
*（一次性触发）One-time trigger
当设置监视的数据发生改变时，该监视事件会被发送到客户端，例如，如果客户端调用了 getData("/znode1", true) 并且稍后 /znode1 节点上的数据发生了改变或者被删除了，客户端将会获取到 /znode1 发生变化的监视事件，而如果 /znode1 再一次发生了变化，除非客户端再次对 / znode1 设置监视，否则客户端不会收到事件通知。
*（发送至客户端）Sent to the client
Zookeeper 客户端和服务端是通过 socket 进行通信的，由于网络存在故障，所以监视事件很有可能不会成功地到达客户端，监视事件是异步发送至监视者的，Zookeeper 本身提供了顺序保证 (ordering guarantee)：即客户端只有首先看到了监视事件后，才会感知到它所设置监视的 znode 发生了变化 (a client will never see a change for which it has set a watch until it first sees the watch event)。网络延迟或者其他因素可能导致不同的客户端在不同的时刻感知某一监视事件，但是不同的客户端所看到的一切具有一致的顺序。
*（被设置 watch 的数据）The data for which the watch was set
这意味着 znode 节点本身具有不同的改变方式。你也可以想象 Zookeeper 维护了两条监视链表：数据监视和子节点监视 (data watches and child watches) getData() 和 exists() 设置数据监视，getChildren()设置子节点监视。或者你也可以想象 Zookeeper 设置的不同监视返回不同的数据，getData() 和 exists() 返回 znode 节点的相关信息，而 getChildren() 返回子节点列表。因此，setData() 会触发设置在某一节点上所设置的数据监视（假定数据设置成功），而一次成功的 create() 操作则会出发当前节点上所设置的数据监视以及父节点的子节点监视。一次成功的 delete 操作将会触发当前节点的数据监视和子节点监视事件，同时也会触发该节点父节点的 child watch。
Zookeeper 中的监视是轻量级的，因此容易设置、维护和分发。当客户端与 Zookeeper 服务器失去联系时，客户端并不会收到监视事件的通知，只有当客户端重新连接后，若在必要的情况下，以前注册的监视会重新被注册并触发，对于开发人员来说这通常是透明的。只有一种情况会导致监视事件的丢失，即：通过 exists() 设置了某个 znode 节点的监视，但是如果某个客户端在此 znode 节点被创建和删除的时间间隔内与 zookeeper 服务器失去了联系，该客户端即使稍后重新连接 zookeeper 服务器后也得不到事件通知。
Consistency Guarantees
Zookeeper 是一个高效的、可扩展的服务，read 和 write 操作都被设计为快速的，read 比 write 操作更快。
顺序一致性（Sequential Consistency）：从一个客户端来的更新请求会被顺序执行。
原子性（Atomicity）：更新要么成功要么失败，没有部分成功的情况。
唯一的系统镜像（Single System Image）：无论客户端连接到哪个 Server，看到系统镜像是一致的。
可靠性（Reliability）：更新一旦有效，持续有效，直到被覆盖。
时间线（Timeliness）：保证在一定的时间内各个客户端看到的系统信息是一致的。
ZooKeeper 的工作原理
在 zookeeper 的集群中，各个节点共有下面 3 种角色和 4 种状态：
- 角色：leader,follower,observer
- 状态：leading,following,observing,looking
Zookeeper 的核心是原子广播，这个机制保证了各个 Server 之间的同步。实现这个机制的协议叫做 Zab 协议（ZooKeeper Atomic Broadcast protocol）。Zab 协议有两种模式，它们分别是恢复模式（Recovery 选主）和广播模式（Broadcast 同步）。当服务启动或者在领导者崩溃后，Zab 就进入了恢复模式，当领导者被选举出来，且大多数 Server 完成了和 leader 的状态同步以后，恢复模式就结束了。状态同步保证了 leader 和 Server 具有相同的系统状态。
为了保证事务的顺序一致性，zookeeper 采用了递增的事务 id 号（zxid）来标识事务。所有的提议（proposal）都在被提出的时候加上了 zxid。实现中 zxid 是一个 64 位的数字，它高 32 位是 epoch 用来标识 leader 关系是否改变，每次一个 leader 被选出来，它都会有一个新的 epoch，标识当前属于那个 leader 的统治时期。低 32 位用于递增计数。
每个 Server 在工作过程中有 4 种状态：
LOOKING：当前 Server 不知道 leader 是谁，正在搜寻。
LEADING：当前 Server 即为选举出来的 leader。
FOLLOWING：leader 已经选举出来，当前 Server 与之同步。
OBSERVING：observer 的行为在大多数情况下与 follower 完全一致，但是他们不参加选举和投票，而仅仅接受 (observing) 选举和投票的结果。
Leader Election
当 leader 崩溃或者 leader 失去大多数的 follower，这时候 zk 进入恢复模式，恢复模式需要重新选举出一个新的 leader，让所有的 Server 都恢复到一个正确的状态。Zk 的选举算法有两种：一种是基于 basic paxos 实现的，另外一种是基于 fast paxos 算法实现的。系统默认的选举算法为 fast paxos。先介绍 basic paxos 流程：
1. 选举线程由当前 Server 发起选举的线程担任，其主要功能是对投票结果进行统计，并选出推荐的 Server；
2. 选举线程首先向所有 Server 发起一次询问（包括自己）；
3. 选举线程收到回复后，验证是否是自己发起的询问（验证 zxid 是否一致），然后获取对方的 id（myid），并存储到当前询问对象列表中，最后获取对方提议的 leader 相关信息（id,zxid），并将这些信息存储到当次选举的投票记录表中；
4. 收到所有 Server 回复以后，就计算出 zxid 最大的那个 Server，并将这个 Server 相关信息设置成下一次要投票的 Server；
5. 线程将当前 zxid 最大的 Server 设置为当前 Server 要推荐的 Leader，如果此时获胜的 Server 获得 n/2 + 1 的 Server 票数，设置当前推荐的 leader 为获胜的 Server，将根据获胜的 Server 相关信息设置自己的状态，否则，继续这个过程，直到 leader 被选举出来。
通过流程分析我们可以得出：要使 Leader 获得多数 Server 的支持，则 Server 总数必须是奇数 2n+1，且存活的 Server 的数目不得少于 n+1.
每个 Server 启动后都会重复以上流程。在恢复模式下，如果是刚从崩溃状态恢复的或者刚启动的 server 还会从磁盘快照中恢复数据和会话信息，zk 会记录事务日志并定期进行快照，方便在恢复时进行状态恢复。
fast paxos 流程是在选举过程中，某 Server 首先向所有 Server 提议自己要成为 leader，当其它 Server 收到提议以后，解决 epoch 和 zxid 的冲突，并接受对方的提议，然后向对方发送接受提议完成的消息，重复这个流程，最后一定能选举出 Leader。
Leader 工作流程
Leader 主要有三个功能：
1. 恢复数据；
2. 维持与 follower 的心跳，接收 follower 请求并判断 follower 的请求消息类型；
3.follower 的消息类型主要有 PING 消息、REQUEST 消息、ACK 消息、REVALIDATE 消息，根据不同的消息类型，进行不同的处理。
PING 消息是指 follower 的心跳信息；REQUEST 消息是 follower 发送的提议信息，包括写请求及同步请求；
ACK 消息是 follower 的对提议的回复，超过半数的 follower 通过，则 commit 该提议；
REVALIDATE 消息是用来延长 SESSION 有效时间。
Follower 工作流程
Follower 主要有四个功能：
1. 向 Leader 发送请求（PING 消息、REQUEST 消息、ACK 消息、REVALIDATE 消息）；
2. 接收 Leader 消息并进行处理；
3. 接收 Client 的请求，如果为写请求，发送给 Leader 进行投票；
4. 返回 Client 结果。
Follower 的消息循环处理如下几种来自 Leader 的消息：
1.PING 消息：心跳消息
2.PROPOSAL 消息：Leader 发起的提案，要求 Follower 投票
3.COMMIT 消息：服务器端最新一次提案的信息
4.UPTODATE 消息：表明同步完成
5.REVALIDATE 消息：根据 Leader 的 REVALIDATE 结果，关闭待 revalidate 的 session 还是允许其接受消息
6.SYNC 消息：返回 SYNC 结果到客户端，这个消息最初由客户端发起，用来强制得到最新的更新。
Zab: Broadcasting State Updates
Zookeeper Server 接收到一次 request，如果是 follower，会转发给 leader，Leader 执行请求并通过 Transaction 的形式广播这次执行。Zookeeper 集群如何决定一个 Transaction 是否被 commit 执行？通过 “两段提交协议”（a two-phase commit）：
- Leader 给所有的 follower 发送一个 PROPOSAL 消息。
- 一个 follower 接收到这次 PROPOSAL 消息，写到磁盘，发送给 leader 一个 ACK 消息，告知已经收到。
- 当 Leader 收到法定人数（quorum）的 follower 的 ACK 时候，发送 commit 消息执行。
Zab 协议保证：
- 1） 如果 leader 以 T1 和 T2 的顺序广播，那么所有的 Server 必须先执行 T1，再执行 T2。
- 2） 如果任意一个 Server 以 T1、T2 的顺序 commit 执行，其他所有的 Server 也必须以 T1、T2 的顺序执行。
“两段提交协议” 最大的问题是如果 Leader 发送了 PROPOSAL 消息后 crash 或暂时失去连接，会导致整个集群处在一种不确定的状态（follower 不知道该放弃这次提交还是执行提交）。Zookeeper 这时会选出新的 leader，请求处理也会移到新的 leader 上，不同的 leader 由不同的 epoch 标识。切换 Leader 时，需要解决下面两个问题：
1. Never forget delivered messages
Leader 在 COMMIT 投递到任何一台 follower 之前 crash，只有它自己 commit 了。新 Leader 必须保证这个事务也必须 commit。
2. Let go of messages that are skipped
Leader 产生某个 proposal，但是在 crash 之前，没有 follower 看到这个 proposal。该 server 恢复时，必须丢弃这个 proposal。
Zookeeper 会尽量保证不会同时有 2 个活动的 Leader，因为 2 个不同的 Leader 会导致集群处在一种不一致的状态，所以 Zab 协议同时保证：
- 1） 在新的 leader 广播 Transaction 之前，先前 Leader commit 的 Transaction 都会先执行。
- 2） 在任意时刻，都不会有 2 个 Server 同时有法定人数（quorum）的支持者。
这里的 quorum 是一半以上的 Server 数目，确切的说是有投票权力的 Server（不包括 Observer）。
总结：简单介绍了 Zookeeper 的基本原理，数据模型，Session，Watch 机制，一致性保证，Leader Election，Leader 和 Follower 的工作流程和 Zab 协议。
参考：
- 《ZooKeeper—Distributed Process Coordination》 by FlavioJunqueira and Benjamin Reed
- http://zookeeper.apache.org/doc/current/zookeeperOver.html
- http://www.ibm.com/developerworks/cn/opensource/os-cn-zookeeper/index.html
- 《ZooKeeper 的一致性算法赏析》
