达内广州C++学院|c++培训|广州达内科技C++/C#培训|.NET培训|IT培训|达内广州岗顶中心 达内广州C++学院|c++培训|广州达内科技C++/C#培训|.NET培训|IT培训|达内广州岗顶中心
java程序员
 当前位置:主页 > 高端课程 > java程序员 >

Zookeeper选举算法原理

时间:2019-10-09  来源:未知  作者:广州达内培训

Leader选举

Leader选举是保证分布式数据一致性的关键所在。当Zookeeper集群中的一台服务器出现以下两种情况之一时,需要进入Leader选举。

  • (1) 服务器初始化启动。(集群的每个节点都没有数据 → 以SID的大小为准)
  • (2) 服务器运行期间无法和Leader保持连接。(集群的每个节点都有数据 ,或者Leader 宕机→ 以ZXID 和 SID 的最大值为准)

 

1. 服务器启动时期的Leader选举

若进行Leader选举,则至少需要2台机器,两台的高可用性会差一些,如果Leader 宕机,就剩下一台,自己没办法选举。这里选取3台机器组成的服务器集群为例。

在集群初始化阶段,当有一台服务器Server1启动时,其单独无法进行和完成Leader选举,当第二台服务器Server2启动时,此时两台机器可以相互通信,每台机器都试图找到Leader,于是进入Leader选举过程。选举过程如下

  • (1) 每个Server发出一个投票。由于是初始情况,Server1和Server2都会将自己作为Leader服务器来进行投票,每次投票会包含所推举的服务器的myid和ZXID,使用(myid, ZXID)来表示,此时Server1的投票为(1, 0),Server2的投票为(2, 0),然后各自将这个投票发给集群中其他机器。
  • (2) 接受来自各个服务器的投票。集群的每个服务器收到投票后,首先判断该投票的有效性,如检查是否是本轮投票、是否来自LOOKING状态的服务器。
  • (3) 处理投票。针对每一个投票,服务器都需要将别人的投票和自己的投票进行PK,PK规则如下:
  • 优先检查ZXID。ZXID比较大的服务器优先作为Leader。(这个很重要:是数据最新原则,保证数据的完整性)
  • 如果ZXID相同,那么就比较myid。myid较大的服务器作为Leader服务器。(集群的节点标识)对于Server1而言,它的投票是(1, 0),接收Server2的投票为(2, 0),首先会比较两者的ZXID,均为0。再比较myid,此时Server2的myid最大,于是更新自己的投票为(2, 0),然后重新投票,对于Server2而言,其无须更新自己的投票,只是再次向集群中所有机器发出上一次投票信息即可。
  • (4) 统计投票。每次投票后,服务器都会统计投票信息,判断是否已经有过半机器接受到相同的投票信息,对于Server1、Server2而言,都统计出集群中已经有两台机器接受了(2, 0)的投票信息,此时便认为已经选出了Leader。
  • (5) 改变服务器状态。一旦确定了Leader,每个服务器就会更新自己的状态,如果是Follower,那么就变更为FOLLOWING,如果是Leader,就变更为LEADING。

2. 服务器运行时期的Leader选举

在Zookeeper运行期间,Leader与非Leader服务器各司其职,即便当有非Leader服务器宕机或新加入,此时也不会影响Leader,但是一旦Leader服务器挂了,那么整个集群将暂停对外服务,进入新一轮Leader选举,其过程和启动时期的Leader选举过程基本一致。

假设正在运行的有Server1、Server2、Server3三台服务器,当前Leader是Server2,若某一时刻Leader挂了,此时便开始Leader选举。

选举过程如下:

  • (1) 变更状态。Leader挂后,余下的非Observer服务器都会讲自己的服务器状态变更为LOOKING,然后开始进入Leader选举过程。
  • (2) 每个Server会发出一个投票。在运行期间,每个服务器上的ZXID可能不同,此时假定Server1的ZXID为123,Server3的ZXID为122;在第一轮投票中,Server1和Server3都会投自己,产生投票(1, 123),(3, 122),然后各自将投票发送给集群中所有机器。
  • (3) 接收来自各个服务器的投票。与启动时过程相同。
  • (4) 处理投票。与启动时过程相同,此时,Server1将会成为Leader。
  • (5) 统计投票。与启动时过程相同。
  • (6) 改变服务器的状态。与启动时过程相同。

2.2 Leader选举算法分析

在3.4.0后的Zookeeper的版本只保留了TCP版本的FastLeaderElection选举算法。当一台机器进入Leader选举时,当前集群可能会处于以下两种状态

  • 集群中已经存在Leader。
  • 集群中不存在Leader。

对于集群中已经存在Leader而言,此种情况一般都是某台机器启动得较晚,在其启动之前,集群已经在正常工作,对这种情况,该机器试图去选举Leader时,会被告知当前服务器的Leader信息,对于该机器而言,仅仅需要和Leader机器建立起连接,并进行状态同步即可。而在集群中不存在Leader情况下则会相对复杂,其步骤如下

(1) 第一次投票。无论哪种导致进行Leader选举,集群的所有机器都处于试图选举出一个Leader的状态,即LOOKING状态,LOOKING机器会向所有其他机器发送消息,该消息称为投票。投票中包含了SID(服务器的唯一标识)和ZXID(事务ID),(SID, ZXID)形式来标识一次投票信息。假定Zookeeper由5台机器组成,SID分别为1、2、3、4、5,ZXID分别为9、9、9、8、8,并且此时SID为2的机器是Leader机器,某一时刻,1、2所在机器出现故障,因此集群开始进行Leader选举。在第一次投票时,每台机器都会将自己作为投票对象,于是SID为3、4、5的机器投票情况分别为(3, 9),(4, 8), (5, 8)。

(2) 变更投票。每台机器发出投票后,也会收到其他机器的投票,每台机器会根据一定规则来处理收到的其他机器的投票,并以此来决定是否需要变更自己的投票,这个规则也是整个Leader选举算法的核心所在,其中术语描述如下

  • vote_sid:接收到的投票中所推举Leader服务器的SID。
  • vote_zxid:接收到的投票中所推举Leader服务器的ZXID。
  • self_sid:当前服务器自己的SID。
  • self_zxid:当前服务器自己的ZXID。

每次对收到的投票的处理,都是对(vote_sid, vote_zxid)和(self_sid, self_zxid)对比的过程。

  • 规则一:如果vote_zxid大于self_zxid,就认可当前收到的投票,并再次将该投票发送出去。
  • 规则二:如果vote_zxid小于self_zxid,那么坚持自己的投票,不做任何变更。
  • 规则三:如果vote_zxid等于self_zxid,那么就对比两者的SID,如果vote_sid大于self_sid,那么就认可当前收到的投票,并再次将该投票发送出去。
  • 规则四:如果vote_zxid等于self_zxid,并且vote_sid小于self_sid,那么坚持自己的投票,不做任何变更。

结合上面规则,给出下面的集群变更过程。

Zookeeper选举算法原理

 

(3) 确定Leader。经过第二轮投票后,集群中的每台机器都会再次接收到其他机器的投票,然后开始统计投票,如果一台机器收到了超过半数的相同投票,那么这个投票对应的SID机器即为Leader。此时Server3将成为Leader。

由上面规则可知,通常那台服务器上的数据越新(ZXID会越大),其成为Leader的可能性越大,也就越能够保证数据的恢复。如果ZXID相同,则SID越大机会越大。

2.3 Leader选举实现细节

1. 服务器状态

服务器具有四种状态,分别是LOOKING、FOLLOWING、LEADING、OBSERVING。

  • LOOKING:寻找Leader状态。当服务器处于该状态时,它会认为当前集群中没有Leader,因此需要进入Leader选举状态。
  • FOLLOWING:跟随者状态。表明当前服务器角色是Follower。
  • LEADING:领导者状态。表明当前服务器角色是Leader。
  • OBSERVING:观察者状态。表明当前服务器角色是Observer。

2. 投票数据结构

每个投票中包含了两个最基本的信息,所推举服务器的SID和ZXID,投票(Vote)在Zookeeper中包含字段如下

  • id:被推举的Leader的SID。
  • zxid:被推举的Leader事务ID。
  • electionEpoch:逻辑时钟,用来判断多个投票是否在同一轮选举周期中,该值在服务端是一个自增序列,每次进入新一轮的投票后,都会对该值进行加1操作。
  • peerEpoch:被推举的Leader的epoch。
  • state:当前服务器的状态。

为什么zookeeper集群是单数?

1、容错

由于在增删改操作中需要半数以上服务器通过,来分析以下情况。

2台服务器,至少2台正常运行才行(2的半数为1,半数以上最少为2),正常运行1台服务器都不允许挂掉

3台服务器,至少2台正常运行才行(3的半数为1.5,半数以上最少为2),正常运行可以允许1台服务器挂掉

4台服务器,至少3台正常运行才行(4的半数为2,半数以上最少为3),正常运行可以允许1台服务器挂掉

5台服务器,至少3台正常运行才行(5的半数为2.5,半数以上最少为3),正常运行可以允许2台服务器挂掉

6台服务器,至少3台正常运行才行(6的半数为3,半数以上最少为4),正常运行可以允许2台服务器挂掉

通过以上可以发现,3台服务器和4台服务器都最多允许1台服务器挂掉,5台服务器和6台服务器都最多允许2台服务器挂掉

但是明显4台服务器成本高于3台服务器成本,6台服务器成本高于5服务器成本。这是由于半数以上投票通过决定的。

2、防脑裂

一个zookeeper集群中,可以有多个follower、observer服务器,但是必需只能有一个leader服务器。

如果leader服务器挂掉了,剩下的服务器集群会通过半数以上投票选出一个新的leader服务器。

集群互不通讯情况:

一个集群3台服务器,全部运行正常,但是其中1台裂开了,和另外2台无法通讯。3台机器里面2台正常运行过半票可以选出一个leader。

一个集群4台服务器,全部运行正常,但是其中2台裂开了,和另外2台无法通讯。4台机器里面2台正常工作没有过半票以上达到3,无法选出leader正常运行。

一个集群5台服务器,全部运行正常,但是其中2台裂开了,和另外3台无法通讯。5台机器里面3台正常运行过半票可以选出一个leader。

一个集群6台服务器,全部运行正常,但是其中3台裂开了,和另外3台无法通讯。6台机器里面3台正常工作没有过半票以上达到4,无法选出leader正常运行。

通可以上分析可以看出,为什么zookeeper集群数量总是单出现,主要原因还是在于第2点,防脑裂,对于第1点,无非是正常控制,但是不影响集群正常运行。但是出现第2种裂的情况,zookeeper集群就无法正常运行了。

ZooKeeper的脑裂的出现和解决方案

出现:

在搭建hadoop的HA集群环境后,由于两个namenode的状态不一,当active的namenode由于网络等原因出现假死状态,standby接收不到active的心跳,因此判断active的namenode宕机,但实际上active并没有死亡。此时standby的namenode就会切换成active的状态,保证服务能够正常使用。若原来的namenode复活,此时在整个集群中就出现2个active状态的namenode,该状态成为脑裂。脑裂现象可能导致这2个namenode争抢资源,从节点不知道该连接哪一台namenode,导致节点的数据不统一,这在企业生产中是不可以容忍的。

解决方案:

1、添加心跳线。

原来两个namenode之间只有一条心跳线路,此时若断开,则接收不到心跳报告,判断对方已经死亡。此时若有2条心跳线路,一条断开,另一条仍然能够接收心跳报告,能保证集群服务正常运行。2条心跳线路同时断开的可能性比1条心跳线路断开的小得多。再有,心跳线路之间也可以HA(高可用),这两条心跳线路之间也可以互相检测,若一条断开,则另一条马上起作用。正常情况下,则不起作用,节约资源。

2、启用磁盘锁。

由于两个active会争抢资源,导致从节点不知道该连接哪一台namenode,可以使用磁盘锁的形式,保证集群中只能有一台namenode获取磁盘锁,对外提供服务,避免数据错乱的情况发生。但是,也会存在一个问题,若该namenode节点宕机,则不能主动释放锁,那么其他的namenode就永远获取不了共享资源。因此,在HA上使用"智能锁"就成为了必要措施。"智能锁"是指active的namenode检测到了心跳线全部断开时才启动磁盘锁,正常情况下不上锁。保证了假死状态下,仍然只有一台namenode的节点提供服务。

3、设置仲裁机制

脑裂导致的后果最主要的原因就是从节点不知道该连接哪一台namenode,此时如果有一方来决定谁留下,谁放弃就最好了。因此出现了仲裁机制,比如提供一个参考的IP地址,当出现脑裂现象时,双方接收不到对方的心跳机制,但是能同时ping参考IP,如果有一方ping不通,那么表示该节点网络已经出现问题,则该节点需要自行退出争抢资源的行列,或者更好的方法是直接强制重启,这样能更好的释放曾经占有的共享资源,将服务的提供功能让给功能更全面的namenode节点。

以上的3种方式可以同时使用,这样更能减少集群中脑裂情况的发生。但是还是不能保证完全不出现,如果仲裁机制中2台机器同时宕机,那么此时集群中没有namenode可以使用。此时需要运维人员人工的抢修,或者提供一台新的机器作为namenode,这个时间是不可避免的。希望未来能有更好的解决办法,能彻底杜绝这类情况的发生吧~




上一篇:解决MybatisGenerator多次运行mapper生成重复内容
下一篇:没有了

友情链接:
  • 全球最大晶圆代工半导体制造厂,台积电斥资订购艾斯摩尔机器设备
  • 英特尔依然是那个英特尔,且看英特尔的城防体系
  • 支持双 DRAM 内存接口,慧荣企业级 SSD 主控方案披露
  • 在全球被反垄断罚款,冤!高通到底哪里得罪了欧盟?
  • 强强联合!万业、微电子所和芯鑫共同打造全新半导体设备
  • 复旦大学校长称:对于集成电路产业发展,大学应该主动担当
  • 技术再升级!无锡中科芯攻克晶圆级再布线及晶圆级凸点制备关键技
  • 聚力!万业企业设立集成电路装备集团,提供自主可控设备
  • 德州仪器C2000微控制器增强连通性和控制性
  • 英特尔打出降价策略,以免被竞争对手 AMD 打败?
  • 贸易摩擦的闹剧没有赢家,苹果有勇气离开中国吗?
  • 图像信号与视觉处理器的发展趋势
  • 真干快消品定位方案班(第二期)火热开班
  • Java集合 ArrayList原理及使用
  • TDD(测试驱动开发)死了吗?
  • JAVA基础之XML相关
  • javaweb项目搭建ehcache缓存系统
  • 每日一码——字符串统计
  • 一篇文章帮你彻底搞清楚“I/O多路复用”和“异步I/O”的前世今生
  • 九:模板方法模式
  • 十二:命令模式(人员解耦和)
  • Java 转PPT为图片、PDF、SVG、XPS、ODP以及PPT和PPTX互转
  • SpringCloud学习(SPRINGCLOUD微服务实战)一
  • 记一次微信网页授权后获取用户信息并重定向
  • 速途新营销五点实战洞察解码“品效合一”
  • 十一:外观模式详解(Service,action与dao)
  • 手把手教你学会 基于JWT的单点登录
  • mysql锁机制总结,以及优化建议
  • 解决多个版本jar包冲突【jar内包名重命名】
  • 中国首张5G终端电信设备进网许可证 华为Mate 20 X 5G版入网
  • RPC之Thrift
  • 高级Java工程师必备 ----
  • 天猫618期间实物支付GMV增长38.5%
  • 换季了,老板你的库存处理好了吗?
  • 从“618”大数据看中国消费新活力
  • 小米生态链:贵在格局感与收放度
  • CODING 2.0 企业级持续交付解决方案
  • 老铁奇趴“新京济” 快手*京东618战报出炉
  • 中小企业新媒体运营基本技能
  • 上汽大通房车再度携手LINE FRIENDS 魔都巡游顺利开启
  • 华为高端手机国内市场份额超苹果夺得榜首
  • 中国智能制造分析报告
  • iPlus艾加营销助力腾讯广告牵手吴晓波 推进商业IP变现
  • 2019世界新能源汽车大会7月1日将在海南举行
  • 区域酒企如何转型突围
  • 时时彩论坛
  • 五星体育斯诺克
  • 北单比分直播
  • 河北11选5走势图
  • 福建体彩36选7开奖结果
  • 九龙图库下载