Hadoop集群中給定候選任務集的最大利潤問題

鄭 羽，胡積寶

(1.安慶師范大學 現代教育技術中心，安徽 安慶 2460112.安慶師范大學 物理與電氣工程學院，安徽 安慶 246133)

0 引 言

隨著計算機網絡和傳感器網絡的迅速發展，數據呈指數級增長，特別是在因特網上。為了有效地處理大規模數據，需要具有良好的可伸縮性、靈活性和容錯性的并行分布式集群。由Google提出的MapReduce[1]架構，應用分而治之的方法來處理數據密集型任務，是大數據領域一個既成事實的標準。Google使用了一個運行MapReduce和相關技術的大型集群，諸如GFS[2]和Bigtable[3]，每周處理PB級數據以上。在這種服務過程中，企業與客戶之間的服務細節通常是通過服務水平協議來(SLA)[4-5]描述的。SLA分兩種，根據數量定價和根據有效性定價。根據數量定價的SLA向客戶收取與硬件規模和服務時間成比例的費用。根據有效性定價的SLA依據服務效能向客戶收費。以垃圾郵件檢測服務為例，該服務必須在一定時間內完成，因此，只有服務在規定時間內完成，才會支付款項。文中研究了如何安排客戶的任務以使得Hadoop集群的總利潤最大化。在研究中，主要關注的是定時MapReduce任務，它是以時間的有效性為代價的，即任務必須在給定的時間內完成。在這里將每個任務抽象為四個部分，即用戶定義的Map/Reduce函數、完成時間、利潤和懲罰，并試圖找到一種最大化Hadoop集群總利潤的調度算法。

1 相關知識

1.1 MapReduce環境

MapReduce是一種流行的面向數據密集型任務的編程模型，在許多領域得到了廣泛應用[6-8]。Hadoop是一個由Apache基金會所開發的分布式系統基礎架構。用戶可以在不了解分布式底層細節的情況下，開發分布式程序。充分利用集群的優勢進行高速運算和存儲。Hadoop實現了一個分布式文件系統(Hadoop distributed file system，HDFS)。HDFS有高容錯性的特點，并且可以部署在低廉的(low-cost)硬件上；而且它提供高吞吐量來訪問應用程序的數據，適合那些有著超大數據集的應用程序。

圖1為MapReduce框架，在用戶定義的map函數中，輸入是一個鍵值對，輸出是零或多個鍵值對。在組步驟中，具有相同密鑰的系統組鍵值對會被發送到相同的還原節點。在自定義的Reduce函數中，組合鍵值對處理產生的結果。MapReduce任務通常需要多次Map/Reduce迭代。

圖1 MapReduce框架

1.2 相關工作

在MapReduce，有一些通用的任務調度程序，如FIFO調度器、基于容量的調度器和基于公平的調度器。在具體應用中，Sandholm和Lai等提出了一種調度算法，允許用戶根據MapReduce任務的重要性動態調整需要的計算資源。Zaharia等提出了一種異構集群環境下的調度算法。Kwon等提出了skewtune算法處理MapReduce任務的過程偏度。此外，還有一些調度算法，涉及到在給定時間內完成的MapReduce任務[9-15]。

1.3 存在的問題

文中研究的目的是最大限度地提高同類的Hadoop集群的總利潤，其中所有節點的計算能力是相同的。在一個Hadoop集群中，有M個Map任務，M個Reduce任務，對于每個提交的任務j，假設以下參數：

j.Nm：j中的Map作業數。

j.Nr，j中的Reduce作業數；為了獲得高效率，j.Nm和j.Nr是M的整數倍。

j.deadline，j所規定的時間或期限。

j.profit，j在截止時間前完成所獲得的利潤。

這里必須注意，如果j沒有在截止時間之前完成，那么j的懲罰是j.profit.α。當許多客戶同時向Hadoop集群提交任務時，這些任務形成一個候選任務集J={j1,j2,…,j|J|}。Hadoop集群需要從J中選擇一個可接受的任務集J={j1,j2,…,j|J|}，通過適當的算法調度選定的任務以完成它們。對每一個任務ji∈A，如果ji比jideadline完成得早，則ji是有效的，利潤是ji.profit；反之，如果ji沒有在jideadline前完成，那么ji不是有效的，懲罰是j.profit.α，也就是說，利潤是-j.profit.α。因此，Hadoop集群的總利潤是：

(1)

其中，E()表示給定的任務是否有效。

1.4 調度算法

在這一部分中，首先提出了一種基于序列的任務調度策略，然后提出了一種基于該策略的調度算法，最后給出了一種處理超時的方法。

1.4.1 基于序列的調度策略

對每一個任務j∈J，可以估計Map任務j.Tm的處理時間和Reduce任務j.Tr的處理時間。如果所有任務槽都用于處理任務j，完成所有Map任務的時間是TCm(j)=「j.Nm/M?×j.Tm，完成所有Reduce任務的時間是TCr(j)=「j.Nr/M?×j.Tr。

定義1：序列對于任務集JS(任務數是|JS|)，序列S是|JS|中所有任務的排列，并根據完成時間指定作業的順序。如果在Map步驟中完成j的時間是COTm(j)，那對于給定的序列S={j1,j2,…,j|JS|}，COTm(j)

基于給定的序列S，提出了如下的調度策略：

(1)Map當空閑任務槽需要一個Map作業時，按順序選擇第一個任務的映射作業。當分配S中第一個任務的所有Map作業時，從S中刪除第一個任務。

根據以上的調度策略，對于一個給定序列，可以計算出Map步驟的完成時間COTm(j)和Reduce步驟的完成時間COTr(j)。COTm(j)和COTr(j)的計算如下：

基于上述調度策略和完工時間的計算，給出了有效序列的定義。

定義2：對任意序列S給定任務集JS，基于上述調度策略，有COTr(j)≤j.deadline，則S是一個有效的序列。

定理1：對于任務集JS和序列S，擬議的調度策略可以確保，對?ji∈JS，在S的約束下，ji可以用最少的時間完成Map步驟。

定理2：對于任務集JS和序列S，如果使用建議的調度策略時發生任務超時，則使用任何調度策略，不可能按時完成JS中的所有任務，因此，S必須不是有效的序列。

證明：從定理1知道，提出的調度策略在Map步驟中是最優的。這里，只考慮Reduce步驟。假設j是基于調度策略的超時任務，可以分為兩種情況：

(1)COTm(j)+TCr(j)>j，如果j的Reduce步驟在它的Map作業完成時立即運行，但仍不能按時完成，那么無論采用什么調度策略，j都不能按時完成。

在上述兩種情況下，都不可能按時完成JS中的所有任務，因此S必須不是有效的序列。基于定理1和定理2，可以得出結論，所提出的調度策略對于固定序列S是最優的。這意味著如果在提議的策略下存在超時任務，那么它們必須存在于任何其他調度策略中。

1.4.2 調度算法

在提出的基于序列的調度策略的基礎上，文中提出了一種調度算法。首先，當候選任務設置是靜態的，使用的評分策略為所有任務指定優先級，將找到可接受的任務并為其設定一個有效的修剪策略，并發現一個有效的序列。其次，當候選的任務集實現了動態更新，會執行增量法判斷可接受的任務集和更新有效序列是否必要。

為了提高判斷可接受集的效率，首先對j中的所有任務進行排序，然后確定每個任務的優先級。根據MapReduce任務的特點，主要考慮以下兩個方面：

(2)在MapReduce中，如果某個任務j的運行時間太長，那么當運行j的Map/Reduce任務時，大多數任務槽將是空閑的。這樣會浪費大量資源，影響其他任務的接受。

在此基礎上，提出了一種以總利潤最大化為目標的評分函數。對任務J而言，得分是：

(2)

其中，Ad(j)為J的調整系數，STC(j).Ad(j)為J的調整時間。從式2可以看出，得分高的任務將獲得更高的優先級。

現在，分析了如何提高查找有效序列的效率。假設候選集通過式2的計算進行了排序，即窮舉搜索法需要(|A|+1)!遍歷所有候選序列的復雜性。為了提高搜索速度，給出了以下兩種方法。

定理3：給定一個任務集A和它的一個序列J={j1,j2,…,j|J|}，對于一個新的任務jnew，有n+1個位置可以插入它，如果TCm(jnew)+COTm(ji)+TCr(ji)>ji.deadline，那么jnew就不能被插入到[1,i]中的位置。

證明：很明顯，如果jnew被插入到[1,i]中的任意位置，jnew就會超時。

定理4：給定一個任務集A和它的一個序列S={j1,j2,…,jn}，對于一個新任務jnew，如果TCm(jnew)+COTm(ji)+TCr(jnew)>ji.deadline，那么jnew就不能被插入到[i+1,n+1]中的任意位置。

證明：假設jnew被插入到[i+1,n+1]中的任意位置，根據提出的調度策略，得出jnew最早完成時間等于或者大于TCm(jnew)+COTm(ji)+TCr(jnew)。因此，jnew肯定會超時。

基于定理3和定理4，提出了一種快速找到可接受集及其相應有效序列的算法，其細節在算法1中。利用該算法，可以得到候選任務集的最大利潤。

算法1：

輸入：提交工作集J={j1,j2,…,j|J|}

輸出：接收的工作集A及其有效的序列φ

用式2為每個工作計算出得分并排名

將J中的工作按照得分降序排序

假設A←{j1}，φ←{{j1}}

For每個ji∈Jandi≠1 do

假設φi←{} for 每個S∈φi-1do

判斷jj能被插入的最小位置a

通過定理3

Ifa≤bthen

For每個p∈[a,b] do

在位置p將jj插入S并得到S'

計算所有工作需要的完成時間

IfS'符合SEQ策略

IfS'是一個有效的序列 then

使φi←φi∪S'

Ifφ≠φthen

使A←A∪ji

返回A和φ|J|中的有效序列

2 實 驗

2.1 實驗設置

在實驗中，Hadoop集群包含一個主節點和40個從節點，每個節點包含一個英特爾酷睿i3 3.1 GHz處理器，8 GB的內存和500 GB的存儲，運行的操作系統是RedHat Linux 6.1。在從節點中，每個節點配置兩個Map任務槽和兩個Reduce任務槽。實驗中的數據是enwiki(https://dumps.wikimedia.org/enwiki/20150204/)，運行了三個經典任務的數據集，即統計詞頻、倒排索引、分布式grep。數據存儲在Hadoop文件系統(HDFS)中，每一塊是64 MB，每個數據塊有三份拷貝。對于一個候選任務集j，主要考慮以下三個影響性能的參數：

(1)平均任務尺寸L，即L中所有任務的平均尺寸(塊數)；

(2)任務數N，即L中任務的數量；

(3)平均期限D，即L中所有任務的平均期限(完成時間)。

總利潤的計算見式1。此外，定義接收率和完成率如下：

(3)

(4)

2.2 實驗結果

實驗中使用的基線算法是DC和WC。首先評估了任務數對總利潤的影響，結果如圖2所示。在圖2(a)中，理想曲線是理想的利潤，隨著平均任務規模的增加，所有利潤值都減少，但此方法接近理想值。在圖2(b)中，所畫的三個接收率逐漸降低，但此方法具有最高的價值，意味著該方法可以獲得最多的候選任務。在圖2(c)中，提出的方法比另外兩種方法有更高的完成率。

圖2 任務數對總利潤的影響

由于該方法不僅接收到最多的候選任務，而且完成大部分任務，因此可以帶來最大的利潤。

同時，觀察了任務數和平均截止期對總利潤的影響，結果如圖3所示。

圖3 任務數的影響

由于同樣的原因，方法不僅接收到最多的候選任務，而且完成大部分任務，因此可以帶來最大的利潤。此外，對三種情況的總利潤非常接近理想值。

最后，動態地將任務提交給Hadoop集群，觀察總利潤的變化。從數據可以看出，該方法不僅接收到最多的候選任務，而且完成大部分任務，因此可以帶來最大的利潤。這說明所提出的方法也適用于動態提交的任務。

3 結束語

研究了Hadoop集群中的最大利潤問題。為了使利潤最大化，基于候選任務集的有效序列選擇了一些高利潤率的任務。此外，為了提高查找有效序列的效率，設計了一些修剪策略，并給出了相應的調度算法。實驗結果表明，該算法的總收益非常接近理想的最大值，在不同的實驗環境下明顯優于相關的調度算法。