Paxos算法
Paxos算法是一种基于消息传递的具有高容错性的一致性算法,Paxos算法是一种公认的晦涩难懂的算法,并且实现它有很大难度。比较有名的工程是实现有Google Chubby,ZAB,微信的PhxPaxos等。
Paxos和拜占庭问题
拜占庭将军问题,是由Paxos算法作者提出的在对点对点通讯的基本问题,该问题的基本含义就是,在存在消息丢失且不可靠信道上试图使用消息传递达到一致性是不可能的,而Paxos算法的前提是不存在拜占庭将军的问题
即信道是安全 ,可靠的且不被篡改的,实际工程中,大多数系统中系统部署在局域网中,消息被篡改的情况很少,且网络中存在的消息不完整性也不是问题,只需要实现一条简单的验证算法即可,因此整个过程不存在拜占庭将军问题。
算法描述
三种角色
proposer:提案的提议者
Acceprot:提案的表决者
Learners:提案的学习者,当提案被选定后,其会同步并执行提案
一致性算法的可以保证以下几点
Paxos算法包含两个阶段,准备阶段prepare和接受阶段accept
准本阶段
接受阶段
算法举例
假设有三台机器,他们分别在不同时期充当提议者,表决者,学习者,三种角色,每一个提议者(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的状态描述三种描述,同步模式,恢复模式,广播模式
zxid
zxid是一个64位long类型,有两部分组成,其中高32位是纪元epoch,低32位是事务xid.
每一个leader都会有不同的epoch,表示不同的时期,每一次选举后,都会生成一个epoch,Leader会更新其他zkserver的epoch,zxid是事务的一个事物id每一个事务都会有一个zxid,zxid是一个自增流水号,每一个写操作都需要Leader发起一个提案,等大多数Follower表决是否同意,每个提案都会有一个zxid.
未完待更新