前言
分布式系统中有的各个节点的地位是均等的,有的是有leader和flower。这种区分leader的集群更好管理些。这样在写操作的时候都交给Leader去处理，然后由leader再将数据同步给各个flower上的副本。如果同时对多个分布式节点写数据，势必不好进行数据同步。读的时候可以从flower上读取，也可以从leader上读取，分散下系统压力。有些分布式系统，Leader还负责一些元数据的管理。所以对于这种分布式系统来说leader选举很重要。
这就涉及到如何在集群初始化或者主挂掉之后，或有新节点加入到集群中，会重新选主的问题。有的算法根据ID的大小来选举leader，有的算法采用多数派投票算法，谁的票数多谁当老大。本篇主要聊下简单的Bully算法，即根据ID来选举leader的算法。
一 Bully选主算法
Bully算法基本思想就是谁的ID最大或最小谁来当老大（一般选择ID大的）。节点的角色分为两种主节点和普通节点。在集群开始启动的时候，或者主挂了之后会发起选举，节点间通过发消息来进行选举，消息分为三种：
- Election Message： 选举消息 A->B发送选举消息，表示A支持B当Leader。
- Alive Message： 响应选举消息，刚才A->B选举B，B给A回复Answer Messge。
- Victory Message： 宣布胜利消息，如果B最终当选为Leader，则B向其他节点发送Victory Message。
拿现实生活举例，比如你们部门的领导不在了，调走了，然后大家都彼此相互了解（节点保存集群中所有节点的信息），每个人都对其他资历比自己老的（id比自己id大的）发起选举消息，意思是我选你当leader；如果自己资历最老对其他人说，我当老大（发起victory 消息）；如果不是，当它发送选举消息有返回后，就知道有比自己资历还老的存在，那么自己选举就失败了；如果过一段时间，没有收到选举消息的回复，那说明我最大，我就可以对其他节点发送victory消息，宣告我当leader了。
以集群中leader节点挂掉来说明具体过程：
图1 集群中Leader 节点5挂掉
1） Leader挂掉后，1节点通过心跳探测消息发现，将发起新的选举，节点1 向比它大的所有节点发起选举消息，也需要向节点5发送选举消息，因为节点5这时候可能已经活了，所以再发一次。
节点2，3，4 回复Alive给1节点，5节点由于网络故障回复Alive消息丢失。
1 有收到Alive的回复后，说明有比它资格老的还活着，老老实实等待选举完成的Victory消息吧。
图2节点2发送选举消息
2）节点2也通过心跳探测发现leader 5挂了，这时候，通过向所有节点ID比它大的3，4，5发送选举消息，这时候，3和4都回复Alive消息给2，2 就知道自己不能当leader，老老实实等待吧；同样道理节点3 也会向节点4和节点5发送选举消息，同样收到节点4回复的Alive消息后就进入等待状态。
节点4发起选举消息
3）节点4也探测到超时后，发起选举消息给节点5，接收选举回复消息超时，这时候由于节点4没有收到任何选举消息的恢复消息，那就认为自己是leader，向其他所有节点发送victory消息，宣布主权，从而完成这轮选举。
发送victory消息给其他节点
二 Bully算法特点
早期的mangodb采用bully算法，Bully算法又叫欺负算法，是因为直接粗暴的选择最大id（这个id也可以用时间戳，谁的大说明谁新）作为leader。
Bully算法优点：算法实现比较简单，直接通过比较id就可以抉择出谁是leader，由于简单，所以性能比较好，实现起来也比较容易；
Bully算法缺点： 每个节点都要保存全部其他节点的信息，保存的元数据量大了点，我觉得这个不是缺点，就算成千台机器，保存的数据也不会很多；还有个缺点就是如果集群的最大id机器不稳定，那么频繁掉线上线，可能会造成频繁选举，选举的时候没有leader就没有办法进行一些写操作，从而造成集群不稳定。
三 Bully算法实现
算法虽然简单，实践中还需要考虑不少问题。
3.1 如何防止过期消息干扰
比如说我们如何决定一轮选举，像上文那种，如果选举结束了，那么节点5回复给节点3的消息现在才过来，那么节点3如何处理这个消息，我的理解是可以设置逻辑时钟，标识每一轮的选举，选举成功后，逻辑时钟加1，这种延迟到来的消息，由于是上一轮选举的所以可以扔掉。
3.2 如何防止脑裂
还有个问题，就是如何防止脑裂，比如还是刚才的例子，对于节点5来说，它收到别人的选举消息后，也会发起选举，由于它的id最大，那么它自己会发送选举成功消息给1，2，3，4节点，由于网络问题，其他节点并没有收到这个消息，4节点法给它的选举成功消息也可能没有收到，那么它也自认为自己是老大，这样整个集群中就有二个leader了，如果有客户端连接5节点，发起写操作，它当自己为leader话就自己先处理了，不会转发。
对于这个问题，我的解决思路是集合集群中的存活节点数要包含集群中节点量一半，如果集群中的存活的节点数量没有达到一半，则把自己变成dead状态。比如上面描述的节点5，当客户端发送请求给节点5的时候，直接回复节点死掉，客户端可以重试其他节点，从而把写请求发到真正的leader 节点4上，从而防止了脑裂。
网上分布式Bully算法选举实现：[https://github.com/Justin02180218/distribute-election-bully](https://github.com/Justin02180218/distribute-election-bully)
我大概看了下，它的代码，发现大概实现了这个算法，使用起来可能还有些问题，比如：
private void electLeader() throws Exception {
logger.info("[" + metadata + "] cluster leader: " + cluster.getLeader());
if (cluster.getNodes().size() > 1) {
Metadata leader = cluster.getLeader();
if ((leader == null) || (leader.getNodeStatus() != NodeStatus.ALIVE)) {
logger.info("Starting election ...");
epoch.getAndIncrement();
metadata.setEpoch(epoch.get());
List<Metadata> largerNodes = cluster.largerNodes(metadata);
if (largerNodes.isEmpty()) {
if (metadata.getNodeStatus() != NodeStatus.ALIVE) {
logger.warn("Node is not alive: " + metadata);
}else {
// 如果比它大的节点为空，设置自己为leader
cluster.getNodes().get(metadata.getNodeId().toString()).setEpoch(epoch.get());
cluster.setLeader(metadata);
// 直接向其他节点发送宣布主权消息，
List<Metadata> otherNodes = cluster.otherNodes(metadata);
for (Metadata otherNode : otherNodes) {
client.invokeOneway(otherNode.getNodeAddress(), VictoryMessage.getInstance().request(metadata), 3*1000);
}
}
}else {
// 向比它大的节点发送选举消息
for (Metadata largerNode : largerNodes) {
RemotingMessage response = client.invokeSync(largerNode.getNodeAddress(), ElectionMessage.getInstance().request(metadata), 3*1000);
String res = new String(response.getMessageBody(), Charset.forName("UTF-8"));
logger.info("Election response: " + res);
}
}
}
}
}
大概说明了选举的流程，当时，没有说如果发送给比它大的选举消息超时后如何处理，我上述描述的情况就无法选举出四节点作为leader了，或者再发送比它大的节点的时候判断节点是否存活，如果不存活，则不算入集群，不过这又会造成误判的情况，他代码里面并没有这么做：
public List<Metadata> largerNodes(final Metadata metadata) {
final List<Metadata> largerNodes = new ArrayList<Metadata>();
for (Metadata node : nodes.values()) {
if (metadata.compareTo(node) < 0) {
largerNodes.add(node);
}
}
return largerNodes;
}
总体来说，还是很有参考价值的，有空自己实现一个应该挺有意思的。
四 诗词欣赏
临江仙 寒柳
[清] [纳兰性德]
飞絮飞花何处是
层冰积雪摧残
疏疏一树五更寒
爱他明月好
憔悴也相关
最是繁丝摇落后
转教人忆春山
湔裙梦断续应难
西风多少恨
吹不散眉弯
网友评论