E-Aalo: 面向無先驗知識Coflow的高效多級隊列調(diào)度

施凌鵬 盧士達(dá) 劉云飛 李 靜

1(國網(wǎng)上海市電力公司信息通信公司 上海 200072) 2(南京航空航天大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院 江蘇 南京 211106)

0 引 言

目前,為了提高資源利用率和大規(guī)模任務(wù)處理的效率,往往通過集群技術(shù)將大量多余閑置的計算機(jī)連接起來形成云數(shù)據(jù)中心。在云數(shù)據(jù)中心中,通常采用MapReduce[1]、Spark[2]等分布式并行計算框架來處理大規(guī)模的數(shù)據(jù)。由于采用了分布式計算框架,一個作業(yè)往往會被劃分成多個子任務(wù)然后交給數(shù)據(jù)中心中的多臺計算機(jī)來完成,在對子任務(wù)進(jìn)行分發(fā)及子任務(wù)結(jié)果進(jìn)行合并時,會產(chǎn)生大量的中間通信數(shù)據(jù)流。如果其中的某條數(shù)據(jù)流沒能及時完成,依賴這條數(shù)據(jù)流結(jié)果的后續(xù)子任務(wù)將無法繼續(xù),最終導(dǎo)致作業(yè)的完成時間延長[3]。文獻(xiàn)[4]表明這些中間數(shù)據(jù)通信流傳輸花費(fèi)的時間平均占作業(yè)總完成時間的33%,最高可達(dá)50%。所以優(yōu)化這些中間數(shù)據(jù)流的完成時間具有十分重要的意義。

目前的研究中,具有語義相關(guān)的一組通信數(shù)據(jù)流被稱為Coflow[5]。Coflow是一組數(shù)據(jù)流(flow)的集合,以MapReduce并行計算框架為例,Map映射階段需要對作業(yè)的任務(wù)進(jìn)行劃分和分發(fā)(shuffle),會產(chǎn)生中間通信數(shù)據(jù)流,Reduce歸并階段需要讀取Map階段處理完成后的中間結(jié)果,也會產(chǎn)生中間通信數(shù)據(jù)流。為了提高云數(shù)據(jù)中心的性能,提高其中作業(yè)的完成時間,需要對Coflow的完成時間(Coflow Completion Time, CCT)進(jìn)行優(yōu)化,而不是對單個數(shù)據(jù)通信流的完成時間(Flow Completion Time, FCT)進(jìn)行優(yōu)化。因為對于一個網(wǎng)絡(luò),只有當(dāng)此階段的所有流都完成,這個階段的通信才算真正完成,才可以進(jìn)行下一個階段的任務(wù)。目前的一些研究者在改進(jìn)降低FCT的同時,忽略了應(yīng)用程序級別的要求,例如方法PDQ[6]和pFabric[7],往往不能做到網(wǎng)絡(luò)資源的最優(yōu)調(diào)度。而Coflow抽象則可以通過網(wǎng)絡(luò)公開應(yīng)用程序級別的語義進(jìn)行彌補(bǔ),文獻(xiàn)[8-9]指出這種語義相關(guān)的抽象可以提高計算平臺的性能。但是目前Coflow調(diào)度方法也存在一定的缺陷,目前最優(yōu)方法Varys[10]由于需要額外的先驗知識而導(dǎo)致其實用性較差;Aalo[11]無需先驗知識但仍存在可以優(yōu)化的閑置空間和可利用的端口信息。

對目前Coflow調(diào)度的主流方法進(jìn)行介紹,然后分析目前主流方法存在的實用性不強(qiáng)和Coflow平均完成時間過高的缺陷,并提出一種面向無先驗知識Coflow的高效多級隊列調(diào)度E-Aalo。通過Coflow流量放置策略選擇所需傳輸數(shù)據(jù)最小且負(fù)載最小的接收節(jié)點(diǎn)來減小Coflow的發(fā)送量,并對現(xiàn)有Aalo方法中的多級隊列調(diào)度存在的閑置空間通過提前調(diào)度低優(yōu)先級隊列中流量進(jìn)行優(yōu)化來降低Coflow調(diào)度的CCT。最后基于Facebook的MapReduce公開數(shù)據(jù)集和CoflowSim框架與現(xiàn)有方法進(jìn)行對比驗證。

1 相關(guān)工作

為了提高云數(shù)據(jù)中心應(yīng)用的性能,對流量進(jìn)行調(diào)度的方法從優(yōu)化的對象上主要可以分為兩類:(1) 面向單個數(shù)據(jù)流(single flow),優(yōu)化目標(biāo)是最小化其FCT,主要的研究工作包括PDQ[6]、pFabric[7]等,這一類方法往往因為是對單一數(shù)據(jù)流的調(diào)度,而無法做到整個網(wǎng)絡(luò)資源的最優(yōu)調(diào)度[12]。(2) 面向Coflow,優(yōu)化目標(biāo)是最小化CCT,主要的研究工作包括Varys[10]、Baraat[9]和Aalo[10]等。Varys[10]基于最小有效瓶頸優(yōu)先的機(jī)制對Coflow進(jìn)行調(diào)度,是目前先驗知識已知情況下效果最好的方法。Baraar[9]采用FIFO(First In First Out)和公平共享機(jī)制提高帶寬的利用率,進(jìn)而減少平均CCT。Aalo[10]則是基于隊列的多級調(diào)度器,為不同的Coflow分配不同的優(yōu)先級來進(jìn)行調(diào)度。目前主要的研究都是圍繞面向Coflo優(yōu)化的第二類問題展開,即最小化平均CCT。

對Coflow進(jìn)行優(yōu)化的方法可分為兩類:(1) 擁有Coflow大小等先驗知識的Coflow調(diào)度方法。這方面主要的調(diào)度效果最好的有Varys[10],它采用一種最小瓶頸優(yōu)先(Smallest-Effective-Bottleneck-First,SEBF)機(jī)制對瓶頸較小的流優(yōu)先調(diào)度,且控制不同內(nèi)部流的發(fā)送速度,節(jié)省了端口的帶寬并為其他Coflow騰出空間,可以使所有內(nèi)部流的完成時間一致。其缺陷在于需要提前獲取Coflow的大小等信息,而這一點(diǎn)往往只有在Coflow完成之后才能知曉,因此實用性不強(qiáng)。(2) 在沒有Coflow先驗信息的情況下對Coflow進(jìn)行調(diào)度。Aalo[10]是目前最具代表性的方法之一,Aalo不需要提前知曉Coflow的流量大小信息,而是根據(jù)Coflow當(dāng)前已經(jīng)發(fā)送的字節(jié)數(shù)目來判斷Coflow的大小,通過設(shè)置不同優(yōu)先級的隊列并按照優(yōu)先級對Coflow進(jìn)行調(diào)度。Aalo為每個隊列設(shè)置閾值,當(dāng)Coflow已發(fā)送的字節(jié)數(shù)超過閾值時降低Coflow的優(yōu)先級。Aalo擁有較強(qiáng)的實用性,但是其缺陷在于只考慮了Coflow當(dāng)前已發(fā)送的字節(jié)數(shù)目,而沒有充分考慮其他有用的信息,如Coflow的寬度信息也是可以利用的,且多級隊列也存在可以優(yōu)化的閑置空間。對于較大一點(diǎn)的Coflow, Aalo由于缺乏先驗知識而表現(xiàn)不如Varys。A-SEBF(Approximate Smallest-Effective-Bottleneck-First)[3]是在先驗信息未知的情況下的一種近似最小有效瓶頸優(yōu)先的Coflow調(diào)度機(jī)制,通過Coflow當(dāng)前大小和寬度信息決定Coflow的調(diào)度信息,其核心思想是在一定程度上提高寬度大的Coflow的優(yōu)先級,相比于Aalo,能夠顯著降低CCT,效果接近于利用先驗知識的SEBF方法。

針對上面方法中存在的Coflow平均完成時間較高和可用性不強(qiáng)的問題,提出面向無先驗知識Coflow的高效多級隊列調(diào)度E-Aalo,在無先驗知識的情況下通過基于計算節(jié)點(diǎn)狀態(tài)的流量放置策略和優(yōu)化多級隊列調(diào)度中的閑置空間來降低Coflow的平均完成時間,并保證可用性。

2 研究背景

2.1 數(shù)據(jù)中心網(wǎng)絡(luò)抽象模型

數(shù)據(jù)中心中包含大量的計算節(jié)點(diǎn),為了研究的方便,可以將整個數(shù)據(jù)中心抽象為一個連接了所有計算機(jī)的無阻塞大型交換機(jī)。這個大型交換機(jī)的入口端口對應(yīng)于服務(wù)器的出口鏈路,而出口端口則對應(yīng)于服務(wù)器的入口鏈路[13-14]。通過這種抽象,該模型的優(yōu)勢在于只需要考慮入口端口和出口端口,便于對Coflow流量的調(diào)度進(jìn)行分析,且在簡單且全平分帶寬拓?fù)浣Y(jié)構(gòu)下具有很高的實用性,目前已經(jīng)被大量的研究者采納。

數(shù)據(jù)中心抽象模型如圖1所示。圖1是由n個入口端口和n個出口端口組成的一個大型無阻塞交換機(jī),即數(shù)據(jù)中心抽象模型,這些入口端口和出口端口是對數(shù)據(jù)中心中各個主機(jī)的流量輸入和輸出端口的抽象。在這個模型中,每個入口端口都可能會擁有一個或多個Coflow,這些Coflow將會從入口端口對應(yīng)的服務(wù)器中發(fā)出,到達(dá)交換機(jī),并通過抽象的無阻塞交換機(jī)最終被轉(zhuǎn)發(fā)到出口端口中,這些出口端口對應(yīng)接收節(jié)點(diǎn)的入口鏈路。每一個主機(jī)在一段時間內(nèi)將會需要調(diào)度多個Coflow,所以圖1中入口端口的最左邊使用一個虛擬的隊列用于存放到達(dá)的需要調(diào)度的Coflow。

圖1 數(shù)據(jù)中心抽象模型

2.2 Coflow調(diào)度目標(biāo)和相關(guān)定義

式中:每個Coflow的完成時間是其所包含的flow中完成時間最長的flow的完成時間。那么Coflow調(diào)度的目標(biāo)如式(2)所示。

(2)

后續(xù)敘述中使用的變量定義如表1所示。

表1 相關(guān)參數(shù)及定義

3 E-Aalo調(diào)度

3.1 E-Aalo總體架構(gòu)

E-Aalo架構(gòu)如圖2所示,主要包括全局協(xié)調(diào)器和本地守護(hù)進(jìn)程兩個部分。

圖2 面向無先驗知識Coflow的高效多級隊列調(diào)度整體框架

(1) 全局協(xié)調(diào)器。全局協(xié)調(diào)器監(jiān)測每個作業(yè)是否產(chǎn)生Coflow,對產(chǎn)生Coflow的作業(yè)利用Coflow流量放置策略,篩選合適的計算節(jié)點(diǎn)放置每個Coflow中的流量并生成放置方案,然后通知發(fā)送節(jié)點(diǎn)將Coflow中的流量發(fā)送到接收節(jié)點(diǎn)。同時,全局協(xié)調(diào)器還需接收發(fā)送節(jié)點(diǎn)發(fā)送來的每個Coflow已發(fā)送的數(shù)據(jù)流大小信息,根據(jù)這些信息確定不同Coflow的優(yōu)先級并發(fā)送給本地守護(hù)進(jìn)程。再對當(dāng)前多級隊列調(diào)度中可能產(chǎn)生的閑置空間進(jìn)行分析,若當(dāng)前最高優(yōu)先級隊列中只有一個Coflow且只使用部分發(fā)送端口,此時出現(xiàn)端口閑置空間,則提前啟動低優(yōu)先級隊列中的Coflow流量調(diào)度來降低CCT。

(2) 本地守護(hù)進(jìn)程。本地守護(hù)進(jìn)程主要負(fù)責(zé)接收全局協(xié)調(diào)器發(fā)送來的Coflow優(yōu)先級信息,然后在本地的多級隊列中對Coflow進(jìn)行調(diào)度。多級隊列內(nèi)部使用FIFO方式進(jìn)行調(diào)度,不同隊列之間使用加權(quán)公平隊列調(diào)度方式。此外,本地的守護(hù)進(jìn)程還需要將本計算節(jié)點(diǎn)中每個Coflow已發(fā)送的數(shù)據(jù)量信息發(fā)送給全局協(xié)調(diào)器,以便全局協(xié)調(diào)器可以及時調(diào)整Coflow的優(yōu)先級。

全局協(xié)調(diào)器負(fù)責(zé)分析Coflow的發(fā)送位置和Coflow的調(diào)度優(yōu)先級,本地守護(hù)進(jìn)程負(fù)責(zé)進(jìn)行Coflow流量的發(fā)送并將已經(jīng)發(fā)送的Coflow信息通知全局協(xié)調(diào)器,幫助全局協(xié)調(diào)器進(jìn)行優(yōu)先級的分析。全局協(xié)調(diào)器和本地守護(hù)進(jìn)程相互合作完成Coflow的調(diào)度。

3.2 基于計算節(jié)點(diǎn)狀態(tài)的流量放置策略

目前A-SEBF、Aalo等方法只考慮利用Coflow到達(dá)之后的優(yōu)化調(diào)度來降低CCT,但忽略了Coflow中流量的放置問題。而云數(shù)據(jù)中心中的作業(yè)往往被劃分成多個子任務(wù)進(jìn)行處理,每個子任務(wù)將被分派放置到不同的主機(jī)上執(zhí)行,相應(yīng)的數(shù)據(jù)也被傳輸?shù)綀?zhí)行任務(wù)的主機(jī)節(jié)點(diǎn)上,帶來更多的數(shù)據(jù)流量傳輸,也導(dǎo)致更大的開銷[15-16]。若該主機(jī)上原本就存在相應(yīng)的數(shù)據(jù)(云數(shù)據(jù)中心的HDFS文件系統(tǒng)一般都具有冗余備份,即文件的數(shù)據(jù)塊可能存在于多臺不同的主機(jī)上),就可避免額外的數(shù)據(jù)傳輸開銷。因此,對Coflow中的流量進(jìn)行不同的放置可對子任務(wù)在不同的主機(jī)上進(jìn)行分配,而合理的分配也將會減少數(shù)據(jù)的傳輸量,降低時間開銷,提高云數(shù)據(jù)中心的性能[17-18]。

Coflow中流量放置策略即是對一道作業(yè)在云數(shù)據(jù)中心選擇不同的計算主機(jī)來執(zhí)行其子任務(wù),選擇時需要考慮該計算節(jié)點(diǎn)的狀態(tài):是否已經(jīng)擁有執(zhí)行任務(wù)所需要的數(shù)據(jù)和該計算節(jié)點(diǎn)的網(wǎng)絡(luò)負(fù)載情況。

Coflow的放置策略如式(3)所示。

(4)

算法1Coflow流量放置選擇

輸入:集合Q1,Q2,…,Qk對應(yīng)Cn的k個數(shù)據(jù)流。

輸出:Cn的放置方案M1,M2,…,Mk對應(yīng)的k個數(shù)據(jù)量的放置方案。

1. for allifrom 1 tokdo

2. for alljfrom 1 tomdo

4.Qi.push(j)

//將合適的節(jié)點(diǎn)j放入數(shù)據(jù)流i對應(yīng)的集合中

5. end

6. end

7. end

8. for allifrom 1 tokdo

9. for alljinQido

11. end

12. end

13. returnM1,M2,…,Mk

流量放置策略是在Coflow流量進(jìn)行發(fā)送之前的一個優(yōu)化操作,之前的方法[10-11]沒有在Coflow流量發(fā)送并進(jìn)行調(diào)度之前對流量的目標(biāo)節(jié)點(diǎn)進(jìn)行篩選,而是選擇直接將流量發(fā)送到隨機(jī)的節(jié)點(diǎn)上,很容易造成節(jié)點(diǎn)的堵塞,導(dǎo)致Coflow調(diào)度的平均CCT時間加長。而通過判斷目標(biāo)節(jié)點(diǎn)上是否存在Coflow流量的數(shù)據(jù)以及目標(biāo)節(jié)點(diǎn)的當(dāng)前網(wǎng)絡(luò)負(fù)載情況,可以為Coflow中流量的調(diào)度選擇出最合適的目標(biāo)節(jié)點(diǎn)。如果此時目標(biāo)節(jié)點(diǎn)已經(jīng)擁有Coflow將要傳輸?shù)牧髁繑?shù)據(jù),可以避免額外數(shù)據(jù)的傳輸,將網(wǎng)絡(luò)資源空出給其他流量進(jìn)行傳輸。目標(biāo)節(jié)點(diǎn)在處理完計算任務(wù)之后需要將數(shù)據(jù)回傳,如果此時目標(biāo)節(jié)點(diǎn)的網(wǎng)絡(luò)負(fù)載較小,那么也會加快回傳完成的速度,所以通過計算節(jié)點(diǎn)狀態(tài)來選擇合適的目標(biāo)節(jié)點(diǎn)可以相比之前的方法進(jìn)一步降低Coflow調(diào)度的平均CCT。

3.3 優(yōu)化閑置空間的多級隊列調(diào)度

除了流量放置外,Coflow的流量調(diào)度也是影響CCT的重要環(huán)節(jié)。Coflow的放置策略可以選擇合適的計算節(jié)點(diǎn),這些節(jié)點(diǎn)在執(zhí)行任務(wù)時,往往要處理來自多個Coflow的流量,這些流量可能同時到達(dá),也可能先后到達(dá),如何對這些Coflow流量進(jìn)行調(diào)度同樣會對CCT造成重要影響。其中,Varys方法對瓶頸因子最小的Coflow流量進(jìn)行優(yōu)先調(diào)度,本質(zhì)上是對CCT最小的Coflow進(jìn)行優(yōu)先調(diào)度來降低CCT;Aalo方法在先驗未知的情況下通過設(shè)置多個優(yōu)先級隊列,并根據(jù)Coflow已發(fā)送的數(shù)據(jù)量大小來決定Coflow的優(yōu)先級進(jìn)行調(diào)度;而A-SEBF方法對Varys中的瓶頸因子和Coflow寬度信息進(jìn)行改進(jìn)。A-SEBF和Aalo方法中都使用了優(yōu)先級隊列,但是其中的考慮相對簡單,在復(fù)雜情況下仍然存在一定的改進(jìn)空間,因此提出一種改進(jìn)的高效多級隊列調(diào)度方法。

3.3.1調(diào)度過程中的閑置空間分析

以圖3為例,圖3中一共包含了3個Coflow,分別為C1(灰色)、C2(白色)、C3(黑色),C1的大小為2,只包含一條數(shù)據(jù)流;C2大小為7,包含2條數(shù)據(jù)流;C3大小為3,包含一條數(shù)據(jù)流;C2和C3同時到達(dá),C1在C2之后到達(dá)。這里假設(shè)只存在3個端口,每個入口端口的左邊存在三個隊列,分別對應(yīng)發(fā)送目的端口,例如:入口端口1中的C3在第一個隊列中,表示它將發(fā)送3個單位的數(shù)據(jù)到出口端口1中;C2在第三個隊列中,表示要發(fā)送3個單位的數(shù)據(jù)到出口端口3中。

圖3 數(shù)據(jù)中心流量

在Varys方法中,采用的是最小瓶頸優(yōu)先,采用Varys的調(diào)度情況如圖4所示,C3的完成時間為3,C2的完成時間為6,C1的完成時間為2,此時的平均CCT為(3+2+6)/3≈3.66,這是理想狀態(tài)下Coflow調(diào)度的最優(yōu)調(diào)度結(jié)果。

圖4 Varys方法的調(diào)度情況

在Aalo方法中,根據(jù)Coflow已發(fā)送數(shù)據(jù)量大小設(shè)置Coflow的優(yōu)先級,由于例子中的Coflow大小比較小,所以這里假設(shè)多級隊列的閾值分別為1、2、4、8等。采用Aalo的調(diào)度情況如圖5所示,在Aalo中按照優(yōu)先級隊列對Coflow進(jìn)行調(diào)度,優(yōu)先級高的隊列將會被優(yōu)先調(diào)度,隊列內(nèi)部采取FIFO策略,因此當(dāng)高優(yōu)先級隊列中的Coflow的發(fā)送量達(dá)到閾值時將會被下放到低優(yōu)先級隊列中,只有高優(yōu)先級隊列中的Coflow調(diào)度完之后才會調(diào)度低優(yōu)先級隊列中的Coflow。從圖5中可以看出這樣會導(dǎo)致端口發(fā)送的時間段內(nèi)存在一些閑置空間的情況,這些情況會導(dǎo)致CCT變大。此時的CCT為(8+4+4)/3≈5.33。

圖5 Aalo方法調(diào)度情況

3.3.2優(yōu)化調(diào)度過程中的閑置空間

Aalo的多級隊列調(diào)度方法根據(jù)Coflow已發(fā)送的數(shù)據(jù)量來決定Coflow的調(diào)度優(yōu)先級,當(dāng)高優(yōu)先級隊列中的Coflow的發(fā)送量達(dá)到閾值時將會被下放到低優(yōu)先級隊列中,只有高優(yōu)先級隊列中的Coflow調(diào)度完之后才會調(diào)度低優(yōu)先級隊列中的Coflow。通過分析發(fā)現(xiàn),Aalo會在調(diào)度過程中存在一些閑置空間,即為了等待高優(yōu)先級隊列中一些Coflow流量傳輸?shù)耐瓿?會導(dǎo)致將要調(diào)度發(fā)送低優(yōu)先級隊列中的Coflow流量的端口處于停滯狀態(tài),必須要等待高優(yōu)先級度列中的Coflow發(fā)送都超過隊列的閾值時才會進(jìn)一步調(diào)度低優(yōu)先級隊列中的Coflow流量,這種閑置空間無疑會導(dǎo)致Coflow的平均CCT增大。通過在這些停滯的端口上提前對低優(yōu)先級隊列中的Coflow流量進(jìn)行調(diào)度,設(shè)置當(dāng)端口發(fā)生閑置時主動去低優(yōu)先級隊列中提前調(diào)度Coflow,可以充分利用每個端口的網(wǎng)絡(luò)資源,從而有效降低多級隊列調(diào)度方法中Coflow的平均CCT。

對這種閑置空間進(jìn)行改進(jìn),允許在依據(jù)優(yōu)先級隊列進(jìn)行調(diào)度的過程中產(chǎn)生閑置空間時,提前啟動低優(yōu)先級隊列中Coflow的調(diào)度,以此來充分利用閑置空間,降低Coflow的CCT,提高效率。提前開啟低優(yōu)先級隊列中Coflow調(diào)度后,調(diào)度的情況如圖6所示。

圖6 E-Aalo調(diào)度情況

可以看出,產(chǎn)生閑置空間被用于調(diào)度C2,圖6中星號標(biāo)記的即為提前調(diào)度的Coflow流量,這種方法下,最終的CCT為(6+4+4)/3≈4.66,比Aalo降低了0.67。提前調(diào)度方式如圖7所示。

圖7 E-Aalo調(diào)度方式

圖7中,C2和C3是同時到達(dá)的且在不同的端口,所以它們相當(dāng)于在隊列中并列。當(dāng)?shù)谝粋€時間過去后,端口1和端口3都發(fā)送1個單位的流量,C2和C3由于不在同一端口,所以依然可以并列看待。當(dāng)C1到達(dá)時,端口1開始調(diào)度C1,但是端口3此時并不需要調(diào)度C1的流量,此時如果按照Aalo和A-SEBF中的方法,端口3此時將被閑置,將會導(dǎo)致端口3中C2和C3的CCT變大,而此時如果在端口3提前調(diào)度較低一級隊列中的C2,就可以顯著減小CCT。具體來說,E-Aalo高效多級隊列調(diào)度算法調(diào)度步驟如下:

(1) 全局協(xié)調(diào)器根據(jù)流量放置方案選擇Coflow的合適的接收節(jié)點(diǎn),通知Coflow的發(fā)送端,然后發(fā)送端會先將這些流量排入高優(yōu)先級隊列中,在同一級隊列中通過FIFO方式調(diào)度。

(2) 每個發(fā)送端口先將高優(yōu)先級隊列中的Coflow進(jìn)行調(diào)度,每個發(fā)送端口還需要將當(dāng)前Coflow已經(jīng)調(diào)度的流量信息發(fā)送到全局協(xié)調(diào)器,全局協(xié)調(diào)器對每個Coflow已經(jīng)發(fā)送的數(shù)據(jù)量進(jìn)行統(tǒng)計,如果Coflow的已發(fā)送數(shù)據(jù)量超過了當(dāng)前優(yōu)先級隊列的閾值,則將Coflow下調(diào)到低一級優(yōu)先級隊列中,即降低該Coflow的優(yōu)先級。

(3) 發(fā)送端口在選擇隊列中下一個Coflow進(jìn)行調(diào)度時,如果其他的端口中的Coflow都已經(jīng)被放置到下一級優(yōu)先級隊列中且其他發(fā)送端口存在閑置空間時,對下一個Coflow進(jìn)行調(diào)度的同時,提前開啟閑置端口的低一級優(yōu)先級隊列中的Coflow進(jìn)行調(diào)度,充分利用閑置空間;其他端口中的低優(yōu)先級隊列中的Coflow調(diào)度方式和(2)中一樣。

(4) 提前開啟閑置端口的低一級優(yōu)先級隊列時,同樣在同一級隊列中使用FIFO方式進(jìn)行調(diào)度,直到所有的Coflow調(diào)度完。

4 實驗評估

為了評估提出的基于多級隊列的Coflow調(diào)度機(jī)制的有效性,使用公開的Facebook數(shù)據(jù)集,通過和現(xiàn)有的先驗已知Coflow調(diào)度方法Varys、先驗未知Coflow調(diào)度方法Aalo、傳統(tǒng)的FAIR方法進(jìn)行對比,驗證方法的有效性。所給調(diào)度方法目前是在Java語言實現(xiàn)的CoflowSim調(diào)度模擬器進(jìn)行實驗和評估,還未在真實的分布式集群環(huán)境對所給方法進(jìn)行實現(xiàn)和實驗評估,在真實的分布式集群環(huán)境對所給方法進(jìn)行實現(xiàn)和實驗評估是下一步的目標(biāo)。

4.1 實驗配置

CoflowSim是目前專門用于流級別的模擬器,用于實現(xiàn)和比較各種Coflow調(diào)度機(jī)制,且已經(jīng)實現(xiàn)了多種先驗知識和無先驗知識情況下的Coflow調(diào)度方法,比如Varys、Aalo等,所以選擇CoflowSim模擬工具進(jìn)行實驗驗證。

CoflowSim調(diào)度模擬器上進(jìn)行實驗的部署環(huán)境為:Intel Xeon W-2102 CPU、32 GB內(nèi)存,Ubuntu16.04操作系統(tǒng)和Java 1.8.0_181環(huán)境。在Eclipse中通過maven工具導(dǎo)入CoflowSim框架,由于CoflowSim模擬器內(nèi)部已經(jīng)對數(shù)據(jù)中心的抽象模型進(jìn)行了建模和實現(xiàn),同時實現(xiàn)了Aalo和Varys等CoflowSim調(diào)度算法,所以只需要使用Java語言實現(xiàn)所給調(diào)度方法并進(jìn)行實驗驗證。

使用的數(shù)據(jù)集為Facebook提供的從現(xiàn)實世界中數(shù)據(jù)密集型應(yīng)用程序合成的實際工作負(fù)載。原始的數(shù)據(jù)來自Facebook上3 000臺150機(jī)架的MapReduce集群,合成后的數(shù)據(jù)包含526個Coflow,這些Coflow是在不同時刻到達(dá)。該數(shù)據(jù)集中的數(shù)據(jù)格式如圖8所示。其中數(shù)據(jù)被壓縮到了機(jī)架級別,Mapper的位置和Reducer的位置都是機(jī)架級別的,而機(jī)架的范圍是0～149,即150臺服務(wù)器。同一機(jī)架中的Mapper被組合成一個機(jī)架級別的Mapper,同一機(jī)架中的Reducer被組合成一個機(jī)架級別的Reducer。圖8給出了一個Coflow實例,表明該Coflow ID為3,到達(dá)時間為13 122,一共有兩個Mapper,位置分別是機(jī)架中的66和138號機(jī)架,一共1個Reducer,Reducer的位置在38號機(jī)架且需要接收的數(shù)據(jù)為4.0 MB。在本實驗中,CoflowSim中模擬的每臺服務(wù)器的端口的初始帶寬為1 Gbit/s。

圖8 數(shù)據(jù)集格式

在之前使用Facebook提供的數(shù)據(jù)集的研究中[19],可以發(fā)現(xiàn)其中大部分的Coflow的完成時間都在60 s之內(nèi),比例約占90%左右,所以數(shù)據(jù)集中大部分都是小型Coflow(能在60 s內(nèi)完成),只有少量的大型Coflow,但是這些大型Coflow的傳輸數(shù)據(jù)量占總量的90%以上。

4.2 對比實驗

E-Aalo調(diào)度主要包括Coflow流量放置和在端口閑置時提前調(diào)度低優(yōu)先級隊列流量,所以設(shè)置的實驗主要包括:(1) E-Aalo方法和其他Coflow調(diào)度方法的CCT對比;(2) 使用Coflow流量放置策略和提前調(diào)度低優(yōu)先級隊列流量前后的效果對比。

設(shè)置的對比方法涉及Aalo[11]、Varys[12]和FS。Varys是在先驗知識已知情況下的基于最小瓶頸優(yōu)先(SEBF)的Coflow調(diào)度方法;Aalo是在先驗未知情況下利用多級隊列來調(diào)度Coflow的方法;FS(Fair Sharing)是根據(jù)流量數(shù)量對網(wǎng)絡(luò)帶寬進(jìn)行平均分配的策略。比較的指標(biāo)主要是Coflow的平均完成時間(Average CCT)。

4.2.1E-Aalo和其他方法的對比

圖9給出了使用不同的Coflow調(diào)度方法得到的平均完成時間對比圖。Varys調(diào)度完數(shù)據(jù)集中526個Coflows之后,平均完成時間CCT為28 528.46 ms,是所有對比方法中最好的,因為它可以根據(jù)已知的先驗知識來進(jìn)行最小瓶頸優(yōu)先調(diào)度從而達(dá)到最優(yōu)的結(jié)果;Aalo調(diào)度完526個Coflow之后的CCT為46 097.70 ms,Aalo根據(jù)目前已經(jīng)發(fā)送的數(shù)據(jù)量來設(shè)置不同Coflow的優(yōu)先級,而不是其中flow的優(yōu)先級,導(dǎo)致多級隊列在調(diào)度的時候存在一些可以進(jìn)一步優(yōu)化利用的閑置空間,所以其CCT相比Varys增加了61.58%;FS調(diào)度完526個Coflow之后的CCT為70 592.82 ms,它的效果是4種方法中最差的,CCT最高。E-Aalo方法調(diào)度完526個Coflow之后的CCT為40 437.61 ms,比Aalo降低了12.28%,因為E-Aalo方法對Coflow流量放置策略進(jìn)行了優(yōu)化,并將Aalo中多級隊列調(diào)度中的閑置空間加以利用,從而降低CCT。

圖9 4種調(diào)度方法的CCT

圖10給出了4種不同方法每個Coflow的大小及其完成時間的散點(diǎn)圖。可以看出,Varys方法調(diào)度的大部分的Coflow都出現(xiàn)在圖中的左下方,大部分較小的Coflow的完成時間也較小,保證了Coflow調(diào)度的效率。FAIR中則出現(xiàn)了許多大小較小但是完成時間較大的點(diǎn),所以FAIR方法的CCT通常并不理想,會高于其他方法。在Aalo方法中,通過多級隊列調(diào)度方法可以保證基本不會出現(xiàn)FAIR中較小Coflow被延誤而導(dǎo)致完成時間過大的情況,但是一些較大的Coflow的完成時間卻會相應(yīng)提高。在E-Aalo中,通過對多級隊列調(diào)度過程中的閑置空間進(jìn)行優(yōu)化,可以降低部分較大Coflow的完成時間,且也可以加速一些較小Coflow的調(diào)度來降低整體的CCT。

圖10 Coflow完成時間和Coflow大小的關(guān)系

圖11給出了4種不同方法Coflow完成時間的累計分布函數(shù)曲線圖?？梢钥闯?FAIR方法的效果最差,在同一時間間隔內(nèi),其Coflow的完成率最低。Varys是先驗知識下的最小瓶頸優(yōu)先方法,效果最好,同一時間內(nèi)的Coflow完成率最高。Aalo與E-Aalo接近,但E-Aalo對其進(jìn)行了優(yōu)化,故同一時間E-Aalo完成的Coflow率略高于Aalo,與Varys方法最接近。因此,方法E-Aalo的Coflow調(diào)度效果優(yōu)于Aalo方法。

圖11 Coflow完成時間的累計分布函數(shù)曲線

4.2.2E-Aalo自身的對比

圖12給出了使用Coflow流量放置策略和提前調(diào)度低優(yōu)先級隊列流量前后的效果對比。E-Aalo方法其實是對Aalo多級隊列的改進(jìn),通過加入流量放置策略和提前調(diào)度低優(yōu)先級隊列流量來優(yōu)化CCT?？梢钥闯?Aalo在數(shù)據(jù)集上的CCT為46 097.70 ms,使用上流量放置策略后CCT下降到44 046.3 ms,降低了4.45%;E-Aalo使用流量放置策略加上改進(jìn)的多級隊列調(diào)度后,CCT下降為40 437.61 ms,比使用流量放置的Aalo方法下降了8.19%。

所給調(diào)度方法主要適用于集群中存在大量分布式計算任務(wù)且先驗知識未知情況下的Coflow調(diào)度。所給方法是針對無先驗知識下Coflow調(diào)度方法Aalo進(jìn)行的改進(jìn)。但是暫時只是在Java語言的CoflowSim框架下進(jìn)行了模擬實驗。然后基于Facebook的Coflow公開數(shù)據(jù)集對所給方法的有效性進(jìn)行實驗驗證。

5 結(jié) 語

由于Varys方法只能應(yīng)用于先驗知識已知的情況導(dǎo)致實用性較差,且Aalo方法存在一些可以改進(jìn)的缺陷,提出一種面向無先驗知識Coflow的高效多級隊列調(diào)度E-Aalo。首先,基于計算節(jié)點(diǎn)的狀態(tài)信息選擇合適的節(jié)點(diǎn)對流量進(jìn)行放置來減少部分?jǐn)?shù)據(jù)的傳輸,進(jìn)而降低Coflow的CCT。然后,通過對Aalo方法中的多級隊列調(diào)度的閑置空間進(jìn)行改進(jìn)利用,在閑置時提前調(diào)度低優(yōu)先級的流量來優(yōu)化Coflow的CCT。最后,利用Facebook的公開數(shù)據(jù)集和CoflowSim框架進(jìn)行對比驗證。E-Aalo在CCT上比Aalo方法下降了12.28%,優(yōu)于Aalo方法。由于CoflowSim平臺功能比較簡單,接下來的工作將考慮在仿真模型功能更強(qiáng)的CloudSim平臺或真實環(huán)境中實現(xiàn)提出的E-Aalo調(diào)度。