ZooKeeper FastLeader 选举

ZooKeeper 在集群模式下默认会使用 FastLeader 算法来选举 leader。下面将说说 ZooKeeper 集群使用 FastLeader 算法选举的具体过程。写的过程中参考了多篇文章，详见文末的参考资料。

首先需要明确几个概念:

节点状态：每个集群中的节点都有一个状态 LOOKING/FOLLOWING/LEADING/OBSERVING。每个节点启动的时候都是 LOOKING 状态，如果这个节点参与选举但最后不是leader，则状态是 FOLLOWING，如果不参与选举则是 OBSERVING，leader 的状态是 LEADING。
epoch: 表示选举轮数。
zxid: 事务 zxid 包含了本地数据的最后更新时间相关的信息。
serverid: 当前 server 的 ID, 通过配置文件指定(比如: echo '1' > myid)。

先用文字描述一下大概的选举思想：

在没有遇到比我牛的人之前，第一票推荐我自己
当接收到其他人的选举信息时，如果他们推荐的人没我牛，那我还是推荐我自己
我有一个票箱，保存了当前这一轮选举中自己的推荐人以及接收到的推荐人信息，一人一票，重复或过期的票概不接受
当我发现了比我牛的人的时候，改为推荐这个牛人
如果我发现我的选举轮数落后了，清空票箱，改为推荐接收到的最新选举中大家推荐的最牛的那个人（如果没有人比我牛，那还是推荐我自己）
不断的重复上面的过程，不断的告诉别人“我的投票是第几轮”、“我推举的人是谁”。直到我的票箱中“我推举的最牛的人”收到了不少于 N / 2 + 1 的推举投票，此时这个人就是我认定的最终 leader。
当我确定了谁是最终 leader 并且这个 leader 一切正常，我就更新我的状态为 FOLLOWING/LEADING（我自己是最终 leader 则是 LEADING 否则就是 FOLLOWING），之后的选举中都直接反馈我确定的这个最终 leader。

那么，以什么标准来确定一个节点可以成为一个 leader 呢？依次比较 epoch, zxid, serverid ：

接收到的消息中，有 epoch 比我大的，则选 epoch 大的消息中确定的 server
如果 epoch 相等，则选 zxid 最大的 server
如果 zxid 也相等，则选 serverid 最大的 server (有的节点生来就是当 leader 的 😂）

switch (n.state) {
//LOOKING消息，则
case LOOKING:
......
    //检查下收到的这张选票是否可以胜出，依次比较选举轮数epoch，事务zxid，服务器编号server id
    } else if (totalOrderPredicate(n.leader, n.zxid, n.peerEpoch,
            proposedLeader, proposedZxid, proposedEpoch)) {
        //胜出了，就把自己的投票修改为对方的，然后广播消息
        updateProposal(n.leader, n.zxid, n.peerEpoch);
        sendNotifications();
    }
}

protected boolean totalOrderPredicate(long newId, long newZxid, long newEpoch, long curId, long curZxid, long curEpoch) {
    return (
        (newEpoch > curEpoch) ||
        ((newEpoch == curEpoch) &&
        ((newZxid > curZxid) || ((newZxid == curZxid) &&
        (newId > curId))))
    );
    }

从网上找了一个流程图，可以看看：

举个例子，理想情况下，先后启动三个节点的选举过程如下：

第一轮：每个节点广播选自己（此时只有 node1)
第二轮：node2 启动了，发起一轮投票。node1 收到了 node2 选它自己的投票，发现 node2 比自己牛，广播选 node2。此时 node1 发现 node2 获得了2票 >= N / 2 + 1，认定 node2 为 leader 进入 following 状态。 node2 收到了 node1 选自己的广播，此时 node2 发现自己获得了2票 >= N / 2 + 1，进入 leading 状态。
第三轮：node3 启动了，发起一轮投票。node1 和 node2 都选 node2 , node3 通过比对发现 node2 的票数 >= N /2 + 1，认定 node2 是 leader 进入 following 状态。

上面就是 FastLeader 算法选举的简单介绍了，更详细的信息可以查阅官方文档和代码。

ZooKeeper FastLeader 选举

参考¶

Comments