ZooKeeper(一)

Paxos算法

Basic Paxos

角色介绍

client,系统外部角色，请求发起者，向民众

Propser,接受Client请求,向集群提出提议(propose),并在发送冲突的时候，起到冲突调节的作用，向议员,替民众提出议案

Acceptor,提议投票和接受者，只有在形成发法定人数(Quorum),提议才会被接受，像国会

leaner,提议接受者，备份，对集群一致性没有说明影响，向记录员

分为两大步骤，每一步骤又分为两小步骤

1. prepare

proposer提出一个提案N,然后向Acceptor的某个超过半数的子集成员发送提案N的prepare请求

1. promise 如果N大于此Acceptor之前接受的任何提案编号则接受，否则拒绝
2. Accept 如果大多数人都接受，Proposer发出accept请求，此请求包含提案编号N,以及提案内容
3. Accepted 如果此时Acceptor在此期间没有收到任何编号大于N的提案，则接受此提案，否则忽略

基本流程

1. 客户端发起请求到proposer
2. proposer提出编号为1的提案,交给大多数Acceptor
3. Acceptor收到prepare进行讨论，得到最大的编号1，反馈给proposer
4. proposer收到了大部分Acceptor的响应，就会发出请求提案(1,Vn),Vn为最大编号的值,交给Acceptor
5. 当Acceptor接受到(1,Vn)的请求，只要该Acceptor尚未对更大编号prepare请求做出响应，这个提案就会通过

部分节点失败，但是绝大部分正常

上图在当Acceptor其中有一个节点失败了，但是存活的还是大多数进行了响应,因此后面的流程正常进行

proposer失败

1. 上图前面两部不变，但是在进行请求Accept的时候，proposer宕机
2. 此时分布式可用性体现出来，另外一个proposer就会重新发起一个提案2
3. 然后依次正常执行，最后(2,Vn)提案被选了出来

潜在的问题，就是活锁

正如我们最开始的步骤，第二步

2.promise
如果N大于此Acceptor之前接受的任何提案编号则接受，否则拒绝

当在进行第二步操作的时候，此时又来了一个提案编号是2，则Acceptor就会接受提案2，此时前一次的proposer看到自己的提案被替换了，就会在此提一个提案，编号为3，就这样一次类推，最后造成活锁

当然这个问题也很好解决，就是当第二个提案提出的时候，如果已经有提案了，我们可以等一会,这样当过一会第一个提案可能已经选了出来.

可以发现Basic Paxos有很多问题，难实现，效率低，发生活锁因此提出了优化

Multi Paxos

Leader唯一的propser，所有请求都需要经过此leader

1. 不管客户端是否有请求，proposer就会发出prepare(N),说我要当leader
2. 当Acceptor接受到请求之后，就你就当leader吧
3. 当客户端请求来的时候，就不用再次执行上限操作，此时只有一个leader的proposer，他就是N为领导，他提出提案编号为I,提案内容为Vm
4. 然后Acceptor收到请求，然后接受这个请求，对应的提案就会被选出来

这样当下次客户端请求的时候，此时领导还没有改变，就会直接提出I+1提案，提案的内容为w,不会产生冲突,然后进行流程选出提案，这样的好处节省了一次RPC请求，且这种算法也简化了角色。如下图

ZAB协议

所有事务请求必须有一个全局唯一的服务器来协调处理，这样的服务器就是leader,其余的其他服务器则成为Follower的服务器，Leader服务器就是负责一个客户端事务请求转换一个事务proposal，并提交proposal分发给其他follower,但其中大部分follower反馈可以的时候，leader服务器就会在再次向所有的Follower服务器分发commit消息，要求其将前一个proposal进行提交

ZAB要解决两个问题,设计两种模式

• 消息广播，把数据更新到多有follower
• 崩溃恢复模式，Leader发生崩溃时候，如何恢复

消息广播

消息广播类似一个二阶段提交，但是又不一样，是因为移除了中断逻辑,所有follower服务器要么正常反馈leader提出的事务proposal，要么抛弃leader服务器，同时ZAB协议将二阶段提交中的中断逻辑意味着我们不需要等到多有Folloer的反馈.

1. leader将客户端的request转化为一个propose
2. leader为每个Follower准备了一个FIFO队列,并把Proposal发送到队列上
3. leader接受到大多数Follower反馈
4. leader向所有follower发送commit

崩溃恢复

上面我们提到了二阶段的优化，移除了中断阶段，只要大多数follower的反馈，因此出现数据不一致的情况，且当leader服务器崩溃或者网络原因导致失去了过半follower的联系，因此崩溃恢复就起到了作用

基本特性

• ZAB协议需要确保那些已经在leader服务器上提交的事务最终被所有服务提交
• ZAB协议需要确保丢弃那些只在leader服务器上被提出的事务

leader在ZAB协议中是一个重要角色，正如生活中,部门的领导，如果领导离职了，公司肯定会重新选择一个leader组织，其中这个选择一个领导是一个非常重要的过程。如下过程

既然要当领导，每个人都希望自己是领导，因此就会投票选举，且会每个人都会有一个记录表，来记录这个信息，比如有三个人A,B,C

1. 成员A告诉BC要成为领导，BC记录下来(A成员广播)
2. B恢复可以，C恢复不可以
3. A收到B和C的回复更新自己的记录表
4. 此时A是2票，B0票，C0票
5. C也想当领导，而且给自己投了一票
6. B和A都同意了
7. C收到了AB的回复，更新记录表
8. 此时A0票，B0票，C3票，于是C成为领导了

整个选举过程，并且每个人选举，都代表了一个事件，为了保证分布式系统的时间有序性，因此每个事件都分配了一个ZXID,相当一个编号，64位的数字，高32代表了leader周期epoch编号，每当选举产生一个新的leader服务器，就会从这个leader服务器中解析最大事务proposal的ZXID，然后取出高32位的epoch加1,低32为代表一个事务计数器，产生一个事务就会累计1操作。

崩溃恢复基本过程

1. 选取当前最大的ZXID代表当前事件的最新的
2. 选举的新的leader把这个事件proposal提交给其他follower节点
3. follower节点会根据leader的消息进行回退或者数据同步操作，最终目的就是要达到所有节点的数据副本保持一致

1.Leader election（选举阶段）：节点在一开始都处于选举阶段，只要有一个节点得到超半数节点的票数，它就可以当选准 leader。
2. Discovery（发现阶段）：在这个阶段，followers 跟准 leader 进行通信，同步 followers 最近接收的事务提议。
3. Synchronization（同步阶段）：同步阶段主要是利用 leader 前一阶段获得的最新提议历史，同步集群中所有的副本。同步完成之后 准 leader 才会成为真正的 leader。
4. Broadcast（广播阶段）：到了这个阶段，Zookeeper 集群才能正式对外提供事务服务，并且 leader 可以进行消息广播。同时如果有新的节点加入，还需要对新节点进行同步。

ZAB和Paxos算法区别

相同点

• 两者都有类似leader角色，负责协调follower进行
• Leader都是超过多半数的follower做出正确反馈后，才会将一个提案提交

不同点

• ZAB协议，每个proposal都包含一个epoch值代表当前的leader周期，paxos中的名字Ballot
• ZAB用来构建高可用的分布式数据主备系统(zookeeper)，Paxos用来构建分布式一致性状态机系统
• 在paxos算法中，一个新的选举的主进程会进行两个阶段的工作，第一阶段读阶段，这个新的主进程会通知和所有其他进程通信的方式收集上一个主进程提出的提案，第二阶段是写阶段，这阶段开始提交他自己的提案，而ZAB添加了同步阶段，在同步阶段之前，ZAB协议也存在一个和Paxos算法中阶段类似过程的发现阶段，在同步阶段中，新的leader可以确保在过半的follower已经提交了之前leader周期中的所有事务proposal，这个同步阶段,能够有效的保证leader在新的周期提出事务之前，所有的进程都已经完成了对之前所有的事务proposal的提交。

Leader如何选举

server id(sid),服务id,比如有三台服务器，编号分别是1，2，3

zxid:事务id,服务器存放的数据事务id,值越大说明数据越新

Epoch,投票的次数即第几代领导

server状态，LOOKING,竞选状态，FOLLOWING,随从状态，参与投票，OBSERVING,观察状态，不参与投票，leading,领导者状态

首先要明白几个东西，zookeeper节点是根据什么进行比较选举成leader,首先比较的是事物id即zxid(节点越新zxid就越大)，如果zxid一样，就比较sid,即集群节点的唯一标识

什么时候进行选举的

• 服务初始化
• 服务器运行期间leader宕机

服务器初始化

服务1启动

服务1感觉自己可以当领导，就会投自己一票，不够半数以上，选举无法完成

此时投票结果，服务器1位1票，状态为LOOKING

服务2启动

服务2启动也感觉自己可以，投自己一票，但是和服务1交流得出，服务2的id比较大，因此更改服务1的投票，选择投给了服务2，此时达到了半数，因此此时服务2就变成了leader,同时更改服务1的状态为follower

服务3启动

此时服务1，2，已经不是looking状态了，不会更改投票信息了，且已经有了leader,因此服务4虽然此时投了自己一票，但是和其他服务器交流，然后还是更改了投票给了服务2,然后此时服务3的状态改成了Following

最终服务2成为了leader,其他服务是follower

运行期间leader宕机进行新的leader选举

此时集群leader宕机，

1. 状态变更，leader故障后，余下的Follower状态变成了Looking,然后进行新的选举
2. 每个server发出投票
3. 接受到各个服务器的投票,如果其他服务器的数据比自己的新会改投票
4. 处理和统计投票，每一轮投票结果都会统计投票，超过半数可当选
5. 改变服务器的状态，宣布当选

如上图，每个服务器都会先选择自己，然后每个台机器会将自己的投票发给其他机器，如果比自己的zxid大，就会重新投一次，比如server1收到三张偷拍哦，发现server2的zxid为102,因此修改自己的投票，给了server2，最终server2成为了leader.