转自:https://www.yuque.com/renyong-jmovm/kb/fukd3b
https://www.cnblogs.com/shuaiandjun/p/9383655.html

人类选举的基本原理

正常情况下,选举是一定要投票的.

我们应该都经历过投票，在投票时我们可能会将票投给和我们关系比较好的人，如果你和几个候选人都比较 熟，这种情况下你会将选票投给你认为能力比较强的人，如果你和几个候选人都不熟，并且你自己也是候选人 的话，这时你应该会认为你是这些候选人里面最厉害的那个人，大家都应该选你，这时你就会去和别人交流以 获得别人的投票，但是很有可能在交流的过程中，你发现了比你更厉害的人，这时你如果脸皮不是那么厚的 话，你应该会改变你的决定，去投你觉得更厉害的人，最终你将得到在你心中认为最厉害的人，且将票投给他，选票将会放在投票中，最后从投票箱中进行统计，获得票数最多的人当选。

在这样一个选举过程中我们提炼出四个基本概念：

  1. 个人能力：投我认为能力最强的人，这是投票的基本规则
  2. 改票：能力最强的人是逐渐和其他人沟通之后的结果，类似改票，先投给A，但是后来发现B更厉害，则改
    为投B
  3. 投票箱：所有人公用一个投票箱
  4. 领导者：获得投票数最多的人为领导者

Zookeeper选举的基本原理

Zookeeper集群模式才需要选举

一、zookeeper集群

配置多个实例共同构成一个集群对外提供服务以达到水平扩展的目的，每个服务器上的数据是相同的，每一个服务器均可以对外提供读和写的服务，这点和redis是相同的，即对客户端来讲每个服务器都是平等的。
Zookeeper快速领导者选举原理 - 图1
这篇主要分析leader的选择机制，zookeeper提供了三种方式：

  • LeaderElection
  • AuthFastLeaderElection
  • FastLeaderElection （最新默认）

默认的算法是FastLeaderElection，所以这篇主要分析它的选举机制。

二、选举流程简述

目前有5台服务器，每台服务器均没有数据，它们的编号分别是1,2,3,4,5,按编号依次启动，它们的选择举过程如下：

  • 服务器1启动，给自己投票，然后发投票信息，由于其它机器还没有启动所以它收不到反馈信息，服务器1的状态一直属于Looking(选举状态)。
  • 服务器2启动，给自己投票，同时与之前启动的服务器1交换结果，由于服务器2的编号大所以服务器2胜出，但此时投票数没有大于半数，所以两个服务器的状态依然是LOOKING。
  • 服务器3启动，给自己投票，同时与之前启动的服务器1,2交换信息，由于服务器3的编号最大所以服务器3胜出，此时投票数正好大于半数，所以服务器3成为领导者，服务器1,2成为小弟。
  • 服务器4启动，给自己投票，同时与之前启动的服务器1,2,3交换信息，尽管服务器4的编号大，但之前服务器3已经胜出，所以服务器4只能成为小弟。
  • 服务器5启动，后面的逻辑同服务器4成为小弟。

总结: 组成集群的服务器台数,必须是奇数

三、选择机制中的概念

1、Serverid：服务器ID

比如有三台服务器，编号分别是1,2,3。

编号越大在选择算法中的权重越大。

2、Zxid：数据ID

服务器中存放的最大数据ID.

值越大说明数据越新，在选举算法中数据越新权重越大。

3、Epoch：逻辑时钟

或者叫投票的次数，同一轮投票过程中的逻辑时钟值是相同的。每投完一次票这个数据就会增加，然后与接收到的其它服务器返回的投票信息中的数值相比，根据不同的值做出不同的判断。

4、Server状态：选举状态

  • LOOKING，竞选状态。
  • FOLLOWING，随从状态，同步leader状态，参与投票。
  • OBSERVING，观察状态,同步leader状态，不参与投票。
  • LEADING，领导者状态。

    五、选举流程图

    因为每个服务器都是独立的，在启动时均从初始状态开始参与选举，下面是简易流程图。
    Zookeeper快速领导者选举原理 - 图2

    六、选举状态图

    描述Leader选择过程中的状态变化，这是假设全部实例中均没有数据，假设服务器启动顺序分别为：A,B,C。
    Zookeeper快速领导者选举原理 - 图3

    七、判断是否已经胜出

    默认是采用投票数大于半数则胜出的逻辑。

    八、选举流程详述

    一、首先开始选举阶段，每个Server读取自身的zxid。
    二、发送投票信息
    a、首先，每个Server第一轮都会投票给自己。
    b、投票信息包含 ：所选举leader的Serverid，Zxid，Epoch。Epoch会随着选举轮数的增加而递增。
    三、接收投票信息
    1、如果服务器B接收到服务器A的数据（服务器A处于选举状态(LOOKING 状态)
    1）首先，判断逻辑时钟值：
    　　　　a）如果发送过来的逻辑时钟Epoch大于目前的逻辑时钟。首先，更新本逻辑时钟Epoch，同时清空本轮逻辑时钟收集到的来自其他server的选举数据。然后，判断是否需要更新当前自己的选举leader Serverid。判断规则rules judging：保存的zxid最大值和leader Serverid来进行判断的。先看数据zxid,数据zxid大者胜出;其次再判断leader Serverid,leader Serverid大者胜出；然后再将自身最新的选举结果(也就是上面提到的三种数据（leader Serverid，Zxid，Epoch）广播给其他server)
    　　　　b）如果发送过来的逻辑时钟Epoch小于目前的逻辑时钟。说明对方server在一个相对较早的Epoch中，这里只需要将本机的三种数据（leader Serverid，Zxid，Epoch）发送过去就行。
    　　　　c）如果发送过来的逻辑时钟Epoch等于目前的逻辑时钟。再根据上述判断规则rules judging来选举leader ，然后再将自身最新的选举结果(也就是上面提到的三种数据（leader Serverid，Zxid，Epoch）广播给其他server)。
    2）其次，判断服务器是不是已经收集到了所有服务器的选举状态：若是，根据选举结果设置自己的角色(FOLLOWING还是LEADER)，退出选举过程就是了。
    最后，若没有收到没有收集到所有服务器的选举状态：也可以判断一下根据以上过程之后最新的选举leader是不是得到了超过半数以上服务器的支持,如果是,那么尝试在200ms内接收一下数据,如果没有新的数据到来,说明大家都已经默认了这个结果,同样也设置角色退出选举过程。
    2、 如果所接收服务器A处在其它状态（FOLLOWING或者LEADING）。
    　　　　a)逻辑时钟Epoch等于目前的逻辑时钟，将该数据保存到recvset。此时Server已经处于LEADING状态，说明此时这个server已经投票选出结果。若此时这个接收服务器宣称自己是leader, 那么将判断是不是有半数以上的服务器选举它，如果是则设置选举状态退出选举过程。
    　　　　b) 否则这是一条与当前逻辑时钟不符合的消息，那么说明在另一个选举过程中已经有了选举结果，于是将该选举结果加入到outofelection集合中，再根据outofelection来判断是否可以结束选举,如果可以也是保存逻辑时钟，设置选举状态，退出选举过程。