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

鄭羽 羅漢云

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

關鍵詞：MapReduce;任務集;調度算法;利潤;大數據

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

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

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

1 相關知識

這一部分簡要介紹了MapReduce，然后回顧了有關MapRe-duce任務調度的工作。

1.1 Mapreduce環境

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

1.2相關工作

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

1.3存在的問題

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

j.N，j中的Map作業數。

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

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

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

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

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

1.4.2調度算法

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

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

2 實驗

2.1 實驗設置

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

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

2）任務數N，即L中任務的數量;

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

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

接受任務集的大小

（3）

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

完成的任務數

完成率= 接受的任務數

（4）

2.2 實驗結果

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

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

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

3 結束語

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

參考文獻：

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

[2]王靜蕾.Hadoop云計算框架中的分布式數據庫HBase研究[J].商丘職業技術學院學報，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）楊倩茹，黃夢醒，萬兵，一種引入內存平衡的Hadoop平臺作業調度算法[Jl.小型微型計算機系統，2014（12）：2708-2011.

[7]孫彥超，王興芬.基于Hadoop框架的MapReduce計算模式的優化設計[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的日志實時處理系統研究[J].西南師范大學學報：自然科學版.2017（4）：119-126.

[12]梁俊榮.基于Hadoop的圖書館復合大數據存儲系統研究[Jl，現代情報，2017（2）：63-67.

[13]余輝，黃永峰，胡萍.微博輿情的Hadoop存儲和管理平臺設計與實王見[J].電子技術應用，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的異常傳感數據時間序列檢測[J].傳感技術學報，2014，27（12）：1659-1665.

【通聯編輯：王力】