支持服務優先級的多階段服務模型研究

摘 要:多階段服務模型是一種支持高并發、高吞吐的事件驅動服務應用架構，為使其更好地適應當前Internet上大部分應用提供區分等級服務的現狀，提出了一種為該模型增加對帶優先級請求支持的方法;定義了動態優先級，改進了隨機早期檢測算法以控制不同優先級事件的入隊，并通過優先級動態提升防止低優先級事件被“餓死”。實驗結果表明，改進后的模型在保持系統良好性能的基礎上，滿足了不同優先級請求的實時性和吞吐率需求。

關鍵詞:階段; 優先級; 隊列控制

中圖分類號:TP301.6文獻標志碼:A

文章編號:1001-3695(2009)09-3345-03

doi:10.3969/j.issn.1001-3695.2009.09.041

Study on supporting priority-aware services in SEDA

LUO Hai-nan， ZHOU Ming-tian， CHEN Bo

(School of Computer Science Engineering， University of Electronic Science Technology of China， Chengdu 610054， China)

Abstract:SEDA is an event-driven server application architecture to support high concurrency and throughput. In order to adapt differentiated service provision which was the key to implement various levels of service in Internet applications currently， this paper proposed to incorporate the notion of priority in SEDA. Defined dynamic priority and improved RED algorithm to control events enqueue according to their priorities. Presented dynamic priority upgrading to keep events with lower priority from starvation. Experimental results show that the priority-aware SEDA can satisfy timeliness，throughput requirements of multi-level requests，and maintain the good performance of the system.

Key words:stage; priority; queue control

隨著Internet的迅猛發展，面向社會公眾提供服務的各種服務業應用越來越多地通過Internet發布，且大部分服務都是區分等級的，體現了Internet網絡商業化的目標[1]。網絡信息范圍和數量的指數級增長，龐大的用戶群和服務訪問的強突發性對服務器的并發處理、峰值應對、負載等能力提出了較高的要求和前所未有的挑戰。文獻[2]中提出了一種基于階段的事件驅動架構(staged event-driven architecture，SEDA)，通過動態資源管理策略高效地管理并發、I/O、調度和其他服務器資源，具有比傳統服務架構更高的服務性能和更好的穩定性，但SEDA并不提供對區分等級服務的支持，高優先級事件得不到更及時穩定的優先服務。

本文根據SEDA模型的特點，提出了事件動態優先級的計算方法，借鑒改進的RED算法對事件進行入隊控制，通過事件優先級動態提升進行事件服務順序管理，達到既能為應用中不同等級用戶提供對應級別的服務，又能盡量避免擁塞，獲得較高吞吐率的目的。

1 多階段服務模型

SEDA模型是由Matt Welsh等人于2001年提出的一種階段事件驅動的服務器應用程序架構，其設計目標包括支持大規模的并發操作，有效實現條件負載，確保系統的高可用性等。SEDA的核心思想是將應用程序服務處理邏輯劃分為一系列相互關聯的階段，每個階段是一個相對獨立的執行模塊，完成一個獨立的處理邏輯功能[2]，如對HTTP請求的處理可分為接收、處理和響應三個階段。

每個階段由事件隊列、線程池、事件處理器、隊列控制器和反饋控制器等一系列控制器組成[2]，如圖1所示，每種控制器可以采用不同的實現和控制策略。一個階段可以有多個事件隊列，接收從其他階段傳來的事件，工作線程從隊列中取出事件，調用事件處理邏輯實現對事件的并發處理，并將處理結果封裝為事件傳遞給下一個階段，實現階段之間的相互通信。隊列控制器負責事件準入控制，一般采用隊列長度閾值控制和入隊速率控制兩種策略，當隊列中的事件數量或當前事件到達速率超過預設閾值，將拒絕新的事件入隊。

SEDA原型中實現了動態數組阻塞隊列(DynamicArrayBlockingQueue)等三種隊列，它們的區別僅在于存取事件的數據結構不同，而事件的調度機制均采用的是FIFO策略。然而，針對不同應用的特點和對響應的實時性、完整性等不同要求，當階段負載較大時，簡單的FIFO調度并不能提供令人滿意的處理性能。例如對區分優先級的服務，在FIFO調度下可能造成實時性要求較高的服務請求得不到有效服務的情況。因此，增加對帶優先級事件處理的支持，可以更加充分利用系統資源，使階段在具有多等級用戶的應用中，能優先為高等級用戶提供可靠的服務，同時盡力滿足其他等級用戶的要求，從而獲得更好的性能。

2 優先級支持策略

FIFO調度除了不能及時響應高優先級請求外，它采用的尾部丟棄策略在隊列已滿時丟棄所有到達的事件。這樣的尾部丟棄策略過于簡單，不進行擁塞避免，也無公平性保證[3]。另一方面，從SEDA模型本身的結構來講，采用基于階段的啟發式控制策略也可能造成對系統整體性能的拖滯，如存在事件在上游階段消耗了大量資源后可能在后面的階段中被拒絕的情況。因此，增加SEDA對優先級應用的支持，需要定義事件的動態優先級，研究優先級事件調度和隊列控制算法。借鑒Internet環境下針對請求高流量和突發性的分組隊列管理思想，在系統內部階段網絡中也可以采用避免擁塞、區分服務的主動隊列管理算法，在隊列達到飽和之前，以一定概率丟棄事件，不同優先級具有不同的丟棄概率，以避免服務質量大幅下降[4]。

本文中定義階段的隊列緩沖區中每個優先級對應一個事件隊列，分別維護隊列中事件的數量;工作線程總是從非空的最高優先級隊列中取出事件;然后，通過請求分級、基于優先級的事件丟棄和優先級升級處理三種策略，實現事件入隊和隊列控制。

2.1 優先級定義

一個服務請求進入系統后，將其封裝為一個事件，并為其設置優先級。事件的優先級分為靜態和動態兩部分，定義如下:

P=Psmtic+Pdynamic(1)

Pdynamic=n+λ(2)

由式(1)(2)可得P=Psmtic+n+λ(3)

其中:Psmtic是請求本身的優先級別;Pdynamic是動態優先級;n表示該事件到達本階段之前，已經對其進行過處理的上游階段數目;λ是優先級變化因子，根據不同的條件對動態優先級進行修正，當事件被階段接收入隊，λ將被置為0。因此事件跨越的階段越多，優先級變化因子越大，其動態優先級就越高。引入事件的動態優先級是為了減少因事件本身的低優先級被丟棄而導致之前對它的處理全部作廢，從而浪費系統資源的情況發生。

2.2 事件分級處理

對服務請求進行區別和分類，是用于Web QoS控制的重要方法[5]。本文采用以請求目標的大小作為優先調度依據的分類方法，可以有效地改善高優先級事件的延遲狀況，同時對低優先級事件影響較小。

將事件按照訪問目標文件的大小劃分為(n+1)級，形如x1

對于到達系統起始階段的服務請求和系統中等待入隊的事件，其優先級變化因子λ根據訪問目標大小取不同的值。若將目標文件大小分為(n+1)級，當xi

2.3 基于優先級的事件丟棄策略

隨機早期檢測算法 (random early detection， RED)是1993年由S.Floyd等人[3]提出的一種基于平均隊列長度的主動隊列管理機制，通過隨機早期丟棄避免網絡擁塞和全局同步現象。雖然RED算法是為改善盡力服務網絡的擁塞控制而提出的，但它及其改進算法還是被廣泛應用于區分服務體系結構中[7]。

本文改進基于優先級的RED算法，通過平均隊列長度和給定的長度閾值計算各等級事件的丟棄概率。算法同時考慮事件的入隊和出隊，因此能更準確地反映隊列長度變化和階段的擁塞情況。算法各參數定義如下:N是優先級的級別數目;Pi(i=0，1，…，N-1)是事件的動態優先級權值，P0

當事件到達階段，根據其優先級計算當前相應優先級隊列長度的加權平均值。其中:Qi(t)應當包含t時刻優先級為i和優先級比i高的隊列中的所有事件數量，即

Qi(t)=Qi(t)+Qi+1(t)+…+QN-1(t)(4)

Qiavg=(1-wq)Qiavg+wqQi(t)(5)

然后計算事件丟棄概率

Pdrop=0Qiavg≤minth(Qiavg-minh)/(maxth-minth)maxp minth≤Qiavg<maxth1 maxth≤Qiavg(6)

由式(6)，當minth≤Qiavg<maxth有

Pidrop=c1Qiavg-c2(7)

由式(4)(5)有

PN-1drop=c1QN-1avg-c2

PN-2drop=c1QN-1avg-c2=PN-1drop+c1wqQN-2(t)

……

P0drop=c1Q0avg-c2=P1drop+c1wqQ0(t)

其中:c1=maxp/(maxth-minth)，c2=maxpminth/(maxth-minth)。因此，各優先級事件之間存在明確的丟棄優先關系，即優先級越低，隊列長度越長，平均隊列長度越大，丟棄的概率越高;反之亦然。

PN-1drop

同時，為合理保持隊列長度，定義調整參數α，每當平均隊列長度更新時動態調整maxp取值[8]。如果平均隊列長度經常超過maxth，說明較多的事件被丟棄，應適當增加maxp，而如果Qiavg經常低于minth，則應減少maxp，這樣，將平均隊列長度維持在一個合理的范圍內，盡量避免溢出或者隊列空閑。調整算法如下:

if(Qiavg≥maxth)(above==5){

above=0;

maxp=maxp*α;

}

if(Qiavg

below=0;

minp=minp/α;

}

基于優先級的事件丟棄算法描述如下:

a)t時刻到達一批事件，檢查事件的動態優先級Pi;

b)根據優先級，由式(4)(5)計算相應的平均隊列長度Qiavg;

c)if minth≤Qiavg<maxth

由式(6)計算丟棄概率Pdrop;

以Pdrop概率丟棄事件;

else if maxth≤Qiavg

丟棄該事件;

d)動態調整最大丟棄概率maxp。

2.4 事件優先級升級處理

由于最高優先級事件總是優先出隊，如果不斷有高優先級事件到達，低優先級事件即使已經進入階段多時，也不能及時得到服務，將出現餓死的情況。為盡量避免這種情況發生，定義事件的優先級提升時間函數tupgrade(Pi)，表示事件在優先級為Pi的隊列中等待了tupgrade(Pi)時間而沒有得到處理[5]，則其優先級將會提升為Pi+1。tupgrade(Pi)的取值根據不同級別事件對目標響應時間的要求來確定。

用Pi(i=0，1，…，N-1)表示優先級，由于事件被準入，λ=0。優先級為Pi的事件首先被放入優先級為Pi的隊列中，當它在隊列中的等待時間超過tupgrade(Pi)時，置λ=1，即事件優先級提高一個級別并入隊到相應Pi+1的隊列中。如果在接下來的tupgrade(Pi+1)時間中，該事件仍未得到處理，置λ=2，并將其入隊到優先級為Pi+2的隊列中，依此類推。如果事件一直沒有得到處理，經過N-1-Pi次提升，它會到達最高優先級N-1的隊列。對于優先級為N-1的隊列中的事件，不存在優先級提升。由于單個優先級隊列中的事件采用的是FIFO調度方式，就保證了事件會在∑N-1itupgrade(Pi)時間內被處理，避免了已進入隊列的低優先級事件被“餓死”。

3 實驗和分析

本文對上述設計實現進行了相關測試。改進原基于SEDA架構的HTTP服務器Haboob，使其增加對帶優先級事件處理的支持，命名新的HTTP服務器為CSOpti，并與Haboob進行性能對比測試。測試環境為:服務器端Intel酷睿2 2.2 GHz CPU，2 GB DDR2內存，Linux 2.6操作系統，軟件為Haboob和CSOpti;用三臺PC機模擬客戶端，向服務器并發靜態網頁請求，每臺客戶端發出的請求帶有一個相應的固定優先級標志，分別為0、1、2，定義數值越大代表的優先級越高;網絡環境為100 Mbps以太網，測試軟件為LoadRunner 8.1。

共設計三組實驗，每臺PC客戶端模擬300個用戶向服務器并發1個靜態網頁請求，每組分別完成5次，取平均值。實驗1測試網頁大小為20 KB，實驗2測試網頁大小為1.1 MB，實驗3中靜態優先級為0的客戶端的請求測試網頁大小為1.1 MB，靜態優先級為1、2的客戶端的請求測試網頁大小為20 KB。算法主要參數為:分級界限值x1=1M，wq=0.02，maxth=280，minth=200，maxp=0.2。實驗采集的數據如表1所示。

實驗結果表明，Haboob對各優先級的請求響應比較平均，而支持區分優先級的CSOpti對高優先級請求的響應優于低優先級。實驗3中高優先級請求的訪問目標也小，優先級服務差別更加明顯。在系統的總體性能上，CSOpti比Haboob略有提高，是因為在高負載環境下，CSOpti通過丟棄一部分請求避免擁塞，并使容易滿足的小文件訪問請求優先得到響應，從而提高了請求服務數量，系統吞吐量得到保證。

4 結束語

本文提出一種對多階段事件驅動模型支持區分優先級服務的改進，通過定義動態優先級，改進了基于優先級的事件入隊丟棄RED算法，并結合請求分級和優先級動態升級策略實現事件入隊、調度控制，使系統既能針對不同等級的請求提供相應質量的服務，又能保持良好的\\擁塞控制、高并發和高吞吐的服務處理性能，從而更符合當前Internet網絡服務應用的要求。

參考文獻:

[1]SHENKER S，PARTRIDGE C，GUERIN R.RFC 2212， Specification of guaranteed quality of service[S].Munich，Germany:Internet Engineering Task Force，1997.

[2]WELSH M，CULLER D， BREWER E.SEDA:an architecture for well-conditioned scalable Internet services[C]//Proc of 18th ACM Symposium on Operating Systems Principles. New York:ACM Press， 2002:230-243.

[3]FLOYD S，JACOBSON V. Random early detection gateways for congestion avoidance[J].IEEE/ACM Trans on Networking，1993，1(4):397-413.

[4]孫麗，王立宏，逯昭義.基于多優先級的動態閾值RED算法[J].計算機工程， 2008，34(9):116-118.

[5]牛春雷，李磊，魏峻.一種面向Web服務的分級服務模型[J].計算機應用研究， 2007，24(9):233-237.

[6]劉進元，廖湘科，譚郁松，等.Keta的Web QoS機制與實現[J].計算機工程與科學，2007，29(2):15-18.

[7]劉明，竇文華，張鶴穎.主動隊列管理研究綜述[J].計算機工程，2006，32(24): 84-86.

[8]FENG W C，KANDLUR D D，SAHA D，et al.A self-configuring RED gateway[C]// Proc of the 18th Annual Joint Conference of the IEEE Computer and Communications Societies. New York:IEEE Communications Society， 1999:1320-1328.