Leader 选举算法源码

选票比较

org/apache/zookeeper/server/quorum/FastLeaderElection.java(3.9.6,节选,省略了 debug 日志与注释) protected boolean totalOrderPredicate(long newId, long newZxid, long newEpoch, long curId, long curZxid, long curEpoch) { ... // LOG.debug(...) if (self.getQuorumVerifier().getWeight(newId) == 0) { return false; } ... // 注释:三种情形 return ((newEpoch > curEpoch) || ((newEpoch == curEpoch) && ((newZxid > curZxid) || ((newZxid == curZxid) && (newId > curId))))); }

注意源码里的参数名:前三个是新收到的票(newId、newZxid、newEpoch),后三个是当前投票;函数头的 debug 日志里把名字写反了,别被误导。开头还有一个 getWeight(newId) == 0 的检查 —— 在普通的多数派配置(QuorumMaj)里权重恒为 1,所以它对观察者不起作用;观察者是靠另一个机制(下面)挡住的。

  比对 64 组:不一致 0 组;返回 true 的 28 组(其余 36 组为 false,其中 8 组是完全相同的两张票:相同的票不会替换当前投票)
  几个具体例子(new = 收到的票,cur = 当前投票):
    new(id=3,zxid=0x100000002,epoch=1) vs cur(id=1,zxid=0x100000035,epoch=1) → false  // 同 epoch,zxid 更小
    new(id=1,zxid=0x100000035,epoch=1) vs cur(id=3,zxid=0x100000002,epoch=1) → true  // 同 epoch,zxid 更大
    new(id=3,zxid=0x5,epoch=1) vs cur(id=2,zxid=0x5,epoch=1) → true  // 同 epoch、同 zxid,id 更大
    new(id=2,zxid=0x5,epoch=1) vs cur(id=3,zxid=0x5,epoch=1) → false  // 同 epoch、同 zxid,id 更小
    new(id=1,zxid=0x5,epoch=2) vs cur(id=3,zxid=0x63,epoch=1) → true  // epoch 更大(即使 zxid 小得多)
    new(id=1,zxid=0x5,epoch=1) vs cur(id=1,zxid=0x5,epoch=1) → false  // 两张票完全相同
  观察者的初始选票是 (id=Long.MIN_VALUE, zxid=Long.MIN_VALUE, epoch=Long.MIN_VALUE):它去挑战任何参与者的选票 → false;参与者的选票挑战观察者的初始选票 → true

观察者为什么永远不会赢

  观察者(myid 4)日志里的 New election: [('4', '0x8000000000000000')]
  参与者(myid 1)日志里的 New election: [('1', '0x0')]
  观察者最终 mode = observer | leader = z99c-2

源码里 getInitId() 对不在投票成员里的节点返回 Long.MIN_VALUE,getInitLastLoggedZxid() 对非参与者同样返回 Long.MIN_VALUE,所以观察者的票在上面的比较里永远输。

凑够票之后还要再等 200 ms

同一文件,lookForLeader 中收齐过半票之后的段落 if (voteSet.hasAllQuorums()) { // Verify if there is any change in the proposed leader while ((n = recvqueue.poll(finalizeWait, TimeUnit.MILLISECONDS)) != null) { if (totalOrderPredicate(n.leader, n.zxid, n.peerEpoch, proposedLeader, proposedZxid, proposedEpoch)) { recvqueue.put(n); break; } } if (n == null) { setPeerState(proposedLeader, voteSet); Vote endVote = new Vote(proposedLeader, proposedZxid, logicalclock.get(), proposedEpoch); leaveInstance(endVote); return endVote; } }

  第 1 次:kill z99-2 → 新 leader z99-1;新 leader 日志里 LEADING 的选举耗时(历次):[218] ms;follower 日志里最近一次 FOLLOWING 的选举耗时:[212] ms
  第 2 次:kill z99-1 → 新 leader z99-2;新 leader 日志里 LEADING 的选举耗时(历次):[227] ms;follower 日志里最近一次 FOLLOWING 的选举耗时:[224] ms
  第 3 次:kill z99-2 → 新 leader z99-1;新 leader 日志里 LEADING 的选举耗时(历次):[223] ms;follower 日志里最近一次 FOLLOWING 的选举耗时:[220] ms
  第 4 次:kill z99-1 → 新 leader z99-2;新 leader 日志里 LEADING 的选举耗时(历次):[217] ms;follower 日志里最近一次 FOLLOWING 的选举耗时:[219] ms
  第 5 次:kill z99-2 → 新 leader z99-1;新 leader 日志里 LEADING 的选举耗时(历次):[222] ms;follower 日志里最近一次 FOLLOWING 的选举耗时:[218] ms
  5 次 leader 选举耗时(ms):[218, 227, 223, 217, 222],最小 217 ms ≥ 200 ms:True

这就是选举期间写不可用约 400 多毫秒的一部分来源:至少 200 ms 的 finalizeWait,加上失败检测与通信。

超时退避

同一文件 notTimeout = Math.min(notTimeout << 1, maxNotificationInterval);

  14 秒内 Notification time out 依次为:['400', '800', '1600', '3200', '6400', '12800'](日志打印的是翻倍之后的值;第一次等待是 200 ms = finalizeWait,之后每次翻倍)

退避是在没有收到足够通知时(比如对端都没起来)才会发生。

分步演示