基于因子分析的動態負載均衡算法*

陳練達，曾國蓀，2（.同濟大學 計算機科學與技術系，上海 200092；2.國家高性能計算機工程技術中心　同濟分中心，上海 200092）

基于因子分析的動態負載均衡算法*

陳練達1，曾國蓀1，2
（1.同濟大學 計算機科學與技術系，上海 200092；2.國家高性能計算機工程技術中心同濟分中心，上海 200092）

隨著互聯網的不斷發展、用戶數量的急劇增長，互聯網中出現了網絡擁塞、服務器負載過重、響應時間過長等嚴重問題，其中負載均衡算法是影響服務器集群整體性能的一個關鍵因素。運用統計學中的因子分析理論，提出了一種基于因子分析的負載均衡算法。該算法利用因子分析法計算出綜合負載，并用這個指標幫助負載均衡器選擇合適的服務器，均勻地將用戶的請求進行分發，從而達到整體上較好的負載均衡。

內容分發；因子分析；負載均衡

0　引言

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

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

據以往的研究看來，負載的計算往往是按照一定的加權比例進行的，比較經驗主義，且主觀性和隨意性比較大，沒有一個較為科學的方法來確定加權的比例，從而導致實時負載計算式反饋出來的不太不準確。為了解決準確評估實時負載的問題，本文采用了統計學中的因子分析法來評估實時負載，以求達到較準確評估負載。

1　基于因子分析的動態負載均衡方法

1.1算法設計思路

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

圖1　負載均衡算法的模型圖

設有n臺緩存服務器組成的集群，則可以定義服務器設備集合S=｛S1，S2，…，Sn｝（n＞1）。該算法的核心內容為：服務器設備集群中的各個服務器節點在每間隔一個時間周期T就向負載均衡調度器反饋當前服務器的服務器性能參數，調度器接收到這些負載度量信息后，利用這些負載度量信息評估出實時負載情況，結合實時負載情況，做出緩存服務器的選擇，達到合理的負載均衡。因此，本文要做的工作是：（1）選擇什么負載度量信息；（2）用什么計算方法組織這些負載度量信息，得出一個綜合的負載情況指標；（3）如何與WLC算法進行結合。1.2實時負載情況的量化

首要的工作是如何評價服務器的負載情況。采用數值量化的辦法無疑是較為合理的，本文利用多元統計分析學中的因子分析法［7-8］，通過合理的推導和計算，獲得能夠反映實時負載情況的量化，從而幫助現有負載均衡算法做出更準確的任務分配，達到改進已有負載均衡算法的目的。

定義1負載參數變量：某種可觀測的、影響實時負載能力的變量，Xi表示第 i種影響負載能力的變量，這里用 X1表示 CPU利用率，X2表示內存利用率，X3表示磁盤利用率，X4表示網絡帶寬使用率。

定義 2實時負載指數：Load表示負載實時指數，有Load=g（X1，…，X4），g表示Xi與Load的關系函數。

定義3負載參數向量：由X1，…，X4構成的4維可觀測向量，記為X，其各維數據均為可以較準確、直接觀測出的數據。

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

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

該模型用矩陣表示為：

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

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

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

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

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

經過以上分析過程，從原來常用簡單的線性疊加式，通過使用因子分析法的方式，得到了實時負載指數的計算公式，為后文的負載均衡算法的改進和實驗分析提供了依據。

1.3DLBFA算法的設計

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

從前文可知，負載情況的計算需要采集的一些服務器性能信息是以較主流的 CPU、內存、磁盤和網絡4個方面來源為主的。其中負載參數向量X記為：X＝（U1，U2，U3，U4）T，其中向量各維分別為 CPU利用率、內存利用率、磁盤利用率和網絡帶寬使用率。那么可以結合式（8），經過因子分析的過程算出Li。再將Li與WLC算法結合，形成改進算法。可以約定如下：設服務器集合 S=｛S1，S2，…，Sn｝（n＞1），W（Si）表示服務器的權值，C（Si）表示服務器 Si當前連接數，α（Si）表示服務器Si對應的可變因子，則選擇服務器的策略為：其中，βi=（β1i，…，β4i）T是前面提到的因子得分系數矩陣的列向量，X為負載因素向量。

由于在因子分析法計算出的綜合得分有一些會出現負值，因此做一定修正，即：

式（9）達到了 W（Si）的動態變化的目的，其中 α（Si）的確定與 Li的值有關，這樣就可以做到 Li與WLC算法的結合。α（Si）確定的策略以各個服務器的負載平均值L為基準，即：其中，當第i臺服務器的負載指數大于平均負載指數時，可認為負載過重，此時將 α（Si）的值調小，達到了降低權值的目的；如果第i臺服務器的負載指數小于平均負載指數，則認為負載較輕，此時 α（Si）的值為 1不變，保持權值也不變。這里設置的ε、θ是為了防止 α（Si）調整過于頻繁影響任務調度而設置的閾值，保證了服務器的負載情況穩定在一定范圍之內。算法的偽代碼描述如下：

算法1基于因子分析的動態負載均衡算法

輸入：用戶請求集 VR，服務器節點集 VS，服務器權重集合W，可變因子集合α，服務器當前連接數集合C。

輸出：請求映射到服務器的集合。

2　實驗及分析

2.1實驗方案與環境

為了驗證改進算法的基本性能，本實驗采用網絡仿真軟件 OPNETModeler模擬網絡環境進行測試，將DLBFA算法與 OPNETModeler自帶的最小連接調度（WLC）算法以及其他改進的基于動態反饋的負載均衡算法（MTN）［9］進行對比。本次實驗主要觀察平均響應時間，即集群系統對連接請求的平均響應時間。

模擬網絡的客戶端有200個節點，仿真運行30 min，由于客戶端的配置數目較大，固定性能數據采集周期T設置為20 s。為了驗證算法在性能不同的服務器集群上的效果，本實驗使用3種性能不同的服務器組成了實驗集群，服務器性能大小次序為：服務器1＜服務器2＜服務器3。客戶端與服務器集群系統通過鏈路與負載均衡器相連。

2.2實驗結果與分析

實驗結果如圖2所示。

圖2　實驗結果

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

3　結論

CDN中的負載均衡算法是提高網站服務質量和性能的關鍵，與傳統的負載均衡算法相比，本文提出的動態負載均衡算法有如下特點：

（1）該算法通過負載均衡器動態地收集各個服務器的實時性能數據，將服務器的實時負載加入到算法中綜合考慮，使得連接請求的調度更加合理。

（2）如何通過實時的性能數據合理地評估實時負載情況是本文的主要著力點。本文通過使用統計學中的因子分析法將獲得的實時數據組織起來，提出了一個較為有理有據的實時負載情況的計算式。

通過合理地組織實時負載數據，較準確地測算出實時負載情況，可以幫助負載均衡模塊在連接請求調度時做出更為合理的選擇，而本文的實驗結果也證明了這一點，具有一定的應用價值。

［1］胡利軍.Web集群服務器的負載均衡和性能優化［D］.北京：北京郵電大學，2010.

［2］張慧芳.基于動態反饋的加權最小連接數服務器負載均衡算法研究［D］.上海：華東理工大學，2013.

［3］HWANG S T，JUNG N S.Dynamic scheduling of web server cluster［C］.Proceedings of the 9thInternational Conference on Parallel and Distributed System，2002：563-568.

［4］Duan Zhaolei，Gu Zhimin.Dynamic load balancing in web cache cluster［C］.7thInternational Conference on Grid and Cooperative Computing，2008：147-150.

［5］章文嵩.Linux服務器集群系統（四）［EB/OL］.（2002-05-20）.［2014-08-30］.http：//www.ibm.com/developerworks/cn/ linux/cluster/lvs/part4/index.html.

［6］陳偉，張玉芳，熊忠陽.動態反饋的異構集群負載均衡算法的實現［J］.重慶大學學報，2010，33（2）：73-78.

［7］謝雯.基于因子分析的中國證券公司競爭力研究［D］.上海：復旦大學，2012.

［8］高惠璇.應用多元統計分析［M］.北京：北京大學出版社，2005.

［9］劉健，徐磊，張維明.基于動態反饋的負載均衡算法［J］.計算機工程與科學，2003，25（5）：65-68.

CDN′s dynamic load-balance algorithm based on factor analysis method

Chen Lianda1，Zeng Guosun1，2
（1.Department of Computer Science and Technology，Tongji University，Shanghai 200092，China；2.Tongji Branch，National Engineering&Technology Center of High Performance Computer，Shanghai 200092，China）

With the development of Internet and the rapid increase of users，there are a lot of serious problems in Internet，such as network congestion，server overload and too long response time.The load balance algorithm is the important factor that impacts the whole performance.In this paper，the factor analysis method is used to improve the algorithm，and an improved algorithm that combined with factor analysis method is propsed.The improved algorithm uses factor analysis method to figure out the servers′load，and the index can help load balancer choose the appropriate server，then the requests will be distributed evenly，and the cluster achieves a better load-balance status.

content delivery；factor analysis；load balance

TP319

A

1674-7720（2015）02-0059-04

863項目（2009AA012201）；國家自然基金項目（61272107，61202173，61103068）；上海市優秀學科帶頭人計劃項目（10XD1404400）；華為創新研究計劃項目（IRP-2013-12-03）；高效能服務器和存儲技術國家重點實驗室開放基金項目（2014HSSA10）

（2014-09-17）

陳練達（1990-），男，碩士研究生，主要研究方向：并行與分布式計算。

曾國蓀（1962-），男，博士，教授，博士生導師，主要研究方向：并行計算，可信軟件，信息安全。