面向軟件即服務(wù)的負(fù)載均衡策略建模與分析

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

(1.云南大學(xué) 軟件學(xué)院，昆明 650500； 2.云南省軟件工程重點(diǎn)實(shí)驗室(云南大學(xué))，昆明 650500)

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

面向軟件即服務(wù)的負(fù)載均衡策略建模與分析

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

(1.云南大學(xué) 軟件學(xué)院，昆明 650500； 2.云南省軟件工程重點(diǎn)實(shí)驗室(云南大學(xué))，昆明 650500)

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

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

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

0 引言

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

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

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

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

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

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

1 本文思路

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

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

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

2 面向SaaS服務(wù)的負(fù)載均衡策略分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2 相關(guān)定義

關(guān)于Petri網(wǎng)和隨機(jī)Petri網(wǎng)的基本知識，這里只引用和本文相關(guān)的幾個概念，其他的可以參考文獻(xiàn)[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的流關(guān)系。

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

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

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

(1)

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

(2)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

步驟1 變遷T1點(diǎn)火，多租戶的請求到達(dá)在x1；

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

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

步驟4 if (N(ai)

與ai對應(yīng)的服務(wù)器集群ri處理租戶請求；

步驟5 if (N(bi)

與bi對應(yīng)的服務(wù)器集群si處理租戶請求；

步驟6 if (N(ki)

與ki對應(yīng)的服務(wù)器集群mi處理租戶請求；

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

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

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

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

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

變遷ti的實(shí)施概率為：

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

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

變遷ei的實(shí)施概率為：

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

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

變遷wi的實(shí)施概率為：

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

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

變遷di的實(shí)施概率為：

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

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

變遷oi的實(shí)施概率為：

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

4 實(shí)驗仿真和分析

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

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

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

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

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

4.2 模型評價標(biāo)準(zhǔn)

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

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

(3)

其中：E是使變遷t能夠點(diǎn)火的所有情態(tài)集，u為變遷t的實(shí)施速率，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模型總體響應(yīng)時間RT為：

4.3 結(jié)果與分析

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

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

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

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

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

表3 四種算法的總體響應(yīng)時間和總吞吐量對比結(jié)果

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

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

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

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

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

5 結(jié)語

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

)

[1] 白海石.WindowsAzure實(shí)戰(zhàn)[M].北京：機(jī)械工業(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應(yīng)用的負(fù)載均衡機(jī)制研究與實(shí)現(xiàn)[J].小型微型計算機(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] 陳燕升,張贊波,任江濤.改進(jìn)的最小鏈接負(fù)載均衡調(diào)度算法[J].計算機(jī)系統(tǒng)應(yīng)用,2015,24(7):88-92.(CHENYS,ZHANGZB,RENJT.Improvedminimumlinkloadbalancingschedulingalgorithm[J].ComputerSystems&Applications, 2015, 24(7): 88-92.)

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

[9] 趙少卡,李立耀,徐聰,等.基于SaaS的彈性云平臺優(yōu)化調(diào)度策略設(shè)計[J].計算機(jī)應(yīng)用研究,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] 熊偉,李兵,陳軍,等.一種基于預(yù)測控制的SaaS系統(tǒng)自適應(yīng)方法[J].計算機(jī)學(xué)報,2016,39(2):364-376.(XIONGW,LIB,CHENJ,etal.Aself-adaptionapproachbasedonpredictivecontrolforSaaS[J].ChineseJournalofComputers, 2016, 39(2): 364-376.)

[15] 牟權(quán),葉保留,陸桑璐.基于云計算的普適服務(wù)集成平臺技術(shù)研究[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架構(gòu)設(shè)計[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ī)群彈性負(fù)載均衡機(jī)制[J].計算機(jī)應(yīng)用,2013,33(3):830-833.(DUY,GUOT,CHENJJ.Fleetelasticloadbalancingmechanismincloudenvironment[J].JournalofComputerApplications, 2013, 33(3): 830-833.)

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

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

[21] 李彤.軟件并行開發(fā)過程[M].北京：科學(xué)出版社,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。

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

明利(1989—)，女，河南安陽人，碩士研究生，主要研究方向：軟件動態(tài)演化、云計算； 李彤(1963—)，男，河北石家莊人，教授，博士生導(dǎo)師，博士，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