基于節(jié)點(diǎn)識(shí)別的慢任務(wù)調(diào)度算法

崔云飛，李新明，李藝，劉東

（1. 北京航天飛行控制中心，北京 100094；2. 裝備學(xué)院 復(fù)雜電子系統(tǒng)仿真重點(diǎn)實(shí)驗(yàn)室，北京 101416）

1 引言

隨著科學(xué)技術(shù)的快速發(fā)展，科學(xué)研究、互聯(lián)網(wǎng)服務(wù)、電子商務(wù)等多個(gè)領(lǐng)域均出現(xiàn)數(shù)據(jù)量激增的趨勢(shì)，如何對(duì)大數(shù)據(jù)進(jìn)行高效處理成為亟需解決的問題。為了應(yīng)對(duì)大數(shù)據(jù)處理的挑戰(zhàn)，Google 提出了Map-Reduce[1]，Apache Hadoop 對(duì) Map-Reduce實(shí)現(xiàn)了開源，并成為目前最流行的大數(shù)據(jù)處理工具。Map-Reduce目前已有2個(gè)版本：使用最廣泛的MR1和正在測(cè)試的Yarn，它們主要的框架均是設(shè)定系統(tǒng)由主控節(jié)點(diǎn)（Master）和數(shù)據(jù)節(jié)點(diǎn)（Slave）組成。Master負(fù)責(zé)接收用戶請(qǐng)求 job和管理整個(gè)集群的Slave，首先將job拆分成多個(gè)task并根據(jù)Slave的負(fù)載情況分配task；然后對(duì)Slave節(jié)點(diǎn)信息和運(yùn)行task進(jìn)行狀態(tài)監(jiān)控，并根據(jù)設(shè)定的容錯(cuò)調(diào)度策略進(jìn)行動(dòng)態(tài)調(diào)度調(diào)整；最后匯總Slave完成的task信息，給出job處理結(jié)果。

每個(gè)程序員在編程時(shí)都會(huì)問自己2個(gè)問題“如何完成這個(gè)任務(wù)”，以及“如何能讓程序運(yùn)行的更快”。Map-Reduce計(jì)算模型的使用和多次優(yōu)化也是為了更好地解答這2個(gè)問題[2]。其中一個(gè)比較重要的是針對(duì)慢任務(wù)進(jìn)行優(yōu)化。在分布式集群環(huán)境下，因?yàn)槌绦?bug，負(fù)載不均衡或者資源分布不均，造成同一個(gè)job的多個(gè)task運(yùn)行速度不一致，有的task運(yùn)行速度明顯慢于其他task（比如：一個(gè)job的某個(gè)task進(jìn)度只有10%，而其他所有task已經(jīng)運(yùn)行完畢），則這些task拖慢了作業(yè)的整體執(zhí)行進(jìn)度，這種進(jìn)度緩慢從而影響整個(gè)job執(zhí)行速度的task稱為慢任務(wù)。

如何確定真正的慢task，并在合適的節(jié)點(diǎn)上為慢 task啟動(dòng)備份 task成為減少作業(yè)響應(yīng)時(shí)間的關(guān)鍵。集群資源緊缺時(shí)，合理控制備份task的數(shù)量和啟動(dòng)節(jié)點(diǎn)，對(duì)確保在少用資源情況下，減少大作業(yè)響應(yīng)時(shí)間有至關(guān)重要的作用。由于大數(shù)據(jù)處理系統(tǒng)的異構(gòu)性，集群必然存在任務(wù)執(zhí)行效率不同，任務(wù)執(zhí)行時(shí)間不同的情況。應(yīng)該對(duì)當(dāng)前運(yùn)行的task進(jìn)行分析，確定對(duì)大作業(yè)響應(yīng)時(shí)間影響最大的task，即慢task，采取以空間換時(shí)間的思路，為慢task啟動(dòng)備份task，讓備份task與原始task同時(shí)運(yùn)行，哪個(gè)先運(yùn)行完，則使用哪個(gè)結(jié)果，從而減少大作業(yè)的整體響應(yīng)時(shí)間。慢task完成的時(shí)間是整個(gè)作業(yè)運(yùn)行時(shí)間的關(guān)鍵，只有減小慢task完成的時(shí)間，才能減小大作業(yè)完成的總時(shí)間。如何判定慢task，如何選擇合適的節(jié)點(diǎn)啟動(dòng)備份任務(wù)，如何減少慢任務(wù)的產(chǎn)生，是Map-Reduce調(diào)度方式在異構(gòu)環(huán)境中能夠高效運(yùn)行所必須解決的問題[3～6]。

針對(duì)慢任務(wù)問題，經(jīng)典的解決方案[7～10]有Google MapReduce、Hadoop Speculative task、Berkerley的LATE（Longest Approximate Time to End）和Hadoop Yarn Speculative Execution。

Google MapReduce采用以空間換時(shí)間的方式為慢任務(wù)啟動(dòng)多個(gè)備份任務(wù)，一定程度上解決了慢任務(wù)的影響。但存在以下不足：Google是基于同構(gòu)環(huán)境研究的，不能動(dòng)態(tài)識(shí)別異構(gòu)環(huán)境中節(jié)點(diǎn)性能，不能夠選擇最優(yōu)節(jié)點(diǎn)啟動(dòng)任務(wù)拷貝；同時(shí)啟動(dòng)多個(gè)任務(wù)拷貝，對(duì)資源造成浪費(fèi)。

Hadoop Speculative task較Google MapReduce更精準(zhǔn)地定位慢任務(wù)，但仍然沒有解決異構(gòu)的問題，沒有考慮節(jié)點(diǎn)性能，容易造成調(diào)度抖動(dòng)。

Berkerley的LATE建立了節(jié)點(diǎn)隊(duì)列和任務(wù)隊(duì)列來解決慢任務(wù)識(shí)別和節(jié)點(diǎn)識(shí)別的問題，選擇性能優(yōu)異的節(jié)點(diǎn)啟動(dòng)備份任務(wù)。

Hadoop Yarn Speculative Execution提出了備份價(jià)值[11～13]的概念，選擇執(zhí)行備份任務(wù)帶來最大價(jià)值的節(jié)點(diǎn)，比原有算法更精準(zhǔn)地定位哪個(gè)節(jié)點(diǎn)來執(zhí)行備份任務(wù)。

上述4種算法共同的思路均是以空間換時(shí)間，在執(zhí)行能力強(qiáng)、負(fù)載較輕的節(jié)點(diǎn)上對(duì)慢任務(wù)啟動(dòng)備份任務(wù)，4種算法均在處理已經(jīng)存在的慢任務(wù)時(shí)存在一定的缺陷，更重要的是都沒有從根本上解決慢任務(wù)生成的問題，不能夠有效地減少慢任務(wù)的生成。

本文分析上述幾種慢任務(wù)調(diào)度算法存在的問題，提出異構(gòu)環(huán)境中基于節(jié)點(diǎn)識(shí)別的慢任務(wù)調(diào)度算法。該算法通過實(shí)時(shí)調(diào)整運(yùn)行任務(wù)中的慢任務(wù)隊(duì)列和集群節(jié)點(diǎn)中歸一化的慢節(jié)點(diǎn)隊(duì)列，精確識(shí)別慢任務(wù)，在合適的節(jié)點(diǎn)上為慢任務(wù)啟動(dòng)合適的備份任務(wù)，并對(duì)后續(xù)任務(wù)進(jìn)行動(dòng)態(tài)調(diào)度，從根本上減少慢任務(wù)的生成。

2 研究背景

2.1 Hadoop作業(yè)調(diào)度流程及執(zhí)行描述

Apache Hadoop的 MapReduce框架是基于Google MapReduce原理實(shí)現(xiàn)的開源軟件，目前是最流行的大數(shù)據(jù)處理工具。

Hadoop的 MapReduce框架執(zhí)行作業(yè)時(shí)，單個(gè)作業(yè) job被拆分成多個(gè)任務(wù) task執(zhí)行。由JobInProgress監(jiān)控job的執(zhí)行進(jìn)度，TaskInProgress監(jiān)控單個(gè) task的執(zhí)行，task的執(zhí)行采用 task attempt機(jī)制。正常情況下，每個(gè)task啟動(dòng)一個(gè)task attempt；當(dāng)檢測(cè)到任務(wù)執(zhí)行失敗后，控制中心會(huì)為該任務(wù)啟動(dòng)一個(gè)相同的 task attempt；當(dāng) task attempt被判定為慢任務(wù)后，控制中心會(huì)選擇一個(gè)合適的節(jié)點(diǎn)為對(duì)應(yīng)的慢任務(wù)再啟動(dòng)一個(gè) task attempt，稱為備份任務(wù)，這2個(gè)task attempt同時(shí)運(yùn)行，哪個(gè)先執(zhí)行完，就采用哪個(gè)的結(jié)果，并kill掉另一個(gè)task attempt。

圖1 Hadoop MapReduce作業(yè)描述方式

為了降低慢任務(wù)對(duì)作業(yè)整體執(zhí)行效率的影響，Google、Apache Hadoop以及一些研究機(jī)構(gòu)對(duì)此進(jìn)行了一定研究，目前主要的解決思路是：根據(jù)各Slave節(jié)點(diǎn)的負(fù)載情況，將慢任務(wù)調(diào)度到執(zhí)行能力強(qiáng)、負(fù)載較輕的節(jié)點(diǎn)運(yùn)行。關(guān)鍵的技術(shù)點(diǎn)是如何在大量task運(yùn)行環(huán)境中動(dòng)態(tài)判定慢任務(wù)，以及如何選擇合適的節(jié)點(diǎn)啟動(dòng)備份任務(wù)。

2.2 問題的提出

在目前備份任務(wù)的機(jī)制下，由于慢節(jié)點(diǎn)的原因，某種情況下會(huì)出現(xiàn)多節(jié)點(diǎn)執(zhí)行作業(yè)反而慢于較少節(jié)點(diǎn)執(zhí)行同樣作業(yè)。下面以一個(gè)簡(jiǎn)單的例子進(jìn)行說明。

假設(shè)集群中有 slave1、slave2、slave3、slave4共4個(gè)節(jié)點(diǎn)，其中slave4工作效率低。

一共有12個(gè)任務(wù)需要去做，slave1、slave2和slave3執(zhí)行一個(gè)任務(wù)需要1 min，slave4執(zhí)行一個(gè)任務(wù)需要3 min。假設(shè)每個(gè)slave完成自身的任務(wù)才去執(zhí)行備份任務(wù)。

如果讓 slave1、slave2和 slave3去做，則需要4 min，并行執(zhí)行總時(shí)間就是單個(gè)slave的執(zhí)行時(shí)間4 min；然而4臺(tái)同時(shí)去做需要5 min，分析如下。

這里slave1、slave2和slave3都完成了自身的3個(gè)任務(wù)，slave4完成了1個(gè)任務(wù)，還有2個(gè)任務(wù)沒開始執(zhí)行，已經(jīng)花費(fèi)了3 min，剩下最后2個(gè)任務(wù)中的一個(gè)考慮到數(shù)據(jù)的本地性分給了 slave4，另一個(gè)分給slave1。1 min后，slave1上的任務(wù)執(zhí)行完畢，slave4上的任務(wù)仍在執(zhí)行，基于目前的備份任務(wù)機(jī)制，jobtracker會(huì)覺得slave4正在執(zhí)行的任務(wù)為慢任務(wù)，假設(shè)在slave2上執(zhí)行其備份任務(wù)，再經(jīng)過1 min，slave2上的備份任務(wù)執(zhí)行完畢，slave4上的任務(wù)kill掉，最后執(zhí)行時(shí)間是5 min。

上述例子說明使用目前解決慢任務(wù)的備份機(jī)制，執(zhí)行相同的作業(yè)，使用較多的節(jié)點(diǎn)可能會(huì)比使用較少的節(jié)點(diǎn)所需時(shí)間更長(zhǎng)。為了避免此類情況的出現(xiàn)，有必要使用節(jié)點(diǎn)識(shí)別技術(shù)，通過資源的動(dòng)態(tài)調(diào)度，從根本上減少慢任務(wù)的生成，減少作業(yè)的響應(yīng)時(shí)間。

3 基于節(jié)點(diǎn)識(shí)別的慢任務(wù)調(diào)度

本文提出的基于節(jié)點(diǎn)識(shí)別的慢任務(wù)調(diào)度算法，解決2個(gè)問題：根據(jù)任務(wù)執(zhí)行信息，判斷已經(jīng)產(chǎn)生的慢任務(wù)，并為其選擇合適的節(jié)點(diǎn)啟動(dòng)備份任務(wù)；識(shí)別集群中的慢節(jié)點(diǎn)，動(dòng)態(tài)調(diào)整集群的任務(wù)調(diào)度，降低慢任務(wù)生成的概率，從根本上解決慢任務(wù)問題。

基于節(jié)點(diǎn)識(shí)別的慢任務(wù)調(diào)度算法的基本思想是，首先，根據(jù)任務(wù)的執(zhí)行進(jìn)度，建立任務(wù)隊(duì)列，并以此來判斷可能的慢任務(wù)；其次，根據(jù)歸一化的節(jié)點(diǎn)執(zhí)行能力，建立節(jié)點(diǎn)隊(duì)列，并以此來區(qū)分慢節(jié)點(diǎn)和快節(jié)點(diǎn)；然后，當(dāng)一個(gè)節(jié)點(diǎn)空閑時(shí)，根據(jù)節(jié)點(diǎn)隊(duì)列信息、任務(wù)隊(duì)列信息和備份任務(wù)執(zhí)行信息，確定是否為該節(jié)點(diǎn)分配任務(wù)，是否為該節(jié)點(diǎn)分配備份任務(wù)。

3.1 任務(wù)隊(duì)列和節(jié)點(diǎn)隊(duì)列

為了判斷慢任務(wù)，設(shè)計(jì)了任務(wù)隊(duì)列排序算法。使用TaskQueue記錄任務(wù)快慢信息，根據(jù)任務(wù)近似結(jié)束時(shí)間升序排列task；使用NodeQueue記錄集群中各節(jié)點(diǎn)的快慢信息，根據(jù)節(jié)點(diǎn)計(jì)算能力進(jìn)行降序排列slave節(jié)點(diǎn)。

算法1 任務(wù)隊(duì)列和節(jié)點(diǎn)隊(duì)列建立算法

輸入：slave節(jié)點(diǎn)的心跳信息（任務(wù)執(zhí)行進(jìn)度、執(zhí)行時(shí)間）

輸出：任務(wù)隊(duì)列和節(jié)點(diǎn)隊(duì)列

Begin

1)When a heartbeat of slave node arrives:

2)計(jì)算該slave node 上正在運(yùn)行的tasks的運(yùn)行速率；

3)根據(jù)任務(wù)運(yùn)行進(jìn)度 progress和運(yùn)行速率推測(cè)任務(wù)近似結(jié)束時(shí)間AproximateEndTime；

4)sort TaskQueue by AproximateEndTime in descending order;

5)sort NodeQueue by average speed of tasks running on slave nodes in ascending order;

6)define first 25% of TaskQueue as SlowTaskSet;

7)define first 25% of NodeQueue as SlowNodeSet;

8)define first 10% of NodeQueue(and its speed＜averagespeed*0.5)as VerySlowNodeSet;

End

3.2 減少慢任務(wù)生成及其處理算法

在算法1確定慢任務(wù)隊(duì)列、慢節(jié)點(diǎn)隊(duì)列和非常慢節(jié)點(diǎn)隊(duì)列的基礎(chǔ)上，提出減少慢任務(wù)生成及其處理算法。

算法2 減少慢任務(wù)生成及其處理算法

輸入：當(dāng)前到達(dá)的空閑節(jié)點(diǎn)n

輸出：是否向節(jié)點(diǎn)n下發(fā)任務(wù)，是否向其下發(fā)備份任務(wù)

Begin

4)//為非常慢的節(jié)點(diǎn)分配一個(gè)測(cè)試任務(wù)，測(cè)試該節(jié)點(diǎn)的性能，直到該節(jié)點(diǎn)不屬于非常慢的節(jié)點(diǎn)。

8)//根據(jù)系統(tǒng)事先部署的FIFO或Capacity等調(diào)度算法下發(fā)一個(gè)新任務(wù)，避免在慢節(jié)點(diǎn)上啟動(dòng)備份任務(wù)。

9)return;

10)else if 符合啟動(dòng)備份任務(wù)的條件 then

11)fortaskiin SlowTaskSet do

12)compute speculativeValue of taskiif it runs on slave noden;

13)//計(jì)算慢任務(wù)隊(duì)列中所有任務(wù)在noden上備份執(zhí)行的價(jià)值。

14)end for

15)return;

16)選擇speculativeValue最大的taskj;

17)as sin gntaskj(n)；

18)//在noden上為taskj啟動(dòng)備份任務(wù)。

19)return;

20)else

21)as sin gnNewtask(n);

22)return;

End

下面重點(diǎn)對(duì)算法中測(cè)試任務(wù)、啟動(dòng)備份任務(wù)的條件和speculativeValue的計(jì)算方法說明如下。

測(cè)試任務(wù)：在算法2中，被認(rèn)定為特別慢的節(jié)點(diǎn) VerySlowNode，在其空閑時(shí)將不再被分配正常的任務(wù)，而怎樣對(duì)其能力進(jìn)行實(shí)時(shí)監(jiān)測(cè)以及何時(shí)將其重新納入正常節(jié)點(diǎn)的范疇成為必須解決的問題。本文使用測(cè)試任務(wù)對(duì)VerySlowNode進(jìn)行測(cè)試，測(cè)試任務(wù)是一個(gè)隨機(jī)的正常任務(wù)的副本執(zhí)行，其執(zhí)行過程及執(zhí)行結(jié)果均與正常任務(wù)無(wú)關(guān)（規(guī)避測(cè)試任務(wù)對(duì)正常任務(wù)的影響）。使用測(cè)試任務(wù)監(jiān)測(cè)VerySlowNode歸一化的處理能力，一旦監(jiān)測(cè)到該節(jié)點(diǎn)的處理能力達(dá)到集群使用的標(biāo)準(zhǔn)（該節(jié)點(diǎn)的實(shí)時(shí)能力大于VerySlowNode的判定值），將該節(jié)點(diǎn)從VerySlowNodeSet中釋放。

VerySlowNodeSet中某個(gè)節(jié)點(diǎn)只要滿足以下 2個(gè)條件中的任意一個(gè)，那么就將節(jié)點(diǎn)重新納入正常節(jié)點(diǎn)范疇，并讓其正常執(zhí)行任務(wù)。

1)該節(jié)點(diǎn)歸一化的執(zhí)行能力大于所有節(jié)點(diǎn)隊(duì)列NodeQueue中最慢的10%的節(jié)點(diǎn)的執(zhí)行能力。

2)該節(jié)點(diǎn)歸一化的執(zhí)行能力大于所有節(jié)點(diǎn)平均執(zhí)行能力的50%。

說明：第一個(gè)條件是確認(rèn)節(jié)點(diǎn)執(zhí)行性能不屬于最差范疇；第二個(gè)條件避免把性能還不錯(cuò)的節(jié)點(diǎn)劃入VerySlowNodeSet節(jié)點(diǎn)范疇，避免造成資源使用的浪費(fèi)。

VerySlowNode節(jié)點(diǎn)只運(yùn)行測(cè)試任務(wù)原因如下。

1)目前，以Hadoop為代表的大數(shù)據(jù)處理體系，采取了一種粗放的方式處理海量的數(shù)據(jù)，機(jī)器學(xué)習(xí)的原理很多時(shí)候也是依靠大量的樣本而不是精確的邏輯。想要用好大數(shù)據(jù)，需要通過技術(shù)手段快速高效地分析整理海量的樣本，需要盡量用簡(jiǎn)單的方式去處理大量的數(shù)據(jù)，避免復(fù)雜的處理方式帶來不必要的開銷。因此，本文在對(duì)慢任務(wù)調(diào)度進(jìn)行優(yōu)化的過程中，盡量避免復(fù)雜化大數(shù)據(jù)處理主流程。VerySlowNode節(jié)點(diǎn)變慢的原因可能會(huì)有很多種（如磁盤故障、內(nèi)存溢出、程序bug、負(fù)載不均衡等），在處理過程中分析節(jié)點(diǎn)變慢的原因并進(jìn)行修復(fù)，會(huì)影響大數(shù)據(jù)處理主流程的效率。本文采用簡(jiǎn)單的方式處理非常慢的節(jié)點(diǎn)（不再分發(fā)任務(wù)），最大可能減少慢任務(wù)的產(chǎn)生，減少處理方式本身對(duì)大數(shù)據(jù)處理主流程的影響；在VerySlowNode節(jié)點(diǎn)上運(yùn)行測(cè)試任務(wù)，當(dāng)檢測(cè)到該節(jié)點(diǎn)歸一化后的執(zhí)行能力達(dá)到閾值時(shí)，將其納入正常節(jié)點(diǎn)范疇，并讓其正常執(zhí)行任務(wù)。

2)VerySlowNode節(jié)點(diǎn)只運(yùn)行測(cè)試任務(wù)會(huì)造成資源使用的浪費(fèi)，但能夠減少慢任務(wù)的產(chǎn)生。避免資源的浪費(fèi)和減少慢任務(wù)的產(chǎn)生是一對(duì)矛盾體。在2.2節(jié)（問題的提出部分）對(duì)資源使用個(gè)數(shù)和作業(yè)響應(yīng)時(shí)間之間的可能關(guān)系進(jìn)行了說明。為了避免資源浪費(fèi)，而在非常慢的節(jié)點(diǎn)上正常執(zhí)行任務(wù)，產(chǎn)生慢任務(wù)的可能性會(huì)很大，反而會(huì)降低作業(yè)的整體執(zhí)行效率。因此，本文不向“真正的慢節(jié)點(diǎn)”分發(fā)正常任務(wù)，減少慢任務(wù)的產(chǎn)生；同時(shí)，使用慢節(jié)點(diǎn)判定條件2)減少誤判慢節(jié)點(diǎn)的概率，盡量避免資源浪費(fèi)。

啟動(dòng)備份任務(wù)的條件如下。

1)還沒有為慢任務(wù)taskj啟動(dòng)備份任務(wù)。

2)整個(gè)作業(yè)job的備份任務(wù)數(shù)目小于其上限，該數(shù)目是以下3個(gè)數(shù)值的最大值：

①M(fèi)INIMUM_ALLOWED_SPECULATIVE_TASKS（常量10）

②PROPORTION_TOTAL_TASKS_SPECUL ATABLE（常量0.01）×totalTaskNumber

③PROPORTION_RUNNING_TASKS_SPECU LATABLE（常量0.1）×numberRunningTasks

3)在目前的空閑節(jié)點(diǎn)上為慢任務(wù) taskj啟動(dòng)備份任務(wù)的價(jià)值speculativeValue比其他task啟動(dòng)備份任務(wù)的價(jià)值大。

speculativeValue的計(jì)算方法：借鑒hadoop- 0.23系列中speculationValue的計(jì)算方法。

speculationValue=estimatedEndTime_estimated ReplacementEndTime

其中，estimatedEndTime是通過預(yù)測(cè)算法推測(cè)的該任務(wù)的最終完成時(shí)刻，計(jì)算方法為

estimatedEndTime=estimatedRunTime_task AttemptStartTime

其中，taskAttemptStartTime為該任務(wù)的啟動(dòng)時(shí)間，而estimatedRunTime為推測(cè)出來的任務(wù)運(yùn)行時(shí)間，計(jì)算方法如下

estimatedEndTime=(timestamp_start)/Math.max(0.0001,progress)

其中，timestamp為當(dāng)前時(shí)刻，而start為任務(wù)開始運(yùn)行時(shí)間，timestamp_start表示已經(jīng)運(yùn)行時(shí)間，progress為任務(wù)運(yùn)行進(jìn)度（0～1.0）。

estimatedReplacementEndTime含義為：如果此刻啟動(dòng)該任務(wù)，（可推測(cè)出來的）任務(wù)最終可能的完成時(shí)刻。

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

為了分析文中提出的基于節(jié)點(diǎn)識(shí)別的慢任務(wù)調(diào)度算法（TQST）的性能，下面將 TQST算法和Berkeley LATE算法、Hadoop Yarn Speculatve Execution算法進(jìn)行比較?；贖adoop開發(fā)了Adaptive Capacity Scheduler模塊。通過在異構(gòu)集群的實(shí)驗(yàn)，分析算法的性能。

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

本節(jié)主要描述實(shí)驗(yàn)的環(huán)境，以及環(huán)境的各個(gè)參數(shù)。使用實(shí)驗(yàn)室的10臺(tái)PC機(jī)進(jìn)行實(shí)驗(yàn)集群的搭建，各PC機(jī)采用1000 Mbit/s的局域網(wǎng)互聯(lián)。這10臺(tái)PC機(jī)是異構(gòu)的，如表1所示。

表1 實(shí)驗(yàn)用集群環(huán)境配置

原型系統(tǒng)基于 Hadoop-0.23.5開發(fā)，Master模塊部署于管理節(jié)點(diǎn)，Slave模塊部署于 9個(gè)計(jì)算節(jié)點(diǎn)，1000 Mbit/s以太網(wǎng)作為數(shù)據(jù)傳輸網(wǎng)絡(luò)。輸入文件由Hadoop分布式文件系統(tǒng)管理，文件塊存儲(chǔ)于計(jì)算節(jié)點(diǎn)的本地硬盤，每個(gè)文件塊的大小為100 KB至 64 MB（用于測(cè)試處理不同大小數(shù)據(jù)塊時(shí)的效率），并且有2個(gè)副本。每一個(gè)MapReduce job作為一個(gè)作業(yè)，而一個(gè)作業(yè)中的Map Task作為任務(wù)。實(shí)驗(yàn)利用Hadoop自帶的Capacity Scheduler模塊實(shí)現(xiàn) Hadoop Yarn Speculatve Execution算法，利用Adaptive Capacity Scheduler模塊實(shí)現(xiàn) Berkeley LATE算法和TQST算法。

4.2 實(shí)驗(yàn)設(shè)置

為了比較調(diào)度算法對(duì)不同規(guī)模作業(yè)的影響，實(shí)驗(yàn)依照單個(gè)task處理的數(shù)據(jù)量分成5組，分別為100 kB、1 MB、10 MB、32 MB和64 MB。每組測(cè)試的任務(wù)數(shù)均取20個(gè)任務(wù)、100個(gè)任務(wù)和500個(gè)任務(wù)。具體設(shè)置如表2所示。

表2 作業(yè)參數(shù)設(shè)置

通過提交不同大小的作業(yè)，主要考察2個(gè)指標(biāo)：備份任務(wù)執(zhí)行數(shù)量，主要反映慢任務(wù)生成個(gè)數(shù)；算法完成作業(yè)的響應(yīng)時(shí)間。

4.3 慢任務(wù)生成個(gè)數(shù)分析

在使用不同算法的實(shí)驗(yàn)中，采用相同的慢任務(wù)判斷標(biāo)準(zhǔn)：任務(wù)執(zhí)行效率為最慢的20%的任務(wù)，并且小于作業(yè)中所有任務(wù)平均執(zhí)行效率的 50%。TQST算法和Berkeley LATE算法、Hadoop Yarn Speculatve Execution算法執(zhí)行完作業(yè)過程中共啟動(dòng)的備份任務(wù)數(shù)量對(duì)比如圖2～圖4所示。

圖2 備份任務(wù)數(shù)量對(duì)比（20任務(wù)）

圖3 備份任務(wù)數(shù)量對(duì)比（100任務(wù)）

圖4 備份任務(wù)數(shù)量對(duì)比（500任務(wù)）

從上述比較中可以直觀看出，原來的慢任務(wù)調(diào)度算法 Berkeley LATE算法和 Hadoop Yarn Speculatve Execution算法沒有采取異構(gòu)環(huán)境中減少慢任務(wù)產(chǎn)生的機(jī)制，會(huì)產(chǎn)生較多的慢任務(wù)，同時(shí)會(huì)啟動(dòng)較多的備份任務(wù)；而本文提出的TQST算法，采取基于節(jié)點(diǎn)識(shí)別的調(diào)度算法，避免向非常慢的節(jié)點(diǎn)調(diào)度新任務(wù)，從而減少慢任務(wù)的產(chǎn)生，大幅度降低了慢任務(wù)的產(chǎn)生。同時(shí)，從上述幾個(gè)圖中可以看出，隨著單個(gè)任務(wù)處理數(shù)據(jù)量的增加，備份任務(wù)執(zhí)行的數(shù)量變多，原因是單個(gè)任務(wù)的執(zhí)行時(shí)間增大，更容易達(dá)到識(shí)別慢任務(wù)的時(shí)間限制。

4.4 作業(yè)響應(yīng)時(shí)間分析

作業(yè)響應(yīng)時(shí)間如圖5～圖7所示。

圖5 作業(yè)響應(yīng)時(shí)間（20任務(wù)）

圖6 作業(yè)響應(yīng)時(shí)間（100任務(wù)）

圖7 作業(yè)響應(yīng)時(shí)間（500任務(wù)）

從上述比較中可以直觀地看出，Hadoop Yarn Speculatve Execution算法由于采用備份價(jià)值最大的啟動(dòng)機(jī)制，能夠更準(zhǔn)確地為慢任務(wù)啟動(dòng)備份任務(wù)，從而比Berkeley LATE算法減少了作業(yè)響應(yīng)時(shí)間。本文提出的TQST算法，采用基于節(jié)點(diǎn)識(shí)別的慢任務(wù)調(diào)度算法，不為非常慢的節(jié)點(diǎn)調(diào)度新任務(wù)，雖然部分慢節(jié)點(diǎn)不能正常參加集群工作，但是減少了慢任務(wù)的產(chǎn)生，從而最大可能降低了慢任務(wù)對(duì)作業(yè)響應(yīng)時(shí)間的影響，明顯提高了作業(yè)效應(yīng)效率。

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

本文提出了一種基于節(jié)點(diǎn)識(shí)別的慢任務(wù)備份執(zhí)行和減少慢任務(wù)產(chǎn)生的調(diào)度算法。該算法與已有慢任務(wù)處理算法的不同在于非常慢節(jié)點(diǎn)不再執(zhí)行新任務(wù)。根據(jù)備份任務(wù)啟動(dòng)價(jià)值，為慢任務(wù)啟動(dòng)價(jià)值最大的備份任務(wù)，解決已經(jīng)產(chǎn)生的慢任務(wù)；在確保集群資源利用率的前提下，規(guī)避非常慢的節(jié)點(diǎn)，從根本上減少慢任務(wù)的產(chǎn)生。該算法能顯著降低慢任務(wù)的數(shù)量，提高作業(yè)的響應(yīng)效率。最后的實(shí)驗(yàn)結(jié)果證明了TQST算法的正確性和合理性。

[1]DEAN J,GHEMAWAT S. MapReduce: simplified data processingon large clu8ters [J].Communications of the ACM,2008,51(1): 107-113.

[2]陸嘉恒. Hadoop實(shí)戰(zhàn)[M]. 北京：機(jī)械工業(yè)出版社,2012.LU J H. Hadoop actual combat[M]. Beijing: China Machine Press,2012.

[3]Adaptive scheduler[EB/OL]. https://issues.apache.org/jira/browse/MAPREDUCE-1380,2013.

[4]Improve speculative execution[EB/OL]. https://issues.apache.org/ jira/browse/MAPREDUCE-2039,2013.

[5]Speculative execution is too aggressive under certain conditions[EB/OL].https://issues.apache.org/jira/browse/MAPREDUCE- 2062,2013.

[6]Speculative execution algorithm in 1.0 is too pessimistic in many cases[EB/OL]. https://issues.apache.org/jira/browse/MAPREDUCE-3895,2013.

[7]FLORIN D T. S. Eugene ngunderstanding the effects and implications of compute node related failures in hadoopHPDC’12[A]. The Netherlands ACM[C]. 2012.187-197.

[8]段翰聰,李俊杰,陳宬等. 異構(gòu)環(huán)境下降低任務(wù)抖動(dòng)的調(diào)度法——DPST[J]. 計(jì)算機(jī)應(yīng)用,2012,32(7): 1910 -1912,1938 DUAN H C,LI J J,CHEN C,et al. DPST: a scheduling algorithm of preventing slow task trashing in heterogenous environment [J]. Journal of Computer Applications,2012,32(7): 1910 -1912,1938.

[9]LEE K H,LEE Y J,CHOI H,et al.Parallel data processing with MapReduce: a survey[J]. SIGMOD Record,2011,40(4):11-20.

[10]MATEI Z,ANDY K,ANTHONY D. Improving MapReduce performance in heterogeneous environments[A]. 8th Usenix Symposium on Operating Systems Design and Implementation[C]. 2008.29-42.

[11]Resource manager rest[EB/OL].www.hadoop.apace.org/docs/r0.23.6,2013

[12]Speculative execution for reads[EB/OL]. https://issues.apache.org/jira/browse/CASSANSRA-4705,2013.

[13]Looking for speculative tasks is very expensive[EB/OL]. https://issues.apache.org/ jira/browse/MAPREDUCE -4499,2013.