摘  要： 隨著互聯(lián)網(wǎng)的不斷發(fā)展、用戶數(shù)量的急劇增長,，互聯(lián)網(wǎng)中出現(xiàn)了網(wǎng)絡(luò)擁塞,、服務(wù)器負(fù)載過重、響應(yīng)時間過長等嚴(yán)重問題,，其中負(fù)載均衡算法是影響服務(wù)器集群整體性能的一個關(guān)鍵因素,。運(yùn)用統(tǒng)計學(xué)中的因子分析理論，提出了一種基于因子分析的負(fù)載均衡算法,。該算法利用因子分析法計算出綜合負(fù)載,，并用這個指標(biāo)幫助負(fù)載均衡器選擇合適的服務(wù)器，均勻地將用戶的請求進(jìn)行分發(fā),，從而達(dá)到整體上較好的負(fù)載均衡,。

　　關(guān)鍵詞： 內(nèi)容分發(fā)；因子分析,；負(fù)載均衡

0 引言

　　隨著網(wǎng)絡(luò)的高速發(fā)展和普及,，人們對網(wǎng)絡(luò)服務(wù)的依賴和需求也越來越來大。為了保持所提供網(wǎng)絡(luò)服務(wù)的高質(zhì)量,、高效率,，負(fù)載均衡系統(tǒng)是影響服務(wù)器集群性能的核心部分，而負(fù)載均衡算法是決定負(fù)載均衡模塊如何分發(fā)用戶請求的重要部分,，但已有負(fù)載均衡算法容易造成用戶請求分配不均,，有著一定的局限性[1]。

　　研究者們提出了一些新的評估各個服務(wù)器節(jié)點(diǎn)負(fù)載的方法,，以此來改進(jìn)負(fù)載均衡算法,。例如,，張慧芳[2]選擇靜態(tài)參數(shù)（如CPU主頻、內(nèi)存大小等）和動態(tài)參數(shù)來計算節(jié)點(diǎn)的綜合負(fù)載（如CPU利用率,、內(nèi)存利用率等）,；HWANG S T等人[3]提出了用硬件指標(biāo)、CPU利用率和在線連接數(shù)作為評估指標(biāo),。Duan Zhaolei等人[4]利用CPU利用率,、磁盤利用率、分頁錯誤數(shù),、請求數(shù),、請求響應(yīng)時間等指標(biāo)來計算服務(wù)器的實(shí)時負(fù)載；章文嵩[5],、陳偉[6]等人在研究集群系統(tǒng)的動態(tài)負(fù)載均衡算法方面利用輸入指標(biāo)、服務(wù)器節(jié)點(diǎn)指標(biāo)兩類負(fù)載信息來計算綜合負(fù)載,，其中綜合負(fù)載通過線性加權(quán)計算得出,，各指標(biāo)的權(quán)值按照其重要性大小進(jìn)行確定。

　　據(jù)以往的研究看來,，負(fù)載的計算往往是按照一定的加權(quán)比例進(jìn)行的,，比較經(jīng)驗(yàn)主義，且主觀性和隨意性比較大,，沒有一個較為科學(xué)的方法來確定加權(quán)的比例,，從而導(dǎo)致實(shí)時負(fù)載計算式反饋出來的不太不準(zhǔn)確。為了解決準(zhǔn)確評估實(shí)時負(fù)載的問題,，本文采用了統(tǒng)計學(xué)中的因子分析法來評估實(shí)時負(fù)載,，以求達(dá)到較準(zhǔn)確評估負(fù)載。

1 基于因子分析的動態(tài)負(fù)載均衡方法

　　1.1 算法設(shè)計思路

　　在已有負(fù)載均衡算法中,，有一些以實(shí)時負(fù)載情況作為依據(jù)的負(fù)載均衡算法,，已有的加權(quán)最小連接（WLC）算法能夠較有效地均衡服務(wù)器集群的負(fù)載、分發(fā)用戶請求,，然而目前的WLC算法僅僅是參考了實(shí)時連接數(shù)這一負(fù)載信息,，并沒有考慮到不同網(wǎng)絡(luò)應(yīng)用的連接對服務(wù)器負(fù)載的影響程度是不同的，如視頻連接對服務(wù)器的影響肯定比文本連接對服務(wù)器的影響大,。因此,，本文的思路是通過采集一些其他服務(wù)器的性能數(shù)據(jù)信息，改進(jìn)實(shí)時負(fù)載情況的計算方式,，并將這些新的負(fù)載度量信息與WLC算法結(jié)合,，以達(dá)到改進(jìn)算法、提高用戶請求調(diào)度效率的目的,。改進(jìn)的動態(tài)負(fù)載均衡算法的應(yīng)用模型如圖1所示,。

　　設(shè)有n臺緩存服務(wù)器組成的集群,，則可以定義服務(wù)器設(shè)備集合S={S1，S2,，…,，Sn}（n>1）。該算法的核心內(nèi)容為：服務(wù)器設(shè)備集群中的各個服務(wù)器節(jié)點(diǎn)在每間隔一個時間周期T就向負(fù)載均衡調(diào)度器反饋當(dāng)前服務(wù)器的服務(wù)器性能參數(shù),，調(diào)度器接收到這些負(fù)載度量信息后,，利用這些負(fù)載度量信息評估出實(shí)時負(fù)載情況，結(jié)合實(shí)時負(fù)載情況,，做出緩存服務(wù)器的選擇,，達(dá)到合理的負(fù)載均衡。因此,，本文要做的工作是：（1）選擇什么負(fù)載度量信息,；（2）用什么計算方法組織這些負(fù)載度量信息，得出一個綜合的負(fù)載情況指標(biāo),；（3）如何與WLC算法進(jìn)行結(jié)合,。

　　1.2 實(shí)時負(fù)載情況的量化

　　首要的工作是如何評價服務(wù)器的負(fù)載情況。采用數(shù)值量化的辦法無疑是較為合理的,，本文利用多元統(tǒng)計分析學(xué)中的因子分析法[7-8],，通過合理的推導(dǎo)和計算，獲得能夠反映實(shí)時負(fù)載情況的量化,，從而幫助現(xiàn)有負(fù)載均衡算法做出更準(zhǔn)確的任務(wù)分配,，達(dá)到改進(jìn)已有負(fù)載均衡算法的目的。

　　定義1 負(fù)載參數(shù)變量：某種可觀測的,、影響實(shí)時負(fù)載能力的變量,，Xi表示第i種影響負(fù)載能力的變量，這里用X1表示CPU利用率,，X2表示內(nèi)存利用率,，X3表示磁盤利用率，X4表示網(wǎng)絡(luò)帶寬使用率,。

　　定義2 實(shí)時負(fù)載指數(shù)：Load表示負(fù)載實(shí)時指數(shù),，有Load=g（X1，…,，X4）,，g表示Xi與Load的關(guān)系函數(shù)。

　　定義3 負(fù)載參數(shù)向量：由X1,，…,，X4構(gòu)成的4維可觀測向量，記為X,，其各維數(shù)據(jù)均為可以較準(zhǔn)確,、直接觀測出的數(shù)據(jù),。

　　僅僅通過Load=g（X1，…,，X4）無法得出各種負(fù)載參數(shù)變量與Load的合理關(guān)系,，于是開始因子分析法。首先,，建立正交因子分析模型：設(shè)X=（X1,，…，X4）T是可觀測的隨機(jī)向量,，即按照上面的定義引入了p種負(fù)載參數(shù)變量,，其協(xié)方差矩陣為：

　　其中，σij為Xi和Xj的協(xié)方差,。設(shè)F=（F1,，F(xiàn)2，F(xiàn)3）T為公共因子,，這些因子屬于不可直接觀測,、卻又可以影響每個負(fù)載參數(shù)變量的共同潛在因素，按照本文選取的參數(shù),，可以給F1、F2,、F3分別命名為計算速度因子,、網(wǎng)絡(luò)傳輸速度因子、I/O速度因子,；且E（F）=0,，D（F）=I3（即F的各分量方差為1，且互不相關(guān)）,。設(shè)ε=（ε1,，ε2，…,，ε4）T為特殊因子,，它與F互不相關(guān)卻又可以影響負(fù)載參數(shù)變量，那么每個負(fù)載參數(shù)變量都可以表示成公共因子的線性函數(shù)與特殊因子之和,，則：

　　該模型用矩陣表示為：

　　X=AF+ε（3）

　　通過以上過程,，得到了初步的數(shù)學(xué)模型，即描述了負(fù)載參數(shù)Xi與潛在因素F存在一定的關(guān)系,。然而模型中仍有未知的特殊因子ε和aij,，因此可利用觀測出的數(shù)據(jù)X對模型進(jìn)行求解，以得到Xi與Fm的關(guān)系,。

　　由于公共因子是不相關(guān)的,，且均有潛在影響,，則有：Load=f（F1，F(xiàn)2,，F(xiàn)3）,。然而這些公共因子F很難通過實(shí)際數(shù)據(jù)去測量，因此在因子分析法中,，首先考慮用X來代替F,，用可觀測量反映不可測量。接下來將公共因子轉(zhuǎn)換成負(fù)載參數(shù)的組合,，這個過程就是因子得分（factor scoring）,。潛在因素向量F=（F1，F(xiàn)2,，F(xiàn)3）T可以用最小二乘法估計為：

　　F≈[（ATA）-1AT]X=STX（4）

　　這樣就可以得到潛在因素向量F與最初的可觀測向量X的關(guān)系,，其中S=（βij）4×3為因子得分系數(shù)矩陣，而X就是前面各種負(fù)載因素變量組成的向量,，可以看出因子得分系數(shù)矩陣的計算主要與因子載荷矩陣A有關(guān),。再把F替換為X，得到：

　　根據(jù)因子分析方法中的概念,，將潛在因素使用線性相加的辦法可以進(jìn)一步得出一些關(guān)于負(fù)載指數(shù)的具體計算式：

　　其中,，wi為公共因子Fi的權(quán)重。由因子分析法可知,，wi的值為使用方差貢獻(xiàn)率作為權(quán)重值,，結(jié)合式（5）和（6），得到：

　　其中,，βi=（β1i,，…，β4i）T是前面提到的因子得分系數(shù)矩陣的列向量,，X為負(fù)載因素向量,。

　　由于在因子分析法計算出的綜合得分有一些會出現(xiàn)負(fù)值，因此做一定修正,，即：

　　經(jīng)過以上分析過程,，從原來常用簡單的線性疊加式，通過使用因子分析法的方式,，得到了實(shí)時負(fù)載指數(shù)的計算公式,，為后文的負(fù)載均衡算法的改進(jìn)和實(shí)驗(yàn)分析提供了依據(jù)。

　　1.3 DLBFA算法的設(shè)計

　　本文的思路是在已有算法的基礎(chǔ)上進(jìn)行改進(jìn),，其中加權(quán)最小連接（Weighted Least-Connection,，WLC）是目前已有算法連接請求調(diào)度情況較好的一種算法，它選擇服務(wù)器設(shè)備節(jié)點(diǎn)的算法過程主要以考慮服務(wù)器節(jié)點(diǎn)的連接數(shù)為主,，但是其缺陷就是算法中每個服務(wù)器節(jié)點(diǎn)的分配權(quán)重為固定值,，并不能實(shí)時地按照服務(wù)的性能調(diào)整服務(wù)器節(jié)點(diǎn)的權(quán)重,。因此引入前面得出的服務(wù)器實(shí)時負(fù)載指數(shù)，提出基于因子分析的動態(tài)負(fù)載均衡（Dynamic Load-balance Based on Factor Analysis,，DLBFA）算法,，動態(tài)地修正服務(wù)器的權(quán)值，這樣負(fù)載均衡系統(tǒng)可以根據(jù)動態(tài)權(quán)重做出服務(wù)器的選擇,。

　　從前文可知,，負(fù)載情況的計算需要采集的一些服務(wù)器性能信息是以較主流的CPU、內(nèi)存,、磁盤和網(wǎng)絡(luò)4個方面來源為主的,。其中負(fù)載參數(shù)向量X記為：X＝（U1，U2,，U3,，U4）T，其中向量各維分別為CPU利用率,、內(nèi)存利用率,、磁盤利用率和網(wǎng)絡(luò)帶寬使用率。那么可以結(jié)合式（8）,，經(jīng)過因子分析的過程算出Li,。再將Li與WLC算法結(jié)合，形成改進(jìn)算法,?？梢约s定如下：設(shè)服務(wù)器集合S={S1，S2,，…，Sn}（n>1）,，W（Si）表示服務(wù)器的權(quán)值,，C（Si）表示服務(wù)器Si當(dāng)前連接數(shù)，α（Si）表示服務(wù)器Si對應(yīng)的可變因子,，則選擇服務(wù)器的策略為：

　　式（9）達(dá)到了W（Si）的動態(tài)變化的目的,，其中α（Si）的確定與Li的值有關(guān)，這樣就可以做到Li與WLC算法的結(jié)合,。α（Si）確定的策略以各個服務(wù)器的負(fù)載平均值L為基準(zhǔn),，即：

　　其中，當(dāng)?shù)趇臺服務(wù)器的負(fù)載指數(shù)大于平均負(fù)載指數(shù)時,，可認(rèn)為負(fù)載過重,，此時將α（Si）的值調(diào)小，達(dá)到了降低權(quán)值的目的,；如果第i臺服務(wù)器的負(fù)載指數(shù)小于平均負(fù)載指數(shù),，則認(rèn)為負(fù)載較輕,，此時α（Si）的值為1不變，保持權(quán)值也不變,。這里設(shè)置的ε,、θ是為了防止α（Si）調(diào)整過于頻繁影響任務(wù)調(diào)度而設(shè)置的閾值，保證了服務(wù)器的負(fù)載情況穩(wěn)定在一定范圍之內(nèi),。算法的偽代碼描述如下：

　　算法1 基于因子分析的動態(tài)負(fù)載均衡算法

　　輸入：用戶請求集VR,，服務(wù)器節(jié)點(diǎn)集VS，服務(wù)器權(quán)重集合W,，可變因子集合α,，服務(wù)器當(dāng)前連接數(shù)集合C。

　　輸出：請求映射到服務(wù)器的集合,。

　　begin

　　m←REQUEST_NUM//獲得請求數(shù)

　　n←SERVER_NUM//獲得服務(wù)器數(shù)

　　minWeight←MAX_WEIGTH//最小權(quán)重初值

　　C←getConnectionNum（）//獲得連接數(shù)

　　W←InitalWeight（）//初始化權(quán)重集合

　　for i←1 to n do

　　Li←getServerLoad（i）

　　//根據(jù)式（8）獲得每個服務(wù)器節(jié)點(diǎn)的負(fù)載值

　　if（Li>=ε）//更新α（Si）

　　α（Si）=Li*α（Si）

　　α（Si）=1

　　else

　　α（Si） = α（Si）

　　W（Si） ← C（Si）/（W（Si）α（Si）） //更新服務(wù)器權(quán)重

　　for i←1 to m do

　　for i←1 to n do

　　if（W（Si）< minWeight）

　　SERVER←Si  //選擇負(fù)載較小的服務(wù)器

　　G←{VR→SERVER}

　　//請求到服務(wù)器的映射的加入結(jié)果集合

　　return G   //返回映射結(jié)果集

　　end

2 實(shí)驗(yàn)及分析

　　2.1 實(shí)驗(yàn)方案與環(huán)境

　　為了驗(yàn)證改進(jìn)算法的基本性能,，本實(shí)驗(yàn)采用網(wǎng)絡(luò)仿真軟件OPNET Modeler模擬網(wǎng)絡(luò)環(huán)境進(jìn)行測試，將DLBFA算法與OPNET Modeler自帶的最小連接調(diào)度（WLC）算法以及其他改進(jìn)的基于動態(tài)反饋的負(fù)載均衡算法（MTN）[9]進(jìn)行對比,。本次實(shí)驗(yàn)主要觀察平均響應(yīng)時間,，即集群系統(tǒng)對連接請求的平均響應(yīng)時間。

　　模擬網(wǎng)絡(luò)的客戶端有200個節(jié)點(diǎn),，仿真運(yùn)行30 min,，由于客戶端的配置數(shù)目較大，固定性能數(shù)據(jù)采集周期T設(shè)置為20 s,。為了驗(yàn)證算法在性能不同的服務(wù)器集群上的效果,，本實(shí)驗(yàn)使用3種性能不同的服務(wù)器組成了實(shí)驗(yàn)集群，服務(wù)器性能大小次序?yàn)椋悍?wù)器1<服務(wù)器2<服務(wù)器3,?？蛻舳伺c服務(wù)器集群系統(tǒng)通過鏈路與負(fù)載均衡器相連。

　　2.2 實(shí)驗(yàn)結(jié)果與分析

　　實(shí)驗(yàn)結(jié)果如圖2所示,。

　　實(shí)驗(yàn)運(yùn)行約5 min后進(jìn)入響應(yīng)時間穩(wěn)定期,，通過觀察此后響應(yīng)時間數(shù)據(jù)分析結(jié)果。從圖2（a）可見,，在運(yùn)行WLC算法的集群中,，不同性能的服務(wù)器的響應(yīng)時間差別并不太大，說明性能較好的服務(wù)器其處理資源并沒有被充分利用,，負(fù)載均衡算法對任務(wù)分配并不理想,，并沒有達(dá)到預(yù)期的目的。從圖2（b）可以看出,，改進(jìn)的MTN算法由于考慮了服務(wù)器的負(fù)載和性能情況,，各個節(jié)點(diǎn)的響應(yīng)時間隨著性能變化而變化，分配效果有了一定的改進(jìn)，但是響應(yīng)時間的區(qū)分程度還是不夠明顯,。而圖2（c）顯示,，本文的DLBFA算法的負(fù)載均衡效果有了進(jìn)一步提高，能更好區(qū)分不同服務(wù)器的性能任務(wù)的分配,，這使得服務(wù)器集群的資源得到了充分的利用,，達(dá)到了實(shí)驗(yàn)需要的目標(biāo)。

3 結(jié)論

　　CDN中的負(fù)載均衡算法是提高網(wǎng)站服務(wù)質(zhì)量和性能的關(guān)鍵,，與傳統(tǒng)的負(fù)載均衡算法相比,，本文提出的動態(tài)負(fù)載均衡算法有如下特點(diǎn)：

　　（1）該算法通過負(fù)載均衡器動態(tài)地收集各個服務(wù)器的實(shí)時性能數(shù)據(jù),，將服務(wù)器的實(shí)時負(fù)載加入到算法中綜合考慮,，使得連接請求的調(diào)度更加合理。

　?。?）如何通過實(shí)時的性能數(shù)據(jù)合理地評估實(shí)時負(fù)載情況是本文的主要著力點(diǎn),。本文通過使用統(tǒng)計學(xué)中的因子分析法將獲得的實(shí)時數(shù)據(jù)組織起來，提出了一個較為有理有據(jù)的實(shí)時負(fù)載情況的計算式,。

　　通過合理地組織實(shí)時負(fù)載數(shù)據(jù),，較準(zhǔn)確地測算出實(shí)時負(fù)載情況，可以幫助負(fù)載均衡模塊在連接請求調(diào)度時做出更為合理的選擇,，而本文的實(shí)驗(yàn)結(jié)果也證明了這一點(diǎn),，具有一定的應(yīng)用價值。

參考文獻(xiàn)

　　[1] 胡利軍.Web集群服務(wù)器的負(fù)載均衡和性能優(yōu)化[D].北京：北京郵電大學(xué),，2010.

　　[2] 張慧芳.基于動態(tài)反饋的加權(quán)最小連接數(shù)服務(wù)器負(fù)載均衡算法研究[D].上海：華東理工大學(xué),，2013.

　　[3] HWANG S T， JUNG N S. Dynamic scheduling of web server cluster[C]. Proceedings of the 9th International Conference on Parallel and Distributed System,， 2002：563-568.

　　[4] Duan Zhaolei,， Gu Zhimin. Dynamic load balancing in web cache cluster[C]. 7th International Conference on Grid and Cooperative Computing， 2008：147-150.

　　[5] 章文嵩.Linux服務(wù)器集群系統(tǒng)（四）[EB/OL].（2002-05-20）.[2014-08-30].http：//www.ibm.com/developerworks/cn/linux/cluster/lvs/part4/index.html.

　　[6] 陳偉,，張玉芳,，熊忠陽.動態(tài)反饋的異構(gòu)集群負(fù)載均衡算法的實(shí)現(xiàn)[J].重慶大學(xué)學(xué)報，2010,，33（2）：73-78.

　　[7] 謝雯.基于因子分析的中國證券公司競爭力研究[D].上海：復(fù)旦大學(xué),，2012.

　　[8] 高惠璇.應(yīng)用多元統(tǒng)計分析[M].北京：北京大學(xué)出版社,，2005.

　　[9] 劉健,，徐磊，張維明.基于動態(tài)反饋的負(fù)載均衡算法[J].計算機(jī)工程與科學(xué),，2003,，25（5）：65-68.