基于多層集群架構的自適應過載控制機制

摘 要：提出一種自適應的過載控制策略，預先不需要知道任何負載信息，不需要關鍵屬性的人為調節，根據接納率與響應時間的動態關系進行自適應調節，更好地保證了服務水平協議，縮短了響應時間，優化了系統資源。

關鍵詞：自適應； 過載控制； 會話； 多層體系結構

中圖分類號：TP393文獻標志碼：A

文章編號：1001-3695(2009)06-2260-03

doi:10.3969/j.issn.1001-3695.2009.06.079

Self-adaptive overload control mechanism for clusters with multi-tier architecture

ZHENG Rui-feng， FEI Yao-ping， LI Min

(School of Information Science Engineering， Central South University， Changsha 410075， China)

Abstract:

This paper contributed a self-adaptive overload control (SAOC) mechanism，which did not require any prior information on the incoming traffic or manual configuration of key parameters. The monitor module took measures to analyze the relationship between the observed response time (RT) and the rate of admitted sessions. SAOC mechanism guarantees better service level agreements， shortens the response time， self-optimizes the resource utilization rapidly.

Key words：self-adaptive; overload control; session; multi-tier architecture

服務內容的多樣性、用戶訪問的多變性，以及不可預料的需求增加和大量的flash crowds，使Web服務的QoS控制得到越來越多的關注。近年來，圍繞Web服務的QoS控制進行了大量研究，提出了資源劃分、請求調度、接納控制、服務內容區分等典型控制方法，但這些方法始終不足以解決突如其來的額外增加的負載，造成系統過載，嚴重影響用戶服務的響應時間，甚至造成服務失敗。這些機制需要繁瑣的人為設置參數和人為配置，制約了系統根據當前負載狀況快速作出反應。

一個有效控制服務質量的策略，即使在業務量劇增的情況下，也必須保證快速反應和響應。本文提出一種自適應的過載控制策略，實現自適應配置參數、自適應優化系統資源、自適應預防過載。不需要預先知道任何負載信息，也不需要關鍵屬性的人為調節，根據各層請求的響應時間，動態自動調節session接納率，更好地預防系統過載，在保證服務水平協議的基礎上接收盡量多的session，最大化地利用系統資源。

根據自適應過載控制策略要達到的性能，本文的接納控制器操作在應用層，根據應用層session信息，通過cookie或HTTP參數可以方便地區分新的session或已經接收但尚未完成的session^[1]。本文后端集群采用典型的多層體系結構^[2，3] 。一個完整的session包含的一系列請求在不同的層次上被執行，相應的平均處理時間也不同。

1 典型的接納控制策略

1）基于閾值的接納控制（threshold based admission control，TBAC）^[4~6]前端控制器每隔TTBACACs，統計后端集群每一層請求的響應時間，如果響應時間超過規定的閾值RTTBAC，前端控制器便會拒絕新的session，只接收已建立TCP連接的request; 如果響應時間低于RTTBAC，所有新的session在下一個TTBACAC s內都會被接收。基于閾值的接納控制，屬于典型的ON/OFF控制，容易引起響應時間振蕩，并且該機制的性能取決于參數TTBACAC、RTTBAC的設置，無法適應復雜多變的高負載情形。

2）概率接納控制（probabilistic admission control，PAC）^[6] 新的session以概率p(n)被接納，前端控制器每隔TPACAC根據所得響應時間與兩個閾值RTPAClow、 RTPAChigh比較， 計算后端每一層請求的接納率p(ri)，其計算公式為

p(ri)Δ=1if ri≤RTPAClow(RTPAChigh-ri)/(RTPAChigh-RTPAClow)if RTPAClow＜ri≤RTPAChigh

0if ri＞RTPAClow

根據上式計算前端控制器接納率為

p(n)=mini=1，2，…，K p(ri)

與之類似的機制在文獻[7，8]中也有應用，PAC機制兩個閾值的設定，具有主觀性，而且性能控制受監測間隔TPACAC很大影響，依然無法實現控制策略的自適應性。

2 自適應過載控制（SAOC）策略

自適應過載控制策略包括兩種負載模式，在每種模式運行過程中對變量統計并更新，檢測當前負載狀況實現模式之間的轉換。

2.1 服務水平設定

Web應用的服務質量被設定為SLA (service level agreement)，本文涉及的相關參數為引用文獻[9]中的數據參數：RTiSLA為用戶能夠接收的第i層請求的響應時間，本文取響應時間的95%-ile(濾掉最大響應時間與最小響應時間，取中間95%作為參照數據)。其中，i∈{1，2，…，K}，K為集群的層數；λSLA為系統必須保證的最小接納率，本文中λin(t)表示session到達率，λadm(t)表示session接納率，根據服務水平協議必須滿足λadm(t)≥min(λin(t)，λSLA);TSLA為滿足SLA約束的監測間隔時間。

2.2 兩種SAOC模型的提出

SAOC策略包括兩種模式，即normal mode 和flash crowd management mode，根據當前業務狀況，進行模式之間的自動轉換。

正常模式下，系統每隔TSAOCAC進行性能控制更新，每個迭代循環n，接納控制器以自動調整概率p(n)接收新的session，并且統計該時間間隔內requst響應時間，每個迭代結束，系統更新統計量：session平均到達率λin(n)，session平均接納率λadm(n)，95%-ile響應時間RTi(n)，i∈{1，2，…，K}。核心代碼見算法1，算法中t表示本次循環間隔內已經執行的時間。

算法1 Normal mode 核心算法

normal_mode:

while((t

{ n=n+1;

 for each session arrival{

 probabilistic_admission_control;

 collect_raw_measures;

}

}/*end while*/

if(change_detection())

 goto flash_crowd_mode;

else {update_stats;

 update_curve;

 update_admission_probability;

 t=0;

goto normal_mode;}

如果檢測到負載急劇增加，則轉到flash crowd管理模式，進入flash crowd模式后，每接收一個新的session，都要對策略進行更新，當檢測到session瞬時接納率λist低于λ，其中，λ為SAOC機制提供的極限參數，該參數通過分析響應時間和接納率來決定。在這種情況下則認為不可預期的業務劇增已經得到控制，轉入正常模式。核心代碼見算法2。

算法2 Flash crowd management mode 核心算法

flash_crowd_mode:

for each session arrival {

update_stats;

n++;

update_admission_probability;

probabilistic_admission_control;

collect_raw_measures;

measure λist;

if (λist＜λ) goto normal_mode

else goto flash_crowd_mode;}

2.3 變量更新

變量統計與更新是SAOC策略的核心，保證了接納率與響應時間的協調，為實現兩種負載模式轉換提供了數據。

2.3.1 變量參數初始化

SAOC控制策略具有自適應性，初始化數據的設置在SAOC控制機制中不具有重要的作用，本文實驗設置初始化數據為n=0，λ(0)=λSLA，p(0)=1。

2.3.2 更新統計參數

定義Tni為i層請求在時間片[tn，tn+1）內當前已經接收的session的所有請求響應時間的集合， i∈{1，2，…，K}，依此更新統計參數；RTi(n)取集合Tni的95%-ile；λin(n)為時間片[tn，tn+1)內session的平均到達率；λadm(n)為時間片[tn，tn+1)內session的平均接納率。

2.3.3 更新各層請求響應時間質點曲線

單次循環迭代并不能滿足本文要實現的自適用策略，負載的多變性會造成瞬時影響，并且單次迭代測量數量并不足以保證用戶的需求協議，本文采用多次循環迭代，每個迭代周期結束都對響應時間曲線進行更新。

定義第i層RtΔ={(λadm(n)，RTi(n))，n∈{0，1，…}}為接納率與響應時間的集合點，橫坐標軸以接納率λadm為基準，定義間隔lλ，對于每個間隔[(k-1)lλ;klλ)， k=1，2，…，定義Pik={(λadm，RTi)|λadm∈[(k-1)lλ;klλ)}。

計算質心坐標Bik=(λBk，RTBik)為第k個坐標間隔lλ所包含的集合點的平均值。如果Pik=，那么該坐標空間內沒有質點。圖1為數據庫層請求的質點坐標圖，該圖中的質點坐標已經丟棄超過偏差線（RT_Curve）20%的數據。

圖1描述的是接納率與響應時間的關系，根據機制的自適應性，相鄰質點應該滿足單調不減的關系，由圖1可知，曲線的總體趨勢是不減的，但存在相鄰質點不滿足單調不減，那么采取擴大間隔的長度，再次計算質點平均值，丟棄仍然不滿足線性不減的質點，則得出平均質點曲線圖，如圖2所示。



對集群的每一層請求繪制平均質點曲線圖，求出每一層請求的接納上限λi(n)以便計算接納控制器的接納上限概率λ(n)。如圖2所示，數據庫層的接納上限概率取該圖中高于SLA的第一個質點的橫坐標。

2.3.4 預測到達率、更新接納率

下一個時間間隔[tn，tn+1）內session到達率預測為上一間隔的到達率，即λ^in(n)=λin(n-1)。

在確定[tn，tn+1)接納上限概率之前，首先判定兩種錯誤：

a)[tn-1，tn)間隔內if(λadm(n-1)≥λ(n-1)) and i∈1，2，…，K使RTi＜RTiSLA) then error+=true;

b)[tn-1，tn)間隔內if(λadm(n-1)≤λ(n-1)) and i∈{1，2，…，K}使RTi＞RTiSLA) then error+=true。

如果[tn，tn+1)內沒有出現上述兩種錯誤，則λ(n)=λ(n-1)；如果出現上述錯誤的任意一種，則λ(n)=mini=1，2，…，Kλi(n)。其中：λi(n)由時間質點曲線圖得出，由此得出新的session接納概率：p(n)=min{1，λ(n)/λin(^n)}。

2.4 Normal mode 向 flash crowd 轉換的判斷

該機制包括兩個連接的控制器和觸發器，當檢查到N＞λ×TSAOCAC，且(N/t)＞(λ+κσλ)成立時，觸發器觸發flash crowd模式運行。其中：N為當前循環周期接收的session總數；t為本循環周期所用的時間。其核心代碼見算法3。

算法3 change_detection核心算法

Boolean change_detection() {

if((N＞λ×TSAOCAC)AND((N/t)＞(λ+κσλ)))

 return TRUE;

else return FALSE;

}

3 仿真結果

為檢驗SAOC機制的性能，使用OPNET modeler^[10]仿真本文涉及到的接納控制機制，與基于閾值的接納控制（TBAC）、概率接納控制（PAC）控制策略比較。

實驗采用每個會話模型映射到后端三層集群架構，使用文獻[6]中近似估計的平均處理時間， HTTP請求處理時間為0.001 s，servlet請求處理時間為0.01 s，database請求處理時間為1 s。實驗對數據庫層請求分析，SAOC機制參數的取值TSAOCAC，lλ并不影響該機制的自適應性，仿真中取TSAOCAC為200 s， lλ為0.3。服務超時時間設定為8 s，用戶在SLA定義的服務水平標準RT_SLA=5 s；TBAC控制機制設置RTTBACAC為服務水平標準響應時間，即RTTBACAC=5 s，TTBACAC=200 s，PAC控制機制兩個閾值設置RTPAClow=3 s， RTPAChigh=5 s，滿足SLA定義的服務水平標準， TPACAC=200 s。

實驗表明，SAOC控制策略具有自適應性，由圖3可以得出。當負載增加時，SAOC控制可以盡可能多地接收session，并且可以很好地控制SLA服務質量，對用戶服務作出及時響應。SAOC機制可以快速判斷當前負載狀況，迅速拒絕已經超過設定時限的session后續請求，避免了不必要的資源浪費，提高了session成功接納率。圖4截取了仿真時間開始1 800~5 400 s每隔200 s統計的數據庫層請求95%-ile響應時間，由圖可見SAOC機制抵制了響應時間的振蕩效應，具有相對穩定性。

4 結束語

本文在三層集群體系架構的基礎上提出了一種自適應過載控制機制（SAOC），實現了系統的自適應配置和優化，通過變化檢測機制根據當前業務量狀況實現兩種模式的相互轉換，對復雜變化的負載快速作出響應，更好地保證了用戶定義的SLA，抵制了振蕩效應，保證了系統的穩定性。

SAOC機制不需要人為動態設置參數，與PAC、TBAC比較，更迅速地判斷當前負載，對請求作出快速響應。由于SAOC機制需要統計大量參數并且進行更新，加重了運算量，在低負載時，與前兩種機制比較沒有太大改善，高負載時SAOC控制機制能很好地控制響應時間。

參考文獻：

[1]PHP:hypertext preprocessor[EB/OL]. http://www.php.net.

[2]CARDELLINI V，CASALICCHIO E，COLAJANNI M， et al. The state of the art in locally distributed Web server systems[J]. ACM Computing Surveys， 2002，34(2):263-311.

[3]URGAONKAR B， PACIFICI G， SHENOY P， et al. An analytical model for multi-tier Internet services and its applications[C]//Proc of ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems. 2005:291-302.

[4]BARTOLINI N， BONGIOVANNI G， SILVESTRI S. Distributed ser-ver selection and admission control in replicated Web systems[C]//Proc of the 6rd IEEE International Symposium on Parallel and Distri-buted Computing (ISPDC). 2007:31-38.

[5]CHERKASOVA L， PHAAL P. Session based admission control: a mechanism for peak load management of commercial Web sites[J]. IEEE Trans on Computers， 2002， 51(6):669-685.

[6]ELNIKETY S， NAHUM E， TRACEY J， et al. A method for transparent admission control and request scheduling in e-commerce Web sites[C]//Proc of the 13th International Conference on World Wide Web (WWW). 2004:276-286.

[7]AWEYA J， OUELETTE M， MONTUNO D Y， et al. An adaptive load balancing scheme for Web servers[J]. International Journal of Network Management， 2002，12(1):3-39.

[8]MAURICE C， MICHAEL D， MICHAEL R. Load balancing and control for distributed World Wide Web servers[C]//Proc of IEEE Control Applications. 1999:1614-1618.

[9]BARTOLINI N， BONGIOVANNI G， SILVESTRI S. An adaptive admission control policy for geographically distributed Web systems[C]//Proc of ACM International Conference on Scalable Information Systems (INFOSCALE). 2007: 178-186.

[10]OPNET Technologies Inc[EB/OL]. http://www.opnet.com.

[11]XU Z， BOCHMANN G V. A probabilistic approach for admission control to Web servers[C]//Proc of International Symposium on Performance Evaluation ofComputer and Telecommunication Systems (SPECTS). 2004:787-794.