集群服務器在混合請求下的負載均衡優化算法

申澤星，彭云建，岳喜順

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

1 引言

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

圖1 Web集群服務器組網的拓撲結構示意圖

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

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

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

2 混合服務請求的負載均衡模型

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

靜態頁面訪問產生的負載量與靜態頁面文件大小、讀取頁面的方式有關，用ρS表示：

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

服務器處理動態頁面訪問的負載量主要由兩部分組成：一是服務器根據頁面訪問參數，查詢數據和調用業務邏輯處理程序，生成視圖頁面，該部分是與計算性能有關的常量，用G表示；其次是緩存和發送視圖頁面產生的負載量。同理，單位時間內要處理動態頁面的負載量記為LD，計算式：

其中cd是TD時間內需緩存與轉發的動態頁面訪問數量，ρD是動態頁面訪問產生的負載量。

在混合類型服務請求中，服務器在單位時間內承受的總負載量是靜態頁面訪問和動態頁面訪問產生的負載量之和，記為L：

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

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

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

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

圖4 動態反饋示意圖

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

（1）對靜態頁面文件進行分類提高服務器緩存命中率。

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

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

（4）負載均衡器根據預測負載率和優化模型求得合理的動態頁面訪問分配權重，達到負載均衡的效果。

3 混合服務請求負載均衡算法

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

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

圖5 服務器集群負載分配流程圖

3.2 負載均衡優化模型

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

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

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

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

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

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

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

表1 負載均衡器哈希表

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

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

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

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

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

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

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

其中

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

對式（13）得：

當且僅當

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

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

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

4 服務器集群的負載均衡仿真與結果分析

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

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

表2 群組服務器的性能參數表

表3 靜態頁面大小分類表

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

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

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

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

5 結束語

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