MobiWay應用中基于Hadoop的多目標多任務調度算法

陳家宇 胡建軍

1(鄭州財經學院信息工程學院 河南 鄭州 450000)2(廣東財經大學信息學院 廣東 廣州 510320)

0 引 言

在多核處理器、虛擬化、分布式存儲、寬帶互聯網和自動化管理等技術飛速發展的今天，云計算應運而生，并得到長足的發展和應用。憑借其能夠按照用戶的需求合理分配系統資源，且用戶只需對所用資源付費等優點，云計算已受到IT商業巨頭和專家學者的高度關注。但隨著信息數據化進程的加快，利用有限的資源與成本存儲及處理海量的數據成為云計算技術發展亟需解決的問題[1-2]。

目前，MapReduce框架作為云計算技術的典型，為處理海量數據提供了可行的解決方案[3]。Hadoop是MapReduce框架的開源實現平臺，不僅能夠高效可靠地存儲處理海量數據，而且在并行化技術方面對應用開發者實現了透明處理[4]，為海量數據的并行處理提供簡單的編程框架。Hadoop作為一個新興的平臺，很多技術細節仍需完善，例如MapReduce調度器的工作效率不高與對異構環境適應能力差等問題。而任務調度技術是Hadoop平臺的核心，其技術優劣直接影響到平臺整體執行性能和系統資源利用效率的高低，因此針對調度算法的研究已有大量成果[5]。

文獻[6]提出了一種基于小位置值規則的粒子群算法(Particle Swarm Optimization，PSO)，基于優化傳輸和處理時間的想法，其主要目標是減少總處理時間。文獻[7]提出了一種基于具有動態作業優先級的貪婪背包單一隊列算法，不需要用戶干預就能建立特定的作業優先級，系統通過窮舉參數搜索來計算作業優先級，但該算法計算時間較長，不適用于多目標條件下的多任務調度。文獻[8]提出了一種基于動態優先級的混合調度器(Hybrid Scheduler，HybS)算法。其目標是減少可變長度和延遲，同時保持數據局部性。算法將分數背包算法應用與處理器分配，以使動態優先級適用于不同規模、不同任務長度或等待時間的各項任務。文獻[9]提出的應用特征的PaaS彈性資源管理機制能夠有效減少云計算請求過程中彈性操作的次數，降低了彈性操作帶來的資源開銷，提高了各種系統資源的用率，但在獲取請求率變化時的請求預測精度還有提升空間，以便更好地指導彈性資源分配。文獻[10]提出的FIFO調度程序是第一個Hadoop調度程序，它遵循FIFO模型：實現任務隊列，并通過到達順序將任務分配給主服務器。它是基本的調度算法，并不受任何條件約束。對于節點的分配，它使用了Torque資源管理器，并在每個節點上啟動兩個守護進程：Hadoop MapReduce和HDFS。此調度程序的主要問題是在處理大量任務時資源擁塞。Hadoop環境中的多目標調度需要考慮MapReduce調度機制的擴展，具體體現在以下幾個方面[11]：優化設置和清理任務，減少作業初始化和終止階段的時間成本，瞬間消息傳遞通信機制以及用于加速對性能敏感的任務調度和執行。

針對以上問題，提出了一種適用于多任務多目標的Hadoop調度算法(MOSMT)。MOSMT算法從用戶給定的服務等級協議(service-level agreement, SLA)約束中提取其服務質量偏好權重信息進行預處理，通過選擇唯一的優化目標，并將其他目標參數通過權重所體現的相對重要性轉化為約束條件來解決多目標問題。MOSMT算法思想總結如下：

(1) MOSMT算法同時考慮與用戶、資源相關的目標函數以及約束，其中，將截止日期和預算作為算法的優化目標，將避免資源爭用和集群的最佳工作量作為約束，通過優化目標與約束選取有效實現使用最小資源、最低花費處理最多數據量的目的。

(2) 通常來說，新設計調度算法難以應用于現實的Hadoop集群中，且應用過程需要耗費大量的時間和金錢。而提出的算法使用負載調度模擬器能很好地解決這一問題，因為SLS易于為調度程序設置各種相應的功能。

(3) MOSMT算法具有普適性，從而更好地適用于更多的應用場景。

為了驗證算法的可行性，采用MobiWay應用程序、以不同的度量進行評估，并將MOSMT算法與FIFO[10]、Fair調度程序[11]作對比，結果表明，MOSMT算法能夠實現類似的性能，并且在一些方面表現得更為優越。

1 MOSMT調度算法

1.1 算法建模

每個將要在Hadoop集群中執行的工作J都有一個已知映射任務數量Nmap和約簡任務數量Nreduce[12]，其數學表達為：

J={Ti|Ti∈Map∨Ti∈Reduce} |J|=N

(1)

式中：N為任務的總數，N=Nmap+Nreduce。

每個工作都有一個到達時間A、截止時間D和分配的預算Y。對于每項工作，從一開始就會明確待處理的數據量In。約簡任務需要處理的數據量是未知的，但可以使用之前的工作進行估算。此外，此處將輸入數據量的比率定義為r，其數學表達式為：

Out=r×In

(2)

假設每項工作都有一個所有者，它能夠處理工作并且給出關于執行的等級Π。因此作業J的屬性可以表示為：

Prop(J)=(A,D,B,In,r|Out=r×In,Owner)

(3)

每項工作J都會分配到特定數量的槽，其中，用于映射的槽稱為SLmap，用于約簡的槽稱為SLreduce，同一個槽可以同時用于映射和約簡[13]。因此在這種情況下，槽的總數SL≤SLmap+Slreduce。

每項任務Ti可以通過下列屬性進行關聯：

(1) 處理時間Pi，先驗評估映射任務或約簡任務，它用于計算作業的總時間：

(4)

(5)

(3) 截止時間di，其由集群資源管理器為每項任務設定，用于處理任務執行間的同步問題：

(6)

(4) 權重wi，其取決于資源消耗，與處理時間Pi和分配給任務的預算Yi的乘積成比例，即：

(7)

式中:α為比例常數，如果α≤1，則任務調度和執行將服從于總預算；否則，總開銷可能超過分配的預算。考慮到預算估計的性能，有：

(8)

(9)

(5) 擁有者的反饋πi，擁有者可以使用相同的值評級所有的任務，全局評級矢量Π可以表示為：

Π=[πi]Ti∈J

(10)

式中:π值可以通過計算測量任務執行的表現得到。例如，可以考慮實際執行時間coste(Ti)和任務完成度Ci來估計評級值，即：

(11)

上述定義的參數值和權重均可根據任務屬性和擁有者生成任務后動態分配。因此，任務Ti的屬性表示如下：

Prop(Ti)=(pi,Yi,di,fi,πi,type=map|reduce)

(12)

MOSMT解決的是多目標優化問題，則需要滿足多個約束條件和盡可能多的目標。因此，MOSMT算法考慮如下多重優化問題：

(13)

此外，MOSMT模型中考慮目標與用戶想要獲得的內容相關，最大目標與用戶反饋有關，并且用戶設定截止時間和預算的值。為了實現上述約束，需要了解關于映射任務與約簡任務的信息、處理節點的信息以及了解CPU內存、IO傳輸速率等信息[14]。

1.2 調度策略

在所提調度算法中，采用在每個步驟中的工作和資源間的最佳匹配來滿足。但最理想的方式是全面了解所有集群，找到需要在特定時刻運行的所有作業與可用資源之間的最佳匹配。

集群中任務執行順序匹配算法詳見算法1。每個節點會把預測信息通過heartbeat發送給RAM，RAM把這些預測信息合并起來會產生一個全局的視圖，通過該視圖了解到最早結束任務的信息，把該任務對應的節點作為被選中的節點，把任務完成之后釋放的資源加上節點本身剩余的資源作為節點的空余資源繼續調用作業選擇算法與任務選擇算法，最終選擇一個與節點最匹配的任務。但是，由于該節點的資源需要在最早結束任務完成之后才能把資源分配給選擇出的任務，因此可以提前把選擇出的任務的數據提前傳輸到最早結束任務所在節點，以達到任務數據本地性，減少數據傳輸時間，從而減少作業完成時間。

算法1集群中任務執行順序匹配算法

輸入：作業隊列J，作業配置信息Conf，預測模型結果

輸出：任務執行序列AssignedTask

1: Receive pieces of information through a heartbeat

2:ifnot exist free resourcethen

3:sort(NM,NMtasktimeremain)

4: selectNMof task first end time

5:endif

6:job=SelectAssignJob(J,NM)

7:length=Conf.GetMapTaskSize(job)

8:fori=0;i

9:score[i]=SelectAssignTask(NM,taski)

10:endfor

11:task=Maxscore(score)

12:AssignedTask.add(Task)

13:ifexist delay resourcethen

14: wait for the node to release the resource and move the date of task to NM in advance

15:endif

16:returnAssignedTask

MOSMT算法遵循最佳使用作業資源策略，詳見算法2。如果有足夠的槽用于映射任務與約簡任務，便能夠在指定的預算中完成作業并且直到截止時間結束，則服務函數返回正值。算法2驗證了每個服務中工作和資源之間的分配，然后通過每個服務結果的總和來判斷哪種分配方式更好。

算法2MOSMT 調度算法

要求2：taskQueue一個屬于工作J的所有任務Ti的隊列

要求3：assignedTasks分配到每個工作者節點的任務隊列

1:foreachworkernode∈Rdo

2:maxService←service(workernode)

3:F←0

4:foreachassignedTask∈workernode.assignedTasksdo

5:newAssignedTasks←workernode.assignedTasks-assignedTask

6:whiletaskQueue≠?do

7:task←taskQueue.edq()

8:fi←weight(task)

9:newAssignedTasks←newAssignedTasks∪task

10:ifservice(newAssignedTasks)>maxServicethen

11:maxService←service(newAssignedTasks)

12:F←F+fi

13:endif

14:endwhile

15:endfor

16:workernode.assignedTasks←newAssignedTasks

17:endfor

為了計算服務結果，還需找出Slmap和Slreduce是否可由特定的資源集群提供。 將cost(map) 和cost(reduce)分別定義為通過映射任務和約簡任務處理數據的時間成本。此外，將budger(map) 和budgerI(reduce)分別表示映射任務和約簡任務的預算成本。除上述成本以外，仍需考慮當數據不在約簡任務中運行的節點上時所支付的成本(僅適用于集群中存在的數據)。因此，還應該確定數據傳輸和處理的時間成本cost(data)和預算成budget(data)。

將start(map)和start(reduce)分別定義為映射任務和約簡任務的開始時間，當start(map)為定值時表示所有映射任務均在一項工作到達內部隊列時開始，即start(map)=A。為了計算工作J所需要的映射槽的數量，需要掌握start(map) 的最大值start(max)(map)，則SLmap和SLreduce最小值的數學表達式如下：

(14)

(15)

基于時間處理成本的考慮，使用預算Bused定義為是時間成本和資源數量之間的乘積，即：

(16)

MOSMT算法能夠集成在Hadoop平臺中。由于JobTracker是一個獨立的組件，因此新的調度程序應該擴展為TaskScheduler，并且定義其屬性和方法。完成擴展后，新調度程序需要插件。在MapReduce的配置文件中，有一個變量指示使用的算法，默認情況下變量為Fair Scheduler，如果用戶想使用新的算法，只需修改配置參數并指定它。

2 算法在MobiWay中的應用

城市交通是現代城市生活的伴隨，其可持續性在很大程度上取決于不同資源的消耗，如電力和燃料。因此，它表現為二氧化碳(CO2)和當地污染物排放，直接影響公民的生活質量。城市交通造成40%的二氧化碳排放和70%的道路運輸產生的其他污染物排放公路運輸占整個運輸產業溫室氣體排放量的70%以上，占所有排放總量的13%(運輸產業占排放總量的近20%)[18]。智能交通系統(Intelligent Transportation Systems, ITS)旨在通過結合專業基礎設施，通信技術和創新服務的解決方案來克服此類問題，以提高交通和移動管理、多模式或道路交通解決方案的質量[15]。

然而，為了開發準確的交通模型，能夠理解交通現象并從交通流量在現實世界城市中表現的統計模型做出決策，需要大量的數據。感應移動設備和各種移動應用，其目標是提供一個生態系統框架，使城市社區能夠利用移動的共享價值，這些價值可以超越社會網絡的經典觀點，分別是當前的服務創造趨勢。為了促進協作，該框架旨在在由應用提供商組成的服務云中分發不同的信息源(來自最終用戶或ITS服務，例如出租車公司、交付網絡等)。由于移動用戶將提供各種類型的傳感器數據，因此必須在數十萬參與者的網絡和具有不同興趣的共存服務之間保證智能數據收集、處理和共享。該框架構建了一個集成服務和應用程序的生態系統，靈活且可重新配置，提供給用戶多個包[16]。MobiWay的架構如圖1所示。

圖1 MobiWay 理論架構

該體系結構中的一個重要組成部分是數據聚合，旨在處理大量的流量數據，以便在城市級別提供準確的流量數據模型。這意味著需要收集來自城市數百萬輛汽車的數據，并持續存儲更長時間。進一步定期處理這些數據，得出流量可能性的統計和概率模型，取決于諸如一天中的時間、天氣狀況、預定事件等參數。所提出的算法可以處理不同粒度級別的數據在聚合、清理、統計分析等過程中出現的問題。通過分析城市不同區域的宏觀流量進行預處理，進行微觀層面和細粒度層面的條件評估。

處理應用程序使用MapReduce范例，Apache Hadoop和Spark作為支持技術。顧名思義，MapReduce有兩個重要的任務類型：map和reduce。從輸入接收的數據被分成塊，因此映射任務僅接收整個數據的一部分，并在許多地圖任務中并行運行[17]。所有映射任務的輸出都會進行排序并重定向到reducer。數據存儲在文件系統中，因此Hadoop為此部分使用HDFS(Hadoop分布式文件系統)。調度程序負責計劃如何將作業分配給映射或約簡器。實際應用中期望節點能夠負責計算和存儲，在節點上調度計劃安排的任務，以減少網絡中的流量。但是為了實現這一點，調度程序需要一種改進的算法[18]。因此，對于MobiWay，需要使用可提供優化性能的適當接口來實現map和reduce功能(希望獲得成本和時間最優的解決方案)。

3 實驗與分析

本節介紹了MOSMT算法的比較結果，開發并測試新Hadoop調度程序的所有設置步驟。首先介紹Hadoop框架所需的配置，然后設置調度程序負載模擬器，最后解釋了第一個Hadoop應用程序，其目標為了解場景背后的范例、工作性質和任務。

Hadoop集群設置考慮了如下的配置參數：

(1) Hadoop集群，在64位架構的Ubuntu計算機上進行實驗，包含maven、libssl-dev、cmake和protobuf庫；

(2) HDFS配置，dfs.replication設置為支持容錯；

(3) 調度負載模擬器(Scheduling Load Simulator，SLS)設置(整個模擬器內存或每個容器的內存，虛擬內核的數量等)；

(4) Rumen工具用于信息轉換并將信息添加至作業歷史記錄中，其輸出將是json文件。這個json文件將進一步用作SLS的輸入。

當新的調度算法實現后，很難將其部署在真實的集群中，并且消耗大量的計算資源。但是使用SLS能夠很好地解決這一問題，因為SLS更容易為調度程序部署各種不同的功能，但只能使用一臺計算機完成SLS的配置。采用該方式，不僅節省了大量時間，而且降低了成本。

圖2所示為SLS的體系結構。正如前文所述，SLS的配置均在一臺機器上運行，這意味著所有Hadoop組件應該在沒有網絡組件的同一臺機器上運行。由于調度程序是資源管理器的主要組件之一，因此其便是SLS中需要更改的主體。通常而言，SLS可看成是主調度程序的包裝器，如圖2中的灰色部分所示。在仿真器中，SLS模擬每個節點管理器和每個應用程序管理器。

圖2 調度負載模擬器架構

當作業執行映射任務和約簡任務時，JobHistory程序將保留所有歷史記錄。但這個歷史記錄并不是完全按照SLS指標顯示的，因此模擬器使用不同的輸入。

數據信息轉換過程包含兩個步驟：TraceBuilder和Folder。第一個步驟是處理數據以獲得更好的格式，第二個步驟是根據一些統計運算添加其他信息。這兩個步驟使用兩個命令執行，該命令可以在Hadoop框架中的Rumen工具目錄中找到，如需了解該命令的其他信息、參數和選項可以參考文獻[4]。

3.1 性能度量

調度負載模擬器使用Metrics庫來評估調度算法的性能。通過SLS使用量來進行具體量化。選取以下側重于時間成本和資源使用方式的度量指標與目前廣泛使用的Fair、FIFO算法進行對比實驗。

度量指標如下：

(1) 應用程序和容器：在此期間運行的應用程序量和容量；

(2) 資源：已被使用資源量與剩余資源量；

(3) 每隊列資源：每個隊列所使用的資源量與剩余的資源量；

(4) 時間：每個調度程序均有多個操作，比如添加、刪除和更新節點，以及添加和刪除應用，因此每個操作的時間都有很重要的意義；

(5) 內存：了解模擬器內存使用量是必要的。

3.2 實驗結果分析

本節測試新調度算法主要是將其與文獻[10]所提的FIFO調度程序和文獻[11]所提的Fair調度程序進行比較，由于Fair、FIFO算法已在Hadoop框架中實現，無需額外的工作量。為了使用SLS，需要兩個輸入文件：帶工作負載的json文件和帶拓撲的json文件。

在Hadoop上運行5 000個任務，使用Rumen以模擬器所需的格式獲取工作負載。為此，使用命令TraceBuilde，將歷史記錄作為輸入，并生成作業跟蹤和使用的拓撲。由于本算法創建了12個節點的拓撲結構，所以由TraceBuilde生成拓撲結構不是必需的。使用了具有不同輸入數據的MobiWay應用程序，實驗中有四種類型的輸入，按其大小分類，劃分為小型、中型、大型和超大型。

圖3顯示了群集中節點的已分配核心數。Fair和MOSMT調度程序的核心用法非常相似，均與作業執行時間相關。從圖中可以看出，Fair和MOSMT具有最佳的核心分配方案。

圖3 在Hadoop集群中一個節點的分配核心數量

當作業使用更多內存進行映射或縮減任務時，模擬器內存的分配數量將增加。從圖4中可明顯看出，當輸入增多時，FIFO和FAIR使用了更多的內存。同時，這也表明了MOSMT不會執行超過截止期限、預算或兩者的任務。

圖4 在Hadoop集群中一個節點的內存分配

圖5和圖6顯示了Hadoop集群中資源配置和資源重新配置/更新的性能。從中可以看出，MOSMT算法的時間成本與Fair、FIFO相似，不過性能優于兩者，因為MOSMT算法會動態計算用于映射與約簡任務槽的數量。

圖5 Hadoop集群中的資源提供性能

圖6 Hadoop集群中資源更新的性能

算法運行時作業提交的順序是一定的，因此作業的執行順序與提交時相同。不過調度程序重新排列作業時，即使有很多輸入量也應能夠訪問資源。在MOSMT算法中最大的工作沒有運行權限，因為輸入規模太大，截止時間和預算將超過預期。

圖7的結果表明，所有測試的調度算法在同一個工作中分配集群中的任務沒有等待任務而長時間停留在隊列中。

圖7 任務分配調度

算法度量指標體現了每個操作的時間成本，具體操作包括：分配節點、添加節點、刪除節點、節點更新、添加應用程序、刪除應用程序以及容器過期等。由于條件限制，只完成了添加節點、節點更新以及添加應用程序并刪除應用程序四個操作并進行算法性能測試，Hadoop集群中任務設置的性能測試結果如圖8和圖9所示。顯然，在應用設置成本中MOSMT算法在不同步長下增加節點所需的平均時間最長，而在應用完成成本對比中所需時間最短。

圖8 在Hadoop集群中的應用設置成本

圖9 Hadoop集群中應用完成成本

調度器的時間成本如圖10所示。由于MOSMT算法側重于考慮時間成本，因此在這個方面表現得更具優勢，而FIFO和Fair調度程序的結果相似。

圖10 調度階段的時間成本

調度器的時間成本與調度任務執行的時間相關，圖11顯示了所有計劃任務的開始時間、完成時間和持續時間。可以看出相對時間比較接近，意味著我們可以使用多種優化算法獲得相同的優化性能。

(a) 開始時間

(b) 完成時間

(c) 持續時間圖11 調度任務的運行時間

4 結 語

針對Hadoop平臺多任務多目標調度難題，提出了一種MOSMT算法。算法包括:Hadoop平臺中最相關的約束：避免資源爭用和集群的最佳工作量;與優化目標：截止日期和預算。應用于MobiWay評估MOSMT算法性能，測試結果表明，當工作存在成本和時間限制時，該算法相比于FIFO和Fair算法更為有效。在一定的資源和時間條件下，MOSMT通過使用調度負載模擬器配置不同的算法功能，從而降低時間成本和資源占用，實現多目標多任務的高效合理調度。

研究過程中假定MapReduce作業均是獨立的，調度任務進行前或者期間節點均不會發生故障，但這會使該算法的應用受到很多局限。后期，將針對用于工作流程的迭代MapReduce以及基于過去迭代信息進行預測的調度策略作進一步研究。此外，所提算法的評估指標有待完善，以更好地呈現適用多任務多目標調度算法的重要性，當然，算法的可擴展性是不容忽視的。