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

陳　新

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

?

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

陳新

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

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

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

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

0　引言

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

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

1　云體系架構(gòu)

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

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

2　算法設(shè)計

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

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

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

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

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

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

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

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

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

2.4算法的實現(xiàn)

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

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

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

表2　Time和Cost的偏好程度級別表

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

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

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

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

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

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

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

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

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

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

3　實驗與分析

3.1實驗環(huán)境搭建

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

3.2實驗設(shè)計

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

3.3實驗結(jié)果分析

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

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

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

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

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

4　結(jié)束語

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

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

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

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

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

[5] 廖大強,鄒杜,印鑒. 一種基于優(yōu)先級的網(wǎng)格調(diào)度算法[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] 廖大強,印鑒,鄔依林,等.基于興趣傳播的用戶相似性計算方法研究[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-),男,碩士,講師，主要研究方向：計算機系統(tǒng)架構(gòu)、軟件工程。