大數(shù)據(jù)處理框架中基于MDP的任務調(diào)度算法*

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

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

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

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

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

1 基于 Markov決策過程的調(diào)度算法

1.1 Markov決策過程

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

1）S：狀態(tài)集，表示Agent所有可能狀態(tài)的集合；

3）T (s,a,s')：狀態(tài)轉移函數(shù)，表示在狀態(tài)s下執(zhí)行動作a，狀態(tài)變?yōu)?s '的概率；

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

MDP使用狀態(tài)集對當前集群與任務狀態(tài)進行描述，通過回報函數(shù)對任務調(diào)度策略進行評估，使用值迭代算法進行最優(yōu)策略求解，獲得最優(yōu)的任務調(diào)度策略．

1.2 算法建模

圖1 MDP模型

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

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

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

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

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

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

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

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

表1 nodeT 定義

1.3 求解算法流程

MDPS調(diào)度算法求解目標即根據(jù)當前節(jié)點與任務的狀態(tài)計算最優(yōu)策略p，目標是使得長期回報值最大．MDP策略求解有多種算法，本文使用應用最為廣泛的值迭代求解算法[7]．

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

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

迭代結束后，通過公式（8）求解最優(yōu)策略

表2 MDPS求解算法

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

2 實驗與結果分析

2.1 實驗環(huán)境

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

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

2.2 結果比較

從數(shù)據(jù)本地性和作業(yè)響應時間兩個方面對實驗結果進行分析．

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

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

圖2 數(shù)據(jù)本地性比較

圖3 作業(yè)響應時間比較

3 結 論

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

[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的自適應延遲調(diào)度算法[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．