王溪波 王珊珊 王越峰

（沈陽工業大學 遼寧省沈陽市 110000）

1 引言

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

2 Hadoop體系結構

Hadoop是可靠的，可擴展的和開放式的源代碼框架，由Apache基金會所開發。Hadoop系統本身具有高擴展性，高效性以及高可靠性等特質。分布式文件系統HDFS（Hadoop Distributed Files System）和分布式計算框架 MapReduce計算架構屬于Apache Hadoop的兩個核心子模塊。

2.1 HDFS分布式文件系統

作為Hadoop集群的核心子項目之一的分布式并行文件系統是基于流數據訪問模式開發的，可用于分布式計算的數據存儲管理，也可以滿足超大規模文件處理的需求。HDFS將分好的數據塊存儲在各個節點上，對數據塊進行備份，以防節點失效。HDFS只需一次寫入數據便可以多次使用該數據，這種訪問方式具有高效性[5]。在HDFS中，數據可用性可通過數據備份來實現。數據丟失將會立即采取修復措施[6]。

用戶需要在系統中運行的應用程序被稱為作業，任務作為作業的基本工作單元，各個計算節點可以處理任務，可以把一個作業分成一個或者多個任務[7]。這些任務處理完后被存儲在分布式文件系統中。

2.2 MapReduce計算框架

規模性，多樣性和高速性的特性促進大數據更加快速的發展[8]。MapReduce是一種編程框架，支持高效的大規模計算，由Google提出。MapReduce架構如圖1所示。

系統通常設計為在無共享架構中運行。數據可以分布式存儲，并通過并行使用多個磁盤來提高輸入/輸出速率。MapReduce計

圖1：MapReduce架構示意圖

算框架依賴于Shuffle機制。Shuffle機制[9]的工作原理是把在Map任務中處理完的作業拉取到Reduce任務執行之前。分塊，拷貝和排序代表Shuffle機制的每個不同的階段。MapReduce的主要目標是分配處理以利用并行處理能力。這通常是通過將輸入數據集分割成若干塊在不同的機器上運行來完成的。大型集群可以通過MapReduce框架進行高效排序，在幾個小時內達到對數兆字節的速度。

3 國內外研究現狀

減少作業的完成時間和提高數據本地性是目前許多調度算法的研究重點。在基于節點本地任務完成時間預測的基礎上，通過控制不同的資源分配策略來提高數據本地性。現有算法對于作業缺乏整體性規劃。

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

表1：Map任務的平均運行時間實現偽代碼

圖2：數據塊分布情況

圖3：非本地任務數量實驗對比

現實中存在40%的重復性工作[14]，根據重復性工作規律探索出可預測的特征，可以對節點的預計完成時間進行預測從而規劃資源分配，提高系統資源利用率。

4 數據本地化調度策略設計

數據本地性是Hadoop集群平臺下衡量作業調度器的重要的指標。數據可以在同一機架內傳輸，也可在不同的機架內傳輸，這種跨機架的傳輸方式，產生網絡 I/O，降低作業的平均完成時間，增加非本地任務的數量。節點優先處理本地任務可以實現數據本地化，數據的讀取和處理便于任務的執行。本地任務越多，數據讀取時間越短，非本地任務會加重數據讀取時間，它需要從其它節點上讀取數據，加重網絡負擔，使節點間信息傳輸產生延遲。降低系統運行效率。

數據分配不均會導致任務負載失衡，某些節點需要處理的任務增多，而其余節點會因沒有需要處理的任務處于空閑狀態。通過計算節點負載情況的任務調度方法來解決MapReduce集群存在大量非本地任務的問題，該方法先計算節點的負載情況，根據節點負載情況進行調度，有利于數據塊的合理分配，讓節點間的負載處于中間狀態，這種根據節點的使用情況進行任務分配的策略在很大程度上滿足了數據本地化思想。

如圖2表明數據塊在集群中的分布狀況。MapReduce在選擇任務進行調度時，只是簡單的根據網絡拓撲在同級任務中隨機選取。這樣的選擇方式會造成更多非本地任務的產生,從而降低處理和存儲速度。通過計算節點負載進行任務分配的方法可以盡可能的解決這一問題。

5 算法實現

在觀察節點負載情況時，并不能直接根據節點剩余任務數量來分配任務，節點性能不同，能處理的任務數量就不同，性能好的節點本身就能處理更多的本地任務。節點在作業執行之初先不需要分配非本地任務，在執行本地任務的過程中根據負載情況完成非本地任務的分配，這一過程是非靜態的。所以本文通過節點的本地任務預計完成時間與全部節點執行本地任務的預計完成時間的平均值做比較，小于平均值極為負載較輕的節點，反之較重。

節點的本地任務預計完成時間是通過Map任務的平均運行時間與所有的本地任務的數量的乘積計算得出的。代表已完成的Map任務的平均運行時間，節點中本地任務的數量用表示，給節點分配的任務可能是本地任務和非本地任務，先通過本地任務數量的計算再進行任務合理分配。如公式（2）所示。節點的本地任務預計完成時間：

全部節點執行本地任務的預計完成時間的平均值根據節點的本地任務預計完成時間的總值與節點的個數的比值計算得出。通過平均值與單個節點的預計完成時間我們可以觀察到節點的狀態。如公式（3）所示。全部節點執行本地任務的預計完成時間的平均值：

6 實驗設計

本文研究的作業調度算法是基于Hadoop平臺之下，因此需要搭建Hadoop集群。Hadoop集群的核心是HDFS和MapReduce計算框架。通過虛擬機的方式搭建Hadoop集群及其測試環境，假設存在兩個機架，給每個機架分配5臺虛擬機，每一個虛擬機占據512MB的內存。測試工作為WordCount，通過測試傳統的任務調度策略非本地任務的數量以及平均完成時間和本文提出的負載均衡的任務調度策略中非本地任務的數量和平均完成時間進行對比。

首先對兩種算法的非本地任務數量進行對比實驗，運行job1，job2，job3和job4四個作業，非本地任務數量實驗數據如圖3所示。默認調度算法的作業中非本地任務數量分別是59，49，99和120。負載均衡的調度策略中非本地任務數量是43，33，85，109。由實驗對比圖可以看出作業1非本地任務數量降低了27%，作業2的非本地任務數量降低了32%，作業3的非本地任務數量降低了14%，以及作業4的非本地任務數量降低了9%。綜上四個任務的非本地任務數量降低值可以預估每個任務的降低值。通過負載均衡調度算法可以看出非本地任務數量降低了20.5%。節點負載均衡調度策略可以減少系統中非本地任務的數量，同時減少數據遷移量，減少任務處理時間，提高系統效率。

其次，對兩種算法的平均完成時間進行對比實驗，默認調度算法下job1 平均完成時間為700s，job2的平均完成時間為350s，job3的平均完成時間為460s以及job4的平均完成時間為653s。負載均衡調度策略中作業的平均完成時間分別為399，268，430，590。節點負載均衡的任務調度策略相比與系統默認的調度策略有一定的縮短，平均完成時間實驗數據如圖4所示。作業1的平均完成時間縮短了43%，作業2的平均完成時間縮短了23%，作業3的平均完成時間縮短了6%，作業4的平均完成時間縮短了9%。由多個個體可以估算出整體平均完成時間縮短了20.25%，通過實驗證明節點負載調度策略降低了系統的平均完成時間，有效的優化了系統性能。

通過對非本地任務數量以及平均完成時間的對比實驗可以看出，負載均衡的任務調度策略比系統默認的調度策略的非本地任務數量減少了，平均完成時間降低了，網絡I/O減少了，系統性能提高了。

圖4：作業的平均完成時間對比

7 結束語

本文主要提出對數據本地性調度方面進行優化，通過計算節點負載情況的方法來減少非本地任務的產生，從而減少數據遷移量。借助集群環境中MapReduce計算框架來實現根據節點情況分配任務的調度策略，提升系統性能。這種計算節點的調度算法仍存在一些不足，所以接下來，從這幾方面完善該任務調度策略。