胡 靜

(山西農(nóng)業(yè)大學(xué) 軟件學(xué)院，山西 晉中 030801)

0 引 言

目前大數(shù)據(jù)計(jì)算平臺(tái)中已經(jīng)存在的調(diào)度器如默認(rèn)的FIFO調(diào)度器、公平調(diào)度器和計(jì)算能力調(diào)度器[1]等其它算法[2,3]調(diào)度作業(yè)時(shí)只考慮到了平臺(tái)資源利用率但沒(méi)有考慮作業(yè)截止時(shí)間和服務(wù)商收益問(wèn)題。針對(duì)作業(yè)截止時(shí)間要求，部分研究學(xué)者[4-9]以作業(yè)截止期限為約束提出一種相應(yīng)的作業(yè)調(diào)度算法以提高作業(yè)的執(zhí)行效率與平臺(tái)資源利用率，但仍沒(méi)考慮服務(wù)商的收益問(wèn)題。文獻(xiàn)[10-14]提出相關(guān)調(diào)度算法目的是使服務(wù)商的利潤(rùn)最大化。文獻(xiàn)[15-17]均提出了新的調(diào)度方法，保證服務(wù)商的最大收益、服務(wù)的截止時(shí)間和平臺(tái)的資源利用率。在服務(wù)商指定時(shí)間內(nèi)完成每個(gè)作業(yè)可獲得的收益模式和現(xiàn)有作業(yè)調(diào)度器下，服務(wù)商沒(méi)有考慮到作業(yè)截止時(shí)間的準(zhǔn)確性和作業(yè)執(zhí)行的迫切需求，并且也沒(méi)有考慮作業(yè)調(diào)度結(jié)果對(duì)平臺(tái)資源利用率的影響。

基于上述問(wèn)題，本文提出了一種服務(wù)商收益模式—獎(jiǎng)懲共存收益模式(RP Model)。該收益模式考慮用戶對(duì)服務(wù)商的獎(jiǎng)勵(lì)政策，即當(dāng)服務(wù)商在作業(yè)截止時(shí)間之前的一定時(shí)間范圍內(nèi)完成作業(yè)時(shí)對(duì)服務(wù)商給予相應(yīng)的獎(jiǎng)勵(lì)值。此收益模式針對(duì)的是不確定作業(yè)截止時(shí)間是否準(zhǔn)確的用戶，并且該類用戶對(duì)于作業(yè)執(zhí)行完成有迫切需求。服務(wù)商為了滿足用戶較短的作業(yè)完成時(shí)間需求，盡量縮短每個(gè)作業(yè)的完成時(shí)間。當(dāng)作業(yè)實(shí)際完成時(shí)間比用戶提供的截止時(shí)間短時(shí)，服務(wù)商將該作業(yè)的實(shí)際完成時(shí)間作為較準(zhǔn)確的截止時(shí)間反饋給用戶，使得用戶以后提交相同的作業(yè)時(shí)就可以提供較準(zhǔn)確的截止時(shí)間，并且推進(jìn)了用戶處理作業(yè)群的整體行為。獎(jiǎng)懲共存收益模式的提出實(shí)現(xiàn)了服務(wù)商與用戶的利益共贏。

本文以獎(jiǎng)懲共存收益模式為目標(biāo)，提出了一種高效的MapReduce作業(yè)調(diào)度器——最大收益完成時(shí)間資源利用率調(diào)度器(MPCRS)，以盡量縮短每個(gè)作業(yè)的完成時(shí)間，提高平臺(tái)資源利用率，使服務(wù)商獲得最大收益。

1 MPCRS調(diào)度器設(shè)計(jì)

本文是在Hadoop2.x的Yarn資源管理系統(tǒng)的基礎(chǔ)上提出的MPCRS。Yarn作為統(tǒng)一資源管理系統(tǒng)，核心組件為全局資源管理器(resource manager，RM)，負(fù)責(zé)整個(gè)平臺(tái)的資源管理和分配。它主要由兩個(gè)組件構(gòu)成：作業(yè)調(diào)度器(Scheduler)和應(yīng)用程序管理器ApplicationsManager(ASM)。調(diào)度器能夠根據(jù)容量、隊(duì)列等限制條件，將平臺(tái)中的資源按照作業(yè)資源需求分配給各個(gè)將要運(yùn)行的作業(yè)。由于調(diào)度器是一個(gè)可插拔的組件，故本文將以滿足服務(wù)商最大收益、平臺(tái)最大資源利用以及作業(yè)最短完成時(shí)間為目標(biāo)設(shè)計(jì)一種MPCRS作業(yè)調(diào)度器。圖1展示了在Yarn平臺(tái)中MPCRS的作用以及構(gòu)成。

圖1 MPCRS的作用與構(gòu)成

如圖1所示，該平臺(tái)允許多用戶提交多個(gè)帶有SLA約束的作業(yè)。RM中主要包含MPCRS和ASM兩種組件，其中MPCRS是由RP Model、基于任務(wù)執(zhí)行時(shí)間的確定輪數(shù)算法(TRN)以及基于最大輪數(shù)的作業(yè)調(diào)度算法(MRNS)組成。RP Model將每個(gè)作業(yè)在不同時(shí)間段內(nèi)可獲得的相應(yīng)收益值作為TRN算法與MRNS算法的輸入值。為了盡量縮短每個(gè)作業(yè)的完成時(shí)間，TRN算法以RP Model下可獲得的收益值為標(biāo)準(zhǔn)，根據(jù)各個(gè)作業(yè)的Map和Reduce任務(wù)執(zhí)行時(shí)間，確定出作業(yè)在不同獎(jiǎng)懲階段的Map和Reduce最大輪數(shù)組合以及最大標(biāo)準(zhǔn)時(shí)間。MRNS算法得到最大輪數(shù)組合方案和最大標(biāo)準(zhǔn)時(shí)間值后，結(jié)合平臺(tái)中現(xiàn)有資源數(shù)量，考慮平臺(tái)資源利用率，制定出對(duì)于當(dāng)前所有作業(yè)的調(diào)度策略(TS)。ASM將會(huì)根據(jù)TS策略啟動(dòng)相應(yīng)作業(yè)的(application master，AM)，AM向RM申請(qǐng)所需的資源，RM為其任務(wù)分配在各個(gè)(node manager，NM)上的Container資源，使得該作業(yè)得以開(kāi)始運(yùn)行。AM將作業(yè)分為Map和Reduce任務(wù)，由于MPCRS產(chǎn)生的TS策略是基于任務(wù)級(jí)別的，故為作業(yè)分配資源即為Map或Reduce任務(wù)分配資源。

2 MPCRS調(diào)度器實(shí)現(xiàn)

本文提出的MPCRS調(diào)度器是生成相應(yīng)的作業(yè)調(diào)度策略，而具體任務(wù)分配方法仍然遵循MapReduce的動(dòng)態(tài)分配原則，因此不會(huì)對(duì)平臺(tái)中負(fù)載均衡等其它性能特性造成影響。在滿足平臺(tái)資源利用率最大的條件下，雖盡量縮短每個(gè)作業(yè)的完成時(shí)間，但不可避免會(huì)造成個(gè)別作業(yè)超出截止期限，無(wú)法按時(shí)完成。出現(xiàn)這種情況時(shí)需根據(jù)服務(wù)商收益最大化的目標(biāo)對(duì)作業(yè)的收益與賠付代價(jià)進(jìn)行衡量評(píng)估，經(jīng)過(guò)整體收益權(quán)衡后選擇放棄一些收益較少或賠付較少的作業(yè)。

2.1 獎(jiǎng)懲共存收益模式-RP Model

在計(jì)算平臺(tái)中認(rèn)為每個(gè)節(jié)點(diǎn)的處理能力都大致相同，由于平臺(tái)中的資源是統(tǒng)一進(jìn)行管理和分配，故可動(dòng)態(tài)分配的Container資源用R表示。用戶提交的作業(yè)j已知如下信息：j的截止時(shí)間j_deadline；在j_deadline之前j被完成，服務(wù)商可獲得的收益j_profit；如果j的實(shí)際完成時(shí)間j_completion的a倍比j_deadline短，用戶按照SLA中規(guī)定的獎(jiǎng)勵(lì)比率α，支付除收益以外的獎(jiǎng)勵(lì)值j_profit×α×a；j的實(shí)際完成時(shí)間j_completion超過(guò)j_deadline時(shí)，按照服務(wù)商與用戶簽訂的SLA賠付比率β進(jìn)行賠償，即當(dāng)j_deadlineb×j_deadline， 則需要賠付給用戶原收益的γ倍，即j_profit×γ；j具有的Map數(shù)量j_Nm和Reduce數(shù)量j_Nr；j中每一輪Map任務(wù)的執(zhí)行時(shí)間j_Tm和每一輪Reduce任務(wù)的執(zhí)行時(shí)間j_Tr。為了提高作業(yè)的執(zhí)行效率和平臺(tái)資源利用率，在平臺(tái)資源充足的條件下，要盡量使同一個(gè)作業(yè)的多個(gè)任務(wù)并行執(zhí)行，而每次并行執(zhí)行任務(wù)的時(shí)間稱為一輪任務(wù)的執(zhí)行時(shí)間。

根據(jù)以上關(guān)于作業(yè)的收益與賠付信息，結(jié)合平臺(tái)中可分配的資源數(shù)量，RP Model如下

(1)

(2)

式(1)表示完成所有作業(yè)后可獲得的收益和，其中每個(gè)作業(yè)的實(shí)際收益是由該作業(yè)在截止時(shí)間之前完成的收益j_profit與額外的獎(jiǎng)勵(lì)或者懲罰f(j_profit) 組成。式(2)確保了將要運(yùn)行的任務(wù)每次并行請(qǐng)求資源時(shí)資源數(shù)不超過(guò)平臺(tái)中可動(dòng)態(tài)分配的資源總和。獎(jiǎng)懲共存函數(shù)f(j_profit) 表示如下

(3)

其中，α是在作業(yè)實(shí)際完成時(shí)間比規(guī)定的截止期限短a倍時(shí)可獲得的獎(jiǎng)勵(lì)比率，β是作業(yè)實(shí)際完成時(shí)間比規(guī)定的截止期限長(zhǎng)但沒(méi)有超過(guò)截止時(shí)間的b倍時(shí)作業(yè)的賠付比率，γ是作業(yè)實(shí)際完成時(shí)間超過(guò)規(guī)定截止時(shí)間b倍時(shí)所要賠付的收益倍數(shù)。在考慮到盡量使每個(gè)作業(yè)都在截止期限之前完成，故設(shè)置賠付率值要比獎(jiǎng)勵(lì)率值大，即α≤β≤1； 而作為長(zhǎng)時(shí)間超出截止期限的懲罰設(shè)置γ≥1。 由于不能簡(jiǎn)單的根據(jù)作業(yè)實(shí)際完成時(shí)間和截止時(shí)間值就規(guī)定用戶付出獎(jiǎng)勵(lì)或服務(wù)商付出賠付，而應(yīng)該是在兩者差值超過(guò)一定范圍后用戶才需要支付額外的獎(jiǎng)勵(lì)值或服務(wù)商支付額外的賠付值，故設(shè)a,b>1。

2.2 基于任務(wù)執(zhí)行時(shí)間的確定輪數(shù)算法——TRN

TRN算法根據(jù)每個(gè)作業(yè)的Map和Reduce任務(wù)執(zhí)行時(shí)間，以RP Model中可獲得的收益值為標(biāo)準(zhǔn)，確定每個(gè)作業(yè)在不同獎(jiǎng)懲階段的Map和Reduce最大輪數(shù)組合以及最大標(biāo)準(zhǔn)時(shí)間。在上節(jié)中介紹了用戶提交作業(yè)時(shí)已知的信息，其中包括作業(yè)j中每一輪Map任務(wù)的執(zhí)行時(shí)間j_Tm和每一輪Reduce任務(wù)的執(zhí)行時(shí)間j_Tr，并且j具有的Map數(shù)量j_Nm和Reduce數(shù)量j_Nr。

TRN算法的結(jié)果是要得到每個(gè)作業(yè)在不同獎(jiǎng)懲階段時(shí)的任務(wù)最大輪數(shù)組合方案與最大標(biāo)準(zhǔn)時(shí)間。其中有關(guān)確定任務(wù)輪數(shù)的因素具體包括

(4)

(5)

(6)

在全部動(dòng)態(tài)可分配資源只分配給一個(gè)作業(yè)的情況下，RN_m是作業(yè)j的Map任務(wù)的最少執(zhí)行輪數(shù)；RN_r則是Reduce任務(wù)的最少執(zhí)行輪數(shù)；式(6)表示作業(yè)j的最短執(zhí)行時(shí)間tleast是由任務(wù)的最少輪數(shù)與每輪任務(wù)的執(zhí)行時(shí)間組成。

算法1展示了如何在各獎(jiǎng)懲階段獲得任務(wù)最大輪數(shù)組合方案以及最大標(biāo)準(zhǔn)時(shí)間。首先，算法根據(jù)作業(yè)的已知信息計(jì)算了每個(gè)作業(yè)的Map和Reduce任務(wù)的最少執(zhí)行輪數(shù)、最短執(zhí)行時(shí)間tleast以及在每個(gè)獎(jiǎng)懲階段的最大標(biāo)準(zhǔn)時(shí)間tstandard(line(2)-line(5))； 其次，在每個(gè)最大標(biāo)準(zhǔn)時(shí)間時(shí)，比較了作業(yè)最短執(zhí)行時(shí)間與最大標(biāo)準(zhǔn)時(shí)間的大小，根據(jù)獎(jiǎng)懲共存函數(shù)f(j_profit) 的模式要求，最大標(biāo)準(zhǔn)時(shí)間的最小值一定是大于等于最短執(zhí)行時(shí)間，故在每個(gè)獎(jiǎng)懲階段都可以得到一種輪數(shù)組合方案A，最大限度地以空間換時(shí)間方案，即 (RN_m,RN_r,tstandard-tleast)(line(8))； 最后，根據(jù)剩余時(shí)間值的大小，找到能夠滿足執(zhí)行一輪Map和一輪Reduce任務(wù)時(shí)間的最大變量值k，i，從而得到方案集 (planjm_t∪planjr_t) ——最大限度的以時(shí)間換空間方案。由于作業(yè)完成時(shí)間超過(guò)截止時(shí)間后服務(wù)商就要對(duì)用戶進(jìn)行賠償，故要盡量保證每個(gè)作業(yè)的完成時(shí)間能夠達(dá)到最短，而任務(wù)的執(zhí)行輪數(shù)會(huì)直接影響到作業(yè)的完成時(shí)間。同一獎(jiǎng)懲階段中，在輪數(shù)不超過(guò)任務(wù)數(shù)量的前提下，即 (RN_m+k)

算法1：TRN algorithm

Input：j_Tm: the processing time of the round map task

j_Tr: the processing time of the round reduce task

j_Nm: the number of map tasks for a job

j_Nr: the number of reduce tasks for a job

f(j_profit): the reward or the punishment of a job

N: the number of jobs

R: dynamically allocate the number of resources

Output：Planj_t: the maximum round numbers plans

tstandard: the maximum standard time for a job

(1)forj=0;j

(2)RN_m←the minimum round numbers of map tasks

(3)RN_r←the minimum round numbers of reduce tasks

(4)tleast←the minimum processing time of a jobj

(5)tstandard∈T←the maximum standard time of every PR stage

(6)whiletstandarddo

(7)iftstandard≥tleastthen

(8) getting the round numbers plan A (RN_m,RN_r), the remaining time (tstandard-tleast)

(9)k,i≥1andk,iareintegersandk,iarethemaximumvaluesthatmeettherequirements

(10)if(tstandard-tleast)≥j_Tmkthen

(11) getting plan B (RN_m+k,RN_r), the remaining time (tstandard-tleast-j_Tm×k)

(12)if(tstandard-tleast-j_Tm×k)≥j_Tr×ithen

(13) getting plan C (RN_m+k,RN_r+i), the remaining time (tstandard-tleast-j_Tm×k-j_Tr×i)

(14)elsethen

(15)planjm_t={A,B}

(16)endif

(17) planjm_t={A, B, C}

(18)endif

(19)if(tstandard-tleast)≥j_Tr×ithen

(20) getting plan D (RN_m,RN_r+i), the remaining time (tstandard-tleast-j_Tr×i)

(21)if(tstandard-tleast-j_Tr×i)≥j_Tr×kthen

(22) getting plan E (RN_m+k,RN_r+i), the remaining time (tstandard-tleast-j_Tr×i-j_Tm×k)

(23)elsethen

(24) planjr_t={A, D}

(25)endif

(26) planjr_t={A, D, E}

(27)endif

(28)Planj_t={A}∪planjm_t∪planjr_t

(29)endif

(30)endwhile

(31)endfor

2.3 基于最大輪數(shù)的作業(yè)調(diào)度算法—MRNS

在TRN算法確定出Map、Reduce任務(wù)最大輪數(shù)組合方案和最大標(biāo)準(zhǔn)時(shí)間后，MRNS算法結(jié)合平臺(tái)中現(xiàn)有資源數(shù)量，考慮平臺(tái)資源利用率，制定出對(duì)于當(dāng)前所有作業(yè)的調(diào)度策略，以實(shí)現(xiàn)收益最大化的目標(biāo)。MRNS算法如下所示：

算法2：MRNS algorithm

Input：Planj_t: the maximum round numbers plans

tstandard: the maximum standard time for a job

N: the number of jobs

δ: the threshold of the resource utilization

Output： TS: the optimal scheduling strategy based on tasks

F: the maximum profit

(1)forj=0;j

(2) whenj_tstandard=j_deadline/a, calculate f(j_profit)

(3)F=F+j_profit

(4)endfor

(5)F=F+max(f(j_profit))

(6)jobjof the maximum reward is added to scheduling queue

(7)whenj_tstandard=j_deadline/a,Planj_tof the jobjis selected

(8)whilePlanj_tdo

(9) recording the completion timej_completion

(10) calculating the remaining resourcesrwhen the jobjbegins to be scheduled till the end

(11)if(R-r)/R≥δthen

(12)idlingtheremainingresourcesandwaitingforthepreviousjobcompletion

(13)fori=0;i

(14)ifj_completion≥i_deadlinethen

(15) the jobiis added to the end of scheduling queue

(16)elseifi_deadline-j_completion≥i_1tstandard+j_completionthen

(17) the jobigets the reward f(i_profit)

(18)elseifi_2tstandard+j_completion≤i_deadline-j_completionthen

(19) the jobigets the reward 0

(20)elseifi_3tstandard+j_completion≤i_deadline-j_completionthen

(21) the jobigets the punishment f(i_profit)elsethen

(22) the jobigets the maximum punishment f(i_profit)

(23)endfor

(24) according to f(i_profit) for each job, sortingN-1 jobs

(25)if?f(i_profit)≥0then

(26) the jobithat has the maximum reward is added to the scheduling queue

(27)elseif?f(i_profit)<0then

(28) according to sorting results, find the jobimee-ting f(i_profit)>(-i_profit×γ) & the minimum f(i_profit)

(29) the jobiis added to the scheduling queueelsethen

(30) ?f(i+n_profit)<0,f=|-i+1_profit×γ|+|-i+2_profit×γ|+…+|-i+n_profit×γ|

(31)iff(i_profit)≥fthen

(32) the jobiis added to the scheduling queueelsethen

(33) find the jobi+nmeeting f(i+n_pro-fit)=-i+n_profit×γthat is the minimum

(34) the jobi+nis added to the scheduling queue

(35)elsethen

(36) when the scheduled jobjhas the remaining resources, recording the start timetrfor the remaining resources

(37)fori=0;i

(38)iftr≤i_1tstandardthen

(39) the remaining resourcesrmeetsPlani_tthat on thei_1tstandard

(40) Comparingtr+i_1tstandardwithi_tstandard

(41) the jobiget the maximum |f(i_profit)| besides the maximum punishment

(42)ifi_1tstandard≤tr≤i_2tstandardthen

(43) the remaining resourcesrmeetsPlani_tthat on thei_2tstandard

(44) Comparingtr+i_2tstandardwithi_tstandard

(45) the jobiget the maximum |f(i_profit)| besides the maximum punishment

(46)endfor

(47) the jobiis scheduled that has the maximum |f(i_profit)|

(48)F=F+f(i_profit)

(49)endwhile

(50)F=F+f(i_profit)

算法2中首先根據(jù)所有作業(yè)在j_tstandard=j_deadline/a時(shí)的最大獎(jiǎng)勵(lì)值f(j_profit)，確定被調(diào)度的作業(yè)并且選擇最大輪數(shù)組合方案集(line(1)-line(7))；其次，在前一作業(yè)的所有輪數(shù)組合方案集中，選擇具有局部最大收益的輪數(shù)組合方案進(jìn)行調(diào)度(line(8)-line(49))；最后將所有作業(yè)加入到調(diào)度隊(duì)列后，根據(jù)每個(gè)作業(yè)相應(yīng)的任務(wù)輪數(shù)組合方案，計(jì)算全局的最大收益值(line(50))。其中，在選擇具有局部最大收益的輪數(shù)組合方案時(shí)，優(yōu)先考慮平臺(tái)的資源利用率。當(dāng)資源利用率大于給定閾值時(shí)，則空閑資源，直到前一作業(yè)執(zhí)行完成后，在剩余作業(yè)中選擇局部收益最大的作業(yè)進(jìn)行串行調(diào)度(line(11)-line(34))。在選擇局部收益最大的作業(yè)時(shí)，通過(guò)每個(gè)作業(yè)的截止時(shí)間與前一作業(yè)的完成時(shí)間差所在范圍，比較每個(gè)作業(yè)在該時(shí)間范圍內(nèi)可獲得的獎(jiǎng)勵(lì)或懲罰值，選擇出使得局部收益最大的作業(yè)和相應(yīng)的任務(wù)輪數(shù)組合方案。當(dāng)資源利用率小于給定閾值時(shí)(line(35)-line(48))，將要調(diào)度的作業(yè)與前一作業(yè)并行執(zhí)行，充分利用平臺(tái)資源，使得資源利用率達(dá)到最大。在選擇合適的作業(yè)加入到調(diào)度隊(duì)列之前，記錄前一作業(yè)有空余資源時(shí)的開(kāi)始時(shí)間點(diǎn)tr，tr與每個(gè)作業(yè)的最大標(biāo)準(zhǔn)時(shí)間tstandard進(jìn)行比較，當(dāng)剩余資源能夠滿足最大標(biāo)準(zhǔn)時(shí)間范圍內(nèi)的任務(wù)最大輪數(shù)要求時(shí)，則選擇 |f(j_profit)| 值最大的作業(yè)加入到調(diào)度隊(duì)列，對(duì)于懲罰值已經(jīng)達(dá)到最大的作業(yè)則放在調(diào)度隊(duì)列最后進(jìn)行調(diào)度。由于每個(gè)被選中的作業(yè)都有多種最大輪數(shù)組合方案，故在每選擇出一種調(diào)度組合方案后則計(jì)算相應(yīng)的局部收益值，最終選擇全局收益值最大的調(diào)度隊(duì)列與調(diào)度策略進(jìn)行調(diào)度。調(diào)度策略中包含了已選擇的作業(yè)任務(wù)輪數(shù)與開(kāi)始時(shí)間點(diǎn)，在調(diào)度前就預(yù)先指定了對(duì)于每個(gè)作業(yè)中任務(wù)的資源分配數(shù)與分配時(shí)間點(diǎn)。

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

3.1 實(shí)驗(yàn)環(huán)境與設(shè)置

在基于Hadoop框架的計(jì)算平臺(tái)中對(duì)本文提出的調(diào)度器進(jìn)行驗(yàn)證，使用的是Hadoop 2.7.1版本。平臺(tái)中的所有節(jié)點(diǎn)都是同構(gòu)節(jié)點(diǎn)，其中包含1個(gè)主節(jié)點(diǎn)和20個(gè)從節(jié)點(diǎn)。每個(gè)節(jié)點(diǎn)的配置信息為CPU 8 cores，16 GB RAM，1 TB hard disk, Red Hat Enterprise Linux6.2 System。資源管理和調(diào)度使用Yarn資源框架，設(shè)置Container大小為1 core和2G RAM，這樣每個(gè)節(jié)點(diǎn)上有8個(gè)Container，整個(gè)平臺(tái)中共有160個(gè)Container。在實(shí)驗(yàn)中設(shè)置塊大小為默認(rèn)的64 M。

3.2 實(shí)驗(yàn)數(shù)據(jù)集與實(shí)驗(yàn)指標(biāo)

為評(píng)估算法性能，使用PUMA benchmark suits中的MapReduce標(biāo)準(zhǔn)應(yīng)用程序，每類程序的數(shù)量、輸入數(shù)據(jù)規(guī)模、截止時(shí)間以及數(shù)據(jù)來(lái)源見(jiàn)表1。

表1 數(shù)據(jù)集

WordCount是CPU密集型程序，TeraSort是I/O密集型程序，Inverted-Index既是CPU密集型也是I/O密集型，3種程序均為典型的MapReduce程序。

在評(píng)估MPCRS的效率時(shí)，將MPCRS分別與FIFO、Fair、EDF調(diào)度算法在作業(yè)完成時(shí)間、服務(wù)商收益及平臺(tái)資源利用率等方面進(jìn)行比較。通過(guò)以下性能指標(biāo)評(píng)價(jià)算法的性能。

(1)作業(yè)完成時(shí)間：j_completion。

(2)最大收益：Profit。

(3)平臺(tái)資源利用率：Utilization。

根據(jù)作業(yè)的開(kāi)始時(shí)間和執(zhí)行時(shí)間可以得出作業(yè)的完成時(shí)間，j_start是作業(yè)的開(kāi)始執(zhí)行時(shí)間，j_execute是作業(yè)j的全部任務(wù)執(zhí)行完畢所經(jīng)歷的時(shí)間，默認(rèn)全部的作業(yè)都同時(shí)到達(dá)，作業(yè)的完成時(shí)間j_completion表示為

j_completion=j_start+j_execute

(7)

j_profit為在SLA協(xié)議中規(guī)定的截止時(shí)間之前完成作業(yè)j可獲得的收益，根據(jù)服務(wù)商可獲得的最大收益，用RP Model中獎(jiǎng)懲共存收益函數(shù)f(j_profit)衡量

(8)

式(3)中所提到的α，β，γ分別為獎(jiǎng)勵(lì)比率、懲罰比率以及最大懲罰倍數(shù)，設(shè)置α=0.3，β=0.5，γ=2，a，b分別為時(shí)間限定倍數(shù)，設(shè)置a=b=1.5。

定義平臺(tái)資源利用率Utilization時(shí)，使用作業(yè)完成后所占資源與時(shí)間的乘積和平臺(tái)中整體資源與時(shí)間的乘積比值表示

(9)

其中，Rtotal是平臺(tái)中全部資源數(shù)量，Ttotal是全部作業(yè)執(zhí)行完畢后的總時(shí)間，Rtaski是作業(yè)j中第i輪任務(wù)執(zhí)行所占用的資源數(shù)量，Ttaski是第i輪任務(wù)所需執(zhí)行時(shí)間。

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

3.3.1 作業(yè)執(zhí)行的高效性

如圖2所示，為4個(gè)調(diào)度器在全部作業(yè)的平均完成時(shí)間指標(biāo)上的對(duì)比結(jié)果。從圖中可以看出，F(xiàn)IFO調(diào)度器的作業(yè)平均完成時(shí)間達(dá)到了24.3 min，依次降低是EDF調(diào)度器22.3 min、Fair調(diào)度器20.8 min以及MPCRS 18 min。FIFO調(diào)度器的作業(yè)平均完成時(shí)間最長(zhǎng)是由于當(dāng)一個(gè)作業(yè)正在執(zhí)行時(shí)會(huì)占用集群中的全部資源，不能使其它作業(yè)開(kāi)始執(zhí)行，故這樣就會(huì)延長(zhǎng)大部分作業(yè)的完成時(shí)間，導(dǎo)致全部作業(yè)的平均完成時(shí)間延長(zhǎng)。MPCRS與FIFO、EDF以及Fair相比，作業(yè)的平均完成時(shí)間有所減短。

圖2 作業(yè)平均完成時(shí)間

如圖3所示，為每個(gè)作業(yè)在不同調(diào)度器的調(diào)度下執(zhí)行完畢后的完成時(shí)間對(duì)比結(jié)果。首先可以看出3個(gè)類型的作業(yè)隨著數(shù)據(jù)量的增大，作業(yè)完成時(shí)間在不斷變長(zhǎng)；其次在數(shù)據(jù)量相同時(shí)，不同類型的作業(yè)完成時(shí)間差距很小，說(shuō)明資源的統(tǒng)一分配對(duì)不同類型的作業(yè)性能不會(huì)造成影響；最后通過(guò)比較在4種調(diào)度器調(diào)度下的作業(yè)不同執(zhí)行性能可以看出，使用MPCRS時(shí)的作業(yè)完成時(shí)間明顯短于使用其它3種調(diào)度器時(shí)的時(shí)間，但Job9使用MPCRS時(shí)完成時(shí)間高于使用EDF和Fair的時(shí)間，這是由于在選擇Job9最大輪數(shù)執(zhí)行方案時(shí)，在最大標(biāo)準(zhǔn)時(shí)間范圍內(nèi)，所選的任務(wù)輪數(shù)最多，這樣會(huì)使得作業(yè)的整體完成時(shí)間較輪數(shù)較少時(shí)有所延長(zhǎng)，而且TRN算法和MRNS算法在計(jì)算時(shí)具有一定的時(shí)間消耗，故在作業(yè)執(zhí)行過(guò)程中完成時(shí)間有一定延長(zhǎng)是不可避免的。這個(gè)完成時(shí)間的延長(zhǎng)范圍在可允許的范圍內(nèi)，是可以容忍的。

圖3 每個(gè)作業(yè)完成時(shí)間

3.3.2 收益最大化

根據(jù)上節(jié)作業(yè)執(zhí)行的高效性實(shí)驗(yàn)中可以得出每個(gè)作業(yè)的執(zhí)行性能，但本文設(shè)計(jì)MPCRS的最終目標(biāo)是使服務(wù)商獲取最大收益，故依據(jù)式(1)和式(3)，得到如圖4所示的使用不同調(diào)度器時(shí)的最大化收益。其中Ideal為總收益的理想值

圖4 服務(wù)商收益

(10)

從圖4中可以看出使用不同的調(diào)度器時(shí)，服務(wù)商可以獲得的最大收益差值較大。其中使用FIFO獲得的總收益與理想值Ideal差值最大，使用MPCRS可獲得的總收益與理想值Ideal差值最小。由于大部分作業(yè)的獎(jiǎng)勵(lì)值仍為0和有部分延遲作業(yè)的存在，故使用MPCRS時(shí)服務(wù)商可獲得的總收益值與理想值仍有一定差距。

3.3.3 平臺(tái)資源利用率的高效性

圖5為在各個(gè)統(tǒng)計(jì)階段時(shí)，使用4個(gè)調(diào)度器時(shí)的平臺(tái)資源利用率。從圖中可以看出，使用FIFO時(shí)的平臺(tái)資源利用率最低，這是由于當(dāng)一個(gè)作業(yè)執(zhí)行時(shí)，浪費(fèi)了其它空閑資源。使用EDF時(shí)同樣不能充分利用平臺(tái)資源，使得大量空閑資源浪費(fèi)。使用Fair調(diào)度器時(shí)的資源利用率較高，但仍然沒(méi)有使用MPCRS時(shí)的資源利用率高。MPCRS中的MRNS算法考慮了平臺(tái)資源利用率的影響，故在各個(gè)統(tǒng)計(jì)階段中大部分的資源利用率都在90%以上，但在第5階段和第8階段資源利用率較低，這是在統(tǒng)計(jì)階段時(shí)作業(yè)執(zhí)行情況的影響。

圖5 平臺(tái)資源利用率

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

結(jié)合服務(wù)商與用戶之間的利益關(guān)系，本文提出一種RP Model作為服務(wù)商收益最大化的評(píng)價(jià)標(biāo)準(zhǔn)，并以該評(píng)價(jià)標(biāo)準(zhǔn)為目標(biāo)提出了MPCRS，其中具體包括TRN算法和MRNS算法。TRN算法以RP Model中的收益值為標(biāo)準(zhǔn)，根據(jù)各個(gè)作業(yè)的Map和Reduce任務(wù)執(zhí)行時(shí)間，確定出作業(yè)在不同獎(jiǎng)懲階段的Map和Reduce的最大輪數(shù)組合以及最大標(biāo)準(zhǔn)時(shí)間；MRNS算法以TRN算法得出的結(jié)果為輸入，在滿足平臺(tái)資源利用率的前提下，選擇出具有局部最大收益的作業(yè)和該作業(yè)的任務(wù)最大輪數(shù)方案，從而制定出TS策略。實(shí)驗(yàn)結(jié)果表明，本文設(shè)計(jì)的作業(yè)調(diào)度器MPCRS所生成的TS策略能夠最大程度的縮短每個(gè)作業(yè)的完成時(shí)間，提高平臺(tái)資源利用率，并且在服務(wù)商獲得最大收益的同時(shí)，用戶能夠得到較為準(zhǔn)確的截止時(shí)間，真正意義上實(shí)現(xiàn)了服務(wù)商和用戶的利益共贏。