选举

发表于 | 更新于 | 分类于 | 阅读次数：

zookeeper选举

FastLeaderElection

服务器状态
  • LOOKING 不确定Leader状态。该状态下的服务器认为当前集群中没有Leader，会发起Leader选举
  • FOLLOWING 跟随者状态。表明当前服务器角色是Follower，并且它知道Leader是谁
  • LEADING 领导者状态。表明当前服务器角色是Leader，它会维护与Follower间的心跳
  • OBSERVING 观察者状态。表明当前服务器角色是Observer，与Folower唯一的不同在于不参与选举，也不参与集群写操作时的投票
选票数据结构
  • logicClock 每个服务器会维护一个自增的整数，名为logicClock，它表示这是该服务器发起的第多少轮投票
  • state 当前服务器的状态
  • self_id 当前服务器的myid
  • self_zxid 当前服务器上所保存的数据的最大zxid
  • vote_id 被推举的服务器的myid
  • vote_zxid 被推举的服务器上所保存的数据的最大zxid

投票流程

发送初始化选票

每个服务器最开始都是通过广播把票投给自己。

接收外部投票

服务器会尝试从其它服务器获取投票，并记入自己的投票箱内。如果无法获取任何外部投票，则会确认自己是否与集群中其它服务器保持着有效连接。如果是，则再次发送自己的投票；如果否，则马上与之建立连接。

选票PK

选票PK是基于(self_id, self_zxid)与(vote_id, vote_zxid)的对比

  • 外部投票的logicClock大于自己的logicClock，则将自己的logicClock及自己的选票的logicClock变更为收到的logicClock
  • 若logicClock一致，则对比二者的vote_zxid，若外部投票的vote_zxid比较大，则将自己的票中的vote_zxid与vote_id更新为收到的票中的vote_zxid与vote_id并广播出去，另外将收到的票及自己更新后的票放入自己的票箱。如果票箱内已存在(self_id, self_zxid)相同的选票，则直接覆盖
  • 若二者vote_zxid一致，则比较二者的vote_id，若外部投票的vote_id比较大，则将自己的票中的vote_id更新为收到的票中的vote_myid并广播出去，另外将收到的票及自己更新后的票放入自己的票箱
summary
  • 先投票给自己
  • 根据收到的票比对，将zxid事务id最大（即同步最好的节点）选择leader，如果都一样，选取serve_id最大的为leader。

基于zookeeper选举

znode
  • Persist vs. Ephemeral
    • Persist节点，一旦被创建，便不会意外丢失，即使服务器全部重启也依然存在。每个 Persist 节点即可包含数据，也可包含子节点
    • Ephemeral节点，在创建它的客户端与服务器间的 Session 结束时自动被删除。服务器重启会导致 Session 结束，因此 Ephemeral 类型的 znode 此时也会自动删除
  • Sequence vs. Non-sequence
    • Non-sequence节点，多个客户端同时创建同一 Non-sequence 节点时，只有一个可创建成功，其它匀失败。并且创建出的节点名称与创建时指定的节点名完全一样
    • Sequence节点，创建出的节点名在指定的名称之后带有10位10进制数的序号。多个客户端创建同一名称的节点时，都能创建成功，只是序号不同

非公平模式

所谓的非公平模式的选举是相对的，假设有10台机器进行选举，最后会选到哪一个机器，是完全随机的（看谁抢的快）。比如选到了A机器。某一时刻，A机器挂掉了，这时候会再次进行选举，这一次的选举依然是随机的。与某个节点是不是先来的，是不是等了很久无关。这种选举算法，就是非公平的算法。

方式

客户端同时向Zookeeper集群注册Ephemeral且Non-sequence类型的节点，路径一致，只会有一个创建成功，其它节点均创建失败。注册成功的选举为leader。

总结

  • 非公平模式实现简单，每一轮选举方法都完全一样
  • 竞争参与方不多的情况下，效率高。每个 Follower 通过 Watch 感知到节点被删除的时间不完全一样，只要有一个 Follower 得到通知即发起竞选，即可保证当时有新的 Leader 被选出
  • 给Zookeeper 集群造成的负载大，因此扩展性差。如果有上万个客户端都参与竞选，意味着同时会有上万个写请求发送给 Zookeper。Zookeeper 存在单点写的问题，写性能不高。同时一旦 Leader 放弃领导权，Zookeeper 需要同时通知上万个 Follower，负载较大

公平模式

各客户端均创建/zkroot/leader节点，且其类型为Ephemeral与Sequence。

image

由于是Sequence类型节点，故上图中三个客户端均创建成功，只是序号不一样。此时，每个客户端都会判断自己创建成功的节点的序号是不是当前最小的。如果是，则该客户端为 Leader，否则即为 Follower。

区别

  1. 在非公平中，所有客户端watch一个节点，在公平模式中，是watch序号比较自己小的前一个节点。
  2. 公平模式扩展性好，每个客户端都只 Watch 一个节点且每次节点被删除只须通知一个客户端。
  3. 延迟相对非公平模式要高，因为它必须等待特定节点得到通知才能选出新的 Leader

kafka选举leader

如果某个分区所在的服务器出了问题，不可用，kafka会从该分区的其他的副本中选择一个作为新的Leader。之后所有的读写就会转移到这个新的Leader上。

Kafka会在Zookeeper上针对每个Topic维护一个称为ISR。该集合中是一些分区的副本。只有当这些副本都跟Leader中的副本同步了之后，kafka才会认为消息已提交，并反馈给消息的生产者。如果这个集合有增减，kafka会更新zookeeper上的记录。

如果某个分区的Leader不可用，Kafka就会从ISR集合中选择一个副本作为新的Leader。

常用选主机制的缺点（为什么kafka的选主机制不过度依赖zookeeper）

由于Kafka集群依赖zookeeper集群，所以最简单最直观的方案是，所有Follower都在ZooKeeper上设置一个Watch，一旦Leader宕机，其对应的ephemeral znode会自动删除，此时所有Follower都尝试创建该节点，而创建成功者（ZooKeeper保证只有一个能创建成功）即是新的Leader，其它Replica即为Follower。

前面的方案有以下缺点：

  • split-brain (脑裂): 这是由ZooKeeper的特性引起的，虽然ZooKeeper能保证所有Watch按顺序触发，但并不能保证同一时刻所有Replica“看”到的状态是一样的，这就可能造成不同Replica的响应不一致 ;（kafka为了应对脑裂，引入了纪元epoch）

  • herd effect (羊群效应): 如果宕机的那个Broker上的Partition比较多，会造成多个Watch被触发，造成集群内大量的调整；如果是现在有的isr模式，只有在isr中的才会出现调整，影响范围较小

  • ZooKeeper负载过重 : 每个Replica都要为此在ZooKeeper上注册一个Watch，当集群规模增加到几千个Partition时ZooKeeper负载会过重

  • controller会将Leader的改变直接通过RPC的方式（比Zookeeper Queue的方式更高效）通知需为此作出响应的Broker

  • 选择Leader时也是从超过半数的同步的副本中选择。这种算法需要较高的冗余度。譬如只允许一台机器失败，需要有三个副本；而如果只容忍两台机器失败，则需要五个副本。而kafka的ISR集合方法，分别只需要两个和三个副本。

ES 选举

  1. 对所有可以成为master的节点（node.mast r: true）根据nodeId字典排序，每次选举每个节点都把自己所知道节点排一次序，然后选出第一个（第0位）节点，暂且认为它是master节点。
  2. 如果对某个节点的投票数达到一定的值（可以成为master节点数n/2+1）并且该节点自己也选举自己，那这个节点就是master。否则重新选举一直到满足上述条件。
Reference

https://blog.csdn.net/qq_37502106/article/details/80260415#

https://blog.csdn.net/zh15732621679/article/details/80723358

http://www.jasongj.com/zookeeper/fastleaderelection/

https://blog.csdn.net/xiaoyu_bd/article/details/82016395