集群服務(wù)器在混合請求下的負載均衡優(yōu)化算法

申澤星，彭云建，岳喜順

華南理工大學 自動化科學與工程學院，廣州 510640

1 引言

隨著互聯(lián)網(wǎng)的高速發(fā)展，各類網(wǎng)絡(luò)化信息系統(tǒng)規(guī)模越來越大，訪問流量呈幾何級數(shù)增長，為了滿足新一代網(wǎng)絡(luò)要求，實現(xiàn)B/S網(wǎng)頁信息集成發(fā)布與交互處理，即提供更豐富的內(nèi)容、更好的交互性和更高的安全性[1-3]，Web服務(wù)器采用大量的CGI、java/php/asp動態(tài)生成頁面等信息密集型應用，這對服務(wù)器的工作性能提出更高要求。單個Web服務(wù)器在處理大量服務(wù)請求時會存在工作負載過大，服務(wù)請求響應時間長，反饋延遲大的問題，嚴重時會出現(xiàn)單點故障，用戶體驗表現(xiàn)較差。解決這類問題有兩種基本方法：一是硬件擴展，為服務(wù)器配置計算處理能力更強大的硬件，其優(yōu)點是便于服務(wù)器系統(tǒng)的部署、備份和恢復，維護操作也相對簡單；但是計算機硬件的數(shù)據(jù)處理能力始終存在瓶頸，且高性能的配置價格昂貴，這種方法仍難以滿足Web應用的需求；二是多服務(wù)器并行處理方式[4]，多臺服務(wù)器通過高速局域網(wǎng)的連接，域名服務(wù)器和接入服務(wù)器的管理，構(gòu)成單一站點（訪問的域名或公網(wǎng)IP地址相同）的服務(wù)器集群，將用戶的訪問請求通過負載管理服務(wù)器分配到集群中各個服務(wù)器上[5-6]，從而增加整個站點系統(tǒng)的擴展能力與容錯能力，提高系統(tǒng)響應效率與可靠性，為用戶提供并發(fā)服務(wù)[7-8]，該方法成為目前部署大型信息服務(wù)系統(tǒng)的主要方案，為構(gòu)建開放式的“云”服務(wù)系統(tǒng)提供完備的技術(shù)基礎(chǔ)。Web集群的組網(wǎng)拓撲結(jié)構(gòu)如圖1所示。

圖1 Web集群服務(wù)器組網(wǎng)的拓撲結(jié)構(gòu)示意圖

服務(wù)器集群中單個服務(wù)器的結(jié)構(gòu)和性能存在差異，客戶端訪問具有隨機性和突發(fā)性，訪問來源與內(nèi)容多樣化、碎片化，造成某些服務(wù)器承受過少或過多的負載，此類非均衡的負載分配會嚴重降低服務(wù)器集群系統(tǒng)的整體性能。因此現(xiàn)有系統(tǒng)一般會配置負載均衡器[9]。負載均衡器根據(jù)單個服務(wù)器的最大處理能力和當前的負載狀況，依據(jù)負載調(diào)度策略分配負載任務(wù)，合理利用每臺服務(wù)器的資源而避免出現(xiàn)過載情況，提高了服務(wù)器集群的穩(wěn)定性和響應速度。

對于Web服務(wù)器集群的負載均衡研究，從模型、算法與應用實現(xiàn)幾個方面已有較多成果。文獻[10-12]將負載均衡算法分為靜態(tài)和動態(tài)兩大類。靜態(tài)負載均衡算法包括Random隨機（RAN）算法、Round-Robin輪詢（RR）算法以及靜態(tài)權(quán)重輪詢（SWRR）算法。該類算法將各服務(wù)器的任務(wù)分配比例作為系統(tǒng)參數(shù)保存在負載均衡器中，不考慮服務(wù)器負載的實時變化情況[13-14]。靜態(tài)負載均衡算法屬于開環(huán)負載調(diào)節(jié)方式，難以滿足新一代服務(wù)器集群的性能要求。動態(tài)負載均衡算法包括最少連接（LC）算法、加權(quán)最少連接（WLC）[15]算法和動態(tài)權(quán)重輪詢（DWRR）算法[16]。負載均衡器周期性收集每臺服務(wù)器的負載信息，根據(jù)服務(wù)器的實時負載水平計算任務(wù)分配權(quán)重分配任務(wù)，在請求任務(wù)類型不同和工作負載差異較大的情況下，動態(tài)負載均衡算性能優(yōu)于靜態(tài)負載均衡算法，但動態(tài)負載均衡算法需要額外的數(shù)據(jù)處理與傳輸。傳統(tǒng)的動態(tài)負載均衡算法存在著局限性，譬如，最少連接算法以連接數(shù)量衡量服務(wù)器當前的負載情況，因為服務(wù)器性能不同、動態(tài)頁面訪問任務(wù)消耗的服務(wù)器資源不同，連接數(shù)相同不等同于服務(wù)器承受的負載量相同[17]。服務(wù)器集群長時間運行，會出現(xiàn)負載誤差累積情況，將導致各個服務(wù)器所承受的負載量不均衡。針對最小連接算法的問題，文獻[17]提出了根據(jù)服務(wù)器的CPU、磁盤I/O、內(nèi)存、網(wǎng)絡(luò)帶寬等占用率和最大處理能力以及進程數(shù)量等指標來評估服務(wù)器的負載水平，由此確定服務(wù)器的任務(wù)分配權(quán)重。但受到服務(wù)器負載參數(shù)采樣周期的影響，負載量的計算和采集存在較大誤差，并在一定時間內(nèi)具有累積性。

針對傳統(tǒng)負載均衡算法和文獻[17]中算法的局限性，本文提出了在混合請求服務(wù)中的負載均衡優(yōu)化算法，根據(jù)請求服務(wù)的數(shù)據(jù)存取與處理特點，優(yōu)化處理靜態(tài)和動態(tài)頁面的負載量估計模型以衡量服務(wù)器實時負載率，基于動態(tài)預測方法并采用不同的方式分配服務(wù)請求任務(wù)達到負載均衡的目的。

2 混合服務(wù)請求的負載均衡模型

負載均衡器在接收的服務(wù)請求中包含靜態(tài)頁面請求和動態(tài)頁面請求，靜態(tài)頁面和動態(tài)頁面在數(shù)據(jù)存儲和頁面內(nèi)容產(chǎn)生上有很大的差異性，服務(wù)器的處理方式也不相同。處理靜態(tài)頁面的訪問，服務(wù)器先查看緩存中是否緩存此靜態(tài)頁面，如果有，直接從緩存中讀取頁面數(shù)據(jù)并返回頁面；否則，從磁盤中讀取頁面文件，并按照調(diào)度算法（如LRU算法）緩存靜態(tài)頁面。動態(tài)頁面則是根據(jù)用戶不同的請求參數(shù)，從數(shù)據(jù)庫或數(shù)據(jù)文件等讀取頁面內(nèi)容數(shù)據(jù)，基于數(shù)據(jù)處理邏輯生成信息塊并組合成響應頁面發(fā)送給用戶。因此，動態(tài)頁面一般難以完整緩存[18]。

靜態(tài)頁面訪問產(chǎn)生的負載量與靜態(tài)頁面文件大小、讀取頁面的方式有關(guān)，用ρS表示：

其中，S是靜態(tài)頁面文件大小，λ是讀取靜態(tài)頁面文件及處理發(fā)送的資源（包括CPU、內(nèi)存、磁盤讀取和網(wǎng)絡(luò)）使用率系數(shù)，從磁盤中讀取頁面文件并處理時取λ=λ1，從緩存中讀取靜態(tài)頁面文件及處理時取λ=λ2，一般的，λ1＞λ2。設(shè)服務(wù)器在時間TS內(nèi)累計接收了cS個靜態(tài)頁面的訪問，則服務(wù)器單位時間內(nèi)需處理計算的靜態(tài)頁面負載量記為LS，計算式為：

服務(wù)器處理動態(tài)頁面訪問的負載量主要由兩部分組成：一是服務(wù)器根據(jù)頁面訪問參數(shù)，查詢數(shù)據(jù)和調(diào)用業(yè)務(wù)邏輯處理程序，生成視圖頁面，該部分是與計算性能有關(guān)的常量，用G表示；其次是緩存和發(fā)送視圖頁面產(chǎn)生的負載量。同理，單位時間內(nèi)要處理動態(tài)頁面的負載量記為LD，計算式：

其中cd是TD時間內(nèi)需緩存與轉(zhuǎn)發(fā)的動態(tài)頁面訪問數(shù)量，ρD是動態(tài)頁面訪問產(chǎn)生的負載量。

在混合類型服務(wù)請求中，服務(wù)器在單位時間內(nèi)承受的總負載量是靜態(tài)頁面訪問和動態(tài)頁面訪問產(chǎn)生的負載量之和，記為L：

設(shè)服務(wù)器在t時刻正在處理ns(t)個靜態(tài)頁面訪問和nd(t)個動態(tài)頁面訪問，在t+Δt時刻接收新的靜態(tài)與動態(tài)頁面訪問請求數(shù)分別為Δns(t)和Δnd(t)個，則處理過程的時序如圖2所示。圖中實橫線表示一個動態(tài)頁面訪問，虛橫線表示一個靜態(tài)頁面訪問，橫線的長度表示服務(wù)器完成處理頁面訪問的時間長短，服務(wù)器在任何時刻的負載水平由新接收的訪問處理任務(wù)和之前未處理完任務(wù)的負載量累積而成，由于頁面訪問具有隨機性，且頁面文件大小與處理邏輯的計算量不同導致服務(wù)器完成負載量處理的時間不同，因此，服務(wù)器處理混合頁面訪問的負載率是一類典型的隨機過程。如果僅考慮靜態(tài)頁面訪問或動態(tài)頁面訪問的負載均衡，都會導致服務(wù)器集群負載不均衡。如圖3所示，單一負載均衡會導致局部服務(wù)器承受過多或過少負載。

圖2 單臺服務(wù)器處理混合頁面訪問時序圖

圖3 Web集群服務(wù)器處理混合頁面訪問的時序圖

針對處理混合服務(wù)請求中的負載均衡問題，設(shè)負載均衡器周期性采集每臺服務(wù)器的負載參數(shù)為X(k T),k=1,2,…,T為采樣周期，根據(jù)服務(wù)器的歷史采樣周期的負載量和當前負載量預測下一周期的負載率（即，服務(wù)器單位時間內(nèi)承受的負載量與最大處理能力的比例），根據(jù)服務(wù)器之間的負載水平差異分配當前的頁面訪問任務(wù)，從而形成一類動態(tài)反饋的任務(wù)分配策略，基本方案如圖4所示。

圖4 動態(tài)反饋示意圖

對于圖4表示的反饋型混合服務(wù)請求的負載均衡算法，需要解決以下問題：

（1）對靜態(tài)頁面文件進行分類提高服務(wù)器緩存命中率。

（2）每臺服務(wù)器需采集負載參數(shù)并計算本地機需處理的靜態(tài)、動態(tài)頁面負載量，并周期性地將此信息反饋給負載均衡器。

（3）負載均衡器根據(jù)每臺服務(wù)器承受的歷史負載和當前負載，準確預估下一周期每臺服務(wù)器的負載率。

（4）負載均衡器根據(jù)預測負載率和優(yōu)化模型求得合理的動態(tài)頁面訪問分配權(quán)重，達到負載均衡的效果。

3 混合服務(wù)請求負載均衡算法

3.1 負載均衡算法的基本流程

本文算法流程如圖5所示，系統(tǒng)初始化階段計算服務(wù)器的最大處理能力，確定訪問頁面的類型參數(shù)。其次，根據(jù)負載均衡器哈希表分配靜態(tài)頁面訪問，計算處理靜態(tài)和動態(tài)頁面的負載量。最后，通過計算平均預測負載率與各臺服務(wù)器負載率的最小偏差和求出最優(yōu)分配權(quán)重動態(tài)分配處理頁面訪問的任務(wù)。

圖5 服務(wù)器集群負載分配流程圖

3.2 負載均衡優(yōu)化模型

根據(jù)文獻[6，19]，單臺服務(wù)器最大處理能力主要用5個指標表示：CPU數(shù)量μ，CPU頻率 f(GHz)，內(nèi)存容量 M(GB)，磁盤I/O速率 D(MB?s-1)，網(wǎng)絡(luò)吞吐量N(MB?s-1)。設(shè)各指標對服務(wù)器最大處理能力的影響系數(shù)為k1～k4，服務(wù)器的最大處理能力C由下式計算：

不同類型的服務(wù)器ki不同，比如FTP服務(wù)器側(cè)重網(wǎng)絡(luò)吞吐量和磁盤I/O速率，而HTTP服務(wù)器側(cè)重CPU數(shù)量和頻率[19]。一般情況下，各指標的影響系數(shù)可取k={0.2,0.3,0,0.5}[19-21]。對于有n臺服務(wù)器組成的集群，各臺服務(wù)器最大處理能力計算矩陣公式：

其中，Ci是第i臺服務(wù)器的最大處理能力。

在處理靜態(tài)頁面訪問時，為了提高緩存命中率，將靜態(tài)頁面文件按照大小分類。在t時刻服務(wù)器需處理的靜態(tài)頁面負載LSi()t由下式可得：

其中，Sj是第 j類靜態(tài)頁面的大小，ρSj是訪問第 j類靜態(tài)頁面產(chǎn)生的負載，cj()t為t時刻服務(wù)器處理的第 j類靜態(tài)頁面數(shù)量。

設(shè)t時刻第i臺服務(wù)器第 j類靜態(tài)文件訪問數(shù)量為ci,j(t)，第i臺服務(wù)器在t時刻需處理的靜態(tài)頁面負載記為LSi(t)：

為了加速負載均衡器查找靜態(tài)頁面訪問分配的服務(wù)器記錄，構(gòu)建一張哈希表，鍵為靜態(tài)頁面文件大小范圍類型，值為該類型靜態(tài)頁面訪問被分配到服務(wù)器的最新歷史記錄。靜態(tài)頁面類型數(shù)少，哈希表所占用的內(nèi)存容量有限，不會影響負載均衡器接收和分配訪問請求的性能，其結(jié)構(gòu)見表1。

表1 負載均衡器哈希表

當負載均衡器收到第 j類靜態(tài)頁面訪問時，查找該類頁面已被分配的服務(wù)器記錄ij(1 ≤i≤n )。若服務(wù)器ij還可以對頁面訪問提供服務(wù)，則將此類靜態(tài)頁面訪問分配給該服務(wù)器；若服務(wù)器ij承受的負載接近其最大處理能力，則將頁面訪問分配給負載率最小的服務(wù)器，并更新第j類靜態(tài)頁面訪問分配的服務(wù)器記錄。

在處理動態(tài)頁面訪問時，服務(wù)器不會緩存動態(tài)頁面，故將此時刻負載均衡器接收到的動態(tài)頁面訪問作為一個待分配的負載整體，為達到負載均衡，負載均衡器需在本周期內(nèi)為每臺服務(wù)器分配動態(tài)頁面訪問的權(quán)重。設(shè)t時刻第i臺服務(wù)器要處理的動態(tài)頁面負載記為LDi(t)，由t時刻前未完成動態(tài)頁面負載量和t時刻接收到的動態(tài)頁面訪問產(chǎn)生的負載組成：

其中，cD(t)是t時刻負載均衡器持有的動態(tài)頁面訪問數(shù)量，Gi是第i臺服務(wù)器生成動態(tài)頁面的性能常數(shù)，wi(k T )是在第k個周期內(nèi)負載均衡器分配給第i臺服務(wù)器動態(tài)頁面訪問的權(quán)重，因為負載均衡器接收數(shù)據(jù)的周期性，wi(k T )與k相關(guān)，一個周期內(nèi)服務(wù)器擁有的分配權(quán)重不會改變。

為了計算動態(tài)頁面訪問分配權(quán)重wi(k T )，用負載率η(t)表示t時刻服務(wù)器消耗本機資源的程度，根據(jù)每臺服務(wù)器最大處理能力C、t時刻服務(wù)器承受的總負載量L可得：

在t時刻第i臺服務(wù)器負載率ηi()t如下：

為了均衡各服務(wù)器的負載量，需使每臺服務(wù)器的負載率相近。各類靜態(tài)頁面類型訪問數(shù)量和存儲方式已知，可估計每臺服務(wù)器單位時間內(nèi)要處理的靜態(tài)頁面負載量；對動態(tài)頁面訪問任務(wù)的分配，需要估計動態(tài)負載量并確定分配權(quán)重w。頁面訪問存在局部性[22]和隨機性，ηi(t)是一個隨機處理過程，選擇時間序列預測算法—指數(shù)平滑法[23]預測集群服務(wù)器的負載率分布，求出合理的分配權(quán)重w，確定處理頁面訪問的任務(wù)。設(shè)一次指數(shù)平滑預測法預測第i臺服務(wù)器第k個周期的負載率為與k相關(guān)：

可見，ηi(k T )與的差值越小，負載均衡效果越好。因此，確定各臺服務(wù)器在第k個周期時刻的權(quán)重使得總負載率偏差最小，且滿足如下約束條件：

其中

單臺服務(wù)器負載率 ηi(t) 應低于0.9[17]，若 ηi(t)大于0.9，說明服務(wù)器承受的負載量接近飽和，不應該對該服務(wù)器再分配請求任務(wù)。根據(jù)柯西不等式：

對式（13）得：

當且僅當

即在第k個周期時刻各臺服務(wù)器負載率相等時，等號成立，此時取得最小值，可得方程組：

由此可解第k個周期內(nèi)第i臺服務(wù)器權(quán)重wi(k T)。如果不存在符合條件的解，需通過實驗找到合適的wi(k T )使得目標函數(shù)值盡可能小。

確定服務(wù)器第k個周期的任務(wù)分配權(quán)重wi(k T)后，根據(jù)公式（9）可知t時刻負載均衡器對第i臺服務(wù)器分配的動態(tài)頁面訪問數(shù)量為并根據(jù)公式（10）求出第k個周期第i臺服務(wù)器實際負載率 ηi(k T )，為預測第(k +1) 個周期的提供數(shù)據(jù)。在第(k +1)個周期分配新的頁面訪問請求時，根據(jù)計算分配權(quán)重wi(( k+1) T)。

4 服務(wù)器集群的負載均衡仿真與結(jié)果分析

選擇15臺性能不同的服務(wù)器組成一個Web服務(wù)器集群，模擬采用不同的負載均衡算法處理混合頁面訪問的過程，計算各個服務(wù)器在不同時刻的負載率，從而評估負載均衡的效果。每臺服務(wù)器的計算性能參數(shù)見表2，按照Web訪問的靜態(tài)頁面按文件大小分為4類，見表3，動態(tài)頁面大小在50～100 KB。

負載模擬仿真分兩種情況進行：（1）采用文獻[17]中負載均衡算法，各服務(wù)器的實時負載率分布如圖6所示。（2）采用本文提出的基于預測負載率的負載均衡優(yōu)化算法，各服務(wù)器的實時負載率分布如圖7所示。圖6和圖7中x軸為服務(wù)器編號（15臺），y軸為仿真時間（取20個時間周期），z軸為各服務(wù)器的負載率。圖6中各個服務(wù)器的初始負載率基本一致，在若干個任務(wù)分配周期后服務(wù)器之間的負載率差距變大。圖7中，負載率曲面表明本文的負載均衡優(yōu)化算法使得各臺服務(wù)器處理頁面訪問的負載率均衡增加，沒有出現(xiàn)圖6中的曲面大波動，服務(wù)器之間在同一時間的負載率相差不超過0.1。圖6和圖7的負載率曲面對比直觀地反映了本文算法在混合請求類型下能夠有效調(diào)節(jié)服務(wù)器的負載分配，使集群中每臺服務(wù)器均衡地增加負載量，負載率不會出現(xiàn)大抖動，相比文獻[17]的算法，本算法具更理想的負載均衡效果并且穩(wěn)定地保持這種狀態(tài)。

表2 群組服務(wù)器的性能參數(shù)表

表3 靜態(tài)頁面大小分類表

圖6 文獻[17]中算法的集群服務(wù)器負載率周期分布曲面

圖7 基于預測負載率的集群服務(wù)器負載率周期分布曲面

其次，將仿真（2）中集群服務(wù)器處理頁面訪問的負載率偏差和的最小值、預期平均負載率和實際平均負載率的變化曲線繪制在圖8中?？梢钥闯觯瑢嶋H負載率隨著預期平均負載率上下波動，并逐步收斂于預期平均負載率，說明本文算法求出的預期平均負載率有效地引導實際平均負載率的變化趨勢，成為調(diào)節(jié)服務(wù)器負載的依據(jù)，從而出現(xiàn)圖7所示的負載均衡。同時，負載率總偏差最小值保持在較小范圍（0～0.03）內(nèi)，且相對穩(wěn)定，說明服務(wù)器整體的實際負載情況與預測期望負載率基本一致，進一步說明了本文負載均衡優(yōu)化算法的正確性和有效性。

圖8 實際平均負載率與預測平均負載率曲線變化圖

5 結(jié)束語

本文提出了集群服務(wù)器在混合服務(wù)請求下的一類負載均衡優(yōu)化算法，建立了混合負載量動態(tài)模型，對于靜態(tài)頁面訪問，將同一類的靜態(tài)頁面訪問分配給同一臺服務(wù)器，提高緩存命中率和響應性；對于動態(tài)頁面訪問，使用一次指數(shù)平滑預測法預測下一周期各個服務(wù)器的負載率，避免使用實時測量數(shù)據(jù)而造成分配負載的滯后性和誤差累積性，通過計算各臺服務(wù)器分配動態(tài)頁面訪問后的負載率與預期負載率的偏差之和在約束條件下取得最小值，求出每臺服務(wù)器的分配權(quán)重，并根據(jù)此權(quán)重對動態(tài)頁面訪問進行分配。仿真結(jié)果表明，本文提出的通過分類頁面訪問和預測引導負載分配的算法在均衡集群中各個服務(wù)器的負載具有更理想的效果。