Zookeeper基础篇---面试Paxos算法

Paxos算法

Paxos算法是一种基于消息传递的具有高容错性的一致性算法，Paxos算法是一种公认的晦涩难懂的算法，并且实现它有很大难度。比较有名的工程是实现有Google Chubby,ZAB,微信的PhxPaxos等。

Paxos和拜占庭问题

拜占庭将军问题，是由Paxos算法作者提出的在对点对点通讯的基本问题，该问题的基本含义就是，在存在消息丢失且不可靠信道上试图使用消息传递达到一致性是不可能的，而Paxos算法的前提是不存在拜占庭将军的问题

即信道是安全 ,可靠的且不被篡改的，实际工程中，大多数系统中系统部署在局域网中，消息被篡改的情况很少，且网络中存在的消息不完整性也不是问题，只需要实现一条简单的验证算法即可，因此整个过程不存在拜占庭将军问题。

算法描述

三种角色

proposer:提案的提议者

Acceprot:提案的表决者

Learners:提案的学习者，当提案被选定后，其会同步并执行提案

一致性算法的可以保证以下几点

1. 没有提案被提出则不会有提案被选定
2. 每个提议者提出提案都会指定一个唯一的全局标识，递增编号N，在集群中是唯一的
3. 每个表决者接受该提案后，都会保存该提案的编号N到本地，这样每个表决者都会保存进一个提案的最大编号，即maxN,每个表决者只会接受大于本地maxN的提案
4. 众多提案最终只有一个提案被选定
5. 当提案选定之后，会同步到其他服务器的本地

Paxos算法包含两个阶段，准备阶段prepare和接受阶段accept

准本阶段

1. 提议者准备提交一个编号为N的提议，于是先向所有表决者发送prepare(N),试探性的是否支持该编码的提议
2. 每个表决者保存着曾经接收过提案的最大编号maxN,当表决者接受主机发送的prepare(N)后，会拿自己曾经最大的编号maxN和N进行比较，当N小于maxN时，表决者会不回应或返回error的形式回应提议者的提案prepare(N)的请求，当N大于maxN时，表决者可以接受此提案，表决者把曾经已经接受编号的最大提案prepare(myid,maxN,value),第一位参数是表决者的表示id,第二参数是表决者曾经接受提案的最大编号maxN,第三个参数是该提案的真正内容，当然，如果表决者没有接受过提案，则会将提案Proposal(myid,null,null)反馈给提议者。

接受阶段

1. 当提议者发出prepare(N)后,若收到超过多数的表决者的响应，那么该提议者就会将真正的提案Proposal(N,value)发送给所有表决者
2. 当表决者接受到提议者发送的Proposer(N,value)后，会再次拿出自己曾经接受过的提议中最大的标号maxN,以及曾经反馈过prepare最大编号，当N小于这两个编号的时候，则不响应拒绝或error形式拒绝，当N大于这个两个编号，表决者接受此提案，并反馈给提议者
3. 若提议者没有收到多数的的反馈，则重新进入prepare,递增提案编号，重新提交提案，若超过多数表决者的反馈，则其他未向提议者反馈的接受的表决者成为learner,主动同步 提议者的提案。

算法举例

假设有三台机器，他们分别在不同时期充当提议者，表决者，学习者，三种角色，每一个提议者(Proposer)可以向所有的表决者(Acceptor)投票自己当Leader,假设三个提议者是Proposer-1,Proposer-2,Proposer-3他们的编号是20，10，30，为了举例好理解，我们的Proposer-1向Acceptor-1,Acceptor-2发送消息，Proposer-2向Acceptor-2,Acceptor-3发送消息，Proposer-3向Acceptor-2,Acceptor-3发送消息。

Prepare阶段

假设Proposer-1发送 prepare(20)消息先到达Acceptor-1和Acceptor-2,因为之前他们没有接受过请求，所以他们都是直接接受该请求，并将Proposal(server1,null,null)和Proposal(server2,null,null)反馈给Proposer-1,同时Acceptor-1和Acceptor-2记录下期目前收到做大的提案的编号20，即以后不再接受小于20编号的天，Proposer-1收到超过半数的反馈

Proposer-2发送prepare(10)消息发送给Acceptor-2和Acceptor-3,由于Acceptor-3还没有接受到其他请求，所以其直接接受Proposer-2的prepare(10)的请求，Acceptor-2只能接受大于标号20的提案，所以Acceptor-2拒绝Proposer-2的prepare(10)请求，Proposer-2仅收到一个反馈，未超过半数的反馈。

Proposer-3的prepare(30)请求消息到达Acceptor-2和Acceptor-3，他们都接受过请求，但是编号30的消息大于Acceptor-2和Acceptor-3，他们都可以接受该prepare(30)请求，由于Acceptor-2和Acceptor-3虽然接受过prepare请求，但是未真正接受过提案，所以他们在接受prepare(30)请求是反馈给Proposer-3仍是Proposal(server2,null,null)和Proposal(server3,null,null),Proposer-3收到超过半数的反馈。

由于Proposer-2没有收到过半的的回复，所以其为提案重新制定编号40，并发送给Acceptor-2和Acceptor3,此时编号40大于他们已经接受的提案编号30，所以接受该请求，并将Proposal(server2,null,null)与Proposal(server3,null,null)返回给Proposer-2,Proposer-2反馈超过半数

截止到目前，Acceptor-1,Acceptor-2,Acceptor-3接受到最大的编号分别是20，40，40.(注意，并不是所有的Proposer都必须达到半数才能进入第二阶段，这里只是其中一种)

accept阶段

prposer-1收到反馈过半，且这些反馈表示自己支持提案意愿，即反馈value为null,所以就直接向Acceptor-1和Acceptor-2提交了Proposal(server1-id,20,server1)

prposer-2收到反馈过半，且这些反馈表示自己支持提案意愿，即反馈value为null,所以就直接向Acceptor-2和Acceptor-3提交了Proposal(server2-id,40,server2)

prposer-3收到反馈过半，且这些反馈表示自己支持提案意愿，即反馈value为null,所以就直接向Acceptor-2和Acceptor-3提交了Proposal(server3-id,30,server3)

Acceptor的表决

Acceptor-1和Acceptor-2接受到Proposer-1的提案Proposal(server1-id,20,server1),由于Acceptor-1不能接受小于20的提案，但可以接受等于20的提案,所以通过该提案，但由于Acceptor-2不能接受编号小于40的提案，所以拒绝该提案。

Acceptor-2和Acceptor-3接受到Proposer-2的提案Proposal(server2-id,40,server2),他们均通过了该提案。

Acceptor-2和Acceptor-3接受到Proposer-3的提案Proposal(server3-id,30,server3),他们拒绝了该提案

最后，由于Acceptor-2和Acceptor-3已经通过天Proposal(server2-id,40,server2),并达成了半数的一致性，server2马上成为Leader,选举结束server2会发布广播所有的Learner,通知他们来同步数据，同步完成后，集群进入正常服务状态。

Paxos算法优化

前面介绍的Paxos算法在实际工程中有许多的不便，所以对于Paxos算法的优化出现了许多的方案,例如，Multi Paxos、Fast Paxos、EPaxos。而 Zookeeper 的 Leader 选举算法 FastLeaderElection 则是 Fast Paxos 算法的工程应用。

ZAB协议

ZAB,Zookeeper Atomic Broardcast,zk原子消息广播协议，是专门为zookeeper设计的一种支持崩溃恢复的原子消息广播协议，是Paxos算法的优化方案，是一种实现zookeeper依赖ZAB协议的来实现分布式数据一致性。

zookeeper使用一个单一主进程接受并处理客户端的所有事物请求，即写请求，当服务器数据发生变更时候，集群使用ZAB原子广播协议，以事物提案Proposal的形式广播到其他副节点，ZAB保证会为一个全局的变更序列，即可以为每个事物分配一个递增的编号zxid.

当zookeeper连接到集群的一个节点的时候，当客户端发来一个请求，如果是读请求，则当前节点按照本地的数据进行相应，但是如果是写请求且不是Leader节点，则把写请求转发到Leader节点，Leader节点把请求广播到其他节点，超过半数节点同意此写请求，Leader节点提交此写请求，在广播到其他订阅者，通知他们进行同步数据。

zookeepre三类角色

为了处理zookeeper的单点问题，zookeeper一般是以集群的形式使用，其中会有三种角色

Leader:是唯一处理写请求的处理者，具有投票的发起和决策能力，更新系统数，并且他是很民主的，他不是直接出来写请求，会把写请求广播到其他zkserver,zkserver大多数同意后，才会去执行写请求 。

Follower:处理客户端的读请求，并把写请求转发给Leader,在选举过程中起到投票的能力

Observer:可以理解为没有选主投票权和写请求投票权的Follower,其不属于法定人数范围，主要是为了协助Follower处理读请求，若zookeeper服务的压力非常高的时候，势必会增加服务器的数量，若都已Follower的角色增加，会影响写请求的效率，因为Leader的写请求必须通过法定人数大多数统一，因此增加Folloer会增加通讯的负担，并且选主的时间也会增加，此时，可以通过增加Observer的数量，且不再增加法定人数，也可以提高读请求的效率，也不会增加通讯的压力，都不会影响投票效率.

三种模式

ZAB协议对zkserver的状态描述三种描述，同步模式，恢复模式，广播模式

• 恢复模式:在服务器重启过程中，或在Leader崩溃中回复，就进入了恢复模式，要恢复到zkserver可以服务的状态
• 同步模式:在服务启动时，会崩溃后重新选举Leader后，就进入了同步模式，各个Folloer同步Leader的数据到自己的主机中，当大多数Follower同步完成之后，恢复模式就结束了，同步模式包含恢复模式。
• 广播模式:当大多数zkserver大多数统一提案之后，Leader更新完数据之后，然后把修改的数据广播到其他Follower.

zxid

zxid是一个64位long类型，有两部分组成，其中高32位是纪元epoch,低32位是事务xid.

每一个leader都会有不同的epoch，表示不同的时期，每一次选举后，都会生成一个epoch,Leader会更新其他zkserver的epoch，zxid是事务的一个事物id每一个事务都会有一个zxid,zxid是一个自增流水号，每一个写操作都需要Leader发起一个提案，等大多数Follower表决是否同意，每个提案都会有一个zxid.

未完待更新