Hadoop負(fù)載樹(shù)任務(wù)調(diào)度算法

朱潔 顧燁君 柳飛 李思成 劉瑞

摘要：針對(duì)現(xiàn)有異構(gòu)任務(wù)調(diào)度算法存在負(fù)載不均衡、數(shù)據(jù)本地性問(wèn)題，提出基于樹(shù)結(jié)構(gòu)的負(fù)載樹(shù)任務(wù)調(diào)度算法。該算法通過(guò)量化節(jié)點(diǎn)計(jì)算能力構(gòu)造節(jié)點(diǎn)集最小堆，利用堆排序生成計(jì)算能力逆序樹(shù)，并依據(jù)節(jié)點(diǎn)負(fù)載率將逆序樹(shù)調(diào)整為左節(jié)點(diǎn)優(yōu)先的負(fù)載樹(shù)，為任務(wù)計(jì)算包含完成時(shí)間、負(fù)載率、延遲因子的決策值，最終完成任務(wù)與樹(shù)節(jié)點(diǎn)的匹配。實(shí)驗(yàn)結(jié)果表明，取不同負(fù)載率與延遲權(quán)值比時(shí)，該算法的任務(wù)執(zhí)行效率均能獲得一定程度提高。該算法可利用樹(shù)結(jié)構(gòu)的調(diào)度優(yōu)勢(shì)，在獲得更高集群負(fù)載均衡度時(shí)，有效縮短作業(yè)集執(zhí)行時(shí)間。

關(guān)鍵詞：Hadoop;負(fù)載樹(shù);任務(wù)調(diào)度;負(fù)載均衡;數(shù)據(jù)本地性

Hadoop Load Tree Task Scheduling Algorithm

ZHU Jie1，2， GU Ye?jun?LIU Fei?LI Si?cheng?LIU Rui?1

（1.School of Information Engineering， Nanjing Xiaozhuang University;

2.Key Laboratory of Trusted Cloud Computing and Big Data Analysis， Nanjing 211171， China）

Abstract：Aiming at the problems of the load imbalance and data locality of existing heterogeneous tasks scheduling algorithm， an load tree task scheduling algorithm was proposed. Firstly， the computation capacities of nodes were calculated to build the minimum heap of the node set. The reverse tree was constructed after heap sort. Secondly， the reverse tree was adjusted to the left?node preferential load tree through the load rate of nodes. Finally， the decision values of nodes consist of complete time factor， load rate factor and delay factor were calculated to match tasks and nodes. The experimental results showed that the tasks execution efficiency of the proposed algorithm was improved when different factor proportions of load rate and delay were defined. The proposed algorithm can utilize the scheduling advantage of the tree structure and reduce the job set execution time effectively while achieving the higher cluster load balance degree.

Key Words：Hadoop; load tree; task scheduling; load balance; data locality

0?引言

Hadoop分布式計(jì)算平臺(tái)因其可靠、高效而廣泛應(yīng)用于大數(shù)據(jù)處理。MapReduce是其實(shí)現(xiàn)分布式處理的計(jì)算模型，其中任務(wù)調(diào)度算法為作業(yè)任務(wù)匹配計(jì)算資源，通過(guò)獲得更短作業(yè)集執(zhí)行時(shí)間提升平臺(tái)計(jì)算性能。傳統(tǒng)的先來(lái)先服務(wù)調(diào)度算法[1?2]、容量調(diào)度算法[3]與公平調(diào)度算法[4?5]及其改進(jìn)主要應(yīng)用于同構(gòu)集群環(huán)境[6?7]。隨著集群應(yīng)用發(fā)展，節(jié)點(diǎn)間配置差異使同構(gòu)前提不再成立，設(shè)計(jì)適應(yīng)異構(gòu)環(huán)境的調(diào)度算法成為必要。針對(duì)異構(gòu)環(huán)境的推測(cè)式執(zhí)行機(jī)制通過(guò)為進(jìn)度落后任務(wù)啟用備份任務(wù)以縮短任務(wù)執(zhí)行時(shí)間，但其節(jié)點(diǎn)速度、任務(wù)進(jìn)度恒定假設(shè)并不符合實(shí)際異構(gòu)環(huán)境[8?9]。在此基礎(chǔ)上，改進(jìn)最長(zhǎng)近似結(jié)束時(shí)間（Longest Approximate Time to End，LATE）算法[10]，定義備份任務(wù)數(shù)、慢節(jié)點(diǎn)與慢任務(wù)閾值，通過(guò)在出現(xiàn)資源空閑的快節(jié)點(diǎn)上啟用備份任務(wù)，有效縮短了落后任務(wù)的執(zhí)行時(shí)間。但仍存在問(wèn)題：①Hadoop分布式文件系統(tǒng)使用冗余存儲(chǔ)，任務(wù)數(shù)據(jù)不在本地時(shí)，移動(dòng)數(shù)據(jù)的代價(jià)遠(yuǎn)高于移動(dòng)計(jì)算;②應(yīng)用領(lǐng)域擴(kuò)展、用戶需求多樣、計(jì)算節(jié)點(diǎn)資源異構(gòu)與鏈路帶寬差異將導(dǎo)致集群負(fù)載不均衡，算法中并未涉及。

現(xiàn)有研究集中于對(duì)問(wèn)題①的改進(jìn)：文獻(xiàn)[11]提出允許任務(wù)放棄調(diào)度機(jī)會(huì)，等待調(diào)度到距離數(shù)據(jù)最近節(jié)點(diǎn)的延遲調(diào)度算法;文獻(xiàn)[12]使用任務(wù)進(jìn)度探測(cè)方式區(qū)分快慢節(jié)點(diǎn)以提高推測(cè)執(zhí)行效率;文獻(xiàn)[13]從總體性能考慮，通過(guò)網(wǎng)絡(luò)與負(fù)載狀況動(dòng)態(tài)調(diào)整數(shù)據(jù)本地性;文獻(xiàn)[14]引入排隊(duì)論模型，利用單隊(duì)列多資源池服務(wù)窗口設(shè)計(jì)提高調(diào)度效率;文獻(xiàn)[15]采用預(yù)取任務(wù)輸入數(shù)據(jù)的方式減少作業(yè)響應(yīng)時(shí)間。不少改進(jìn)采用了智能調(diào)度算法，尋求多樣性搜索與集中性搜索平衡，雖然有效減少了任務(wù)執(zhí)行時(shí)間，但容易陷入局部最優(yōu)解，使任務(wù)聚集在最快的幾個(gè)節(jié)點(diǎn)上，延長(zhǎng)了快節(jié)點(diǎn)上任務(wù)的排隊(duì)時(shí)間，使慢節(jié)點(diǎn)的資源得不到充分利用，降低了任務(wù)并行率，導(dǎo)致負(fù)載不均衡，影響了作業(yè)集執(zhí)行時(shí)間。

針對(duì)問(wèn)題②，需要在任務(wù)調(diào)度算法中充分考慮可能引起負(fù)載不均衡的因素，進(jìn)而進(jìn)行預(yù)處理與實(shí)時(shí)控制。已有云計(jì)算環(huán)境下動(dòng)態(tài)負(fù)載均衡算法研究主要涉及任務(wù)完成時(shí)間、資源利用率、能源消耗、云系統(tǒng)性能等方面的改進(jìn)。文獻(xiàn)[16]通過(guò)計(jì)算觸發(fā)條件中集群負(fù)載實(shí)現(xiàn)資源的彈性調(diào)度。文獻(xiàn)[17]建立成本函數(shù)模型，引入動(dòng)態(tài)調(diào)節(jié)因子，改進(jìn)蟻群算法用于降低任務(wù)成本，實(shí)現(xiàn)資源負(fù)載均衡。文獻(xiàn)[18]定義了任務(wù)完成時(shí)間成本的約束函數(shù)和負(fù)載均衡度函數(shù)，通過(guò)改進(jìn)蟻群算法獲得全局最優(yōu)解。文獻(xiàn)[19]采用禁忌搜索和貪心原則選擇任務(wù)交換，從而在優(yōu)化任務(wù)調(diào)度初始解執(zhí)行時(shí)間的同時(shí)改善負(fù)載均衡性能。文獻(xiàn)[20]通過(guò)虛擬機(jī)分組和任務(wù)選擇算法減少任務(wù)的遷移次數(shù)，提高負(fù)載均衡指標(biāo)。

本文針對(duì)以上問(wèn)題，借鑒樹(shù)結(jié)構(gòu)調(diào)度優(yōu)勢(shì)，提出負(fù)載樹(shù)算法（Load Tree Algorithm，LTA）。該算法通過(guò)基于計(jì)算能力的最小堆排序構(gòu)建自平衡逆序樹(shù)，利用完成時(shí)間、負(fù)載率、時(shí)延因子將逆序樹(shù)調(diào)整為左節(jié)點(diǎn)優(yōu)先的負(fù)載樹(shù)，實(shí)現(xiàn)任務(wù)與節(jié)點(diǎn)匹配。算法優(yōu)先考慮數(shù)據(jù)本地性，充分利用樹(shù)索引優(yōu)勢(shì)實(shí)現(xiàn)任務(wù)并行度與資源利用率之間的平衡，使異構(gòu)環(huán)境任務(wù)調(diào)度趨于合理。

1?負(fù)載樹(shù)構(gòu)造

異構(gòu)集群中，不同計(jì)算能力會(huì)使同一任務(wù)在不同節(jié)點(diǎn)上的執(zhí)行時(shí)間各有差異。首先，量化節(jié)點(diǎn)計(jì)算能力。設(shè)?n∈N為樹(shù)節(jié)點(diǎn)數(shù)，定義節(jié)點(diǎn)集P={P?i|i∈[0，n-1]}，節(jié)點(diǎn)計(jì)算能力集P?cap={P?cap（i）|i∈[0，n-1]}，節(jié)點(diǎn)資源集PR={（PRc?i， PRm?i）|i∈[0，n-1]}，節(jié)點(diǎn)速率集PS={PS?i（j）|i∈[0，n-1]， j∈[1，n?t]}，n?t為節(jié)點(diǎn)P?i上已完成的任務(wù)數(shù)。為支持多資源類(lèi)型，資源集值定義了處理器資源值PRc?i與內(nèi)存資源值PRm?i，根據(jù)式（1）計(jì)算節(jié)點(diǎn)速率初始值PS?i（0），ω?r為資源權(quán)值。

集群運(yùn)行后，通過(guò)任務(wù)歷史數(shù)據(jù)反饋更新節(jié)點(diǎn)速率，動(dòng)態(tài)調(diào)整節(jié)點(diǎn)狀態(tài)。定義節(jié)點(diǎn)任務(wù)執(zhí)行時(shí)間集TT={TT?i，j|i∈[0，n-1]， j∈[1，n?t]}，節(jié)點(diǎn)P?i當(dāng)前速率PS?i（n?t）為已完成任務(wù)在單位時(shí)間內(nèi)處理的任務(wù)數(shù)與資源量，通過(guò)式（2）計(jì)算。

每有任務(wù)完成，更新節(jié)點(diǎn)速率。節(jié)點(diǎn)計(jì)算能力通過(guò)式（3）計(jì)算，其中ω?c為計(jì)算能力因子權(quán)值。

利用堆結(jié)構(gòu)在構(gòu)造優(yōu)先級(jí)隊(duì)列時(shí)的高效性，通過(guò)最小堆構(gòu)造逆序樹(shù)。首先，按序構(gòu)造完全二叉樹(shù)，并自底向頂逐步調(diào)整為符合定義1的最小堆。

定義1?P?cap（i）≤P?cap（2i+1）∧P?cap（i）≤P?cap（2i+2）?（i∈[0，|（n-2）/2|]）

完全二叉樹(shù)從最后一個(gè)非葉子節(jié)點(diǎn)?P?|n/2|到根節(jié)點(diǎn)P?0，依次調(diào)用下滑調(diào)整算法比較本輪父節(jié)點(diǎn)與左右孩子節(jié)點(diǎn)的P?cap值。逐步將P?cap值最小的節(jié)點(diǎn)上浮為堆頂節(jié)點(diǎn)，得到初始最小堆。調(diào)用堆排序算法將初始最小堆調(diào)整為逆序樹(shù)，其特征為：①下標(biāo)i為奇數(shù)時(shí)，節(jié)點(diǎn)為左孩子，i為偶數(shù)時(shí)，節(jié)點(diǎn)為右孩子;②采用層次遍歷，得到節(jié)點(diǎn)計(jì)算能力逆序值集;③具有n個(gè)節(jié)點(diǎn)的逆序樹(shù)深度k=|?log?2n|+1。堆排序過(guò)程在最壞情況下時(shí)間復(fù)雜度為O（n?log?2n）?。

基于節(jié)點(diǎn)負(fù)載率動(dòng)態(tài)調(diào)整逆序樹(shù)，利用節(jié)點(diǎn)計(jì)算能力，實(shí)現(xiàn)資源調(diào)度平衡。定義節(jié)點(diǎn)負(fù)載率集為?L={L?i|i∈[0，n-1]}。負(fù)載率計(jì)算涉及節(jié)點(diǎn)性能狀態(tài)，進(jìn)而影響任務(wù)分配，利用處理器與內(nèi)存資源值完成計(jì)算。定義節(jié)點(diǎn)已用資源量集為PRa={（PRac?i， PRam?i）|i∈[0，n-1]}，負(fù)載率計(jì)算如式（4）所示。

負(fù)載率升高可能導(dǎo)致節(jié)點(diǎn)性能下降，還需進(jìn)一步判別節(jié)點(diǎn)速率。若節(jié)點(diǎn)速率同時(shí)出現(xiàn)下降，則可判別節(jié)點(diǎn)性能下降。節(jié)點(diǎn)速率下降條件式為?PS?i（n?t）>PS?i（n?t+1）?，將式（2）代入其中，推導(dǎo)可得條件式（5）。

逆序樹(shù)調(diào)整為負(fù)載樹(shù)后，需要對(duì)樹(shù)節(jié)點(diǎn)的負(fù)載均衡度進(jìn)行判定。判定時(shí)，若將負(fù)載率相近但計(jì)算能力不同的節(jié)點(diǎn)視為同等均衡度，將會(huì)降低強(qiáng)節(jié)點(diǎn)的資源利用率。因此，判定還需考慮節(jié)點(diǎn)計(jì)算能力的影響。設(shè)節(jié)點(diǎn)均衡度集?DB={DB?i|i∈[0，n-1]}，計(jì)算如式（6）所示。

節(jié)點(diǎn)均衡度集的標(biāo)準(zhǔn)差用于描述集群均衡度，計(jì)算如式（7）所示。

σ值正常范圍在[0，1]內(nèi)，值越小，集群均衡度越高。負(fù)載樹(shù)算法側(cè)重于比較均衡效果，通過(guò)條件式DB?i>DB判別節(jié)點(diǎn)過(guò)載。

改善逆序樹(shù)負(fù)載不均衡與弱節(jié)點(diǎn)資源利用率低的問(wèn)題，可以通過(guò)在復(fù)制的逆序樹(shù)中引入負(fù)載率因子構(gòu)造動(dòng)態(tài)負(fù)載樹(shù)實(shí)現(xiàn)。負(fù)載樹(shù)須符合定義2，同層節(jié)點(diǎn)中負(fù)載更輕的節(jié)點(diǎn)將成為左孩子。

定義2?L?2i+1≤L?2i+2?（i=0，1，…，|（n-2）/2|）

節(jié)點(diǎn)上每有任務(wù)分配或完成，若其父節(jié)點(diǎn)不符合定義2，則交換同層節(jié)點(diǎn)。定義節(jié)點(diǎn)P?i上任務(wù)預(yù)計(jì)完成時(shí)間集為T(mén)F={TF?i，j|i∈[0，n-1]， j∈[1，n?p]}，n?p為節(jié)點(diǎn)并行任務(wù)數(shù)閾值。根據(jù)式（8）計(jì)算根節(jié)點(diǎn)與左孩子節(jié)點(diǎn)的決策值D?i，以優(yōu)先選擇計(jì)算能力更強(qiáng)、完成時(shí)間更短、負(fù)載更輕、延遲更短的節(jié)點(diǎn)。其中，w?d為決策值因子權(quán)值。TF?i，j的計(jì)算如式（9）所示。

其中，PP={PP?i，j|i∈[0，n-1]， j∈[1，n?p]}為任務(wù)已完成的進(jìn)度比例集;任務(wù)進(jìn)度比例采用傳統(tǒng)任務(wù)調(diào)度算法規(guī)定;TA={TA?i，j|i∈[0，n-1]， j∈[1，n?p]}為任務(wù)已運(yùn)行時(shí)間集;TP?i，j為任務(wù)優(yōu)先級(jí)，優(yōu)先級(jí)越高，決策值越小，越早獲得執(zhí)行。

2?基于負(fù)載樹(shù)的任務(wù)調(diào)度算法

負(fù)載樹(shù)算法構(gòu)造可動(dòng)態(tài)調(diào)整的集群節(jié)點(diǎn)負(fù)載樹(shù)，通過(guò)比較左節(jié)點(diǎn)決策值為任務(wù)選擇執(zhí)行節(jié)點(diǎn)，算法流程如圖1所示。

算法適應(yīng)負(fù)載率變化，支持拓?fù)涓淖?、?jié)點(diǎn)性能變化等情況。通過(guò)式（5）判別出有節(jié)點(diǎn)性能下降時(shí)，為保持逆序樹(shù)相對(duì)穩(wěn)定，將該節(jié)點(diǎn)標(biāo)記為不參與調(diào)度。若此節(jié)點(diǎn)為左節(jié)點(diǎn)，則判斷同層右節(jié)點(diǎn)是否過(guò)載，若過(guò)載，則僅標(biāo)記;若不過(guò)載，則交換兩節(jié)點(diǎn)。若此節(jié)點(diǎn)為右節(jié)點(diǎn)，則僅標(biāo)記。該節(jié)點(diǎn)上每有任務(wù)完成，即判別性能是否恢復(fù)，若恢復(fù)，則撤銷(xiāo)標(biāo)記，節(jié)點(diǎn)重新參與調(diào)度。當(dāng)拓?fù)渥兓蚬?jié)點(diǎn)計(jì)算能力變化時(shí)，須調(diào)整逆序樹(shù)，進(jìn)行負(fù)載樹(shù)再構(gòu)造。對(duì)于集群拓?fù)洚悩?gòu)與可擴(kuò)展支持，增強(qiáng)了負(fù)載樹(shù)算法的適應(yīng)性。

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

建立集群，測(cè)試負(fù)載樹(shù)算法效果。選取6臺(tái)計(jì)算機(jī)構(gòu)建異構(gòu)環(huán)境，其中3臺(tái)配置處理器四核3.0GHz、內(nèi)存8GB，3臺(tái)減配為處理器雙核2.4GHz、內(nèi)存2GB，在CentOS上部署Hadoop。4個(gè)節(jié)點(diǎn)連接同一交換機(jī)，通過(guò)路由器連接其余2個(gè)節(jié)點(diǎn)，并通過(guò)修改鏈路帶寬值模擬為遠(yuǎn)程節(jié)點(diǎn)。作業(yè)集由不同資源需求量、數(shù)據(jù)量的典型作業(yè)WordCount、TeraSort、Grep組合構(gòu)成。作業(yè)數(shù)100，3種作業(yè)各占約1/3，且每種作業(yè)數(shù)據(jù)量由少到多比例為3∶4∶3，作業(yè)以隨機(jī)順序提交。通過(guò)實(shí)驗(yàn)獲取負(fù)載樹(shù)算法在異構(gòu)集群中采用不同負(fù)載率與時(shí)延權(quán)值時(shí)的作業(yè)集執(zhí)行時(shí)間，并與LATE算法進(jìn)行對(duì)比。

算法固定完成時(shí)間因子權(quán)值，調(diào)整負(fù)載率與時(shí)延權(quán)值比例。實(shí)驗(yàn)1-3中負(fù)載率與延遲權(quán)值依次為（0.35，0.35）、（0.5，0.2）、（0.2，0.5）。實(shí)驗(yàn)4中負(fù)載率與延遲權(quán)值為（0.4，0.3）時(shí)，作業(yè)集執(zhí)行時(shí)間最短。作業(yè)集執(zhí)行時(shí)間對(duì)比如圖2所示。

實(shí)驗(yàn)結(jié)果中，當(dāng)負(fù)載與延遲權(quán)值相當(dāng)時(shí)，調(diào)度效果較好。其中，實(shí)驗(yàn)1、實(shí)驗(yàn)4中負(fù)載樹(shù)算法比LATE算法的作業(yè)集執(zhí)行時(shí)間分別縮短了30.53%、33.1%。在延遲權(quán)值較小的實(shí)驗(yàn)2中，負(fù)載樹(shù)算法比LATE算法的作業(yè)集執(zhí)行時(shí)間縮短了17.88%，調(diào)度效果一般。在延遲權(quán)值較大的實(shí)驗(yàn)3中，負(fù)載樹(shù)算法使作業(yè)集執(zhí)行時(shí)間縮短了23.59%。因此，負(fù)載率與延遲因子均需有所考慮，且比例應(yīng)相當(dāng)。圖3給出了實(shí)驗(yàn)1-4的均衡度標(biāo)準(zhǔn)差，其中實(shí)驗(yàn)2的負(fù)載均衡效果最為明顯。

實(shí)驗(yàn)分析：

（1）任務(wù)完成時(shí)間受節(jié)點(diǎn)性能參數(shù)影響，完成時(shí)間因子可使任務(wù)優(yōu)先選擇計(jì)算能力強(qiáng)的節(jié)點(diǎn)，縮短任務(wù)執(zhí)行時(shí)間。通過(guò)前期實(shí)驗(yàn)發(fā)現(xiàn)，該因子權(quán)值大時(shí)，任務(wù)將集中于高性能節(jié)點(diǎn)，加重了強(qiáng)節(jié)點(diǎn)負(fù)載，使弱節(jié)點(diǎn)空閑;反之，任務(wù)將被均勻分配，雖然優(yōu)先分配到負(fù)載輕、具有本地?cái)?shù)據(jù)的節(jié)點(diǎn)，但任務(wù)執(zhí)行時(shí)間仍相對(duì)較長(zhǎng)。傳統(tǒng)算法使任務(wù)趨向于在強(qiáng)節(jié)點(diǎn)執(zhí)行，而少考慮負(fù)載的影響。因此，實(shí)驗(yàn)設(shè)計(jì)固定完成時(shí)間因子權(quán)值，弱化節(jié)點(diǎn)性能對(duì)任務(wù)執(zhí)行效率的影響，主要分析負(fù)載均衡策略與數(shù)據(jù)本地性的調(diào)度效果。

（2）實(shí)驗(yàn)結(jié)果表明集群均衡度與負(fù)載率因子權(quán)值關(guān)系密切，均衡度標(biāo)準(zhǔn)差與負(fù)載率權(quán)值正相關(guān)，與算法設(shè)計(jì)相符。

（3）集群中不具有本地?cái)?shù)據(jù)的節(jié)點(diǎn)需要耗費(fèi)較多網(wǎng)絡(luò)延遲獲取數(shù)據(jù)備份。延遲因子的使用在于為任務(wù)找到更快獲得數(shù)據(jù)備份的節(jié)點(diǎn)。從實(shí)驗(yàn)結(jié)果看，延遲因子權(quán)值小時(shí)，任務(wù)被分配到遠(yuǎn)程節(jié)點(diǎn)的幾率增加，增加的延遲影響了任務(wù)執(zhí)行時(shí)間;延遲因子權(quán)值大時(shí)，任務(wù)很少被分配到遠(yuǎn)程節(jié)點(diǎn)，從而使任務(wù)集中于高帶寬鏈路節(jié)點(diǎn)，增加了該節(jié)點(diǎn)的負(fù)載，使遠(yuǎn)程節(jié)點(diǎn)利用率降低，影響并行度，使均衡度下降;在負(fù)載與延遲比例相當(dāng)時(shí)，作業(yè)集獲得了較好的執(zhí)行時(shí)間。

因此，在固定完成時(shí)間因子前提下，集群執(zhí)行效果的主導(dǎo)為負(fù)載率因子。延遲因子作為補(bǔ)充，在權(quán)值比例合適時(shí)，能較好地與負(fù)載率因子協(xié)同，獲得更好的調(diào)度效果。

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

本文分析了現(xiàn)有異構(gòu)任務(wù)調(diào)度算法存在負(fù)載不均衡、數(shù)據(jù)本地性問(wèn)題，研究已有動(dòng)態(tài)負(fù)載均衡算法性能改進(jìn)方法，對(duì)在任務(wù)調(diào)度中引入負(fù)載均衡策略進(jìn)行探討，提出了借助樹(shù)結(jié)構(gòu)提高任務(wù)調(diào)度效率的負(fù)載樹(shù)算法。首先量化節(jié)點(diǎn)計(jì)算能力，并據(jù)此構(gòu)造節(jié)點(diǎn)集最小堆，堆排序后形成計(jì)算能力逆序樹(shù)。通過(guò)節(jié)點(diǎn)資源使用情況計(jì)算負(fù)載率，將逆序樹(shù)調(diào)整為負(fù)載樹(shù)，并據(jù)此定義節(jié)點(diǎn)性能判別式與節(jié)點(diǎn)集均衡度標(biāo)準(zhǔn)差。通過(guò)任務(wù)完成時(shí)間、負(fù)載率、延遲因子計(jì)算決策值后，為任務(wù)確定執(zhí)行節(jié)點(diǎn)。算法中樹(shù)結(jié)構(gòu)具有自平衡能力，逆序樹(shù)可根據(jù)拓?fù)浼肮?jié)點(diǎn)計(jì)算能力變化動(dòng)態(tài)調(diào)整，負(fù)載樹(shù)也可根據(jù)節(jié)點(diǎn)負(fù)載率變化及時(shí)調(diào)整。通過(guò)實(shí)驗(yàn)選取不同負(fù)載率與延遲權(quán)值的作業(yè)集執(zhí)行時(shí)間進(jìn)行比較，并與LATE算法執(zhí)行結(jié)果對(duì)比。實(shí)驗(yàn)結(jié)果表明，負(fù)載樹(shù)算法能有效縮短作業(yè)集執(zhí)行時(shí)間，在取得適合的因子權(quán)值比時(shí)，可進(jìn)一步提升調(diào)度效率并使集群擁有較好的負(fù)載均衡度。

負(fù)載樹(shù)算法在并行效率與負(fù)載均衡間提供了協(xié)同調(diào)度途徑，但算法主要側(cè)重在節(jié)點(diǎn)選擇上，進(jìn)一步研究工作是融入任務(wù)端優(yōu)化策略，使節(jié)點(diǎn)與任務(wù)選擇共同作用于調(diào)度算法，并研究權(quán)值比例的自動(dòng)取值實(shí)現(xiàn)。

參考文獻(xiàn)：

[1]?WIKIPEDIA. Apache hadoop [EB/OL]. http：//en.wikipedia.org/wiki/Apache_Hadoop.

[2]?ZAHARIA M. Job scheduling with the fair and capacity schedulers [EB/OL]. http：//www.cs.berkeley.edu/～matei/talks/2009/hadoop_summit_fair_scheduler.pdf.

[3]?THE APACHE SOFTWARE FOUNDATION. Capacity scheduler guide [EB/OL]. http：//hadoop.apache.org/docs/r1.2.1/capacity_scheduler.html.

[4]?ZAHARIA M， BORTHAKUR D， SARMA J S， et al. Job scheduling for multi-user MapReduce clusters[R]. Berkeley： EECS Department， University of California，?2009：1?16.

[5]?THE APACHE SOFTWARE FOUNDATION. Fair scheduler guide [EB/OL]. http：//hadoop.apache.org/docs/r1.2.1/fair_scheduler.html.

[6]?范杰，彭艦，黎紅友.基于蟻群算法的云計(jì)算需求彈性算法[J].計(jì)算機(jī)應(yīng)用，2011，31（1）：1?7.

[7]?楊鏡，吳磊，武德安，等.云平臺(tái)下動(dòng)態(tài)任務(wù)調(diào)度人工免疫算法[J].計(jì)算機(jī)應(yīng)用，2014，34（2）：351?356.

[8]?FISCHER M， SU X， YIN Y. Assigning tasks for efficiency in Hadoop： extended abstract[C]. Proceedings of the 22nd ACM Symposium on Parallelism in Algorithms and Architectures， 2010：30?39.

[9]?GE Y， WEI G. GA?based task scheduler for the cloud computing systems[C]. Proceedings of 2010 International Conference on Web Information Systems and Mining， 2010：181?186.

[10]?ZAHARIA M， KONWINSKI A， JOSEPH A D， et al. Improving MapReduce performance in heterogeneous environments[C].Proceedings of the 8th USENIX Symposium on Operating Systems Design Implementation，2008：29?42.

[11]?ZAHARIA M， BORTHAKUR D， SARMA J S， et al. Delay scheduling： a simple technique for achieving locality and fairness in cluster scheduling[C]. Proceedings of the 5th European Conference on Computer Systems，2010：265?278.

[12]?劉奎，劉向東，馬寶來(lái)，等.基于數(shù)據(jù)局部性的推測(cè)式Hadoop任務(wù)調(diào)度算法研究[J].計(jì)算機(jī)應(yīng)用研究，2014，31（1）：182?187.

[13]?THAWARI V W， BABAR S D， DHAWAS N A， et al. An efficient data locality driven task scheduling algorithm for cloud computing[J]. International Journal In Multidisciplinary and Academic Research， 2012，1（3）：151?158.

[14]?馬莉，唐善成，王靜，等.云計(jì)算環(huán)境下的動(dòng)態(tài)反饋?zhàn)鳂I(yè)調(diào)度算法[J].西安交通大學(xué)學(xué)報(bào)，2014，48（7）：77?82.

[15]?XIE J， MENG F， WANG H， et al. Research on scheduling scheme for Hadoop clusters[C]. Proceedings of the Procedia Computer Science， 2013：49?52.

[16]?戴炳榮，李超，曠志光，等.基于多策略的私有云資源彈性調(diào)度方法[J].計(jì)算機(jī)應(yīng)用，2017，37（S1）：34?38.

[17]?張繼榮，陳琛.基于負(fù)載均衡的云計(jì)算資源分配算法[J].微電子學(xué)與計(jì)算機(jī)，2017，34（9）：43?47.

[18]?葛君偉，郭強(qiáng)，方義秋.一種基于改進(jìn)蟻群算法的多目標(biāo)優(yōu)化云計(jì)算任務(wù)調(diào)度策略[J].微電子學(xué)與計(jì)算機(jī)，2017，34（11）：63?67.

[19]?孫凌宇，冷明，朱平，等.云計(jì)算環(huán)境下基于禁忌搜索的負(fù)載均衡任務(wù)調(diào)度優(yōu)化算法[J].小型微型計(jì)算機(jī)系統(tǒng)，2015，36（9）：1948?1952.

[20]?劉亞秋，孫新越，景維鵬.一種異構(gòu)云環(huán)境下的負(fù)載均衡算法[J].計(jì)算機(jī)應(yīng)用研究，2018（12）：1?2.