基于動(dòng)態(tài)限速的云計(jì)算應(yīng)用負(fù)載調(diào)度方法

劉永波，周 博，李亞瓊，李守超，宋云奎

(1.江蘇潤(rùn)和軟件股份有限公司，江蘇 南京 210012；2.中國(guó)科學(xué)院 軟件研究所，北京 100190)

0 引 言

在云計(jì)算環(huán)境中，云服務(wù)提供商為多個(gè)客戶(hù)提供共享的計(jì)算、網(wǎng)絡(luò)和存儲(chǔ)資源以最大化資源利用率，降低總體能耗，從而減少數(shù)據(jù)中心的運(yùn)營(yíng)成本，同時(shí)保障良好性能，如滿(mǎn)足請(qǐng)求處理延遲時(shí)間，以提升客戶(hù)滿(mǎn)意度。客戶(hù)通常定義服務(wù)水平目標(biāo)(service level object，SLO)以描述處理負(fù)載的性能要求，比如“80%的請(qǐng)求必須在100 ms內(nèi)完成”。那么，需要具有高效的負(fù)載調(diào)度方法，服務(wù)器在滿(mǎn)足性能目標(biāo)的前提下，能夠處理多樣化的負(fù)載。為了應(yīng)對(duì)整合負(fù)載所帶來(lái)的網(wǎng)絡(luò)擁塞問(wèn)題，云服務(wù)提供者和客戶(hù)通常會(huì)達(dá)成限速協(xié)議，客戶(hù)靜態(tài)設(shè)定限速規(guī)則，服務(wù)提供商則進(jìn)行相應(yīng)的優(yōu)化，以實(shí)現(xiàn)性能最大化。

當(dāng)前的負(fù)載調(diào)度方法是，為客戶(hù)預(yù)先保留一定數(shù)量的資源，或者以盡最大努力的方式處理負(fù)載。文獻(xiàn)[1-2]提出了BCLL-Min-Min算法以滿(mǎn)足帶寬需求約束。文獻(xiàn)[3]提出一種在線(xiàn)式負(fù)載調(diào)度算法以最小化數(shù)據(jù)中心的電費(fèi)，建立數(shù)據(jù)中心的電費(fèi)模型，形式化為隨機(jī)優(yōu)化問(wèn)題，求解得到負(fù)載調(diào)度策略。文獻(xiàn)[4]提出一種智能電網(wǎng)環(huán)境下家庭可控負(fù)載優(yōu)化調(diào)度策略，對(duì)負(fù)載進(jìn)行分類(lèi)并劃分優(yōu)先級(jí)，對(duì)負(fù)載進(jìn)行通斷調(diào)度，以提高能源利用效率。文獻(xiàn)[5]提出一種流媒體集群服務(wù)器的負(fù)載調(diào)度策略，運(yùn)用多級(jí)模糊系統(tǒng)和人工神經(jīng)網(wǎng)絡(luò)對(duì)用戶(hù)請(qǐng)求響應(yīng)延時(shí)進(jìn)行模糊預(yù)測(cè)。文獻(xiàn)[6-7]動(dòng)態(tài)評(píng)估作業(yè)在截止時(shí)間內(nèi)完成所需要的Map和Reduce計(jì)算資源數(shù)量，動(dòng)態(tài)地增加或減少獨(dú)立虛擬機(jī)的方式來(lái)調(diào)整CPU資源。文獻(xiàn)[8]建立了負(fù)載雙層矩形域模型，基于貪婪策略給出了多項(xiàng)式時(shí)間近似算法，對(duì)數(shù)據(jù)傳輸階段進(jìn)行負(fù)載排序調(diào)度，使GPU性能達(dá)到全局最優(yōu)或近似最優(yōu)。文獻(xiàn)[9]組建信息傳輸負(fù)載均衡性調(diào)度聚合時(shí)機(jī)的調(diào)度機(jī)制，完成對(duì)海量信息傳輸負(fù)載均衡性調(diào)度。文獻(xiàn)[10]及時(shí)收集釋放空轉(zhuǎn)資源降低資源能耗浪費(fèi),實(shí)現(xiàn)了節(jié)點(diǎn)負(fù)載度量、任務(wù)度量、負(fù)載整合算法,并測(cè)算出節(jié)點(diǎn)自適應(yīng)負(fù)載閾值。Silo[11]設(shè)計(jì)限速方案以保障網(wǎng)絡(luò)延遲，pClock[12]設(shè)計(jì)限速方案以保障存儲(chǔ)延遲,文獻(xiàn)[13]采用性能預(yù)測(cè)的方法動(dòng)態(tài)調(diào)整等待處理的負(fù)載。Pythia[14]監(jiān)測(cè)運(yùn)行過(guò)程中SLO是否發(fā)生沖突，動(dòng)態(tài)學(xué)習(xí)適合的遷移行為。

然而，面對(duì)云計(jì)算環(huán)境下應(yīng)用的大量負(fù)載，難以實(shí)現(xiàn)通過(guò)預(yù)留資源來(lái)滿(mǎn)足處理延遲，尤其是，短期突發(fā)性負(fù)載會(huì)對(duì)處理延遲產(chǎn)生顯著影響。同時(shí)，難以為不同的負(fù)載類(lèi)型設(shè)置合理的限速參數(shù)。針對(duì)該問(wèn)題，面向長(zhǎng)時(shí)間運(yùn)行的云應(yīng)用，提出一種基于動(dòng)態(tài)限速的云應(yīng)用負(fù)載調(diào)度方法，在保障處理負(fù)載的性能滿(mǎn)足SLO的約束下，將負(fù)載調(diào)度并整合到目標(biāo)服務(wù)器，以最小化處理負(fù)載的服務(wù)器數(shù)量。

1 基于動(dòng)態(tài)限速的云應(yīng)用負(fù)載調(diào)度方法

文中刻畫(huà)負(fù)載，描述其對(duì)處理延遲的影響，通過(guò)對(duì)存儲(chǔ)和網(wǎng)絡(luò)進(jìn)行限速，并設(shè)置負(fù)載的優(yōu)先級(jí)，在滿(mǎn)足處理延遲的條件下，自動(dòng)化地減少服務(wù)器數(shù)量。

(1)r-b曲線(xiàn)生成。

生成r-b曲線(xiàn)以描述負(fù)載處理速率r與令牌桶容積b之間的關(guān)系。當(dāng)請(qǐng)求到達(dá)時(shí)，令牌添加到令牌桶中，如果令牌桶中有足夠的空間來(lái)添加令牌，即不超過(guò)令牌桶大小為b，則允許繼續(xù)處理請(qǐng)求。否則，請(qǐng)求就會(huì)排隊(duì)等待，直到令牌桶中有足夠的空間。令牌以速率r不斷地從桶中流出，空間逐漸變得可用。對(duì)于給定的r值，通過(guò)重放具有速率r以及無(wú)限大小令牌桶在任意時(shí)間點(diǎn)的執(zhí)行軌跡，計(jì)算得到不需要排隊(duì)的請(qǐng)求數(shù)量b。輸入r與輸出b構(gòu)成元組作為點(diǎn)，連接形成分段r-b曲線(xiàn)。對(duì)r值進(jìn)行標(biāo)準(zhǔn)化處理(例如，網(wǎng)絡(luò)流量除以網(wǎng)絡(luò)帶寬)，那么，r=1.0表示負(fù)載占用了所有帶寬資源。傳輸?shù)臄?shù)據(jù)量取決于請(qǐng)求類(lèi)型(例如，讀/寫(xiě))，分別生成不同的r-b曲線(xiàn)。

(2)限速參數(shù)設(shè)定。

使用網(wǎng)絡(luò)微積分方程進(jìn)行計(jì)算，由于在服務(wù)器上排隊(duì)而導(dǎo)致的處理延遲，對(duì)于優(yōu)先級(jí)p的負(fù)載，處理延遲的上限為：

(1)

其中，是負(fù)載j的限速設(shè)置，bj是負(fù)載j的令牌桶大小，rj是負(fù)載j的處理速率；pj是負(fù)載j的優(yōu)先級(jí),其高于或等于p；SLOp是與優(yōu)先級(jí)p關(guān)聯(lián)的SLO。

進(jìn)而可以得到：

(2)

使用分段線(xiàn)性凸函數(shù)r-b曲線(xiàn)，可以將bi表示為ri的函數(shù)，進(jìn)而利用線(xiàn)性規(guī)劃方法求解得到每個(gè)限速元組，滿(mǎn)足約束條件：

(3)

每個(gè)負(fù)載關(guān)聯(lián)r-b曲線(xiàn)，當(dāng)新的負(fù)載調(diào)度到該服務(wù)器時(shí)，動(dòng)態(tài)重新計(jì)算現(xiàn)有負(fù)載共享該服務(wù)器的限速設(shè)置。

(3)服務(wù)器選擇。

通過(guò)線(xiàn)性規(guī)劃求解，將負(fù)載分發(fā)給SLOs能夠滿(mǎn)足的服務(wù)器，采用首先匹配的策略。在通常情況下，大多數(shù)服務(wù)器幾乎都是滿(mǎn)載的，所以新負(fù)載不能分發(fā)給幾乎滿(mǎn)負(fù)載的服務(wù)器。因此，文中提出了快速首次匹配方法，跟蹤每個(gè)服務(wù)器上配置的速率總和，跳過(guò)將負(fù)載放到接近滿(mǎn)負(fù)載的服務(wù)器，避免了不必要的運(yùn)行線(xiàn)性規(guī)劃計(jì)算的過(guò)程。

提出的方法能夠根據(jù)服務(wù)的實(shí)際資源使用狀態(tài)，動(dòng)態(tài)調(diào)整限速參數(shù)，即負(fù)載處理速度r和令牌桶容積b;在保障處理負(fù)載的性能滿(mǎn)足SLO的約束下，將負(fù)載調(diào)度并整合到目標(biāo)服務(wù)器，以最小化處理負(fù)載的服務(wù)器數(shù)量；能夠滿(mǎn)足在同一臺(tái)服務(wù)器上，不同類(lèi)型負(fù)載對(duì)于處理延遲的要求。

2 負(fù)載調(diào)度系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)

如圖1所示，文中提出的負(fù)載調(diào)度系統(tǒng)由五個(gè)主要組件構(gòu)成。

(1)r-b曲線(xiàn)生成器：根據(jù)處理負(fù)載的歷史記錄生成r-b曲線(xiàn)，描述負(fù)載的存儲(chǔ)和網(wǎng)絡(luò)利用率，并根據(jù)客戶(hù)需求定義SLO；

(2)部署器：標(biāo)識(shí)可以分發(fā)負(fù)載的候選服務(wù)器；

(3)優(yōu)化器：為每個(gè)負(fù)載配置限速參數(shù)，并決定在哪個(gè)服務(wù)器上放置負(fù)載來(lái)滿(mǎn)足處理延遲要求；

(4)延遲檢查器：確定負(fù)載的候選位置和元組是否能夠滿(mǎn)足負(fù)載的SLO要求；

(5)實(shí)施器：配置適當(dāng)?shù)拇鎯?chǔ)和網(wǎng)絡(luò)限速，并將負(fù)載分配給服務(wù)器。

圖1 負(fù)載調(diào)度系統(tǒng)設(shè)計(jì)

文中提出的負(fù)載調(diào)度方法的執(zhí)行流程如下：

(1)r-b曲線(xiàn)生成器根據(jù)負(fù)載類(lèi)型的歷史執(zhí)行記錄生成網(wǎng)絡(luò)或內(nèi)存的r-b曲線(xiàn)(即線(xiàn)性分段函數(shù)b=f(r))，并將用戶(hù)定義的負(fù)載SLO要求，一同發(fā)送給部署器；

(2)部署器選擇可以分發(fā)負(fù)載的服務(wù)器，并生成候選服務(wù)器列表，即存在較充足資源的服務(wù)器；

(3)優(yōu)化器使用線(xiàn)性規(guī)劃方法計(jì)算服務(wù)器上共存的各類(lèi)負(fù)載的元組參數(shù)，并將計(jì)算結(jié)果發(fā)送給延遲檢查器：

(4)延遲檢查器檢測(cè)在候選服務(wù)器以及元組是否能夠滿(mǎn)足用戶(hù)所定義的SLO要求，如果能滿(mǎn)足則將候選服務(wù)器以及元組信息發(fā)送給實(shí)施器，否則重新發(fā)回部署器以生成新的方案；

(5)實(shí)施器將負(fù)載發(fā)送給選定的候選服務(wù)器，并設(shè)置元組參數(shù)。

3 實(shí)驗(yàn)結(jié)果與評(píng)價(jià)

3.1 實(shí)驗(yàn)環(huán)境

文中搭建由11臺(tái)服務(wù)器構(gòu)建的集群，其中包括1臺(tái)部署客戶(hù)端和10臺(tái)部署服務(wù)端，每臺(tái)服務(wù)器配置了兩個(gè)英特爾Xeon E5-2680處理器，64 GB的DRAM，以及一個(gè)300 GB的Intel 710 SSD，通過(guò)1 Gbps網(wǎng)絡(luò)連接。每臺(tái)機(jī)器運(yùn)行64位Ubuntu 14.04，并通過(guò)標(biāo)準(zhǔn)kvm包(qemu-kvm-1.0)運(yùn)行虛擬機(jī)，使用標(biāo)準(zhǔn)的NFSv3服務(wù)器和客戶(hù)端，提供遠(yuǎn)程存儲(chǔ)訪(fǎng)問(wèn)。在服務(wù)器端存儲(chǔ)文件，客戶(hù)端發(fā)送請(qǐng)求訪(fǎng)問(wèn)文件，訪(fǎng)問(wèn)文件的模式分為讀取、增加、刪除、修改文件等幾種，訪(fǎng)問(wèn)文件的大小隨機(jī)產(chǎn)生，這樣在服務(wù)器端產(chǎn)生各種訪(fǎng)問(wèn)文件的執(zhí)行軌跡。隨機(jī)選取一半執(zhí)行軌跡用于訓(xùn)練產(chǎn)生r-b曲線(xiàn)，另一半執(zhí)行軌跡在服務(wù)器端重放以驗(yàn)證所提出的負(fù)載調(diào)度方法可以保證響應(yīng)時(shí)間，并減少服務(wù)器數(shù)量。

3.2 減少服務(wù)器數(shù)量

文中提出的方法旨在通過(guò)設(shè)置每個(gè)負(fù)載的限速參數(shù)，實(shí)現(xiàn)在滿(mǎn)足負(fù)載處理延遲的情況下，減少服務(wù)器數(shù)量。提出的限速方法與當(dāng)前限速方法比較如下：

(1)擴(kuò)展平均帶寬：統(tǒng)計(jì)計(jì)算歷史帶寬的平均值，將r值設(shè)置為該平均值的1.5倍；

(2)r-b曲線(xiàn)拐點(diǎn)：觀(guān)察選取r-b曲線(xiàn)拐點(diǎn)，作為選取的參數(shù)以最小化r值與b值之和。

實(shí)驗(yàn)中設(shè)置的負(fù)載處理延遲分別為：100 ms、150 ms、250 ms、500 ms、1 000 ms，計(jì)算使用的服務(wù)器數(shù)量。如圖2所示，與現(xiàn)有方法相比，文中提出的方法需要更少的服務(wù)器數(shù)量。

圖2 服務(wù)器數(shù)量變化

3.3 計(jì)算的可伸縮性

隨著集群規(guī)模的增長(zhǎng)，所提出方法計(jì)算能力的可伸縮性如圖3所示。提出的快速首先滿(mǎn)足策略由于跳過(guò)幾乎滿(mǎn)負(fù)載的服務(wù)器，比典型的首先滿(mǎn)足策略具有更好的效果。

3.4 負(fù)載離開(kāi)的影響

以上實(shí)驗(yàn)中，假定負(fù)載隨時(shí)可以到達(dá)，而在實(shí)際中，負(fù)載也會(huì)隨時(shí)離開(kāi)系統(tǒng)，留下一些空白來(lái)放置將來(lái)的負(fù)載。為了模擬這種情況，在實(shí)驗(yàn)中，負(fù)載隨機(jī)到達(dá)并離開(kāi)系統(tǒng)。如圖4所示，提出的方法能夠更好地處理負(fù)載，減少了50%服務(wù)器。

圖3 計(jì)算時(shí)間比較

圖4 負(fù)載離開(kāi)的影響

4 結(jié)束語(yǔ)

云計(jì)算環(huán)境下，應(yīng)用負(fù)載規(guī)模巨大，云服務(wù)提供商為多個(gè)客戶(hù)提供共享的計(jì)算、網(wǎng)絡(luò)和存儲(chǔ)資源以最大化資源利用率，降低總體能耗，從而減少數(shù)據(jù)中心的運(yùn)營(yíng)成本，同時(shí)需要為用戶(hù)提供良好的性能保障。針對(duì)該問(wèn)題，提出一種基于動(dòng)態(tài)限速的云應(yīng)用負(fù)載調(diào)度方法。實(shí)驗(yàn)結(jié)果表明，該方法能夠保障云應(yīng)用性能，減少運(yùn)行服務(wù)器數(shù)量，具有較好的可擴(kuò)展性。