孫懷英，虞慧群，范貴生，陳麗瓊

1.華東理工大學(xué) 計(jì)算機(jī)科學(xué)與工程系，上海 200237

2.上海市計(jì)算機(jī)軟件評(píng)測(cè)重點(diǎn)實(shí)驗(yàn)室，上海 201112

3.上海應(yīng)用技術(shù)大學(xué) 計(jì)算機(jī)科學(xué)與信息工程系，上海 200235

1 引言

軟件定義網(wǎng)絡(luò)（software defined network，SDN）是一種可以將基礎(chǔ)設(shè)備的網(wǎng)絡(luò)控制功能分離并集中地部署到控制器中的網(wǎng)絡(luò)架構(gòu)。它可以讓企業(yè)有著前所未有的可編程性、自動(dòng)化能力、網(wǎng)絡(luò)控制能力。因此，SDN為企業(yè)建立更具有創(chuàng)新性的、易管理的和高擴(kuò)展性的數(shù)據(jù)中心創(chuàng)造了豐富的機(jī)會(huì)。SDN中的領(lǐng)導(dǎo)技術(shù)是基于OpenFlow協(xié)議[1]，這已經(jīng)是用于SDN的一個(gè)標(biāo)準(zhǔn)，且已經(jīng)在各種網(wǎng)絡(luò)和網(wǎng)絡(luò)產(chǎn)品得到廣泛使用[2-3]。OpenFlow的網(wǎng)絡(luò)監(jiān)控和流量監(jiān)控能力可以對(duì)大數(shù)據(jù)處理系統(tǒng)如Hadoop的性能提高提供重要的信息。因此，基于OpenFlow的SDN數(shù)據(jù)中心是當(dāng)前一個(gè)重要的發(fā)展趨勢(shì)。

大數(shù)據(jù)處理是此類數(shù)據(jù)中心的重要應(yīng)用之一。大規(guī)模數(shù)據(jù)處理是如今常用的因特網(wǎng)應(yīng)用如搜索引擎、在線地圖服務(wù)、社交網(wǎng)絡(luò)等的重要部分?，F(xiàn)有的云計(jì)算系統(tǒng)如 MapReduce[4]、Hadoop[5]、Dryad[6]、Spark[7]等都是基于簡(jiǎn)單的并行處理模式，主要用于數(shù)據(jù)密集型的應(yīng)用。其中，Hadoop是MapReduce的一個(gè)開(kāi)源實(shí)現(xiàn)，已經(jīng)成為了雅虎、亞馬遜、Facebook等大型企業(yè)的通用計(jì)算系統(tǒng)[5]。但在實(shí)際的Hadoop系統(tǒng)中，存在一個(gè)影響整體系統(tǒng)性能的NP完全問(wèn)題，解決的關(guān)鍵是要能找到任務(wù)的近似最優(yōu)分配方案，從而最小化作業(yè)的完成時(shí)間[8]。

現(xiàn)有的最小化作業(yè)完成時(shí)間算法，多是從提高任務(wù)數(shù)據(jù)本地性（如果一個(gè)任務(wù)在執(zhí)行時(shí)是從其對(duì)應(yīng)的計(jì)算節(jié)點(diǎn)的本地磁盤讀取輸入數(shù)據(jù)，則該任務(wù)稱為數(shù)據(jù)本地型任務(wù)，否則為數(shù)據(jù)遠(yuǎn)程型任務(wù)）方面著手，如Hadoop默認(rèn)調(diào)度器HDS（Hadoop default scheduler）[9]和Jin等[10]提出的BAR（balance reduce）調(diào)度器。它們存在的問(wèn)題是：高度保證任務(wù)數(shù)據(jù)本地性，可能存在將任務(wù)持續(xù)分配給高負(fù)載節(jié)點(diǎn)的情況，或者沒(méi)有充分利用網(wǎng)絡(luò)中的可用帶寬，造成任務(wù)的長(zhǎng)時(shí)間等待，不能實(shí)現(xiàn)任務(wù)的近似最優(yōu)分配，從而不能最小化作業(yè)的完成時(shí)間。

由于網(wǎng)絡(luò)帶寬是稀有資源，在充分保證數(shù)據(jù)的本地性情況下，充分利用可用的網(wǎng)絡(luò)帶寬資源，對(duì)于作業(yè)完成時(shí)間的降低是至關(guān)重要的。本文的貢獻(xiàn)如下：

（1）將SDN引入Hadoop中，使用SDN的帶寬控制能力，將網(wǎng)絡(luò)中的可用剩余帶寬作為任務(wù)調(diào)度的重要參數(shù)。

（2）定義作業(yè)完成時(shí)間問(wèn)題的描述，根據(jù)網(wǎng)絡(luò)中的剩余帶寬提出任務(wù)調(diào)度算法RBA，因此可獲得任務(wù)的近似最優(yōu)分配，實(shí)現(xiàn)作業(yè)完成時(shí)間的最小化。

（3）通過(guò)仿真實(shí)驗(yàn)，驗(yàn)證RBA在作業(yè)完成時(shí)間、任務(wù)數(shù)據(jù)本地性及計(jì)算時(shí)間方面的性能。

本文結(jié)構(gòu)如下：第2部分介紹相關(guān)工作；第3部分介紹問(wèn)題描述及算法RBA；第4部分是仿真實(shí)驗(yàn)；第5部分是結(jié)束語(yǔ)。

2 相關(guān)工作

文獻(xiàn)[11-12]指出任務(wù)調(diào)度對(duì)Hadoop的作業(yè)完成效果有著重要影響。文獻(xiàn)[8-10,13-17]是關(guān)于改善Hadoop中作業(yè)調(diào)度性能的。文獻(xiàn)[9]中的Hadoop默認(rèn)調(diào)度器（HDS）主要是保證任務(wù)的數(shù)據(jù)本地性，不斷地將任務(wù)分配給其輸入數(shù)據(jù)所在的節(jié)點(diǎn)，因此在作業(yè)完成時(shí)間方面沒(méi)有什么優(yōu)化。Zaharia等人[14]提出了延時(shí)調(diào)度，以解決數(shù)據(jù)本地性和公平性的沖突問(wèn)題。但是引入的延時(shí)可能會(huì)導(dǎo)致資源空閑。Tan等人[15]認(rèn)為當(dāng)前的調(diào)度器并非對(duì)map任務(wù)和reduce任務(wù)進(jìn)行聯(lián)合優(yōu)化，這可能會(huì)產(chǎn)生作業(yè)饑餓及不利的數(shù)據(jù)本地性。因此，提出一個(gè)耦合調(diào)度器，將map和reduce任務(wù)結(jié)合起來(lái)。由于Hadoop假設(shè)所有的集群節(jié)點(diǎn)是為一個(gè)單獨(dú)的用戶服務(wù)的，因此耦合調(diào)度器無(wú)法在共享環(huán)境下保證高性能[16]。因此，Seo等人[16]提出預(yù)先取數(shù)據(jù)和預(yù)先shuffle的方案，但傳輸數(shù)據(jù)時(shí)的帶寬占用時(shí)間是較難有效減少的。

Fischer等人[17]研究了Hadoop中的任務(wù)分配，提出理想化的Hadoop模型，來(lái)評(píng)估任務(wù)分配的代價(jià)。而事實(shí)上，任務(wù)分配是一個(gè)NP完全問(wèn)題，只能是找到近似最優(yōu)的方案[8,11]。因此，Jin等人[10]提出BAR調(diào)度器，BAR首先產(chǎn)生一個(gè)任務(wù)初始分配結(jié)果；接著，通過(guò)不斷地調(diào)整初始分配方案將作業(yè)的完成時(shí)間降低到最小。從本文第4章的例子中看出，BAR和RBA相比于HDS的作業(yè)完成時(shí)間提早了2.12 s和4.00 s，RBA比BAR提早了1.88 s。相對(duì)而言，RBA達(dá)到了近似最優(yōu)的效果。Wang等人[18]關(guān)注的是使用SDN為大數(shù)據(jù)應(yīng)用配置物理拓?fù)浜吐酚?，但是沒(méi)有關(guān)注作業(yè)調(diào)度的問(wèn)題。文獻(xiàn)[8]提出的BASS（bandwidth aware scheduling with SDN）算法，同樣將網(wǎng)絡(luò)帶寬作為任務(wù)分配的參數(shù)，但BASS在進(jìn)行任務(wù)分配前，需要對(duì)網(wǎng)絡(luò)中的最大帶寬按時(shí)間進(jìn)行分片，若所需的帶寬分片不足以傳輸對(duì)應(yīng)的輸入數(shù)據(jù)，則不會(huì)將任務(wù)分配給遠(yuǎn)程節(jié)點(diǎn)。

3 問(wèn)題描述

Hadoop用于大規(guī)模數(shù)據(jù)的處理，其中的輸入處理文件通常是分割成多個(gè)數(shù)據(jù)塊存放于各個(gè)服務(wù)器節(jié)點(diǎn)上。為了有效進(jìn)行數(shù)據(jù)處理，Hadoop的每個(gè)作業(yè)分成多個(gè)子任務(wù)，每個(gè)子任務(wù)會(huì)分配到一個(gè)服務(wù)器節(jié)點(diǎn)上進(jìn)行數(shù)據(jù)塊的處理。因此，當(dāng)作業(yè)所有的子任務(wù)都完成了，該作業(yè)的狀態(tài)才會(huì)完成。

Hadoop集群網(wǎng)絡(luò)中各個(gè)鏈路的帶寬利用率是不盡相同的，對(duì)應(yīng)的最大可用剩余帶寬也不盡相同。因此，本文將SDN引入Hadoop中，通過(guò)SDN的網(wǎng)絡(luò)控制能力可獲得實(shí)時(shí)可用的網(wǎng)絡(luò)帶寬，從任務(wù)的數(shù)據(jù)副本所在的節(jié)點(diǎn)和目的節(jié)點(diǎn)（任務(wù)可能分配到的節(jié)點(diǎn)）之間的所有路徑中，選擇具有最大可用剩余帶寬的路徑作為傳輸數(shù)據(jù)的工作路徑（路徑的最大可用剩余帶寬值等于路徑上實(shí)時(shí)可用帶寬值最小的鏈路對(duì)應(yīng)的帶寬值）。該路徑的最大可用剩余帶寬即為任務(wù)分配時(shí)的重要參數(shù)。RBA在充分考慮任務(wù)數(shù)據(jù)的本地性的情況下，充分利用網(wǎng)絡(luò)中的最大剩余可用帶寬，實(shí)現(xiàn)任務(wù)的近似最優(yōu)分配，從而達(dá)到最小化作業(yè)完成時(shí)間的目的。本文常用符號(hào)如表1所示。

Table 1 Symbols used in this paper表1 本文常用符號(hào)

定義1引入SDN的Hadoop集群中的任務(wù)調(diào)度需求是一個(gè)三元組：Ξ=(Jbr,snd,Gph)，其中：

（1）Jbr是要在時(shí)間[0,T]內(nèi)完成的用戶作業(yè)請(qǐng)求。作業(yè)請(qǐng)求Jbri=(jbti,Ti)，jbti={jti,1,jti,2,…,jti,n}為該作業(yè)的任務(wù)集合，任務(wù)jti,j={jdsij,jwdij}，jdsij為任務(wù)的輸入數(shù)據(jù)分片大小（MB）；jwdij為任務(wù)對(duì)應(yīng)的指令數(shù)。

（2）snd是執(zhí)行任務(wù)的計(jì)算節(jié)點(diǎn)，節(jié)點(diǎn)sndi=(Ewdi,Psdi)，Ewdi為節(jié)點(diǎn)已有的工作量（指令數(shù)），Psdi為節(jié)點(diǎn)的處理速度（MIPS）。

（3）Gph=(V,Lnk)為Hadoop集群網(wǎng)絡(luò)拓?fù)?，V為拓?fù)渲械捻旤c(diǎn)集合，表示集群中的所有計(jì)算節(jié)點(diǎn)和交換機(jī)節(jié)點(diǎn)，Lnk=(likij,mbdij,arij)為頂點(diǎn)間的鏈路集合，lnkij為鏈路編號(hào)，下標(biāo)i、j表示鏈路兩端的頂點(diǎn)號(hào)，mbdij為該鏈路的最大帶寬，arij為該鏈路當(dāng)前可用帶寬百分比。

定義2數(shù)據(jù)分布是使用二分圖G=((T?S),E)表示，令m=|T|且n=|S|，其中T是所有待分配的任務(wù)集合，S為計(jì)算節(jié)點(diǎn)的集合，E?(T×S)是T和S之間的邊的集合，邊e(t,s)表示任務(wù)t∈T的輸入數(shù)據(jù)是放置在節(jié)點(diǎn)s∈S上，且SG.pre(t)是任務(wù)t所對(duì)應(yīng)的輸入數(shù)據(jù)所在的計(jì)算節(jié)點(diǎn)集合。假設(shè)|SG.pre(t)|≥1表示圖G中任務(wù)頂點(diǎn)t的度至少為1。

定義3分配策略是一個(gè)函數(shù)Aloc:T→S，將任務(wù)t∈T分配給計(jì)算節(jié)點(diǎn)Aloc(t)∈S。設(shè)?為一個(gè)分配策略，則任務(wù)t分配到的計(jì)算節(jié)點(diǎn)記為?(t)。在?分配下，任務(wù)t是本地的，當(dāng)且僅當(dāng)?(t)在配置圖G中有邊e(t,?(t))，否則t為遠(yuǎn)程的。設(shè)lonb?和renb?分別為作業(yè)中的本地任務(wù)數(shù)和遠(yuǎn)程任務(wù)數(shù)。如，任務(wù)jti,j在?分配下，分配到的計(jì)算節(jié)點(diǎn)為?(jti,j)，且該分配下節(jié)點(diǎn)的任務(wù)數(shù)據(jù)本地率DR為：

在分配方案?下，計(jì)算節(jié)點(diǎn)snds可能會(huì)分配到多個(gè)任務(wù)，假設(shè)任務(wù)在一個(gè)計(jì)算節(jié)點(diǎn)上是按順序執(zhí)行的，計(jì)算節(jié)點(diǎn)s的負(fù)載為當(dāng)前需要完成的工作量（指令數(shù)），在分配方案?下，計(jì)算節(jié)點(diǎn)的負(fù)載為：

節(jié)點(diǎn)snds處理當(dāng)前分配方案?所分配的任務(wù)集合task對(duì)應(yīng)的總的工作量為：

節(jié)點(diǎn)sndsrc到節(jié)點(diǎn)snddek的工作路徑為：

假設(shè)Trasij記錄的是jti,j所需的輸入數(shù)據(jù)從源節(jié)點(diǎn)snddasrc傳輸?shù)侥康墓?jié)點(diǎn)snddek的時(shí)間，Bwhdasrc,dek記錄的是snddasrc到snddek的工作路徑的可用剩余帶寬，則Trasij為：

任務(wù)jti,j在snddek上的計(jì)算時(shí)間Cptij,dek為：

任務(wù)jti,j在snddek上總的執(zhí)行時(shí)間Extij,dek為：

節(jié)點(diǎn)snddek能開(kāi)始執(zhí)行jti,j的時(shí)間ATij,dek為：

CTij,dek記錄的是jti,j在snddek上的完成時(shí)間，對(duì)于一個(gè)任務(wù)jti,j，目標(biāo)函數(shù)（9）是用于在集群中找到可用節(jié)點(diǎn)sndq，使得jti,j的完成時(shí)間最早。

而從全局的角度看一個(gè)作業(yè)的完成情況，式（10）是為了優(yōu)化最慢完成的任務(wù)jti,j′的完成時(shí)間，對(duì)應(yīng)的最晚任務(wù)完成時(shí)間即為作業(yè)Jbri的完成時(shí)間：

其中，CTJbri為作業(yè)Jbri的完成時(shí)間，m是作業(yè)Jbri的任務(wù)數(shù)，n是Hadoop集群中的節(jié)點(diǎn)個(gè)數(shù)。

3.1 基于剩余帶寬的RBA算法

基于SDN的Hadoop集群，可以根據(jù)SDN的網(wǎng)絡(luò)控制能力，獲得各個(gè)鏈路實(shí)時(shí)可用的帶寬Bwhrl。當(dāng)任務(wù)jti,j對(duì)應(yīng)的本地節(jié)點(diǎn)sndij,loc最早的可用時(shí)間ATij,loc比當(dāng)前集群中除本地節(jié)點(diǎn)之外的可用節(jié)點(diǎn)sndij,el最早的可用時(shí)間ATij,el更晚時(shí)，則選擇任務(wù)輸入數(shù)據(jù)的所有本地節(jié)點(diǎn)到目的節(jié)點(diǎn)之間的路徑中，可用剩余帶寬（Bwhrl,el）最大的路徑作為最終傳輸任務(wù)輸入數(shù)據(jù)的工作路徑。帶寬Bwhrl,el是任務(wù)調(diào)度時(shí)的重要參數(shù)。若該帶寬可以保證任務(wù)在sndij,el上的完成時(shí)間CTij,el小于在sndij,loc上的完成時(shí)間CTij,loc，則將任務(wù)分配給遠(yuǎn)程節(jié)點(diǎn)sndij,el，否則分配給sndij,loc。這樣不僅充分考慮任務(wù)數(shù)據(jù)的本地性，同時(shí)充分利用網(wǎng)絡(luò)中的最大可用剩余帶寬，從全局的角度進(jìn)行任務(wù)的分配，得到任務(wù)近似最優(yōu)分配，最小化作業(yè)的完成時(shí)間。

因?yàn)閷?shí)際場(chǎng)景中，網(wǎng)絡(luò)中每個(gè)鏈路的剩余可用帶寬是不一定相同的，所以要計(jì)算使用sndij,loc與sndij,el間工作路徑上的實(shí)時(shí)可用帶寬傳輸對(duì)應(yīng)輸入數(shù)據(jù)所需的時(shí)間Trasij,rl，調(diào)度器則將工作路徑上的各個(gè)鏈路的帶寬及Trasij,rl通過(guò)控制器分配給對(duì)應(yīng)的任務(wù)jti,j，確保這條路徑上的鏈路的帶寬在任務(wù)jti,j需要傳輸輸入數(shù)據(jù)時(shí)是可用的。通過(guò)提供最大可用剩余帶寬給任務(wù)進(jìn)行數(shù)據(jù)移動(dòng)，等移動(dòng)結(jié)束后就將帶寬收回，可以達(dá)到充分利用可用帶寬的目的。RBA算法如算法1所示。

算法1基于剩余帶寬的RBA算法

3.2 案例

圖1描述的是一個(gè)引入了SDN的Hadoop集群，由4個(gè)節(jié)點(diǎn)組成，分別為node1、node2、node3、node4（假設(shè)4個(gè)節(jié)點(diǎn)可用空閑時(shí)間分別為2 s、8 s、19 s、6 s），4個(gè)SDN-switch分別為SDN-switch1、SDN-switch2、SDN-switch3、SDN-switch4，1 個(gè)SDN Controller，1 個(gè)Scheduler，其中有7個(gè)鏈路分別為link1,link2,…,link7，當(dāng)前待執(zhí)行的作業(yè)Jbri，有9個(gè)任務(wù)jti,j(j=1,2,…,9)需要分配給節(jié)點(diǎn)執(zhí)行，每個(gè)任務(wù)的輸入數(shù)據(jù)塊在兩個(gè)不同的節(jié)點(diǎn)上有備份（方框里的圓圈表示對(duì)應(yīng)任務(wù)的輸入數(shù)據(jù)副本）。

Fig.1 Topology of SDN-enabled Hadoop圖1 引入SDN的Hadoop集群拓?fù)?/p>

假設(shè)每個(gè)任務(wù)的輸入數(shù)據(jù)塊是64 MB，節(jié)點(diǎn)與交換機(jī)之間鏈路 (link1、link2、link5、link7)的最大帶寬為100Mb/s，剩余交換機(jī)之間鏈路的最大帶寬為500Mb/s(link3、link4、link6)，圖中鏈路上的百分?jǐn)?shù)表示的是某時(shí)刻T對(duì)應(yīng)的鏈路上的可用剩余帶寬比例。假設(shè)4個(gè)節(jié)點(diǎn)的處理能力是一樣的，每個(gè)任務(wù)的工作量大小是一樣的，則可將各個(gè)任務(wù)在對(duì)應(yīng)節(jié)點(diǎn)上的計(jì)算時(shí)間視為相同值Cptcom，為了便于比較計(jì)算結(jié)果，在此設(shè)為Cptcom=10。

根據(jù)算法1的描述，RBA對(duì)作業(yè)Jbri的9個(gè)任務(wù)的分配結(jié)果如表2所示。以任務(wù)jti,1為例，4個(gè)節(jié)點(diǎn)對(duì)于jti,1的初始可用空閑時(shí)間分別為ATi1,1=2 s，ATi1,2=8 s，ATi1,3=19 s，ATi1,4=6 s，而jti,1的本地節(jié)點(diǎn)sndi1,loc為node2或node3，因?yàn)锳Til,2＜ATi1,3，所以選擇sndil,loc=node2，而當(dāng)前除node2和node3之外的最早可用節(jié)點(diǎn)為sndi1,el=node1，且ATi1,1＜ATi1,loc=ATi1,2，所以可以考慮在帶寬允許的條件下將jti,1分配給node1而非sndi1,loc=node2。

Table 2 Execution result of RBA表2 RBA的執(zhí)行結(jié)果

通過(guò)計(jì)算可得jti,1在sndil,loc的完成時(shí)間為CTi1,loc=CTi1,2=8+10=18 s，而在sndi1,el上的完成時(shí)間為CTi1,el=CTi1,1=2+10+64 MB/Trasi1,rl，只要CTi1,loc>CTi1,el，即可計(jì)算出所需的最小傳輸帶寬Trasi1,rl=85.3 Mb/s。而此時(shí)，無(wú)論是從node2還是node3將jti,1的輸入數(shù)據(jù)傳輸給node1，對(duì)應(yīng)工作路徑上的實(shí)時(shí)最小可用剩余帶寬為100%×100 Mb/s=100 Mb/s>Trasi1,rl=85.3 Mb/s，所以可以將jti,1分配給node1，且選擇從node3復(fù)制jti,1所需的輸入數(shù)據(jù)到node1，以減少鏈路的占用。

同時(shí)，根據(jù)鏈路的實(shí)時(shí)可用帶寬計(jì)算傳輸輸入數(shù)據(jù)塊所需的真實(shí)時(shí)間Trasi1,31，并將Trasi1,31分配給對(duì)應(yīng)的任務(wù)jti,1，通過(guò)SDN-controller將Trasi1,31分配給對(duì)應(yīng)路徑上的所有鏈路，以保證jti,1在傳輸數(shù)據(jù)時(shí)，對(duì)應(yīng)鏈路上的網(wǎng)絡(luò)帶寬是可用的。對(duì)于剩下的任務(wù)，RBA以同樣的方式進(jìn)行分配，由表2的結(jié)果可知，jti,9為最慢的任務(wù)，因此其對(duì)應(yīng)的完成時(shí)間即為作業(yè)Jbri的完成時(shí)間，為37.12 s。

HDS是先找到任務(wù)的本地節(jié)點(diǎn)，并把任務(wù)分配給最早可用的本地節(jié)點(diǎn)。若找不到任務(wù)對(duì)應(yīng)的數(shù)據(jù)本地節(jié)點(diǎn)，則將任務(wù)隨機(jī)分配給一個(gè)節(jié)點(diǎn)。以jti,1為例，對(duì)應(yīng)的輸入數(shù)據(jù)副本存放在node2和node3上，ATi1,2＜ATi1,3，因此將jti,1分配給node2，剩下的任務(wù)同樣是以此種方式分配。當(dāng)分配jti,9時(shí)，node4在26.00 s就可用，因此HDS將任務(wù)jti,9作為非本地任務(wù)分配給node4，傳輸時(shí)間為5.12 s，任務(wù)jti,9的完成時(shí)間為41.12 s，即作業(yè)Jbri的完成時(shí)間為41.12 s，相比于RBA，慢了4.00 s，具體的分配結(jié)果如表3所示。

Table 3 Execution result of HDS表3 HDS的執(zhí)行結(jié)果

BAR分成了兩個(gè)階段：第一個(gè)階段，使用和HDS類似的方式，對(duì)任務(wù)進(jìn)行分配，得到的是和HDS一樣的初步分配結(jié)果[8]；第二個(gè)階段，找到第一階段中完成時(shí)間最晚的那個(gè)任務(wù)jti,k，查看是否可能將該任務(wù)jti,k放在哪個(gè)遠(yuǎn)程節(jié)點(diǎn)noderem上執(zhí)行，使得jti,k完成的時(shí)間更早。如果找到這樣的遠(yuǎn)程節(jié)點(diǎn)noderem，則將jti,k分配給該noderem，重復(fù)此步驟，直到找不到這樣的遠(yuǎn)程節(jié)點(diǎn)。如本例中，由第一階段的分配結(jié)果可知，在node4上執(zhí)行的任務(wù)jti,9為最晚完成的任務(wù)，CTi9,4為41.12 s，經(jīng)過(guò)查找可知，jti,9可在node3完成的時(shí)間為39 s，比在node4完成得更早。進(jìn)一步分析，只有node3能讓jti,9完成得更早。最后將jti,9分配給node3，即作業(yè)的完成時(shí)間為39 s，具體分配結(jié)果如表4所示。

Table 4 Execution result of BAR表4 BAR的執(zhí)行結(jié)果

由以上例子可知，相比于HDS、BAR，RBA在縮小作業(yè)完成時(shí)間方面更占優(yōu)勢(shì)。接下來(lái)，通過(guò)仿真實(shí)驗(yàn)進(jìn)一步驗(yàn)證所提方法的有效性。

4 仿真實(shí)驗(yàn)

在此部分，通過(guò)仿真實(shí)驗(yàn)，驗(yàn)證RBA和HDS、BAR、BASS在作業(yè)完成時(shí)間、數(shù)據(jù)本地性、計(jì)算時(shí)間方面的性能差異。

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

在仿真實(shí)驗(yàn)中，數(shù)據(jù)分布是由文獻(xiàn)[9]中的方法生成的。假設(shè)所有的計(jì)算節(jié)點(diǎn)是在同一個(gè)機(jī)架上的。數(shù)據(jù)塊的副本設(shè)置為3，這是Hadoop中默認(rèn)設(shè)置[9]。實(shí)際中，可以通過(guò)文獻(xiàn)[13]提出的方法獲得計(jì)算節(jié)點(diǎn)的初始負(fù)載。而在本文的實(shí)驗(yàn)中，設(shè)置初始負(fù)載為[0,W]的隨機(jī)值[10]，W為集群的負(fù)載，W較小代表集群中大部分的計(jì)算節(jié)點(diǎn)將處于空閑狀態(tài)，W較大表示集群中有部分計(jì)算節(jié)點(diǎn)將暫時(shí)不可用。假設(shè)集群中計(jì)算節(jié)點(diǎn)的處理速度都是Psd，任務(wù)的工作量為(0,jwd]中的一個(gè)隨機(jī)值。

在服務(wù)器節(jié)點(diǎn)上部署Open vSwitch（OVS）[18]即可得到SDN交換機(jī)。在服務(wù)器節(jié)點(diǎn)上部署NOX即可獲得SDN控制器，SDN控制器內(nèi)部有整個(gè)集群的拓?fù)浣Y(jié)構(gòu)，調(diào)用SDN控制器的API即可獲取網(wǎng)絡(luò)各個(gè)鏈路的實(shí)時(shí)可用帶寬信息。本文仿真實(shí)驗(yàn)中，設(shè)置交換機(jī)個(gè)數(shù)為30，隨機(jī)生成一個(gè)滿足要求的集群拓?fù)浣Y(jié)構(gòu)。每個(gè)鏈路的實(shí)時(shí)可用的最大剩余帶寬為(0,E]中的一個(gè)隨機(jī)值，不同的E值表示不同的網(wǎng)絡(luò)狀態(tài)。E為200 Mb/s表示網(wǎng)絡(luò)狀態(tài)較差，E為2 000 Mb/s則表示網(wǎng)絡(luò)狀態(tài)較好。

4.2 實(shí)驗(yàn)和結(jié)果分析

4.2.1 作業(yè)完成時(shí)間的評(píng)估

實(shí)驗(yàn)1為了驗(yàn)證網(wǎng)絡(luò)狀態(tài)的影響，通過(guò)調(diào)整網(wǎng)絡(luò)鏈路的最大帶寬為200、400、600、800、1 000、1 400、1 800、2 000 Mb/s，將以上4種算法進(jìn)行比較。同時(shí)，設(shè)置W為40，說(shuō)明大部分的計(jì)算節(jié)點(diǎn)將快速進(jìn)入可用狀態(tài)。設(shè)置任務(wù)輸入數(shù)據(jù)為300 MB，節(jié)點(diǎn)處理速度Psd為20，jwd為100。實(shí)驗(yàn)分別設(shè)置了30個(gè)計(jì)算節(jié)點(diǎn)，20個(gè)作業(yè)（400個(gè)任務(wù)）；60個(gè)計(jì)算節(jié)點(diǎn)，20個(gè)作業(yè)（400個(gè)任務(wù)）兩種計(jì)算環(huán)境。最后記錄的是作業(yè)平均的完成時(shí)間（RBA_30_400表示30個(gè)節(jié)點(diǎn)，400個(gè)任務(wù)時(shí)，RBA的結(jié)果；RBA_60_400表示60個(gè)節(jié)點(diǎn)，400個(gè)任務(wù)，RBA的結(jié)果。其他表述同理）。

實(shí)驗(yàn)結(jié)果如圖2所示。在兩種計(jì)算環(huán)境中，隨著網(wǎng)絡(luò)中帶寬的增大，4種算法的作業(yè)完成時(shí)間都會(huì)有減少的趨勢(shì)。因?yàn)?種算法都會(huì)將部分任務(wù)分配給遠(yuǎn)程節(jié)點(diǎn)，帶寬的增大，一定程度上可以降低任務(wù)輸入數(shù)據(jù)在傳輸過(guò)程中的時(shí)間。同時(shí)，在網(wǎng)絡(luò)的最大帶寬為200 Mb/s至800 Mb/s之間時(shí)，4種算法對(duì)應(yīng)的作業(yè)的完成時(shí)間減少的趨勢(shì)都較大，當(dāng)最大帶寬大于800 Mb/s時(shí)，4種算法的作業(yè)完成時(shí)間減少的趨勢(shì)會(huì)減緩。這是因?yàn)?，作業(yè)的完成時(shí)間是由任務(wù)的處理時(shí)間和任務(wù)數(shù)據(jù)的傳輸時(shí)間兩部分組成的，當(dāng)帶寬增大到一定程度時(shí)，帶寬對(duì)于傳輸時(shí)間的改善會(huì)趨于穩(wěn)定。

Fig.2 Effect of bandwidth on job completion time圖2 網(wǎng)絡(luò)帶寬對(duì)作業(yè)完成時(shí)間的影響

而HDS并沒(méi)有將帶寬作為任務(wù)分配時(shí)的參數(shù)。BAR是在HDS的分配基礎(chǔ)上，嘗試對(duì)作業(yè)中最晚完成的任務(wù)進(jìn)行調(diào)整，若最晚完成的任務(wù)在其他節(jié)點(diǎn)能提前完成，則對(duì)該任務(wù)進(jìn)行重新分配，以降低作業(yè)的完成時(shí)間。實(shí)質(zhì)上，BAR也是沒(méi)有將帶寬作為任務(wù)分配時(shí)的參數(shù)。對(duì)于RBA而言，是以網(wǎng)絡(luò)中的最大可用剩余帶寬作為任務(wù)分配時(shí)的重要參數(shù)，每次進(jìn)行任務(wù)分配時(shí)，若任務(wù)的最早本地節(jié)點(diǎn)的可用時(shí)間大于遠(yuǎn)程最早可用節(jié)點(diǎn)，網(wǎng)絡(luò)中的最大可用剩余帶寬若能使得任務(wù)在該遠(yuǎn)程最早可用節(jié)點(diǎn)上的完成時(shí)間更早，則將該任務(wù)分配給該遠(yuǎn)程節(jié)點(diǎn)。RBA充分考慮了任務(wù)數(shù)據(jù)本地性，同時(shí)也充分利用網(wǎng)絡(luò)中的最大可用剩余帶寬，將任務(wù)分配給遠(yuǎn)程節(jié)點(diǎn)的方式，減少任務(wù)的等待時(shí)間，從而降低作業(yè)的完成時(shí)間。BASS也是將網(wǎng)絡(luò)帶寬作為任務(wù)分配的參數(shù)，但是在進(jìn)行任務(wù)分配前，需要對(duì)網(wǎng)絡(luò)中的最大帶寬按時(shí)間進(jìn)行分片，相比于RBA這是附加的工作，且RBA充分利用網(wǎng)絡(luò)中的最大可用剩余帶寬較為適用于實(shí)際場(chǎng)景。且從圖2看出，總體上RBA的作業(yè)完成時(shí)間是較優(yōu)于BASS、BAR和HDS的。

4.2.2 數(shù)據(jù)本地性的評(píng)估

實(shí)驗(yàn)2根據(jù)實(shí)驗(yàn)1的不同計(jì)算環(huán)境，4種算法執(zhí)行后，分配給本地節(jié)點(diǎn)的任務(wù)數(shù)占總?cè)蝿?wù)數(shù)的比例有所差異，即檢驗(yàn)4種算法在維持任務(wù)本地性方面的性能差異。各個(gè)節(jié)點(diǎn)對(duì)應(yīng)的本地任務(wù)的數(shù)據(jù)本地率計(jì)算如式（1）所示。結(jié)果如圖3所示。

Fig.3 Effect of bandwidth on DR圖3 網(wǎng)絡(luò)帶寬對(duì)DR的影響

由圖3可得出，在兩種計(jì)算環(huán)境中，隨著網(wǎng)絡(luò)帶寬的增加，4種算法對(duì)應(yīng)的DR值都有所降低，這是因?yàn)閹挼脑黾?，任?wù)輸入數(shù)據(jù)的傳輸時(shí)間會(huì)相對(duì)有所降低，任務(wù)的完成時(shí)間會(huì)降低，節(jié)點(diǎn)對(duì)應(yīng)的可用時(shí)間會(huì)有所降低，則任務(wù)整體的分配情況在不同的帶寬下會(huì)有所變化，對(duì)應(yīng)的DR結(jié)果值也會(huì)有所不同。如帶寬為1 000 Mb/s（1 800 Mb/s）時(shí)，BAR與HDS（60個(gè)節(jié)點(diǎn)，400個(gè)任務(wù)時(shí)）的DR值分別為91.5%、91.4%（91.3%、91.2%），因?yàn)锽AR通過(guò)不斷調(diào)整，可能會(huì)將作業(yè)最晚完成的任務(wù)分配給其對(duì)應(yīng)的本地節(jié)點(diǎn)，降低了作業(yè)的完成時(shí)間，同時(shí)提高了BAR算法執(zhí)行結(jié)果的DR值。圖3中，整體上HDS和BAR比BASS和RBA的DR值高。且BASS和RBA的DR值絕對(duì)值相差為0.4%左右。這是因?yàn)椋珺ASS和RBA都會(huì)在分配任務(wù)時(shí)將帶寬作為重要參數(shù)，不同的是RBA使用的是網(wǎng)絡(luò)中的最大剩余可用帶寬，而B(niǎo)ASS是將帶寬按時(shí)間分片進(jìn)行分配，因此存在鏈路的時(shí)間分片不可用的情況，從而兩者最后的任務(wù)分配情況會(huì)有差異，對(duì)應(yīng)DR值也有所不同，但兩者的作業(yè)完成時(shí)間由圖2可知，RBA的值是較優(yōu)于BASS的。

綜上可得，雖然在任務(wù)數(shù)據(jù)本地性比例上來(lái)說(shuō)，RBA不是最優(yōu)的，但是RBA可以在充分保證任務(wù)數(shù)據(jù)本地性的情況下，充分利用網(wǎng)絡(luò)中的最大可用剩余帶寬，實(shí)現(xiàn)任務(wù)的近似最優(yōu)分配，達(dá)到最小化作業(yè)完成時(shí)間的目的。

4.2.3 計(jì)算時(shí)間的評(píng)估

實(shí)驗(yàn)3主要是驗(yàn)證RBA和HDS、BASS、BAR在計(jì)算時(shí)間方面的性能差異。設(shè)置網(wǎng)絡(luò)中鏈路最大帶寬為1 000 Mb/s，計(jì)算節(jié)點(diǎn)為90，W為800，任務(wù)輸入數(shù)據(jù)為300 MB，節(jié)點(diǎn)處理速度Psd為20，jwd為100。實(shí)驗(yàn)結(jié)果記錄的是執(zhí)行4種算法產(chǎn)生任務(wù)的分配方案所消耗的時(shí)間，取值為10次運(yùn)行時(shí)間的平均值，保證結(jié)果的客觀性。

實(shí)驗(yàn)3的結(jié)果如圖4所示。在計(jì)算時(shí)間方面，4種算法之間的差異總體不是很大，如任務(wù)為3 200個(gè)時(shí)，RBA的計(jì)算時(shí)間為187.913 s，與計(jì)算時(shí)間最少的HDS（為184.957）相差2.956 s。

Fig.4 Computation time圖4 計(jì)算時(shí)間

綜合以上3個(gè)實(shí)驗(yàn)可得，在類似的計(jì)算時(shí)間內(nèi)，使用RBA可以獲得比其他3種算法更好的效果。即RBA總體上較優(yōu)于其他3種算法。

5 結(jié)束語(yǔ)

本文將SDN引入Hadoop，利用SDN的帶寬控制能力，將網(wǎng)絡(luò)中的可用剩余帶寬作為任務(wù)調(diào)度的重要參數(shù)；定義作業(yè)完成時(shí)間問(wèn)題的描述，在充分考慮任務(wù)本地性的情況下，根據(jù)網(wǎng)絡(luò)中的可用剩余帶寬提出任務(wù)調(diào)度算法RBA，因此可獲得任務(wù)的近似最優(yōu)分配方案，實(shí)現(xiàn)作業(yè)完成時(shí)間的最小化。最后通過(guò)仿真對(duì)比實(shí)驗(yàn)，驗(yàn)證了RBA在作業(yè)完成時(shí)間、任務(wù)數(shù)據(jù)本地性及計(jì)算時(shí)間方面的性能?？傮w上RBA是優(yōu)于其他3種算法的。

未來(lái)的一個(gè)工作是考慮Hadoop配置（如reduce個(gè)數(shù)）對(duì)算法的影響，并將RBA運(yùn)用到真實(shí)的Hadoop環(huán)境中，與Hadoop的資源管理器yarn中的capacity調(diào)度器和fair調(diào)度器進(jìn)行比較并改進(jìn)。實(shí)際中，計(jì)算系統(tǒng)會(huì)有出現(xiàn)故障的情況，本文在Hadoop中引入了SDN，同樣可能會(huì)存在鏈路或節(jié)點(diǎn)故障等。因此，在任務(wù)調(diào)度時(shí)進(jìn)行故障容錯(cuò)也是未來(lái)的一個(gè)研究方向。