Zookeeper的FastLeaderElection算法分析
我们知道，在经典的paxos算法中每一个peer都是proposer，但是这就不可避免的产生提案冲突，为了减少这种冲突带来的系统消耗与时间延迟，就产生了Leader这个角色，整个系统中，就只允许Leader可以发出提案。ZooKeeper就是按照这个思路来实现的。本文主要讨论ZooKeeper中的FastLeaderElection算法，来说明Leader是如何产生的。
我们先要清楚以下几点
-
一个Server是如何知道其它的Server？
在ZooKeeper集群中，Server的信息都在zoo.conf配置文件中，根据配置文件的信息就可以知道其它Server的信息。 -
ZooKeeper服务器有哪几种状态？（选主相关的状态）
LOOKING：寻找leader状态
LEADING：领导状态（节点为leader）
FOLLOWING：跟随者状态
OBSERVING：观察者状态（此状态不参与选举） -
成为Leader的必要条件？
Leader要具有最高的zxid；集群中大多数的机器（至少n/2+1）得到响应并follow选出的Leader。 -
如果所有zxid都相同(例如: 刚初始化时)，此时有可能不能形成n/2+1个Server，怎么办？
ZooKeeper中每一个Server都有一个ID，这个ID是不重复的，如果遇到这样的情况时，ZooKeeper就推荐ID最大的哪个Server作为Leader。 -
lookForLeader函数什么时候被调用？
当Server的状态为LOOKING时，lookForLeader就会被调用。具体参见QuorumPeer类的run方法。 -
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的选举周期
}
关键字段、函数解释
-
leader
所推荐的leader的id。 -
zxid(ZooKeeper transaction id)
ZooKeeper事务Id，每个ZooKeeper状态的改变都会形成一个新的zxid值，这个值越大表示更新越新。 -
electionEpoch/logicalclock/peerEpoch
选举周期，用来判断是否为同一次选举。每调用一次选举函数，logicalclock自增1，并且在选举过程中如果遇到election比当前logicalclock大的值，就更新本地logicalclock的值。 -
public Vote lookForLeader() throws InterruptedException
选举函数，当ZooKeeper Server的状态变为LOOKING时，就会发起选举。函数会阻塞式地进行选主，直到最终的主产生，并返回为最终的投票结果。 -
synchronized void updateProposal(long leader, long zxid, long epoch)
更新投票 -
private boolean totalOrderPredicate(long newId, long newZxid, long newEpoch, long curId, long curZxid, long curEpoch)
将收到的对方的投票与当前自己的投票对比，判断对方的投票是否优于自己的投票。具体代码：
protected boolean totalOrderPredicate(long newId, long newZxid, long newEpoch, long curId, 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函数的主要逻辑）
- 发起一轮投票选举，推举自己作为leader，通知所有的服务器，等待接收外部选票。
- 只要当前服务器状态为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
Zookeeper全解析——Paxos作为灵魂
一个不错的讲解zookeeper选举算法
