集群選舉演算法實現

来源:https://www.cnblogs.com/bwar/archive/2019/01/23/10311894.html
-Advertisement-
Play Games

一個分散式服務集群管理通常需要一個協調服務，提供服務註冊、服務發現、配置管理、組服務等功能，而協調服務自身應是一個高可用的服務集群，ZooKeeper是廣泛應用且眾所周知的協調服務。協調服務自身的高可用需要選舉演算法來支撐，本文將講述選舉原理並以分散式服務集群NebulaBootstrap的協調服務N ...


一個分散式服務集群管理通常需要一個協調服務，提供服務註冊、服務發現、配置管理、組服務等功能，而協調服務自身應是一個高可用的服務集群，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，謝謝。

 
您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 小程式圖片懶載入較完美解決方案
    無需考慮數據結構，效果如圖 話不多說，先上代碼 1.wxml 2.wxss Action添加一個簡單的漸顯動畫 3.js 原理：通過onPageScroll() 方法返回的e.scrollTop值與手機視窗寬高進行計算，較完美的解決了等高或均高圖片序列的圖片懶載入。 關於圖片高度：圖片+容器寬高必須 ...
  • 就是要用Vim寫Vue
    Vim關於Vue的生態鏈還是很少，不過湊活湊活還是能用的。 縮進 縮進採用的是兩個空格，.vimrc配置： 語法高亮 重要的語法高亮，支持最好的應該是vim-vue。 使用Vundle下載： 這樣語法高亮基本上就實現了，不過會出現滑動過快高亮失效的情況，文檔中給出的原因是vue包含html、css、 ...
  • js學習之路1 初識js函數
    1. 簡單的函數： 2.1 帶參數的函數： 2.2 帶參數的函數： 3.1 帶返回值的函數 3.2 帶有參數和返回值的函數 嘗試把返回值用字元串拼接的方式組合了一下，還真成功了 結果： ...
  • Vue學習之路第二篇：插值表達式
    要開始寫Vue的功能了，是不是很激動呢！開始吧！ 1、首先建立一個html頁面，導入Vue js包 1 <script type="text/javascript" src="js/vue.min.js"></script> 2、架包導入之後，我們需要創建一個Vue對象，用來綁定元素節點，從而達到操 ...
  • ionic4 開發企業微信應用0
    作為一個後臺開發人員，幾年前參與過Ionic1開發過一微信公眾號的經歷，所以這次開發企業微信應用，就使用了ionic，正好ionic4 rc版本發佈，雖然不是正式版，作為本項目的項目經理，還是決定使用ionic4開發，因為項目組員也是我。簡單記錄一下本次開發的過程，很多命令不經常輸入，就忘記了。 0 ...
  • readonly與disabled的區別
    一. 範圍不同 readonly 只對 <input> 和 <textarea> 標簽有效 disabled 對所有表單元素都有效, 包括：<input>, <textarea>, <button>, <label>, <option>, <select>等 二. 程度不同 readonly 只是將 ...
  • 前端調用介面得到的數據跟postman跑出來的數據里數字部份不相等
    昨天碰到這樣一個場景，調用後端介面返回的數據發現所有數據都是正常的，只有一個商品ID的最後兩位是錯的，每一個商品都是，導致無法進行商品的上下架和刪除， 經過查資料發現： 瀏覽器解析數字的坑，一旦超出一定長度最後兩位會精度失準變為兩位隨機數，所以出現這種問題先列印出來 typeof（出錯的數字欄位）， ...
  • Spring Cloud和Dubbo整合開發筆記(1)
    一、需求背景： 二、Dubbo和Spring Cloud 的比較 首先Dubbo是一個分散式服務框架，以及SOA治理方案。它的功能主要包括：高性能NIO通訊及多協議集成，服務動態定址與路由，軟負載均衡與容錯，依賴分析與降級等,它是著名的阿裡服務治理的核心框架。Spring Cloud更加關心為開發人 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類