[發明專利]一種基于負載感知的數據流動態負載均衡策略分析方法

在審

• 申請號: 202110070393.3
• 申請日: 2021-01-19
• 公開（公告）號: CN112764926A
• 公開（公告）日: 2021-05-07
• 發明（設計）人: 錢建裕;賀曉鳳;陳海鋒;許華福
• 申請（專利權）人: 漢納森（廈門）數據股份有限公司
• 主分類號: G06F9/50
• 分類號: G06F9/50
• 代理公司: 廈門致群財富專利代理事務所(普通合伙) 35224
• 代理人: 劉兆慶

本發明公開了一種基于負載感知的數據流動態負載均衡策略分析方法，包括如下步驟：S1、獲取數據元組經過每個節點的延遲時間；S2、計算最大延遲和延遲方差，并與設定的閾值比較從而判定節點負載情況；S3、將數據元組映射為數據塊，并根據數據塊的大小形成小頂堆結構；S4、利用負載遷移算法進行負載遷移，直到均衡為止。本發明采用節點處理元組的延遲時間評估節點的性能，以克服單一性能評估指標存在的局限性；利用深度優先搜索的負載感知算法，用于檢測節點的計算延遲時間、獲取其后繼的負載信息，為路由決策提供支持；通過小頂堆結構管理數據塊，實現有狀態的流式計算的分塊負載遷移。

技術領域

本發明涉及負載均衡技術領域，特別涉及一種基于負載感知的數據流動態負載均衡策略分析方法。

背景技術

在分布式計算環境下，負載均衡策略的依據是計算節點的資源利用率，通過將資源利用率過高節點的計算負載遷移到資源利用率較低的節點中，從而實現節點間負載的均衡。

一個節點的可用資源包括CPU、內存、磁盤I/O、網絡傳輸等，而現有研究成果多將CPU或內存利用率等單一指標作為性能評估依據。事實上，節點中任何一種資源的匱乏都會成為節點響應能力的瓶頸，導致數據元組在內存中被滯留而計算延遲加長。因此，任何單一的性能評估指標在實際應用中都存在局限性。

發明內容

為解決上述問題，本發明提供了一種基于負載感知的數據流動態負載均衡策略分析方法。

本發明采用以下技術方案：

一種基于負載感知的數據流動態負載均衡策略分析方法，包括如下步驟：

S1、獲取數據元組經過每個節點的延遲時間；

S2、計算最大延遲和延遲方差，并與設定的閾值比較從而判定節點負載情況；

S3、將數據元組映射為數據塊，并根據數據塊的大小形成小頂堆結構；

S4、利用負載遷移算法進行負載遷移，直到均衡為止。

進一步地，步驟S1具體為：通過深度優先搜索算法遍歷整個節點拓撲，為每個節點的不同訪問狀態標記不同顏色，并記錄每個節點狀態改變的時間戳；所述時間戳包括發現時間和完成時間；所述延遲時間等于所述完成時間和所述發現時間的差。

進一步地，所述發現時間是節點收到數據元組的時間；所述完成時間是節點發出的數據元組完成所有計算并到達匯點的時間，即一條路徑的完成時間。

進一步地，所述設定的閾值為極大延遲θ和極大方差ε，設某一節點O_n的后繼節點集為S_n＝{O_n+1,O_n+2,…,O_n+m}，共包含m個節點，且每個節點的延遲時間分別為W_n＝{w(O_n,O_n+1),w(O_n,O_n+2),…,w(O_n,O_n+m)}，則后繼節點的平均延遲時間和最大延遲max_n分別為：

max_n＝MAX(w(O_n,O_n+1),w(O_n,O_n+2),…,w(O_n,O_n+m))；

其中，w(O_n,O_i)是節點O_i的延時時間，也是弧O_n→O_i的權值。

進一步地，所述延遲方差的計算為：