胡逸飛,包梓群,包曉安

(浙江理工大學 信息學院,浙江 杭州 310018)

Nginx服務器集群的負載均衡技術領域已出現(xiàn)較多傳統(tǒng)靜態(tài)調度算法,例如,Nginx已自行支持的輪詢和加權輪詢算法、最小連接數(shù)算法、IP_Hash算法等[1]。這些算法能夠在簡單的工作場景下發(fā)揮一定作用,但其在復雜的現(xiàn)代網絡環(huán)境下已凸顯各種問題,例如,其無法根據(jù)具體網絡負載情況進行實時的負載策略再調整[2],點到點式的靜態(tài)算法在實際網絡環(huán)境中常會產生大量錯誤峰值點導致最佳結果的判定出錯,因此在靜態(tài)算法的基礎上出現(xiàn)了根據(jù)服務器反饋的實際負載信息。通過實時變動負載的分配策略進行負載均衡調度的動態(tài)負載均衡算法[3]在一定程度上滿足了根據(jù)負載情況實時進行算法調整的要求,但也存在一定程度的問題,例如低負載情況下的低負載均衡效率、對網絡資源的占用和局部峰值導致整體分配未達到最佳情況等[4]。本文所提算法解決了動靜態(tài)算法存在的問題,同時通過引入遺傳算法解決了局部最優(yōu)問題,具有一定的應用價值和研究意義。

1 負載均衡研究現(xiàn)狀

目前,負載均衡普遍可分為靜態(tài)算法和動態(tài)算法兩個版本,動態(tài)負載平衡技術更受研究人員青睞。文獻[5]對比了已有Web服務器集群的調度策略,包括隨機法、循環(huán)法、加權循環(huán)法、最短隊列算法以及擴散負載平衡法等,并提出了協(xié)作性自適應對稱發(fā)起擴散策略。通過隊列長度計算服務器的負載閾值并使得服務器通過廣播知曉彼此的狀態(tài),從而進行負載均衡策略重定位,但該策略存在高并發(fā)狀態(tài)下相應時間較長、系統(tǒng)吞吐量提升不明顯等問題。文獻[6]提出了基于約束測度的負載均衡技術,定時計算每個服務器的容量和負載。如果服務器的負載大于平衡閾值,則使用負載平衡算法分配任務,但該策略存在影響因子單一、提升效率不明顯等問題。文獻[7]通過在兩個負載均衡服務器上分別對Nginx及HAProxy進行改進加權輪詢算法的對比實驗,獲得了相關算法的性能評價參數(shù),但其在低負載情況下的負載均衡效果不佳。

我國科研人員在負載均衡技術研究方面亦取得了不錯的進展。文獻[8]通過研究Nginx負載均衡的加權輪詢算法原理和實現(xiàn)過程,提出了一種基于后端服務器實時負載信息和相應時間情況的動態(tài)反饋負載均衡算法,并通過實驗論證了該算法在抗并發(fā)能力上的優(yōu)勢。但該算法存在低負載下無提升甚至負提升等問題,有待進一步改進優(yōu)化。文獻[9]提出了一種自適應負載指標權值的負載均衡算法,該算法在對服務器節(jié)點分類的基礎上利用節(jié)點性能和綜合負載信息分配任務,從而避免負載傾斜問題。但該算法僅在相同I/O和相近CPU服務器環(huán)境下進行測試,不能有效地反應復雜集群下的負載情況。文獻[10]提出了一種基于動態(tài)反饋機制的負載均衡算法,通過自適應加權最小負載方法獲取更優(yōu)秀的輔助均衡效果,但其在低負載下分配效率較低。文獻[11]提出了一種基于預測模型和獨立訓練節(jié)點的負載均衡算法。采用機器學習算法、樸素貝葉斯方法、決策樹算法和支持向量機分別對實驗數(shù)據(jù)進行訓練從而獲得響應時間預測模型。然而,由于樸素貝葉斯算法的缺陷,可能出現(xiàn)局部最優(yōu)解的情況,從而影響算法整體的準確性,在高并發(fā)環(huán)境下表現(xiàn)不佳。

上述文獻中的算法在實驗環(huán)境的高負載情況大都有一定效率上的提升,但在低負載情況下,相比于傳統(tǒng)算法并沒有效率上的提升,甚至還會出現(xiàn)效率下降情況,同時亦存在由于局部負載計算最優(yōu)解導致的整體分配不均等問題。為了推動解決當前負載均衡算法所存在的上述問題,本文提出了一種基于改進遺傳算法的動靜態(tài)結合的負載均衡算法。

2 算法分析與設計

2.1 服務器節(jié)點性評價指標

對于服務器集群的負載均衡來說,準確評估服務器性能是問題的關鍵所在,不同的指標對于負載均衡調度選擇的判斷具有較大影響。本文結合文獻結論及實驗反饋,采用各服務器節(jié)點CPU(C)、內存(M)、磁盤I/O(I)和網絡帶寬(N)作為綜合性能評價指標。

當集群中存在n個節(jié)點時,對于每個節(jié)點Si∈{S1,S2,S3,…,Sn},n>1,服務器性能評價指標C(Si)∈{C(S1),C(S2),C(S3),…,C(Sn)},n>1,根據(jù)各項性能可設定評價指標為

(1)

其中,σi為各個服務器性能的權值參數(shù),和值為1。本文根據(jù)文獻[12]及實驗數(shù)據(jù)反饋,標定服務器性能的評價指標為

(2)

其中,每個服務器節(jié)點各性能評價權值為

(3)

其中,j∈{C,M,I,N},為各性能集合中的一項;Wi(Si)為服務器集群中節(jié)點Si的一項初始性能數(shù)值。

2.2 自適應動態(tài)負載均衡算法

本文通過改進概率擇優(yōu)算法[13]提出了一種適用于高負載狀態(tài)下的新的自適應動態(tài)負載均衡算法,其算法流程描述如下:對不同的業(yè)務服務器集群進行初始化。根據(jù)客戶端不同的請求類型或請求處理需求將服務器集群進行分組,對于一些泛用節(jié)點或無法根據(jù)請求區(qū)分的服務器節(jié)點則先根據(jù)式(2)計算器初始性能評價指標,并對各服務器節(jié)點初始性能評價指標進行排序后再根據(jù)節(jié)點數(shù)量盡可能地進行均勻分組。例如對于擁有N個服務器節(jié)點的服務器集群,在先根據(jù)請求類型將其中的M個節(jié)點(M

對于將請求分配至服務器組中某個節(jié)點的分配算法,需根據(jù)自適應動態(tài)負載均衡算法的特點,基于各節(jié)點的實時負載情況進行分配算法邏輯更新。本文采用服務器節(jié)點負載信息收集模塊來收集各節(jié)點的實時負載信息,但其為一種需要消耗網絡資源及傳輸時間的收集方法。當后端服務器集群數(shù)量較大且某些服務器節(jié)點在時間段T內的負載信息情況未發(fā)生明顯變化時,為了節(jié)省集群網絡資源,本文根據(jù)負載評價指標變化率ΔD來判斷某節(jié)點Si在t1～t2時間段內的負載信息是否上傳,其計算式如式(4)所示。

(4)

其中,Di為根據(jù)式(2)計算的節(jié)點Si在對應時間點的實時負載性能評價指標。本文根據(jù)服務器集群的實際運行環(huán)境對其設定一個預設上報閾值Δd,當服務器本次計算的負載變化率ΔD小于該閾值時,說明該時間段內該節(jié)點的負載信息變化過小,本次負載信息將不會上報,只在本節(jié)點負載收集模塊中更新本次收集數(shù)據(jù),以用于下一次的本地負載變化率計算。而負載均衡服務器在時間段T內未收到對應節(jié)點的負載信息上報,則沿用之前的負載信息,以此來節(jié)省節(jié)點負載信息的頻繁上報所導致的網絡資源消耗。

在收集到對應服務器組的各節(jié)點的實時負載信息后,本文根據(jù)節(jié)點的性能使用率L進行概率擇優(yōu)算法的動態(tài)分配概率調節(jié),計算式如式(5)所示。

(5)

其中,Wi代表該節(jié)點某項性能的使用率,WC、WM、WI以及WN分別代表工作狀態(tài)下的CPU使用率、內存利用率、磁盤I/O使用率和網絡帶寬使用率。性能使用率L準確反映了節(jié)點在每一時刻的負載情況,但存在使用率L與節(jié)點處理能力相反的問題,即使用率越高,當前節(jié)點處理能力越低。因此,本文引入一個變量λ來反映當前節(jié)點的負載情況,計算式如式(6)所示。

(6)

其中,λ(Si)代表當前節(jié)點使用率與所有節(jié)點使用率平均值的比值。當λ(Si)>1時,代表當前節(jié)點的使用率已超過平均值,需要適當減小該節(jié)點的分配概率,提高那些未達到平均使用率的節(jié)點分配概率,以達到更好的負載均衡效果。而基于服務器節(jié)點性能評價指標的概率擇優(yōu)算法,對于在服務器組中某節(jié)點Si的分配概率Pi的計算式如式(7)所示。

(7)

為了綜合考慮服務器節(jié)點的評價指標及實時性能的使用率,本文將概率擇優(yōu)算法改進為自適應的動態(tài)加權輪詢算法,將服務器組中的各節(jié)點分配概率改進為基于擇優(yōu)分配概率的分配權重。如式(8)所示,Q(Si)為對應服務器節(jié)點Si的分配權重。

(8)

其中,B為使得BP>1成立的權值常數(shù)。當負載變量λ(Si)>1時,表示當前節(jié)點的性能負載較重,超出了集群整體的平均負載情況,需通過實時減小其分配權重來降低新的客戶端請求分配給該節(jié)點的概率;當λ(Si)<1時則相反。這種在高負載情況下的負載均衡算法結合了當前節(jié)點的性能評價指標、實時性能使用率和分組概率擇優(yōu)的優(yōu)勢,使得其負載分配更加合理。

2.3 基于改進遺傳算法的閾值計算

本文經過研究文獻[14]及進行對比實驗后得出結論,對于Nginx作為負載均衡服務器的后端服務器集群而言,在低負載狀態(tài)下靜態(tài)負載均衡算法因其簡單的分配邏輯,對網絡資源消耗較少,因而具有良好的分配效果;而在高負載狀態(tài)下,動態(tài)負載均衡算法的優(yōu)勢則逐漸顯著。找到由靜態(tài)算法優(yōu)勢區(qū)間轉為動態(tài)算法優(yōu)勢區(qū)間的負載值即并發(fā)請求數(shù)量的閾值,是更好地進行Nginx負載均衡算法研究的關鍵所在。本文在對標準遺傳算法流程[15-16]進行研究分析后提出了一種改進的自適應遺傳算法,并將其用于動靜態(tài)算法優(yōu)勢區(qū)間閾值,其流程和計算方式如下所示。

首先與標準遺傳算法相近,進行編碼及產生初始種群,并通過適應度函數(shù)計算各染色體個體的適應度函數(shù)值,計算出平均適應度值Favg及最大適應度值Fmax。通過這兩種適應度值計算本文算法的關鍵閾值即操作變換閾值,作為改變變異算子操作和交叉算子操作流程順序的計算閾值。計算結束后優(yōu)先判斷算法整體是否滿足終止條件,若不滿足算法的終止條件,則進一步對算法設置的操作變換閾值進行判斷,即判斷sin(Favg/Fmin×π/2)≥1/2是否成立。當該條件滿足時,說明此時種群的平均適應度值與最大適應度值接近,染色體個體間差異較小,則先以一定概率PB進行變異算子操作,再以概率PJ進行交叉算子操作,最后進行選擇算子操作,可減小上述問題中變異操作所帶來的破壞種群優(yōu)異性的問題。當不滿足該閾值條件時,則先以一定概率進行交叉算子操作,再進行變異算子操作,最后進行選擇算子操作,可最大程度緩解算法進行無區(qū)分度迭代的問題,以加快收斂速度。其中,PJ和PB的計算式為如式(9)和式(10)所示。

(9)

(10)

當Favg/Fmin為較小值時,表明當前種群的染色體的適應度平均值與最大適應度值差值較大,種群適應度值分布較為分散,此時PJ的值相對增大,即提高了交叉算子操作的概率。以更大的概率對具有較大差異基因位的染色體個體進行交叉操作,進化出新的下一代優(yōu)質個體的概率更大。與之相對應地,減小PB的值,即降低了變異算子操作的概率,使得優(yōu)秀的個體更容易被保留,并同時加快了收斂的速度。當Favg/Fmin為較大值時,表明當前種群適應值的差異較小,較為集中,交叉算子操作已難以得到新的優(yōu)質染色體,因此降低了交叉算子操作的概率,同時也對應地增加了變異算子操作的概率,使算法跳出局部最優(yōu)解具有更大的可能性,以達到獲得全局最優(yōu)解的目的。

在遺傳算法流程中,交叉算子操作和變異算子操作大都具有隨機性和無方向性的特點,而選擇算子操作作為人為可控的操作,通過選擇合適的算子可使算法按照期望方向進行演化,因此具有一定重要性。本文基于適應度值非負的特點及對收斂性需求的考慮,選擇了一種基于三角函數(shù)的自適應的選擇算子操作概率的計算方法。如式(11)和(12)所示,該選擇算子概率既滿足了適應度值非負的要求,又避免了冗余參數(shù)的設置,在收斂性上也具有較好的效果。

(11)

(12)

對于某個染色體個體的選擇概率Pi,其值由個體適應度函數(shù)值Fi、種群的最大適應度值Fmax和最小適應度值Fmin決定。當種群整體的適應度差異極值較高時,表明當前種群的適應度整體差異過大,則選擇降低單獨某個染色體個體的概率,整體選擇分布更加均勻,能夠提高選擇的算子基因位的范圍。同時選擇某染色體個體的概率與其適應度值和最小適應度值的差值成正比,則選擇適應度優(yōu)秀的染色體個體,使得種群能夠較快地向優(yōu)秀進化方向演化。而通過三角函數(shù)這種非線性變化的方式自適應地調整選擇算子的概率,使得變化的速率按照差異期望進行變化,在保持種群多樣性方面具有良好的效果,使算法能以較快的收斂速度更大概率地獲取全局最優(yōu)解。

根據(jù)負載均衡算法及改進遺傳算法確定適應度函數(shù)。本文采用章節(jié)3.1中的服務器節(jié)點性能評價指標作為適應度函數(shù)優(yōu)化的選擇標準,使用章節(jié)2.2中的自適應動態(tài)負載均衡計算方法作為對區(qū)間閾值的計算方法之一,并根據(jù)文獻[17]引入基于最小熵增原理的適應度函數(shù)計算方法,最終確定本文算法的適應度函數(shù)如式(13)所示。

(13)

其中,Di為節(jié)點Si的節(jié)點性能評價指標;D0為服務器集群的初始硬件性能評價指標;k為熱力學常量;Q(Si)為自適應動態(tài)負載均衡算法中節(jié)點Si的分配權值。

本文采用基本的適應度函數(shù)構造方法,將目標優(yōu)化函數(shù)作為適應度函數(shù),通過尋找該目標優(yōu)化函數(shù)的零值解,在搜索空間內找到對應服務器集群的動靜態(tài)算法區(qū)間劃分的閾值。

本文通過改進的遺傳算法對基于服務器性能指標的適應度函數(shù)值進行研究計算及各種遺傳操作,不斷地使種群朝全局最優(yōu)解的方向演化,最終找到滿足要求的全局最優(yōu)解,即將所進行計算的服務器集群的靜態(tài)負載均衡算法優(yōu)勢區(qū)轉變?yōu)閯討B(tài)負載均衡算法優(yōu)勢區(qū)的閾值。

2.4 動靜態(tài)結合的負載均衡算法

以上述研究進度及改進算法為鋪墊,本文綜合了全部研究成果,提出了一種基于改進遺傳算法的Nginx動靜態(tài)結合的負載均衡算法。其核心思想為在計算出動靜態(tài)算法劃分區(qū)間的閾值之后在負載均衡服務器上設置負載監(jiān)控模塊。當監(jiān)控到當前服務器集群負載在閾值以內時,采用基于節(jié)點性能指標的靜態(tài)加權輪詢算法作為負載均衡策略,而當集群負載超過閾值后,將負載均衡策略動態(tài)調整為章節(jié)2.2中所提出的改進自概率擇優(yōu)算法的自適應動態(tài)負載均衡算法,并開始啟用安裝在各服務器節(jié)點上的負載信息收集模塊。通過收集的實時節(jié)點負載信息動態(tài)調整算法中各節(jié)點分配的權值,以此獲得更優(yōu)秀的負載均衡效果。算法的整體流程如圖1所示。

圖1 算法整體流程 Figure 1. Overall flow of the proposed algorithm

3 算法分析與設計

3.1 實驗環(huán)境

本文實驗環(huán)境由虛擬機搭建的9臺服務器組成。其中,1臺服務器作為測試客戶端,場景為某智慧宿管項目,1臺作為反向代理服務器,剩下的7臺作為后端服務器集群,分為3種不同請求的服務器集群。虛擬機操作系統(tǒng)均為CentOS7,其他參數(shù)如表1所示。

表1 實驗環(huán)境參數(shù)Table 1. Experimental environment parameters

本文在實驗過工程中設置了各后端服務器節(jié)點每隔3 s上傳一次節(jié)點性能使用率情況,并利用Siege工具模擬多用戶并發(fā)訪問及數(shù)據(jù)實時收集。根據(jù)文獻及實驗反饋結果,本文選取服務器平均響應時間和實際并發(fā)連接數(shù)作為算法評價的性能指標。

3.2 實驗結果與分析

由于本文算法是基于結合靜態(tài)負載均衡算法和動態(tài)負載均衡算法的優(yōu)勢所提出的,因此本文選取了靜態(tài)加權輪詢算法和動態(tài)的概率擇優(yōu)算法作為對比實驗的參考算法。為驗證本文算法具有更優(yōu)秀的負載均衡效果,選取了文獻[18]的動態(tài)負載均衡算法(dnfs_conn)進行對比。通過將包含本文算法和上述算法的4種算法分別使用Nginx的第三方模塊寫入作為其負載均衡策略算法均,在實驗環(huán)境中通過不斷提高并發(fā)請求數(shù)量,每次運行30 min,獲得對應的平均響應時間及實際并發(fā)連接數(shù),并生成對比結果,如圖2和圖3所示。

圖2 平均響應時間比較Figure 2. Average response time comparison

圖3 實際并發(fā)連接數(shù)比較Figure 3. Comparison of the actual number of concurrent connections

由圖2和圖3可以看出,相比于Nginx自帶的加權輪詢算法、概率擇優(yōu)算法和dnfs_conn算法,本文提出的基于改進遺傳算法的動靜態(tài)負載均衡算法隨著并發(fā)數(shù)量的增加(即服務器集群整體負載增大),對于請求的平均響應時間相對較短的優(yōu)勢越來越大,且在高并發(fā)情況下實際的并發(fā)連接數(shù)量優(yōu)勢更加明顯。相比于dnfs_conn算法,本文算法在數(shù)值上具有15%左右的提升。這反映出在高并發(fā)環(huán)境下,本文算法相比于傳統(tǒng)算法在負載均衡方面有著一定優(yōu)勢,能夠更好地分配請求和服務器資源,在低負載狀況下保留靜態(tài)算法優(yōu)勢的同時最大化利用服務器集群的性能,具有更加優(yōu)秀的負載均衡效果。

上述實驗結果證明,本文提出的基于改進遺傳算法的Nginx動靜態(tài)負載均衡算法既保留了靜態(tài)算法在低負載環(huán)境下平均響應時間較低的優(yōu)勢,又在高負載環(huán)境下具有相對更優(yōu)秀的負載均衡效果,充分利用了服務器各節(jié)點的性能和資源,使得整個服務器集群的響應速度和承載能力都得到了進一步優(yōu)化。在本文的模擬服務器集群環(huán)境下,本文算法相比于靜態(tài)加權輪詢算法、概率擇優(yōu)算法和dnfs_conn算法具有更優(yōu)秀的負載均衡效果。

4 結束語

為了更好地在各種高并發(fā)情況下實現(xiàn)分布式服務器集群的負載均衡,本文基于綜合CPU性能、內存性能、磁盤I/O和網絡帶寬等服務器性能的節(jié)點負載性能指標,結合靜態(tài)負載均衡算法及動態(tài)負載均衡算法優(yōu)點,并通過改進遺傳算法解決閾值計算問題,提出了一種基于改進遺傳算法的動靜態(tài)負載均衡算法。為驗證本文算法的正確性和有效性,通過Siege工具設計了網絡集群的模擬實驗,對加權輪詢算法、概率擇優(yōu)算法、dnfs_conn算法和本文算法進行了對比實驗,實驗結果證明了本文算法在性能上的優(yōu)勢,對于推動Nginx負載均衡算法的研究具有一定意義。