[發明專利]一種應用于服務器集群的動態負載均衡方法及系統

有效

• 申請號: 201910455915.4
• 申請日: 2019-05-29
• 公開（公告）號: CN110266769B
• 公開（公告）日: 2021-12-17
• 發明（設計）人: 孟利民;周磊;應頌翔;林夢嫚;蔣維
• 申請（專利權）人: 杭州夢視網絡科技有限公司
• 主分類號: H04L29/08
• 分類號: H04L29/08
• 代理公司: 杭州斯可睿專利事務所有限公司 33241
• 代理人: 王利強

1.一種應用于服務器集群的動態負載均衡方法，其特征在于：所述方法包括以下步驟：

A、假設服務器集群中有n臺服務器，由集合表示為S＝{S₁，S₂，S₃，…，S_n}，服務器每處理一個用戶請求，將記錄該請求的任務量r，處理開始時間t_start和處理結束時間t_end，并由下式得到服務器當前負載指標v：

同時服務器集群將負載指標反饋至管理服務器；

B1、管理服務器從請求隊列按順序取出與服務器數量相等的n個請求，表示為J＝{J₁，J₂，J₃，…，J_n}，由請求預估模塊得到對應請求的任務量為R＝{R₁，R₂，R₃，…，R_n}，以及期望完成時間為T＝{T₁，T₂，T₃，…，T_n }；

B2、計算模塊以服務器集合S和請求集合J作為二部圖的頂點集；

B3、對所有服務器和請求進行遍歷：對于任意一個服務器S_i和一個請求J_m，可由下式預估服務器S_i執行任務J_m實際所需時間t_im：

若t_im≤T_m，則表示服務器S_i能夠及時處理請求J_m，即預計服務器S_i能在請求J_m的期望時間T_m內處理完該請求，并將二部圖圖中的頂點S_i和頂點J_m相連，得到一條邊e＝S_iJ_m；若t_im＞T_m，則表示以服務器S_i當前的負載狀態無法及時地完成該請求，那么二部圖中的頂點S_i和頂點J_m不相連，遍歷完成后即可得到服務器與請求的二部圖；

C、再根據深度優先的Edmonds的匈牙利算法求二部圖G的最大匹配：遍歷頂點集合，使頂點S_i依次與集合J中的頂點進行匹配，若頂點S_i與頂點J_m相連，且頂點J_m還未與集合S中的其他頂點匹配，則邊e＝S_iJ_m為一條匹配邊，并開始匹配集合S的下個頂點；若頂點S_i與頂點J_m相連，但頂點J_m已經與集合S中的其他頂點匹配，則尋找其增廣路，若找到增廣路，則將增廣路的匹配邊變成未匹配邊，而未匹配邊變成匹配邊，并開始匹配集合S的下個頂點；若找不到增廣路，則頂點S_i沒有匹配邊；

D、步驟C的遍歷完成后，即可得到二部圖的最大匹配M＝{S_iJ_m，…}，最后由用戶請求分配模塊按照M的匹配邊，將請求J_m發送至服務器S_i進行處理。

2.根據權利要求1所述的一種應用于服務器集群的動態負載均衡方法，其特征在于：初始化時，管理服務器向各個服務器發送一個測試請求，其任務量為r₀，得到請求完成時間為t₀，對于請求預估模塊，請求J_m的任務量R_m由下式得到：

其中c₀為測試請求的復雜度，C_m為請求J_m的復雜度，任務J_m的期望完成時間T_m由下式得到：

其中α的取值為經驗值，與實際服務器性能相關。