廖建錦,孫慶驍,楊海龍,欒鐘治,錢德沛
(北京航空航天大學(xué)計算機學(xué)院,北京 100191)
科學(xué)應(yīng)用中不同計算任務(wù)之間往往存在復(fù)雜的依賴關(guān)系,為了更好地刻畫不同計算任務(wù)之間的依賴關(guān)系,這些計算任務(wù)通常被組織成工作流,如CyberShake[1]和MapReduce[2]。工作流通常被表示成有向無環(huán)圖DAG(Directed Acyclic Graph),在本文場景下,DAG和工作流可以互相替換。此外,隨著云計算市場的蓬勃發(fā)展,將工作流放置到云上計算可以更好地滿足科學(xué)應(yīng)用不斷增加的計算需求。亞馬遜云服務(wù)AWS(Amazon Web Services)、阿里云等云計算服務(wù)提供商可以提供大量大小不一且可靠的虛擬機計算資源。
然而,將工作流放置到云上計算存在著幾個重要的挑戰(zhàn)。一方面是工作流調(diào)度的復(fù)雜性,如何將虛擬機資源映射到各個任務(wù)以滿足工作流執(zhí)行時限的要求;另一方面,將工作流放到云上計算會產(chǎn)生大量的經(jīng)濟(jì)成本,如何在滿足工作流執(zhí)行時限的前提下降低成本也是個難題。其中,對于執(zhí)行時限內(nèi)降低工作流成本的問題,現(xiàn)有的研究工作提出了很多方法對工作流的虛擬機資源進(jìn)行優(yōu)化。例如,Abrishami等人[3]使用部分關(guān)鍵路徑解決虛擬機資源的選擇問題,但是其使用的虛擬機資源大部分是按需付費虛擬機實例[4],這類計算資源較為可靠但價格固定,其成本優(yōu)化空間相當(dāng)有限。云計算服務(wù)提供商也提供了可搶占虛擬機實例[5,6],其價格一般為按量按需付費實例的10%~20%。如果工作流虛擬機資源配置中可以利用好可搶占實例,會極大地減少工作流的計算成本。雖然可搶占實例價格低廉,但是其在執(zhí)行過程中存在一定概率被云服務(wù)商收回釋放,導(dǎo)致工作流無法按時完成。因此,如何在工作流執(zhí)行過程中,可靠地利用可搶占實例,在滿足執(zhí)行時限要求的情況下,降低計算成本是一個新的挑戰(zhàn)。
針對上述挑戰(zhàn),本文提出了滿足工作流執(zhí)行時限的可搶占虛擬機實例配置和調(diào)度方法,可以在滿足工作流最長執(zhí)行時限的前提下,最小化工作流執(zhí)行的計算成本。本文提出的方法具有重要的實際經(jīng)濟(jì)價值。具體而言,本文的主要貢獻(xiàn)如下所示:
(1)提出了基于馬爾科夫模型的可搶占虛擬機實例價格預(yù)測模型。
(2)提出了針對單任務(wù)的成本估計方法。通過估計不同出價策略下的工作流計算成本,從中選擇最優(yōu)出價策略。
(3)提出了基于可搶占虛擬機實例價格特點的工作流配置和調(diào)度方法。
(4)基于阿里云真實數(shù)據(jù),對本文提出的方法進(jìn)行模擬驗證,并與已有算法進(jìn)行對比。
可搶占實例是云計算市場中較為特殊的一類資源,其價格低廉,但生命周期不再只由用戶決定,還和市場有關(guān)[5,7]。用戶需要提供出價以創(chuàng)建可搶占實例,而創(chuàng)建可搶占實例是否成功還和市場價格以及資源是否充足有關(guān)。當(dāng)用戶出價大于市場價格且資源充足的情況下,用戶可以成功創(chuàng)建可搶占實例。其中市場價格取決于市場供需關(guān)系,隨時間發(fā)生波動。在用戶成功創(chuàng)建可搶占實例后,云計算服務(wù)提供商會不斷檢查用戶出價和市場價格,當(dāng)市場價格大于用戶出價或資源不足,那么該用戶的可搶占實例就會被云計算服務(wù)提供商收回并釋放。由此可知,當(dāng)用戶出價較高時,可搶占實例會更加穩(wěn)定,但相應(yīng)地價格也會更加昂貴。
可搶占實例的出價策略主要分2種:靜態(tài)出價策略和動態(tài)出價策略。靜態(tài)出價策略一般目標(biāo)比較單一,常見的有依據(jù)歷史價格出價和預(yù)測未來價格出價。Andrzejak等人[8]提出了一種概率模型,其證明當(dāng)出價為最低價或者平均價格時,一般規(guī)律是出價越高成本越高,但相應(yīng)地完成時間會更短。Baughman等人[9]利用LSTM預(yù)測未來價格變化,而Fabra等人[10]首先對各個可用區(qū)進(jìn)行分類,然后根據(jù)其不同的價格特點分別建模預(yù)測價格??偠灾?,靜態(tài)出價策略比較簡單,出價的高低對應(yīng)著任務(wù)對時間和可靠性的要求。
Figure 1 Spot instance configuration and scheduling method proposed in this paper圖1 本文提出的可搶占虛擬機實例配置和調(diào)度方法WCSSI
相比靜態(tài)策略,動態(tài)策略可以協(xié)同優(yōu)化計算成本和完成時間。對此,許多研究提出了在不同約束條件下的出價策略,比如限制成本或者計算時間等。Kamiński等人[11]提出了一種自適應(yīng)的出價策略,該策略可以同時降低計算成本和實例回收帶來的延遲。Zafer等人[12]則將此類問題建模為一般的離散時間動態(tài)規(guī)劃問題,并提出了最優(yōu)出價策略,該策略可以在固定時間內(nèi)最大程度地降低計算成本。相對而言,動態(tài)出價策略可以在一定約束條件下獲得比較好的結(jié)果,但是建模和求解會相對比較復(fù)雜。
眾所周知,工作流調(diào)度是一個NP-complete問題[13]。當(dāng)工作流放置到云上進(jìn)行計算的時候,成本是研究關(guān)注的重點問題之一。在云上進(jìn)行工作流調(diào)度,比較常見的場景包括有限時間內(nèi)最小化成本和有限成本內(nèi)最小化執(zhí)行時間。除此之外,還有研究討論云計算實例的計算能力和工作流的魯棒性問題。
對于在有限時間內(nèi)最小化成本的問題,一般的方法是選擇較為廉價的資源分配給非關(guān)鍵路徑上的任務(wù),如此便可以在不增加工作流整體運行時間的基礎(chǔ)上降低成本,其中比較常見的方式是通過時間分配來選擇資源。例如,Yu等人[14]根據(jù)工作流中的依賴關(guān)系對各個任務(wù)進(jìn)行分類,然后根據(jù)每個任務(wù)的類別來分配時間,最后按照分配的時間來為任務(wù)選擇不同的資源。除此之外,也有研究利用關(guān)鍵路徑來選擇資源。例如,Gao等人[15]利用關(guān)鍵路徑和最短路徑對工作流中的各個任務(wù)進(jìn)行分類,然后按照一定的優(yōu)先級來逐步減少各個任務(wù)的計算成本,從而降低整個工作流的成本。Abrishami等人[3]則是利用部分關(guān)鍵路徑并通過遞歸的方式來決定各個任務(wù)的資源分配。
鑒于可搶占實例比較廉價,部分學(xué)者在工作流中加入可搶占實例以降低工作流成本。Monge等人[16]提出了CMI(Cloud Multi-objective Intelligence),其同時考慮了工作流的時間和出錯概率,通過遺傳算法求解。Poola等人[17]則是通過啟發(fā)式算法來使用搶占式實例,進(jìn)而降低工作流的成本。Zhou等人[18]用A star算法進(jìn)行剪枝,然后調(diào)整各個任務(wù)的資源分配,從而以一定的概率使工作流不會超時。這些算法對于搶占式實例的出價大都以盡可能保證能夠獲得可搶占實例為主,并沒有考慮進(jìn)一步降低有限時間內(nèi)獲得可搶占實例的成本。另外,由于期限的不同,可搶占實例的期望價格也不一樣,當(dāng)工作流執(zhí)行時限過大時會出現(xiàn)邊際效應(yīng),會帶來虛擬機利用率的問題。此外,不同可搶占實例的價格差異很大,這些差異很大程度上影響工作流整體的配置。上述算法如果能考慮到這些問題,那么可以進(jìn)一步降低工作流的成本。
本文提出的可搶占虛擬機實例配置和調(diào)度方法WCSSI(Workflow Cost Saver based on Spot Instance)的整體結(jié)構(gòu)如圖 1所示,具體包括價格預(yù)測、成本估計和工作流配置和調(diào)度3個部分。首先根據(jù)可搶占實例的價格特點,在工作流執(zhí)行前通過工作流配置算法確定工作流中任務(wù)所選擇的可搶占實例,在工作流配置的層次上降低計算成本。之后在工作流執(zhí)行過程中,根據(jù)工作流的執(zhí)行情況調(diào)整任務(wù)的執(zhí)行時限和使用的可搶占實例資源。最后,在為任務(wù)購買可搶占實例時,通過成本估計和價格預(yù)測成本最低的方式,在單任務(wù)的層次上降低計算成本。
接下來對本文方法進(jìn)行建模,首先做出如下假設(shè):
(1)市場的可搶占實例資源充足,在購買可搶占實例時,只要用戶出價大于或等于市場價格即可獲得可搶占實例。
(2)可搶占實例只有可能在任務(wù)結(jié)束時或者市場價格大于用戶出價時才會被釋放。當(dāng)可搶占實例被服務(wù)提供商釋放時,會產(chǎn)生一定的成本,該成本為實例從最近檢查點到被釋放時產(chǎn)生的計算成本。
(3)可搶占實例的價格每小時變化一次,而且其收費也是按照小時收費。
(4)決策只針對單個任務(wù),不會影響可搶占實例市場的價格變化。
(5)每小時執(zhí)行一次檢查點,并忽略進(jìn)行檢查的時間和從檢查恢復(fù)的時間。
(6)忽略可搶占實例的性能變化,以及傳輸所需要的時間。
一般來說,工作流調(diào)度的原則是讓工作流盡可能使用價格低廉的資源。對于按需付費實例,其3xlarge、2xlarge、xlarge的關(guān)鍵指標(biāo),如CPU數(shù)量、內(nèi)存大小,分別為large的6,4,2倍,而價格也是如此,所以單位計算資源的價格相同。但是,對于可搶占實例這類價格一直在變化的資源,很難直接判斷資源的使用優(yōu)先級。所以,本文根據(jù)可搶占實例的歷史平均價格,對可搶占實例進(jìn)行排序。
圖 2是可用區(qū)(可用區(qū)是指云計算提供商的物理數(shù)據(jù)中心內(nèi),電力和網(wǎng)絡(luò)相互獨立的物理區(qū)域)cn-beijing-h的不同規(guī)格可搶占實例的平均價格相對于按需付費實例的價格??梢园l(fā)現(xiàn),其中3xlarge的價格最高,然后2xlarge、xlarge、large的逐漸降低,但降低幅度也越來越小。為了降低工作流的計算費用,整個工作流應(yīng)該盡可能使用較低規(guī)格的實例。同時,還需要考慮各個規(guī)格之間的差價,工作流中各個任務(wù)的規(guī)格不能相差太大。除此之外,還需要考慮到各個任務(wù)對工作流執(zhí)行時長的影響。在這里本文提出了BFRC(Branch First Reduce Cost)工作流資源調(diào)度算法。
Figure 2 Relative price of spot instances(compared with the price of on-demand instances of the same specifications)圖2 可搶占實例的相對價格(與同規(guī)格的按需付費實例價格相比)
根據(jù)上述可搶占實例價格特點,首先進(jìn)行工作流的配置和調(diào)度。配置算法如算法1所示:
算法1工作流資源調(diào)度(BFRC)
輸入:工作流、工作流執(zhí)行時限、可供選擇的資源、可搶占實例的歷史價格數(shù)據(jù)。
輸出:工作流的資源調(diào)度。
步驟1工作流的全部任務(wù)選擇最貴的資源(即算力最強),計算整體工作流的執(zhí)行時間;
步驟2對工作流的各個任務(wù)進(jìn)行分類;
步驟3根據(jù)工作流執(zhí)行時限和工作流的執(zhí)行時間,分配各個任務(wù)的執(zhí)行時限;
步驟4根據(jù)任務(wù)的執(zhí)行時限,為各個任務(wù)選擇合適的可搶占實例;
步驟5按照特定優(yōu)先級,調(diào)整各個任務(wù)的資源使用。
步驟1是在工作流執(zhí)行前的初始化配置,主要是為了得到整體工作流的執(zhí)行時間,由此確定工作流是否能在執(zhí)行時限內(nèi)完成。
步驟2是對工作流中的任務(wù)進(jìn)行分類,如圖 3所示,這里借鑒了Yu等人[14]的分類方法,將任務(wù)分為簡單任務(wù)和同步任務(wù)2類:前驅(qū)或者后繼不止一個的任務(wù)分類為同步任務(wù),其它任務(wù)為簡單任務(wù)。同步任務(wù)在工作流執(zhí)行的過程中起到了對其他任務(wù)的同步作用,這類任務(wù)對于工作流的影響比其他任務(wù)更明顯。然后對簡單任務(wù)進(jìn)行篩選,如果簡單任務(wù)為某同步任務(wù)的唯一后繼或者唯一前驅(qū),那么調(diào)整該簡單任務(wù)所產(chǎn)生的影響和調(diào)整其相鄰的同步任務(wù)所產(chǎn)生的影響類似,所以該簡單任務(wù)也應(yīng)該歸屬于同步任務(wù)。
Figure 3 Classification of workflow task圖3 工作流任務(wù)分類
步驟3和步驟4是按照各個任務(wù)的工作量,分配相應(yīng)的執(zhí)行時間,這樣使得每個任務(wù)的執(zhí)行時間和選擇的資源盡可能平均。
步驟5是為了利用工作流中剩余空閑時間,從而進(jìn)一步降低各個任務(wù)的規(guī)格。如圖 4中的任務(wù)A、B分別有1.7 h和1.6 h的執(zhí)行時限,各自的計算時間為1.0 h,如果將時間碎片合并利用,A的計算成本可以進(jìn)一步降低。除此之外,不同類型的任務(wù)對工作流計算的影響程度也不同,對此我們更傾向于優(yōu)先降低簡單任務(wù)的節(jié)點規(guī)格,如圖 3所示,可以同時降低相同起點和終點的多個簡單任務(wù)的計算成本。
Figure 4 Using time fragments in the workflow圖4 利用工作流中的時間碎片
當(dāng)完成工作流執(zhí)行前的資源配置之后,需要考慮如何在工作流執(zhí)行時使用可搶占實例,即設(shè)置任務(wù)的執(zhí)行時限來減少計算成本。首先要保證每個任務(wù)的執(zhí)行時限不會導(dǎo)致工作流超時,即每個任務(wù)都不能晚于最晚完成時間完成計算。其次圖 5表示理想狀態(tài)下,每種可搶占實例在不同執(zhí)行時限的情況下的最低價格。從圖5中可以發(fā)現(xiàn),價格和執(zhí)行時限有著非常大的關(guān)系,除了large和xlarge這2種可搶占實例的價格范圍相近,其他類型之間的價格范圍差距很大??紤]到這是理想情況下的結(jié)果,實際上各種出價策略下各個可搶占實例的價格變化可能會更小。因此,對于每個任務(wù)增加執(zhí)行時限的比例不如降低規(guī)格所帶來的成本降低更大。在這種情況下,每個任務(wù)的執(zhí)行時限不應(yīng)該過大,例如當(dāng)任務(wù)的執(zhí)行時限和計算時間的比例超過1.5倍時,反而有可能會出現(xiàn)如圖4所示的時間碎片過多的情況?;蛘咴谌蝿?wù)的執(zhí)行時限比較大的情況下將計算資源調(diào)整為更加廉價的可搶占實例。綜上,對于每個任務(wù)的執(zhí)行時限有2個上限,只需要選擇其中比較小的作為任務(wù)的執(zhí)行時限即可。
Figure 5 Spot instance relative minimum price圖5 可搶占實例最低相對價格
確定任務(wù)所選擇的可搶占實例類型之后,還需要考慮如何降低可搶占實例的購買成本,從而在工作流執(zhí)行時限內(nèi)降低計算成本。這樣問題就變?yōu)閱稳蝿?wù)的可搶占實例購買問題,本文給出了不同出價的成本估計方法,通過估計不同出價的成本可以得到成本最低的最優(yōu)出價。
首先假設(shè)該計算任務(wù)一共需要ch完成,執(zhí)行時限為th,假設(shè)代價函數(shù)為cost,那么根據(jù)可搶占實例的特點可以設(shè)置一些邊界條件。
首先要保證該任務(wù)不能超時,還要考慮到可搶占實例可能會由于市場資源緊張而出現(xiàn)購買失敗或者被釋放的情況,所以在c=t時,必須使用按需付費實例來進(jìn)行計算,此時cost=priceod*c,其中priceod是按需付費實例的價格。
s代表可搶占實例的市場價格,則s∈(0,priceod]。當(dāng)c=t-1時,為了避免使用按需付費實例,用戶出價應(yīng)為priceod。根據(jù)上文的假設(shè),可搶占實例一定會購買成功,且不會被釋放,可以得到:
(1)
其中si代表ih后可搶占實例的市場價格。
cost(t,b)=g(b)*E(s)+(1-g(b))*
(2)
其中s≤b,如此可以將一個問題進(jìn)行遞歸求解。當(dāng)c≥2時,還需要考慮剩余的任務(wù)要如何處理,所以相比于c=1的情況,在成功購買時,這里又多了一項cost(c-1,t-1,b),其中c代表所需要的計算時間,t代表執(zhí)行時限,b代表用戶出價。因此,計算成本可以表示為:
cost(c,t,b)=g(b)*
E(s+cost(c-1,t-1,b))+(1-g(b))*
(3)
在得到了估計不同出價時計算成本的遞歸求解公式之后,接下來的問題就是如何得到其中的g(b)和E(s)等函數(shù)。這些函數(shù)很明顯和可搶占實例的價格有著很大的關(guān)系,如果可以預(yù)測可搶占實例的未來價格,便可從中得到這些函數(shù)的計算結(jié)果。
這里使用馬爾科夫模型來預(yù)測可搶占實例的價格變化。首先根據(jù)已有的歷史價格數(shù)據(jù)得到概率轉(zhuǎn)移矩陣P,其中pss′代表可搶占實例價格從s變?yōu)閟′的概率,然后通過該矩陣來預(yù)測未來價格。由于未來價格還和當(dāng)前價格有關(guān),所以cost、g(b)等函數(shù)需要增加參數(shù)進(jìn)行計算,其代表當(dāng)前可搶占實例的價格??梢缘玫剑?/p>
(4)
(5)
將式(4)和式(5)代入式(3)中化簡得到:
cost(c,t,b,s)=
(6)
如果增加實例被釋放或者購買失敗的成本,則式(6)可以寫為:
cost(c,t,b,s)=
(7)
其中,r是可搶占實例回收產(chǎn)生的成本。
如此便得到了計算不同出價的成本估計函數(shù),用戶出價b為成本估計的最小值:
(8)
工作流:本文使用由Pegasus[19]提供的具有代表性的工作流來進(jìn)行測試,包括CyberShake、Sipht、Inspiral和Epigenomics。
資源設(shè)置:使用阿里云的不同可用區(qū)的數(shù)據(jù),包括cn-beijing-h(北京地區(qū)h可用區(qū))、cn-shanghai-f(上海地區(qū)f可用區(qū))和cn-shenzhen-e(深圳地區(qū)e可用區(qū))。本文使用g6系列的實例進(jìn)行測試。此外,歷史價格為可搶占實例在2019年10月10日到2019年12月19日的價格。這些歷史價格的數(shù)據(jù)特征如表1~表3所示。
Table 1 Available zone cn-beijing-h g6 family price characteristics
對比算法:本文選取Poola等人[17]提出的AIB(Aggressive with Intelligent Bidding)算法作為對比,該工作也是利用可搶占實例來降低工作流
Table 2 Available zone cn-shanghai-f g6 family price characteristics
Table 3 Available zone cn-shenzhen-e g6 family price characteristics
的計算成本?;鶞?zhǔn)實驗為全部都用按需付費實例執(zhí)行工作流。在實驗驗證中,每組實驗進(jìn)行30次取平均值,每次都隨機選擇開始時間。每次測試的工作流執(zhí)行時限大小從工作流執(zhí)行時間的1.1倍開始,然后逐漸遞增到3.0倍。
最低成本下限:為了更好地理解不同算法對工作流計算成本的節(jié)省效果,這里定義了最低成本下限。為了簡化計算,假設(shè)工作流從開始到結(jié)束只有一條路徑,那么其配置最多有2種可搶占實例,例如只有3xlarge和2xlarge,所以其配置比例變化可以近似為如下不等式:
(9)
Figure 6 Relative cost of WCSSI and AIB, the benchmark is the cost of all on-demand instances圖6 WCSSI與AIB的相對成本,基準(zhǔn)為全部使用按需付費實例的成本
其中,w為計算任務(wù)大小,d為最長計算時間(deadline),t1、t2分別是2種可搶占實例的執(zhí)行時間,c1、c2分別是2種可搶占實例每小時能夠完成計算任務(wù)的大小,p1、p2分別是2種可搶占實例每小時的價格,不妨假設(shè)c1>c2,根據(jù)圖 5所展示的關(guān)系,有1 (10) 實驗結(jié)果如圖 6所示,其中WCSSI的成本比AIB的成本更低。在圖 6中,WCSSI的成本是基線成本的 10.1%~19.8%(最高可節(jié)省89.9%),平均為11.7%;相對于AIB為76.8%~104.2%(最高可節(jié)省23.2%),平均為94.2%。這得益于對于任務(wù)的分類處理,通過優(yōu)先對簡單任務(wù)調(diào)整可搶占實例類型,使得更多簡單任務(wù)也因此受益,從而使得工作流使用更多價格較低的可搶占實例,進(jìn)一步降低工作流的計算成本。而AIB則是為先執(zhí)行的任務(wù)分配廉價資源,再對后執(zhí)行的任務(wù)分配。這樣的結(jié)果是先執(zhí)行的任務(wù)可搶占實例價格很低,但是執(zhí)行時間特別長,而后執(zhí)行的任務(wù)只能使用較為昂貴的資源,從而增大了工作流的計算成本,這也是在某個區(qū)間內(nèi)工作流執(zhí)行時限越大成本反而上升的原因之一。對于結(jié)構(gòu)復(fù)雜的工作流,例如CyberShake,簡單任務(wù)節(jié)點很少,甚至沒有簡單任務(wù)節(jié)點。這種情況下WCSSI的性能和AIB的性能類似,但是受益于資源平均分配的策略,WCSSI能夠有效避免出現(xiàn)反常成本上升問題。 表4是WCSSI表現(xiàn)優(yōu)于AIB的比例,在大部分工作流和可用區(qū)價格數(shù)據(jù)下都達(dá)到了90%以上(在Inspiral工作流與cn-shenzhen-e價格數(shù)據(jù)上,WCSSI優(yōu)于AIB比例最低,為65.2%)。在WCSSI成本高于AIB的情況下,成本高出的平均比例為1.1%,差距并不明顯。在其它WCSSI優(yōu)于AIB的情況下,成本比例為89.7%~98.2%,平均為93.5%。在所有工作流和可用區(qū)價格數(shù)據(jù)組合下,當(dāng)WCSSI成本高于AIB時,成本高出比例為0.5%~1.9%,平均為1.0%。 Table 4 WCSSI outperforms AIB experiment ratio 除此之外,WCSSI的成本最終收斂到基線成本的10%,結(jié)合圖 5所示的平均價格,這可能代表計算成本優(yōu)化已經(jīng)接近上限,接下來將對此進(jìn)行分析。 從圖 6e和圖6f可以發(fā)現(xiàn),WCSSI的折線軌跡基本和最低成本下限一致??紤]到工作流Inspiral 中非簡單任務(wù)的比重極少,且各個分支比重相當(dāng),可以近似為多個假設(shè)的工作流混合而成,所以認(rèn)為WCSSI已經(jīng)達(dá)到了最低成本下限。 而圖 6g和圖 6i中WCSSI成本低于最低成本下限,這是因為Epigenomics不符合且不可近似為上述假設(shè)的工作流,簡單任務(wù)和非簡單任務(wù)在工作流中都有著很大的比重。由于WCSSI優(yōu)先降低簡單任務(wù)的成本,所以低成本可搶占實例在工作流中所占的比重會比估計的要高,從而使得WCSSI的運行成本低于最低成本下限。 綜上,WCSSI得出的工作流計算成本可以達(dá)到最低成本下限。 云計算中可搶占實例的出現(xiàn),為降低工作流執(zhí)行成本提供了巨大優(yōu)化空間,Poola等人[17]通過結(jié)合使用可搶占實例和按需付費實例,以在滿足執(zhí)行時限的要求下降低工作流的計算成本。其使用激進(jìn)算法和保守算法來估計工作流中各個任務(wù)的執(zhí)行時間,然后使用計算得到的最晚執(zhí)行時限(按需付費下)來決定工作流在執(zhí)行的過程中是否可以使用可搶占實例來降低成本。WCSSI相比于該算法,考慮了不同任務(wù)對于工作流執(zhí)行時限的不同影響,通過對任務(wù)進(jìn)行差異化處理可以更好地節(jié)省工作流計算成本。在購買可搶占實例的策略上,Zafer等人[12]將其建模為動態(tài)規(guī)劃問題來得到最優(yōu)出價策略,但是其沒有考慮實例被釋放所帶來的成本,且價格模型比較簡單。本文提出的成本估計方法則考慮了實例釋放所帶來的成本,且使用馬爾科夫模型,更加貼近實際情況。 本文提出了滿足工作流執(zhí)行時限的可搶占虛擬機實例配置和調(diào)度方法,可以極大地降低工作流的計算成本。本文選取了有代表性的工作流負(fù)載,并在阿里云真實數(shù)據(jù)上進(jìn)行了實驗驗證。實驗結(jié)果顯示,本文提出的工作流調(diào)度方法可以最高節(jié)省89.9%的成本開銷。在未來的工作中,我們會考慮可搶占實例的性能變化因素,并在工作流配置和調(diào)度中考慮其對執(zhí)行時限的影響。4.2 實驗結(jié)果與分析
5 相關(guān)工作
6 結(jié)束語