分布式算法需要一个进程充当协调者、发起者或者其他某种特殊的角色。

Bully算法

Bully算法是一种协调者（主节点）竞选算法，主要思想是集群的每个成员都可以声明它是主节点并通知其他节点。别的节点可以选择接受这个声称或是拒绝并进入主节点竞争。被其他所有节点接受的节点才能成为主节点。节点按照一些属性来判断谁应该胜出。这个属性可以是一个静态ID，也可以是更新的度量像最近一次事务ID（最新的节点会胜出）。
Bully 算法在选举过程中，需要用到以下 3 种消息：

  • Election 消息，用于发起选举；
  • Alive 消息，对 Election 消息的应答；
  • Victory 消息，竞选成功的主节点向其他节点发送的宣誓主权的消息。

mongodb
任何一个时刻，一个进程只能从编号比他小的进程接受election消息，当消息到达时，接受者发送一个OK消息给发送者，表明它在运行，接管工作。
最终除了一个进程外，其他进程都放弃，那个进程就是新的协调者。
他将获胜消息发送给其他所有进程，通知他们新的协调者。
当一个以前崩溃的进程恢复过来了后，它将主持一场选举。如果该进程恰好是当前运行进程中编号最大的进程，它将获胜，故此成为欺负算法。

环算法

Raft算法

Raft 算法是典型的多数派投票选举算法，其选举机制与我们日常生活中的民主投票机制类似，核心思想是“少数服从多数”。也就是说，Raft 算法中，获得投票最多的节点成为主。
采用 Raft 算法选举，集群节点的角色有 3 种：

  • Leader，即主节点，同一时刻只有一个 Leader，负责协调和管理其他节点；
  • Candidate，即候选者，每一个节点都可以成为 Candidate，节点在该角色下才可以被选为新的 Leader；
  • Follower，Leader 的跟随者，不可以发起选举。

Raft 选举的流程，可以分为以下几步：

  1. 初始化时，所有节点均为 Follower 状态。
  2. 开始选主时，所有节点的状态由 Follower 转化为 Candidate，并向其他节点发送选举请求。
  3. 其他节点根据接收到的选举请求的先后顺序，回复是否同意成为主。这里需要注意的是，在每一轮选举中，一个节点只能投出一张票。
  4. 若发起选举请求的节点获得超过一半的投票，则成为主节点，其状态转化为 Leader，其他节点的状态则由 Candidate 降为 Follower。Leader 节点与 Follower 节点之间会定期发送心跳包，以检测主节点是否活着。
  5. 当 Leader 节点的任期到了，即发现其他服务器开始下一轮选主周期时，Leader 节点的状态由 Leader 降级为 Follower，进入新一轮选主

    ZAB算法

    ZooKeeper
    相较于 Raft 算法的投票机制，ZAB 算法增加了通过节点 ID 和数据 ID 作为参考进行选主，节点 ID 和数据 ID 越大，表示数据越新，优先成为主。相比较于 Raft 算法，ZAB 算法尽可能保证数据的最新性。所以，ZAB 算法可以说是对 Raft 算法的改进。
    集群中每个节点拥有 3 种角色：
  • Leader，主节点；
  • Follower，跟随者节点；
  • Observer，观察者，无投票权。

集群中的节点拥有 4 个状态：

  • Looking 状态，即选举状态。当节点处于该状态时，它会认为当前集群中没有 Leader，因此自己进入选举状态。
  • Leading 状态，即领导者状态，表示已经选出主，且当前节点为 Leader。
  • Following 状态，即跟随者状态，集群中已经选出主后，其他非主节点状态更新为 Following，表示对 Leader 的追随。
  • Observing 状态，即观察者状态，表示当前节点为 Observer，持观望态度，没有投票权和选举权。

ZAB 选举算法的核心是“少数服从多数，ID 大的节点优先成为主”，因此选举过程中通过 (vote_id, vote_zxID) 来表明投票给哪个节点，其中 vote_id 表示被投票节点的 ID，vote_zxID 表示被投票节点的服务器 zxID。ZAB 算法选主的原则是：server_zxID 最大者成为 Leader；若 server_zxID 相同，则 server_id 最大者成为 Leader。
第一步：当系统刚启动时，3 个服务器当前投票均为第一轮投票，即 epoch=1，且 zxID 均为 0。此时每个服务器都推选自己，并将选票信息 广播出去。
第二步：根据判断规则，由于 3 个 Server 的 epoch、zxID 都相同，因此比较 server_id，较大者即为推选对象，因此 Server 1 和 Server 2 将 vote_id 改为 3，更新自己的投票箱并重新广播自己的投票。
第三步：此时系统内所有服务器都推选了 Server 3，因此 Server 3 当选 Leader，处于 Leading 状态，向其他服务器发送心跳包并维护连接；Server1 和 Server2 处于 Following 状态。
ZAB 算法性能高，对系统无特殊要求，采用广播方式发送信息，若节点中有 n 个节点，每个节点同时广播，则集群中信息量为 n*(n-1) 个消息，容易出现广播风暴；且除了投票，还增加了对比节点 ID 和数据 ID，这就意味着还需要知道所有节点的 ID 和数据 ID，所以选举时间相对较长。但该算法选举稳定性比较好，当有新节点加入或节点故障恢复后，会触发选主，但不一定会真正切主，除非新节点或故障后恢复的节点数据 ID 和节点 ID 最大，且获得投票数过半，才会导致切主。
ZooKeeper、Kubernetes 等开源软件选主均采用奇数节点的一个关键原因就是当两个节点均获得一半投票时，无法确定该选谁为主

转载 https://www.yuque.com/jykss/jykss/mlo3u1