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

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

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

0 引言

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

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

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

1 系統結構及原理模型描述

1.1 云計算中心的工作機制

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

圖1 云計算中心的工作機制

典型的云計算環境可分為4層結構，分別是物理資源層、虛擬化資源層、管理中間件層和SOA服務層。云計算資源池屬于資源虛擬化層，它屏蔽了物理資源層在分布上的細節，為其上層的管理中間件層提供服務支持。

1.2 云計算中心的任務隊列模型

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

圖2 M/M/c排隊模型

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

1.3 隨機任務模型

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

圖3 云計算資源池狀態流圖

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

λn=λforalln

(1)

(2)

由此可得概率系統狀態轉移矩陣:

(3)

由于n為目前系統中的任務數，設pn為此時系統中共有n個任務的概率，由此可知：

(4)

(5)

(6)

定義系統空閑概率為：

(7)

由于請求云計算資源池服務的作業最終都會完成服務，故丟失概率Pl=0。因此可知隨機訪問處于穩態時的各項系統指標，其計算公式如下：

排隊隊列中的平均客戶數量:

(8)

系統中總的平均客戶數量：

(9)

排隊隊列中的預期平均等待時間：

(10)

系統中總的預期平均等待時間：

(11)

1.4 建立實際場景模型

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

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

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

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

1.5 建立系統能耗模型

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

WA=W1×n1+W22×G+

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

(12)

2 算法描述

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

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

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

(13)

而此時系統的實際消耗功率為：

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

(n2-cat)×W21+n1×W1

(14)

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

具體算法如Alg.1所示，系統框圖如圖5所示。

圖5 基于反饋控制調節的系統框圖

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 實驗結果與分析

3.1 參數設置及實驗背景

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

表1 實驗參數設置

3.2 實驗結果及比較

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

圖6 泊松分布下任務請求數量到達變化

圖7 3種算法響應時間比較

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

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

圖9 ERP變化比較圖

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

4 結束語

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