陳家宇 胡建軍

1(鄭州財(cái)經(jīng)學(xué)院信息工程學(xué)院 河南 鄭州 450000)2(廣東財(cái)經(jīng)大學(xué)信息學(xué)院 廣東 廣州 510320)

0 引 言

在多核處理器、虛擬化、分布式存儲(chǔ)、寬帶互聯(lián)網(wǎng)和自動(dòng)化管理等技術(shù)飛速發(fā)展的今天，云計(jì)算應(yīng)運(yùn)而生，并得到長(zhǎng)足的發(fā)展和應(yīng)用。憑借其能夠按照用戶的需求合理分配系統(tǒng)資源，且用戶只需對(duì)所用資源付費(fèi)等優(yōu)點(diǎn)，云計(jì)算已受到IT商業(yè)巨頭和專家學(xué)者的高度關(guān)注。但隨著信息數(shù)據(jù)化進(jìn)程的加快，利用有限的資源與成本存儲(chǔ)及處理海量的數(shù)據(jù)成為云計(jì)算技術(shù)發(fā)展亟需解決的問(wèn)題[1-2]。

目前，MapReduce框架作為云計(jì)算技術(shù)的典型，為處理海量數(shù)據(jù)提供了可行的解決方案[3]。Hadoop是MapReduce框架的開源實(shí)現(xiàn)平臺(tái)，不僅能夠高效可靠地存儲(chǔ)處理海量數(shù)據(jù)，而且在并行化技術(shù)方面對(duì)應(yīng)用開發(fā)者實(shí)現(xiàn)了透明處理[4]，為海量數(shù)據(jù)的并行處理提供簡(jiǎn)單的編程框架。Hadoop作為一個(gè)新興的平臺(tái)，很多技術(shù)細(xì)節(jié)仍需完善，例如MapReduce調(diào)度器的工作效率不高與對(duì)異構(gòu)環(huán)境適應(yīng)能力差等問(wèn)題。而任務(wù)調(diào)度技術(shù)是Hadoop平臺(tái)的核心，其技術(shù)優(yōu)劣直接影響到平臺(tái)整體執(zhí)行性能和系統(tǒng)資源利用效率的高低，因此針對(duì)調(diào)度算法的研究已有大量成果[5]。

文獻(xiàn)[6]提出了一種基于小位置值規(guī)則的粒子群算法(Particle Swarm Optimization，PSO)，基于優(yōu)化傳輸和處理時(shí)間的想法，其主要目標(biāo)是減少總處理時(shí)間。文獻(xiàn)[7]提出了一種基于具有動(dòng)態(tài)作業(yè)優(yōu)先級(jí)的貪婪背包單一隊(duì)列算法，不需要用戶干預(yù)就能建立特定的作業(yè)優(yōu)先級(jí)，系統(tǒng)通過(guò)窮舉參數(shù)搜索來(lái)計(jì)算作業(yè)優(yōu)先級(jí)，但該算法計(jì)算時(shí)間較長(zhǎng)，不適用于多目標(biāo)條件下的多任務(wù)調(diào)度。文獻(xiàn)[8]提出了一種基于動(dòng)態(tài)優(yōu)先級(jí)的混合調(diào)度器(Hybrid Scheduler，HybS)算法。其目標(biāo)是減少可變長(zhǎng)度和延遲，同時(shí)保持?jǐn)?shù)據(jù)局部性。算法將分?jǐn)?shù)背包算法應(yīng)用與處理器分配，以使動(dòng)態(tài)優(yōu)先級(jí)適用于不同規(guī)模、不同任務(wù)長(zhǎng)度或等待時(shí)間的各項(xiàng)任務(wù)。文獻(xiàn)[9]提出的應(yīng)用特征的PaaS彈性資源管理機(jī)制能夠有效減少云計(jì)算請(qǐng)求過(guò)程中彈性操作的次數(shù)，降低了彈性操作帶來(lái)的資源開銷，提高了各種系統(tǒng)資源的用率，但在獲取請(qǐng)求率變化時(shí)的請(qǐng)求預(yù)測(cè)精度還有提升空間，以便更好地指導(dǎo)彈性資源分配。文獻(xiàn)[10]提出的FIFO調(diào)度程序是第一個(gè)Hadoop調(diào)度程序，它遵循FIFO模型：實(shí)現(xiàn)任務(wù)隊(duì)列，并通過(guò)到達(dá)順序?qū)⑷蝿?wù)分配給主服務(wù)器。它是基本的調(diào)度算法，并不受任何條件約束。對(duì)于節(jié)點(diǎn)的分配，它使用了Torque資源管理器，并在每個(gè)節(jié)點(diǎn)上啟動(dòng)兩個(gè)守護(hù)進(jìn)程：Hadoop MapReduce和HDFS。此調(diào)度程序的主要問(wèn)題是在處理大量任務(wù)時(shí)資源擁塞。Hadoop環(huán)境中的多目標(biāo)調(diào)度需要考慮MapReduce調(diào)度機(jī)制的擴(kuò)展，具體體現(xiàn)在以下幾個(gè)方面[11]：優(yōu)化設(shè)置和清理任務(wù)，減少作業(yè)初始化和終止階段的時(shí)間成本，瞬間消息傳遞通信機(jī)制以及用于加速對(duì)性能敏感的任務(wù)調(diào)度和執(zhí)行。

針對(duì)以上問(wèn)題，提出了一種適用于多任務(wù)多目標(biāo)的Hadoop調(diào)度算法(MOSMT)。MOSMT算法從用戶給定的服務(wù)等級(jí)協(xié)議(service-level agreement, SLA)約束中提取其服務(wù)質(zhì)量偏好權(quán)重信息進(jìn)行預(yù)處理，通過(guò)選擇唯一的優(yōu)化目標(biāo)，并將其他目標(biāo)參數(shù)通過(guò)權(quán)重所體現(xiàn)的相對(duì)重要性轉(zhuǎn)化為約束條件來(lái)解決多目標(biāo)問(wèn)題。MOSMT算法思想總結(jié)如下：

(1) MOSMT算法同時(shí)考慮與用戶、資源相關(guān)的目標(biāo)函數(shù)以及約束，其中，將截止日期和預(yù)算作為算法的優(yōu)化目標(biāo)，將避免資源爭(zhēng)用和集群的最佳工作量作為約束，通過(guò)優(yōu)化目標(biāo)與約束選取有效實(shí)現(xiàn)使用最小資源、最低花費(fèi)處理最多數(shù)據(jù)量的目的。

(2) 通常來(lái)說(shuō)，新設(shè)計(jì)調(diào)度算法難以應(yīng)用于現(xiàn)實(shí)的Hadoop集群中，且應(yīng)用過(guò)程需要耗費(fèi)大量的時(shí)間和金錢。而提出的算法使用負(fù)載調(diào)度模擬器能很好地解決這一問(wèn)題，因?yàn)镾LS易于為調(diào)度程序設(shè)置各種相應(yīng)的功能。

(3) MOSMT算法具有普適性，從而更好地適用于更多的應(yīng)用場(chǎng)景。

為了驗(yàn)證算法的可行性，采用MobiWay應(yīng)用程序、以不同的度量進(jìn)行評(píng)估，并將MOSMT算法與FIFO[10]、Fair調(diào)度程序[11]作對(duì)比，結(jié)果表明，MOSMT算法能夠?qū)崿F(xiàn)類似的性能，并且在一些方面表現(xiàn)得更為優(yōu)越。

1 MOSMT調(diào)度算法

1.1 算法建模

每個(gè)將要在Hadoop集群中執(zhí)行的工作J都有一個(gè)已知映射任務(wù)數(shù)量Nmap和約簡(jiǎn)任務(wù)數(shù)量Nreduce[12]，其數(shù)學(xué)表達(dá)為：

J={Ti|Ti∈Map∨Ti∈Reduce} |J|=N

(1)

式中：N為任務(wù)的總數(shù)，N=Nmap+Nreduce。

每個(gè)工作都有一個(gè)到達(dá)時(shí)間A、截止時(shí)間D和分配的預(yù)算Y。對(duì)于每項(xiàng)工作，從一開始就會(huì)明確待處理的數(shù)據(jù)量In。約簡(jiǎn)任務(wù)需要處理的數(shù)據(jù)量是未知的，但可以使用之前的工作進(jìn)行估算。此外，此處將輸入數(shù)據(jù)量的比率定義為r，其數(shù)學(xué)表達(dá)式為：

Out=r×In

(2)

假設(shè)每項(xiàng)工作都有一個(gè)所有者，它能夠處理工作并且給出關(guān)于執(zhí)行的等級(jí)Π。因此作業(yè)J的屬性可以表示為：

Prop(J)=(A,D,B,In,r|Out=r×In,Owner)

(3)

每項(xiàng)工作J都會(huì)分配到特定數(shù)量的槽，其中，用于映射的槽稱為SLmap，用于約簡(jiǎn)的槽稱為SLreduce，同一個(gè)槽可以同時(shí)用于映射和約簡(jiǎn)[13]。因此在這種情況下，槽的總數(shù)SL≤SLmap+Slreduce。

每項(xiàng)任務(wù)Ti可以通過(guò)下列屬性進(jìn)行關(guān)聯(lián)：

(1) 處理時(shí)間Pi，先驗(yàn)評(píng)估映射任務(wù)或約簡(jiǎn)任務(wù)，它用于計(jì)算作業(yè)的總時(shí)間：

(4)

(5)

(3) 截止時(shí)間di，其由集群資源管理器為每項(xiàng)任務(wù)設(shè)定，用于處理任務(wù)執(zhí)行間的同步問(wèn)題：

(6)

(4) 權(quán)重wi，其取決于資源消耗，與處理時(shí)間Pi和分配給任務(wù)的預(yù)算Yi的乘積成比例，即：

(7)

式中:α為比例常數(shù)，如果α≤1，則任務(wù)調(diào)度和執(zhí)行將服從于總預(yù)算；否則，總開銷可能超過(guò)分配的預(yù)算?？紤]到預(yù)算估計(jì)的性能，有：

(8)

(9)

(5) 擁有者的反饋πi，擁有者可以使用相同的值評(píng)級(jí)所有的任務(wù)，全局評(píng)級(jí)矢量Π可以表示為：

Π=[πi]Ti∈J

(10)

式中:π值可以通過(guò)計(jì)算測(cè)量任務(wù)執(zhí)行的表現(xiàn)得到。例如，可以考慮實(shí)際執(zhí)行時(shí)間coste(Ti)和任務(wù)完成度Ci來(lái)估計(jì)評(píng)級(jí)值，即：

(11)

上述定義的參數(shù)值和權(quán)重均可根據(jù)任務(wù)屬性和擁有者生成任務(wù)后動(dòng)態(tài)分配。因此，任務(wù)Ti的屬性表示如下：

Prop(Ti)=(pi,Yi,di,fi,πi,type=map|reduce)

(12)

MOSMT解決的是多目標(biāo)優(yōu)化問(wèn)題，則需要滿足多個(gè)約束條件和盡可能多的目標(biāo)。因此，MOSMT算法考慮如下多重優(yōu)化問(wèn)題：

(13)

此外，MOSMT模型中考慮目標(biāo)與用戶想要獲得的內(nèi)容相關(guān)，最大目標(biāo)與用戶反饋有關(guān)，并且用戶設(shè)定截止時(shí)間和預(yù)算的值。為了實(shí)現(xiàn)上述約束，需要了解關(guān)于映射任務(wù)與約簡(jiǎn)任務(wù)的信息、處理節(jié)點(diǎn)的信息以及了解CPU內(nèi)存、IO傳輸速率等信息[14]。

1.2 調(diào)度策略

在所提調(diào)度算法中，采用在每個(gè)步驟中的工作和資源間的最佳匹配來(lái)滿足。但最理想的方式是全面了解所有集群，找到需要在特定時(shí)刻運(yùn)行的所有作業(yè)與可用資源之間的最佳匹配。

集群中任務(wù)執(zhí)行順序匹配算法詳見算法1。每個(gè)節(jié)點(diǎn)會(huì)把預(yù)測(cè)信息通過(guò)heartbeat發(fā)送給RAM，RAM把這些預(yù)測(cè)信息合并起來(lái)會(huì)產(chǎn)生一個(gè)全局的視圖，通過(guò)該視圖了解到最早結(jié)束任務(wù)的信息，把該任務(wù)對(duì)應(yīng)的節(jié)點(diǎn)作為被選中的節(jié)點(diǎn)，把任務(wù)完成之后釋放的資源加上節(jié)點(diǎn)本身剩余的資源作為節(jié)點(diǎn)的空余資源繼續(xù)調(diào)用作業(yè)選擇算法與任務(wù)選擇算法，最終選擇一個(gè)與節(jié)點(diǎn)最匹配的任務(wù)。但是，由于該節(jié)點(diǎn)的資源需要在最早結(jié)束任務(wù)完成之后才能把資源分配給選擇出的任務(wù)，因此可以提前把選擇出的任務(wù)的數(shù)據(jù)提前傳輸?shù)阶钤缃Y(jié)束任務(wù)所在節(jié)點(diǎn)，以達(dá)到任務(wù)數(shù)據(jù)本地性，減少數(shù)據(jù)傳輸時(shí)間，從而減少作業(yè)完成時(shí)間。

算法1集群中任務(wù)執(zhí)行順序匹配算法

輸入：作業(yè)隊(duì)列J，作業(yè)配置信息Conf，預(yù)測(cè)模型結(jié)果

輸出：任務(wù)執(zhí)行序列AssignedTask

1: Receive pieces of information through a heartbeat

2:ifnot exist free resourcethen

3:sort(NM,NMtasktimeremain)

4: selectNMof task first end time

5:endif

6:job=SelectAssignJob(J,NM)

7:length=Conf.GetMapTaskSize(job)

8:fori=0;i

9:score[i]=SelectAssignTask(NM,taski)

10:endfor

11:task=Maxscore(score)

12:AssignedTask.add(Task)

13:ifexist delay resourcethen

14: wait for the node to release the resource and move the date of task to NM in advance

15:endif

16:returnAssignedTask

MOSMT算法遵循最佳使用作業(yè)資源策略，詳見算法2。如果有足夠的槽用于映射任務(wù)與約簡(jiǎn)任務(wù)，便能夠在指定的預(yù)算中完成作業(yè)并且直到截止時(shí)間結(jié)束，則服務(wù)函數(shù)返回正值。算法2驗(yàn)證了每個(gè)服務(wù)中工作和資源之間的分配，然后通過(guò)每個(gè)服務(wù)結(jié)果的總和來(lái)判斷哪種分配方式更好。

算法2MOSMT 調(diào)度算法

要求2：taskQueue一個(gè)屬于工作J的所有任務(wù)Ti的隊(duì)列

要求3：assignedTasks分配到每個(gè)工作者節(jié)點(diǎn)的任務(wù)隊(duì)列

1:foreachworkernode∈Rdo

2:maxService←service(workernode)

3:F←0

4:foreachassignedTask∈workernode.assignedTasksdo

5:newAssignedTasks←workernode.assignedTasks-assignedTask

6:whiletaskQueue≠?do

7:task←taskQueue.edq()

8:fi←weight(task)

9:newAssignedTasks←newAssignedTasks∪task

10:ifservice(newAssignedTasks)>maxServicethen

11:maxService←service(newAssignedTasks)

12:F←F+fi

13:endif

14:endwhile

15:endfor

16:workernode.assignedTasks←newAssignedTasks

17:endfor

為了計(jì)算服務(wù)結(jié)果，還需找出Slmap和Slreduce是否可由特定的資源集群提供。 將cost(map) 和cost(reduce)分別定義為通過(guò)映射任務(wù)和約簡(jiǎn)任務(wù)處理數(shù)據(jù)的時(shí)間成本。此外，將budger(map) 和budgerI(reduce)分別表示映射任務(wù)和約簡(jiǎn)任務(wù)的預(yù)算成本。除上述成本以外，仍需考慮當(dāng)數(shù)據(jù)不在約簡(jiǎn)任務(wù)中運(yùn)行的節(jié)點(diǎn)上時(shí)所支付的成本(僅適用于集群中存在的數(shù)據(jù))。因此，還應(yīng)該確定數(shù)據(jù)傳輸和處理的時(shí)間成本cost(data)和預(yù)算成budget(data)。

將start(map)和start(reduce)分別定義為映射任務(wù)和約簡(jiǎn)任務(wù)的開始時(shí)間，當(dāng)start(map)為定值時(shí)表示所有映射任務(wù)均在一項(xiàng)工作到達(dá)內(nèi)部隊(duì)列時(shí)開始，即start(map)=A。為了計(jì)算工作J所需要的映射槽的數(shù)量，需要掌握start(map) 的最大值start(max)(map)，則SLmap和SLreduce最小值的數(shù)學(xué)表達(dá)式如下：

(14)

(15)

基于時(shí)間處理成本的考慮，使用預(yù)算Bused定義為是時(shí)間成本和資源數(shù)量之間的乘積，即：

(16)

MOSMT算法能夠集成在Hadoop平臺(tái)中。由于JobTracker是一個(gè)獨(dú)立的組件，因此新的調(diào)度程序應(yīng)該擴(kuò)展為TaskScheduler，并且定義其屬性和方法。完成擴(kuò)展后，新調(diào)度程序需要插件。在MapReduce的配置文件中，有一個(gè)變量指示使用的算法，默認(rèn)情況下變量為Fair Scheduler，如果用戶想使用新的算法，只需修改配置參數(shù)并指定它。

2 算法在MobiWay中的應(yīng)用

城市交通是現(xiàn)代城市生活的伴隨，其可持續(xù)性在很大程度上取決于不同資源的消耗，如電力和燃料。因此，它表現(xiàn)為二氧化碳(CO2)和當(dāng)?shù)匚廴疚锱欧?，直接影響公民的生活質(zhì)量。城市交通造成40%的二氧化碳排放和70%的道路運(yùn)輸產(chǎn)生的其他污染物排放公路運(yùn)輸占整個(gè)運(yùn)輸產(chǎn)業(yè)溫室氣體排放量的70%以上，占所有排放總量的13%(運(yùn)輸產(chǎn)業(yè)占排放總量的近20%)[18]。智能交通系統(tǒng)(Intelligent Transportation Systems, ITS)旨在通過(guò)結(jié)合專業(yè)基礎(chǔ)設(shè)施，通信技術(shù)和創(chuàng)新服務(wù)的解決方案來(lái)克服此類問(wèn)題，以提高交通和移動(dòng)管理、多模式或道路交通解決方案的質(zhì)量[15]。

然而，為了開發(fā)準(zhǔn)確的交通模型，能夠理解交通現(xiàn)象并從交通流量在現(xiàn)實(shí)世界城市中表現(xiàn)的統(tǒng)計(jì)模型做出決策，需要大量的數(shù)據(jù)。感應(yīng)移動(dòng)設(shè)備和各種移動(dòng)應(yīng)用，其目標(biāo)是提供一個(gè)生態(tài)系統(tǒng)框架，使城市社區(qū)能夠利用移動(dòng)的共享價(jià)值，這些價(jià)值可以超越社會(huì)網(wǎng)絡(luò)的經(jīng)典觀點(diǎn)，分別是當(dāng)前的服務(wù)創(chuàng)造趨勢(shì)。為了促進(jìn)協(xié)作，該框架旨在在由應(yīng)用提供商組成的服務(wù)云中分發(fā)不同的信息源(來(lái)自最終用戶或ITS服務(wù)，例如出租車公司、交付網(wǎng)絡(luò)等)。由于移動(dòng)用戶將提供各種類型的傳感器數(shù)據(jù)，因此必須在數(shù)十萬(wàn)參與者的網(wǎng)絡(luò)和具有不同興趣的共存服務(wù)之間保證智能數(shù)據(jù)收集、處理和共享。該框架構(gòu)建了一個(gè)集成服務(wù)和應(yīng)用程序的生態(tài)系統(tǒng)，靈活且可重新配置，提供給用戶多個(gè)包[16]。MobiWay的架構(gòu)如圖1所示。

圖1 MobiWay 理論架構(gòu)

該體系結(jié)構(gòu)中的一個(gè)重要組成部分是數(shù)據(jù)聚合，旨在處理大量的流量數(shù)據(jù)，以便在城市級(jí)別提供準(zhǔn)確的流量數(shù)據(jù)模型。這意味著需要收集來(lái)自城市數(shù)百萬(wàn)輛汽車的數(shù)據(jù)，并持續(xù)存儲(chǔ)更長(zhǎng)時(shí)間。進(jìn)一步定期處理這些數(shù)據(jù)，得出流量可能性的統(tǒng)計(jì)和概率模型，取決于諸如一天中的時(shí)間、天氣狀況、預(yù)定事件等參數(shù)。所提出的算法可以處理不同粒度級(jí)別的數(shù)據(jù)在聚合、清理、統(tǒng)計(jì)分析等過(guò)程中出現(xiàn)的問(wèn)題。通過(guò)分析城市不同區(qū)域的宏觀流量進(jìn)行預(yù)處理，進(jìn)行微觀層面和細(xì)粒度層面的條件評(píng)估。

處理應(yīng)用程序使用MapReduce范例，Apache Hadoop和Spark作為支持技術(shù)。顧名思義，MapReduce有兩個(gè)重要的任務(wù)類型：map和reduce。從輸入接收的數(shù)據(jù)被分成塊，因此映射任務(wù)僅接收整個(gè)數(shù)據(jù)的一部分，并在許多地圖任務(wù)中并行運(yùn)行[17]。所有映射任務(wù)的輸出都會(huì)進(jìn)行排序并重定向到reducer。數(shù)據(jù)存儲(chǔ)在文件系統(tǒng)中，因此Hadoop為此部分使用HDFS(Hadoop分布式文件系統(tǒng))。調(diào)度程序負(fù)責(zé)計(jì)劃如何將作業(yè)分配給映射或約簡(jiǎn)器。實(shí)際應(yīng)用中期望節(jié)點(diǎn)能夠負(fù)責(zé)計(jì)算和存儲(chǔ)，在節(jié)點(diǎn)上調(diào)度計(jì)劃安排的任務(wù)，以減少網(wǎng)絡(luò)中的流量。但是為了實(shí)現(xiàn)這一點(diǎn)，調(diào)度程序需要一種改進(jìn)的算法[18]。因此，對(duì)于MobiWay，需要使用可提供優(yōu)化性能的適當(dāng)接口來(lái)實(shí)現(xiàn)map和reduce功能(希望獲得成本和時(shí)間最優(yōu)的解決方案)。

3 實(shí)驗(yàn)與分析

本節(jié)介紹了MOSMT算法的比較結(jié)果，開發(fā)并測(cè)試新Hadoop調(diào)度程序的所有設(shè)置步驟。首先介紹Hadoop框架所需的配置，然后設(shè)置調(diào)度程序負(fù)載模擬器，最后解釋了第一個(gè)Hadoop應(yīng)用程序，其目標(biāo)為了解場(chǎng)景背后的范例、工作性質(zhì)和任務(wù)。

Hadoop集群設(shè)置考慮了如下的配置參數(shù)：

(1) Hadoop集群，在64位架構(gòu)的Ubuntu計(jì)算機(jī)上進(jìn)行實(shí)驗(yàn)，包含maven、libssl-dev、cmake和protobuf庫(kù)；

(2) HDFS配置，dfs.replication設(shè)置為支持容錯(cuò)；

(3) 調(diào)度負(fù)載模擬器(Scheduling Load Simulator，SLS)設(shè)置(整個(gè)模擬器內(nèi)存或每個(gè)容器的內(nèi)存，虛擬內(nèi)核的數(shù)量等)；

(4) Rumen工具用于信息轉(zhuǎn)換并將信息添加至作業(yè)歷史記錄中，其輸出將是json文件。這個(gè)json文件將進(jìn)一步用作SLS的輸入。

當(dāng)新的調(diào)度算法實(shí)現(xiàn)后，很難將其部署在真實(shí)的集群中，并且消耗大量的計(jì)算資源。但是使用SLS能夠很好地解決這一問(wèn)題，因?yàn)镾LS更容易為調(diào)度程序部署各種不同的功能，但只能使用一臺(tái)計(jì)算機(jī)完成SLS的配置。采用該方式，不僅節(jié)省了大量時(shí)間，而且降低了成本。

圖2所示為SLS的體系結(jié)構(gòu)。正如前文所述，SLS的配置均在一臺(tái)機(jī)器上運(yùn)行，這意味著所有Hadoop組件應(yīng)該在沒(méi)有網(wǎng)絡(luò)組件的同一臺(tái)機(jī)器上運(yùn)行。由于調(diào)度程序是資源管理器的主要組件之一，因此其便是SLS中需要更改的主體。通常而言，SLS可看成是主調(diào)度程序的包裝器，如圖2中的灰色部分所示。在仿真器中，SLS模擬每個(gè)節(jié)點(diǎn)管理器和每個(gè)應(yīng)用程序管理器。

圖2 調(diào)度負(fù)載模擬器架構(gòu)

當(dāng)作業(yè)執(zhí)行映射任務(wù)和約簡(jiǎn)任務(wù)時(shí)，JobHistory程序?qū)⒈Ａ羲袣v史記錄。但這個(gè)歷史記錄并不是完全按照SLS指標(biāo)顯示的，因此模擬器使用不同的輸入。

數(shù)據(jù)信息轉(zhuǎn)換過(guò)程包含兩個(gè)步驟：TraceBuilder和Folder。第一個(gè)步驟是處理數(shù)據(jù)以獲得更好的格式，第二個(gè)步驟是根據(jù)一些統(tǒng)計(jì)運(yùn)算添加其他信息。這兩個(gè)步驟使用兩個(gè)命令執(zhí)行，該命令可以在Hadoop框架中的Rumen工具目錄中找到，如需了解該命令的其他信息、參數(shù)和選項(xiàng)可以參考文獻(xiàn)[4]。

3.1 性能度量

調(diào)度負(fù)載模擬器使用Metrics庫(kù)來(lái)評(píng)估調(diào)度算法的性能。通過(guò)SLS使用量來(lái)進(jìn)行具體量化。選取以下側(cè)重于時(shí)間成本和資源使用方式的度量指標(biāo)與目前廣泛使用的Fair、FIFO算法進(jìn)行對(duì)比實(shí)驗(yàn)。

度量指標(biāo)如下：

(1) 應(yīng)用程序和容器：在此期間運(yùn)行的應(yīng)用程序量和容量；

(2) 資源：已被使用資源量與剩余資源量；

(3) 每隊(duì)列資源：每個(gè)隊(duì)列所使用的資源量與剩余的資源量；

(4) 時(shí)間：每個(gè)調(diào)度程序均有多個(gè)操作，比如添加、刪除和更新節(jié)點(diǎn)，以及添加和刪除應(yīng)用，因此每個(gè)操作的時(shí)間都有很重要的意義；

(5) 內(nèi)存：了解模擬器內(nèi)存使用量是必要的。

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

本節(jié)測(cè)試新調(diào)度算法主要是將其與文獻(xiàn)[10]所提的FIFO調(diào)度程序和文獻(xiàn)[11]所提的Fair調(diào)度程序進(jìn)行比較，由于Fair、FIFO算法已在Hadoop框架中實(shí)現(xiàn)，無(wú)需額外的工作量。為了使用SLS，需要兩個(gè)輸入文件：帶工作負(fù)載的json文件和帶拓?fù)涞膉son文件。

在Hadoop上運(yùn)行5 000個(gè)任務(wù)，使用Rumen以模擬器所需的格式獲取工作負(fù)載。為此，使用命令TraceBuilde，將歷史記錄作為輸入，并生成作業(yè)跟蹤和使用的拓?fù)洹Ｓ捎诒舅惴▌?chuàng)建了12個(gè)節(jié)點(diǎn)的拓?fù)浣Y(jié)構(gòu)，所以由TraceBuilde生成拓?fù)浣Y(jié)構(gòu)不是必需的。使用了具有不同輸入數(shù)據(jù)的MobiWay應(yīng)用程序，實(shí)驗(yàn)中有四種類型的輸入，按其大小分類，劃分為小型、中型、大型和超大型。

圖3顯示了群集中節(jié)點(diǎn)的已分配核心數(shù)。Fair和MOSMT調(diào)度程序的核心用法非常相似，均與作業(yè)執(zhí)行時(shí)間相關(guān)。從圖中可以看出，F(xiàn)air和MOSMT具有最佳的核心分配方案。

圖3 在Hadoop集群中一個(gè)節(jié)點(diǎn)的分配核心數(shù)量

當(dāng)作業(yè)使用更多內(nèi)存進(jìn)行映射或縮減任務(wù)時(shí)，模擬器內(nèi)存的分配數(shù)量將增加。從圖4中可明顯看出，當(dāng)輸入增多時(shí)，F(xiàn)IFO和FAIR使用了更多的內(nèi)存。同時(shí)，這也表明了MOSMT不會(huì)執(zhí)行超過(guò)截止期限、預(yù)算或兩者的任務(wù)。

圖4 在Hadoop集群中一個(gè)節(jié)點(diǎn)的內(nèi)存分配

圖5和圖6顯示了Hadoop集群中資源配置和資源重新配置/更新的性能。從中可以看出，MOSMT算法的時(shí)間成本與Fair、FIFO相似，不過(guò)性能優(yōu)于兩者，因?yàn)镸OSMT算法會(huì)動(dòng)態(tài)計(jì)算用于映射與約簡(jiǎn)任務(wù)槽的數(shù)量。

圖5 Hadoop集群中的資源提供性能

圖6 Hadoop集群中資源更新的性能

算法運(yùn)行時(shí)作業(yè)提交的順序是一定的，因此作業(yè)的執(zhí)行順序與提交時(shí)相同。不過(guò)調(diào)度程序重新排列作業(yè)時(shí)，即使有很多輸入量也應(yīng)能夠訪問(wèn)資源。在MOSMT算法中最大的工作沒(méi)有運(yùn)行權(quán)限，因?yàn)檩斎胍?guī)模太大，截止時(shí)間和預(yù)算將超過(guò)預(yù)期。

圖7的結(jié)果表明，所有測(cè)試的調(diào)度算法在同一個(gè)工作中分配集群中的任務(wù)沒(méi)有等待任務(wù)而長(zhǎng)時(shí)間停留在隊(duì)列中。

圖7 任務(wù)分配調(diào)度

算法度量指標(biāo)體現(xiàn)了每個(gè)操作的時(shí)間成本，具體操作包括：分配節(jié)點(diǎn)、添加節(jié)點(diǎn)、刪除節(jié)點(diǎn)、節(jié)點(diǎn)更新、添加應(yīng)用程序、刪除應(yīng)用程序以及容器過(guò)期等。由于條件限制，只完成了添加節(jié)點(diǎn)、節(jié)點(diǎn)更新以及添加應(yīng)用程序并刪除應(yīng)用程序四個(gè)操作并進(jìn)行算法性能測(cè)試，Hadoop集群中任務(wù)設(shè)置的性能測(cè)試結(jié)果如圖8和圖9所示。顯然，在應(yīng)用設(shè)置成本中MOSMT算法在不同步長(zhǎng)下增加節(jié)點(diǎn)所需的平均時(shí)間最長(zhǎng)，而在應(yīng)用完成成本對(duì)比中所需時(shí)間最短。

圖8 在Hadoop集群中的應(yīng)用設(shè)置成本

圖9 Hadoop集群中應(yīng)用完成成本

調(diào)度器的時(shí)間成本如圖10所示。由于MOSMT算法側(cè)重于考慮時(shí)間成本，因此在這個(gè)方面表現(xiàn)得更具優(yōu)勢(shì)，而FIFO和Fair調(diào)度程序的結(jié)果相似。

圖10 調(diào)度階段的時(shí)間成本

調(diào)度器的時(shí)間成本與調(diào)度任務(wù)執(zhí)行的時(shí)間相關(guān)，圖11顯示了所有計(jì)劃任務(wù)的開始時(shí)間、完成時(shí)間和持續(xù)時(shí)間?？梢钥闯鱿鄬?duì)時(shí)間比較接近，意味著我們可以使用多種優(yōu)化算法獲得相同的優(yōu)化性能。

(a) 開始時(shí)間

(b) 完成時(shí)間

(c) 持續(xù)時(shí)間圖11 調(diào)度任務(wù)的運(yùn)行時(shí)間

4 結(jié) 語(yǔ)

針對(duì)Hadoop平臺(tái)多任務(wù)多目標(biāo)調(diào)度難題，提出了一種MOSMT算法。算法包括:Hadoop平臺(tái)中最相關(guān)的約束：避免資源爭(zhēng)用和集群的最佳工作量;與優(yōu)化目標(biāo)：截止日期和預(yù)算。應(yīng)用于MobiWay評(píng)估MOSMT算法性能，測(cè)試結(jié)果表明，當(dāng)工作存在成本和時(shí)間限制時(shí)，該算法相比于FIFO和Fair算法更為有效。在一定的資源和時(shí)間條件下，MOSMT通過(guò)使用調(diào)度負(fù)載模擬器配置不同的算法功能，從而降低時(shí)間成本和資源占用，實(shí)現(xiàn)多目標(biāo)多任務(wù)的高效合理調(diào)度。

研究過(guò)程中假定MapReduce作業(yè)均是獨(dú)立的，調(diào)度任務(wù)進(jìn)行前或者期間節(jié)點(diǎn)均不會(huì)發(fā)生故障，但這會(huì)使該算法的應(yīng)用受到很多局限。后期，將針對(duì)用于工作流程的迭代MapReduce以及基于過(guò)去迭代信息進(jìn)行預(yù)測(cè)的調(diào)度策略作進(jìn)一步研究。此外，所提算法的評(píng)估指標(biāo)有待完善，以更好地呈現(xiàn)適用多任務(wù)多目標(biāo)調(diào)度算法的重要性，當(dāng)然，算法的可擴(kuò)展性是不容忽視的。