明 利，李 彤,2，秦江龍,2，鄭 明，蔣旭東，謝仲文,2

(1.云南大學 軟件學院，昆明 650500； 2.云南省軟件工程重點實驗室(云南大學)，昆明 650500)

(*通信作者電子郵箱qinjianglong@ynu.edu.cn)

面向軟件即服務的負載均衡策略建模與分析

明 利1，李 彤1,2，秦江龍1,2*，鄭 明1，蔣旭東1，謝仲文1,2

(1.云南大學 軟件學院，昆明 650500； 2.云南省軟件工程重點實驗室(云南大學)，昆明 650500)

(*通信作者電子郵箱qinjianglong@ynu.edu.cn)

為提高軟件即服務(SaaS)應用中資源的訪問效率，提出支持SaaS服務重要特征的負載均衡策略。首先，結合SaaS服務的多租戶和高度可伸縮兩大特性，提出一種基于租戶請求分流、在局部和全局兩個層次伸縮的負載均衡策略；其次，對所提出負載均衡策略用Petri網(wǎng)進行建模并仿真；最后，將提出的負載均衡策略與輪詢(RR)、隨機和改進的最小連接(ILCS)負載均衡算法在總體響應時間和總吞吐量兩方面進行比較。實驗結果表明：在請求速率達到500請求/秒后，所提策略的總體響應時間和總吞吐量趨于穩(wěn)定并優(yōu)于另外三種算法。

軟件即服務;多租戶;可伸縮性;負載均衡;Petri網(wǎng)

0 引言

隨著云計算的深入發(fā)展，軟件即服務(Software as a Service, SaaS)作為一種新的軟件交付方式得到了越來越廣泛的關注。多租戶(multi-tenancy)是SaaS的核心優(yōu)勢之一[1]。隨著業(yè)務的發(fā)展及用戶訪問量的急速增長，SaaS應用必須支持可擴展性，這樣才能有效利用系統(tǒng)資源[2]。

在云計算中，負載均衡是一項優(yōu)化技術，是一種在服務器之間均衡地分配大量的請求的機制[3]，是支持SaaS應用高效分配海量請求的關鍵技術。它被用于提高資源利用率、減少延遲、縮短響應時間、提高系統(tǒng)整體性能。

文獻[4]為了達到SaaS服務提供商的目標——利益最大化及客戶滿意度，提出了一種性價比較高的映射和調(diào)度策略，用一臺虛擬機優(yōu)化資源分配，同時也將服務質(zhì)量(Quality of Service, QoS)參數(shù)、由不同類型的虛擬機造成的基礎設施異質(zhì)性及不同的服務初始時間考慮在內(nèi)。文獻[5]提出了一種面向租約功能類型的服務器負載模型和面向租約用戶非功能需求的執(zhí)行請求按需分配算法，在此基礎上實現(xiàn)了一個面向多租約SaaS應用的負載均衡系統(tǒng)。文獻[6]提出了改進的最小連接數(shù)算法，當檢測到需要將某客戶端連接進行重定向時，將此重定向連接到當前連接數(shù)最少的服務器，但是連接數(shù)最少的服務器并不一定是負載最小，所以此算法只在一定程度上實現(xiàn)了服務器之間的負載均衡問題。同樣文獻[7]也提出了一種改進的最小連接負載均衡調(diào)度算法，主要方法是實時地計算所有服務器的負載率并更新排序，當服務器超過最大負載率的時候向用戶反饋錯誤信息并停止服務。文獻[8]提出了臨界加速遞減請求分配策略，通過動態(tài)監(jiān)測請求任務被分配后對各個服務器工作負荷造成的影響、服務器實際的工作負載狀態(tài)的反饋及設定的服務器固有處理能力進行請求分配。文獻[9]提出的一種基于隨機理論調(diào)度模型將SaaS層描述成一種多目標的優(yōu)化問題。為了提高整體性能，映射規(guī)則分析器主要負責將任務分配到合適的服務副本，彈性控制器負責云服務的彈性分配，降低了請求的積壓量。文獻[10]提出了改進的節(jié)流算法并用云端模擬器分析了其性能。文獻[11]使用了主動監(jiān)控和資源感知相結合的算法，對于每一個到來的請求都給予有效分配并將總體請求時間最小化。文獻[3，12]的主要工作是對現(xiàn)存的啟發(fā)式負載均衡算法(比如Min-Min算法[13])進行分類并在吞吐量、遷移時間、容錯性等方面進行了對比研究，并且文獻[3]對現(xiàn)有的蜜蜂覓食算法進行了擴展。

以上文獻中提出的算法均從不同方面實現(xiàn)了負載均衡，但是到目前為止，專門針對云計算下的SaaS軟件，并能體現(xiàn)其核心特征(如多租戶、高度可伸縮性等)的負載均衡策略尚屬鮮見。

SaaS環(huán)境下，一方面，一個應用往往供多個租戶(租戶往往是一個單位或組織)同時使用，一個租戶下又擁有數(shù)量眾多的用戶，數(shù)量龐大的用戶發(fā)出海量的請求；另一方面，SaaS作為云計算服務棧中離用戶最近的一層，其背后有高度可伸縮的云資源的有力支持。在此背景下，如何提高SaaS軟件響應海量請求的效率、如何充分利用云計算的高度可伸縮特征成為一個重要課題，如何設計負載均衡策略使之更好地發(fā)揮作用成為一個關鍵問題。

針對上述問題，本文立足SaaS的核心特征，提出一種基于租戶請求分流、在局部和全局兩個層次伸縮的面向SaaS服務的負載均衡策略，并以Petri網(wǎng)為形式化工具對策略進行建模分析。

1 本文思路

根據(jù)歷史監(jiān)測，業(yè)務負載通常表現(xiàn)趨勢性、周期性和隨機性，如果當系統(tǒng)在一年的某個特定時間內(nèi)遇到大量并發(fā)請求，負載達到峰值，其性能會降低，這時若沒有適當?shù)脑黾酉到y(tǒng)的負載能力，系統(tǒng)的響應時間會變長，業(yè)務的失效率也會增加，從而導致客戶滿意度下降[14]，并且考慮到現(xiàn)有文獻[4-13]中關于負載均衡研究的主要思路，鮮有結合SaaS服務特征的策略，所以本文的策略緊扣SaaS服務的多租戶特征和云計算的高度可伸縮性特征，思路如下。

1)針對SaaS的多租戶特性?？紤]到一個SaaS應用往往供多個租戶同時使用，一個租戶下又擁有數(shù)量眾多的用戶，數(shù)量龐大的用戶發(fā)出海量的請求。進一步，在SaaS環(huán)境下，不同的租戶往往處于不同的物理位置，對于部分SaaS應用而言，不同的租戶甚至分布于不同的國家、區(qū)域。另一方面，支撐SaaS應用的云計算技術使得響應海量請求的物理服務器也分布于不同的地理位置(每個不同地理位置的服務器集群是一個相對于全局的局部)。在此背景下，理想的情況是：發(fā)出的請求能在負載均衡機制的支持下，在網(wǎng)絡通信代價較低的服務器上計算和響應，同時又不顯著降低負載均衡器分發(fā)請求的效率。傳統(tǒng)的通過動態(tài)監(jiān)測服務器工作負荷的負載均衡策略顯然無法滿足要求，在SaaS環(huán)境下，本文提出基于租戶請求分流的策略：首先根據(jù)網(wǎng)絡通信代價、各個局部服務器集群的資源多少等因素建立不同租戶與各個局部服務器集群之間的較優(yōu)映射關系，然后根據(jù)不同請求所屬的用戶所在的租戶，將請求分流到與該租戶對應的局部服務器集群。

2)針對云計算的高度可伸縮性特性。SaaS作為云計算服務棧中離用戶最近的一層，其背后有高度可伸縮的云資源的有力支持。云計算一個重要的特征和優(yōu)點是：資源的高度可伸縮性，對資源的需求可以根據(jù)應用的需求動態(tài)地增加或減少。在此背景下，理想的情況是：在基于租戶請求分流的策略的實施下，各個局部服務器集群都能高效地完成計算并響應，當某個局部服務器集群資源不夠而導致響應時間過長時，可動態(tài)增加資源；當某個局部服務器集群資源過剩時，可動態(tài)縮減資源。但由于云計算看似源源不斷的資源其本質(zhì)來源于虛擬化技術[15]，因此受制于實際物理服務器的多少。因此，本文提出在局部和全局兩個層次伸縮的策略：依據(jù)負載情況和擁有資源的實際情況，在局部(SaaS應用位于某個地區(qū)或?qū)ｉT服務于某些租戶的分部服務器集群)和全局(SaaS應用的總部服務器集群)兩個層次進行伸縮。首先，當檢測到與請求匹配的局部服務器集群負載過重時，在局部環(huán)境增加資源，即“局部伸”以提高請求的響應速度；其次，雖然云在理論上是“資源無限”的，但畢竟受限于實際的物理資源，因此策略還增加了“全局伸縮”，當某個局部環(huán)境的物理資源無法滿足要求時，將任務請求分配到某個資源充足的全局服務器上，即“全局伸”；反之，當檢測到某個服務器集群資源過剩時，釋放部分資源，即“局部縮”和“全局縮”。

2 面向SaaS服務的負載均衡策略分析

文獻[16]中提到了SaaS應用的成熟度模型。SaaS應用的成熟度模型分為四級，其中在第四級中，為了更好地提高服務器集群的吞吐率并且降低響應延遲，在第三級的基礎上增加了負載均衡機制，使系統(tǒng)更好地實現(xiàn)了可擴展性。

從架構層面分析，SaaS區(qū)別于傳統(tǒng)技術主要表現(xiàn)在多租戶模式和可伸縮性[17]。本文主要從SaaS服務具有的特性：多租戶和可伸縮兩方面著手，根據(jù)SaaS服務這兩大優(yōu)勢，將不同租戶發(fā)來的任務按一定的規(guī)則進行分配。具體過程如以下步驟所示。

1)通過多租戶特征處理多租戶的請求。

①將不同租戶與各個服務器集群之間建立起較優(yōu)的映射關系。

a)首先根據(jù)租戶ID判斷其物理位置：當有來自多個租戶發(fā)來的多種請求時，首先根據(jù)租戶ID判斷其物理位置，因為SaaS軟件的物理服務器集群也分布于不同的地理位置，所以將物理位置一樣的租戶的請求分配給物理上距其最近的SaaS軟件的物理服務器集群，這樣租戶與執(zhí)行請求的服務器集群之間可以建立起優(yōu)化的關聯(lián)關系，減少網(wǎng)絡通信代價。

b)其次將同一物理位置的租戶的請求進行分類：使用聚類的方法計算租戶請求的相似度值，并設定一個閾值，如果相似度值小于已設定的閾值，則可以將這些租戶的請求分配給與租戶請求匹配程度最高的服務器集群。假設來自A…N的同一物理位置的租戶的請求集合分別為X…Z,則相似度值μ=(X∩Y∩…∩Z)/(X∪Y∪…∪Z)。

c)計算服務器集群的當前負載狀況：當前等待隊列中的請求數(shù)量與服務器處理請求的速率的比值。

②建立起映射關系以后，按照服務器集群的當前負載狀況(如果服務器集群處于正常負載水平，即還沒到達瓶頸期)，并根據(jù)不同請求所屬的用戶所在的租戶及其請求的相似度，將請求分流到與該租戶對應的服務器集群。

2)利用SaaS軟件的可伸縮性處理多租戶的請求。

①如果與租戶請求匹配程度最高的服務器集群達到瓶頸期，則利用SaaS的高可伸縮性這一優(yōu)勢先進行“局部擴展”——在局部環(huán)境增加用于處理租戶請求的服務器(局部備用服務器)，如果局部有備用服務器處于正常負載能力范圍內(nèi)甚至是空閑，則利用局部備用服務器進行請求處理以縮短響應時間。

②雖然云資源在理論上是無限的，然而其受制于實際的物理資源，所以如果局部范圍內(nèi)沒有可利用的服務器資源或者已被占用，則要在全局環(huán)境增加用于處理租戶請求的服務器(全局備用服務器)，進行“全局擴展”，如果全局環(huán)境有處于正常負載范圍內(nèi)的甚至是空閑的服務器，則放入此服務器的等待隊列中。

③如果局部及全局服務器目前都已不具備處理請求的能力，資源不足，則多租戶的請求暫停處理，直到有服務器可以處理請求為止。

本文中2)提到的局部擴展及全局擴展體現(xiàn)了云計算的核心特征之一——可伸縮性中的“伸”這一特性。

圖1為多租戶的請求處理方法的活動圖。

圖1 多租戶請求處理活動圖

當然，局部和全局的服務器不可能永遠處于滿載的狀態(tài)，當負載過低又被租戶占用時，需要對服務器進行釋放——即“局部縮”和“全局縮”，以便下次方便服務，所以進行資源回收并更好地處理已經(jīng)分配出去的服務器是必要的。同時，資源回收要根據(jù)實際情況選擇性能較好的回收策略，否則回收程度過大或者過小都會產(chǎn)生不良影響[18]。這恰恰體現(xiàn)了云計算的核心特征之一——可伸縮性中的“縮”這一特性。

3 基于隨機Petri網(wǎng)的調(diào)度策略分析

3.1 基于Petri網(wǎng)的建模思路

本文基于圖1對所提出的調(diào)度策略進行Petri網(wǎng)建模，建模思路如下：1)選用隨機Petri網(wǎng)(StochasticPetriNet,SPN)作為建模的主要形式化工具。Petri網(wǎng)具有直觀的圖形表示，又具有嚴格的數(shù)學基礎，而隨機Petri網(wǎng)是通過給P/T網(wǎng)的每個變遷相關聯(lián)一個實施速率得到的模型。大多數(shù)隨機Petri網(wǎng)的性能分析是建立在其狀態(tài)空間與馬爾可夫鏈同構的基礎上的。2)通過引入隨機Petri中的時間變遷和瞬時變遷，可以將請求進行確定性地分發(fā)，而基本Petri網(wǎng)中的分發(fā)都是非確定性的。

3.2 相關定義

關于Petri網(wǎng)和隨機Petri網(wǎng)的基本知識，這里只引用和本文相關的幾個概念，其他的可以參考文獻[19-21]。

定義1 三元組N=(S,T;F)為一個Petri網(wǎng)的充分必要條件是：

1)S∪T≠?;

2)S∩T=?;

3)F?(S×T)×(T×S);

其中：S是N的庫所有限集；T是N的變遷有限集；F是N的有向弧集，稱為N的流關系。

定義2 連續(xù)時間SPN=(S,T;F,W,M0，λ)。其中(S,T;F,W,M0)是一個P/T系統(tǒng)，變遷平均實施速率的集合為λ=(λ1，λ2，…,λn)。λi是變遷ti∈T的平均實施速率，表示在可實施的情況下單位時間內(nèi)平均實施次數(shù)，單位是次數(shù)/單位時間。特別地，有時實施速率可能依賴于標識，是標識的函數(shù)。

要對系統(tǒng)性能進行分析，首先使用隨機Petri網(wǎng)構造出系統(tǒng)模型，然后同構出該模型的馬爾可夫鏈(Markov Chain， MC)，最后在基于MC的穩(wěn)定狀態(tài)概率下得到所要分析的系統(tǒng)性能指標。在求得穩(wěn)態(tài)概率的基礎上，可進一步分析一些性能指標。

1)庫所中的平均token數(shù)，它可以看作是租戶請求的隊列長度，可利用此數(shù)值估算設備或者資源的利用率等：

(1)

2)token概率密度函數(shù):

(2)

其中Mj∈[M0?且Mj(s)=i。

3.3 基于多租戶和可伸縮的負載均衡SPN模型

圖2為基于多租戶和可伸縮的SPN模型。在圖2中，白色長方形表示時間變遷，黑色長方形表示瞬時變遷，白色圓圈表示隨機Petri網(wǎng)中的庫所，庫所中的黑色圓點代表token，token的數(shù)量指請求的隊列長度，實線框1和框2表示局部備用服務器集群，虛線框1和框2表示全局備用服務器集群，根據(jù)云的特點，其中局部備用服務器和全局備用服務器都為n臺，受篇幅影響，本文在圖2的基于多租戶和可伸縮的負載均衡SPN模型中的備用服務器集群只分別畫出兩臺，其他備用服務器集群用省略號表示。

首先對此模型作如下約定：1)所有服務器集群，即處理請求的變遷si，ri，mi，它們的處理速率是獨立指數(shù)分布的；2)租戶的請求不分優(yōu)先級，即請求獲得處理的概率是相等的；3)任一類租戶請求的到達為泊松過程，一個到來的請求可以根據(jù)租戶的特征將其分配給服務器集群中處理此類請求的服務器，當請求隊列已滿，則拒絕接收任何新到來的請求；4)1≤i≤n。

為不失一般性，假設租戶可以分為z類，服務器集群數(shù)為n。下面對圖2中各個庫所及變遷的具體意義進行詳細說明：

1)T1表示不同租戶請求的到達，其平均到達速率為λi。考慮到SaaS租戶往往來自于不同的物理位置，并具有不同的特征，與此同時，SaaS應用的物理服務器集群往往也分布于不同的地理位置；因此，當不同特征租戶的請求到達的時候，變遷T1執(zhí)行并由x1進行分配，這樣經(jīng)租戶ID和特征分類過的多租戶請求能夠在較短時間內(nèi)得到處理，由此能夠在很大程度上為租戶和執(zhí)行請求的服務器集群之間建立起優(yōu)化的關聯(lián)關系，減少響應時間。

2)x1表示由變遷T1執(zhí)行后到來的租戶請求進行分配的庫所，它根據(jù)變遷ti所關聯(lián)的可實施謂詞及實施概率來決定將租戶請求放入哪個隊列。

3)ti表示對庫所x1中的所有租戶請求進行分配的變遷。

4)fi表示接收經(jīng)過分類后的請求的庫所，它根據(jù)變遷ei和wi所關聯(lián)的可實施謂詞及實施概率來決定將租戶請求放入到fi的某一個隊列中，設其容量為f_buffi。

5)ei和wi表示對已經(jīng)分類好的請求的分配變遷，以決定是將請求放入與租戶請求匹配程度最高的服務器集群(亦或是局部服務器集群)進行處理還是放入全局服務器集群。

6)pi表示將用局部服務器集群處理的請求的緩沖隊列，設其容量為p_buffi。

7)di指的是如果ri服務器處于正常負載水平，則通過di的執(zhí)行將pi中已有的租戶請求放入此類服務器的緩沖隊列ai。

8)ai表示與租戶請求匹配程度最高的服務器集群的緩沖隊列，設其容量為a_buffi。

9)bi表示局部備用服務器集群的緩沖隊列，如果pi中請求較多，并且ri吞吐量變低，則通過oi的執(zhí)行將請求放入其中，設其容量為b_buffi。

10)ri表示局部環(huán)境下可以在正常負載水平下處理租戶請求的服務器集群，其平均處理速率為r_vi。

11)si表示在局部環(huán)境下將對租戶請求進行處理的變遷，即局部備用服務器集群，其平均處理速率為s_vi。

12)ki表示全局環(huán)境下的緩沖隊列，設其容量為k_buffi。

13)ii表示為全局范圍內(nèi)可以為租戶請求提供的資源，資源數(shù)為1。

14)mi表示為SaaS服務供應商提供的全局環(huán)境下的備用服務器集群，其平均出處理速率為m_vi。

15)c1表示租戶請求處理結束，設其容量為c_buffi。

16)g1的含義：g1點火后將會把c1中的token釋放掉，防止c1中的token數(shù)量超過其容量。

為了更加具體地說明本文提出的策略模型是如何執(zhí)行的，下面給出執(zhí)行過程的偽代碼(如圖2所示)：

輸入：多租戶請求到達的速率、變遷(服務器集群)ri,si,mi的平均處理速率及服務器隊列長度閾值。

輸出：庫所ai,bi,ki中的平均token數(shù)(隊列長度)及變遷si,ri,mi吞吐量。

為了保證基于多租戶和可伸縮的負載均衡SPN模型在仿真過程中能成功執(zhí)行完所有租戶請求，將庫所c1與變遷T1相連，箭頭指向T1，其中在c1中設置服務器隊列長度閾值16，同時將g1刪除，這樣可以構成一個循環(huán)網(wǎng)，只有當服務器隊列中的所有租戶請求被執(zhí)行完成后才終止。

步驟1 變遷T1點火，多租戶的請求到達在x1；

步驟2 經(jīng)過判斷租戶的ID，識別出其所在物理位置，根據(jù)物理位置將請求分別分發(fā)到指定的庫所fi；

步驟3 到達fi之后判斷與租戶請求匹配度最高的服務器集群緩沖隊列ai中的平均token數(shù)是否小于bi和ki中的數(shù)量；

步驟4 if (N(ai)

與ai對應的服務器集群ri處理租戶請求；

步驟5 if (N(bi)

與bi對應的服務器集群si處理租戶請求；

步驟6 if (N(ki)

與ki對應的服務器集群mi處理租戶請求；

步驟7 繼續(xù)執(zhí)行步驟2～6，直至所有請求被處理完畢。

3.4 基于多租戶和可伸縮的負載均衡調(diào)度策略性能指標描述

基于多租戶和可伸縮的負載均衡SPN模型的性能可由圖2中的ti，ei，wi，oi，di的可實施謂詞及實施概率進行描述。

1)變遷ti的可實施謂詞為：根據(jù)第2章中的相似度值μ可知：

Y(ti)：?i,1≤i≤n, (M(fi)

變遷ti的實施概率為：

2)變遷ei的可實施謂詞為：

Y(ei):?i,1≤i≤n,M(pi)

變遷ei的實施概率為：

3)變遷wi的可實施謂詞為：

Y(wi):?i,1≤i≤n, (M(ki)p_buffi)

變遷wi的實施概率為：

4)變遷di的可實施謂詞為：

Y(di):?i,1≤i≤n,M(ai)

變遷di的實施概率為：

5)變遷oi的可實施謂詞為：

Y(oi):?i,1≤i≤n, (M(ai)>a_buffi)∧ (M(bi)

變遷oi的實施概率為：

圖2 基于多租戶和可伸縮的負載均衡SPN模型

4 實驗仿真和分析

4.1 實驗環(huán)境、參數(shù)設置及實施方案說明

仿真程序使用JDK1.8.0_45和隨機Petri網(wǎng)建模工具SPNP[20]開發(fā)，運行在一臺CPU為IntelCorei7，主頻為3.40GHz，4GB內(nèi)存的PC上。

為了簡化模型的求解，模型中參數(shù)的設置參考文獻[20]中的方法，服務器隊列長度閾值為16(經(jīng)實驗表明，當隊列長度閾值超過16，則會出現(xiàn)狀態(tài)空間爆炸)，變遷si,ri,mi的平均處理速率均設為3.0，多租戶請求T1到達的速率設為9個值，分別為5.0，10.0，30.0，50.0，80.0，100.0，500.0，1 000.0，3 000.0。

實施方案：本文主要是對提出的負載均衡策略與輪詢(RoundRobin,RR)算法、隨機算法和文獻[11]中提出的改進的最小連接(ImprovedLeast-ConnectionScheduling,ILCS)算法的總體響應時間和總吞吐量進行對比，對于這四種算法的數(shù)據(jù)獲得過程，都是用SPNP軟件首先對其進行建模，其次用C語言代碼進行實現(xiàn)，并求得庫所的平均token數(shù)及時間變遷的吞吐量，其會隨著請求到達速率的變化而變化。進而利用這些數(shù)據(jù)，根據(jù)4.2節(jié)中的公式求得四種調(diào)度策略的總體響應時間及總吞吐量。

本文策略所采用的模型如圖2所示，執(zhí)行過程如3.3節(jié)中的偽碼所示，由于篇幅限制，另外三種算法的模型不再畫出。對另外三種算法建模的時候，在同樣的實驗環(huán)境下采取了與本文相同的時間變遷數(shù)量、平均處理速率、多租戶請求達到的速率和隊列長度閾值，用C語言代碼對變遷的點火進行控制，且C代碼的實現(xiàn)是按照這三種算法的思想具體實現(xiàn)。

4.2 模型評價標準

在一般的SPN模型中，性能指標可以通過模型的穩(wěn)定狀態(tài)概率求得。系統(tǒng)設計者在研究一種新的調(diào)度策略的時候，一定要考慮到一系列因素，比如系統(tǒng)類型和用戶需求等，根據(jù)系統(tǒng)的類型，用戶和設計者一定希望調(diào)度策略可以達到以下目標：吞吐量最大化、避免無限推遲甚至饑餓現(xiàn)象、響應時間和利用率之間達到一個平衡等[22]。在本文中，通過分析基于多租戶和可伸縮性的負載均衡SPN模型的總體響應時間和吞吐量來評價系統(tǒng)的性能。總體響應時間和吞吐量可以分別表示如下。

1)令P[M]為情態(tài)M的穩(wěn)態(tài)概率，則在穩(wěn)態(tài)下變遷t的吞吐量可以表示為：

(3)

其中：E是使變遷t能夠點火的所有情態(tài)集，u為變遷t的實施速率，u取不同的值時則吞吐量不同。

2)根據(jù)圖2的SPN模型可以得知其總吞吐量TH為：

(4)

其中：TH(t)在式(3)中求出，表示穩(wěn)態(tài)下變遷t的吞吐量，在本文中，t指si,ri,mi(1≤i≤n)。

3)圖2的SPN模型總體響應時間RT為：

4.3 結果與分析

為了驗證基于多租戶和可伸縮性的負載均衡策略的可行性，進行了一組仿真實驗，將此策略與RR、隨機調(diào)度算法及ILCS算法進行性能比較。

表1和表2分別是在穩(wěn)態(tài)概率下SPN模型中庫所的平均token數(shù)及時間變遷的吞吐量。由表1和表2可知，當請求速率(每秒請求到達數(shù))持續(xù)增大的時候，本文策略的SPN模型中的庫所的平均token數(shù)及時間變遷的吞吐量越來越大，但是當請求速率增大到一定程度時候，其保持基本平衡，這說明本文策略的穩(wěn)定性較好，當租戶的請求源源不斷的到來的時候先局部后全局的策略仍然可以保證請求被處理。關于RR算法、隨機調(diào)度算法和ILCS算法得到的庫所平均token數(shù)及時間變遷的吞吐量，在此只列出其總體響應時間和總吞吐量數(shù)據(jù)，如表3所示。

為了更加直觀，圖3和圖4表現(xiàn)出了四種調(diào)度策略在請求速率不斷增大的情況下的總體響應時間和總吞吐量。

表1 穩(wěn)態(tài)概率下SPN模型中的平均token數(shù)

表2 穩(wěn)態(tài)概率下SPN模型中的服務器總吞吐量

表3 四種算法的總體響應時間和總吞吐量對比結果

圖3是實施四種調(diào)度策略時隨著請求速率增加其總吞吐量變化的曲線。從圖3中可以看出，隨著請求速率的持續(xù)增加，四種調(diào)度策略的總吞吐量都在增加，但是請求速率達到30請求/s時，本文調(diào)度策略的吞吐量達到基本平衡，即請求速率即使再不斷增大，其吞吐量呈小幅度上升，當請求速率達到500請求/s時，其吞吐量基本保持不變；然而當請求速率達到100請求/s時，RR算法和隨機算法的吞吐量大幅度下降，因為這兩種算法都沒有考慮到服務器當前的連接數(shù)，進而導致其吞吐量不穩(wěn)定，服務器間的負載不均衡；ILCS算法的總吞吐量在請求速率達到100請求/s之前呈上升趨勢，略高于本文策略的吞吐量，但是在100請求/s之后開始呈小幅度下降趨勢，略低于本文策略的吞吐量，因為ILCS算法定時地評估各個服務器的負載狀態(tài)，處理性能極值等，同時還評估新請求的歸一化負載率，整體來說，ILCS算法與本文的策略的性能相差較小，在請求速率達到1 000請求/s后幾近重合。

圖4為四種調(diào)度策略的總體響應時間對比。由圖4可知，隨著請求速率的持續(xù)增加，本文調(diào)度策略的響應時間在增加，當請求速率達到500請求/s時，系統(tǒng)的響應時間趨于穩(wěn)定，即請求速率即使再不斷增大，其響應時間基本保持不變，因為本文策略可以對租戶請求進行更合理的分配，當負載持續(xù)增加的時候，可以進行局部伸縮甚至是全局伸縮，并且可以保證租戶的請求總是能被處理而不至于擁塞過度，從而使整體負載水平保持平衡，體現(xiàn)出了SaaS的優(yōu)勢；而隨著請求速率的不斷增加，RR調(diào)度算法和隨機調(diào)度算法的總體響應時間急劇上升，因為在這種情況下，系統(tǒng)的處理能力逐漸達到飽和而引起更多的租戶請求得不到處理進而導致請求積壓和總體響應時間增加；ILCS算法的總體響應時間略高于本文策略的總體響應時間，又優(yōu)于RR和隨機算法的總體響應時間，但是其波動稍大，穩(wěn)定性較差。

圖3 四種調(diào)度策略的總吞吐量對比

圖4 四種調(diào)度策略的總體響應時間對比

因此從以上分析可以得知，從整體上來說，本文提出的調(diào)度策略性能較優(yōu)于RR調(diào)度算法、隨機調(diào)度算法和ILCS算法。

5 結語

隨著云計算的深入發(fā)展，SaaS必然作為一種新的軟件交付方式成為時代的潮流，并且借助負載均衡機制支持更多的租戶并實現(xiàn)更好的可擴展性。本文介紹了一種基于隨機Petri網(wǎng)的面向SaaS服務的負載均衡機制，實現(xiàn)了針對多租戶和可伸縮性的負載均衡策略，在一定程度上提高了資源利用率并降低了系統(tǒng)開銷，縮短了執(zhí)行時間，并且避免了傳統(tǒng)的負載均衡機制的不足。同時與輪詢調(diào)度、隨機調(diào)度和ILCS算法進行比較，結果表明，本文提出的算法的整體性能較好。如何在提高效率的同時也提高服務質(zhì)量，降低拒絕概率，并且對模型進行精化與分解將是下一步研究課題的重點，同時將對負載類型分類并在SaaS平臺上進行模擬實驗。

)

[1] 白海石.WindowsAzure實戰(zhàn)[M].北京：機械工業(yè)出版社,2014:4-80.(BAIHS.WindowsAzureinAction[M].Beijing:ChinaMachinePress, 2014:4-80.)

[2]GUOCJ,SUNW,HUANGY,etal.Aframeworkfornativemulti-tenancyapplicationdevelopmentandmanagement[C]//CEC2007:Proceedingsofthe9thIEEEInternationalConferenceonE-CommerceTechnology.Washington,DC:IEEEComputerSociety, 2007: 551-558.

[3]PATHAKKK,YADAVPS,TIWARIR,etal.Amodifiedapproachforloadbalancingincloudcomputingusingextendedhoneybeealgorithm[J].InternationalJournalofResearchReviewinEngineeringScienceandTechnology, 2012, 3(1): 12-19.

[4]WUL,GARGSK,BUYYAR.SLA-basedresourceallocationforSoftwareasaServiceprovider(SaaS)incloudcomputingenvironments[C]//Proceedingsofthe2011 11thIEEE/ACMInternationalSymposiumonCluster,CloudandGridComputing.Washington,DC:IEEEComputerSociety, 2011: 195-204.

[5] 汪德帥，張一川，張斌,等.面向多租約SaaS應用的負載均衡機制研究與實現(xiàn)[J].小型微型計算機系統(tǒng),2012,33(1):71-77.(WANGDS,ZHANGYC,ZHANGB,etal.Researchandimplementationofloadbalancingmechanismformulti-tenantSaaSapplication[J].JournalofChineseComputerSystems, 2012, 33(1): 71-77.)

[6]AVERSAL,BESTAVROSA.LoadbalancingaclusterofWebservers:usingdistributedpacketrewriting[C]//IPCCC’ 00:Proceedingsofthe2000IEEEInternationalConferenceonPerformance,Computing,andCommunications.Piscataway,NJ:IEEE, 2000: 24-29.

[7] 陳燕升,張贊波,任江濤.改進的最小鏈接負載均衡調(diào)度算法[J].計算機系統(tǒng)應用,2015,24(7):88-92.(CHENYS,ZHANGZB,RENJT.Improvedminimumlinkloadbalancingschedulingalgorithm[J].ComputerSystems&Applications, 2015, 24(7): 88-92.)

[8] 郭成城,晏蒲柳.一種異構Web服務器集群動態(tài)負載均衡算法[J].計算機學報,2005,28(2):179-184.(GUOCC,YANPL.Adynamicload-balancingalgorithmforheterogeneousWebservercluster[J].ChineseJournalofComputers, 2005, 28(2): 179-184.)

[9] 趙少卡,李立耀,徐聰,等.基于SaaS的彈性云平臺優(yōu)化調(diào)度策略設計[J].計算機應用研究,2014,31(2):422-425.(ZHAOSK,LILY,XUC,etal.ElasticcloudplatformoptimalschedulingstrategydesignbasedonSaaS[J].ApplicationResearchofComputers, 2014, 31(2): 422-425.)

[10]DOMANALSG,REDDYGRM.Loadbalancingincloudcomputingusingmodifiedthrottledalgorithm[C]//Proceedingsofthe2013IEEEInternationalConferenceonCloudComputinginEmergingMarkets.Piscataway,NJ:IEEE, 2013: 1-5.

[11]RATHORER,SHARMAV,GOLAKK.Anewapproachforloadbalancingincloudcomputing[J].InternationalJournalofEngineeringandComputerScience, 2014, 2(5): 1636-1640.

[12]MEHMOODM,SATTARK,KHANAH,etal.Loadbalancingapproachincloudcomputing[J].JournalofInformationTechnology&SoftwareEngineering, 2015, 5(3): 100153.

[13]KOKILAVANIT,AMALARETHINAMDIG.Loadbalancedmin-minalgorithmforstaticmeta-taskschedulingingridcomputing[J].InternationalJournalofComputerApplications, 2011, 20(2): 43-49.

[14] 熊偉,李兵,陳軍,等.一種基于預測控制的SaaS系統(tǒng)自適應方法[J].計算機學報,2016,39(2):364-376.(XIONGW,LIB,CHENJ,etal.Aself-adaptionapproachbasedonpredictivecontrolforSaaS[J].ChineseJournalofComputers, 2016, 39(2): 364-376.)

[15] 牟權,葉保留,陸桑璐.基于云計算的普適服務集成平臺技術研究[EB/OL].[2016-03-15].http://www.itfront.cn/attachment.aspx?attachmentid=3072.(MOUQ,YEBL,LUSL.Atechnologyresearchofpervasiveserviceintegrationplatformbasedoncloudcomputing[EB/OL].[2016-03-15].http://www.itfront.cn/attachment.aspx?attachmentid=3072.)

[16] 葉偉.互聯(lián)網(wǎng)時代的軟件革命:SaaS架構設計[M].北京:電子工業(yè)出版社,2009:32-47.(YEW.TheSoftwareEvolutionoftheInternetAge:SaaSArchitectureDesign[M].Beijing:PublishingHouseofElectronicsIndustry, 2009: 32-47.).

[17]TSAIWT,BAIXY,HUANGY.Software-as-a-Service(SaaS):perspectivesandchallenges[J].ScienceChinaInformationSciences, 2014, 57(5): 1-15.

[18] 杜垚,郭濤,陳俊杰.云環(huán)境下機群彈性負載均衡機制[J].計算機應用,2013,33(3):830-833.(DUY,GUOT,CHENJJ.Fleetelasticloadbalancingmechanismincloudenvironment[J].JournalofComputerApplications, 2013, 33(3): 830-833.)

[19] 吳哲輝.Petri網(wǎng)導論[M].北京：機械工業(yè)出版社,2006:1-65.(WUZH.IntroductionofPetriNet[M].Beijing:ChinaMachinePress, 2006:1-65.)

[20] 林闖.隨機PETRI網(wǎng)和系統(tǒng)性能評介[M].2版.北京：清華大學出版社,2005:19-62.(LINC.StochasticPetriNetandPerformanceEvaluationofSystems[M].2nded.Beijing:TsinghuaUniversityPress, 2005: 19-62.)

[21] 李彤.軟件并行開發(fā)過程[M].北京：科學出版社,2003:11-15.(LIT.ConcurrentDevelopmentProcessesofSoftware[M].Beijing:SciencePress, 2003: 11-15.)

[22]SINGHA,GOYALP,BATRAS.AnoptimizedroundrobinschedulingalgorithmforCPUscheduling[J].InternationalJournalonComputerScience&Engineering, 2010, 2(7): 2383-2385.

ThisworkispartiallysupportedbytheNaturalScienceFoundationofChina(61379032, 61262024, 61462092),theScienceandTechnologyProgramofScientificResearchFoundationinEducationDepartmentofYunnanProvince(2014Y12).

MING Li, born in 1989, M.S.candidate.Her research interests include software dynamic evolution, cloud computing.

LI Tong, born in 1963, Ph.D., professor.His research interests include software engineering, software process.

QIN Jianglong, born in 1984, Ph.D., lecturer.His research interests include software process, software evolution.

ZHENG Ming, born in 1992, M.S.candidate.His research interests include software evolution, cloud computing.

JIANG Xudong, born in 1986, M.S.candidate.His research interests include software evolution, software process.

XIE Zhongwen, born in 1982, Ph.D., lecturer.His research interests include software dynamic evolution, cloud computing, software process.

SaaS-oriented modeling and analysis of load balancing strategy

MING Li1, LI Tong1,2, QIN Jianglong1,2*, ZHENG Ming1, JIANG Xudong1, XIE Zhongwen1,2

(1.SchoolofSoftware,YunnanUniversity,KunmingYunnan650500,China;2.KeyLaboratoryinSoftwareEngineeringofYunnanProvince(YunnanUniversity),KunmingYunnan650500,China)

To improve the efficiency of resource access in Software as a Service (SaaS) applications, a load balancing strategy combined with the important features of SaaS service was proposed.Firstly, the load balancing strategy was proposed by combining multi-tenancy and high scalability in SaaS service based on the distribution of request and global and local scalability.Secondly, the load balancing strategy model was constructed and simulated by a Petri net.Finally, this strategy was compared with Round Robin (RR), stochastic algorithm and Improved Least-Connection Scheduling (ILCS) load balancing algorithm in response time and throughput.The experimental results show that the response time and throughput of the proposed strategy become stable and they are superior to the other three algorithms after the request rate reaches 500 per second.

Software as a Service (SaaS); multi-tenancy; scalability; load balancing; Petri net

2016-07-18;

2016-08-14。

國家自然科學基金資助項目(61379032, 61262024, 61462092)；云南省教育廳科學研究基金理(工)科資助項目(2014Y012)。

明利(1989—)，女，河南安陽人，碩士研究生，主要研究方向：軟件動態(tài)演化、云計算； 李彤(1963—)，男，河北石家莊人，教授，博士生導師，博士，CCF會員，主要研究方向：軟件工程、軟件過程； 秦江龍(1984—)，男，云南安寧人，講師，博士，CCF會員，主要研究方向：軟件過程、軟件演化； 鄭明(1992—)，男，安徽安慶人，碩士研究生，主要研究方向：軟件演化、云計算； 蔣旭東(1986—)，男，湖南邵陽人，碩士研究生，主要研究方向：軟件演化、軟件過程； 謝仲文(1982—)，男，福建漳州人，講師，博士，CCF會員，主要研究方向：軟件動態(tài)演化、云計算、軟件過程。

1001-9081(2017)01-0024-07DOI:10.11772/j.issn.1001-9081.2017.01.0024

TP

A