基于M/M/c排隊模型的云計算中心能耗管理策略

張書豪,張延華,王倩雯,王朱偉,李 萌

(北京工業(yè)大學(xué) 電子信息與控制工程學(xué)院,北京 100124)

0 引言

云計算作為一種新興的技術(shù)，以能夠提供彈性的計算資源和按需付費的方式，在信息與通信技術(shù)領(lǐng)域引起了新的革命[1]。云計算是由分布式計算、網(wǎng)格計算和并行處理等技術(shù)逐步發(fā)展而來[2]，它將大量存儲、軟件和計算等資源集中調(diào)度，構(gòu)成超大規(guī)模、高性能且可擴(kuò)充的虛擬IT資源池，再通過面向云用戶的服務(wù)接口，提供按需計費的服務(wù)模式[3]。但是在云計算中，云端服務(wù)器集群能耗極高，如何快速響應(yīng)和解決用戶任務(wù)請求和云端服務(wù)器能耗之間的矛盾，對用戶體驗、云服務(wù)提供商的服務(wù)質(zhì)量、運營成本控制等都有著重大的影響[4]。分析用戶訪問云計算中心的排隊過程并研究云計算中心服務(wù)器的休眠策略，能夠有效地提升云計算中心運行效率。

目前，有許多文獻(xiàn)針對數(shù)據(jù)中心能耗管理以及資源分配問題開展研究，G.Huang，S.Wang等人曾研究了云計算平臺中的資源分配問題，通過建立模型預(yù)測了每個客戶的到達(dá)時間，從而計算滿足資源需求的最小資源量并提出自動擴(kuò)展虛擬機(jī)的算法，進(jìn)而減少資源的使用[5],但他們在對虛擬機(jī)的調(diào)節(jié)上使用的是基于閾值的策略，而設(shè)置閾值又是一項艱巨的任務(wù)，一旦閾值設(shè)置不當(dāng)，策略效果將受到極大影響。文獻(xiàn)[6]從客戶的服務(wù)需求入手，進(jìn)行了預(yù)測，以便服務(wù)提供商避免為滿足服務(wù)水平協(xié)議(service layer agreement，SLA)而過度配置資源，但客戶請求是隨機(jī)變動的，通過預(yù)測值動態(tài)配置計算資源來滿足SLA和的同時達(dá)到資源的最佳利用是困難的；文獻(xiàn)[7]使用M/G/m模型分析了平均隊長、平均響應(yīng)時間和服務(wù)單元數(shù)量之間的關(guān)系，但是沒有獲得響應(yīng)時間概率分布函數(shù)的精確表達(dá)式。文獻(xiàn)[8]通過對云數(shù)據(jù)中心的測試和分析，提出一種降低“等待能耗”的思路，并使用了DPS(Dynamic Powering On/off)技術(shù)，但無法應(yīng)對大量關(guān)閉服務(wù)器時訪問量驟增的情況；文獻(xiàn)[9]則通過對云計算中心建模從而對其服務(wù)性能進(jìn)行分析，得出了用戶請求的平均等待時間以及其他性能指標(biāo)，給出了影響云計算中心性能的各種因素。文獻(xiàn)[10]中提出了基于突發(fā)感知的云計算服務(wù)器資源預(yù)留機(jī)制，有效的解決了任務(wù)請求突然驟增情況下，休眠狀態(tài)服務(wù)器無法及時被喚醒的問題，但是這會在一定程度上造成空閑資源的浪費。文獻(xiàn)[11]中使用了雙狀態(tài)馬爾可夫鏈對云計算虛擬機(jī)的資源需求進(jìn)行建模，并且提出了基于靜態(tài)分布的算法來調(diào)節(jié)虛擬機(jī)數(shù)量，但是對于現(xiàn)有的云計算中心而言，其虛擬機(jī)數(shù)量和任務(wù)到達(dá)量都是十分龐大的，而求解馬爾可夫過程的計算量會隨著基數(shù)的增加而指數(shù)增長。

本文提出一種基于M/M/c過程的云計算訪問排隊模型，通過對模型中的等待時間、隊列長度等指標(biāo)進(jìn)行分析，獲得了該模型響應(yīng)時間的概率分布函數(shù)，在此基礎(chǔ)上引入基于預(yù)留機(jī)制的DPS技術(shù)，并且嵌入以ERP為反饋量的閉環(huán)反饋策略，從而動態(tài)均衡系統(tǒng)能耗與QoS之間的關(guān)系。

1 系統(tǒng)結(jié)構(gòu)及原理模型描述

1.1 云計算中心的工作機(jī)制

在云計算中心系統(tǒng)中，通常有大批任務(wù)請求進(jìn)入數(shù)據(jù)中心。一旦有客戶任務(wù)請求，云計算中心將根據(jù)客戶的不同需求自適應(yīng)提供不同類型的服務(wù)，云計算中心的工作機(jī)制如圖1所示[12]。

圖1 云計算中心的工作機(jī)制

典型的云計算環(huán)境可分為4層結(jié)構(gòu)，分別是物理資源層、虛擬化資源層、管理中間件層和SOA服務(wù)層。云計算資源池屬于資源虛擬化層，它屏蔽了物理資源層在分布上的細(xì)節(jié)，為其上層的管理中間件層提供服務(wù)支持。

1.2 云計算中心的任務(wù)隊列模型

假設(shè)云計算資源池中有c臺服務(wù)器(即c個計算單元)，每個服務(wù)器都是獨立運行的，服務(wù)器完成任務(wù)時不互相影響?？蛻粽埱蟮竭_(dá)的時間間隔服從參數(shù)為λ的泊松分布，并且每個服務(wù)器的服務(wù)速率服從參數(shù)為μ的指數(shù)分布。將這種系統(tǒng)稱為具有多服務(wù)窗口的排隊模型，簡稱M/M/c模型，M/M/c排隊模型運行方式如圖2所示。

圖2 M/M/c排隊模型

將所有用戶每一次訪問云服務(wù)器的動作，都當(dāng)成一次顧客到達(dá)過程，并設(shè)到達(dá)的訪問具有馬爾可夫性，則可以將馬爾可夫鏈引入云計算資源池中，預(yù)測分析未來時刻云計算資源池的狀態(tài)[13]。由于訪問過程服從參數(shù)為λ的泊松分布，且每次到來的任務(wù)所使用的資源量都是隨機(jī)的，即可認(rèn)為每個服務(wù)器的平均服務(wù)率遵循參數(shù)為μ的指數(shù)分布。除此之外，云服務(wù)器資源中物理機(jī)(PM)一般會被抽象為多個虛擬機(jī)(VM)，客戶實際分配到的是虛擬機(jī)資源，為簡化起見本文將為每一個為客戶服務(wù)的服務(wù)器都認(rèn)為是一臺虛擬機(jī)服務(wù)器VM，則可以假設(shè)共有c臺服務(wù)器。在不同時刻到達(dá)的用戶服務(wù)請求中，服務(wù)順序按先到先服務(wù)的規(guī)則。因此，客戶訪問云服務(wù)資源池的過程屬于M/M/c排隊過程。

1.3 隨機(jī)任務(wù)模型

由于服務(wù)請求符合參數(shù)為λ的泊松分布，每個服務(wù)器的平均服務(wù)率遵循參數(shù)為μ的指數(shù)分布，且有c臺服務(wù)器，則云服務(wù)資源池的平均服務(wù)率為cμ，1/λ為平均到達(dá)間隔，1/μ為每個服務(wù)器的平均服務(wù)時間。設(shè)ρ為服務(wù)強(qiáng)度，ρ=λ/cμ，當(dāng)ρ趨近于0時，用戶任務(wù)的等待時間短，服務(wù)器節(jié)點有大量的空閑時間；反之當(dāng)ρ趨近于1時，節(jié)點的空閑時間少，用戶的等待時間長。cμ應(yīng)當(dāng)大于等于λ即ρ≤1，此時排隊模型存在平穩(wěn)分布。假設(shè)云計算資源池不限制任務(wù)數(shù)量，故云計算資源池中隨機(jī)任務(wù)的可能狀態(tài)集應(yīng)為Φ={0，1，2… }。由此可以得出云計算資源池隨機(jī)任務(wù)的狀態(tài)流圖，如圖3所示。

圖3 云計算資源池狀態(tài)流圖

其中：狀態(tài)圓圈內(nèi)的數(shù)字代表系統(tǒng)中服務(wù)進(jìn)程數(shù)設(shè)為n，當(dāng)0≤n≤c時，表示云計算資源池內(nèi)有n個服務(wù)器單元正在被任務(wù)使用，其余c-n個服務(wù)器單元空閑；當(dāng)狀態(tài)n>c時(即達(dá)到云計算資源池的任務(wù)n超過c時)，c個進(jìn)程都在被任務(wù)占用，而余下的任務(wù)排隊等待服務(wù)。根據(jù)圖3，可得到系統(tǒng)狀態(tài)之間的概率轉(zhuǎn)移如下:

λn=λforalln

(1)

(2)

由此可得概率系統(tǒng)狀態(tài)轉(zhuǎn)移矩陣:

(3)

由于n為目前系統(tǒng)中的任務(wù)數(shù)，設(shè)pn為此時系統(tǒng)中共有n個任務(wù)的概率，由此可知：

(4)

(5)

(6)

定義系統(tǒng)空閑概率為：

(7)

由于請求云計算資源池服務(wù)的作業(yè)最終都會完成服務(wù)，故丟失概率Pl=0。因此可知隨機(jī)訪問處于穩(wěn)態(tài)時的各項系統(tǒng)指標(biāo)，其計算公式如下：

排隊隊列中的平均客戶數(shù)量:

(8)

系統(tǒng)中總的平均客戶數(shù)量：

(9)

排隊隊列中的預(yù)期平均等待時間：

(10)

系統(tǒng)中總的預(yù)期平均等待時間：

(11)

1.4 建立實際場景模型

在云計算任務(wù)排隊過程中，客戶請求的任務(wù)量是隨機(jī)變化的，若在大量服務(wù)器單元處于休眠狀態(tài)時突遇用戶任務(wù)請求驟增，由于喚醒服務(wù)器需要花費一定的時間，則可能無法及時地、有效地應(yīng)付云用戶的請求?；趲ьA(yù)留機(jī)制的DPS(dynamic powering onoff)策略，將所有服務(wù)器分為兩組，其中永久運行的服務(wù)器構(gòu)成服務(wù)主模塊(base line module，BLM)，等待啟動的服務(wù)器構(gòu)成服務(wù)預(yù)留模塊(reserved line module，RLM)。系統(tǒng)共設(shè)置有n2個服務(wù)器，BLM中有n1個服務(wù)器，RLM中有n2-n1個服務(wù)器。其中BLM中服務(wù)器永久開啟，RLM中服務(wù)器可以在工作狀態(tài)與休眠之間轉(zhuǎn)變，當(dāng)它的某個服務(wù)器處于休眠狀態(tài)時，則該服務(wù)器僅消耗極少的維持休眠狀態(tài)的能量。將緩沖區(qū)(Buffer)的設(shè)置為無限大，設(shè)置任務(wù)隊列在緩沖區(qū)中也要消耗能量，但能量消耗較少。

從能耗方面考慮，RLM中的服務(wù)器可以在服務(wù)器響應(yīng)較快即緩沖區(qū)中作業(yè)數(shù)量較少時休眠一部分；同時為了保證用戶體驗即QOS值，RLM服務(wù)器應(yīng)在系統(tǒng)響應(yīng)時間過長即緩沖區(qū)中作業(yè)較多時，重新開啟一部分。一般地，由于云服務(wù)器數(shù)量足夠多，且服務(wù)器喚醒——睡眠狀態(tài)轉(zhuǎn)化足夠快，所以服務(wù)器的狀態(tài)轉(zhuǎn)換時間可忽略不計。需要注意的是，在對RLM中服務(wù)器進(jìn)行休眠操作時，休眠策略是在RLM的控制器接收到指令后，休眠已經(jīng)完成任務(wù)的服務(wù)器，對于RLM中正在服務(wù)卻未完成服務(wù)的服務(wù)器則需要等待其完成當(dāng)前工作后休眠，不能休眠正在為顧客服務(wù)的服務(wù)器。

為了符合實際場景，本文設(shè)置相同情況下，BLM中服務(wù)器正常工作時的平均能耗等于RLM服務(wù)器，在請求到來時優(yōu)先訪問BLM中的服務(wù)器，避免 BLM服務(wù)器資源的浪費。排隊過程系統(tǒng)流程如圖4所示。

圖4 實際訪問排隊過程模型

1.5 建立系統(tǒng)能耗模型

考慮到實際問題，某些云服務(wù)器是不能夠隨意關(guān)閉的，關(guān)閉后可能會導(dǎo)致數(shù)據(jù)丟失或者重新配置數(shù)據(jù)庫等一系列問題。所以設(shè)定BLM中服務(wù)器始終保持工作狀態(tài)并保持能耗W1；為了簡化起見，將RLM服務(wù)器的狀態(tài)設(shè)置為兩種：第一種是休眠狀態(tài)，此時服務(wù)器功耗是W21，第二種是工作狀態(tài)，服務(wù)器功耗是W22，W22要遠(yuǎn)大于W21,其總能耗記為W2；由于顧客請求在緩沖器中排隊時也消耗能量，所以設(shè)置在緩沖器Buffer中的等待能耗為W3；由于前文中將RLM中服務(wù)器喚醒與休眠態(tài)之間的轉(zhuǎn)化設(shè)置為瞬時的，所以轉(zhuǎn)換狀態(tài)的能耗W4也可忽略不計。設(shè)BLM共有n1臺服務(wù)器，其中n1臺正在運行；BLM共有n2-n1臺服務(wù)器，其中G臺正在運行則n2-n1-G臺處于休眠狀態(tài)；設(shè)緩沖器隊列中共有D個請求，故此系統(tǒng)的總能耗為：

WA=W1×n1+W22×G+

W21×(n2-n1-G)+D×W3

(12)

2 算法描述

能量響應(yīng)時間乘積ERP(energy-response time product)，被認(rèn)為是尋找能量性能權(quán)衡的合適度量。它被定義為：ERPπ=E[Pπ]×E[Tπ][14]。其中E[Pπ]是控制策略π下的長期平均功耗，E[Tπ]是策略π下的平均客戶響應(yīng)時間。最小化ERP可被視為最大化"每瓦特性能"，此處性能被定義為平均響應(yīng)時間的倒數(shù)。在控制領(lǐng)域，反饋算法作為閉環(huán)控制系統(tǒng)的核心，對系統(tǒng)各個節(jié)點狀態(tài)的控制、調(diào)節(jié)起到了至關(guān)重要的作用。本文提出一種帶預(yù)留機(jī)制的基于ERP標(biāo)準(zhǔn)的反饋算法，實現(xiàn)對系統(tǒng)的全局控制和優(yōu)化。

W*=Lq*×W3+(c*-n1)×W22+

(n2-c*)×W21+n1×W1

(13)

而此時系統(tǒng)的實際消耗功率為：

Wa=Lat×W3+(cat-n1)×W22+

(n2-cat)×W21+n1×W1

(14)

其中:Lat為此時Buffer中實際隊列長度，cat是此時實際運行服務(wù)器臺數(shù)。

具體算法如Alg.1所示，系統(tǒng)框圖如圖5所示。

圖5 基于反饋控制調(diào)節(jié)的系統(tǒng)框圖

Algorithm 1 Feedback algorithm based on ERP

Input:λ,μ,B,Q,n1,Tc,Tmax;

Output: Number of servers to adjust；

1 set User satisfaction response time B

4 computeW*by Equs.(13)

5 get the Feedback system inputW*×B

6 detect the actual power consumptionWaand actual response timeTinTc

7 get the Feedback system inputWa×T

8 compute △W=Wa×T-W*×B

9 If △W>0 then

10 wake up some servers by Linear programming Alg.

11 else if △W<0

12 dormancy some servers by Linear programming Alg.

13 else

14 Dormancy all servers in RLM

15 End if

16Tc=Tc+10

17 End while

18 return

3 實驗結(jié)果與分析

3.1 參數(shù)設(shè)置及實驗背景

在Matlab 2019a環(huán)境下，進(jìn)行實驗仿真，對本文提出的基于ERP的帶預(yù)留機(jī)制的反饋算法進(jìn)行仿真，從任務(wù)的響應(yīng)時間和能耗兩個方面進(jìn)行仿真來評估算法。實驗建立了一個由100個服務(wù)器組成的數(shù)據(jù)中心，其中50個BLM服務(wù)器，50個等待啟動的RLM服務(wù)器。排隊規(guī)則設(shè)置為服從M/M/c排隊模型，在任務(wù)排隊的過程中，根據(jù)實時ERP的值，來決定是否開啟RLM中服務(wù)器以及開啟多少數(shù)量的RLM服務(wù)器。計算出系統(tǒng)在仿真時長內(nèi)的能耗，以及系統(tǒng)平均響應(yīng)時間，與never-off算法與靜態(tài)閾值算法進(jìn)行比較，仿真時長到達(dá)后，實驗結(jié)束。

表1 實驗參數(shù)設(shè)置

3.2 實驗結(jié)果及比較

首先，仿真完成了在上述參數(shù)及規(guī)則下的基于 ERP的帶預(yù)留機(jī)制的反饋算法，其次比較了never- off算法、靜態(tài)閾值算法、本文算法的任務(wù)平均響應(yīng)時間和系統(tǒng)執(zhí)行任務(wù)的功耗。設(shè)λ=700后，可得到任務(wù)到達(dá)符合泊松分布的數(shù)據(jù)，如圖6所示。仿真實驗比較了在總仿真時間為100 s時，3種算法的平均響應(yīng)時間，如圖7所示，never-off算法的平均響應(yīng)時間最短，靜態(tài)閾值算法最長，而本文算法的平均響應(yīng)時間介于上述兩種算法之間。這是由于在 never-off算法中，云計算中心開啟的服務(wù)器數(shù)量是根據(jù)排隊理論預(yù)測出來的，云數(shù)據(jù)中心的服務(wù)器不能動態(tài)喚醒或休眠，所有任務(wù)都可以盡快地分配到服務(wù)器；在靜態(tài)閾值算法中，雖然服務(wù)器可以動態(tài)喚醒休眠，但開啟服務(wù)器的數(shù)量在每個階段都有固定值，在該階段內(nèi)即使任務(wù)數(shù)增加，服務(wù)器數(shù)量也不會增加，此時便會導(dǎo)致平均響應(yīng)時間增長，無法較好地滿足云用戶任務(wù)響應(yīng)時間需求；而在本文算法中，云計算中心的運行服務(wù)器數(shù)量能夠根據(jù)ERP變動動態(tài)改變，能夠較好地滿足云用戶任務(wù)響應(yīng)時間需求。

圖6 泊松分布下任務(wù)請求數(shù)量到達(dá)變化

圖7 3種算法響應(yīng)時間比較

由圖8可知，在相同條件下，本文算法的消耗的能耗最小，never-off算法的消耗的能耗最大，靜態(tài)閾值算法消耗的能耗介于上述兩個算法之間。這是由于在never-off算法中，云計算中心的服務(wù)器總數(shù)量是根據(jù)排隊論預(yù)測值計算得出的，并始終全部開啟，在任務(wù)到來較少時產(chǎn)生了大量無用能耗，因此其節(jié)能效果最差；在靜態(tài)閾值算法中，只有當(dāng)隊列中的任務(wù)超過設(shè)定的閾值時，部分服務(wù)器才開啟并提供服務(wù)，這在一定程度上避免了大量空閑能耗的產(chǎn)生，相對never-off算法也有一定的改進(jìn)，然而該算法需要設(shè)置閾值，閾值設(shè)置本身就困難，閾值設(shè)置不當(dāng)很可能會導(dǎo)致系統(tǒng)性能不佳。在本文算法中，可以根據(jù)ERP值動態(tài)調(diào)整并決策出相對較優(yōu)的運行服務(wù)器數(shù)量，避免開啟過多RLM中的服務(wù)器，有利于降低云數(shù)據(jù)中心空閑能耗。通過結(jié)果對3種算法進(jìn)行對比，可知never-off算法能提供最優(yōu)的系統(tǒng)性能，但其消耗的總能耗最多，不能滿足云計算中心的利益；靜態(tài)閾值算法在一定程度上節(jié)約了能耗，照顧到了云計算中心的利益，但一旦系統(tǒng)中任務(wù)數(shù)過多，就會使任務(wù)的平均等待時間上升，降低了QOS值；而本文提出的策略能夠兼顧云計算中心和用戶的利益，相對較優(yōu)。圖9中，actualERP是實際ERP的變化，ERP*是期望。

圖8 3種算法功率消耗比較

圖9 ERP變化比較圖

從圖9可以看出，本文的算法得出的實際ERP值始終在預(yù)估值的附近波動，而且越來越趨近于預(yù)期ERP，故可知仿真結(jié)果符合預(yù)期。值得注意的是，在圖6和圖7中，本文算法的初期波動較大，圖8中實際ERP值也呈現(xiàn)出折線狀波動，這是由于本文算法在初期調(diào)整時為了輕量化計算量選用了反饋算法而造成的現(xiàn)象。但經(jīng)過短暫的波動期后，數(shù)據(jù)指標(biāo)便會趨于穩(wěn)定。

4 結(jié)束語

針對現(xiàn)有云計算中心能耗浪費問題，對云計算中心的工作機(jī)制進(jìn)行了分析，得出了云計算中心的工作特點，利用M/M/c排隊模型對云計算中心用戶訪問過程進(jìn)行了建模，并得出各項重要指標(biāo)。引入了動態(tài)開關(guān)策略(DPS)，在此基礎(chǔ)上提出了基于ERP標(biāo)準(zhǔn)的帶預(yù)留機(jī)制的反饋控制策略?；贛arkov過程的狀態(tài)空間及其狀態(tài)轉(zhuǎn)換關(guān)系的控制策略會隨著服務(wù)器數(shù)量的增加導(dǎo)致策略計算指數(shù)型增加，本文提出的輕量級算法在云服務(wù)器中心服務(wù)器計算單元巨大的實際情況下，具有快速得出策略控制結(jié)果的優(yōu)勢。以ERP為衡量標(biāo)準(zhǔn)，均衡考慮了能耗與響應(yīng)時間兩項重要指標(biāo)，最大化“每瓦特性能”，尋找最佳的能耗績效權(quán)衡。實驗證明，該策略能夠在保證QoS的情況下，有效降低系統(tǒng)能耗。但是也存在得出的控制結(jié)果不夠精確，仿真初期震蕩較大的缺點。下一步將重點考慮引入?yún)?shù)隨時間變化的泊松分布，在不過多增加計算量的前提下，研究更加精確的控制方法，提出本算法的補(bǔ)充算法，進(jìn)一步對云計算中心的服務(wù)質(zhì)量和能耗進(jìn)行優(yōu)化管理。