大數據處理框架中基于MDP的任務調度算法*

馮延蓬，仵 博，孟憲軍，何國坤，江建舉

（深圳職業技術學院 教育技術與信息中心，廣東 深圳 518055）

MapReduce是一個用于大數據處理的分布式計算框架，是目前大數據處理平臺使用最為廣泛的并行編程模型[1]．MapReduce將待處理數據集分為若干獨立的數據塊，由map任務以完全并行的方式處理，然后對map任務的輸出進行排序，并把結果輸入給reduce任務．Hadoop[2]是由Google提出的基于MapReduce編程模型的開源實現，由分布式編程模型（MapReduce）和分布式存儲系統（HDFS）組成，具有高可靠性、高擴展性、高效性和高容錯性等優點，是對大數據進行分布式處理的典型框架．Hadoop得到業界和研究領域的共同關注，被眾多大型公司選作業務平臺，比如Yahoo、Facebook、Twitter等．

任務調度是MapReduce框架的重要組成部分，用戶作業提交后，系統會將其劃分為多個任務，通過調度算法決定將任務分配到哪個任務服務器上來執行．FIFO是 Hadoop默認的調度器，其優點是算法簡單，便于實現，其缺點為僅以作業進入隊列的先后順序作為調度依據，無法針對作業的不同需求進行差異化調度．Zaharia M.等人提出一種公平調度（Fair Scheduler）算法[3]，在多用戶共享集群的環境下，最大化地保證系統中的作業能平均分配到集群的資源．公平調度器能最大限度地滿足公平性原則，但無法滿足數據本地性要求．文獻[4]提出一種延遲調度（Delay Scheduling）算法，為隊首作業設置延遲等待時間，當空閑節點出現時，如果此節點包含隊首作業所需數據，則立刻執行隊首作業，否則先調度其它作業，在隊首作業的等待時間超過閾值時，立即執行隊首作業．延遲調度策略能夠很好地做到公平性與數據本地性之間的均衡，延遲調度的等待時間是通過配置文件進行靜態設置的，無法滿足集群負載動態變化的情況[5]．

本文提出一種基于 Markov決策過程[6]的MapReduce任務調度算法（Markov Decision Process Scheduling，MDPS），使用狀態空間描述集群中節點的負載情況和作業相關的數據本地性情況，通過狀態轉移函數描述調度前后節點和作業的變化，使用回報函數描述數據本地性、作業等待時間和節點負載的綜合回報，利用值迭代策略求解算法求解最優調度策略，動態調節作業數據本地性與作業響應時間，達到最優調度的效果．

1 基于 Markov決策過程的調度算法

1.1 Markov決策過程

Markov決策過程（Markov Decision Process，MDP）是為Agent進行智能決策建立的數學模型，如圖1所示．

1）S：狀態集，表示Agent所有可能狀態的集合；

3）T (s,a,s')：狀態轉移函數，表示在狀態s下執行動作a，狀態變為 s '的概率；

4）R (s,a)：回報函數，表示在狀態s下執行動作a獲得的回報值．

MDP使用狀態集對當前集群與任務狀態進行描述，通過回報函數對任務調度策略進行評估，使用值迭代算法進行最優策略求解，獲得最優的任務調度策略．

1.2 算法建模

圖1 MDP模型

在運行MapReduce的集群中，將選擇一個節點作為JobTracker，該節點是MapReduce的核心部件，用來完成任務調度與監控功能．將JobTracker作為一個Agent，需要根據當前集群負載狀態和不同任務的數據本地性需求，求取一個最優調度策略，其本質是一個最優決策求解問題，首要任務是建立MDPS的形式化描述模型．

（1）狀態集S用來描述當前集群中節點負載狀態和任務的數據本地性需求，因此狀態集其中，Snode表示集群中節點的負載狀態，若集群共包括n個節點，則使用一個n維向量表示，如式（1）所示：

（2）動作集A為 JobTracker可能采取的所有策略集合，即按照可能采取的策略，可定義 ai的取值為：

（3）狀態轉移函數T，表示在JobTracker選定某個調度策略后，系統從當前狀態變化到下一狀態的概率．由于狀態子集Snode和Stask相互獨立，按照可分解的思想，可以對Snode和Stask分別構建狀態轉移函數Tnode和Ttask．對于Ttask，由于任務對節點的數據本地性不受動作選擇節點的影響，只與任務的初始設定相關，可得Ttask如式（4）所示：

對于 Tnode，節點若被分派新任務，則節點的負載會增加，s_ni'相對 s_ni增加的概率較大；若節點未分派新任務，則 s_ni'相對 s_ni不變的概率較大，對應的 Tnode定義如表1所示，其中d為非負數，取值為節點增加一個任務所增加的負載值，表中取值為本文實驗中使用的值，在實際使用中可根據具體情況進行調節．

醫學分子生物學是醫學院校學生重要的基礎理論課程之一，以分子生物學的方法來研究中醫藥，闡明中醫辨證原理及中藥的作用機理，才能加快中醫學走向世界的步伐。中醫專業的學生肩負將傳統醫學發揚光大的使命，分子生物學的理論和實驗技術將成為有力的工具。多年來，通過不斷改進教學方法，從教材的選擇，教學內容的優化，加強教學過程中的各個環節等方面進行探索和實踐，在中醫專業醫學分子生物學的教學過程中取得了較好的效果。今后還要不斷努力，為社會培養更多高素質人才。

（4）回報函數R使用任務數據遷移的代價、數據本地性需求和節點負載的加權綜合指作為模型的回報值，如式（5）所示：

其中，調節因子 a+b+g=1(a30,b30,g30)，通過調節a、b和g的取值，可以根據不同的任務需求來設定回報函數中每一部分的權重．

表1 nodeT 定義

1.3 求解算法流程

MDPS調度算法求解目標即根據當前節點與任務的狀態計算最優策略p，目標是使得長期回報值最大．MDP策略求解有多種算法，本文使用應用最為廣泛的值迭代求解算法[7]．

在值迭代算法中，t時刻的回報函數可以通過當前狀態，回報函數，狀態轉移函數以及 1t- 時刻的回報值求取，如式（6）所示．

迭代結束條件如式（7）所示：

迭代結束后，通過公式（8）求解最優策略

表2 MDPS求解算法

MDPS調度求解算法流程使用值迭代（如表2）來求解最優策略，迭代次數決定了最終求解結果的運算時間和精度，如果迭代次數過少，則無法得到足夠的精度，如果迭代次數過多，則導致運算開銷過大，可以通過調整e的取值來控制迭代次數．

2 實驗與結果分析

2.1 實驗環境

實驗平臺由10臺曙光A840r-H組成，配置為：4*8378 CPU，16GB 內存，2*300G 15K 硬盤，256M SAS RAID 卡，2*4GB HBA 卡，2*1000M 集成網卡．采用Hadoop版本為0.21.0，通過對原有調度器包的替換和配置文件修改，運行本文的MDPS算法．

將本文MDPS算法與FIFO算法、Fair算法和Delay算法進行比較，針對每個算法所運行的環境，作業的設置和數據分布均一致．選取文本搜索作為實驗對象，處理大小為256M～4G的5組樣本，樣本來自作者所在高校校園一卡通系統的消費記錄，目的是匹配某些賬號的消費記錄．針對5組不同的數據樣本，每組測試10個作業，值迭代求解中折扣因子g=0.95．

2.2 結果比較

從數據本地性和作業響應時間兩個方面對實驗結果進行分析．

圖2表示了四種算法在5組樣本下的數據本地性的比較．FIFO算法由于只考慮進入隊列的先后，因此數據本地性存在隨機性．Fair算法未考慮數據本地性，在處理數據較少時，其數據本地性低于FIFO算法，當處理數據較多時，其數據本地性與FIFO算法相當．Delay算法與本文MDPS算法在數據本地性上表現較好，不管處理數據的多少，數據本地性均維持較高水平．

圖3表示四種算法在5組樣本下的任務響應時間的比較．在處理數據較少時，四種算法任務響應時間差別較?。S著處理數據的增多，FIFO算法的響應時間相比其它三種算法明顯增加．與Fair算法和Delay算法相比，本文的MDPS算法在任務響應時間上具有優勢．

圖2 數據本地性比較

圖3 作業響應時間比較

3 結 論

本文使用 Markov決策過程對大數據處理框架MapReduce中的任務調度算法進行建模，采用值迭代求解算法實現最優調度策略求解．該算法可以在獲得較好的數據本地性和較短的任務響應時間的同時，平衡節點的負載，提高集群的整體性能，通過實驗，驗證了提出算法的有效性和優越性．

[1] 李建江，崔?。甅apReduce并行編程模型研究綜述[J]．電子學報，2Ol1（11）：2636-2641．

[2] Apache Hadoop[EB/OL]．http://hadoop.apache.org/, 2012 March．

[3] Zaharia M, Borthakur D, Sarma J S, et al．Job Scheduling for Multi user Mapreduce Clusters[J]．EECS Department, 2009，55：1-16．

[4] Zaharia M，Borthakur D，Sarma J S，et al．Delay scheduling: A simple technique for achieving locality and fairness in cluster scheduling[C]．Proc of the EuroSys，2010：265-278．

[5] 寧文瑜，吳慶波，譚郁松．面向MapReduce的自適應延遲調度算法[J]．計算機工程與科學，2013，35（3）：52-57．

[6] Alexander L. Strehl and Michael L. Littman. An Empirical Evaluation of Interval Estimation for Markov Decision Processes[C]// The 16th IEEE International on Tools with Artificial Intelligence Conference. Washington,DC, USA: IEEE Computer Society, 2004：128-135．

[7] Kaelbling L，Littman M L，Cassandra A R．Planning and acting in partially observable stochastic domains[J]．Artificial Intelligence, 1998，101（1/2）：99-134．