加载中…
正文 字体大小:

【Zookeeper】Zookeeper的FastLeaderElection算法分析

(2012-02-20 09:31:27)
标签:

zookeeper

fast

leader

election

算法

分类: 算法

我们知道,在经典的paxos算法中每一个peer都是proposer,但是这就不可避免的产生提案冲突,为了减少这种冲突带来的系统消耗与时间延迟,就产生了Leader这个角色,整个系统中,就只允许Leader可以发出提案。ZooKeeper就是按照这个思路来实现的。本文主要讨论ZooKeeper中的FastLeaderElection算法,来说明Leader是如何产生的。

 

我们先要清楚以下几点

l  一个Server是如何知道其它的Server

ZooKeeper集群中,Server的信息都在zoo.conf配置文件中,根据配置文件的信息就可以知道其它Server的信息。

l  ZooKeeper服务器有哪几种状态?(选主相关的状态)

LOOKING:寻找leader状态

LEADING:领导状态(节点为leader

FOLLOWING:跟随者状态

OBSERVING:观察者状态(此状态不参与选举)

l  成为Leader的必要条件?

Leader要具有最高的zxid集群中大多数的机器(至少n/2+1得到响应并follow选出的Leader

l  如果所有zxid都相同(例如刚初始化时),此时有可能不能形成n/2+1Server,怎么办?

ZooKeeper中每一个Server都有一个ID,这个ID是不重复的,如果遇到这样的情况时,ZooKeeper就推荐ID最大的哪个Server作为Leader

l  lookForLeader函数什么时候被调用?

Server的状态为LOOKING时,lookForLeader就会被调用。具体参见QuorumPeer类的run方法。

l  ZooKeeperLeader怎么知道Fllower还存活,Fllower怎么知道Leader还存活?

Leader定时向Fllowerping消息,Fllower定时向Leaderping消息,当发现Leader无法ping通时,就改变自己的状态(LOOKING),发起新的一轮选举。

 

算法相关的数据结构

收到的通知的数据结构:

static public class Notification {

long leader;//被推荐的leaderid

  long zxid;//被推荐的leader的事务id        

  long electionEpoch;//推荐者的选举周期

  QuorumPeer.ServerState state;//推荐者的状态

  long sid;//推荐者的id

  long peerEpoch;//被推荐的leader选举周期

}

 

 

发送通知使用数据结构(跟接收其实差不多):

static public class ToSend {

static enum mType {crequestchallengenotificationack}

 

  ToSend(mType type,

                  long leader,

                long zxid,

                long electionEpoch,

                ServerState state,

                long sid,

                long peerEpoch) {

 

            this.leader leader;

            this.zxid zxid;

            this.electionEpoch electionEpoch;

            this.state state;

            this.sid sid;

            this.peerEpoch peerEpoch;

        }

        long leader;//推荐的Leader ID

        long zxid;//推荐的Leader的最大事务ID

        long electionEpoch;// 推荐者本身的选举周期

        QuorumPeer.ServerState state;// 推荐者本身的状态

        long sid; // 推荐者本身的ID

        long peerEpoch; // 推荐的Leader的选举周期

}

 

 

 

关键字段、函数解释

l  leader

推荐的leaderid

l  zxid(ZooKeeper transaction id)

ZooKeeper事务Id,每个ZooKeeper状态的改变都会形成一个新的zxid值,这个值越大表示更新越新。

l  electionEpoch/logicalclock/peerEpoch

选举周期,用来判断是否为同一次选举。每调用一次选举函数,logicalclock自增1,并且在选举过程中如果遇到election比当前logicalclock大的值,就更新本地logicalclock的值。

 

l  public Vote lookForLeader() throws InterruptedException

选举函数,当ZooKeeper Server的状态变为LOOKING时,就会发起选举。函数会阻塞式地进行选主,直到最终的主产生,并返回为最终的投票结果。

 

l  synchronized void updateProposal(long leader, long zxid, long epoch)

更新投票

 

l  private boolean totalOrderPredicate(long newId, long newZxid, long newEpoch, long curId, long curZxid, long curEpoch)

将收到的对方的投票与当前自己的投票对比,判断对方的投票是否优于自己的投票。具体代码:

    protected boolean totalOrderPredicate(long newId, long newZxid, long newEpoch, long curId, long curZxid, long curEpoch) {

        LOG.debug("id: " + newId + ", proposed id: " + curId + ", zxid: 0x" +

                Long.toHexString(newZxid) + ", proposed zxid: 0x" + Long.toHexString(curZxid));

        // 使用计票器判断当前server的权重是否为0

        if(self.getQuorumVerifier().getWeight(newId) == 0){

            return false;

        }

       

       

        // 通过Epochzxidid来比较两个候选leader

        return ((newEpoch > curEpoch) ||

                ((newEpoch == curEpoch) &&

                ((newZxid > curZxid) || ((newZxid == curZxid) && (newId > curId)))));

    }

 

FastLeaderElection算法lookForLeader函数的主要逻辑)

1.发起一轮投票选举,推举自己作为leader,通知所有的服务器,等待接收外部选票。

 

2.只要当前服务器状态为LOOKING,进入循环,不断地读取其它Server发来的通知、进行比较、更新自己的投票、发送自己的投票、统计投票结果,直到leader选出或出错退出。具体作法:

从队列中取出一个Notification(选票),则根据消息中对方的状态进行相应的处理。

1LOOKING状态:

a.如果发送过来的逻辑时钟大于目前的逻辑时钟,那么说明这是更新的一次选举投票,此时更新本机的逻辑时钟(logicalclock),清空投票箱(因为已经过期没有用了),调用totalOrderPredicate函数判断对方的投票是否优于当前的投票(判断规则上面提过了),是的话用对方推荐的leader更新下一次的投票,否则使用初始的投票(投自己),调用sendNotifications() 通知所有服务器我的选择,跳到d

b.如果对方处于上轮投票,不予理睬,回到2

c.如果对方也处于本轮投票,调用totalOrderPredicate函数判断对方的投票是否优于当前的投票,是的话更新当前的投票,否则使用初始的投票(投自己)并新生成notification消息放入发送队列。调用sendNotifications() 通知所有服务器我的选择

d.将收到的投票放入自己的投票箱中。

e.调用计票器的containsQuorum函数,判断所推荐的leader是否得到集群多数人的同意(根据计票器的实现不同,可以是单纯看数量是否超过n/2,也可以是按权重来判断,我们这里假设单纯看数量),如果得到多数人同意,那么还需等待一段时间,看是否有比当前更优的提议,如果没有,则认为投票结束。根据投票结果修改自己的状态。以上任何一条不满足,则继续循环。

2OBSERVING状态:

不做任何事。

3FOLLOWINGLEADING状态:

a.如果选举周期相同(选票是同一轮选举产生),将该数据保存到投票箱,根据当前投票箱的投票判断对方推荐的leader是否得到多数人的同意,如果是则设置状态退出选举过程,否则到b

b.这是一条与当前逻辑时钟不符合的消息,或者对方推荐的leader没有得到多数人的同意(有可能是收集到的投票数不够)那么说明可能在另一个选举过程中已经有了选举结果,于是将该选举结果加入到outofelection集合中,再根据outofelection来判断是否可以结束选举,如果可以也是保存逻辑时钟,设置状态,退出选举过程。否则继续循环。outofelection用于保存那些状态为FOLLOWING或者LEADINGZooKeeper节点发送的选票,由于对方的状态为FOLLOWING或者LEADING,所以它们当前不参与选举过程(可能人家已经选完了),因此称为“out of election”

 

参考资料

分布式设计与开发(三)——高一致性服务ZooKeeperhttp://www.360doc.com/content/11/1215/11/116188_172393672.shtml

Zookeeper全解析——Paxos作为灵魂:http://www.spnguru.com/2010/08/zookeeper全解析——paxos的灵魂/

一个不错的讲解zookeeper选举算法的:http://blog.csdn.net/xhh198781/article/details/6619203

 

0

阅读 评论 收藏 转载 喜欢 打印举报
已投稿到:
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 不良信息反馈 电话:4006900000 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有