集群选举算法实现

本文涉及的产品
服务治理 MSE Sentinel/OpenSergo,Agent数量 不受限
注册配置 MSE Nacos/ZooKeeper,118元/月
云原生网关 MSE Higress,422元/月
简介: 一个分布式服务集群管理通常需要一个协调服务,提供服务注册、服务发现、配置管理、组服务等功能,而协调服务自身应是一个高可用的服务集群,ZooKeeper是广泛应用且众所周知的协调服务。协调服务自身的高可用需要选举算法来支撑,本文将讲述选举原理并以分布式服务集群NebulaBootstrap的协调服务NebulaBeacon为例详细说明协调服务的选举实现。

一个分布式服务集群管理通常需要一个协调服务,提供服务注册、服务发现、配置管理、组服务等功能,而协调服务自身应是一个高可用的服务集群,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选举流程

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

4. Beacon节点间选举通信

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

Beacon间心跳

  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,谢谢。

相关实践学习
基于MSE实现微服务的全链路灰度
通过本场景的实验操作,您将了解并实现在线业务的微服务全链路灰度能力。
目录
相关文章
|
4月前
|
算法
Bully、Raft、Zab选举算法的差异比较
Bully算法、Raft算法、Zab的差与异。他们如何脱胎于Paxos而成?
|
4月前
|
算法
共识协议的技术变迁问题之Raft的选举算法进行如何解决
共识协议的技术变迁问题之Raft的选举算法进行如何解决
101 7
|
5月前
|
存储 NoSQL 算法
Redis集群,集群的概念 三种主流分片方式1.哈希求余 一致性哈希算法:方案三:哈希槽分区算法问题一Redis集群是最多有16384个分片吗问题二:为什么是16384个,集群扩容:1.新的主节点
Redis集群,集群的概念 三种主流分片方式1.哈希求余 一致性哈希算法:方案三:哈希槽分区算法问题一Redis集群是最多有16384个分片吗问题二:为什么是16384个,集群扩容:1.新的主节点
|
6月前
|
算法 Go 分布式数据库
构建高可用的分布式数据库集群:使用Go语言与Raft共识算法
随着数据量的爆炸式增长,单一数据库服务器已难以满足高可用性和可扩展性的需求。在本文中,我们将探讨如何使用Go语言结合Raft共识算法来构建一个高可用的分布式数据库集群。我们不仅会介绍Raft算法的基本原理,还会详细阐述如何利用Go语言的并发特性和网络编程能力来实现这一目标。此外,我们还将分析构建过程中可能遇到的挑战和解决方案,为读者提供一个完整的实践指南。
|
6月前
|
人工智能 算法 BI
【图论】【 割边】【C++算法】1192. 查找集群内的关键连接
【图论】【 割边】【C++算法】1192. 查找集群内的关键连接
|
存储 监控 NoSQL
深入探究Redis:内存模型、哨兵选举算法与脑裂解决方案
深入探究Redis:内存模型、哨兵选举算法与脑裂解决方案
717 1
|
存储 NoSQL 算法
【Redis】集群数据hash分片算法
【Redis】集群数据hash分片算法
185 0
|
负载均衡 算法 容灾
Spring Cloud Alibaba - 11 Ribbon 自定义负载均衡策略(同集群优先权重负载均衡算法)
Spring Cloud Alibaba - 11 Ribbon 自定义负载均衡策略(同集群优先权重负载均衡算法)
193 0
|
传感器 机器学习/深度学习 算法
【WSN】异构无线传感器网络的开发分布式节能集群算法(DDEEC)附matlab代码
【WSN】异构无线传感器网络的开发分布式节能集群算法(DDEEC)附matlab代码
|
负载均衡 算法 调度
负载均衡集群LVS调度算法实战(三)|学习笔记
快速学习负载均衡集群LVS调度算法实战
负载均衡集群LVS调度算法实战(三)|学习笔记