鄭 羽，胡積寶

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

0 引 言

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

1 相關(guān)知識

1.1 MapReduce環(huán)境

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

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

圖1 MapReduce框架

1.2 相關(guān)工作

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

1.3 存在的問題

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

j.Nm：j中的Map作業(yè)數(shù)。

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

j.deadline，j所規(guī)定的時間或期限。

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

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

(1)

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

1.4 調(diào)度算法

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

1.4.1 基于序列的調(diào)度策略

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

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

基于給定的序列S，提出了如下的調(diào)度策略：

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

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

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

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

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

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

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

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

在上述兩種情況下，都不可能按時完成JS中的所有任務(wù)，因此S必須不是有效的序列?；诙ɡ?和定理2，可以得出結(jié)論，所提出的調(diào)度策略對于固定序列S是最優(yōu)的。這意味著如果在提議的策略下存在超時任務(wù)，那么它們必須存在于任何其他調(diào)度策略中。

1.4.2 調(diào)度算法

在提出的基于序列的調(diào)度策略的基礎(chǔ)上，文中提出了一種調(diào)度算法。首先，當(dāng)候選任務(wù)設(shè)置是靜態(tài)的，使用的評分策略為所有任務(wù)指定優(yōu)先級，將找到可接受的任務(wù)并為其設(shè)定一個有效的修剪策略，并發(fā)現(xiàn)一個有效的序列。其次，當(dāng)候選的任務(wù)集實現(xiàn)了動態(tài)更新，會執(zhí)行增量法判斷可接受的任務(wù)集和更新有效序列是否必要。

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

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

在此基礎(chǔ)上，提出了一種以總利潤最大化為目標(biāo)的評分函數(shù)。對任務(wù)J而言，得分是：

(2)

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

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

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

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

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

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

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

算法1：

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

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

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

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

假設(shè)A←{j1}，φ←{{j1}}

For每個ji∈Jandi≠1 do

假設(shè)φ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 實驗設(shè)置

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

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

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

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

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

(3)

(4)

2.2 實驗結(jié)果

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

圖2 任務(wù)數(shù)對總利潤的影響

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

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

圖3 任務(wù)數(shù)的影響

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

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

3 結(jié)束語

研究了Hadoop集群中的最大利潤問題。為了使利潤最大化，基于候選任務(wù)集的有效序列選擇了一些高利潤率的任務(wù)。此外，為了提高查找有效序列的效率，設(shè)計了一些修剪策略，并給出了相應(yīng)的調(diào)度算法。實驗結(jié)果表明，該算法的總收益非常接近理想的最大值，在不同的實驗環(huán)境下明顯優(yōu)于相關(guān)的調(diào)度算法。