陳　新

(廣東省培英職業(yè)技術(shù)學(xué)校， 廣東 廣州 510630)

?

Hadoop平臺(tái)中作業(yè)調(diào)度算法分析與改進(jìn)研究

陳新

(廣東省培英職業(yè)技術(shù)學(xué)校， 廣東 廣州 510630)

針對(duì)傳統(tǒng)云計(jì)算作業(yè)調(diào)度中簡(jiǎn)單優(yōu)先級(jí)設(shè)置的不足，首先對(duì)作業(yè)調(diào)度進(jìn)行研究并提出了基于用戶服務(wù)等級(jí)協(xié)議(SLA)的作業(yè)分級(jí)機(jī)制。該設(shè)計(jì)基于QoS約束的多優(yōu)先級(jí)作業(yè)調(diào)度算法，在算法中利用云用戶作業(yè)中的偏好程度來(lái)設(shè)計(jì)優(yōu)先級(jí)值計(jì)算函數(shù)Priority，在作業(yè)調(diào)度時(shí)可以使較高等級(jí)的云用戶和具有較高優(yōu)先級(jí)的作業(yè)優(yōu)先得到任務(wù)的執(zhí)行，通過(guò)上述方式可以較好地保證云計(jì)算環(huán)境下的服務(wù)質(zhì)量。

云計(jì)算；作業(yè)分級(jí)機(jī)制；作業(yè)調(diào)度算法；SLA；QoS

引用格式：陳新. Hadoop平臺(tái)中作業(yè)調(diào)度算法分析與改進(jìn)研究[J].微型機(jī)與應(yīng)用，2016,35(11)：80-82，86.

0　引言

Hadoop是目前比較流行的云計(jì)算實(shí)現(xiàn)平臺(tái)，通過(guò)Hadoop可以快速搭建和部署云計(jì)算的環(huán)境。在Hadoop中有兩個(gè)重要的功能組件，分別是分布式文件系統(tǒng)和MapReduce計(jì)算組件。通過(guò)上述功能組件可以實(shí)現(xiàn)云計(jì)算的分布式計(jì)算和應(yīng)用的虛擬化[1]。開(kāi)源云計(jì)算平臺(tái)Hadoop中的分布式文件系統(tǒng)是谷歌公司實(shí)現(xiàn)云計(jì)算的文件系統(tǒng)開(kāi)源部分，而MapReduce是谷歌公司實(shí)現(xiàn)云計(jì)算中的并行計(jì)算和處理的實(shí)現(xiàn)部分[2]。

在云計(jì)算的環(huán)境下，目前的作業(yè)調(diào)度算法主要有三種，分別為先進(jìn)先出作業(yè)調(diào)度算法、公平調(diào)度算法和計(jì)算能力調(diào)度算法。無(wú)論是哪種調(diào)度算法，在Hadoop中都需要通過(guò)主控節(jié)點(diǎn)進(jìn)行分配和安排，通過(guò)作業(yè)調(diào)度器對(duì)云計(jì)算中的作業(yè)和任務(wù)進(jìn)行調(diào)度，根據(jù)用戶的設(shè)置偏好來(lái)實(shí)現(xiàn)對(duì)任務(wù)的分配和作業(yè)的調(diào)度[3-4]。從這個(gè)角度上看，作業(yè)的調(diào)度和安排直接關(guān)系到云計(jì)算平臺(tái)性能的好壞，直接影響到云計(jì)算平臺(tái)的效率，同時(shí)也會(huì)對(duì)用戶的服務(wù)質(zhì)量產(chǎn)生影響[5]。在云計(jì)算的環(huán)境下，需要對(duì)用戶提交的作業(yè)進(jìn)行分級(jí)處理，并對(duì)每一個(gè)作業(yè)進(jìn)行登記標(biāo)注，這樣就可以對(duì)提交的作業(yè)設(shè)置不同的優(yōu)先級(jí)別，在進(jìn)行調(diào)度時(shí)可以按照作業(yè)調(diào)度的優(yōu)先級(jí)別進(jìn)行處理，優(yōu)先安排服務(wù)質(zhì)量高的作業(yè)進(jìn)行資源的分配和處理，這樣可以有效地提高云用戶作業(yè)的服務(wù)質(zhì)量以及云用戶的滿意程度[6]。

1　云體系架構(gòu)

圖1　云計(jì)算作業(yè)調(diào)度的體系架構(gòu)

云計(jì)算的服務(wù)包括多種類(lèi)型，具體有私有云和公有云，對(duì)于不同的云計(jì)算環(huán)境其具體的劃分結(jié)構(gòu)如圖1所示[7]。在云計(jì)算的體系結(jié)構(gòu)中，對(duì)于私有云來(lái)說(shuō)，用戶可以很好地實(shí)現(xiàn)對(duì)數(shù)據(jù)的控制，保證云計(jì)算中的用戶數(shù)據(jù)的安全。并且在私有云的計(jì)算環(huán)境下，用戶不僅可以通過(guò)其調(diào)度得到內(nèi)部的計(jì)算資源，還可以通過(guò)云計(jì)算的作業(yè)調(diào)度獲取到公有云中的計(jì)算資源和服務(wù)，使得云計(jì)算的體系結(jié)構(gòu)具有高可用性、易擴(kuò)展的特點(diǎn)[8]。

2　算法設(shè)計(jì)

任務(wù)調(diào)度是集群系統(tǒng)的核心技術(shù)。本文中共劃分了五個(gè)主要的等級(jí)隊(duì)列，對(duì)作業(yè)進(jìn)行服務(wù)質(zhì)量(QoS)屬性偏好設(shè)置，就可以得到具有不同用戶屬性偏好的多優(yōu)先級(jí)的作業(yè)，然后通過(guò)作業(yè)調(diào)度器來(lái)完成對(duì)作業(yè)的調(diào)度和安排，滿足用戶作業(yè)調(diào)度服務(wù)的需求，為此，本文提出了多優(yōu)先級(jí)作業(yè)調(diào)度算法(QoS-Multi Priority Scheduler，QoS-MP Scheduler)。

2.1算法的設(shè)計(jì)思想

在QoS-MP Scheduler算法中，其設(shè)計(jì)的主要思路是，首先需要設(shè)計(jì)作業(yè)優(yōu)先級(jí)計(jì)算函數(shù) Priority，在這個(gè)函數(shù)中包括了基于 QoS 屬性約束的優(yōu)先條件，對(duì)每一個(gè)作業(yè)的優(yōu)先級(jí)的數(shù)值進(jìn)行計(jì)算。接著，在云計(jì)算主控節(jié)點(diǎn) JobTracker的作業(yè)調(diào)度器中對(duì)Priority建立隊(duì)列，然后，在進(jìn)行作業(yè)調(diào)度任務(wù)分配時(shí)，選取隊(duì)列中具有最高優(yōu)先級(jí)值的作業(yè)進(jìn)行分配，并將相關(guān)數(shù)據(jù)調(diào)入到云計(jì)算本地文件系統(tǒng)區(qū)去執(zhí)行，這樣就可以在最大程度上考慮用戶的服務(wù)質(zhì)量需求，有效地提高用戶作業(yè)的服務(wù)質(zhì)量，提升整個(gè)系統(tǒng)的質(zhì)量和服務(wù)滿意度。

2.2服務(wù)質(zhì)量設(shè)計(jì)

在云計(jì)算的環(huán)境下，云計(jì)算的服務(wù)質(zhì)量是全部服務(wù)性能和程度的總和。對(duì)云服務(wù)的能力進(jìn)行衡量和描述，具體如表1所示。

表1　云計(jì)算服務(wù)質(zhì)量 QoS 的屬性說(shuō)明表

2.3優(yōu)先級(jí)計(jì)算函數(shù)設(shè)計(jì)

圖2　作業(yè)中的兩個(gè)重要的QoS 屬性

云服務(wù)中的作業(yè)包括了兩個(gè)重要的屬性，即Time和Cost屬性，對(duì)于每一個(gè)作業(yè)，其Time和Cost的需求是不盡相同的，根據(jù)具體的實(shí)際情況才能確定。在云計(jì)算的環(huán)境下，其計(jì)算數(shù)值相差都較大，具有比較大的波動(dòng)性，但是這兩個(gè)屬性是衡量云計(jì)算服務(wù)質(zhì)量的最重要的屬性，如何對(duì)其進(jìn)行定義和配置關(guān)系到云服務(wù)質(zhì)量的好壞，需要在這兩個(gè)作業(yè)屬性之間找到平衡，來(lái)保證云服務(wù)的質(zhì)量。為此，本文提出了使用基于 QoS 約束的優(yōu)先級(jí)計(jì)算函數(shù) Priority來(lái)完成上述各個(gè)屬性的約束與控制，實(shí)現(xiàn)用戶作業(yè)服務(wù)質(zhì)量的滿足。Time和Cost屬性具體如圖2所示。

2.4算法的實(shí)現(xiàn)

通過(guò)對(duì)用戶作業(yè)的分級(jí)可以在開(kāi)源云計(jì)算框架中的主控節(jié)點(diǎn)JobTracker中得到5個(gè)具有不同級(jí)別的隊(duì)列，表示為VERY_HIGH、HIGH、NORMAL、LOW、VERY_LOW。上述作業(yè)隊(duì)列的優(yōu)先級(jí)別為從高到低。在節(jié)點(diǎn)中對(duì)作業(yè)客戶端所提交的作業(yè)信息進(jìn)行提取，可以得到作業(yè)等級(jí)的數(shù)據(jù)信息，將其提交到主控節(jié)點(diǎn)中進(jìn)行作業(yè)隊(duì)列的安排，通過(guò)映射就可以使得每一個(gè)作業(yè)隊(duì)列都具有優(yōu)先級(jí)別。同樣地，在主控節(jié)點(diǎn)中，對(duì)于作業(yè)隊(duì)列通過(guò)計(jì)算其優(yōu)先權(quán)值的數(shù)據(jù)，并對(duì)每一個(gè)優(yōu)先級(jí)別VERY_HIGH、HIGH、NORMAL、LOW、VERY_LOW分別設(shè)置ω1、ω2、ω3、ω4、ω5的權(quán)重?cái)?shù)值，云用戶就可以對(duì)上述的權(quán)值進(jìn)行配置，實(shí)現(xiàn)對(duì)云計(jì)算中的作業(yè)優(yōu)先級(jí)別的計(jì)算。對(duì)于其權(quán)重的計(jì)算，如圖3所示。

圖3　JobTracker 中作業(yè)隊(duì)列的優(yōu)先級(jí)權(quán)值系數(shù)的設(shè)計(jì)

在云計(jì)算環(huán)境下，對(duì)每一個(gè)作業(yè)，其用戶都有其QoS屬性的偏好，對(duì)于不同的偏好可以通過(guò)基于 QoS 約束的優(yōu)先級(jí)計(jì)算函數(shù) Priority來(lái)描述和實(shí)現(xiàn)，這樣就可以使得在云用戶進(jìn)行作業(yè)提交時(shí)實(shí)現(xiàn)偏好程度的選擇，在云計(jì)算的作業(yè)提交之后通過(guò)參數(shù)的方式將其數(shù)據(jù)信息傳遞到云計(jì)算中的主控節(jié)點(diǎn)進(jìn)行處理。本文對(duì)于優(yōu)先級(jí)別函數(shù)的計(jì)算中，主要是對(duì)服務(wù)質(zhì)量屬性中的Time 和 Cost進(jìn)行設(shè)計(jì)和計(jì)算。下面介紹Time 和 Cost 的偏好程度級(jí)別的設(shè)計(jì)，其級(jí)別的設(shè)置如表2所示。

表2　Time和Cost的偏好程度級(jí)別表

對(duì)于偏好程度共設(shè)置了1～10之間的多個(gè)級(jí)別，其中1的級(jí)別最低，10的級(jí)別最高。不同屬性按照用戶需求選擇，如果對(duì)實(shí)時(shí)性要求較高，則在偏好程度數(shù)值的選擇上選擇較大的Time 屬性值，在云計(jì)算進(jìn)行作業(yè)調(diào)度時(shí)，則是選擇優(yōu)先級(jí)別較高的作業(yè)進(jìn)行調(diào)度實(shí)現(xiàn)；此外，對(duì)于用戶對(duì)云計(jì)算中的花費(fèi)較低的需求，則在作業(yè)中屬性選擇時(shí)選擇較低的 Cost 屬性值。通過(guò)上述設(shè)置完成選擇，將作業(yè)Time 和 Cost 信息傳遞到主控節(jié)點(diǎn)。對(duì)于上述過(guò)程，具體如圖4所示。

圖4用戶對(duì)作業(yè) QoS 屬性偏好值的傳遞過(guò)程

圖6　改進(jìn)后的云計(jì)算系統(tǒng)的作業(yè)處理流程

通過(guò)上述過(guò)程，作業(yè)自身的Time 和 Cost屬性消息傳遞到云計(jì)算中的主控節(jié)點(diǎn)，并在主控節(jié)點(diǎn)對(duì)此消息進(jìn)行計(jì)算和分析，對(duì)所提交的作業(yè)進(jìn)行分級(jí)，根據(jù)用戶所提交的作業(yè)等級(jí)進(jìn)行調(diào)度，將處于優(yōu)先級(jí)別較高的作業(yè)優(yōu)先安排到作業(yè)隊(duì)列中進(jìn)行處理。因此，在云計(jì)算的作業(yè)調(diào)度中，對(duì)于作業(yè)的處理是通過(guò)對(duì)作業(yè)隊(duì)列的優(yōu)先級(jí)系數(shù)值和用戶對(duì) QoS 屬性的偏好程度進(jìn)行計(jì)算，從而得到優(yōu)先級(jí)計(jì)算函數(shù) Priority，最終通過(guò)云計(jì)算中的主控節(jié)點(diǎn)進(jìn)行作業(yè)的調(diào)度，完成作業(yè)的執(zhí)行。

對(duì)于任務(wù)的分配其具體實(shí)施策略如圖5所示。分配步驟如下：

圖5　JobTracker分配任務(wù)給 TaskTracker 的分配策略圖

(1)任務(wù)跟蹤節(jié)點(diǎn)通過(guò)心跳協(xié)議的內(nèi)容，一旦出現(xiàn)處于空閑的map 任務(wù)槽和空閑的 reduce 任務(wù)槽，就進(jìn)行統(tǒng)計(jì)和分析，并將其統(tǒng)計(jì)到主控節(jié)點(diǎn)JobTracker進(jìn)行安排。

(2)主控節(jié)點(diǎn)對(duì)目前調(diào)度的map 任務(wù)數(shù)與處于空閑的map 任務(wù)數(shù)進(jìn)行比較；判斷是否mapslots> req_mapno，如果是，則將作業(yè)的map任務(wù)全分配給主控節(jié)點(diǎn)，執(zhí)行步驟(3)；否則，mapslots 個(gè) map 任務(wù)進(jìn)行調(diào)度，并將其分配到主控節(jié)點(diǎn)中，直到空閑的任務(wù)數(shù)分配完畢。

(3)如果mapslots = req_mapno，則跳轉(zhuǎn)到(4)；否則，結(jié)束分配過(guò)程。

(4)比較目前調(diào)度作業(yè)的reduce 任務(wù)數(shù)與空閑的 reduce 任務(wù)槽數(shù)，如果reduceslots>= req_reduceno，則進(jìn)行任務(wù)的分配，并將其分配到任務(wù)跟蹤節(jié)點(diǎn)中進(jìn)行調(diào)度；否則結(jié)束分配。對(duì)作業(yè)分級(jí)機(jī)制和調(diào)度算法改進(jìn)后的云計(jì)算系統(tǒng)的作業(yè)處理流程具體如圖6所示。

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

3.1實(shí)驗(yàn)環(huán)境搭建

硬件環(huán)境：Inter Pentium Dual E2200@2.20 GHz，1 GB內(nèi)存，160 GB硬盤(pán)； 軟件環(huán)境 ：操作系統(tǒng)為L(zhǎng)inux Ubuntu 8.04，編程環(huán)境為Hadoop 0.20.2、jdk-6u24-linux-i586。

3.2實(shí)驗(yàn)設(shè)計(jì)

仿真實(shí)驗(yàn)中對(duì)作業(yè)的完成時(shí)間進(jìn)行比較。在Hadoop集群環(huán)境下，仿真20個(gè)不同用戶的工作和業(yè)務(wù)流，并且對(duì)每一組的工作流都執(zhí)行20次，對(duì)這些重復(fù)執(zhí)行的工作任務(wù)進(jìn)行計(jì)算取其平均值，計(jì)算作業(yè)的完成時(shí)間，按照上述方式，對(duì)不同級(jí)別的文件進(jìn)行作業(yè)調(diào)度，計(jì)算不同作業(yè)調(diào)度算法和策略下其總的作業(yè)運(yùn)行時(shí)間和平均作業(yè)運(yùn)行時(shí)間。

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

在本次實(shí)驗(yàn)中，將作業(yè)的隊(duì)列等級(jí)權(quán)重設(shè)置為不同的級(jí)別，權(quán)重分別為VERY_HIGH=4、HIGH=2、NORMAL=1、LOW=0.5、VERY_LOW=0.25,對(duì)于優(yōu)

先級(jí)別中的屬性參數(shù)Time和Cost均設(shè)置為 0.5。

在本次實(shí)驗(yàn)中，對(duì)于不同算法(靜態(tài)調(diào)度算法表示為Static，遺傳算法表示為GA，本文算法表示為QOS)下的作業(yè)完成時(shí)間，其結(jié)果如圖7所示。

圖7　云作業(yè)的平均完成時(shí)間對(duì)比

從上述的作業(yè)完成時(shí)間比較示意圖可以看到，本文算法的作業(yè)完成時(shí)間最小。

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

針對(duì)傳統(tǒng)作業(yè)調(diào)度算法中的不足，通過(guò)對(duì)作業(yè)進(jìn)行QoS 屬性的偏好標(biāo)記，調(diào)度中進(jìn)行優(yōu)先級(jí)函數(shù)計(jì)算保證用戶的服務(wù)質(zhì)量。通過(guò)仿真實(shí)驗(yàn)，驗(yàn)證了算法的平均完成時(shí)間相對(duì)較少，有效地提高了作業(yè)調(diào)度成功率，表明算法具有較好性能。

[1] 柳少鋒，董劍.一種基于優(yōu)先級(jí)隊(duì)列的集群動(dòng)態(tài)反饋調(diào)度算法[J].智能計(jì)算機(jī)與應(yīng)用，2014，12(4)：45-49.

[2] 廖大強(qiáng).面向多目標(biāo)的云計(jì)算資源調(diào)度算法[J]. 計(jì)算機(jī)系統(tǒng)應(yīng)用，2016,25(2):180-189.

[3] 鐘浩濤.基于遺傳算法的動(dòng)態(tài)調(diào)度分組算法[J].計(jì)算機(jī)學(xué)報(bào)，2013，45(8)：11-12.

[4] 涂剛陽(yáng)，富民.基于動(dòng)態(tài)優(yōu)先級(jí)策略的最優(yōu)軟非周期任務(wù)調(diào)度算法[J].計(jì)算機(jī)研究與發(fā)展，2014，42(11)：23-24.

[5] 廖大強(qiáng),鄒杜,印鑒. 一種基于優(yōu)先級(jí)的網(wǎng)格調(diào)度算法[J]. 計(jì)算機(jī)工程, 2014, 40(10): 11-16.

[6] AGUILERA M K， CHEN W，TOUEG S. On quiescent reliable communication[J]. Computing，2014,39(6):2040-2073.

[7] VAQUERO L，RODERO-MERINO L，CACERES J，et al.A break in the clouds：towards a cloud definition[J].ACM SIGCOMM Computer Communication Review，2014，39(1)：50-55.

[8] 廖大強(qiáng),印鑒,鄔依林,等.基于興趣傳播的用戶相似性計(jì)算方法研究[J]．計(jì)算機(jī)應(yīng)用與軟件，2015，32(10)：95-100,104.

Analysis and improvement of job scheduling algorithm in Hadoop platform

Chen Xin

(Guangdong Province Pei Ying Occupation Technical School， Guangzhou 510630, China)

In view of the shortcoming of simple priority setting in the traditional cloud computing job scheduling, this paper studies the job grading mechanism firstly and puts forward the job grading mechanism based on user’s service level agreement (SLA). The priority job scheduling algorithm is designed based on QoS constraints. In the algorithm the cloud users’ preference can be used to design the priority value to calculate function priority. When scheduling jobs, tasks from higher lever of could users and higher priority jobs can be performed finstly. This mentioned methods can better guarantee the quality of service in cloud computing environment.

cloud computing； job grading mechanism； job scheduling algorithm； SLA； QoS

TP393

A

10.19358/j.issn.1674- 7720.2016.11.024

2016-02-02)

陳新(1974-),男,碩士,講師，主要研究方向：計(jì)算機(jī)系統(tǒng)架構(gòu)、軟件工程。