Hadoop集群中給定候選任務(wù)集的最大利潤(rùn)問題

鄭羽 羅漢云

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

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

中圖分類號(hào)：G642 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2020）08-0269-05

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

1 相關(guān)知識(shí)

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

1.1 Mapreduce環(huán)境

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

1.2相關(guān)工作

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

1.3存在的問題

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

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

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

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

j.profit√在截止時(shí)間前完成所獲得的利潤(rùn)。

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

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

1.4.2調(diào)度算法

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

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

2 實(shí)驗(yàn)

2.1 實(shí)驗(yàn)設(shè)置

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

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

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

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

總利潤(rùn)的計(jì)算在公式l中。此外，定義接收率和完成率如下：

接受任務(wù)集的大小

（3）

接受率= 候選任務(wù)集的大小

完成的任務(wù)數(shù)

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

（4）

2.2 實(shí)驗(yàn)結(jié)果

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

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

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

3 結(jié)束語

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

參考文獻(xiàn)：

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

[2]王靜蕾.Hadoop云計(jì)算框架中的分布式數(shù)據(jù)庫HBase研究[J].商丘職業(yè)技術(shù)學(xué)院學(xué)報(bào)，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]向麗輝，繆力，張大方.壓縮對(duì)Hadoop性能影響研究[J].計(jì)算機(jī)工程與科學(xué)，2015（2）：207-212.

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

[7]孫彥超，王興芬.基于Hadoop框架的MapReduce計(jì)算模式的優(yōu)化設(shè)計(jì)[J].計(jì)算機(jī)科學(xué)，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的日志實(shí)時(shí)處理系統(tǒng)研究[J].西南師范大學(xué)學(xué)報(bào)：自然科學(xué)版.2017（4）：119-126.

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

[13]余輝，黃永峰，胡萍.微博輿情的Hadoop存儲(chǔ)和管理平臺(tái)設(shè)計(jì)與實(shí)王見[J].電子技術(shù)應(yīng)用，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]張建平，李斌，劉學(xué)軍，等.基于Hadoo的異常傳感數(shù)據(jù)時(shí)間序列檢測(cè)[J].傳感技術(shù)學(xué)報(bào)，2014，27（12）：1659-1665.

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