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

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

0 引 言

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

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

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

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

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

(1)r-b曲線生成。

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

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

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

(1)

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

進而可以得到：

(2)

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

(3)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 實驗結(jié)果與評價

3.1 實驗環(huán)境

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

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

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

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

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

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

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

3.3 計算的可伸縮性

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

3.4 負載離開的影響

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

圖3 計算時間比較

圖4 負載離開的影響

4 結(jié)束語

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