廖建錦，孫慶驍，楊海龍，欒鐘治，錢(qián)德沛

(北京航空航天大學(xué)計(jì)算機(jī)學(xué)院，北京 100191)

1 引言

科學(xué)應(yīng)用中不同計(jì)算任務(wù)之間往往存在復(fù)雜的依賴關(guān)系，為了更好地刻畫(huà)不同計(jì)算任務(wù)之間的依賴關(guān)系，這些計(jì)算任務(wù)通常被組織成工作流，如CyberShake[1]和MapReduce[2]。工作流通常被表示成有向無(wú)環(huán)圖DAG(Directed Acyclic Graph)，在本文場(chǎng)景下，DAG和工作流可以互相替換。此外，隨著云計(jì)算市場(chǎng)的蓬勃發(fā)展，將工作流放置到云上計(jì)算可以更好地滿足科學(xué)應(yīng)用不斷增加的計(jì)算需求。亞馬遜云服務(wù)AWS(Amazon Web Services)、阿里云等云計(jì)算服務(wù)提供商可以提供大量大小不一且可靠的虛擬機(jī)計(jì)算資源。

然而，將工作流放置到云上計(jì)算存在著幾個(gè)重要的挑戰(zhàn)。一方面是工作流調(diào)度的復(fù)雜性，如何將虛擬機(jī)資源映射到各個(gè)任務(wù)以滿足工作流執(zhí)行時(shí)限的要求；另一方面，將工作流放到云上計(jì)算會(huì)產(chǎn)生大量的經(jīng)濟(jì)成本，如何在滿足工作流執(zhí)行時(shí)限的前提下降低成本也是個(gè)難題。其中，對(duì)于執(zhí)行時(shí)限內(nèi)降低工作流成本的問(wèn)題，現(xiàn)有的研究工作提出了很多方法對(duì)工作流的虛擬機(jī)資源進(jìn)行優(yōu)化。例如，Abrishami等人[3]使用部分關(guān)鍵路徑解決虛擬機(jī)資源的選擇問(wèn)題，但是其使用的虛擬機(jī)資源大部分是按需付費(fèi)虛擬機(jī)實(shí)例[4]，這類計(jì)算資源較為可靠但價(jià)格固定，其成本優(yōu)化空間相當(dāng)有限。云計(jì)算服務(wù)提供商也提供了可搶占虛擬機(jī)實(shí)例[5,6]，其價(jià)格一般為按量按需付費(fèi)實(shí)例的10%～20%。如果工作流虛擬機(jī)資源配置中可以利用好可搶占實(shí)例，會(huì)極大地減少工作流的計(jì)算成本。雖然可搶占實(shí)例價(jià)格低廉，但是其在執(zhí)行過(guò)程中存在一定概率被云服務(wù)商收回釋放，導(dǎo)致工作流無(wú)法按時(shí)完成。因此，如何在工作流執(zhí)行過(guò)程中，可靠地利用可搶占實(shí)例，在滿足執(zhí)行時(shí)限要求的情況下，降低計(jì)算成本是一個(gè)新的挑戰(zhàn)。

針對(duì)上述挑戰(zhàn)，本文提出了滿足工作流執(zhí)行時(shí)限的可搶占虛擬機(jī)實(shí)例配置和調(diào)度方法，可以在滿足工作流最長(zhǎng)執(zhí)行時(shí)限的前提下，最小化工作流執(zhí)行的計(jì)算成本。本文提出的方法具有重要的實(shí)際經(jīng)濟(jì)價(jià)值。具體而言，本文的主要貢獻(xiàn)如下所示：

(1)提出了基于馬爾科夫模型的可搶占虛擬機(jī)實(shí)例價(jià)格預(yù)測(cè)模型。

(2)提出了針對(duì)單任務(wù)的成本估計(jì)方法。通過(guò)估計(jì)不同出價(jià)策略下的工作流計(jì)算成本，從中選擇最優(yōu)出價(jià)策略。

(3)提出了基于可搶占虛擬機(jī)實(shí)例價(jià)格特點(diǎn)的工作流配置和調(diào)度方法。

(4)基于阿里云真實(shí)數(shù)據(jù)，對(duì)本文提出的方法進(jìn)行模擬驗(yàn)證，并與已有算法進(jìn)行對(duì)比。

2 研究背景

2.1 可搶占虛擬機(jī)實(shí)例

可搶占實(shí)例是云計(jì)算市場(chǎng)中較為特殊的一類資源，其價(jià)格低廉，但生命周期不再只由用戶決定，還和市場(chǎng)有關(guān)[5,7]。用戶需要提供出價(jià)以創(chuàng)建可搶占實(shí)例，而創(chuàng)建可搶占實(shí)例是否成功還和市場(chǎng)價(jià)格以及資源是否充足有關(guān)。當(dāng)用戶出價(jià)大于市場(chǎng)價(jià)格且資源充足的情況下，用戶可以成功創(chuàng)建可搶占實(shí)例。其中市場(chǎng)價(jià)格取決于市場(chǎng)供需關(guān)系，隨時(shí)間發(fā)生波動(dòng)。在用戶成功創(chuàng)建可搶占實(shí)例后，云計(jì)算服務(wù)提供商會(huì)不斷檢查用戶出價(jià)和市場(chǎng)價(jià)格，當(dāng)市場(chǎng)價(jià)格大于用戶出價(jià)或資源不足，那么該用戶的可搶占實(shí)例就會(huì)被云計(jì)算服務(wù)提供商收回并釋放。由此可知，當(dāng)用戶出價(jià)較高時(shí)，可搶占實(shí)例會(huì)更加穩(wěn)定，但相應(yīng)地價(jià)格也會(huì)更加昂貴。

可搶占實(shí)例的出價(jià)策略主要分2種：靜態(tài)出價(jià)策略和動(dòng)態(tài)出價(jià)策略。靜態(tài)出價(jià)策略一般目標(biāo)比較單一，常見(jiàn)的有依據(jù)歷史價(jià)格出價(jià)和預(yù)測(cè)未來(lái)價(jià)格出價(jià)。Andrzejak等人[8]提出了一種概率模型，其證明當(dāng)出價(jià)為最低價(jià)或者平均價(jià)格時(shí)，一般規(guī)律是出價(jià)越高成本越高，但相應(yīng)地完成時(shí)間會(huì)更短。Baughman等人[9]利用LSTM預(yù)測(cè)未來(lái)價(jià)格變化，而Fabra等人[10]首先對(duì)各個(gè)可用區(qū)進(jìn)行分類，然后根據(jù)其不同的價(jià)格特點(diǎn)分別建模預(yù)測(cè)價(jià)格?？偠灾?，靜態(tài)出價(jià)策略比較簡(jiǎn)單，出價(jià)的高低對(duì)應(yīng)著任務(wù)對(duì)時(shí)間和可靠性的要求。

Figure 1 Spot instance configuration and scheduling method proposed in this paper圖1 本文提出的可搶占虛擬機(jī)實(shí)例配置和調(diào)度方法WCSSI

相比靜態(tài)策略，動(dòng)態(tài)策略可以協(xié)同優(yōu)化計(jì)算成本和完成時(shí)間。對(duì)此，許多研究提出了在不同約束條件下的出價(jià)策略，比如限制成本或者計(jì)算時(shí)間等。Kamiński等人[11]提出了一種自適應(yīng)的出價(jià)策略，該策略可以同時(shí)降低計(jì)算成本和實(shí)例回收帶來(lái)的延遲。Zafer等人[12]則將此類問(wèn)題建模為一般的離散時(shí)間動(dòng)態(tài)規(guī)劃問(wèn)題，并提出了最優(yōu)出價(jià)策略，該策略可以在固定時(shí)間內(nèi)最大程度地降低計(jì)算成本。相對(duì)而言，動(dòng)態(tài)出價(jià)策略可以在一定約束條件下獲得比較好的結(jié)果，但是建模和求解會(huì)相對(duì)比較復(fù)雜。

2.2 工作流調(diào)度優(yōu)化

眾所周知，工作流調(diào)度是一個(gè)NP-complete問(wèn)題[13]。當(dāng)工作流放置到云上進(jìn)行計(jì)算的時(shí)候，成本是研究關(guān)注的重點(diǎn)問(wèn)題之一。在云上進(jìn)行工作流調(diào)度，比較常見(jiàn)的場(chǎng)景包括有限時(shí)間內(nèi)最小化成本和有限成本內(nèi)最小化執(zhí)行時(shí)間。除此之外，還有研究討論云計(jì)算實(shí)例的計(jì)算能力和工作流的魯棒性問(wèn)題。

對(duì)于在有限時(shí)間內(nèi)最小化成本的問(wèn)題，一般的方法是選擇較為廉價(jià)的資源分配給非關(guān)鍵路徑上的任務(wù)，如此便可以在不增加工作流整體運(yùn)行時(shí)間的基礎(chǔ)上降低成本，其中比較常見(jiàn)的方式是通過(guò)時(shí)間分配來(lái)選擇資源。例如，Yu等人[14]根據(jù)工作流中的依賴關(guān)系對(duì)各個(gè)任務(wù)進(jìn)行分類，然后根據(jù)每個(gè)任務(wù)的類別來(lái)分配時(shí)間，最后按照分配的時(shí)間來(lái)為任務(wù)選擇不同的資源。除此之外，也有研究利用關(guān)鍵路徑來(lái)選擇資源。例如，Gao等人[15]利用關(guān)鍵路徑和最短路徑對(duì)工作流中的各個(gè)任務(wù)進(jìn)行分類，然后按照一定的優(yōu)先級(jí)來(lái)逐步減少各個(gè)任務(wù)的計(jì)算成本，從而降低整個(gè)工作流的成本。Abrishami等人[3]則是利用部分關(guān)鍵路徑并通過(guò)遞歸的方式來(lái)決定各個(gè)任務(wù)的資源分配。

鑒于可搶占實(shí)例比較廉價(jià)，部分學(xué)者在工作流中加入可搶占實(shí)例以降低工作流成本。Monge等人[16]提出了CMI(Cloud Multi-objective Intelligence)，其同時(shí)考慮了工作流的時(shí)間和出錯(cuò)概率，通過(guò)遺傳算法求解。Poola等人[17]則是通過(guò)啟發(fā)式算法來(lái)使用搶占式實(shí)例，進(jìn)而降低工作流的成本。Zhou等人[18]用A star算法進(jìn)行剪枝，然后調(diào)整各個(gè)任務(wù)的資源分配，從而以一定的概率使工作流不會(huì)超時(shí)。這些算法對(duì)于搶占式實(shí)例的出價(jià)大都以盡可能保證能夠獲得可搶占實(shí)例為主，并沒(méi)有考慮進(jìn)一步降低有限時(shí)間內(nèi)獲得可搶占實(shí)例的成本。另外，由于期限的不同，可搶占實(shí)例的期望價(jià)格也不一樣，當(dāng)工作流執(zhí)行時(shí)限過(guò)大時(shí)會(huì)出現(xiàn)邊際效應(yīng)，會(huì)帶來(lái)虛擬機(jī)利用率的問(wèn)題。此外，不同可搶占實(shí)例的價(jià)格差異很大，這些差異很大程度上影響工作流整體的配置。上述算法如果能考慮到這些問(wèn)題，那么可以進(jìn)一步降低工作流的成本。

3 WCSSI方法設(shè)計(jì)實(shí)現(xiàn)

3.1 總體設(shè)計(jì)

本文提出的可搶占虛擬機(jī)實(shí)例配置和調(diào)度方法WCSSI(Workflow Cost Saver based on Spot Instance)的整體結(jié)構(gòu)如圖 1所示，具體包括價(jià)格預(yù)測(cè)、成本估計(jì)和工作流配置和調(diào)度3個(gè)部分。首先根據(jù)可搶占實(shí)例的價(jià)格特點(diǎn)，在工作流執(zhí)行前通過(guò)工作流配置算法確定工作流中任務(wù)所選擇的可搶占實(shí)例，在工作流配置的層次上降低計(jì)算成本。之后在工作流執(zhí)行過(guò)程中，根據(jù)工作流的執(zhí)行情況調(diào)整任務(wù)的執(zhí)行時(shí)限和使用的可搶占實(shí)例資源。最后，在為任務(wù)購(gòu)買(mǎi)可搶占實(shí)例時(shí)，通過(guò)成本估計(jì)和價(jià)格預(yù)測(cè)成本最低的方式，在單任務(wù)的層次上降低計(jì)算成本。

接下來(lái)對(duì)本文方法進(jìn)行建模，首先做出如下假設(shè)：

(1)市場(chǎng)的可搶占實(shí)例資源充足，在購(gòu)買(mǎi)可搶占實(shí)例時(shí)，只要用戶出價(jià)大于或等于市場(chǎng)價(jià)格即可獲得可搶占實(shí)例。

(2)可搶占實(shí)例只有可能在任務(wù)結(jié)束時(shí)或者市場(chǎng)價(jià)格大于用戶出價(jià)時(shí)才會(huì)被釋放。當(dāng)可搶占實(shí)例被服務(wù)提供商釋放時(shí)，會(huì)產(chǎn)生一定的成本，該成本為實(shí)例從最近檢查點(diǎn)到被釋放時(shí)產(chǎn)生的計(jì)算成本。

(3)可搶占實(shí)例的價(jià)格每小時(shí)變化一次，而且其收費(fèi)也是按照小時(shí)收費(fèi)。

(4)決策只針對(duì)單個(gè)任務(wù)，不會(huì)影響可搶占實(shí)例市場(chǎng)的價(jià)格變化。

(5)每小時(shí)執(zhí)行一次檢查點(diǎn)，并忽略進(jìn)行檢查的時(shí)間和從檢查恢復(fù)的時(shí)間。

(6)忽略可搶占實(shí)例的性能變化，以及傳輸所需要的時(shí)間。

3.2 工作流配置和調(diào)度

一般來(lái)說(shuō)，工作流調(diào)度的原則是讓工作流盡可能使用價(jià)格低廉的資源。對(duì)于按需付費(fèi)實(shí)例，其3xlarge、2xlarge、xlarge的關(guān)鍵指標(biāo)，如CPU數(shù)量、內(nèi)存大小，分別為large的6,4,2倍，而價(jià)格也是如此，所以單位計(jì)算資源的價(jià)格相同。但是，對(duì)于可搶占實(shí)例這類價(jià)格一直在變化的資源，很難直接判斷資源的使用優(yōu)先級(jí)。所以，本文根據(jù)可搶占實(shí)例的歷史平均價(jià)格，對(duì)可搶占實(shí)例進(jìn)行排序。

圖 2是可用區(qū)(可用區(qū)是指云計(jì)算提供商的物理數(shù)據(jù)中心內(nèi)，電力和網(wǎng)絡(luò)相互獨(dú)立的物理區(qū)域)cn-beijing-h的不同規(guī)格可搶占實(shí)例的平均價(jià)格相對(duì)于按需付費(fèi)實(shí)例的價(jià)格?？梢园l(fā)現(xiàn)，其中3xlarge的價(jià)格最高，然后2xlarge、xlarge、large的逐漸降低，但降低幅度也越來(lái)越小。為了降低工作流的計(jì)算費(fèi)用，整個(gè)工作流應(yīng)該盡可能使用較低規(guī)格的實(shí)例。同時(shí)，還需要考慮各個(gè)規(guī)格之間的差價(jià)，工作流中各個(gè)任務(wù)的規(guī)格不能相差太大。除此之外，還需要考慮到各個(gè)任務(wù)對(duì)工作流執(zhí)行時(shí)長(zhǎng)的影響。在這里本文提出了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 可搶占實(shí)例的相對(duì)價(jià)格(與同規(guī)格的按需付費(fèi)實(shí)例價(jià)格相比)

根據(jù)上述可搶占實(shí)例價(jià)格特點(diǎn)，首先進(jìn)行工作流的配置和調(diào)度。配置算法如算法1所示：

算法1工作流資源調(diào)度(BFRC)

輸入：工作流、工作流執(zhí)行時(shí)限、可供選擇的資源、可搶占實(shí)例的歷史價(jià)格數(shù)據(jù)。

輸出：工作流的資源調(diào)度。

步驟1工作流的全部任務(wù)選擇最貴的資源(即算力最強(qiáng))，計(jì)算整體工作流的執(zhí)行時(shí)間；

步驟2對(duì)工作流的各個(gè)任務(wù)進(jìn)行分類；

步驟3根據(jù)工作流執(zhí)行時(shí)限和工作流的執(zhí)行時(shí)間，分配各個(gè)任務(wù)的執(zhí)行時(shí)限；

步驟4根據(jù)任務(wù)的執(zhí)行時(shí)限，為各個(gè)任務(wù)選擇合適的可搶占實(shí)例；

步驟5按照特定優(yōu)先級(jí)，調(diào)整各個(gè)任務(wù)的資源使用。

步驟1是在工作流執(zhí)行前的初始化配置，主要是為了得到整體工作流的執(zhí)行時(shí)間，由此確定工作流是否能在執(zhí)行時(shí)限內(nèi)完成。

步驟2是對(duì)工作流中的任務(wù)進(jìn)行分類，如圖 3所示，這里借鑒了Yu等人[14]的分類方法，將任務(wù)分為簡(jiǎn)單任務(wù)和同步任務(wù)2類：前驅(qū)或者后繼不止一個(gè)的任務(wù)分類為同步任務(wù)，其它任務(wù)為簡(jiǎn)單任務(wù)。同步任務(wù)在工作流執(zhí)行的過(guò)程中起到了對(duì)其他任務(wù)的同步作用，這類任務(wù)對(duì)于工作流的影響比其他任務(wù)更明顯。然后對(duì)簡(jiǎn)單任務(wù)進(jìn)行篩選，如果簡(jiǎn)單任務(wù)為某同步任務(wù)的唯一后繼或者唯一前驅(qū)，那么調(diào)整該簡(jiǎn)單任務(wù)所產(chǎn)生的影響和調(diào)整其相鄰的同步任務(wù)所產(chǎn)生的影響類似，所以該簡(jiǎn)單任務(wù)也應(yīng)該歸屬于同步任務(wù)。

Figure 3 Classification of workflow task圖3 工作流任務(wù)分類

步驟3和步驟4是按照各個(gè)任務(wù)的工作量，分配相應(yīng)的執(zhí)行時(shí)間，這樣使得每個(gè)任務(wù)的執(zhí)行時(shí)間和選擇的資源盡可能平均。

步驟5是為了利用工作流中剩余空閑時(shí)間，從而進(jìn)一步降低各個(gè)任務(wù)的規(guī)格。如圖 4中的任務(wù)A、B分別有1.7 h和1.6 h的執(zhí)行時(shí)限,各自的計(jì)算時(shí)間為1.0 h，如果將時(shí)間碎片合并利用，A的計(jì)算成本可以進(jìn)一步降低。除此之外，不同類型的任務(wù)對(duì)工作流計(jì)算的影響程度也不同，對(duì)此我們更傾向于優(yōu)先降低簡(jiǎn)單任務(wù)的節(jié)點(diǎn)規(guī)格，如圖 3所示，可以同時(shí)降低相同起點(diǎn)和終點(diǎn)的多個(gè)簡(jiǎn)單任務(wù)的計(jì)算成本。

Figure 4 Using time fragments in the workflow圖4 利用工作流中的時(shí)間碎片

當(dāng)完成工作流執(zhí)行前的資源配置之后，需要考慮如何在工作流執(zhí)行時(shí)使用可搶占實(shí)例，即設(shè)置任務(wù)的執(zhí)行時(shí)限來(lái)減少計(jì)算成本。首先要保證每個(gè)任務(wù)的執(zhí)行時(shí)限不會(huì)導(dǎo)致工作流超時(shí)，即每個(gè)任務(wù)都不能晚于最晚完成時(shí)間完成計(jì)算。其次圖 5表示理想狀態(tài)下，每種可搶占實(shí)例在不同執(zhí)行時(shí)限的情況下的最低價(jià)格。從圖5中可以發(fā)現(xiàn)，價(jià)格和執(zhí)行時(shí)限有著非常大的關(guān)系，除了large和xlarge這2種可搶占實(shí)例的價(jià)格范圍相近，其他類型之間的價(jià)格范圍差距很大?？紤]到這是理想情況下的結(jié)果，實(shí)際上各種出價(jià)策略下各個(gè)可搶占實(shí)例的價(jià)格變化可能會(huì)更小。因此，對(duì)于每個(gè)任務(wù)增加執(zhí)行時(shí)限的比例不如降低規(guī)格所帶來(lái)的成本降低更大。在這種情況下，每個(gè)任務(wù)的執(zhí)行時(shí)限不應(yīng)該過(guò)大，例如當(dāng)任務(wù)的執(zhí)行時(shí)限和計(jì)算時(shí)間的比例超過(guò)1.5倍時(shí)，反而有可能會(huì)出現(xiàn)如圖4所示的時(shí)間碎片過(guò)多的情況?；蛘咴谌蝿?wù)的執(zhí)行時(shí)限比較大的情況下將計(jì)算資源調(diào)整為更加廉價(jià)的可搶占實(shí)例。綜上，對(duì)于每個(gè)任務(wù)的執(zhí)行時(shí)限有2個(gè)上限，只需要選擇其中比較小的作為任務(wù)的執(zhí)行時(shí)限即可。

Figure 5 Spot instance relative minimum price圖5 可搶占實(shí)例最低相對(duì)價(jià)格

3.3 成本估計(jì)方法

確定任務(wù)所選擇的可搶占實(shí)例類型之后，還需要考慮如何降低可搶占實(shí)例的購(gòu)買(mǎi)成本，從而在工作流執(zhí)行時(shí)限內(nèi)降低計(jì)算成本。這樣問(wèn)題就變?yōu)閱稳蝿?wù)的可搶占實(shí)例購(gòu)買(mǎi)問(wèn)題，本文給出了不同出價(jià)的成本估計(jì)方法，通過(guò)估計(jì)不同出價(jià)的成本可以得到成本最低的最優(yōu)出價(jià)。

首先假設(shè)該計(jì)算任務(wù)一共需要ch完成，執(zhí)行時(shí)限為th，假設(shè)代價(jià)函數(shù)為cost，那么根據(jù)可搶占實(shí)例的特點(diǎn)可以設(shè)置一些邊界條件。

首先要保證該任務(wù)不能超時(shí)，還要考慮到可搶占實(shí)例可能會(huì)由于市場(chǎng)資源緊張而出現(xiàn)購(gòu)買(mǎi)失敗或者被釋放的情況，所以在c=t時(shí)，必須使用按需付費(fèi)實(shí)例來(lái)進(jìn)行計(jì)算，此時(shí)cost=priceod*c，其中priceod是按需付費(fèi)實(shí)例的價(jià)格。

s代表可搶占實(shí)例的市場(chǎng)價(jià)格，則s∈(0,priceod]。當(dāng)c=t-1時(shí)，為了避免使用按需付費(fèi)實(shí)例，用戶出價(jià)應(yīng)為priceod。根據(jù)上文的假設(shè)，可搶占實(shí)例一定會(huì)購(gòu)買(mǎi)成功，且不會(huì)被釋放，可以得到：

(1)

其中si代表ih后可搶占實(shí)例的市場(chǎng)價(jià)格。

cost(t,b)=g(b)*E(s)+(1-g(b))*

(2)

其中s≤b，如此可以將一個(gè)問(wèn)題進(jìn)行遞歸求解。當(dāng)c≥2時(shí)，還需要考慮剩余的任務(wù)要如何處理，所以相比于c=1的情況，在成功購(gòu)買(mǎi)時(shí)，這里又多了一項(xiàng)cost(c-1,t-1,b)，其中c代表所需要的計(jì)算時(shí)間，t代表執(zhí)行時(shí)限，b代表用戶出價(jià)。因此，計(jì)算成本可以表示為:

cost(c,t,b)=g(b)*

E(s+cost(c-1,t-1,b))+(1-g(b))*

(3)

3.4 價(jià)格預(yù)測(cè)模型

在得到了估計(jì)不同出價(jià)時(shí)計(jì)算成本的遞歸求解公式之后，接下來(lái)的問(wèn)題就是如何得到其中的g(b)和E(s)等函數(shù)。這些函數(shù)很明顯和可搶占實(shí)例的價(jià)格有著很大的關(guān)系，如果可以預(yù)測(cè)可搶占實(shí)例的未來(lái)價(jià)格，便可從中得到這些函數(shù)的計(jì)算結(jié)果。

這里使用馬爾科夫模型來(lái)預(yù)測(cè)可搶占實(shí)例的價(jià)格變化。首先根據(jù)已有的歷史價(jià)格數(shù)據(jù)得到概率轉(zhuǎn)移矩陣P，其中pss′代表可搶占實(shí)例價(jià)格從s變?yōu)閟′的概率，然后通過(guò)該矩陣來(lái)預(yù)測(cè)未來(lái)價(jià)格。由于未來(lái)價(jià)格還和當(dāng)前價(jià)格有關(guān)，所以cost、g(b)等函數(shù)需要增加參數(shù)進(jìn)行計(jì)算，其代表當(dāng)前可搶占實(shí)例的價(jià)格?？梢缘玫剑?/p>

(4)

(5)

將式(4)和式(5)代入式(3)中化簡(jiǎn)得到：

cost(c,t,b,s)=

(6)

如果增加實(shí)例被釋放或者購(gòu)買(mǎi)失敗的成本，則式(6)可以寫(xiě)為:

cost(c,t,b,s)=

(7)

其中，r是可搶占實(shí)例回收產(chǎn)生的成本。

如此便得到了計(jì)算不同出價(jià)的成本估計(jì)函數(shù)，用戶出價(jià)b為成本估計(jì)的最小值：

(8)

4 實(shí)驗(yàn)評(píng)估

4.1 實(shí)驗(yàn)設(shè)置

工作流：本文使用由Pegasus[19]提供的具有代表性的工作流來(lái)進(jìn)行測(cè)試，包括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系列的實(shí)例進(jìn)行測(cè)試。此外，歷史價(jià)格為可搶占實(shí)例在2019年10月10日到2019年12月19日的價(jià)格。這些歷史價(jià)格的數(shù)據(jù)特征如表1～表3所示。

Table 1 Available zone cn-beijing-h g6 family price characteristics

對(duì)比算法：本文選取Poola等人[17]提出的AIB(Aggressive with Intelligent Bidding)算法作為對(duì)比，該工作也是利用可搶占實(shí)例來(lái)降低工作流

Table 2 Available zone cn-shanghai-f g6 family price characteristics

Table 3 Available zone cn-shenzhen-e g6 family price characteristics

的計(jì)算成本。基準(zhǔn)實(shí)驗(yàn)為全部都用按需付費(fèi)實(shí)例執(zhí)行工作流。在實(shí)驗(yàn)驗(yàn)證中，每組實(shí)驗(yàn)進(jìn)行30次取平均值，每次都隨機(jī)選擇開(kāi)始時(shí)間。每次測(cè)試的工作流執(zhí)行時(shí)限大小從工作流執(zhí)行時(shí)間的1.1倍開(kāi)始，然后逐漸遞增到3.0倍。

最低成本下限：為了更好地理解不同算法對(duì)工作流計(jì)算成本的節(jié)省效果，這里定義了最低成本下限。為了簡(jiǎn)化計(jì)算，假設(shè)工作流從開(kāi)始到結(jié)束只有一條路徑，那么其配置最多有2種可搶占實(shí)例，例如只有3xlarge和2xlarge，所以其配置比例變化可以近似為如下不等式：

(9)

Figure 6 Relative cost of WCSSI and AIB, the benchmark is the cost of all on-demand instances圖6 WCSSI與AIB的相對(duì)成本，基準(zhǔn)為全部使用按需付費(fèi)實(shí)例的成本

其中，w為計(jì)算任務(wù)大小，d為最長(zhǎng)計(jì)算時(shí)間(deadline)，t1、t2分別是2種可搶占實(shí)例的執(zhí)行時(shí)間，c1、c2分別是2種可搶占實(shí)例每小時(shí)能夠完成計(jì)算任務(wù)的大小，p1、p2分別是2種可搶占實(shí)例每小時(shí)的價(jià)格，不妨假設(shè)c1>c2，根據(jù)圖 5所展示的關(guān)系，有1

(10)

4.2 實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)結(jié)果如圖 6所示，其中WCSSI的成本比AIB的成本更低。在圖 6中，WCSSI的成本是基線成本的 10.1%～19.8%(最高可節(jié)省89.9%)，平均為11.7%；相對(duì)于AIB為76.8%～104.2%(最高可節(jié)省23.2%)，平均為94.2%。這得益于對(duì)于任務(wù)的分類處理，通過(guò)優(yōu)先對(duì)簡(jiǎn)單任務(wù)調(diào)整可搶占實(shí)例類型，使得更多簡(jiǎn)單任務(wù)也因此受益，從而使得工作流使用更多價(jià)格較低的可搶占實(shí)例，進(jìn)一步降低工作流的計(jì)算成本。而AIB則是為先執(zhí)行的任務(wù)分配廉價(jià)資源，再對(duì)后執(zhí)行的任務(wù)分配。這樣的結(jié)果是先執(zhí)行的任務(wù)可搶占實(shí)例價(jià)格很低，但是執(zhí)行時(shí)間特別長(zhǎng)，而后執(zhí)行的任務(wù)只能使用較為昂貴的資源，從而增大了工作流的計(jì)算成本，這也是在某個(gè)區(qū)間內(nèi)工作流執(zhí)行時(shí)限越大成本反而上升的原因之一。對(duì)于結(jié)構(gòu)復(fù)雜的工作流，例如CyberShake，簡(jiǎn)單任務(wù)節(jié)點(diǎn)很少，甚至沒(méi)有簡(jiǎn)單任務(wù)節(jié)點(diǎn)。這種情況下WCSSI的性能和AIB的性能類似，但是受益于資源平均分配的策略，WCSSI能夠有效避免出現(xiàn)反常成本上升問(wèn)題。

表4是WCSSI表現(xiàn)優(yōu)于AIB的比例，在大部分工作流和可用區(qū)價(jià)格數(shù)據(jù)下都達(dá)到了90%以上(在Inspiral工作流與cn-shenzhen-e價(jià)格數(shù)據(jù)上，WCSSI優(yōu)于AIB比例最低，為65.2%)。在WCSSI成本高于AIB的情況下，成本高出的平均比例為1.1%，差距并不明顯。在其它WCSSI優(yōu)于AIB的情況下，成本比例為89.7%～98.2%，平均為93.5%。在所有工作流和可用區(qū)價(jià)格數(shù)據(jù)組合下，當(dāng)WCSSI成本高于AIB時(shí)，成本高出比例為0.5%～1.9%，平均為1.0%。

Table 4 WCSSI outperforms AIB experiment ratio

除此之外，WCSSI的成本最終收斂到基線成本的10%，結(jié)合圖 5所示的平均價(jià)格，這可能代表計(jì)算成本優(yōu)化已經(jīng)接近上限，接下來(lái)將對(duì)此進(jìn)行分析。

從圖 6e和圖6f可以發(fā)現(xiàn)，WCSSI的折線軌跡基本和最低成本下限一致?？紤]到工作流Inspiral 中非簡(jiǎn)單任務(wù)的比重極少，且各個(gè)分支比重相當(dāng)，可以近似為多個(gè)假設(shè)的工作流混合而成，所以認(rèn)為WCSSI已經(jīng)達(dá)到了最低成本下限。

而圖 6g和圖 6i中WCSSI成本低于最低成本下限，這是因?yàn)镋pigenomics不符合且不可近似為上述假設(shè)的工作流，簡(jiǎn)單任務(wù)和非簡(jiǎn)單任務(wù)在工作流中都有著很大的比重。由于WCSSI優(yōu)先降低簡(jiǎn)單任務(wù)的成本，所以低成本可搶占實(shí)例在工作流中所占的比重會(huì)比估計(jì)的要高，從而使得WCSSI的運(yùn)行成本低于最低成本下限。

綜上，WCSSI得出的工作流計(jì)算成本可以達(dá)到最低成本下限。

5 相關(guān)工作

云計(jì)算中可搶占實(shí)例的出現(xiàn)，為降低工作流執(zhí)行成本提供了巨大優(yōu)化空間，Poola等人[17]通過(guò)結(jié)合使用可搶占實(shí)例和按需付費(fèi)實(shí)例，以在滿足執(zhí)行時(shí)限的要求下降低工作流的計(jì)算成本。其使用激進(jìn)算法和保守算法來(lái)估計(jì)工作流中各個(gè)任務(wù)的執(zhí)行時(shí)間，然后使用計(jì)算得到的最晚執(zhí)行時(shí)限(按需付費(fèi)下)來(lái)決定工作流在執(zhí)行的過(guò)程中是否可以使用可搶占實(shí)例來(lái)降低成本。WCSSI相比于該算法，考慮了不同任務(wù)對(duì)于工作流執(zhí)行時(shí)限的不同影響，通過(guò)對(duì)任務(wù)進(jìn)行差異化處理可以更好地節(jié)省工作流計(jì)算成本。在購(gòu)買(mǎi)可搶占實(shí)例的策略上，Zafer等人[12]將其建模為動(dòng)態(tài)規(guī)劃問(wèn)題來(lái)得到最優(yōu)出價(jià)策略，但是其沒(méi)有考慮實(shí)例被釋放所帶來(lái)的成本，且價(jià)格模型比較簡(jiǎn)單。本文提出的成本估計(jì)方法則考慮了實(shí)例釋放所帶來(lái)的成本，且使用馬爾科夫模型，更加貼近實(shí)際情況。

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

本文提出了滿足工作流執(zhí)行時(shí)限的可搶占虛擬機(jī)實(shí)例配置和調(diào)度方法，可以極大地降低工作流的計(jì)算成本。本文選取了有代表性的工作流負(fù)載，并在阿里云真實(shí)數(shù)據(jù)上進(jìn)行了實(shí)驗(yàn)驗(yàn)證。實(shí)驗(yàn)結(jié)果顯示，本文提出的工作流調(diào)度方法可以最高節(jié)省89.9%的成本開(kāi)銷(xiāo)。在未來(lái)的工作中，我們會(huì)考慮可搶占實(shí)例的性能變化因素，并在工作流配置和調(diào)度中考慮其對(duì)執(zhí)行時(shí)限的影響。