学步园

FastLeaderELection选举算法是类fast paoxs的算法，由于网上分析该算法的文章比较多，所以我这里就不重复这些工作了，直接从实现的角度进行考虑，事实上，在实现上，还是有许多细节需要考虑，就像初始的设计总是不是那么的完美，往往在实现的时候才能更新的看清问题。因此，我把在设计和实现中遇到的问题总结写出来，

一、选举算法设计和分析中遇到的问题

分布式系统中，节点的状态各个时刻可能都是不一样，在zookeeper中，选举实际上主要有3种状态，LOOKING,FOLLOWING,LEADING，这里我假设有4个节点，分别为A,B,C,D，各自的id(zookeeper中是sid)4， 3， 2， 1，那么这个分布式系统中，可能存在的情况[A(4,3)组合]共有24种，我在这里列出其中的几种情况，其他的情况分析相似

第一种情况分析：节点都是LOOKING条件下

1.1. 首先要明确一下推荐leader的标准是什么，这里我列了三点，分别为

• 推荐的节点的纪元比当前的节点的纪元要大，可以举个列子，有一个人从秦代穿越过来，一个是现代人，如果我们想选择哪个人更加了解历史，我们一般会选择现代人。
• 如果不满足第一点，则比较节点的更新操作，更新比较频繁的节点则推荐该节点id，举个例子，两个都是现代人，我们会选择那个拼命学习历史知识的人。
• 如果还是不能满足上面两点，则推荐id大，比如说，我们选择那个身份证比较大的人

但是，有一点需要明确，推荐的leader并不意味着最终选举出来的leader就是该id，而最终判断某个节点为leader则是看是否获得的票数是最多的。

1.2. 什么时候发起(paxos accept阶段)投票？

• 发起一轮投票的时候，群发推荐的投票(初始为自己的id)
• 超过一定时间内，没有收到它人的投票，群发推荐的投票
• 更新了我的推荐的leader id，群发推荐的投票

1.3. 如何判断是否是同一轮的投票？用一个字段进行表示logicalClock（每次启动一轮选举，都会自增），如果是同一轮选举，则这字段不一样，否则就不是同一轮选举。

1.4. 如何认为某一票是有效的？如果logicalClock大于或者等于当前的这个字段，则认为是该票是有效的，另外，一个节点仅投一票，最新的票会覆盖掉它过去的票

第二种情况分析：节点的状态是有FOLLOWING和LOOKING

先分析FOLLOWING状态的节点

2.1 当前是FOLLOWING状态，那么收到的投票，怎么处理？直接处理掉(选举完成后，并不会把后台接收发送线程关闭，在文章后一部分用图示表示了这一部分)！如果收到的投票中发现对方还是LOOKING状态，直接把我当前的leader 的id发送给它，其他情况则丢弃该票

2.2. 进入到FOLLOWING状态，需要做什么？需要和当前的leader进一步确认，与leader重新建立TCP连接，等待Leader的NEWLEADER消息，并发送一个ACK消息进行确认，此操作是为了避免出来两个leader的情况(我在后边分析LEADING情况说明这种出现的可能情况，并说明为什么确认后就不会有两个leader的分析)。

再分析LOOKING状态的节点，此时它可能收到两种票，来自FOLLOWING节点和来自LOOKING节点的票

2.3. 如果是LOOKING的票怎么处理？这个和上面的第一种情况分析是一样的

2.4. 如果是FOLLOWING的票怎么处理？关键在这个FOLLOWING状态，到底是本轮的选出来的FOLLOWING呢？还是不是本轮(如上一轮或者比当前节点更新的)的选出来的FOLLOWING？因此，需要做个判断，如果是本轮的，可以认为该票和其他LOOKING投票是等效的；但是如果不是本轮的票呢？在这里zookeeper似乎没有做处理，而是不管是更(第四声)新的还是上几轮的票，都一并做了放入到另一个队列。所以这样的操作是很关键的，如果没有这么操作，在这样一种情况，LOOKING状态的节点有问题

第三种情况分析：

此时，有三种状态FOLLOWING、LOOKING、LEADING

FOLLOWING和LOOKING状态的节点的处理和第二种情况的分析是一样的

LEADING状态的分析

3.1. 进入到LEADING状态的leader，需要开启TCP等待，等待FOLLOWING的节点建立连接，建立连接后FOLLOWING发送一个NEWLEADER消息，并等待FOLLOWING的ACK，如果在这个过程中，收到的ACK不到达大多数(quorum)，则重新选leader

3.2. 如果出现两个Leader，上边3.1的操作方法是否能避免？可以，假设有N个节点，如果有N/2+1个节点连接了某一leader，则另一个leader不会形成大多数的情况，即另一个节点收不到N/2+1个节点的ACK确认。

3.3. 为什么可能出现两个leader？假设如上四个节点[A(id=1)， B(id=2)， C(id=3)， D(id=4)]，都刚刚启动，这意味着这些节点只有id上的可比性（因为其他都一样），D有网络延迟，很快A,B,C选出C是leader，但A或者B（或者两者）没有进入到FOLLOWING之前，收到D的投票，这样就出现了两个leaderC和D，接下来可能的一种情况是A给C发送ACK消息，B给D发送ACK消息，但两者都打不到大多数的，所以只有进入重新选举了，所以上边3.1的这种方法能够有效的防止两个leader的问题

4.4. LEADER收到投票如何处理？这个处理与第二种情况2.1类似

4. 选举算法部分的设计图示

设计图示

可以看到，后台线程在整个生命周期都是在运行的，而选举线程在只在选举的时候有作用。

二、心跳同步部分

在完成选举后，就开始进入到心跳同步过程，虽然这部分，我觉得并没有选举算法那么多的细节，但是我觉得这部分的设计非常的有趣，是非常直接推荐的，因此，我在设计过程中，也借鉴了它的这种设计方法，下面我用一副图尽量简洁表示一下大致的框架

sync主要操作是当前leader的时钟计数器tick与Handler的时间计数器tickOfLastAck进行比较，tick是每隔一定时间会+1，而tickOfLastAck是在follower有响应数据则加+1，通常情况是会有心跳，所有tickOfLastAck就是+1，另外，还有一个同步的超限syncLimit，即tickOfLastAck
大于或者等于leader.self.tick - leader.self.syncLimit，则表示Follower是存活的，否则，Leader会认为Follower挂了，这样就会移除Handler，此时，Follower会自己启动一轮新的选举。

三、数据通信

由于使用了Hadoop Record，所以通信可以很简单地就支持C/C++/JAVA/C#等扩展，就样像thrift、Protocol Buffers一样解决通信数据问题，当然后两者支持的语言更多，支持的功能也更广泛。

我把代码提交到google code，如果有同学感兴趣，可以checkout出来：

svn checkout https://election.googlecode.com/svn/trunk/
election --username tassemble@gmail.com

同时，我也上传到csdn上，以供下载：<自己动手写zookeeper选举和心跳同步>

http://download.csdn.net/detail/techq/4045878

最新整个项目在github上，同样，可以根据以下的url checkout出来:

git clone git://github.com/Tassemble/available.git