一種基于cpu占用率的動態調度改進算法

0動態調度算法ha是云計算的源結構，主要由云計算模型和hdfs（hadistributfilesystem）組成。目前,對Hadoop性能優化的研究主要有兩種方法,一是基于配置文件的性能優化,從配置文件入手,改變配置參數以提高Hadoop集群的性能。主要的配置文件有Conf下面的Core-site.xml,Hdfs-site.xml和Mapredsite.xml,這種優化方法在一定程度上能優化集群性能,但是也具有一定的局限性。一方面每個集群的硬件配置并不完全相同,每種優化方法并不一定適合所有的集群。另一方面,這種方法只能靜態地對集群的配置參數作修改,在任務運行中不能根據需要動態地改變配置文件并使其生效。第二種方法是優化Hadoop調度器。因為調度器一旦在啟動,整個任務運行過程將根據需要自適應變化,并且適用于不同硬件平臺下的Hadoop集群,所以對Hadoop調度器的研究具有很大的現實意義。目前,Hadoop的調度器有3種,分別是Hadoop默認的FIFO調度器,計算能力調度器,公平份額調度器。其中FIFO是所有調度器的基礎,然而此調度器按照作業提交先后順序將作業排序,再根據這一順序逐一把任務分發給各個節點執行,這就忽略了每個節點的實際負載情況。計算能力調度器能很好地支持內存密集型作業,公平調度器只是盡可能給每個任務分配等同的資源,都不能很好解決靈活性問題。本文即是在Hadoop默認調度器的基礎上,提出一種基于CPU占用率作為負載指標的動態調度算法。該算法能有效解決默認FIFO調度器缺乏動態性和靈活性的問題,進而縮短Hadoop集群的任務整體響應時間。1map-roung的模型結構Hadoop由核心組件MapReduce編程模型和HDFS分布式文件系統以及其他一些輔助組件組成。如圖1所示,其中,MapReduce編程模型負責Hadoop所有的數據流和控制流,貫穿整個作業執行始末。JobTracker統一調度和分發任務,TaskTracker負責每一個子任務的執行,直到任務運行完畢。MapReduce的設計思想是:一個任務可以拆成多個子任務同時執行,然后將分解的多個任務按要求進行處理,將中間結果歸并后統計出最后結果。MapReduce由Map和Reduce兩部分組成,其中Map處理一個key/value對生成的中間鍵值對集合,Reduce接受一個中間key和它對應的值的集合并合并這些值以形成一個較小的值集合。MapReduce數學模型如下:map:(k1,v1)→(list(k2,v2)reduce:(k2,list(v2))→(list(k3,v3)HDFS通過塊級數據的分布冗余存儲,負責所有臨時的或者永久的數據存儲工作。它采用主從模型,包含一個NameNode和一系列的DataNode,NameNode負責管理HDFS文件系統,接受用戶的請求,DataNode則用來存儲數據文件。Hadoop整合MapReduce和HDFS以及其他輔助層,將Map-Reduce中的TaskTracker和HDFS中的DataNode部署在同一個計算節點上。Hadoop默認的是FIFO調度器,用戶在Hadoop客戶端提交任務,調度器將所有用戶的作業提交到一個隊列中,JobTracker根據作業提交的先后順序將作業排序,再根據這一順序選擇將要調度的任務并將任務分發給TaskTracker。TaskTracker接收JobTracker分配的任務并執行。FIFO調度器使得JobTracker的工作負擔較輕,每個Job都公平共享整個集群,但是同時也失去了靈活性和JobTracker動態調度的可能性。JobTracker不能把握每個TaskTracker的實時負載能力,因為每個TaskTracker別無選擇,只能被動地接受JobTracker分發的任務。這樣使得繁忙的節點更繁忙,空閑的節點更空閑,造成了系統資源的浪費。2基于task-tabler的專業調度算法Hadoop由JobTracker/TaskTracker主從結構組成,且JobTracker在Hadoop集群中有且只有一個。用戶提交任務給JobTracker后,在JobTracker的構造函數中,生成一個TaskScheduler成員變量,即默認的FIFO調度器,進行Job的調度,在JobTracker的OfferService函數中,調用TaskScheduler的Start函數啟動FIFO調度器,調度器根據初始化配置和集群情況調度和分配任務。TaskTracker準備就緒后,向JobTracker報告自己當前的狀態。而JobTracker返回給TaskTracker的HeartbeatResponse中已經包含了分配好的任務LaunchTaskAction。TaskTracker接收該任務,并根據任務類型(Map任務或者Reduce任務)執行任務。JobTracker/TaskTracker調度簡圖如圖2所示。3提高算法3.1基于平臺的任務分配FIFO調度器只能完成簡單的任務分發和執行,每個Job公平共享整個集群,但是Job-Tracker無法根據當前TaskTracker的負載情況實時判斷當前節點是否還能繼續高效地執行任務。基于此提出一種改進算法:在FIFO調度器的基礎上,實時獲取每個節點的CPU占用率,根據每個節點當前的CPU占用率判斷節點的負載狀態,將此占用率放入心跳包(HeartBeat)中,并反饋給JobTracker。當JobTracker啟動調度器調度任務的時候,取出該值與CPU閾值比較,判斷當前節點負載情況,從而決定是否應該繼續給當前節點分配任務。調度流程如圖3所示。該算法在每個TaskTracker中執行一個線程來獲取CPU占用率。當JobClient類的SubmitJob函數提交Job后,JobTracker接受該任務,創建并初始化與Job有關的參數和一系列用來管理和調度任務的對象。Job分割成子任務后,由TaskTracker執行任務。即TaskTracker的Run函數一直鏈接JobTracker,如果鏈接成功,TaskTracker的OfferService函數會定期與JobTracker通信一次,報告自己任務的執行狀態并接受JobTracker指令。TaskTracker還會調用TransmitHeartBeat函數獲得HeartbeatResponse信息。然后調用HeartbeatResponse的getActions函數獲得JobTracker傳過來的指令即TaskTrackerAction數組,再根據數組類型決定應該執行的任務類型。TaskTracker和JobTracker的通信是由HeartBeat方法實現的。在原始版本的基礎上,添加一個獲取CPU占用率的線程,在OfferService函數中每隔一個心跳間隔啟動一次該線程更新一次CPU占用率,這樣就保證每次獲取到的CPU占用率是最新的。將此占用率傳遞給HeartBeat函數,每次JobTracker和TaskTracker通信的時候,都會向JobTracker報告該CPU占用率,實時地與CPU閾值作比較,JobTracker再根據當前節點的負載情況分配任務。這樣就做到了任務分配的實時性和動態性。以某節點為例,作浮點數運算測試,CPU占用率達到峰值0.95(閾值)時,CPU計算性能逐漸下降。可以得知,當實時獲取的CPU占用率大于此閾值時,說明當前CPU處于繁忙狀態。此時,JobTracker不能再向此節點分配任務,應該將任務分配給處于空閑狀態的節點執行。直到當前節點的CPU占用率小于閾值時,JobTracker再繼續向該節點分配任務,循環直到任務全部執行完成。這樣就可以實時動態地調整集群的負載狀況,進而使作業整體響應效率提高。3.2doop工程代碼本算法采用Java語言,將新增代碼添加到Hadoop工程源代碼中,在eclipse平臺上重新編譯生成jar包。輸入:用戶提交的任務輸出:map/reduce計算出的結果4結果分析4.1節點pcr操作系統Cenos5.6,帶寬100M,8個節點,Intel雙核,硬盤250G,內存2GB,jdk1.6.0-21,Hadoop源代碼版本hadoop-0.21.0。4.2實驗結果和討論本文基于Hadoop-0.21.0版本實現改進算法。將改進的源代碼在eclipse上編譯成jar包,分別是hadoopcore.jar,hadoop-mapred.jar,hadoop-hdfs.jar,將3個jar包分別部署在Hadoop集群的每個節點上并重啟集群使其生效。實驗采用Hadoop系統自帶的terasort(計算集中型)基準測試程序。該程序實現數據排序的功能,是典型的CPU密集型程序,適用于本改進算法。實驗分別對1百萬字節,2百萬字節,4百萬字節和5百萬字節的數據排序,在原始版本和改進版本上分別測試。為了減小測試結果的隨機性,實驗分別測試了10組數據取其平均值作為最終測試結果。實驗結果如表1,2,3,4所示。表中記錄了四組數據原始版和改進版的任務整體響應時間。可以得出,運行于改進版的四組數據的任務整體響應效率都有不同程度的提高,分別提高了2.1秒,3.8秒,5.4秒,7.8秒。直觀對比如圖4所示。計算得出,改進版比原始版的作業整體響應效率(任務提高的時間/原始版本任務執行時間)至少提高了6%,如圖6所示。并且,隨著任務數據量的不斷增加,任務的整體響應效率有快速提高的趨勢,這將更利于長作業的運行。雖然實驗測試數據呈倍數增長,但是任務執行效率的提升并沒有按照倍數增長。這是因為,一方面,任何CPU的運算能力是有上限的,默認版本的CPU計算能力已經達到或者超過了CPU運算性能的最佳運算狀態,本算法只改進了CPU的過載運算部分,使得在不影響CPU計算能力的情況下,最快地完成任務。另一方面,改進算法啟動一個線程實時獲取CPU占用率,此線程在實時獲取CPU占用率的同時也耗費了一部分CPU計算資源。5任務整體響應時間本文深入分析并改進了Hadoop默認任務調度模型,提出的以CPU占用率作為負載指標,在循環分配任務時根據反饋的負載指標判斷