协议

集群启动顺序（演示图与实际图node数值相差1）

1. 先启动node01
   • 会建立一个2888的服务端口与3888的选举端口。
   • 此时只有一个服务启动，所以没有其他关联。
2. 再启动node02
   • 同样建立一个2888的服务端口与3888的选举端口。
   • 同时查找集群配置，发现能联通node1，并建立socket连接，将随机分配一个端口与node1的3888选举端口映射。
3. 然后是node03
   • 同样建立一个2888的服务端口与3888的选举端口。
   • 查找集群配置，发现能联通node1与node2，并建立两条socket连接，随机分配端口与node1与node2的3888选举端口映射。
4. 最后是node04
   • 同样建立一个2888的服务端口与3888的选举端口。
   • 查找集群配置，发现能联通node1，node2与node3，并建立三条socket连接，随机分配端口与node1，node2与node3的3888选举端口映射。

当启动完后，会发现如下一张图，其每个节点都有一条与其他node连接。又由于是socket连接，可以互通，所以达到了每个节点都能与其他通信的可能。

paxos 算法

场景描述

• 有一个叫做Paxos的小岛(Island)上面住了一批居民，岛上面所有的事情由一些特殊的人决定，他们叫做议员(Senator)。

• 议员的总数(Senator Count)是确定的，不能更改。

• 岛上每次环境事务的变更都需要通过一个提议(Proposal)。

• 每个提议都有一个编号(PID)，这个编号是一直增长的，不能倒退。

• 每个提议都需要超过半数((Senator Count)/2 +1)的议员同意才能生效。

• 每个议员只会同意大于当前编号的提议，包括已生效的和未生效的。

• 如果议员收到小于等于当前编号的提议，他会拒绝，并告知对方：你的提议已经有人提过了。这里的当前编号是每个议员在自己记事本上面记录的编号，他不断更新这个编号。

• 整个议会不能保证所有议员记事本上的编号总是相同的。现在议会有一个目标：保证所有的议员对于提议都能达成一致的看法。

协议运行

正常场景

• 所有议员一开始记事本上面记录的编号都是0。
• 有一个议员发了一个提议：将电费设定为1元/度。他首先看了一下记事本，嗯，当前提议编号是0，那么我的这个提议的编号就是1，于是他给所有议员发消息：1号提议，设定电费1元/度。
• 其他议员收到消息以后查了一下记事本，哦，当前提议编号是0，这个提议可接受，于是他记录下这个提议并回复：我接受你的1号提议，同时他在记事本上记录：当前提议编号为1。发起提议的议员收到了超过半数的回复，立即给所有人发通知：1号提议生效！
• 收到的议员会修改他的记事本，将1好提议由记录改成正式的法令，当有人问他电费为多少时，他会查看法令并告诉对方：1元/度。

冲突场景

• S1和S2同时发起了一个提议:1号提议，设定电费。S1想设为1元/度, S2想设为2元/度。
• S3先收到了S1的提议，于是他做了和前面同样的操作。紧接着他又收到了S2的提议，结果他一查记事本，咦，这个提议的编号小于等于我的当前编号1，于是他拒绝了这个提议：对不起，这个提议先前提过了。于是S2的提议被拒绝，
• S1正式发布了提议: 1号提议生效。S2向S1或者S3打听并更新了1号法令的内容，然后他可以选择继续发起2号提议。

zab协议

Zab协议 的全称是 Zookeeper Atomic Broadcast （Zookeeper原子广播）。

与paxos相似，但paxos中的角色都是平等的，但zab协议中的角色是有区别的，多了一个总统的概念。可以说zab是paxos的变种。

角色映射

• 小岛(Island)——ZK Server Cluster

• 议员(Senator)——ZK Server

• 提议(Proposal)——ZNode Change(Create/Delete/SetData…)

• 提议编号(PID)——Zxid(ZooKeeper Transaction Id)

• 居民（client）– ZK clint

协议运行

场景一（查）

• 居民（client）到其中一个议员（zk server）那询问（get）某条法令的情况（znode数据）。
• 议员拿出记事本（local storage）查阅法令并告诉他结果。但会声明，这条法令虽然是有效的，但未必是最新的。
• 居民如果强调需要最新的法令，议员会让居民等待，与总统（leader）询问法令数据（sync）后，返回正确的法令情况给居民。

场景二（增删改）

• 居民（client）到其中一个议员（zk server）那里要求更改（set）某条法令。
• 议员让其等待，并将更改要求反馈给总统，总统发起提议更改法令，议员收到提议后有半数接受提议并反馈给总统。
• 总统正式更改了法令后，将新的法令让议员通知到居民。
• 居民拿着变更后的法令返回了。

具体执行步骤

增演示

1. client客户端，连接一个follower，并发送一条创建节点语句。
2. follower接收到请求后，向leader发送创建节点语句。
3. leader收到follower的请求后，给该创建节点的语句编唯一序号zxid（控制版本用）。
4. leader通过队列向follower发送创建节点的日志。
   1. follower接收到消息后保存日志（还未启用），并向leader回执，表示收到。
   2. leader监听到半数follower回执完成日志记录后，再发送生效命令。
   3. follower收到生效命令，把保存日志的记录读取到内存生效，并回执。
5. leader返回follower响应。
6. follower返回client响应。

查演示

• client连接follower，查询节点信息。follower返回当前节点的数据，但未必是最新的。
• client连接follower，查询节点信息，要求是最新的。follower先同步节点信息，再返回节点数据，保证返回的数据最新。

leader选举

选举原理

• zookeeper集群中只有超过半数以上的服务器启动，集群才可以对外服务。
• myid小的服务器给myid大的服务器投票，直到选出leader。
• 如果是恢复模式下，myid小的投票给myid大的前提是两者保存的都是最新数据（zxid），否则，谁的数据新，谁获得票。

场景一：第一次启动集群

1. 启动node01：
   • node01未找到集群中的leader，发起投票，先给自己投一票。
   • 由于没有其他联通的服务器，等待计票时没有一个票数超过半数，所以保持looking状态。等待其他服务的上线与选举。
2. 启动node02：
   • node02未找到集群leader,发起投票，票箱里是空的，所以投自己一票，并广播出去自己选了的leader信息。
   • node01接收到node02发送的广播信息，将node02选出的leader(node02)信息与自己选择的leader（node01）做比较,发现node02的myid比自己选择的leader大，将自己的leader更改为node02的leader，保存进票箱，并广播。
   • node02收到广播，发现node01变更的leader与自己的leader一致，写入票箱。
   • 由于没有其他联通的服务器，等待计票时没有一个票数超过半数，所以保持looking状态。等待其他服务的上线与选举。
3. 启动node03：
   • node03未找到集群leader,发起投票，票箱里是空的，所以投自己一票，并广播出去自己选了的leader信息。
   • node02与node01接受到广播消息，将node03选出的leader（node03）信息与自己选出的leader（node02）作比较，发现node03的myid比自己选的ldeader大，将自己的leader更改为node03的leader，保存进票箱，并广播。
   • node01收到node02的广播，发现与自己现在选的leader一致，保存进票箱，不再广播。
   • node02收到node01的广播，发现与自己现在选的leader一致，保存进票箱，不再广播。
   • node03收到node01，node02的广播，发现与自己现在选的leader一致，保存进票箱，不再广播。
   • 最终归票，发现node03的票数为3，过半，node03将身份变为leader，node01，node02将身份变为follower。
4. 启动node04：
   • node04发现集群中存在leader是node03，不再进行投票，直接变成follower身份，并关联leader。

场景二：中途leader菪机

1. node03菪机：

   • 由于某些原因，node03服务器上的zookeeper服务挂了。

2. node02发现leader挂了：

   • node02未找到集群leader，发起投票，将自己作为leader进行广播。

   • node04收到node02的广播，与自己做比对，发现是自己的zxid新，则将给自己投一票，并广播。

     node01收到node02的广播，与自己做比对，发现是自己的zxid新，则将给自己投一票，并广播。

   • node01与node02收到node04的广播，与自生当前leader做比较，发现node04的leader胜选，将票记下，并更改leader为node4的leader并广播。

   • node01收到node02的广播，发现leader一致，将票记下，不广播。

     node02收到node01的广播，发现leader一致，将票记下，不广播。

     node04收到node01，node02的广播，发现leader一致，将票记下，不广播。

   • 最终归票，发现node03的票数为3，过半，node03将身份变为leader，node01，node02将身份变为follower。

算法核心

1、自增选举轮次。Zookeeper规定所有有效的投票都必须在同一轮次中，在开始新一轮投票时，会首先对logicalclock进行自增操作。

2、初始化选票。在开始进行新一轮投票之前，每个服务器都会初始化自身的选票，并且在初始化阶段，每台服务器都会将自己推举为Leader。

3、发送初始化选票。完成选票的初始化后，服务器就会发起第一次投票。Zookeeper会将刚刚初始化好的选票放入sendqueue中，由发送器WorkerSender负责发送出去。

4、接收外部投票。每台服务器会不断地从recvqueue队列中获取外部选票。如果服务器发现无法获取到任何外部投票，那么就会立即确认自己是否和集群中其他服务器保持着有效的连接，如果没有连接，则马上建立连接，如果已经建立了连接，则再次发送自己当前的内部投票。

5、判断选举轮次。在发送完初始化选票之后，接着开始处理外部投票。在处理外部投票时，会根据选举轮次来进行不同的处理。

• 外部投票的选举轮次大于内部投票。若服务器自身的选举轮次落后于该外部投票对应服务器的选举轮次，那么就会立即更新自己的选举轮次(logicalclock)，并且清空所有已经收到的投票，然后使用初始化的投票来进行PK以确定是否变更内部投票。最终再将内部投票发送出去。
• 外部投票的选举轮次小于内部投票。若服务器接收的外选票的选举轮次落后于自身的选举轮次，那么Zookeeper就会直接忽略该外部投票，不做任何处理，并返回步骤4。
• 外部投票的选举轮次等于内部投票。此时可以开始进行选票PK。

6、选票PK。在进行选票PK时，符合任意一个条件就需要变更投票。

• 若外部投票中推举的Leader服务器的选举轮次大于内部投票，那么需要变更投票。
• 若选举轮次一致，那么就对比两者的ZXID，若外部投票的ZXID大，那么需要变更投票。
• 若两者的ZXID一致，那么就对比两者的SID，若外部投票的SID大，那么就需要变更投票。

7、变更投票。经过PK后，若确定了外部投票优于内部投票，那么就变更投票，即使用外部投票的选票信息来覆盖内部投票，变更完成后，再次将这个变更后的内部投票发送出去。

8、选票归档。无论是否变更了投票，都会将刚刚收到的那份外部投票放入选票集合recvset中进行归档。recvset用于记录当前服务器在本轮次的Leader选举中收到的所有外部投票（按照服务队的SID区别，如{(1, vote1), (2, vote2)…}）。

9、统计投票。完成选票归档后，就可以开始统计投票，统计投票是为了统计集群中是否已经有过半的服务器认可了当前的内部投票，如果确定已经有过半服务器认可了该投票，则终止投票。否则返回步骤4。

10、更新服务器状态。若已经确定可以终止投票，那么就开始更新服务器状态，服务器首选判断当前被过半服务器认可的投票所对应的Leader服务器是否是自己，若是自己，则将自己的服务器状态更新为LEADING，若不是，则根据具体情况来确定自己是FOLLOWING或是OBSERVING。

以上10个步骤就是FastLeaderElection的核心，其中步骤4-9会经过几轮循环，直到有Leader选举产生。

部分参考摘抄：倪超 著《从Paxos到Zookeeper 分布式一致性原理与实践 》