大數(shù)據(jù)處理集群面向效用最大化的動態(tài)資源分配技術(shù)研究

王松云 李葉飛 陳國琳

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

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

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

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

1 問題描述

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

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

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

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

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

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

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

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

t=當前時間

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

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

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

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

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

3 性能評估

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

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

4 結(jié)語

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

[參考文獻]

[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.