集群选举算法实现

一个分布式服务集群管理通常需要一个协调服务，提供服务注册、服务发现、配置管理、组服务等功能，而协调服务自身应是一个高可用的服务集群，zookeeper是广泛应用且众所周知的协调服务。协调服务自身的高可用需要选举算法来支撑，本文将讲述选举原理并以分布式服务集群nebulabootstrap的协调服务nebulabeacon为例详细说明协调服务的选举实现。

  为什么要选nebulabeacon来说明协调服务的选举实现？一方面是我没有读过zookeeper的代码，更重要的另一方面是nebulabeacon的选举实现只有两百多行代码，简单精炼，很容易讲清楚。基于高性能c++网络框架nebula实现的分布式服务集群nebulabootstrap是一种用c++快速构建高性能分布式服务的解决方案。

  为什么要实现自己的协调服务而不直接用zookeeper？想造个c++的*，整个集群都是c++服务，因为选了zookeeper而需要部署一套java环境，配置也跟其他服务不是一个体系，实在不是一个好的选择。spring cloud有eureka，nebulabootstrap有nebulabeacon，未来nebulabootstrap会支持zookeeper，不过暂无时间表，还是首推nebulabeacon。

1. 选举算法选择

  paxos算法 和 zookeeper zab协议 是两种较广为人知的选举算法。zab协议主要用于构建一个高可用的分布式数据主备系统，例如zookeeper，而paxos算法则是用于构建一个分布式的一致性状态机系统。也有很多应用程序采用自己设计的简单的选举算法，这类型简单的选举算法通常依赖计算机自身因素作为选举因子，比如ip地址、cpu核数、内存大小、自定义序列号等。

  paxos规定了四种角色（proposer，acceptor，learner，以及client）和两个阶段（promise和accept）。   zab服务具有四种状态：looking、following、leading、observing。   nebulabeacon是高可用分布式系统的协调服务，采用zap协议更为合适，不过zap协议还是稍显复杂了，nebulabeacon的选举算法实现基于节点的ip地址标识，选举速度快，实现十分简单。

2. 选举相关数据结构

  nebulabeacon的选举相关数据结构非常简单：

const uint32 sessiononlinenodes::mc_uileader = 0x80000000;   ///< uint32最高位为1表示leader
const uint32 sessiononlinenodes::mc_uialive  = 0x00000007;   ///< 最近三次心跳任意一次成功则认为在线
std::map<std::string, uint32> m_mapbeacon;                   ///< key为节点标识，值为在线心跳及是否为leader标识

  如上数据结构m_mapbeacon保存了beacon集群各beacon节点信息，以beacon节点的ip地址标识为key排序，每次遍历均从头开始，满足条件（1&&2 或者 1&&3）则标识为leader：1. 节点在线；2. 已经成为leader； 3. 整个列表中不存在在线的leader，而节点处于在线节点列表的首位。

3. beacon选举流程

  beacon选举基于节点ip地址标识，实现非常简单且高效。

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

  进程启动时首先检查beacon集群配置，若未配置其他beacon节点信息，则默认只有一个beacon节点，此时该节点在启动时自动成为leader节点。否则，向其他beacon节点发送一个心跳消息，等待定时器回调检查并选举出leader节点。选举流程如下图：

  检查是否在线就是通过检查两次定时器回调之间是否收到了其他beacon节点的心跳消息。对m_mapbeacon的遍历检查判断节点在线情况，对已离线的leader节点置为离线状态，若当前节点应成为leader节点则成为leader节点。

4. beacon节点间选举通信

  beacon节点间的选举通信与节点心跳合为一体，这样做的好处是当leader节点不可用时，fllower节点立刻可以成为leader节点，选举过程只需每个fllower节点遍历自己内存中各beacon节点的心跳信息即可，无须在发现leader不在线才发起选举，更快和更好地保障集群的高可用性。

  beacon节点心跳信息带上了leader节点作为协调服务产生的新数据，fllower节点在接收心跳的同时完成了数据同步，保障任意一个fllower成为leader时已获得集群所有需协调的信息并可随时切换为leader。除定时器触发的心跳带上协调服务产生的新数据之外，leader节点产生新数据的同时会立刻向fllower发送心跳。

5. beacon选举实现

  beacon心跳协议proto：

/**
 * @brief beacon节点间心跳
 */
message election
{
    int32 is_leader                  = 1;    ///< 是否主节点
    uint32 last_node_id              = 2;    ///< 上一个生成的节点id
    repeated uint32 added_node_id    = 3;    ///< 新增已使用的节点id
    repeated uint32 removed_node_id  = 4;    ///< 删除已废弃的节点id
}

  检查beacon配置，若只有一个beacon节点则自动成为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();
    }
}

  发送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节点切换leader

  通过nebula集群的命令行管理工具nebcli可以很方便的查看beacon节点状态，nebcli的使用说明见nebcli项目的readme。下面启动三个beacon节点，并反复kill掉beacon进程和重启，查看leader节点的切换情况。

  启动三个beacon节点：

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节点：

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节点：

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掉的两个节点：

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节点在原leader节点不可用后成为leader节点，且只要不宕机则一直会是leader节点，即使原leader节点重新变为可用状态也不会再次切换。

7. 结束

  开发nebula框架目的是致力于提供一种基于c++快速构建高性能的分布式服务。如果觉得本文对你有用，别忘了到nebula的github或码云给个star，谢谢。