zookeeper 及 paxos 算法基本介绍

1. 概述

zookeeper 是一个高性能的分布式应用程序协调服务，应用程序可以基于他非常简单的实现同步服务、分组服务、配置维护、命名服务等，通过 zookeeper，你可以使用现成的组件实现一致性服务、分组管理、leader 选举。 由于工程师不能很好地使用锁机制，以及基于消息的协调机制不适合在某些应用中使用，因此需要有一种可靠的、可扩展的、分布式的、可配置的协调机制来统一系统的状态。Zookeeper 的目的就在于此。 zookeeper 十分易用，它使用和文件系统中目录树相似的结构来实现他的功能，它使用 java 和 C 编写，运行在 java 环境下。

2. zookeeper 的构成

Zookeeper 构成的分布式系统中，每个节点可以是以下某个角色：

zookeeper 的角色

Leader、Follower、Observer 共同构成了处理请求的 Server，用来处理 Client 发来的各式请求。

zookeeper 的分布式程序通过与标准文件系统非常相似的命名空间相互配合，这些命名空间被称为 znodes，他们和文件系统的文件和目录非常相似。 zookeeper 的所有 server 通过这个共享的命名空间都知道其他 server 的存在，这些 server 中维护着一个状态镜像，还有持久化存储的 log 和快照。

3. zookeeper 的工作原理

zookeeper 的核心是原子广播，使用这个机制保证各个 Server 间的同步，实现原子广播的协议叫做 Zab 协议。 Zab 协议有两种模式：恢复模式（选主）和广播模式（同步），当服务启动或 Leader 宕机，Zab 就进入恢复模式，一旦 Leader 被选举出来，且大多数 Server 完成 Leader 状态同步后，即进入广播模式。 每个工作中的 Server 都有三种工作状态： 1. LOOKING — 搜寻 Leader 2. LEADING — 当前 Server 是集群 Leader 3. FOLLOWING — Leader 已经选举出，当前 Server 节点与 Leader 同步

4. 投票选举 — Paxos 算法

zookeeper 选举算法有两种：basic paxos 和 fast paxos 算法，下面，我们首先介绍一下 basic paxos 算法： 1. Proposer（提案者） 选择一个唯一的提案编号 A 并将 prepare 请求 (A,a) 发送给 Acceptors（决策者）中的一个多数派 2. Acceptor 收到 prepare 消息后，如果提案的编号大于它已经回复的所有 prepare 消息(Sh)，则 Acceptor 将自己上次接受的提案回复给 Proposer (S,v) 并更新历史最大提案编号 Sh，并承诺不再回复小于 n 的提案，否则直接返回 false 3. Acceptor 在指定超时时间内，收到请求中如果有 false（拒绝提案），则直接终止该提案，如果收到非本次提案编号，则放弃本次提案，重新广播收到的提案 4. 如果多数派都通过了决议，则向所有 Acceptor 广播 accept 请求 5. 在不违背自己向其他 Proposer 的承诺的前提下，Acceptor 收到 accept 请求后即接受这个请求

对于 zookeeper，唯一编号是使用一个 64位的事务 id 号（zxid）来标识的，低 32 位是递增计数值，高 32 位用来标识 leader 关系是否被改变。

5. 工作流程

5.1. Leader

Leader 主要进行以下工作： 1. 恢复数据 2. 维持与 Follower 的心跳 3. 接受 Follower 请求

Follower 请求共有以下四种： 1. PING — 保持心跳 2. REQUEST — 写请求和同步请求，需要加入处理队列进行处理 3. ACK — 超过半数 Follower 对某提议回复 ACK，则 commit 该提议 4. REVALIDATE — 延长 session 有效时间

5.2. Follower

Follower 主要有以下四个功能： 1. 向 Leader 发送请求（PING、REQUEST、ACK、REVALIDATE） 2. 接收 Leader 消息并处理 3. 接收 Client 请求，如果为写请求则发送给 Leader 投票 4. 将结果返回给 Client

Follower 处理的来自 Leader 的请求共有以下六种： 1. PING — 心跳 2. PROPOSAL — Leader 发起提案，要求 Follower 投票，投票过程见上述 Paxos 算法 3. COMMIT — 最新一次提案信息 4. UPTODATE — 表明同步完成 5. REVALIDATE — 对客户端 REVALIDATE 的回应 6. SYNC — 由客户端发起，强制得到最新的更新

6. 参考资料

官方文档 — http://zookeeper.apache.org/ paxos algorithm — https://en.wikipedia.org/wiki/Paxos_(computer_science) What is a simple explanation of the Paxos algorithm? — https://www.quora.com/Distributed-Systems-What-is-a-simple-explanation-of-the-Paxos-algorithm。 Paxos — http://www.cs.yale.edu/homes/aspnes/pinewiki/Paxos.html。 paxos算法如何容错的—讲述五虎将的实践 — http://blog.csdn.net/russell_tao/article/details/7238783。