fast-paxos算法与zookeeper-leader选举源代码分析.doc

fastpaxos算法与Zookeeperleader选举源代码分析雷明******@1、、分布式一致性问题在分布式系统中,有多个节点(服务器),这些节点可以为客户(客户端)提供某种服务。这至少带来两个好处:一方面可以提供性能,另一方面可以提供容错,当部分服务器挂掉之后,不影响整个服务。但是问题又来了:如果多个服务器节点修改同一个变量,后果会怎么样?、paxos算法paxos算法是一个基于消息传递的一致性算法,在1990年由Lamport提出,最近被广泛的应用于分布式计算中。Google的Chubby,Apache的Zookeeper都是基于该理论实现。Paxos被认为是到目前为止唯一正确的分布式一致性算法,其他的算法都是Paxos的改进或者简化。、fastpaxos算法问题提出:在分布式系统中,需要选举出一个leader节点,只有该节点可以做出决策。问题:怎么在n个节点中选择一个作为leader?方法一:指定某一个节点作为leader,问题:这个leader挂了怎么办? 方法二:给每个节点指定一个唯一的id,比较所有节点的id,id最大的为leader,问题:怎么知道活着的id中,哪个是最大的? 要解决的问题: 1、什么时候发起选举? 2、选举过程中,后加入的节点怎么办? 3、一个节点挂掉后重启,要发起选举,怎么办? 选举轮数的新旧: 每个节点的数据的新旧(选举结果) 有多个节点都活着,在同一轮选举中,选择哪个节点作为leader?2、、概述Zookeeper集群中,只有一个节点是leader节点,其他节点都是follower节点(实际上还有observer节点,不参与选举的投票,在这里我们先忽略,下同)。所有的更新操作,必须经过leader节点,leader节点和follower节点之间保持着数据同步和心跳。客户端使用zookeeper时,可能会连到follower身份的server上,也可能会连到leader身份的server上。三类角色的分工如下:Leader:处理写请求,单点Follower:处理客户端请求,参与投票Observer:不参与leader选举的投票,只处理客户端请求在一个zookeeper集群里,有多少个server是固定的,每个节点有一个唯一的id,标识它自己,另外,每个server还有用于选举的IP和port,这些都在配置文件中。一个具体的例子如下:=:2888:=:2888:=:2888:3888这里有3个server,其id分别为1、2、3。2888为节点和leader交换信息的端口,3888为选举的端口。这个节点的id,在投票时,用户标识参加竞选的节点的身份。问题:这个leader节点是怎么确定的?答案:zookeeper系统自己选举出来的,所有的server节点(observer除外),都参与这个选举。这样做的好处是:当现在的leader挂掉了之后,系统可以重新选举一个节点做leader。Zookeeper的选举算法能保证:只要超过半数的节点还活着,就一定能选举出唯一个一个节点作为leader。、节点的状态 Zookeeper中的节点有以下三种状态(忽略observer节点): LOOKING:初始化状态,处于选举过程中,leader还没有选出 LEADING:leader已经选出,本节点是leader FOLLOWING:leader已经选出,、选举发生的时机 当任何一个节点进入looking状态时,选举开始,进入looking状态有如下原因: 1、节点刚启动,使自己进入选举状态 2、发现leader节点挂掉了Zookeeper中的leader怎么知道follower还活着?follower怎么知道leader还活着?leader会定时向follower发ping消息;follower会定时向leader发ping消息。当发现无法ping通leader时,就会将自己的状态改为LOOKING,并发起新的一轮选举。处于选举模式时,zookeeper的服务不可用。、一个节点成为leader的条件 一个节点要成为leader,必须得到至少n/2+1(即半数以上节点)的投票,实际上,在实现时,还可以考虑其他规则,比如节点权重。 为什么要保证至少n/2+1的节点同意?因为这样能保证本节点得到多数派的支持。因为每一个节点,只能支持一个节点成为leader,因此,只要一个节点获得至少n/2+1的选票,就一定会比其他任何节点得到的选票多。 这个规