集群管理選舉算法實現(xiàn)

一個分布式服務(wù)集群管理通常需要一個協(xié)調(diào)服務(wù)，提供服務(wù)注冊、服務(wù)發(fā)現(xiàn)、配置管理、組服務(wù)等功能，而協(xié)調(diào)服務(wù)自身應(yīng)是一個高可用的服務(wù)集群，ZooKeeper是廣泛應(yīng)用且眾所周知的協(xié)調(diào)服務(wù)。協(xié)調(diào)服務(wù)自身的高可用需要選舉算法來支撐，本文將講述選舉原理并以分布式服務(wù)集群NebulaBootstrap的協(xié)調(diào)服務(wù)NebulaBeacon為例詳細(xì)說明協(xié)調(diào)服務(wù)的選舉實現(xiàn)。

??為什么要選NebulaBeacon來說明協(xié)調(diào)服務(wù)的選舉實現(xiàn)？一方面是我沒有讀過Zookeeper的代碼，更重要的另一方面是NebulaBeacon的選舉實現(xiàn)只有兩百多行代碼，簡單精煉，很容易講清楚?；诟咝阅蹸++網(wǎng)絡(luò)框架Nebula實現(xiàn)的分布式服務(wù)集群NebulaBootstrap是一種用C++快速構(gòu)建高性能分布式服務(wù)的解決方案。

??為什么要實現(xiàn)自己的協(xié)調(diào)服務(wù)而不直接用Zookeeper？想造個C++的輪子，整個集群都是C++服務(wù)，因為選了ZooKeeper而需要部署一套Java環(huán)境，配置也跟其他服務(wù)不是一個體系，實在不是一個好的選擇。Spring Cloud有Eureka，NebulaBootstrap有NebulaBeacon，未來NebulaBootstrap會支持ZooKeeper，不過暫無時間表，還是首推NebulaBeacon。

1. 選舉算法選擇

??Paxos算法 和 ZooKeeper ZAB協(xié)議 是兩種較廣為人知的選舉算法。ZAB協(xié)議主要用于構(gòu)建一個高可用的分布式數(shù)據(jù)主備系統(tǒng)，例如ZooKeeper，而Paxos算法則是用于構(gòu)建一個分布式的一致性狀態(tài)機系統(tǒng)。也有很多應(yīng)用程序采用自己設(shè)計的簡單的選舉算法，這類型簡單的選舉算法通常依賴計算機自身因素作為選舉因子，比如IP地址、CPU核數(shù)、內(nèi)存大小、自定義序列號等。

??Paxos規(guī)定了四種角色（Proposer，Acceptor，Learner，以及Client）和兩個階段（Promise和Accept）。 ??ZAB服務(wù)具有四種狀態(tài)：LOOKING、FOLLOWING、LEADING、OBSERVING。 ??NebulaBeacon是高可用分布式系統(tǒng)的協(xié)調(diào)服務(wù)，采用ZAP協(xié)議更為合適，不過ZAP協(xié)議還是稍顯復(fù)雜了，NebulaBeacon的選舉算法實現(xiàn)基于節(jié)點的IP地址標(biāo)識，選舉速度快，實現(xiàn)十分簡單。

2. 選舉相關(guān)數(shù)據(jù)結(jié)構(gòu)

??NebulaBeacon的選舉相關(guān)數(shù)據(jù)結(jié)構(gòu)非常簡單：

const uint32 SessionOnlineNodes::mc_uiLeader = 0x80000000;   ///< uint32最高位為1表示leader
const uint32 SessionOnlineNodes::mc_uiAlive  = 0x00000007;   ///< 最近三次心跳任意一次成功則認(rèn)為在線
std::map<std::string, uint32> m_mapBeacon;                   ///< Key為節(jié)點標(biāo)識，值為在線心跳及是否為leader標(biāo)識

??如上數(shù)據(jù)結(jié)構(gòu)m_mapBeacon保存了Beacon集群各Beacon節(jié)點信息，以Beacon節(jié)點的IP地址標(biāo)識為key排序，每次遍歷均從頭開始，滿足條件（1&&2 或者 1&&3）則標(biāo)識為Leader：1. 節(jié)點在線；2. 已經(jīng)成為Leader； 3. 整個列表中不存在在線的Leader，而節(jié)點處于在線節(jié)點列表的首位。

3. Beacon選舉流程

??Beacon選舉基于節(jié)點IP地址標(biāo)識，實現(xiàn)非常簡單且高效。

"beacon":["192.168.1.11:16000", "192.168.1.12:16000"]

??進程啟動時首先檢查Beacon集群配置，若未配置其他Beacon節(jié)點信息，則默認(rèn)只有一個Beacon節(jié)點，此時該節(jié)點在啟動時自動成為Leader節(jié)點。否則，向其他Beacon節(jié)點發(fā)送一個心跳消息，等待定時器回調(diào)檢查并選舉出Leader節(jié)點。選舉流程如下圖：

??檢查是否在線就是通過檢查兩次定時器回調(diào)之間是否收到了其他Beacon節(jié)點的心跳消息。對m_mapBeacon的遍歷檢查判斷節(jié)點在線情況，對已離線的Leader節(jié)點置為離線狀態(tài)，若當(dāng)前節(jié)點應(yīng)成為Leader節(jié)點則成為Leader節(jié)點。

4. Beacon節(jié)點間選舉通信

??Beacon節(jié)點間的選舉通信與節(jié)點心跳合為一體，這樣做的好處是當(dāng)leader節(jié)點不可用時，fllower節(jié)點立刻可以成為leader節(jié)點，選舉過程只需每個fllower節(jié)點遍歷自己內(nèi)存中各Beacon節(jié)點的心跳信息即可，無須在發(fā)現(xiàn)leader不在線才發(fā)起選舉，更快和更好地保障集群的高可用性。

??Beacon節(jié)點心跳信息帶上了leader節(jié)點作為協(xié)調(diào)服務(wù)產(chǎn)生的新數(shù)據(jù)，fllower節(jié)點在接收心跳的同時完成了數(shù)據(jù)同步，保障任意一個fllower成為leader時已獲得集群所有需協(xié)調(diào)的信息并可隨時切換為leader。除定時器觸發(fā)的心跳帶上協(xié)調(diào)服務(wù)產(chǎn)生的新數(shù)據(jù)之外，leader節(jié)點產(chǎn)生新數(shù)據(jù)的同時會立刻向fllower發(fā)送心跳。

5. Beacon選舉實現(xiàn)

??Beacon心跳協(xié)議proto：

/**
 * @brief BEACON節(jié)點間心跳
 */message Election
{
    int32 is_leader                  = 1;    ///< 是否主節(jié)點
    uint32 last_node_id              = 2;    ///< 上一個生成的節(jié)點ID
    repeated uint32 added_node_id    = 3;    ///< 新增已使用的節(jié)點ID
    repeated uint32 removed_node_id  = 4;    ///< 刪除已廢棄的節(jié)點ID
}

??檢查Beacon配置，若只有一個Beacon節(jié)點則自動成為Leader：

void SessionOnlineNodes::InitElection(const neb::CJsonObject& oBeacon)
{
    neb::CJsonObject oBeaconList = oBeacon;    
    for (int i = 0; i < oBeaconList.GetArraySize(); ++i)
    {
        m_mapBeacon.insert(std::make_pair(oBeaconList(i) + ".1", 0));
    }    if (m_mapBeacon.size() == 0)
    {
        m_bIsLeader = true;
    }    else if (m_mapBeacon.size() == 1
            && GetNodeIdentify() == m_mapBeacon.begin()->first)
    {
        m_bIsLeader = true;
    }    else
    {
        SendBeaconBeat();
    }
}

??發(fā)送Beacon心跳：

void SessionOnlineNodes::SendBeaconBeat()
{
    LOG4_TRACE("");
    MsgBody oMsgBody;
    Election oElection;    
    if (m_bIsLeader)
    {
        oElection.set_is_leader(1);
        oElection.set_last_node_id(m_unLastNodeId);        
        for (auto it = m_setAddedNodeId.begin(); it != m_setAddedNodeId.end(); ++it)
        {
            oElection.add_added_node_id(*it);
        }        
        for (auto it = m_setRemovedNodeId.begin(); it != m_setRemovedNodeId.end(); ++it)
        {
            oElection.add_removed_node_id(*it);
        }
    }    
    else
    {
        oElection.set_is_leader(0);
    }
    m_setAddedNodeId.clear();
    m_setRemovedNodeId.clear();
    oMsgBody.set_data(oElection.SerializeAsString());    
    for (auto iter = m_mapBeacon.begin(); iter != m_mapBeacon.end(); ++iter)
    {        
        if (GetNodeIdentify() != iter->first)
        {
            SendTo(iter->first, neb::CMD_REQ_LEADER_ELECTION, GetSequence(), oMsgBody);
        }
    }
}

??接收Beacon心跳：

void SessionOnlineNodes::AddBeaconBeat(const std::string& strNodeIdentify, const Election& oElection)
{    
    if (!m_bIsLeader)
    {        
        if (oElection.last_node_id() > 0)
        {
            m_unLastNodeId = oElection.last_node_id();
        }        
        for (int32 i = 0; i < oElection.added_node_id_size(); ++i)
        {
            m_setNodeId.insert(oElection.added_node_id(i));
        }        
        for (int32 j = 0; j < oElection.removed_node_id_size(); ++j)
        {
            m_setNodeId.erase(m_setNodeId.find(oElection.removed_node_id(j)));
        }
    }    
    auto iter = m_mapBeacon.find(strNodeIdentify);    
    if (iter == m_mapBeacon.end())
    {
        uint32 uiBeaconAttr = 1;        
        if (oElection.is_leader() != 0)
        {
            uiBeaconAttr |= mc_uiLeader;
        }
        m_mapBeacon.insert(std::make_pair(strNodeIdentify, uiBeaconAttr));
    }    
    else
    {
        iter->second |= 1;        
        if (oElection.is_leader() != 0)
        {
            iter->second |= mc_uiLeader;
        }
    }
}

??檢查在線leader，成為leader：

void SessionOnlineNodes::CheckLeader()
{
    LOG4_TRACE("");    
    std::string strLeader;    
    for (auto iter = m_mapBeacon.begin(); iter != m_mapBeacon.end(); ++iter)
    {        
        if (mc_uiAlive & iter->second)
        {            
            if (mc_uiLeader & iter->second)
            {
                strLeader = iter->first;
            }            
            else if (strLeader.size() == 0)
            {
                strLeader = iter->first;
            }
        }        
        else
        {
            iter->second &= (~mc_uiLeader);
        }
        uint32 uiLeaderBit = mc_uiLeader & iter->second;
        iter->second = ((iter->second << 1) & mc_uiAlive) | uiLeaderBit;        
        if (iter->first == GetNodeIdentify())
        {
            iter->second |= 1;
        }
    }    
    if (strLeader == GetNodeIdentify())
    {
        m_bIsLeader = true;
    }
}

6. Beacon節(jié)點切換leader

??通過Nebula集群的命令行管理工具nebcli可以很方便的查看Beacon節(jié)點狀態(tài)，nebcli的使用說明見Nebcli項目的README。下面啟動三個Beacon節(jié)點，并反復(fù)kill掉Beacon進程和重啟，查看leader節(jié)點的切換情況。

??啟動三個beacon節(jié)點：

nebcli): show beacon
node                        is_leader       is_online
192.168.157.176:16000.1     yes             yes
192.168.157.176:17000.1     no              yes
192.168.157.176:18000.1     no              yes

??kill掉leader節(jié)點：

nebcli): show beacon
node                        is_leader       is_online
192.168.157.176:16000.1     no              no
192.168.157.176:17000.1     yes             yes
192.168.157.176:18000.1     no              yes

??kill掉fllower節(jié)點：

nebcli): show beacon
node                        is_leader       is_online
192.168.157.176:16000.1     no              no
192.168.157.176:17000.1     yes             yes
192.168.157.176:18000.1     no              no

??重啟被kill掉的兩個節(jié)點：

nebcli): show beacon
node                        is_leader       is_online
192.168.157.176:16000.1     no              yes
192.168.157.176:17000.1     yes             yes
192.168.157.176:18000.1     no              yes

??fllower節(jié)點在原leader節(jié)點不可用后成為leader節(jié)點，且只要不宕機則一直會是leader節(jié)點，即使原leader節(jié)點重新變?yōu)榭捎脿顟B(tài)也不會再次切換。

7. 結(jié)束

??開發(fā)Nebula框架目的是致力于提供一種基于C++快速構(gòu)建高性能的分布式服務(wù)。如果覺得本文對你有用，別忘了到Nebula的Github或碼云給個star，謝謝。