基于Hadoop的云計算算法研究

辛大欣，屈 偉

（西安工業(yè)大學(xué) 陜西 西安 710021）

隨著信息技術(shù)的不斷提高，信息和數(shù)據(jù)呈現(xiàn)幾何級的增長，大量的數(shù)據(jù)需要處理。在這種環(huán)境下，單點(diǎn)存儲的問題已逐步暴露。

區(qū)域問題：單點(diǎn)存儲，使用戶在外出需要克服相當(dāng)大的網(wǎng)絡(luò)延遲訪問服務(wù)。同時，為了方便維修，升級等問題使得存儲數(shù)據(jù)選擇的位置變得相對困難。

災(zāi)難恢復(fù)問題：當(dāng)系統(tǒng)崩潰后必須被恢復(fù)時，如果數(shù)據(jù)存儲備份被破壞將導(dǎo)致災(zāi)難性的后果。假如盲目地支持多個備份，不僅本身就是一種資源浪費(fèi)，而且多個數(shù)據(jù)備份之間的一致性和可用性也是一個棘手的問題。

可擴(kuò)展性問題：單點(diǎn)存儲在可擴(kuò)展性方面有很多問題。每個額外需要增加的功能或者服務(wù)都需要重新對硬件軟件的結(jié)構(gòu)進(jìn)行重新設(shè)計和配置。同時對于硬件的更新也會帶來巨大的麻煩。

管理費(fèi)用：單點(diǎn)存儲需要很多額外的管理開銷，如機(jī)房，服務(wù)集群功率消耗，以及專門的數(shù)據(jù)管理開銷和人員的培訓(xùn)費(fèi)用。據(jù)統(tǒng)計僅數(shù)據(jù)中心的碳排放量占碳的總排放量百分之二，排放量達(dá)到約35 000 000噸每年。

有些公司電力成本每年超過硬件投資。在電力分配中，服務(wù)器設(shè)備占52%的總能源消耗，冷卻系統(tǒng)和電力系統(tǒng)各38%和9%，只有1%的照明系統(tǒng)。面對這種嚴(yán)峻的形勢下，構(gòu)建節(jié)能綠色數(shù)據(jù)中心已成為焦點(diǎn)。

云計算在節(jié)約能源方面的特點(diǎn)正好符合了”低碳節(jié)能”的思想。

1）通過使用云計算，提高了設(shè)備的利用資源，減少數(shù)據(jù)中心能耗，同時避免經(jīng)濟(jì)損失造成的閑置設(shè)備。云“自我服務(wù)”的計算架構(gòu)將大大降低成本和管理，可以節(jié)省資源。

2）使用公共云服務(wù)，企業(yè)只需購買云計算服務(wù)，根據(jù)自己的需要，不需要購買電腦設(shè)備，尤其是不需要購置管理服務(wù)和數(shù)據(jù)中心的服務(wù)器，從而達(dá)到節(jié)約能耗的目的。

3）使用云桌面終端接入，沒有笨重的機(jī)箱和風(fēng)扇聲。減少功率消耗，減少熱量，每個用戶平均耗電量小于25瓦，大大降低了能源消耗，每年可節(jié)省近70%的電力供應(yīng)。

從上面可以看出云計算可以解決目前單點(diǎn)存儲的局限性以，而且對于資源的節(jié)約有很好的效果。下面對于云計算中的3種方法進(jìn)行研究。

1 在Hadoop云計算框架中的調(diào)度算法

1.1 FIFO算法

FIFO調(diào)度算法中所有的用戶任務(wù)都被提交到一個隊列中，然后由TaskTracker按照任務(wù)的優(yōu)先級（比如提交時間的先后順序）選擇將被執(zhí)行的任務(wù)。該算法的具體實(shí)現(xiàn)是Task Queue Sub Task Scheduler。具體而言，當(dāng)一個 Sub Task Tracker工作的游刃有余，期待獲得新的子任務(wù)的時候，Task Queue Sub Task Scheduler會按照各個任務(wù)的優(yōu)先級，從最高優(yōu)先級的任務(wù)開始分配子任務(wù)。而且，在給SubTaskTracker分配子任務(wù)時，還會為其留出余量，已被不時之需。這樣的策略，基本思路就是一切為高優(yōu)先級的任務(wù)服務(wù)，優(yōu)先分配不說，同時還需保留有余力以備不時之需。

FIFO調(diào)度算法調(diào)度任務(wù)的基本原理。

圖1 FIFO算法原理圖Fig.1 FIFO algorithm principle diagram

FIFO易實(shí)現(xiàn)，且整個集群的調(diào)度開銷較少。但是在FIFO調(diào)度算法中優(yōu)先級不支持搶占，這就造成了優(yōu)先級低的一些任務(wù)被阻塞的現(xiàn)象。FIFO調(diào)度算法最大的缺點(diǎn)是在存在大任務(wù)的情況下小任務(wù)響應(yīng)時間較差，且忽略了不同用戶不同任務(wù)間的需求差異，造成平臺的整體性能和系統(tǒng)資源的利用率不高，甚至影響任務(wù)的執(zhí)行。

1.2 公平調(diào)度算法

公平調(diào)度算法是由Facebook提出的一種新的任務(wù)調(diào)度算法，F(xiàn)acebook的初衷是讓Hadoop的MapReduce計算框架能夠更好的處理不同類型的任務(wù)并行執(zhí)行的需求。

1）設(shè)計思想

公平調(diào)度算法的基本思想是最大化的保證系統(tǒng)中的任務(wù)平均分配系統(tǒng)的資源。當(dāng)系統(tǒng)中只有一個任務(wù)執(zhí)行時，它將獨(dú)占整個集群并使用所有的計算資源。而一旦有其他的任務(wù)被提交，就會有 SubTaskTracker被釋放并分配給新提交的任務(wù)，以保證所有的任務(wù)都能夠獲得大體相同的計算資源量。這就使得短任務(wù)能夠在合理的時間內(nèi)完成，同時又不會有長任務(wù)長期處于饑餓狀態(tài)。

公平算法中的任務(wù)運(yùn)行情況如圖2所示。

圖2 公平調(diào)度算法原理圖Fig.2 Fair scheduling algorithm principle diagram

由圖2可以很明顯地看出，與 FIFO算法相比，在有兩個任務(wù)Job1和Job2在Hadoop集群中運(yùn)行時，該算法能夠讓Job2在Job1未全部完成的情況下使用Job1完成部分空出來的SubTaskTracker，而不是像FIFO那樣必須Job1全部完成后才能運(yùn)行Job2。

2）具體實(shí)現(xiàn)

在公平算法中，用戶提交的任務(wù)被進(jìn)一步組織為能夠公平共享資源的任務(wù)池，任務(wù)池中的任務(wù)可以平分那些分配給所在任務(wù)池的資源。在缺省情況下，公平調(diào)度算法會為每位用戶建立一個單獨(dú)的任務(wù)池，這使得所有用戶都能夠獲得等量的資源份額而不論他提交了多少任務(wù)，這也解決了Facebook案例中難以平衡的不同種類用戶任務(wù)的計算需求問題。當(dāng)然，任務(wù)池的設(shè)定也可以根據(jù)其他指標(biāo)，例如用戶的Unix組屬性等。

在實(shí)際應(yīng)用中，任務(wù)和任務(wù)池通過 PoolManager類被賦予不同的權(quán)值并以此為依據(jù)獲得相應(yīng)比例的資源額度。該算法雖不再是嚴(yán)格的平均分配，但卻更符合現(xiàn)實(shí)中的應(yīng)用環(huán)境，使系統(tǒng)可以根據(jù)子任務(wù)的重要程度等各種因素合理的為不同用戶的不同任務(wù)合理的分配系統(tǒng)資源，這有利于減少交互型任務(wù)的響應(yīng)時間。在公平調(diào)度算法的具體實(shí)現(xiàn)中，有兩個方面是關(guān)鍵：一個是如何計算每一個任務(wù)的公平份額；另一個就是當(dāng)有SubTaskTracker空閑時應(yīng)該選擇執(zhí)行哪個任務(wù)。公平調(diào)度算法的實(shí)現(xiàn)類圖如圖3所示。

3）公平調(diào)度算法優(yōu)缺點(diǎn)

公平調(diào)度算法提供了最小共享額度方法。它支持任務(wù)分類調(diào)度，使不同類型的任務(wù)獲得不同的資源分配，從而提高了服務(wù)質(zhì)量（QOS）和動態(tài)調(diào)整并行數(shù)量，它使任務(wù)能夠充分利用系統(tǒng)資源，提高系統(tǒng)的利用程度。它克服了FIFO算法上簡單，不支持搶占，資源利用率低的缺點(diǎn)，但是它并沒有考慮當(dāng)前系統(tǒng)各節(jié)點(diǎn)的負(fù)載水平和實(shí)際的負(fù)載狀態(tài)，導(dǎo)致節(jié)點(diǎn)實(shí)際負(fù)載不均衡，從而影響了整個系統(tǒng)的響應(yīng)時間，而且配置文件配置的好壞直接影響到整個系統(tǒng)的性能。

1.3 計算能力調(diào)度算法（Capacity Scheduler）

計算能力調(diào)度算法是由Yahoo提出的任務(wù)調(diào)度算法，它提供了類似公平調(diào)度算法的功能，但在設(shè)計與實(shí)現(xiàn)上兩者存在著很大差別。

1）設(shè)計思想

計算能力調(diào)度算法的思路是為各個隊列中的任務(wù)模擬出具有指定計算能力的獨(dú)立的 Hadoop集群資源，而不像公平調(diào)度算法那樣試圖在所有的任務(wù)間實(shí)現(xiàn)公平的資源分享。計算能力調(diào)度算法任務(wù)運(yùn)行情況如圖4所示。

2）具體實(shí)現(xiàn)

在計算能力調(diào)度算法的具體實(shí)現(xiàn)中，最關(guān)鍵的也是如何挑選合適的任務(wù)去執(zhí)行。它在每個隊列中的調(diào)度策略是采取基于優(yōu)先級的FIFO算法。計算能力調(diào)度算法是非搶占式的。為了使同屬于同一用戶的任務(wù)不出現(xiàn)獨(dú)占資源的情況，該算法對隊列中同一用戶提交的任務(wù)能夠獲得的資源百分比進(jìn)行了強(qiáng)制限定。另外，計算能力調(diào)度支持內(nèi)存密集型應(yīng)用，能夠有效地對Hadoop集群的內(nèi)存資源進(jìn)行管理。計算能力調(diào)度算法的實(shí)現(xiàn)類圖如圖5所示。

圖3 公平調(diào)度算法類圖Fig.3 Fair scheduling algorithm for Graphs

圖4 計算能力調(diào)度算法任務(wù)運(yùn)行圖Fig.4 Calculation of capacity scheduling algorithm task operation diagram

圖5 計算能力調(diào)度算法的實(shí)現(xiàn)類圖Fig.5 Calculation of capacity scheduling algorithm of the graph

3）計算能力調(diào)度算法優(yōu)缺點(diǎn)

計算能力調(diào)度算法克服了FIFO算法簡單而且資源利用率低的缺點(diǎn)，它支持多任務(wù)并行執(zhí)行提高了資源利用率，通過動態(tài)調(diào)整資源分配從而提高了任務(wù)執(zhí)行效率，但是計算能力調(diào)度算法中隊列設(shè)置和隊列組無法自動進(jìn)行，用戶需要了解系統(tǒng)信息進(jìn)而對作業(yè)進(jìn)行隊列設(shè)置和隊列選組，在大型系統(tǒng)中，這將成為提高系統(tǒng)整體性能的一大瓶頸。

2 總 結(jié)

通過在Hadoop平臺下的分組任務(wù)試驗(yàn)結(jié)論，隨著預(yù)算和截止時間增加，F(xiàn)IFO算法的任務(wù)完成數(shù)總體是增加的，但不是絕對遞增。第4組比第3組完成的任務(wù)少，第6組比第5組完成的任務(wù)少，出現(xiàn)了預(yù)算和截止時間增加，任務(wù)完成數(shù)反而減少的現(xiàn)象。這主要是由于在無法全部完成任務(wù)的情況下，預(yù)算和截止時間的限制會對選擇調(diào)度任務(wù)產(chǎn)生影響，以致整個調(diào)度完成后會產(chǎn)生任務(wù)完成數(shù)目減少的情況出現(xiàn)。比較得出，F(xiàn)air scheduling，Capacity Scheduler算法隨著預(yù)算和截止時間的增加，完成的任務(wù)總數(shù)逐漸遞增。對于每組預(yù)算和截止時間參數(shù)，Capacity Scheduler算法的性能要好于Fair scheduling和FIFO兩個算法，約有22.0%和10.6%的性能提高。

3 結(jié) 論

通過結(jié)合hadoop云存儲平臺下的算法模擬，說明在3種算法隨著任務(wù)數(shù)逐漸增加Capacity Scheduler算法的性能要好于Fair scheduling和FIFO兩個算法。驗(yàn)證結(jié)構(gòu)如同初期預(yù)想，隨著任務(wù)總數(shù)以及任務(wù)完成周期要求的不同，在云存儲系統(tǒng)中選擇適合用戶算法對于用戶完成任務(wù)的效率有很大的提升。

圖6 試驗(yàn)結(jié)論效果對比圖Fig.6 Effect comparison of test results

[1]劉曉茜.云計算數(shù)據(jù)中心及其調(diào)度機(jī)制研究 [D].北京:中國科技技術(shù)大學(xué)，2011.

[2]劉鵬著.云計算[M].北京：電子工業(yè)出版社，2010.

[3]熊樂.Google集群系統(tǒng)技術(shù)綜述[J].中國科技信息，2009（9）:126-127.

XIONG Le.Google cluster system technique in China[J].science and technology information，2009（9）:126-127.

[4]胡文波，徐造林.分布式存儲方案的設(shè)計與研究[J].計算機(jī)技術(shù)與發(fā)展，2010（4）:65-68.

HU Wen-bo，XU Zao-lin.Design and research on distributed storage scheme[J].Computer Technology and The Development，2010（4）:65-68.

[5]周姝.云計算之淺見[C]//2011國際信息技術(shù)與應(yīng)用論壇論文集，2011.

[6]黃曉云.基于HDFS的云存儲服務(wù)系統(tǒng)研究[D].大連:大連海事大學(xué)，2010.