一種基于集群的動態(tài)負載均衡算法研究

吳俊鵬，劉曉東

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

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

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

1.1 負載均衡簡介

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

1.2 負載均衡常見算法簡介

常見的負載均衡算法包括隨機法、輪詢調(diào)度算法、比率算法、優(yōu)先權(quán)調(diào)度算法、最小連接數(shù)調(diào)度算法、最快響應(yīng)時間算法等[7]。

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

2 基于集群的一種動態(tài)負載均衡算法

2.1 算法思路

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

2.2 服務(wù)器各指標定義

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

2.3 服務(wù)器各性能性能指標權(quán)重更新

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

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

2.4 服務(wù)器加權(quán)值計算

Wi動態(tài)調(diào)整公式如式（11）所示。

其中，A的作用是放大服務(wù)器加權(quán)值減小的效果，根據(jù)服務(wù)器加權(quán)值初始值大小可進行相應(yīng)修改。

2.5 任務(wù)分配

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

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

圖1 服務(wù)器概率區(qū)間

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

2.6 算法流程

算法流程如圖2 所示。

圖2 算法流程

3 實驗結(jié)果及分析

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

圖3 3種算法的任務(wù)完成總時間對比

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

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

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

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

4 結(jié)論

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