大數據處理集群面向效用最大化的動態資源分配技術研究

王松云 李葉飛 陳國琳

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

關鍵詞：大數據處理;時間-效用函數;資源分配

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

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

1 問題描述

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

2 基于優先關系的資源調度算法

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

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

將上面的基于單處理器的算法思想拓展為支持多處理器的算法，即可得到求解原問題的優先關系調度算法（PR）：

算法：優先關系算法（PR）

While數據處理集群正在運行do：

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

t=當前時間

s為當前時刻使函數P（t，s）取值最大，即優先于的作業數最多的作業

從未被調度的作業集合Tr中刪掉作業s

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

if有新作業jn到達do：

將新到達的作業jn加入未被執行的作業集Tr中

3 性能評估

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

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

4 結語

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

[參考文獻]

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