基于可信任度的任務(wù)調(diào)度策略研究?

邢艷芳 秦 軍

（中國傳媒大學(xué)南廣學(xué)院 南京 211172）

1 引言

隨著信息技術(shù)的快速發(fā)展和普及應(yīng)用，大規(guī)模的數(shù)據(jù)處理需求日益增加，傳統(tǒng)的并行計(jì)算機(jī)難以提供足夠的存儲空間和計(jì)算資源進(jìn)行處理，云計(jì)算技術(shù)為解決海量數(shù)據(jù)處理提供了良好的環(huán)境。Ma?pReduce 是云計(jì)算進(jìn)行海量數(shù)據(jù)處理的分布式計(jì)算模型，它簡化了分布式并行程序的編寫。

MapReduce 并行編程模型改變了大規(guī)模數(shù)據(jù)集的計(jì)算方式，并且在分布式計(jì)算領(lǐng)域發(fā)揮著重要的作用，但是MapReduce編程模型的性能上仍然存在一些問題。MapReduce 編程模型設(shè)計(jì)的目的是用數(shù)量龐大的工作節(jié)點(diǎn)處理海量數(shù)據(jù)，因此這也就要求MapReduce 要能夠快速地處理發(fā)生的機(jī)器故障。在MapReduce 編程模型中，JobTracker 節(jié)點(diǎn)會定期ping 每個TaskTracker 節(jié)點(diǎn)，如果TaskTracker節(jié)點(diǎn)在規(guī)定時間內(nèi)沒有響應(yīng)信息，該節(jié)點(diǎn)就會被標(biāo)記為失效。失效的節(jié)點(diǎn)上完成的所有任務(wù)都將會被設(shè)置為未執(zhí)行狀態(tài)，并被分配在其他TaskTracker節(jié)點(diǎn)上重新執(zhí)行。這種容錯機(jī)制開銷大，效率低，浪費(fèi)了大量資源［1～3］。

在MapReduce 并行編程模型中，系統(tǒng)將Task?Tracker 節(jié)點(diǎn)的失效作為一種常態(tài)，即不需要特殊處理，一般情況只是將失效節(jié)點(diǎn)的任務(wù)調(diào)度到其他節(jié)點(diǎn)上執(zhí)行。由于在失效的節(jié)點(diǎn)上所完成的Map任務(wù)都是存儲在本地磁盤上，因此所有完成的map任務(wù)都要重新執(zhí)行。本文從任務(wù)調(diào)度的角度對MapReduce 的性能進(jìn)行優(yōu)化，提出引入節(jié)點(diǎn)失效恢復(fù)機(jī)制的可靠性任務(wù)調(diào)度策略。對云環(huán)境中的資源節(jié)點(diǎn)進(jìn)行可信任度評估，建立可信任度模型，避免任務(wù)分配到可靠性低的節(jié)點(diǎn)，造成任務(wù)重新調(diào)度執(zhí)行，浪費(fèi)時間和資源［4～6］。

2 可信任度度量指標(biāo)

可信任度是對系統(tǒng)或產(chǎn)品的可靠性評估的參數(shù)。一般來說可靠性是指某一系統(tǒng)或產(chǎn)品是可信任或可信賴的。對某一系統(tǒng)或產(chǎn)品而言，如果能按照用戶要求正常完成任務(wù)，就可以認(rèn)為它是可靠的；但是如果它不能按照用戶的要求持續(xù)工作完成任務(wù)，那么我們就認(rèn)為它是不可靠的。對任一產(chǎn)品而言，其可靠性越高，用戶對其的可信任度就越高。同理可知，產(chǎn)品可靠性越低，用戶對其的可信任度也就越低?？煽啃栽礁叩漠a(chǎn)品可以穩(wěn)定工作的時間就越長。從對可靠性的定義來看，可靠性是指用戶對系統(tǒng)可信賴程度的一種度量，即系統(tǒng)在規(guī)定條件和時間內(nèi)，完成用戶指定的任務(wù)，在任務(wù)運(yùn)行期間不引起系統(tǒng)發(fā)生失效的可能性。從廣義上來說，可靠性是用戶對系統(tǒng)或產(chǎn)品主觀判斷的結(jié)果，也就是用戶對系統(tǒng)或產(chǎn)品的可信任程度。但是為了對可靠性進(jìn)行量化，工業(yè)界對某一產(chǎn)品或系統(tǒng)的可靠性通過其最長無故障連續(xù)工作時間來衡量。工作時間越長，其發(fā)生故障的概率也就越高。

2.1 可信任度

可信任度是指根據(jù)用戶要求，在規(guī)定時間t內(nèi)，系統(tǒng)完成指定任務(wù)的概率，它用一個時間函數(shù)表示：

T 代表發(fā)生故障前的工作時間。不可信任度與可信任度是互補(bǔ)的關(guān)系，不可信任度又稱之為失效概率，失效概率F也是一個時間函數(shù)，即

由上述定義可知，可信任度和不可信任度都是針對一定時間而說的。對同一產(chǎn)品或系統(tǒng)來說，如若工作時間不同，那么產(chǎn)品或系統(tǒng)的可信任度和不可信任的也會不一樣。

2.2 失效率

失效率是指工作到時間t 這一刻，產(chǎn)品或系統(tǒng)還沒有發(fā)生失效，在時間t 時刻以后的下一個單位時間內(nèi)系統(tǒng)發(fā)生失效的概率。失效率是系統(tǒng)或產(chǎn)品進(jìn)行可靠性分析的常用數(shù)量特征，產(chǎn)品或系統(tǒng)發(fā)生失效的概率越高，其可信任度就越低。系統(tǒng)或產(chǎn)品在正常工作的情況下，其失效率慢慢穩(wěn)定時，假設(shè)系統(tǒng)或產(chǎn)品的失效率服從指數(shù)分布，可信任度和失效率的關(guān)系為

3 可信任度模型

定義1：節(jié)點(diǎn)模型［7］。假設(shè)云環(huán)境下的節(jié)點(diǎn)是異構(gòu)的，N 中的每一個節(jié)點(diǎn)Nj性能上都存在差異。本文將要研究的節(jié)點(diǎn)模型刻畫為一個無向圖G（T，E），節(jié)點(diǎn)集合：N=｛N1，N2……，Nm｝，m 為節(jié)點(diǎn)個數(shù)。E 代表圖的邊集合，主要用來表示節(jié)點(diǎn)之間的相互聯(lián)系。對于不同的節(jié)點(diǎn)而言，其計(jì)算能力各有高低；同一個任務(wù)在不同的節(jié)點(diǎn)上的響應(yīng)時間也有所不同。為了記錄任務(wù)在不同節(jié)點(diǎn)上的響應(yīng)時間，我們用一個n*m 的矩陣RT 表示，RTij表示任務(wù)i 在節(jié)點(diǎn)j上的運(yùn)行時間。為了表示節(jié)點(diǎn)之間傳遞的信息量，我們用一個m*m 階的矩陣TI 表示節(jié)點(diǎn)之間的通信量，其中節(jié)點(diǎn)a 和節(jié)點(diǎn)b 之間的通信量表示為TIab。在無向圖G（T，E）中，虛擬機(jī)之間彼此相互獨(dú)立，沒有依賴關(guān)系。

定義2：任務(wù)響應(yīng)時間Tij是指所有任務(wù)都執(zhí)行完成返回結(jié)果所花費(fèi)的時間，主要包括任務(wù)等待時間WTij、任務(wù)傳輸時間CTij和任務(wù)執(zhí)行時間RTij。

定義3：可信任度。本文主要從節(jié)點(diǎn)失效率和失效修復(fù)率兩方面考慮節(jié)點(diǎn)的可信任度。節(jié)點(diǎn)出現(xiàn)故障的情況主要是節(jié)點(diǎn)和節(jié)點(diǎn)之間的通信鏈路以及節(jié)點(diǎn)自身是否發(fā)生故障。失效恢復(fù)分布可恢復(fù)失效和不可恢復(fù)失效，通信鏈路失效是不可恢復(fù)失效。我們定義Ιk表示節(jié)點(diǎn)是否可恢復(fù)，如果是不可恢復(fù)失效那么Ιk為0，否則Ιk為1。

假設(shè)節(jié)點(diǎn)出現(xiàn)故障的概率和節(jié)點(diǎn)之間通信鏈路發(fā)生故障的概率分別服從參數(shù)為σ和ξ的泊松分布，則在時間間隔［0，t］內(nèi)節(jié)點(diǎn)發(fā)生故障p次的概率λp(t)=e-σt/p!，同理可知通信鏈路在時間間隔［0，t］內(nèi)通信鏈路失效p次的概率θp(t)=e-ξt/p!。假設(shè)節(jié)點(diǎn)出現(xiàn)故障可恢復(fù)的概率服從參數(shù)為ε的泊松分布，其中通信鏈路發(fā)生故障時不可恢復(fù)的。假設(shè)節(jié)點(diǎn)在時間間隔［0，t］內(nèi)節(jié)點(diǎn)修復(fù)p 次的概率μp(t)=e-εt/p!。

定義Pj(t)為在時間間隔［0，t］內(nèi)節(jié)點(diǎn)j 上沒有發(fā)生故障（即p=0）的概率，其概率值為

定義Cj(t)為在時間間隔［0，t］內(nèi)節(jié)點(diǎn)a 和節(jié)點(diǎn)b 的通信鏈路上沒有發(fā)生故障（即p=0）的概率，其概率值為

式（7）中TIab/Netab表示節(jié)點(diǎn)之間在通信鏈路上的通信時間。

定義Rj(t)在時間間隔［0，t］內(nèi)節(jié)點(diǎn)j 上沒有發(fā)生修復(fù)（即p=0）的概率，其概率值為

由上述介紹可知，節(jié)點(diǎn)j 完成任務(wù)i 的概率為Kij。

為了提升應(yīng)用程序的并行性，一個作業(yè)往往被分割成多個任務(wù)同時在多個節(jié)點(diǎn)上并行執(zhí)行，一個任務(wù)只在一個節(jié)點(diǎn)上執(zhí)行，當(dāng)所有任務(wù)都返回任務(wù)執(zhí)行結(jié)果，則表明該作業(yè)成功完成。假設(shè)N（j）是執(zhí)行任務(wù)的節(jié)點(diǎn)集合，那么任務(wù)的可靠性可以表示為

以任務(wù)調(diào)度可靠性最大化和任務(wù)總響應(yīng)時間最小化為目標(biāo)的任務(wù)調(diào)度策略是云環(huán)境中常見的任務(wù)調(diào)度模型。要使調(diào)度策略達(dá)到可靠性最高化和任務(wù)總響應(yīng)時間最小化的目標(biāo)，就要將目標(biāo)函數(shù)設(shè)定為

由于任務(wù)總響應(yīng)時間的取值要比可靠性的取值范圍大，因此將x 作為比例因子協(xié)調(diào)可靠性和時間成本所占的比例，防止時間成本控制目標(biāo)函數(shù)值。

4 調(diào)度算法

根據(jù)引入失效恢復(fù)機(jī)制的可信任度模型，對蟻群模擬退火算法進(jìn)行擴(kuò)展，針對云環(huán)境中的任務(wù)調(diào)度問題，將考慮失效恢復(fù)機(jī)制的可信任評估模型引入蟻群模擬退火算法中，提出考慮失效恢復(fù)機(jī)制的蟻群模擬退火算法［8～9］。

ACOSA（Ant Clony Optimization Simulated Ane?alling）算法為啟發(fā)式ACO 和SA 的結(jié)合，其原理是對任務(wù)Ti和節(jié)點(diǎn)Nj，通過ACO找出局部最優(yōu)的任務(wù)調(diào)度解，再利用SA進(jìn)行局部優(yōu)化，從而將任務(wù)分配到合適的異構(gòu)資源節(jié)點(diǎn)上執(zhí)行。其中ACO 在螞蟻尚未進(jìn)行搜索前將初始信息素濃度設(shè)置為一常數(shù)，這樣會加大螞蟻的搜索空間［10～14］。

隨著時間的增加，信息素濃度越來越高，螞蟻就可以根據(jù)上次螞蟻?zhàn)哌^的路徑上信息素的濃度來進(jìn)行選擇合適的路徑。當(dāng)任務(wù)被調(diào)度到資源節(jié)點(diǎn)上執(zhí)行時，可信任度反映了目標(biāo)資源節(jié)點(diǎn)提供服務(wù)的可靠程度。將可信度最大化和時間成本最小化作為目標(biāo)函數(shù)，并將該函數(shù)作為ACO 的啟發(fā)函數(shù)：

引入失效恢復(fù)機(jī)制后，節(jié)點(diǎn)可以通過運(yùn)行失效恢復(fù)程序?qū)νＶ箞?zhí)行的任務(wù)進(jìn)行恢復(fù)。基于可靠性任務(wù)調(diào)度策略的執(zhí)行步驟：

1）初始化參數(shù)。設(shè)置初始溫度Tmax、最大迭代次數(shù)Itermax以及初始信息素τij。

2）構(gòu)造可行解。螞蟻j根據(jù)選擇遷移規(guī)則選擇合適的節(jié)點(diǎn)，將選中的節(jié)點(diǎn)加入禁忌表中，指導(dǎo)所有任務(wù)都分配到合適的節(jié)點(diǎn)資源。

3）對信息素進(jìn)行更新。當(dāng)所有螞蟻都完成路徑搜索時產(chǎn)生局部最優(yōu)解，利用局部最優(yōu)解進(jìn)行局部信息素的更新。

4）SA進(jìn)行局部優(yōu)化。根據(jù)ACO獲得的局部最優(yōu)解，利用SA對局部最優(yōu)解優(yōu)化，得到新解

5）Metropolis 準(zhǔn)則。根據(jù)Metropolis 準(zhǔn)則判斷SA構(gòu)造的新解是否會被接受。

6）終止準(zhǔn)則。對當(dāng)前溫度進(jìn)行降溫，判斷是否滿足終止準(zhǔn)則，若滿足則執(zhí)行7），否則返回至4）。

7）全局信息素更新。根據(jù)SA 產(chǎn)生的候選解對全局信息素更新，迭代次數(shù)加1，若迭代次數(shù)大于Itermax，則終止所有步驟，否則返回至2）。

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

針對引入失效恢復(fù)機(jī)制的可靠性任務(wù)調(diào)度策略的仿真實(shí)驗(yàn)［15～17］，該策略的可靠性主要是由節(jié)點(diǎn)可信任度和通信鏈路的可信任度決定，根據(jù)提出的算法性能和應(yīng)用任務(wù)的大小及通信/計(jì)算比Rcc（Communication to Computation Ratio）有關(guān)，因此任務(wù)類型將由通信/計(jì)算比決定，Rcc＞1 表示任務(wù)為通信密集型，0＜Rcc＜1表示任務(wù)為計(jì)算密集型。

實(shí)驗(yàn)環(huán)境參數(shù)設(shè)置如下：任務(wù)Rcc分別為0.1、1、10；任務(wù)數(shù)為100，節(jié)點(diǎn)數(shù)為20，通信鏈路數(shù)為20。設(shè)置兩種可信任度低的節(jié)點(diǎn)，分別占節(jié)點(diǎn)總數(shù)的20%和30%，兩類節(jié)點(diǎn)執(zhí)行失敗的概率分別為80%和50%。如圖1 和圖2 所示，分別驗(yàn)證失效恢復(fù)機(jī)制的有效性和失效恢復(fù)率對任務(wù)執(zhí)行時間的影響。

圖1 不同失效恢復(fù)率下任務(wù)執(zhí)行成功率（不限制最大恢復(fù)次數(shù)）

圖2 不同失效率對應(yīng)的任務(wù)完成時間

上述實(shí)驗(yàn)證明，引入失效恢復(fù)機(jī)制確實(shí)提高了任務(wù)執(zhí)行成功的概率［18～20］，表明了失效恢復(fù)機(jī)制是有效的，但是在進(jìn)行失效恢復(fù)的過程中也會產(chǎn)生時間和資源開銷，因此要選擇合適的失效恢復(fù)概率。不同任務(wù)數(shù)的情況下，比較任務(wù)執(zhí)行成功率和目標(biāo)函數(shù)值的大小。比較FCFS 算法和ACOSA 算法，其中失效恢復(fù)率uk設(shè)為0.6。

圖3 不同任務(wù)數(shù)對應(yīng)不同的任務(wù)執(zhí)行成功率

圖4 不同任務(wù)對應(yīng)的目標(biāo)函數(shù)值

從圖3 中可知，任務(wù)數(shù)逐漸增加的情況下，F(xiàn)CFS 算法和ACOSA 算法任務(wù)執(zhí)行成功率都在逐漸降低，但是引入失效恢復(fù)機(jī)制的ACOSA 算法的任務(wù)執(zhí)行成功率明顯高于FCFS（First Come First Served）算法。由圖4 可知，引入失效恢復(fù)機(jī)制的ACOSA 算法的任務(wù)完成時間要小于FCFS 算法的任務(wù)完成時間。因此，可以證明引入失效恢復(fù)機(jī)制不僅可以提高任務(wù)的執(zhí)行成功率，而且在選擇了合適的失效恢復(fù)率的情況下，引入失效恢復(fù)機(jī)制的ACOSA算法性能優(yōu)于FCFS算法。

6 結(jié)語

針對云計(jì)算中的任務(wù)調(diào)度問題，提出基于可信任度的任務(wù)調(diào)度策略。通過引入節(jié)點(diǎn)失效恢復(fù)機(jī)制，在分析可信任度度量指標(biāo)的基礎(chǔ)上構(gòu)建可信任度模型，結(jié)合失效恢復(fù)機(jī)制和可信任度模型的調(diào)度策略為任務(wù)的成功執(zhí)行提供了可靠性保證。仿真結(jié)果表明，引入失效恢復(fù)機(jī)制的ACOSA 算法性能優(yōu)于FCFS算法。