paxos 实现
本文主要介绍zookeeper中zookeeperServerleader的选举，zookeeper在选举leader的时候采用了paxos算法(主要是fastpaxos)，这里主要介绍其中两种：LeaderElection和FastLeaderElection.
我们先要清楚以下几点
•一个Server是如何知道其它的Server
在zookeeper中,一个zookeeper集群有多少个Server是固定，每个Server用于选举的IP和PORT都在配置文件中
•除了IP和PORT能标识一个Server外，还有没有别的方法
每一个Server都有一个数字编号，而且是唯一的，我们根据配置文件中的配置来对每一个Server进行编号，这一步在部署时需要人工去做，需要在存储数据文件的目录中创建一个文件叫myid的文件，并写入自己的编号,这个编号在处理我提交的value相同很有用
•成为Leader的必要条件
获得n/2+1个Server同意(这里意思是n/2+1个Server要同意拥有zxid是所有Server最大的哪个Server)
•zookeeper中选举采用UDP还是TCP
zookeeper中选举主要是采用UDP，也一种实现是采用TCP，在这里介绍的两种实现采用的是UDP
•zookeeper中有哪几种状态
LOOKING初始化状态
LEADING领导者状态
FOLLOWING跟随者状态
•如果所有zxid都相同(例如:刚初始化时),此时有可能不能形成n/2+1个Server，怎么办
zookeeper中每一个Server都有一个ID,这个ID是不重复的，而且按大小排序，如果遇到这样的情况时，zookeeper就推荐ID最大的哪个Server作为Leader
•zookeeper中Leader怎么知道Fllower还存活，Fllower怎么知道Leader还存活
Leader定时向Fllower发ping消息，Fllower定时向Leader发ping消息，当发现Leader无法ping通时，就改变自己的状态(LOOKING)，发起新的一轮选举
名词解释
zookeeerServer：zookeeper中一个Server,以下简称Server
zxid(zookeepertranstionid)：zookeeper事务id，他是选举过程中能否成为leader的关键因素，它决定当前Server要将自己这一票投给谁(也就是我在选举过程中的value,这只是其中一个,还有id)
myid/id(zookeeperserverid)：zookeeperserverid，他也是能否成为leader的一个因素
epoch/logicalclock：他主要用于描述leader是否已经改变,每一个Server中启动都会有一个epoch,初始值为0,当开始新的一次选举时epoch加1,选举完成时epoch加1。
tag/sequencer：消息编号
xid：随机生成的一个数字，跟epoch功能相同
FastPaxos消息流向图与BasicPaxos的对比
消息流向图
•basicpaxos消息流向图
ClientProposerAcceptorLearner
|||||||
X-------->||||||Request
|X--------->|->|->|||Prepare(N)//向所有Server提议
||<---------X--X--X||Promise(N,{Va,Vb,Vc})//向提议人回复是否接受提议(如果不接受回到上一步)
|X--------->|->|->|||Accept!(N,Vn)//向所有人发送接受提议消息
||<---------X--X--X------>|->|Accepted(N,Vn)//向提议人回复自己已经接受提议)
|<---------------------------------X--XResponse
|||||||
•fastpaxos消息流向图
没有冲突的选举过程
ClientLeaderAcceptorLearner
||||||||
|X--------->|->|->|->|||Any(N,I,Recovery)
||||||||
X------------------->|->|->|->|||Accept!(N,I,W)//向所有Server提议，所有Server收到消息后，接受提议
||<---------X--X--X--X------>|->|Accepted(N,I,W)//向提议人发送接受提议的消息
|<------------------------------------X--XResponse(W)
||||||||
第一种实现:LeaderElection
LeaderElection是Fastpaxos最简单的一种实现，每个Server启动以后都询问其它的Server它要投票给谁，收到所有Server回复以后，就计算出zxid最大的哪个Server，并将这个Server相关信息设置成下一次要投票的Server
每个Server都有一个response线程和选举线程,我们先看一下每个线程是做一些什么事情
response线程
它主要功能是被动的接受对方法的请求，并根据当前自己的状态作出相应的回复，每次回复都有自己的Id，以及xid，我们根据他的状态来看一看他都回复了哪些内容
LOOKING状态：
自己要推荐的Server相关信息(id,zxid)
LEADING状态
myid,上一次推荐的Server的id
FLLOWING状态:
当前Leader的id，以及上一次处理的事务ID(zxid)
选举线程
选举线程由当前Server发起选举的线程担任，他主要的功能对投票结果进行统计，并选出推荐的Server。选举线程首先向所有Server发起一次询问(包括自己)，被询问方，根据自己当前的状态作相应的回复，选举线程收到回复后，验证是否是自己发起的询问(验证xid是否一致)，然后获取对方的id(myid)，并存储到当前询问对象列表中，最后获取对方提议的leader相关信息(id,zxid)，并将这些信息存储到当次选举的投票记录表中，当向所有Server都询问完以后，对统计结果进行筛选并进行统计，计算出当次询问后获胜的是哪一个Server，并将当前zxid最大的Server设置为当前Server要推荐的Server(有可能是自己，也有可以是其它的Server，根据投票结果而定，但是每一个Server在第一次投票时都会投自己)，如果此时获胜的Server获得n/2+1的Server票数，设置当前推荐的leader为获胜的Server，将根据获胜的Server相关信息设置自己的状态。每一个Server都重复以上流程，直到选出leader
了解每个线程的功能以后，我们来看一看选举过程
•选举过程中，Server的加入
当一个Server启动时它都会发起一次选举，此时由选举线程发起相关流程，那么每个Server都会获得当前zxid最大的哪个Server是谁，如果当次最大的Server没有获得n/2+1个票数，那么下一次投票时，他将向zxid最大的Server投票，重复以上流程，最后一定能选举出一个Leader
•选举过程中，Server的退出
只要保证n/2+1个Server存活就没有任何问题，如果少于n/2+1个Server存活就没办法选出Leader
•选举过程中，Leader死亡
当选举出Leader以后，此时每个Server应该是什么状态(FLLOWING)都已经确定，此时由于Leader已经死亡我们就不管它，其它的Fllower按正常的流程继续下去，当完成这个流程以后，所有的Fllower都会向Leader发送Ping消息，如果无法ping通，就改变自己的状态为(FLLOWING==>LOOKING)，发起新的一轮选举
•选举完成以后，Leader死亡
这个过程的处理跟选举过程中Leader死亡处理方式一样，这里就不再描述
第二种实现:FastLeaderElection
fastLeaderElection是标准的fastpaxos的实现，它首先向所有Server提议自己要成为leader，当其它Server收到提议以后，解决epoch和zxid的冲突，并接受对方的提议，然后向对方发送接受提议完成的消息
数据结构
本地消息结构：
staticpublicclassNotification{
longleader;//所推荐的Serverid
longzxid;//所推荐的Server的zxid(zookeepertranstionid)
longepoch;//描述leader是否变化(每一个Server启动时都有一个logicalclock，初始值为0)
QuorumPeer.ServerStatestate;//发送者当前的状态
InetSocketAddressaddr;//发送者的ip地址
}
网络消息结构：
staticpublicclassToSend{
inttype;//消息类型
longleader;//Serverid
longzxid;//Server的zxid
longepoch;//Server的epoch
QuorumPeer.ServerStatestate;//Server的state
longtag;//消息编号
InetSocketAddressaddr;
}
Server具体的实现
每个Server都一个接收线程池(3个线程)和一个发送线程池(3个线程),在没有发起选举时，这两个线程池处于阻塞状态，直到有消息到来时才解除阻塞并处理消息，同时每个Server都有一个选举线程(可以发起选举的线程担任)；我们先看一下每个线程所做的事情，如下：
被动接收消息端(接收线程池)的处理:
notification：首先检测当前Server上所被推荐的zxid,epoch是否合法(currentServer.epoch<=currentMsg.epoch&&(currentMsg.zxid>currentServer.zxid||(currentMsg.zxid==currentServer.zxid&¤tMsg.id>currentServer.id)))如果不合法就用消息中的zxid,epoch,id更新当前Server所被推荐的值，此时将收到的消息转换成Notification消息放入接收队列中，将向对方发送ack消息
ack:将消息编号放入ack队列中，检测对方的状态是否是LOOKING状态，如果不是说明此时已经有Leader已经被选出来，将接收到的消息转发成Notification消息放入接收对队列
主动发送消息端(发送线程池)的处理:
notification:将要发送的消息由Notification消息转换成ToSend消息，然后发送对方，并等待对方的回复,如果在等待结束没有收到对方法回复，重做三次,如果重做次还是没有收到对方的回复时检测当前的选举(epoch)是否已经改变，如果没有改变，将消息再次放入发送队列中，一直重复直到有Leader选出或者收到对方回复为止
ack:主要将自己相关信息发送给对方
主动发起选举端(选举线程)的处理:
首先自己的epoch加1，然后生成notification消息,并将消息放入发送队列中，系统中配置有几个Server就生成几条消息，保证每个Server都能收到此消息,如果当前Server的状态是LOOKING就一直循环检查接收队列是否有消息，如果有消息，根据消息中对方的状态进行相应的处理。
LOOKING状态:
首先检测消息中epoch是否合法，是否比当前Server的大,如果比较当前Server的epoch大时，更新epoch，检测是消息中的zxid,id是否比当前推荐的Server大，如果是更新相关值，并新生成notification消息放入发关队列，清空投票统计表；如果消息小的epoch则什么也不做；如果相同检测消息中zxid,id是否合法,如果消息中的zxid，id大，那么更新当前Server相关信息，并新生成notification消息放入发送队列，将收到的消息的IP和投票结果放入统计表中，并计算统计结果，根据结果设置自己相应的状态
LEADING状态:
将收到的消息的IP和投票结果放入统计表中(这里的统计表是独立的)，并计算统计结果，根据结果设置自己相应的状态
FOLLOWING状态:
将收到的消息的IP和投票结果放入统计表中(这里的统计表是独立的)，并计算统计结果，根据结果设置自己相应的状态
了解每个线程的功能以后，我们来看一看选举过程,选举过程跟第一程一样
•选举过程中，Server的加入
当一个Server启动时它都会发起一次选举，此时由选举线程发起相关流程，通过将自己的zxid和epoch告诉其它Server，最后每个Server都会得zxid值最大的哪个Server的相关信息，并且在下一次投票时就投zxid值最大的哪个Server，重复以上流程，最后一定能选举出一个Leader
•选举过程中，Server的退出
只要保证n/2+1个Server存活就没有任何问题，如果少于n/2+1个Server存活就没办法选出Leader
•选举过程中，Leader死亡
当选举出Leader以后，此时每个Server应该是什么状态(FLLOWING)都已经确定，此时由于Leader已经死亡我们就不管它，其它的Fllower按正常的流程继续下去，当完成这个流程以后，所有的Fllower都会向Leader发送Ping消息，如果无法ping通，就改变自己的状态为(FLLOWING==>LOOKING)，发起新的一轮选举
•选举完成以后，Leader死亡
这个过程的处理跟选举过程中Leader死亡处理方式一样，这里就不再描述
【转自淘宝核心团队博客】：http://rdc.taobao.com/blog/cs/?p=162