《从 PAXOS 到 ZOOKEEPER：分布式一致性原理与实践》读书笔记

1 系统模型

1.1 数据模型

Zookeeper 中，每一个数据节点都被称为一个 ZNode，所有 ZNode 按层次化结构进行组织，节点路径标识方式和 Unix 文件系统路径相似，由一系列使用 / 进行分割的路径表示，开发人员可以向这个节点中写入数据，也可以在节点下面创建子节点

Zookeeper 对于每一个事务请求，都会为其分配一个全局唯一的事务 ID，用 ZXID 来表示，通常是一个 64 位的数字，低 32 位用来对更新操作递增计数，如果有新的 leader 产生出来，高 32 位会自增。从这些 ZXID 中可以间接识别出 Zookeeper 处理这些更新操作请求的全局顺序，从而保证事务的全局顺序一致性

1.2 节点特点

四种节点类型：持久节点（PERSISTENT），持久顺序节点（PERSISTENT_SEQUENTIAL），临时节点（EPHEMERAL），临时顺序节点（EPHEMERAL_SEQUENTIAL）

1.3 版本（原子性）

对于乐观锁控制事务分成以下三个阶段：数据读取，写入校验，数据写入。version 属性正是用来实现乐观锁机制中的写入校验。

写入校验：Zookeeper 会从 setDataRequest 请求中获取当前的版本 version，同时从数据记录 nodeRecord 中获取到当前服务器上该数据的最新版本 currentVersion。如果 version 为 -1，那么说明客户端并不要求使用乐观锁，可以忽略版本对比；如果 version 不是 -1，那么就比对 version 和 currentVersion ，如果两个版本不匹配，那么就会抛出异常。

1.4 Watcher

客户端在向 Zookeeper 服务器注册 Watcher 的同时，会将 Watcher 对象存储在客户端的 WatcherManager 中，当 Zookeeper 服务器端触发 Watcher 事件后，会向客户端发送通知，客户端接收到 Watcher 通知后，主动从 WatcherManager 中取出对应的 Watcher 对象来执行回调逻辑。

Watcher 特性

一次性：一旦一个 Watcher 被触发，Zookeeper 都会将其移除。这种设计有效减轻了服务端的压力
客户端回调过程是串行同步执行过程
轻量：Watcher 通知只传递是否发生事件，不包含事件具体内容
异步发送：Zookeeper 只能最终一致性，无法保证强一致性
注册 Watcher：getData，exits，getChildren
触发 Watcher：create，delete，setData

工作机制

Watcher 机制可以概述为以下三个过程：客户端注册 Watcher，服务端处理 Watcher 和客户端回调 Watcher

客户端注册 Watcher

调用 getData/getChildren/extis 三个 API 传入 Watcher 对象
标记请求 request，封装 Watcher 到 WatcherRegistration
封装成 Packet 对象，向服务端发送 request
收到服务端响应后，将 Watcher 注册到 ZKWatcerManager 中进行管理

服务端处理

服务端接收并存储 Watcher
封装 WatchedEvent 对象，查询并调用 process 方法来触发 Watcher（TCP）

客户端回调

SendThread 接收事件通知：反序列化、处理 chrootPath、还原 WatchedEvent、回调 Watcher
EventThread 处理事件通知

2 客户端

Zookeeper 客户端核心组件：

Zookeeper 实例：客户端的入口
ClientWatchManager：客户端 Watcher 管理器
HostProvider：客户端地址列表管理器
ClientCnxn：客户端核心线程，SendThread（客户端和服务端网络 I/O 通信），EventThread（对服务端事件进行处理）

3 会话管理

分桶策略：将类似的会话放在同一个区块中进行管理，以便于 Zookeeper 对会话进行不同区块的隔离处理以及同一区块的统一处理
分配原则：每个会话的“下次超时时间点”

4 服务器

4.1 服务器角色

Leader

事务请求的唯一调度和处理者，保证集群事务处理的顺序性
集群内部各服务的调度者

Follower

处理客户端的非事务请求，转发事务请求给 Leader 服务器
参与事务请求 Proposal 的投票
参与 Leader 选举投票

Observer

处理客户端的非事务请求，转发事务请求给 Leader 服务器
不参与任何形式的投票

5 Leader 选举

5.1 启动时期

1、每个 Server 会发出一个投票，初始情况，服务器都会将票投给自己，投票的基本元素为：所推举服务器的 myid 和 ZXID，形式为（myid，ZXID）
2、接收来自各个服务器的投票
3、处理投票：优先检查 ZXID，ZXID 较大的服务器优先作为 Leader；其次为 myid，myid 较大的服务器作为 Leader
4、统计投票：判断是否已经有过半的机器接收到相同的投票信息
5、改变服务器状态

处理投票细则

三台服务器组成集群，当 server1 启动时，仅有一台机器，无法进行 Leader 选举，但是 server2 启动后，就进入了选举状态。对于 server1，它自己的投票是（1，0），接收到的投票是（2，0），根据规则显然 server1 会更新自己的投票为（2，0）然后将投票重新发出去，而 server2 只需要再一次向集群中所有机器发出上一次投票信息即可，这时候 server1 和 server2 都收到相同的投票信息（2，0），满足过半要求，则已经选出了 Leader

5.2 运行期间

1、改变状态
2、每个 server 会发起一个投票
3、接收来自各个服务器的投票
4、处理投票
5、统计投票
6、改变服务器状态

处理投票细则

同样是三台服务器组成的集群，当前的 Leader 是挂掉的 server2，这时候需要生成投票信息。由于在运行期间，每个服务器上的 ZXID 可能不同，我们假定 server1 的 ZXID 是 123，server3 的 ZXID 是 122。在第一轮投票中，机器会投给自己，即分别产生投票（1，123）和（3，122），然后将投票发送给集群中的所有机器。按照投票处理规则，明显 server1 会成为新的 Leader。

5.3 算法分析

Zookeeper 中提供了三种 Leader 选举算法，分别是 LeaderElection（UDP）、FastLeaderElection（UDP）、FastLeaderElection（TCP），可以通过配置文件中 zoo.cfg 中使用 electionAlg 属性来指定。

术语解释

SID：服务器 ID
ZXID：事务 ID
Vote：投票
Quorum：过半机器数

第一次投票

第一次投票的时候，由于还无法检测到集群中其他机器的状态信息，因此每台机器是会将自己作为被推举的对象来进行投票。投票形式为（SID，ZXID）

我们假设 Zookeeper 有 5 台机器组成，SID 分别是 1-5，ZXID 分别是 9，9，9，8，8，此时 SID 为 2 的机器是 Leader，并且机器 1 和 2 挂掉，于是 SID 为 3、4、5 的机器，投票情况分别是（3，9），（4，8），（5，8）

变更投票

集群中的机器发出自己的投票后，也会收到来自集群中其他机器的投票，每次对于收到的投票，都是将（vote_sid, vote_zxid）和（self_sid, self_zxid）按照以下规则对比的过程

如果 vote_zxid 大于 self_zxid，那就就认可当前收到的投票，并再次将该投票发送出去
如果 vote_zxid 小于 self_zxid，那么就坚持自己的投票，不做任何变更
如果 vote_zxid 等于 self_zxid，那么就对比两者的 SID，如果 vote_sid 大于 self_sid，那么就认可当前接收到的投票，并再次将该投票发送出去
如果 vote_zxid 等于 self_zxid，并且 vote_sid 小于 self_sid，那就坚持自己的投票，不做变更

第一次投票后，每台机器都把投票发出后，同时也会收到来自另外两台机器的投票

对于 server3 来说，它接收到了（4，8）和（5，8）两个投票，对比后，由于自己的 ZXID 要大于接收到的两个投票，因此不需要做任何改变
对于 server4 来说，它接收到了（3，9）和（5，8）两个投票，对比后，由于（3，9）这个投票的 ZXID 大于自己，因此需要变更投票为（3，9），然后继续将这个投票发送给另外两台机器
对于 server5 来说，它接收都了（3，9）和（4，8）两个投票，对比后，由于（3，9）这个投票的 ZXID 大于自己，因此需要变更投票为（3，9），然后继续将这个投票发送给另外两台机器

确定 Leader

在经过第二次投票后，如果一台机器收到了超过半数的相同的投票，那么这个投票对应的 SID 机器即为 Leader

在上文变更投票后，server3 为 Leader

简单来说，通常哪台服务器的数据越新，即 ZXID 越大，就越有可能成为 Leader

5.4 算法实现

服务器状态

LOOKING：寻找 Leader 状态
FOLLOWING：跟随者状态
LEADING：领导者状态
OBSERVING：观察者状态

投票数据结构 Vote

id：被推举的 Leader 的 SID 值
zxid：被推举的 Leader 的事务 ID
electionEpoch：服务器的选举轮次
peerEpoch：被推举的服务器的选举轮次
state：当前服务器的状态

QuorumCnxManager ：网络 IO

消息队列

QuorumCnxManager 内部维护了一系列的队列，用来保存接收到的，待发送的消息以及消息的发送器，除接收队列以外，其他队列都安装 SID 分组形成队列集合

建立连接

为了能够相互投票，Zookeeper 集群中的所有机器都需要两两建立起网络连接。QuorumCnxManager 在启动时会创建一个 ServerSocket 来监听 Leader 选举的通信端口(默认为 3888 )。开启监听后，Zookeeper 能够不断地接收到来自其他服务器的创建连接请求，在接收到其他服务器的 TCP 连接请求时，会进行处理。

消息接收与发送

消息接收：由消息接收器RecvWorker负责，由于Zookeeper为每个远程服务器都分配一个单独的RecvWorker，因此，每个RecvWorker只需要不断地从这个TCP连接中读取消息，并将其保存到recvQueue队列中。
消息发送：由于Zookeeper为每个远程服务器都分配一个单独的SendWorker，因此，每个SendWorker只需要不断地从对应的消息发送队列中获取出一个消息发送即可，同时将这个消息放入lastMessageSent中。

5.5 算法核心

外部投票：特指其他服务器发来的投票
内部投票：服务器自身当前的投票
选举轮次：Zookeeper 服务器 Leader 选举的轮次，即 logicalclock
PK：指对内部投票和外部投票进行一个对比来确定是否需要变更内部投票
选票管理：sendqueue 选票发送队列，用于保存待发送的选票；recvqueue 选票接收队列，用于保存接收到的外部投票；WorkReceiver 选票接收器，从 QuorumCnxManager 中获取其他服务器的选举信息，并将其转换成一个选票，然后保存到 recvqueue 中；WorkerSender 选票发送器，不断地从 sendqueue 中获取等待发送的选票，并将其传递到 QuorumCnxManager 中

算法流程

1、自增选举轮次。Zookeeper 规定所有有效的投票都必须在同一个轮次中
2、初始化选票。在开始新一轮投票前，每个服务器都会初始化自身的选票，并且在初始化阶段，每台服务器都会将自己推举为 Leader
3、发送初始化选票。Zookeeper 会将刚刚初始化好的选票放入 sendquue 中，由发送器 WorkerSender 负责发送出去
4、接收外部选票。每台服务器不断地从 recvqueue 队列中获取外部选票
5、判断选举轮次。如果服务器自身的选举轮次落后于该外部投票对应的服务器的选举轮次，那么就会立即更新自己的选举轮次，并清空所有已经收到的投票，然后使用初始化的投票来进行 PK；外部轮次小于内部轮次则不做处理，继续接收外部选票；内外轮次相等时，则开始进行选票 PK
6、选票 PK。若外部投票中推举的 Leader 服务器的选举轮次大于内部投票，那么需要变更投票；若选举轮次一致，外部投票的 ZXID 大，则需要变更投票；若 ZXID 一致，外部投票的 SID 大，则需要变更投票
7、变更投票。PK 后，若确定了外部投票优于内部投票，那么就变更投票，即使用外部投票的选票信息来覆盖内部投票，变更完成后，再次将这个变更后的内部投票发送出去。
8、选票归档。无论是否变更了投票，都会将收到的那份外部投票放入选票集合 recvset 中进行归档，按照服务器对应的 SID 来区分
9、统计投票。为了统计集群中是否已经有过半的服务器认可了当前的内部投票，如果有则终止投票，没有则返回步骤 4
10、更新服务器状态。如果 Leader 是服务器自己的话，更新为 LEADING，否则更新为 FOLLOWING 或者 OBSERVING

算法流程图

算法与底层交互

6 高可用集群

Zookeeper 集群建议设计部署成奇数台服务器：N 与 N+1 容灾能力上没有显著优势
三机房部署：假设集群的机器总数为 N，那么 N1=(N-1)/2，N2=1~(N-N1)/2，N3=N-N1-N2
水平扩容：整个重启和逐台重启

G.Fukang's Blog

Zookeeper 技术内幕