王松云 李葉飛 陳國(guó)琳

摘 要：文章引入時(shí)間—效用函數(shù)表述任務(wù)完成時(shí)間與收益的關(guān)系，從而準(zhǔn)確刻畫不同類型大數(shù)據(jù)處理任務(wù)的需求。為最大化系統(tǒng)效用，設(shè)計(jì)了優(yōu)先關(guān)系調(diào)度機(jī)制，確定資源分配。模擬實(shí)驗(yàn)表明，提出的優(yōu)先關(guān)系調(diào)度機(jī)制比公平調(diào)度機(jī)制的效用提升超過50%。

關(guān)鍵詞：大數(shù)據(jù)處理;時(shí)間-效用函數(shù);資源分配

大數(shù)據(jù)處理已被廣泛應(yīng)用于各個(gè)領(lǐng)域，人們已為此開發(fā)多個(gè)框架來加速不同類型的數(shù)據(jù)處理應(yīng)用。由于一個(gè)大數(shù)據(jù)處理集群往往運(yùn)行多個(gè)不同類型數(shù)據(jù)處理任務(wù)，公平資源共享是大部分平臺(tái)所采用的資源配置策略[1]。然而，不同類型任務(wù)對(duì)服務(wù)質(zhì)量的需求是不同的，絕對(duì)公平并不總是終端用戶和服務(wù)提供商的最佳選擇。例如，實(shí)時(shí)數(shù)據(jù)流分析，需要快速完成任務(wù);而綜合決策系統(tǒng)，則主要關(guān)注系統(tǒng)吞吐量。

為了刻畫不同類型任務(wù)對(duì)服務(wù)質(zhì)量的不同要求，本文提出時(shí)間—效用函數(shù)（Time-Utility Function，TUF）[2]，每個(gè)任務(wù)均對(duì)應(yīng)特定TUF，以表述不同完成時(shí)間對(duì)該任務(wù)效用的影響，由此區(qū)分不同類型作業(yè)的服務(wù)質(zhì)量需求。同一類型的作業(yè)TUF走勢(shì)類似，而不同類型作業(yè)會(huì)有較大不同?；诮o定的TUF，集群資源分配的目標(biāo)是使提交的作業(yè)的總收益最大化，從而總體上滿足更多任務(wù)的服務(wù)質(zhì)量要求。此前基于TUF的解決方案主要是針對(duì)具有相同作業(yè)優(yōu)先級(jí)的單個(gè)調(diào)度序列而設(shè)計(jì)的，而實(shí)際在一個(gè)數(shù)據(jù)分析集群中會(huì)有多種任務(wù)，其TUF有顯著區(qū)別。本文針對(duì)這一復(fù)雜任務(wù)調(diào)度問題，提出了一種基于優(yōu)先關(guān)系的在線啟發(fā)式算法來有效地實(shí)現(xiàn)任務(wù)調(diào)度。

1 問題描述

從數(shù)據(jù)處理的角度來看，大數(shù)據(jù)處理作業(yè)可以分為3類，即交互式、流式和批處理式。交互式作業(yè)通常有一個(gè)嚴(yán)格的截止時(shí)間，以保證用戶體驗(yàn)，如果交互式作業(yè)的響應(yīng)時(shí)間超過了截止時(shí)間，則用戶體驗(yàn)會(huì)迅速下降。流式作業(yè)是實(shí)時(shí)作業(yè)，每一個(gè)時(shí)間窗口都有數(shù)據(jù)到達(dá)，若未在當(dāng)前時(shí)間間隔結(jié)束前完成當(dāng)前任務(wù)，可能會(huì)妨礙后續(xù)到來的工作。一般的大數(shù)據(jù)處理作業(yè)是批處理作業(yè)，通常需要相對(duì)長(zhǎng)的時(shí)間（如數(shù)小時(shí)或數(shù)天）來獲得最終結(jié)果，不設(shè)置硬截止時(shí)間。為了能夠體現(xiàn)不同作業(yè)需求，本文設(shè)計(jì)了TUF。效用是指當(dāng)作業(yè)完成時(shí)系統(tǒng)可以獲得的收益或利潤(rùn)，其值Utility根據(jù)作業(yè)完成時(shí)間的不同而發(fā)生變化，是一個(gè)自變量為作業(yè)完成時(shí)間t的函數(shù)值。對(duì)于一個(gè)作業(yè)i，使用ti表示該作業(yè)的完成時(shí)間，該作業(yè)在ti時(shí)刻完成產(chǎn)生的效用是TUFi（ti），其中TUFi（·）表示作業(yè)i的時(shí)間效用函數(shù)。即：

2 基于優(yōu)先關(guān)系的資源調(diào)度算法

我們的目的是得到一個(gè)多處理器的作業(yè)調(diào)度序列使得產(chǎn)生的總效用最大化，但這個(gè)問題是NP-hard問題[3]，因此，我們考慮能否找到一個(gè)具有最優(yōu)解的某些性質(zhì)的解。首先考慮只有一個(gè)處理節(jié)點(diǎn)的簡(jiǎn)單情況，我們將作業(yè)集合劃分為若干子集，使得算法得到的調(diào)度序列最優(yōu)解形式上均為依次調(diào)度T1T2…Tm這m個(gè)子集中的作業(yè)。因此，我們要設(shè)計(jì)一個(gè)產(chǎn)生某個(gè)序列的調(diào)度算法，滿足以下目標(biāo)：（1）算法序列應(yīng)產(chǎn)生接近最佳值的值;（2）如果存在上述劃分，算法序列應(yīng)該與之相兼容。此時(shí)，算法序列在子集層面上與最優(yōu)調(diào)度序列保持一致。

本文將提出一個(gè)實(shí)現(xiàn)了這兩個(gè)目標(biāo)的算法。算法的基本思想是，在每個(gè)選擇步驟中，在所有剩余任務(wù)中選擇在當(dāng)前調(diào)度時(shí)刻是一個(gè)評(píng)估函數(shù)G（t，i）的值最大的任務(wù)。當(dāng)評(píng)估函數(shù)G（t，i）滿足特定條件時(shí)，算法序列也會(huì)有符合需求的特定性質(zhì)。對(duì)于某個(gè)作業(yè)調(diào)度序列，若交換其中某兩個(gè)相鄰作業(yè)i和j的調(diào)度順序后，產(chǎn)生的總效用降低，那么稱i優(yōu)先于j。將在時(shí)刻t作業(yè)i優(yōu)先于的作業(yè)數(shù)記為P（t，i），當(dāng)G（t，i）=P（t，i）時(shí)，算法序列σ將會(huì)是T1T2…Tm的順序，即，算法序列σ將與最優(yōu)分解相一致。

將上面的基于單處理器的算法思想拓展為支持多處理器的算法，即可得到求解原問題的優(yōu)先關(guān)系調(diào)度算法（PR）：

算法：優(yōu)先關(guān)系算法（PR）

While數(shù)據(jù)處理集群正在運(yùn)行do：

if當(dāng)前存在空閑處理器f且當(dāng)前未被處理的作業(yè)的集合Tr不為空集do：

t=當(dāng)前時(shí)間

s為當(dāng)前時(shí)刻使函數(shù)P（t，s）取值最大，即優(yōu)先于的作業(yè)數(shù)最多的作業(yè)

從未被調(diào)度的作業(yè)集合Tr中刪掉作業(yè)s

將選中的作業(yè)s分配給空閑處理器f

if有新作業(yè)jn到達(dá)do：

將新到達(dá)的作業(yè)jn加入未被執(zhí)行的作業(yè)集Tr中

3 性能評(píng)估

使用邏輯回歸任務(wù)對(duì)交互式作業(yè)進(jìn)行仿真，使用wordcount任務(wù)作為流式任務(wù)的仿真，使用pagerank任務(wù)對(duì)批處理任務(wù)進(jìn)行仿真，分別采用本算法PR、先進(jìn)先出算法（First Input First Output，F(xiàn)IFO）和最早截止時(shí)間優(yōu)先算法（Earliest Deadline First，EDF）進(jìn)行調(diào)度，比較仿真實(shí)驗(yàn)的結(jié)果。第一組實(shí)驗(yàn)比較的是這3種算法在不同的工作負(fù)載下的表現(xiàn)，實(shí)驗(yàn)結(jié)果如圖2所示。在不同的工作負(fù)載條件下對(duì)3種算法的表現(xiàn)進(jìn)行對(duì)比，結(jié)果顯示，隨著工作負(fù)載的提高，EDF算法和FIFO算法的性能顯著下降，而PR算法產(chǎn)生的效用明顯高于另外兩個(gè)算法。在高工作負(fù)載下，PR算法產(chǎn)生的總效用比FIFO算法產(chǎn)生的總效用超出50%以上。

在高負(fù)載的工作條件下，大數(shù)據(jù)處理集群理應(yīng)將更多的資源分配給交互式任務(wù)。第二組實(shí)驗(yàn)對(duì)比的是在高工作負(fù)載的條件下，3種算法對(duì)交互式作業(yè)的調(diào)度效果，實(shí)驗(yàn)按照1.4的平均負(fù)載提交交互式作業(yè)，分析比較3種算法在不同時(shí)刻對(duì)作業(yè)的完成率，實(shí)驗(yàn)結(jié)果如圖3所示。該組實(shí)驗(yàn)結(jié)果表明，在3 s內(nèi)，F(xiàn)IFO表現(xiàn)最差，EDF其次，PR表現(xiàn)相對(duì)最佳。3種算法都在大約1.2～2 s的時(shí)間段內(nèi)完成大部分作業(yè)，而由于調(diào)度機(jī)制的原因，F(xiàn)IFO和EDF算法在此階段丟失的作業(yè)更多，在3 s鐘時(shí)，PR算法完成的作業(yè)數(shù)更高。

4 結(jié)語

由于大數(shù)據(jù)處理集群中的多租戶和多框架，具有不同的QoS需求的多個(gè)類型的大數(shù)據(jù)處理任務(wù)同時(shí)運(yùn)行。本文介紹了時(shí)間效用函數(shù)捕捉不同的作業(yè)類型的特征，并認(rèn)為最大化活躍作業(yè)產(chǎn)生的總效用可以提高用戶體驗(yàn)以及系統(tǒng)性能。不幸的是，這個(gè)最大化資源分配問題是NP-hard問題。然后，本文提出了一個(gè)在線啟發(fā)式算法PR來實(shí)現(xiàn)它。PR基于時(shí)間效用函數(shù)，計(jì)算出任務(wù)之間的優(yōu)先關(guān)系，生成的調(diào)度序列接近最優(yōu)調(diào)度序列。仿真結(jié)果表明，我們的機(jī)制比FIFO公平調(diào)度有超出50%的改進(jìn)，在產(chǎn)生較接近最優(yōu)解的同時(shí)保持一定的效率，有效地彌補(bǔ)了現(xiàn)有調(diào)度機(jī)制在不同工作負(fù)載條件下無法靈活調(diào)度的弊端。

[參考文獻(xiàn)]

[1]ZAHARIA M，BORTHAKUR D，SEN S J，et al.Delay scheduling： a simple technique for achieving locality and fairness in cluster scheduling[C].Paris：the 5th European Conference on Computer Systems，2010：265-278.

[2]LI P，WU H，RAVINDRAN B，et al.A utility accrual scheduling algorithm for real-time activities with mutual exclusion resource constraints[J].IEEE Transactions on Computers，2006（4）：454-469.

[3]CLARK R K.Scheduling dependent real-time activities[D].Pittsburgh：Carnegie Mellon University，1990.