鄭羽 羅漢云

摘要：隨著計算機網(wǎng)絡和傳感器網(wǎng)絡的迅速發(fā)展，數(shù)據(jù)呈指數(shù)級增長，特別是在因特網(wǎng)上。為了有效地處理大規(guī)模數(shù)據(jù)，需要具有良好的可伸縮性、靈活性和容錯性的并行分布式集群。目前，許多企業(yè)基于自己的Hadoop集群提供云服務。因為單個Hadoop集群的資源是有限的，Hadoop集群必須將有限的資源分配給一些特殊的任務以獲得最大的利益。該文研究給定候選任務集的最大利潤問題。用有效的序列描述候選任務集，并提出了一種基于序列的調(diào)度策略。為了提高查找有效序列的效率，設計了一些修剪策略，并給出了相應的調(diào)度算法。最后，在某些任務運行超時的情況下，我們提出了超時處理算法。實驗表明，該算法的總收益非常接近理想的最大值，在不同的實驗環(huán)境下明顯優(yōu)于相關(guān)的調(diào)度算法。

關(guān)鍵詞：MapReduce;任務集;調(diào)度算法;利潤;大數(shù)據(jù)

中圖分類號：G642 文獻標識碼：A

文章編號：1009-3044（2020）08-0269-05

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

1 相關(guān)知識

這一部分簡要介紹了MapReduce，然后回顧了有關(guān)MapRe-duce任務調(diào)度的工作。

1.1 Mapreduce環(huán)境

MapReduce是一種流行的面向數(shù)據(jù)密集型任務的編程模型，在許多領(lǐng)域得到了廣泛的應用[6-8]。Hadoop是一個由Apache基金會所開發(fā)的分布式系統(tǒng)基礎架構(gòu)。用戶可以在不了解分布式底層細節(jié)的情況下，開發(fā)分布式程序。充分利用集群的威力進行高速運算和存儲。Hadoop實現(xiàn)了一個分布式文件系統(tǒng)（Hadoop Distributed File System），簡稱HDFS。HDFS有高容錯性的特點，并且可以部署在低廉的Clow-cost）硬件上;而且它提供高吞吐量來訪問應用程序的數(shù)據(jù)，適合那些有著超大數(shù)據(jù)集的應用程序。圖1所畫的就是MapReduce框架，在用戶定義的map函數(shù)中，輸入是一個鍵值對，輸出是零或多個鍵值對。在組步驟中，具有相同密鑰的系統(tǒng)組鍵值對會被發(fā)送到相同的還原節(jié)點。在自定義的Reduce函數(shù)中，組合鍵值對處理產(chǎn)生的結(jié)果。MapReduce任務通常需要多次Map/Reduce迭代。

1.2相關(guān)工作

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

1.3存在的問題

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

j.N，j中的Map作業(yè)數(shù)。

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

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

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

在上述兩種情況下，都不可能按時完成JS中的所有任務，因此S必須不是有效的序列。

基于定理1和2，可以得出結(jié)論，所提出的調(diào)度策略對于固定序列S是最優(yōu)的。這意味著如果在提議的策略下存在超時任務，那么它們必須存在于任何其他調(diào)度策略中。

1.4.2調(diào)度算法

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

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

2 實驗

2.1 實驗設置

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

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

2）任務數(shù)N，即L中任務的數(shù)量;

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

總利潤的計算在公式l中。此外，定義接收率和完成率如下：

接受任務集的大小

（3）

接受率= 候選任務集的大小

完成的任務數(shù)

完成率= 接受的任務數(shù)

（4）

2.2 實驗結(jié)果

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

同時，觀察了任務數(shù)和平均截止期對總利潤的影響，結(jié)果如圖3所示。由于同樣的原因，方法不僅接收到最多的候選任務，而且完成大部分任務，因此可以帶來最大的利潤。此外，對三種情況的總利潤非常接近理想值。

最后，動態(tài)地將任務提交給Hadoop集群，觀察總利潤的變化。在圖中，水平軸是經(jīng)過的時間，垂直軸分別是總利潤、接收率和完成率。從數(shù)據(jù)可以看出，此方法不僅接收到最多的候選任務，而且完成大部分任務，因此可以帶來最大的利潤。這說明所提出的方法也適用于動態(tài)提交的任務。

3 結(jié)束語

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

參考文獻：

[1]李玉丹，鄭曉薇.Hadoop下多模式并行分類算法及其應用研究[J].計算機工程，2014（12）：45-49.

[2]王靜蕾.Hadoop云計算框架中的分布式數(shù)據(jù)庫HBase研究[J].商丘職業(yè)技術(shù)學院學報，2014（2）：18-20.

[3lchu cheng，et al.Map-reduce for machine learning on multicore[C]//Advances in neural information processing systems，2007，25[4]：19-281.

[4]1nza I，Larranaga P，Blanco R.Filter versus wrapper gene se-lection approaches in DNA microarray domain[J].Artificial In-telligence in Medicine， 2004，31（2）：91-103.

[5]向麗輝，繆力，張大方.壓縮對Hadoop性能影響研究[J].計算機工程與科學，2015（2）：207-212.

[6）楊倩茹，黃夢醒，萬兵，一種引入內(nèi)存平衡的Hadoop平臺作業(yè)調(diào)度算法[Jl.小型微型計算機系統(tǒng)，2014（12）：2708-2011.

[7]孫彥超，王興芬.基于Hadoop框架的MapReduce計算模式的優(yōu)化設計[J].計算機科學，2014（11）：333-336.

[8] B.K. Tripathy; Dishant Mittal;， Hadoop based uncertain possi-bilistic kernelized c-means algorithms for image segmentationand a comparative analysis[Jl. Applied Soft Computing. 2016，46（C）：886-923.

[9]Ganesh S，Binu A.Statistical analysis to determine the perform-ance of multiple beneficiaries of educational sector using Ha-doop-Hive[C]// International conference on data science&engineering.[s.I.l：lEEE， 2014：32-37.

[10] Berli 7 nska，M Drozdowski， Scheduling divisible mapreducecomputations[J]. Parallel Distrib. Comput，2011，71（3）：450-459.

[11]李洋，呂家恪.基于Hadoop與Storm的日志實時處理系統(tǒng)研究[J].西南師范大學學報：自然科學版.2017（4）：119-126.

[12]梁俊榮.基于Hadoop的圖書館復合大數(shù)據(jù)存儲系統(tǒng)研究[Jl，現(xiàn)代情報，2017（2）：63-67.

[13]余輝，黃永峰，胡萍.微博輿情的Hadoop存儲和管理平臺設計與實王見[J].電子技術(shù)應用，2017（3）：120-123.

[14] T.K.Ho The random subspace method for constructing deci-sion forests[Jl.IEEE Transaction on PatternAnalysis and Ma-chine InteUigence，1998，20（8）：832-844.

[15]張建平，李斌，劉學軍，等.基于Hadoo的異常傳感數(shù)據(jù)時間序列檢測[J].傳感技術(shù)學報，2014，27（12）：1659-1665.

【通聯(lián)編輯：王力】