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

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

1 引言

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

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

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

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

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

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

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

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

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

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

2 研究背景

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

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

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

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

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

2.2 問題的提出

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

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

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

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

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

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

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

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

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

3.1 任務(wù)隊列和節(jié)點隊列

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

算法1 任務(wù)隊列和節(jié)點隊列建立算法

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

輸出：任務(wù)隊列和節(jié)點隊列

Begin

1)When a heartbeat of slave node arrives:

2)計算該slave node 上正在運行的tasks的運行速率；

3)根據(jù)任務(wù)運行進(jìn)度 progress和運行速率推測任務(wù)近似結(jié)束時間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ù)隊列、慢節(jié)點隊列和非常慢節(jié)點隊列的基礎(chǔ)上，提出減少慢任務(wù)生成及其處理算法。

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

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

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

Begin

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

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

9)return;

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

11)fortaskiin SlowTaskSet do

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

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

14)end for

15)return;

16)選擇speculativeValue最大的taskj;

17)as sin gntaskj(n)；

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

19)return;

20)else

21)as sin gnNewtask(n);

22)return;

End

下面重點對算法中測試任務(wù)、啟動備份任務(wù)的條件和speculativeValue的計算方法說明如下。

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

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

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

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

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

VerySlowNode節(jié)點只運行測試任務(wù)原因如下。

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

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

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

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

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

①MINIMUM_ALLOWED_SPECULATIVE_TASKS（常量10）

②PROPORTION_TOTAL_TASKS_SPECUL ATABLE（常量0.01）×totalTaskNumber

③PROPORTION_RUNNING_TASKS_SPECU LATABLE（常量0.1）×numberRunningTasks

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

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

speculationValue=estimatedEndTime_estimated ReplacementEndTime

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

estimatedEndTime=estimatedRunTime_task AttemptStartTime

其中，taskAttemptStartTime為該任務(wù)的啟動時間，而estimatedRunTime為推測出來的任務(wù)運行時間，計算方法如下

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

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

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

4 實驗與結(jié)果分析

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

4.1 實驗環(huán)境

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

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

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

4.2 實驗設(shè)置

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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