一種改進(jìn)加權(quán)最小連接算法及在CDN的負(fù)載均衡技術(shù)中的應(yīng)用分析

(山東科技大學(xué) 計算機(jī)科學(xué)與工程學(xué)院，山東 青島 266590)

內(nèi)容分發(fā)網(wǎng)絡(luò)[1]的內(nèi)容路由技術(shù)一般由負(fù)載均衡系統(tǒng)來實現(xiàn)，是內(nèi)容分發(fā)網(wǎng)絡(luò)關(guān)鍵技術(shù)之一[2]。負(fù)載均衡的目的是運用多評估機(jī)制選擇最佳節(jié)點并將用戶路由到節(jié)點內(nèi)合適的服務(wù)器上。內(nèi)容路由決定了就近服務(wù)的思想能否實現(xiàn)，決定了整個內(nèi)容分發(fā)網(wǎng)絡(luò)系統(tǒng)的運行效率和性能，因此負(fù)載均衡是整個內(nèi)容分發(fā)網(wǎng)絡(luò)的基礎(chǔ)[4]。常用的負(fù)載平衡算法有靜態(tài)和動態(tài)兩種。靜態(tài)負(fù)載中，代表算法是輪詢算法[5]和加權(quán)輪詢算法[6]。靜態(tài)負(fù)載平衡算法的優(yōu)點是簡單，缺點是由于不考慮服務(wù)器節(jié)點的性能和當(dāng)前負(fù)載狀態(tài)，長時間運行將導(dǎo)致負(fù)載不平衡。由于動態(tài)負(fù)載均衡算法[5]無需先驗知識進(jìn)行決策，可以根據(jù)實時服務(wù)器負(fù)載狀況，自適應(yīng)調(diào)整任務(wù)在各服務(wù)器中執(zhí)行順序，從而提高了系統(tǒng)整體性能，因此在系統(tǒng)中得到廣泛應(yīng)用。現(xiàn)有的動態(tài)負(fù)載均衡算法主要有一致性哈希法[7]、最小連接算法(least connection, LC)[8]和加權(quán)最小連接算法(weighted least connection, WLC)[9]等。其中最小連接算法能動態(tài)獲取服務(wù)器負(fù)載情況，但只關(guān)注連接數(shù)，沒有關(guān)注CPU和內(nèi)存使用率等問題，會出現(xiàn)連接數(shù)小但服務(wù)器資源消耗較高的情況[10-11]；文獻(xiàn)[12]提出一種異構(gòu)集群負(fù)載索引和負(fù)載均衡算法，但對服務(wù)器負(fù)載情況的衡量只以任務(wù)數(shù)量為參考；文獻(xiàn)[13]提出一種自適應(yīng)權(quán)值最小負(fù)載實現(xiàn)負(fù)載均衡的算法，但沒有考慮服務(wù)器所能承受的最大負(fù)載；文獻(xiàn)[14]提出一種基于可變因子α的加權(quán)最小鏈接算法，根據(jù)各服務(wù)器的負(fù)載情況，對α的值進(jìn)行調(diào)整并在一定程度上達(dá)到了負(fù)載均衡；文獻(xiàn)[15]提出一種將終端連接數(shù)作為影響因子和各服務(wù)器參數(shù)進(jìn)行綜合分析的算法，沒有考慮磁盤I/O且只應(yīng)用于特定的場景中。上述文獻(xiàn)對負(fù)載均衡算法都做了改進(jìn)，但都有其片面性。本研究對最小連接算法進(jìn)行改進(jìn)得到一種IWLC(improved weighted leastconnection)算法，提出了針對動態(tài)權(quán)值的關(guān)鍵參數(shù)新的計算方法。IWLC算法通過動態(tài)獲取服務(wù)器反饋性能指標(biāo)與負(fù)載指標(biāo)計算出當(dāng)前集群中最優(yōu)服務(wù)器進(jìn)行任務(wù)的調(diào)度分配，可更好達(dá)到負(fù)載均衡效果，更好地解決CDN系統(tǒng)中大規(guī)模用戶訪問請求下的負(fù)載均衡問題。

1 算法介紹

1.1 典型負(fù)載均衡算法

1.1.1 最小連接算法

最小連接算法思想是：假設(shè)系統(tǒng)內(nèi)各個服務(wù)器性能一致，當(dāng)有新的任務(wù)到來時，總是將該任務(wù)分配給連接數(shù)最少的服務(wù)器[4,7]，即對于現(xiàn)有服務(wù)器集群S={S1，S2，…，Sn}，每個服務(wù)器連接數(shù)為C(Si),1≤i

1.1.2 加權(quán)最小連接算法(IWLC)

加權(quán)最小連接算法算法[3]思想是在LC算法基礎(chǔ)上，考慮了不同服務(wù)器的性能差異，設(shè)置不同的權(quán)值來標(biāo)識服務(wù)器性能指標(biāo)，在任務(wù)調(diào)度時為權(quán)值較大的服務(wù)器分配較大比例的活動連接[8,10]。IWLC算法充分考量服務(wù)器性能指標(biāo)及服務(wù)器動態(tài)負(fù)載指標(biāo)，因此在負(fù)載均衡方面性能要優(yōu)于最小連接算法；然而，現(xiàn)有的IWLC算法對性能指標(biāo)的計算相對簡單化，而系統(tǒng)實際運行過程中性能指標(biāo)與負(fù)載指標(biāo)更加復(fù)雜，因此IWLC算法仍有優(yōu)化改進(jìn)的空間。

1.2 改進(jìn)加權(quán)最小連接算法(IWLC)

1.2.1 IWLC算法思路及流程

CDN應(yīng)用系統(tǒng)中，負(fù)載均衡服務(wù)器實時接收各服務(wù)器節(jié)點的負(fù)載情況及資源使用狀態(tài)，IWLC算法利用實時獲取的參數(shù)來計算各服務(wù)器節(jié)點的綜合性能指標(biāo)并以此作為任務(wù)調(diào)度的依據(jù)，選擇出最適合執(zhí)行任務(wù)的服務(wù)器，從而完成任務(wù)的動態(tài)調(diào)度。

IWLC算法流程如下：

1) 集群中各真實服務(wù)器節(jié)點周期性計算各自的CPU空閑率、內(nèi)存空閑率、磁盤I/O空閑負(fù)荷、負(fù)載連接數(shù)，并反饋給負(fù)載均衡調(diào)度器；

2) 負(fù)載均衡調(diào)度器根據(jù)各服務(wù)器節(jié)點反饋的信息，計算服務(wù)器的綜合性能指標(biāo)P(Si)、綜合負(fù)載指標(biāo)C(Si)以及綜合評價指標(biāo)參數(shù)F(Si)，并計算出各個結(jié)點的權(quán)值wi；

3) 負(fù)載均衡調(diào)度器根據(jù)計算出的權(quán)值修改原先的權(quán)重，將更新后的權(quán)重寫入IPVS內(nèi)核；

4) Linux內(nèi)核啟用LVS編譯安裝IPVS內(nèi)核，IWLC算法根據(jù)新的權(quán)值選擇最合適的服務(wù)器進(jìn)行任務(wù)分配。

1.2.2 IWLC算法中關(guān)鍵參數(shù)計算

1) 集群S由n臺服務(wù)器組成，S={S1,S2,…,Sn}；

(1)

(2)

(3)

(4)

(5)

(6)

其中w1、w2、w3、w4分別代表各服務(wù)器性能指標(biāo)因素的權(quán)重。考慮到CPU空閑率和內(nèi)存空閑率兩個指標(biāo)在描述服務(wù)器性能方面的重要性，因此對于4個權(quán)重的賦值分別是：w1=0.4、w2=0.4、w3=0.1、w4=0.1。若當(dāng)前的系數(shù)w1、w2、w3、w4不能很好反映應(yīng)用的負(fù)載，可以對系數(shù)進(jìn)行不斷的修改，直到找到一組貼近當(dāng)前應(yīng)用的系數(shù)。經(jīng)過多次試驗，判定系數(shù)w1=0.4、w2=0.4、w3=0.1、w4=0.1是最優(yōu)的。

4) 為了更加有效預(yù)測每臺服務(wù)器節(jié)點所能承受的負(fù)載能力，引入服務(wù)器的綜合評價指標(biāo)參數(shù)F(Si)，其計算方法如下：

(7)

F(Si)的變化規(guī)則為：若要使F(Si)取值最小，其對應(yīng)的服務(wù)器Si要么滿足服務(wù)器性能指標(biāo)P(Si)最大，要么滿足服務(wù)器負(fù)載指標(biāo)C(Si)最小，或者同時滿足這兩個條件，此時Si便是集群中最合理的執(zhí)行新任務(wù)的服務(wù)器。

5) 設(shè)服務(wù)器的Si權(quán)重為wi，則令wi=1/F(Si)。F(Si)取值越小，服務(wù)器Si的動態(tài)權(quán)重取值越大，負(fù)載指標(biāo)就越小，服務(wù)器Si的連接數(shù)就越小。

1.2.3 IWLC算法的代碼及分析

IWLC算法只做一次for循環(huán)，依次比較各服務(wù)器綜合指標(biāo)參數(shù)F(Si)，F(xiàn)(Si)取值大的被舍棄，繼續(xù)比較下一個，直到第n個服務(wù)器，選出F(Si)值最小的作為下一輪要執(zhí)行新任務(wù)的服務(wù)器，算法時間復(fù)雜度為O(n)，可見對參數(shù)的改進(jìn)并沒有造成更高的時間復(fù)雜度。

Algorithm:Improved Weighted Least ConnectionInput:CPU idle rate Ci,Memory idle rate Mi,I/O rate Di,Bandwidth Ni,Number of load connectionsLi Number of server n, Weight w1,w2,w3,w4Output:The most weighted serverSiInitialize an Array of n-dimensions arr with 0fori=1;i≤n;i++()do R(i)cpu=Ci/maxC1,C2,…,Cn() R(i)mem=Mi/maxM1,M2,…,Mn() R(i)disk=Di/maxD1,D2,…,Dn() R(i)net=Ni/maxN1,N2,…,Nn() R(i)con=LiL(i)max,CSi()=R(i)con PSi()=w1?R(i)cpu+w2?R(i)mem+w3?R(i)disk+w4?R(i)net FSi()=CSi()/PSi(),Wi=1/FSi() W=Wi arri[]=W Write the weightWi to the IPVS kernel and make install the IPVS kernelend doWmax=arri[]maxreturn the most weighted server Si

IWLC算法通過本研究提出的動態(tài)權(quán)值計算方法得到服務(wù)器綜合評價指標(biāo)值，將新任務(wù)分配到F(Si)值最小的服務(wù)器Si上執(zhí)行，此時Si是當(dāng)前集群中最適合承擔(dān)負(fù)載的服務(wù)器。

2 實驗與分析

2.1 實驗設(shè)計

實驗?zāi)MCDN應(yīng)用系統(tǒng)中邊緣服務(wù)器節(jié)點應(yīng)對客戶訪問請求的負(fù)載均衡效果，本研究利用實驗室現(xiàn)有設(shè)備，基于章文嵩博士[9]所提出的Linux虛擬服務(wù)器開源項目的集群體系結(jié)構(gòu)技術(shù)搭建了一套模擬CDN應(yīng)用系統(tǒng)邊緣服務(wù)器節(jié)點系統(tǒng)。

為驗證提出的IWLC算法在解決CDN應(yīng)用系統(tǒng)中集群負(fù)載均衡問題方面的有效性，同時對比本算法與加權(quán)最小連接算法[5]在服務(wù)器響應(yīng)時間與吞吐量兩個評價指標(biāo)上的實現(xiàn)效果，設(shè)計具體實驗如下：

1) 在負(fù)載均衡服務(wù)器上通過IPVSADM管理軟件部署本研究提出的IWLC算法，而IPVSADM自身已經(jīng)配置了常用負(fù)載均衡算法，如加權(quán)輪詢算法加權(quán)最小連接算法等；

2) 在測試客戶機(jī)器上安裝部署LoadRunner系統(tǒng)負(fù)載測試工具，用來記錄模擬用戶訪問請求后臺服務(wù)器內(nèi)容過程中系統(tǒng)平均響應(yīng)時間與吞吐量；

3) 分10組模擬用戶訪問過程，請求任務(wù)數(shù)以每組遞增100的方式從100到1 000進(jìn)行實驗，利用LoadRunner記錄系統(tǒng)平均響應(yīng)時間與吞吐量指標(biāo)，每組測三次，最終取平均值；

表1 10組平均響應(yīng)時間對比實驗結(jié)果表Tab.1 Experimental results of average response time

4)用MATLAB畫圖對比本研究所提IWLC算法與加權(quán)最小連接算法的系統(tǒng)平均響應(yīng)時間和系統(tǒng)吞吐量。

2.2 實驗結(jié)果分析

提出的IWLC算法與WLC算法的系統(tǒng)平均響應(yīng)時間對比實驗結(jié)果如表1和圖1所示。可以看出：當(dāng)任務(wù)請求數(shù)低于300時，IWLC算法對應(yīng)的系統(tǒng)平均響應(yīng)時間要長于WLC算法，原因在于IWLC算法需要實時獲取各服務(wù)器傳送過來的性能指標(biāo)及負(fù)載指標(biāo)以計算各服務(wù)器的綜合性能指標(biāo)，引起額外的資源消耗，在任務(wù)請求數(shù)量較低的情況下造成了系統(tǒng)響應(yīng)時間延長；但是隨著系統(tǒng)用戶訪問請求任務(wù)數(shù)的增加，由于IWLC算法能夠充分利用系統(tǒng)資源，有效調(diào)度用戶任務(wù)請求，IWLC算法優(yōu)于WLC算法。

2) IWLC算法與WLC算法的系統(tǒng)吞吐量對比實驗如圖 2所示。由圖可見：當(dāng)任務(wù)數(shù)小于500時，IWLC算法測試出的系統(tǒng)吞吐量小于加權(quán)最小連接算法；當(dāng)任務(wù)數(shù)為600～1 000時，IWLC算法測試出的系統(tǒng)吞吐量逐漸超過WLC算法測試出的系統(tǒng)吞吐量，大約提高了1 347 bytes/ms，隨著任務(wù)請求數(shù)的增多，IWLC算法對于合理使用各服務(wù)器更加有優(yōu)勢。

圖1 平均響應(yīng)時間實驗結(jié)果對比圖Fig. 1 Comparison of Experimental Results of Average Response Time

圖2 系統(tǒng)吞吐量實驗結(jié)果對比圖Fig. 2 Comparison of experimental results of throughput

綜上，IWLC算法有效提高了系統(tǒng)平均吞吐量，盡可能避免服務(wù)器過載，將任務(wù)分配到具有最佳性能的服務(wù)器，加強(qiáng)系統(tǒng)資源的有效利用。

3 結(jié)論

本研究從CDN應(yīng)用系統(tǒng)的本地負(fù)載均衡方面，針對邊緣服務(wù)器如何應(yīng)對大量用戶訪問請求而保障負(fù)載均衡的問題，基于加權(quán)最小連接算法，提出了一種改進(jìn)加權(quán)最小連接的CDN負(fù)載均衡算法。

相比于WLC算法，IWLC算法充分考慮了服務(wù)器自身資源使用情況以及負(fù)載情況等因素，通過動態(tài)實時收集各服務(wù)器節(jié)點的資源性能指標(biāo)及負(fù)載指標(biāo)，綜合計算出當(dāng)前的最優(yōu)節(jié)點，完成訪問請求任務(wù)的分配，保證最大限度地利用系統(tǒng)資源，并對用戶的訪問請求更快地做出響應(yīng)。但I(xiàn)WLC算法也存在不足，如任務(wù)請求數(shù)較少時，負(fù)載均衡調(diào)節(jié)器定時發(fā)送請求報文獲取并處理真實服務(wù)器的各種信息帶來的額外開銷會影響整個系統(tǒng)的測試與評估。本工作沒有考慮到當(dāng)CPU空閑率、內(nèi)存空閑率、磁盤I/O空閑負(fù)荷、網(wǎng)絡(luò)帶寬四個參數(shù)都不大于90%的服務(wù)器時的算法情況，比較理想化，需要進(jìn)一步研究和細(xì)化算法來解決上述情況下的問題。