分布式选举-Bully算法-1 原理

分布式选举

        在大型分布式系统中，会存在多个特定功能的集群。最常见的就是协调者集群，如提供分布式锁，分布式事务的协调者集群。集群中的多个机器对外提供统一的状态、一致的数据，这就需要在集群中选择一个主节点(领导者)，来管理集群中的其他节点(跟随者)。这个选择主节点的过程就叫做分布式选举。

        分布式选举的算法有Bully算法、Raft算法、ZAB算法等。我们先来分析Bully算法的原理及实现，后续文章会讲解其他算法及实现。

Bully 算法原理：

    选举原则：在所有活着的节点中，选取节点ID最大或者最小的节点为主节点。

    节点角色：主节点和普通节点

    消息类型：

    1，Election 消息，向节点发起选举的消息

    2，Alive 消息，节点对 Election 消息的应答

    3，Victory 消息，竞选成功的主节点向普通节点发送竞选成功的消息

    选举过程：

    1，集群中每个活着的节点查找比自己ID大的节点，如果不存在则向其他节点发送Victory消息，表明自己为主节点。

    2，如果存在比自己ID大的节点，则向这些节点发送Election消息，并等待响应。

    3，如果在给定的时间内，没有收到这些节点回复的消息，则自己成为主节点，并向比自己ID小的节点发送Victory消息。

    4，节点收到比自己ID小的节点发送的Election消息，则回复Alive消息。

    假设有三个节点，选举过程如下图：

    开源软件应用：在Elasticsearch的master选举采用的就是Bully算法，MongoDB 的副本集选主采用的也是Bully算法。

总结：

        Bully算法选主，节点有两个角色：主节点和普通节点。节点间通信有三种消息：Election消息、Alive消息和Victory消息。选举速度快，算法复杂度低。缺点是如果节点ID大的节点频繁加入，退出集群，就会导致频繁切主。

        Bully算法的原理讲解完了，下一篇文章《分布式选举-Bully算法-2 代码实现》我们来具体看看如何用代码实现分布式环境下的Bully选举。

---

获取Bully算法的实现代码，请关注公众号，后台回复“ Bully ”获取源码。