馮延蓬，仵 博，孟憲軍，何國(guó)坤，江建舉

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

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

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

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

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

1.1 Markov決策過(guò)程

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

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

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

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

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

1.2 算法建模

圖1 MDP模型

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

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

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

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

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

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

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

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

表1 nodeT 定義

1.3 求解算法流程

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

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

迭代結(jié)束條件如式（7）所示：

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

表2 MDPS求解算法

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

2 實(shí)驗(yàn)與結(jié)果分析

2.1 實(shí)驗(yàn)環(huán)境

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

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

2.2 結(jié)果比較

從數(shù)據(jù)本地性和作業(yè)響應(yīng)時(shí)間兩個(gè)方面對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析．

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

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

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

圖3 作業(yè)響應(yīng)時(shí)間比較

3 結(jié) 論

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

[1] 李建江，崔?。甅apReduce并行編程模型研究綜述[J]．電子學(xué)報(bào)，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的自適應(yīng)延遲調(diào)度算法[J]．計(jì)算機(jī)工程與科學(xué)，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．