一種基于集群的動態負載均衡算法研究

吳俊鵬，劉曉東

（1.武漢郵電科學研究院，湖北武漢 430070；2.武漢虹旭信息技術有限責任公司，湖北武漢 430070）

服務器集群可以通過負載均衡算法將任務分配到集群的各服務器中，從而獲得很高的計算速度[1]。傳統的負載均衡算法中通常將服務器各項性能指標權重與服務器加權值設為定值[2-3]，然而在不同時刻各性能指標對服務器性能的影響力度都在變化，導致對服務器當前狀態造成誤判。為了解決上述問題，需合理利用負載資源，文中提出了一種按周期動態更新服務器各項性能指標權重與服務器加權值的算法，經實驗驗證，該算法可以更好地實現服務器集群的負載均衡。

1 負載均衡及其常見算法介紹

1.1 負載均衡簡介

負載均衡就是將工作負載分配到多個服務器上進行處理，從而避免部分服務器壓力過大，其在高并發與高可用的網絡基礎架構中扮演著重要的角色[4-6]。通過使用負載均衡可以提高集群處理任務的能力。

1.2 負載均衡常見算法簡介

常見的負載均衡算法包括隨機法、輪詢調度算法、比率算法、優先權調度算法、最小連接數調度算法、最快響應時間算法等[7]。

隨機算法會把任務隨機分配給一臺服務器，這是最簡單的一種負載均衡算法[8]；輪詢調度算法指的是將任務按照順序依次循環發往第一個服務器到最后一個服務器，是一種較為簡單的負載均衡算法；比率算法指的是根椐固定比例給服務器分配任務，這個比例由給每個服務器分配的加權值決定[9]，服務器的加權值可以人為分配；優先權調度算法會根據各服務器權重分配任務，服務器分配到的任務數的多少跟自身權重的大小成正比，服務器權重可以根據服務器性能來制定并修改；最小連接數調度算法會將任務發送到已有連接數最小的服務器上[10]；最快響應時間算法會將任務發送到響應時間最短的服務器上[11]。

2 基于集群的一種動態負載均衡算法

2.1 算法思路

一個服務器集群由多臺服務器組成，控制中心要通過負載均衡算法來合理分配任務以實現集群的負載均衡，好的負載均衡算法能夠極大地提升服務器集群的工作效率。文中算法會定期更新服務器各項性能指標權重，并計算出剩余負載率，然后，將剩余負載率與所設閾值進行對比從而修正服務器的加權值，控制中心根據各服務器加權值的大小分配任務[12-14]。

2.2 服務器各指標定義

首先，應該明確如何給一個服務器進行狀態評估[15-16]，文中從CPU 頻率、磁盤I/O 速率、內存大小、網絡帶寬4 個性能指標來綜合評價服務器狀態，CPU頻率決定計算機的運行速度，磁盤I/O 速率反應每秒輸入輸出量，內存大小反應服務器緩存性能，網絡帶寬反應服務器能容納數據量的大小。假設一個服務器集群an由n臺服務器組成，an={ }a1,a2,…,an，第i臺服務器的固有負載能力為：

2.3 服務器各性能性能指標權重更新

在以往的負載均衡算法中服務器各項性能指標權重都是固定的，這樣可能會出現服務器單項性能指標已處于較大壓力的狀態，但其余性能指標仍是正常狀態的情況，若用以往的算法對處于該狀況的服務器進行判斷，則該服務器可能仍處于正常狀態，但其實該服務器已處于過載狀態。為了解決這個問題應定期升高或降低服務器各項性能指標權重[17]，這樣有助于對服務器當前狀態進行判斷。文中引入了一個更新權重的標準，該標準可以通過比較單個服務器各性能指標的當前占用率和整個服務器集群中各性能指標的當前占用率的情況，來調整單個服務器各性能指標所占權重。首先計算當前集群中服務器各性能指標占用率均值：

根據服務器各項性能指標的新權值可以更新剩余負載率，在固定周期更新一次各指標權值。

2.4 服務器加權值計算

Wi動態調整公式如式（11）所示。

其中，A的作用是放大服務器加權值減小的效果，根據服務器加權值初始值大小可進行相應修改。

2.5 任務分配

當有任務到來時，控制中心會根據各服務器加權值的大小來分配任務，控制中心將一個任務分配到第i臺服務器的概率為：

根據控制中心將每個任務分配到各臺服務器的概率大小可以得知服務器概率區間如圖1 所示。

圖1 服務器概率區間

當任務到來時，控制中心會生成一個0 到1 之間的數字，并通過該數字在服務器概率區間的位置決定該任務的分配。

2.6 算法流程

算法流程如圖2 所示。

圖2 算法流程

3 實驗結果及分析

1）在不同任務數的情況下，對比率法、最小連接數法以及文中算法的任務完成總時間進行測量，結果如圖3 所示。

圖3 3種算法的任務完成總時間對比

通過觀察對比可以看出，在任務數較少的時候3 種算法的任務完成總時間相差較小，隨著任務數的增多，比率法的劣勢就逐漸體現出來了。文中算法與最小連接數法在任務數小于800 時任務完成總時間差距不大，且文中算法略優于最小連接數法，當任務數大于800 后，二者任務完成總時間的差距開始逐漸加大。

2）在不同任務數的情況下對比率法、最小連接數法以及文中算法的吞吐率（任務數/秒）進行測量，結果如圖4 所示。

圖4 3種算法的吞吐率對比

通過觀察對比可以看出，比率法的吞吐率一直處于穩定增長狀態，且在任務數達到800 之后增長趨勢變緩。但與其他兩種算法的吞吐率相比，比率法的吞吐率始終小于其他兩種算法且差值較大；最小連接數法與文中算法的吞吐率一直在一個范圍內波動，但文中算法的吞吐率始終優于最小連接數法。

4 結論

文中算法通過增加動態更新服務器各項性能指標權重與服務器加權值，修改了傳統負載均衡算法，通過對比率法、最小連接數法與文中算法在任務完成總時間及吞吐率兩方面數據進行對比可以看出，文中算法更好地提升了集群負載程度，縮短了任務完成時間。