Zookeeper的FastLeaderElection算法分析

我们知道，在经典的paxos算法中每一个peer都是proposer，但是这就不可避免的产生提案冲突，为了减少这种冲突带来的系统消耗与时间延迟，就产生了Leader这个角色，整个系统中，就只允许Leader可以发出提案。ZooKeeper就是按照这个思路来实现的。本文主要讨论ZooKeeper中的FastLeaderElection算法，来说明Leader是如何产生的。

我们先要清楚以下几点

l  一个Server是如何知道其它的Server？

在ZooKeeper集群中，Server的信息都在zoo.conf配置文件中，根据配置文件的信息就可以知道其它Server的信息。

l  ZooKeeper服务器有哪几种状态？（选主相关的状态）

LOOKING：寻找leader状态

LEADING：领导状态（节点为leader）

FOLLOWING：跟随者状态

OBSERVING：观察者状态（此状态不参与选举）

l  成为Leader的必要条件？

Leader要具有最高的zxid；集群中大多数的机器（至少n/2+1）得到响应并follow选出的Leader。

l  如果所有zxid都相同(例如: 刚初始化时)，此时有可能不能形成n/2+1个Server，怎么办？

ZooKeeper中每一个Server都有一个ID，这个ID是不重复的，如果遇到这样的情况时，ZooKeeper就推荐ID最大的哪个Server作为Leader。

l  lookForLeader函数什么时候被调用？

当Server的状态为LOOKING时，lookForLeader就会被调用。具体参见QuorumPeer类的run方法。

l  ZooKeeper中Leader怎么知道Fllower还存活，Fllower怎么知道Leader还存活？

Leader定时向Fllower发ping消息，Fllower定时向Leader发ping消息，当发现Leader无法ping通时，就改变自己的状态(LOOKING)，发起新的一轮选举。

算法相关的数据结构

收到的通知的数据结构：

static public class Notification { long leader;//被推荐的leader的id long zxid;//被推荐的leader的事务id long electionEpoch;//推荐者的选举周期 QuorumPeer.ServerState state;//推荐者的状态 long sid;//推荐者的id long peerEpoch;//被推荐的leader的选举周期 }

发送通知使用数据结构（跟接收其实差不多）：

static public class ToSend { static enum mType {crequest, challenge, notification, ack} ToSend(mType type, long leader, long zxid, long electionEpoch, ServerState state, long sid, long peerEpoch) { this.leader = leader; this.zxid = zxid; this.electionEpoch = electionEpoch; this.state = state; this.sid = sid; this.peerEpoch = peerEpoch; } long leader;//推荐的Leader ID long zxid;//推荐的Leader的最大事务ID long electionEpoch;// 推荐者本身的选举周期 QuorumPeer.ServerState state;// 推荐者本身的状态 long sid; // 推荐者本身的ID long peerEpoch; // 推荐的Leader的选举周期 }

关键字段、函数解释

l  leader

所推荐的leader的id。

l  zxid(ZooKeeper transaction id)

ZooKeeper事务Id，每个ZooKeeper状态的改变都会形成一个新的zxid值，这个值越大表示更新越新。

l  electionEpoch/logicalclock/peerEpoch

选举周期，用来判断是否为同一次选举。每调用一次选举函数，logicalclock自增1，并且在选举过程中如果遇到election比当前logicalclock大的值，就更新本地logicalclock的值。

l  public Vote lookForLeader() throws InterruptedException

选举函数，当ZooKeeper Server的状态变为LOOKING时，就会发起选举。函数会阻塞式地进行选主，直到最终的主产生，并返回为最终的投票结果。

l  synchronized void updateProposal(long leader, long zxid, long epoch)

更新投票

l  private boolean totalOrderPredicate(long newId, long newZxid, long newEpoch, long curId, long curZxid, long curEpoch)

将收到的对方的投票与当前自己的投票对比，判断对方的投票是否优于自己的投票。具体代码：

protected boolean totalOrderPredicate(long newId, long newZxid, long newEpoch, longcurId, long curZxid, long curEpoch) {         LOG.debug("id: " + newId + ", proposed id: " + curId + ", zxid: 0x" +                 Long.toHexString(newZxid) + ", proposed zxid: 0x" + Long.toHexString(curZxid));         // 使用计票器判断当前server的权重是否为0         if(self.getQuorumVerifier().getWeight(newId) == 0){             return false;         }         // 通过Epoch、zxid、id来比较两个候选leader         return ((newEpoch > curEpoch) ||                 ((newEpoch == curEpoch) &&                 ((newZxid > curZxid) || ((newZxid == curZxid) && (newId > curId)))));     }

FastLeaderElection算法（lookForLeader函数的主要逻辑）

1.发起一轮投票选举，推举自己作为leader，通知所有的服务器，等待接收外部选票。

2.只要当前服务器状态为LOOKING，进入循环，不断地读取其它Server发来的通知、进行比较、更新自己的投票、发送自己的投票、统计投票结果，直到leader选出或出错退出。具体作法：

从队列中取出一个Notification（选票），则根据消息中对方的状态进行相应的处理。

1）LOOKING状态：

a.如果发送过来的逻辑时钟大于目前的逻辑时钟，那么说明这是更新的一次选举投票，此时更新本机的逻辑时钟（logicalclock），清空投票箱（因为已经过期没有用了），调用totalOrderPredicate函数判断对方的投票是否优于当前的投票（判断规则上面提过了），是的话用对方推荐的leader更新下一次的投票，否则使用初始的投票（投自己），调用sendNotifications() 通知所有服务器我的选择，跳到d。

b.如果对方处于上轮投票，不予理睬，回到2。

c.如果对方也处于本轮投票，调用totalOrderPredicate函数判断对方的投票是否优于当前的投票，是的话更新当前的投票，否则使用初始的投票（投自己）并新生成notification消息放入发送队列。调用sendNotifications() 通知所有服务器我的选择。

d.将收到的投票放入自己的投票箱中。

e.调用计票器的containsQuorum函数，判断所推荐的leader是否得到集群多数人的同意（根据计票器的实现不同，可以是单纯看数量是否超过n/2，也可以是按权重来判断，我们这里假设单纯看数量），如果得到多数人同意，那么还需等待一段时间，看是否有比当前更优的提议，如果没有，则认为投票结束。根据投票结果修改自己的状态。以上任何一条不满足，则继续循环。

2）OBSERVING状态：

不做任何事。

3）FOLLOWING或LEADING状态：

a.如果选举周期相同（选票是同一轮选举产生），将该数据保存到投票箱，根据当前投票箱的投票判断对方推荐的leader是否得到多数人的同意，如果是则设置状态退出选举过程，否则到b。

b.这是一条与当前逻辑时钟不符合的消息，或者对方推荐的leader没有得到多数人的同意（有可能是收集到的投票数不够），那么说明可能在另一个选举过程中已经有了选举结果，于是将该选举结果加入到outofelection集合中，再根据outofelection来判断是否可以结束选举，如果可以也是保存逻辑时钟，设置状态，退出选举过程。否则继续循环。outofelection用于保存那些状态为FOLLOWING或者LEADING的ZooKeeper节点发送的选票，由于对方的状态为FOLLOWING或者LEADING，所以它们当前不参与选举过程（可能人家已经选完了），因此称为“out of election”。

参考资料

分布式设计与开发（三）——高一致性服务ZooKeeper：http://www.360doc.com/content/11/1215/11/116188_172393672.shtml

Zookeeper全解析——Paxos作为灵魂：http://www.spnguru.com/2010/08/zookeeper全解析——paxos的灵魂/

一个不错的讲解zookeeper选举算法的：http://blog.csdn.net/xhh198781/article/details/6619203

（文/阿涵-_-）

本文来源：http://blog.sina.com.cn/s/blog_3fe961ae01012jod.html