王溪波 王珊珊 王越峰

（沈陽(yáng)工業(yè)大學(xué) 遼寧省沈陽(yáng)市 110000）

1 引言

云計(jì)算是用戶通過(guò)遠(yuǎn)程連接來(lái)獲取計(jì)算資源的一種計(jì)算方式，許多IT公司都推出相應(yīng)的云計(jì)算平臺(tái)，將云計(jì)算技術(shù)看成是一項(xiàng)重要的且有利于公司發(fā)展的技術(shù)，由此看出對(duì)云計(jì)算的研究是緊追IT技術(shù)的發(fā)展路線，有較高的應(yīng)用價(jià)值。但伴隨云計(jì)算技術(shù)的發(fā)展會(huì)涌現(xiàn)大量的數(shù)據(jù)，用戶和企業(yè)都會(huì)面臨海量數(shù)據(jù)的存儲(chǔ)與處理問(wèn)題，分布式存儲(chǔ)模塊可以存儲(chǔ)海量數(shù)據(jù)，系統(tǒng)將大的數(shù)據(jù)塊拆分成若干小的數(shù)據(jù)塊，將這些小的數(shù)據(jù)塊存放在集群的各個(gè)節(jié)點(diǎn)上。云計(jì)算技術(shù)的重要典型框架是MapReduce框架，為海量數(shù)據(jù)的處理提供平臺(tái)。Hadoop是MapReduce框架的開源實(shí)現(xiàn)，既為海量數(shù)據(jù)的存儲(chǔ)提供了可靠的平臺(tái)-HDFS(Hadoop分布式文件系統(tǒng))[1]。又能夠很好地實(shí)現(xiàn)MapReduce框架，MapReduce框架為提高云計(jì)算平臺(tái)上的大批量作業(yè)的性能而設(shè)計(jì)的[2]。

2 Hadoop體系結(jié)構(gòu)

Hadoop是可靠的，可擴(kuò)展的和開放式的源代碼框架，由Apache基金會(huì)所開發(fā)。Hadoop系統(tǒng)本身具有高擴(kuò)展性，高效性以及高可靠性等特質(zhì)。分布式文件系統(tǒng)HDFS（Hadoop Distributed Files System）和分布式計(jì)算框架 MapReduce計(jì)算架構(gòu)屬于Apache Hadoop的兩個(gè)核心子模塊。

2.1 HDFS分布式文件系統(tǒng)

作為Hadoop集群的核心子項(xiàng)目之一的分布式并行文件系統(tǒng)是基于流數(shù)據(jù)訪問(wèn)模式開發(fā)的，可用于分布式計(jì)算的數(shù)據(jù)存儲(chǔ)管理，也可以滿足超大規(guī)模文件處理的需求。HDFS將分好的數(shù)據(jù)塊存儲(chǔ)在各個(gè)節(jié)點(diǎn)上，對(duì)數(shù)據(jù)塊進(jìn)行備份，以防節(jié)點(diǎn)失效。HDFS只需一次寫入數(shù)據(jù)便可以多次使用該數(shù)據(jù)，這種訪問(wèn)方式具有高效性[5]。在HDFS中，數(shù)據(jù)可用性可通過(guò)數(shù)據(jù)備份來(lái)實(shí)現(xiàn)。數(shù)據(jù)丟失將會(huì)立即采取修復(fù)措施[6]。

用戶需要在系統(tǒng)中運(yùn)行的應(yīng)用程序被稱為作業(yè)，任務(wù)作為作業(yè)的基本工作單元，各個(gè)計(jì)算節(jié)點(diǎn)可以處理任務(wù)，可以把一個(gè)作業(yè)分成一個(gè)或者多個(gè)任務(wù)[7]。這些任務(wù)處理完后被存儲(chǔ)在分布式文件系統(tǒng)中。

2.2 MapReduce計(jì)算框架

規(guī)模性，多樣性和高速性的特性促進(jìn)大數(shù)據(jù)更加快速的發(fā)展[8]。MapReduce是一種編程框架，支持高效的大規(guī)模計(jì)算，由Google提出。MapReduce架構(gòu)如圖1所示。

系統(tǒng)通常設(shè)計(jì)為在無(wú)共享架構(gòu)中運(yùn)行。數(shù)據(jù)可以分布式存儲(chǔ)，并通過(guò)并行使用多個(gè)磁盤來(lái)提高輸入/輸出速率。MapReduce計(jì)

圖1：MapReduce架構(gòu)示意圖

算框架依賴于Shuffle機(jī)制。Shuffle機(jī)制[9]的工作原理是把在Map任務(wù)中處理完的作業(yè)拉取到Reduce任務(wù)執(zhí)行之前。分塊，拷貝和排序代表Shuffle機(jī)制的每個(gè)不同的階段。MapReduce的主要目標(biāo)是分配處理以利用并行處理能力。這通常是通過(guò)將輸入數(shù)據(jù)集分割成若干塊在不同的機(jī)器上運(yùn)行來(lái)完成的。大型集群可以通過(guò)MapReduce框架進(jìn)行高效排序，在幾個(gè)小時(shí)內(nèi)達(dá)到對(duì)數(shù)兆字節(jié)的速度。

3 國(guó)內(nèi)外研究現(xiàn)狀

減少作業(yè)的完成時(shí)間和提高數(shù)據(jù)本地性是目前許多調(diào)度算法的研究重點(diǎn)。在基于節(jié)點(diǎn)本地任務(wù)完成時(shí)間預(yù)測(cè)的基礎(chǔ)上，通過(guò)控制不同的資源分配策略來(lái)提高數(shù)據(jù)本地性?，F(xiàn)有算法對(duì)于作業(yè)缺乏整體性規(guī)劃。

估算一個(gè)作業(yè)的剩余完成時(shí)間方面，楊浩等人[10]設(shè)計(jì)并實(shí)現(xiàn)了一種基于空閑時(shí)間的硬實(shí)時(shí)調(diào)度器 LSS，根據(jù)作業(yè)的剩余完成時(shí)間來(lái)調(diào)整作業(yè)的優(yōu)先級(jí)，作業(yè)越快處理完優(yōu)先級(jí)越高。Teng等人[11]提出的基于截止時(shí)間的硬實(shí)時(shí)任務(wù)調(diào)度算法 SPS，該算法通過(guò)流工作的周期長(zhǎng)短來(lái)規(guī)定作業(yè)的優(yōu)先級(jí)，同時(shí)盡量使作業(yè)在本地執(zhí)行，從而大大提高了作業(yè)在本地完成的幾率。Ullah等人[12]提出了一種新的搶占方法，該方法在進(jìn)行搶占決策時(shí)考慮了被執(zhí)行作業(yè)的剩余執(zhí)行時(shí)間。為了讓作業(yè)能在時(shí)間約束范圍內(nèi)執(zhí)行完，盧慧[13]提出一種基于資源預(yù)估的作業(yè)調(diào)度算法。不同作業(yè)對(duì)資源的需求也有所不同，根據(jù)資源預(yù)估模型以及數(shù)據(jù)本地性因素來(lái)改進(jìn)延遲調(diào)度策略。

表1：Map任務(wù)的平均運(yùn)行時(shí)間實(shí)現(xiàn)偽代碼

圖2：數(shù)據(jù)塊分布情況

圖3：非本地任務(wù)數(shù)量實(shí)驗(yàn)對(duì)比

現(xiàn)實(shí)中存在40%的重復(fù)性工作[14]，根據(jù)重復(fù)性工作規(guī)律探索出可預(yù)測(cè)的特征，可以對(duì)節(jié)點(diǎn)的預(yù)計(jì)完成時(shí)間進(jìn)行預(yù)測(cè)從而規(guī)劃資源分配，提高系統(tǒng)資源利用率。

4 數(shù)據(jù)本地化調(diào)度策略設(shè)計(jì)

數(shù)據(jù)本地性是Hadoop集群平臺(tái)下衡量作業(yè)調(diào)度器的重要的指標(biāo)。數(shù)據(jù)可以在同一機(jī)架內(nèi)傳輸，也可在不同的機(jī)架內(nèi)傳輸，這種跨機(jī)架的傳輸方式，產(chǎn)生網(wǎng)絡(luò) I/O，降低作業(yè)的平均完成時(shí)間，增加非本地任務(wù)的數(shù)量。節(jié)點(diǎn)優(yōu)先處理本地任務(wù)可以實(shí)現(xiàn)數(shù)據(jù)本地化，數(shù)據(jù)的讀取和處理便于任務(wù)的執(zhí)行。本地任務(wù)越多，數(shù)據(jù)讀取時(shí)間越短，非本地任務(wù)會(huì)加重?cái)?shù)據(jù)讀取時(shí)間，它需要從其它節(jié)點(diǎn)上讀取數(shù)據(jù)，加重網(wǎng)絡(luò)負(fù)擔(dān)，使節(jié)點(diǎn)間信息傳輸產(chǎn)生延遲。降低系統(tǒng)運(yùn)行效率。

數(shù)據(jù)分配不均會(huì)導(dǎo)致任務(wù)負(fù)載失衡，某些節(jié)點(diǎn)需要處理的任務(wù)增多，而其余節(jié)點(diǎn)會(huì)因沒(méi)有需要處理的任務(wù)處于空閑狀態(tài)。通過(guò)計(jì)算節(jié)點(diǎn)負(fù)載情況的任務(wù)調(diào)度方法來(lái)解決MapReduce集群存在大量非本地任務(wù)的問(wèn)題，該方法先計(jì)算節(jié)點(diǎn)的負(fù)載情況，根據(jù)節(jié)點(diǎn)負(fù)載情況進(jìn)行調(diào)度，有利于數(shù)據(jù)塊的合理分配，讓節(jié)點(diǎn)間的負(fù)載處于中間狀態(tài)，這種根據(jù)節(jié)點(diǎn)的使用情況進(jìn)行任務(wù)分配的策略在很大程度上滿足了數(shù)據(jù)本地化思想。

如圖2表明數(shù)據(jù)塊在集群中的分布狀況。MapReduce在選擇任務(wù)進(jìn)行調(diào)度時(shí)，只是簡(jiǎn)單的根據(jù)網(wǎng)絡(luò)拓?fù)湓谕?jí)任務(wù)中隨機(jī)選取。這樣的選擇方式會(huì)造成更多非本地任務(wù)的產(chǎn)生,從而降低處理和存儲(chǔ)速度。通過(guò)計(jì)算節(jié)點(diǎn)負(fù)載進(jìn)行任務(wù)分配的方法可以盡可能的解決這一問(wèn)題。

5 算法實(shí)現(xiàn)

在觀察節(jié)點(diǎn)負(fù)載情況時(shí)，并不能直接根據(jù)節(jié)點(diǎn)剩余任務(wù)數(shù)量來(lái)分配任務(wù)，節(jié)點(diǎn)性能不同，能處理的任務(wù)數(shù)量就不同，性能好的節(jié)點(diǎn)本身就能處理更多的本地任務(wù)。節(jié)點(diǎn)在作業(yè)執(zhí)行之初先不需要分配非本地任務(wù)，在執(zhí)行本地任務(wù)的過(guò)程中根據(jù)負(fù)載情況完成非本地任務(wù)的分配，這一過(guò)程是非靜態(tài)的。所以本文通過(guò)節(jié)點(diǎn)的本地任務(wù)預(yù)計(jì)完成時(shí)間與全部節(jié)點(diǎn)執(zhí)行本地任務(wù)的預(yù)計(jì)完成時(shí)間的平均值做比較，小于平均值極為負(fù)載較輕的節(jié)點(diǎn)，反之較重。

節(jié)點(diǎn)的本地任務(wù)預(yù)計(jì)完成時(shí)間是通過(guò)Map任務(wù)的平均運(yùn)行時(shí)間與所有的本地任務(wù)的數(shù)量的乘積計(jì)算得出的。代表已完成的Map任務(wù)的平均運(yùn)行時(shí)間，節(jié)點(diǎn)中本地任務(wù)的數(shù)量用表示，給節(jié)點(diǎn)分配的任務(wù)可能是本地任務(wù)和非本地任務(wù)，先通過(guò)本地任務(wù)數(shù)量的計(jì)算再進(jìn)行任務(wù)合理分配。如公式（2）所示。節(jié)點(diǎn)的本地任務(wù)預(yù)計(jì)完成時(shí)間：

全部節(jié)點(diǎn)執(zhí)行本地任務(wù)的預(yù)計(jì)完成時(shí)間的平均值根據(jù)節(jié)點(diǎn)的本地任務(wù)預(yù)計(jì)完成時(shí)間的總值與節(jié)點(diǎn)的個(gè)數(shù)的比值計(jì)算得出。通過(guò)平均值與單個(gè)節(jié)點(diǎn)的預(yù)計(jì)完成時(shí)間我們可以觀察到節(jié)點(diǎn)的狀態(tài)。如公式（3）所示。全部節(jié)點(diǎn)執(zhí)行本地任務(wù)的預(yù)計(jì)完成時(shí)間的平均值：

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

本文研究的作業(yè)調(diào)度算法是基于Hadoop平臺(tái)之下，因此需要搭建Hadoop集群。Hadoop集群的核心是HDFS和MapReduce計(jì)算框架。通過(guò)虛擬機(jī)的方式搭建Hadoop集群及其測(cè)試環(huán)境，假設(shè)存在兩個(gè)機(jī)架，給每個(gè)機(jī)架分配5臺(tái)虛擬機(jī)，每一個(gè)虛擬機(jī)占據(jù)512MB的內(nèi)存。測(cè)試工作為WordCount，通過(guò)測(cè)試傳統(tǒng)的任務(wù)調(diào)度策略非本地任務(wù)的數(shù)量以及平均完成時(shí)間和本文提出的負(fù)載均衡的任務(wù)調(diào)度策略中非本地任務(wù)的數(shù)量和平均完成時(shí)間進(jìn)行對(duì)比。

首先對(duì)兩種算法的非本地任務(wù)數(shù)量進(jìn)行對(duì)比實(shí)驗(yàn)，運(yùn)行job1，job2，job3和job4四個(gè)作業(yè)，非本地任務(wù)數(shù)量實(shí)驗(yàn)數(shù)據(jù)如圖3所示。默認(rèn)調(diào)度算法的作業(yè)中非本地任務(wù)數(shù)量分別是59，49，99和120。負(fù)載均衡的調(diào)度策略中非本地任務(wù)數(shù)量是43，33，85，109。由實(shí)驗(yàn)對(duì)比圖可以看出作業(yè)1非本地任務(wù)數(shù)量降低了27%，作業(yè)2的非本地任務(wù)數(shù)量降低了32%，作業(yè)3的非本地任務(wù)數(shù)量降低了14%，以及作業(yè)4的非本地任務(wù)數(shù)量降低了9%。綜上四個(gè)任務(wù)的非本地任務(wù)數(shù)量降低值可以預(yù)估每個(gè)任務(wù)的降低值。通過(guò)負(fù)載均衡調(diào)度算法可以看出非本地任務(wù)數(shù)量降低了20.5%。節(jié)點(diǎn)負(fù)載均衡調(diào)度策略可以減少系統(tǒng)中非本地任務(wù)的數(shù)量，同時(shí)減少數(shù)據(jù)遷移量，減少任務(wù)處理時(shí)間，提高系統(tǒng)效率。

其次，對(duì)兩種算法的平均完成時(shí)間進(jìn)行對(duì)比實(shí)驗(yàn)，默認(rèn)調(diào)度算法下job1 平均完成時(shí)間為700s，job2的平均完成時(shí)間為350s，job3的平均完成時(shí)間為460s以及job4的平均完成時(shí)間為653s。負(fù)載均衡調(diào)度策略中作業(yè)的平均完成時(shí)間分別為399，268，430，590。節(jié)點(diǎn)負(fù)載均衡的任務(wù)調(diào)度策略相比與系統(tǒng)默認(rèn)的調(diào)度策略有一定的縮短，平均完成時(shí)間實(shí)驗(yàn)數(shù)據(jù)如圖4所示。作業(yè)1的平均完成時(shí)間縮短了43%，作業(yè)2的平均完成時(shí)間縮短了23%，作業(yè)3的平均完成時(shí)間縮短了6%，作業(yè)4的平均完成時(shí)間縮短了9%。由多個(gè)個(gè)體可以估算出整體平均完成時(shí)間縮短了20.25%，通過(guò)實(shí)驗(yàn)證明節(jié)點(diǎn)負(fù)載調(diào)度策略降低了系統(tǒng)的平均完成時(shí)間，有效的優(yōu)化了系統(tǒng)性能。

通過(guò)對(duì)非本地任務(wù)數(shù)量以及平均完成時(shí)間的對(duì)比實(shí)驗(yàn)可以看出，負(fù)載均衡的任務(wù)調(diào)度策略比系統(tǒng)默認(rèn)的調(diào)度策略的非本地任務(wù)數(shù)量減少了，平均完成時(shí)間降低了，網(wǎng)絡(luò)I/O減少了，系統(tǒng)性能提高了。

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

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

本文主要提出對(duì)數(shù)據(jù)本地性調(diào)度方面進(jìn)行優(yōu)化，通過(guò)計(jì)算節(jié)點(diǎn)負(fù)載情況的方法來(lái)減少非本地任務(wù)的產(chǎn)生，從而減少數(shù)據(jù)遷移量。借助集群環(huán)境中MapReduce計(jì)算框架來(lái)實(shí)現(xiàn)根據(jù)節(jié)點(diǎn)情況分配任務(wù)的調(diào)度策略，提升系統(tǒng)性能。這種計(jì)算節(jié)點(diǎn)的調(diào)度算法仍存在一些不足，所以接下來(lái)，從這幾方面完善該任務(wù)調(diào)度策略。