高可用保障.选举

相信有几年工作经验的技术人员都有自己的知识库，遇到问题首先大脑会快速索引一下去自己的知识库找解决方案，再次去官网或gg。本着技术人员传播分享的优良传统，试着分享一下zk的源码中的选举流程

zookeeper作为分布式系统常用的中间件，其特点和适应场景相信大家都清楚，比如kafka使用zk做leader选举。那么zk自己的leader选举又是怎样的呢？

下载源码，找到zkServer.sh

找到ZOOMAIN入口类

ZOOMAIN="org.apache.zookeeper.server.quorum.QuorumPeerMain"

其中QuorumPeerMain的initializeAndRun()方法

    protected void initializeAndRun(String[] args)
        throws ConfigException, IOException, AdminServerException
    {
    
        QuorumPeerConfig config = new QuorumPeerConfig();
        if (args.length == 1) {
    
            config.parse(args[0]);
        }

        // Start and schedule the the purge task
        DatadirCleanupManager purgeMgr = new DatadirCleanupManager(config
                .getDataDir(), config.getDataLogDir(), config
                .getSnapRetainCount(), config.getPurgeInterval());
        purgeMgr.start();
        //判断是否集群模式
        if (args.length == 1 && config.isDistributed()) {
    
            runFromConfig(config);
        } else {
    
            LOG.warn("Either no config or no quorum defined in config, running "
                    + " in standalone mode");
            // there is only server in the quorum -- run as standalone
            ZooKeeperServerMain.main(args);
        }
    }

单机模式就不用再往下看了，没选举什么事，集群模式继续往下走runFromConfig(config)方法

    public void runFromConfig(QuorumPeerConfig config)
            throws IOException, AdminServerException {
    
      ....
      try {
    
          ServerCnxnFactory cnxnFactory = null;
          ServerCnxnFactory secureCnxnFactory = null;
          //为客户端提供读写的server, 2181。集群配置中的另一个端口是选举时的通信端口
          if (config.getClientPortAddress() != null) {
    
              cnxnFactory = ServerCnxnFactory.createFactory();
              cnxnFactory.configure(config.getClientPortAddress(),
                      config.getMaxClientCnxns(),
                      false);
          }

          if (config.getSecureClientPortAddress() != null) {
    
              secureCnxnFactory = ServerCnxnFactory.createFactory();
              secureCnxnFactory.configure(config.getSecureClientPortAddress(),
                      config.getMaxClientCnxns(),
                      true);
          }
          //QuorumPeer类选举、投票实现
          quorumPeer = getQuorumPeer();
          quorumPeer.setTxnFactory(new FileTxnSnapLog(
                      config.getDataLogDir(),
                      config.getDataDir()));
          quorumPeer.enableLocalSessions(config.areLocalSessionsEnabled());
          quorumPeer.enableLocalSessionsUpgrading(
              config.isLocalSessionsUpgradingEnabled());
          //quorumPeer.setQuorumPeers(config.getAllMembers());
          quorumPeer.setElectionType(config.getElectionAlg());
          quorumPeer.setMyid(config.getServerId());
          quorumPeer.setTickTime(config.getTickTime());
          quorumPeer.setMinSessionTimeout(config.getMinSessionTimeout());
          quorumPeer.setMaxSessionTimeout(config.getMaxSessionTimeout());
          quorumPeer.setInitLimit(config.getInitLimit());
          quorumPeer.setSyncLimit(config.getSyncLimit());
          quorumPeer.setConfigFileName(config.getConfigFilename());
          quorumPeer.setZKDatabase(new ZKDatabase(quorumPeer.getTxnFactory()));
          quorumPeer.setQuorumVerifier(config.getQuorumVerifier(), false);
          if (config.getLastSeenQuorumVerifier()!=null) {
    
              quorumPeer.setLastSeenQuorumVerifier(config.getLastSeenQuorumVerifier(), false);
          }
          quorumPeer.initConfigInZKDatabase();
          quorumPeer.setCnxnFactory(cnxnFactory);
          quorumPeer.setSecureCnxnFactory(secureCnxnFactory);
          quorumPeer.setLearnerType(config.getPeerType());
          quorumPeer.setSyncEnabled(config.getSyncEnabled());
          quorumPeer.setQuorumListenOnAllIPs(config.getQuorumListenOnAllIPs());
          //
          quorumPeer.start();
          quorumPeer.join();
      } catch (InterruptedException e) {
    
          // warn, but generally this is ok
          LOG.warn("Quorum Peer interrupted", e);
      }
    }

去QuorumPeer类中就能找到投票、选举的实现逻辑

@Override
    public synchronized void start() {
    
        if (!getView().containsKey(myid)) {
    
            throw new RuntimeException("My id " + myid + " not in the peer list");
         }
        loadDataBase();  //此方法主要是从本地文件中最终得到zxid的逻辑
        startServerCnxnFactory();
        try {
    
            adminServer.start();
        } catch (AdminServerException e) {
    
            LOG.warn("Problem starting AdminServer", e);
            System.out.println(e);
        }
        startLeaderElection();//开始选举
        super.start();
    }

跟进startLeaderElection()

protected Election createElectionAlgorithm(int electionAlgorithm){
    
        Election le=null;

        //TODO: use a factory rather than a switch
        switch (electionAlgorithm) {
    
            case 1:
                le = new AuthFastLeaderElection(this);
                break;
            case 2:
                le = new AuthFastLeaderElection(this, true);
                break;
            case 3:
                //Leader选举manager类,管理节点间选举通知的一些操作
                qcm = new QuorumCnxManager(this);
                QuorumCnxManager.Listener listener = qcm.listener;
                if(listener != null){
    
                    listener.start(); //启动选举线程
                    FastLeaderElection fle = new FastLeaderElection(this, qcm);
                    fle.start();
                    le = fle;
                } else {
    
                    LOG.error("Null listener when initializing cnx manager");
                }
                break;
            default:
                assert false;
        }
        return le;
    }

进入FastLeaderElection类，看主要执行逻辑

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));
        if(self.getQuorumVerifier().getWeight(newId) == 0){
    
            return false;
        }

        /*
         * We return true if one of the following three cases hold:
         * 1- New epoch is higher
         * 2- New epoch is the same as current epoch, but new zxid is higher
         * 3- New epoch is the same as current epoch, new zxid is the same
         *  as current zxid, but server id is higher.
         */
         // 1.若epoch大，为leader
         // 2.若epoch相等，zxid大，为leader
         // 3.若zxid相等，则比较myid(配置文件中)

        return ((newEpoch > curEpoch) ||
                ((newEpoch == curEpoch) &&
                ((newZxid > curZxid) || ((newZxid == curZxid) && (newId > curId)))));
    }

totalOrderPredicate()方法在见lookForLeader();

public Vote lookForLeader() throws InterruptedException {
    
    ...
        try {
    
            //存放其它节点的投票
            HashMap<Long, Vote> recvset = new HashMap<Long, Vote>();
            //存放选举
            HashMap<Long, Vote> outofelection = new HashMap<Long, Vote>();

            int notTimeout = finalizeWait;

            synchronized(this){
    
                logicalclock.incrementAndGet(); //增加逻辑时钟
                //更新自己的zxid和epoch
                updateProposal(getInitId(), getInitLastLoggedZxid(), getPeerEpoch());
            }

            LOG.info("New election. My id =  " + self.getId() +
                    ", proposed zxid=0x" + Long.toHexString(proposedZxid));
            sendNotifications(); //通知投票

            /*
             * Loop in which we exchange notifications until we find a leader
             */

            while ((self.getPeerState() == ServerState.LOOKING) &&
                    (!stop)){
    //loop直到选举出leader
                /*
                 * Remove next notification from queue, times out after 2 times
                 * the termination time
                 */
                // 拿到投票消息
                //recvqueue->LinkedBlockedQueue()
                Notification n = recvqueue.poll(notTimeout,
                        TimeUnit.MILLISECONDS);

                /*
                 * Sends more notifications if haven't received enough.
                 * Otherwise processes new notification.
                 */
                if(n == null){
    
                    if(manager.haveDelivered()){
    
                        sendNotifications();
                    } else {
    
                   //等待其它节点就绪？
                        manager.connectAll();
                    }

                    /*
                     * Exponential backoff
                     */
                    int tmpTimeOut = notTimeout*2;
                    notTimeout = (tmpTimeOut < maxNotificationInterval?
                            tmpTimeOut : maxNotificationInterval);
                    LOG.info("Notification time out: " + notTimeout);
                }
                //判断收到的消息是不是属于这个集群内,n.sid就是我们配置的myid
                else if (self.getCurrentAndNextConfigVoters().contains(n.sid)) {
    
                    /*
                     * Only proceed if the vote comes from a replica in the current or next
                     * voting view.
                     */
                    switch (n.state) {
    //节点的状态
                    case LOOKING:
                        if (getInitLastLoggedZxid() == -1) {
    
                            LOG.debug("Ignoring notification as our zxid is -1");
                            break;
                        }
                        if (n.zxid == -1) {
    
                            LOG.debug("Ignoring notification from member with -1 zxid" + n.sid);
                            break;
                        }
                        // If notification > current, replace and send messages out
                        //epoch大于logicalclock，则为是新一轮选举
                        if (n.electionEpoch > logicalclock.get()) {
    
                            logicalclock.set(n.electionEpoch); //更新本地的logicalclock
                            recvset.clear();
                            //比较本轮是否可以胜出（是比较传递过来的票据）
                            if(totalOrderPredicate(n.leader, n.zxid, n.peerEpoch,
                                    getInitId(), getInitLastLoggedZxid(), getPeerEpoch())) {
    
                                //若胜出，把投票改为对方的票据
                                updateProposal(n.leader, n.zxid, n.peerEpoch);
                            } else {
    //否则，票据不变
                                updateProposal(getInitId(),
                                        getInitLastLoggedZxid(),
                                        getPeerEpoch());
                            }
                            sendNotifications();//将本身的票据广播到集群节点
                            //若收到的epoch小于本身节点的epoch，则忽略
                        } else if (n.electionEpoch < logicalclock.get()) {
    
                            if(LOG.isDebugEnabled()){
    
                                LOG.debug("Notification election epoch is smaller than logicalclock. n.electionEpoch = 0x"
                                        + Long.toHexString(n.electionEpoch)
                                        + ", logicalclock=0x" + Long.toHexString(logicalclock.get()));
                            }
                            break;
                            //若epoch相同，则zxid、myid，如果本轮胜出，更新自己的票据，通知其他节点
                        } else if (totalOrderPredicate(n.leader, n.zxid, n.peerEpoch,
                                proposedLeader, proposedZxid, proposedEpoch)) {
    
                            updateProposal(n.leader, n.zxid, n.peerEpoch);//更新
                            sendNotifications();//通知其他节点
                        }

                        if(LOG.isDebugEnabled()){
    
                            LOG.debug("Adding vote: from=" + n.sid +
                                    ", proposed leader=" + n.leader +
                                    ", proposed zxid=0x" + Long.toHexString(n.zxid) +
                                    ", proposed election epoch=0x" + Long.toHexString(n.electionEpoch));
                        }
                        //存储收到的投票
                        recvset.put(n.sid, new Vote(n.leader, n.zxid, n.electionEpoch, n.peerEpoch));

                        //过半节点一致选举leader则选举结束
                        if (termPredicate(recvset,
                                new Vote(proposedLeader, proposedZxid,
                                        logicalclock.get(), proposedEpoch))) {
    
                            // Verify if there is any change in the proposed leader
                            //等待队列中的消息
                            while((n = recvqueue.poll(finalizeWait,
                                    TimeUnit.MILLISECONDS)) != null){
    
                                if(totalOrderPredicate(n.leader, n.zxid, n.peerEpoch,
                                        proposedLeader, proposedZxid, proposedEpoch)){
    
                                    recvqueue.put(n);
                                    break;
                                }
                            }
                            /*
                             * This predicate is true once we don't read any new
                             * relevant message from the reception queue
                             */
                            //选举LEADER
                            if (n == null) {
    
                                //LEADING | FOLLOWING
                                self.setPeerState((proposedLeader == self.getId()) ?
                                        ServerState.LEADING: learningState());
                                //最终投票结果
                                Vote endVote = new Vote(proposedLeader,
                                        proposedZxid, proposedEpoch);
                                leaveInstance(endVote);
                                return endVote;
                            }
                        }
                        break;
                        //OBSERVING角色不参加选举
                    case OBSERVING:
                        LOG.debug("Notification from observer: " + n.sid);
                        break;
                        //FOLLOWING和LEADING节点都需要参与选举
                    case FOLLOWING:
                    case LEADING:
                        /*
                         * Consider all notifications from the same epoch
                         * together.
                         */
                        if(n.electionEpoch == logicalclock.get()){
     //判断epoch是否相同
                            //加入到本机的投票集合
                            recvset.put(n.sid, new Vote(n.leader, n.zxid, n.electionEpoch, n.peerEpoch));
                            //投票是否结束，如果结束，再确认LEADER是否有效
                            //如果结束，修改自己的状态并返回投票结果
                            if(termPredicate(recvset, new Vote(n.leader,
                                            n.zxid, n.electionEpoch, n.peerEpoch, n.state))
                                            && checkLeader(outofelection, n.leader, n.electionEpoch)) {
    
                                self.setPeerState((n.leader == self.getId()) ?
                                        ServerState.LEADING: learningState());

                                Vote endVote = new Vote(n.leader, n.zxid, n.peerEpoch);
                                leaveInstance(endVote);
                                return endVote;
                            }
                        }

                       ...
    }

总结：投票选举流程即，比较集群内节点zxid,myid,统计投票结果得出leader。
附本人平时的一些笔记，欢迎私信分享