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

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

0 引言

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

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

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

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

　　1.1 算法設(shè)計(jì)思路

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

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

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

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

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

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

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

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

　　其中，σij為Xi和Xj的協(xié)方差。設(shè)F=（F1，F(xiàn)2，F(xiàn)3）T為公共因子，這些因子屬于不可直接觀測(cè)、卻又可以影響每個(gè)負(fù)載參數(shù)變量的共同潛在因素，按照本文選取的參數(shù)，可以給F1、F2、F3分別命名為計(jì)算速度因子、網(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ù)變量，那么每個(gè)負(fù)載參數(shù)變量都可以表示成公共因子的線性函數(shù)與特殊因子之和，則：

　　該模型用矩陣表示為：

　　X=AF+ε（3）

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

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

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

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

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

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

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

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

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

　　1.3 DLBFA算法的設(shè)計(jì)

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

　　從前文可知，負(fù)載情況的計(jì)算需要采集的一些服務(wù)器性能信息是以較主流的CPU、內(nèi)存、磁盤和網(wǎng)絡(luò)4個(gè)方面來源為主的。其中負(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對(duì)應(yīng)的可變因子，則選擇服務(wù)器的策略為：

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

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

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

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

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

　　begin

　　m←REQUEST_NUM//獲得請(qǐng)求數(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）獲得每個(gè)服務(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}

　　//請(qǐng)求到服務(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)行測(cè)試，將DLBFA算法與OPNET Modeler自帶的最小連接調(diào)度（WLC）算法以及其他改進(jìn)的基于動(dòng)態(tài)反饋的負(fù)載均衡算法（MTN）[9]進(jìn)行對(duì)比。本次實(shí)驗(yàn)主要觀察平均響應(yīng)時(shí)間，即集群系統(tǒng)對(duì)連接請(qǐng)求的平均響應(yīng)時(shí)間。

　　模擬網(wǎng)絡(luò)的客戶端有200個(gè)節(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)時(shí)間穩(wěn)定期，通過觀察此后響應(yīng)時(shí)間數(shù)據(jù)分析結(jié)果。從圖2（a）可見，在運(yùn)行WLC算法的集群中，不同性能的服務(wù)器的響應(yīng)時(shí)間差別并不太大，說明性能較好的服務(wù)器其處理資源并沒有被充分利用，負(fù)載均衡算法對(duì)任務(wù)分配并不理想，并沒有達(dá)到預(yù)期的目的。從圖2（b）可以看出，改進(jìn)的MTN算法由于考慮了服務(wù)器的負(fù)載和性能情況，各個(gè)節(jié)點(diǎn)的響應(yīng)時(shí)間隨著性能變化而變化，分配效果有了一定的改進(jìn)，但是響應(yīng)時(shí)間的區(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ù)載均衡算法相比，本文提出的動(dòng)態(tài)負(fù)載均衡算法有如下特點(diǎn)：

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

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

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

參考文獻(xiàn)

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

　　[2] 張慧芳.基于動(dòng)態(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] 陳偉，張玉芳，熊忠陽.動(dòng)態(tài)反饋的異構(gòu)集群負(fù)載均衡算法的實(shí)現(xiàn)[J].重慶大學(xué)學(xué)報(bào)，2010，33（2）：73-78.

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

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

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