基于Hadoop的云計算算法研究

辛大欣，屈 偉

（西安工業大學 陜西 西安 710021）

隨著信息技術的不斷提高，信息和數據呈現幾何級的增長，大量的數據需要處理。在這種環境下，單點存儲的問題已逐步暴露。

區域問題：單點存儲，使用戶在外出需要克服相當大的網絡延遲訪問服務。同時，為了方便維修，升級等問題使得存儲數據選擇的位置變得相對困難。

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

可擴展性問題：單點存儲在可擴展性方面有很多問題。每個額外需要增加的功能或者服務都需要重新對硬件軟件的結構進行重新設計和配置。同時對于硬件的更新也會帶來巨大的麻煩。

管理費用：單點存儲需要很多額外的管理開銷，如機房，服務集群功率消耗，以及專門的數據管理開銷和人員的培訓費用。據統計僅數據中心的碳排放量占碳的總排放量百分之二，排放量達到約35 000 000噸每年。

有些公司電力成本每年超過硬件投資。在電力分配中，服務器設備占52%的總能源消耗，冷卻系統和電力系統各38%和9%，只有1%的照明系統。面對這種嚴峻的形勢下，構建節能綠色數據中心已成為焦點。

云計算在節約能源方面的特點正好符合了”低碳節能”的思想。

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

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

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

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

1 在Hadoop云計算框架中的調度算法

1.1 FIFO算法

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

FIFO調度算法調度任務的基本原理。

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

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

1.2 公平調度算法

公平調度算法是由Facebook提出的一種新的任務調度算法，Facebook的初衷是讓Hadoop的MapReduce計算框架能夠更好的處理不同類型的任務并行執行的需求。

1）設計思想

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

公平算法中的任務運行情況如圖2所示。

圖2 公平調度算法原理圖Fig.2 Fair scheduling algorithm principle diagram

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

2）具體實現

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

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

3）公平調度算法優缺點

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

1.3 計算能力調度算法（Capacity Scheduler）

計算能力調度算法是由Yahoo提出的任務調度算法，它提供了類似公平調度算法的功能，但在設計與實現上兩者存在著很大差別。

1）設計思想

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

2）具體實現

在計算能力調度算法的具體實現中，最關鍵的也是如何挑選合適的任務去執行。它在每個隊列中的調度策略是采取基于優先級的FIFO算法。計算能力調度算法是非搶占式的。為了使同屬于同一用戶的任務不出現獨占資源的情況，該算法對隊列中同一用戶提交的任務能夠獲得的資源百分比進行了強制限定。另外，計算能力調度支持內存密集型應用，能夠有效地對Hadoop集群的內存資源進行管理。計算能力調度算法的實現類圖如圖5所示。

圖3 公平調度算法類圖Fig.3 Fair scheduling algorithm for Graphs

圖4 計算能力調度算法任務運行圖Fig.4 Calculation of capacity scheduling algorithm task operation diagram

圖5 計算能力調度算法的實現類圖Fig.5 Calculation of capacity scheduling algorithm of the graph

3）計算能力調度算法優缺點

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

2 總 結

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

3 結 論

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

圖6 試驗結論效果對比圖Fig.6 Effect comparison of test results

[1]劉曉茜.云計算數據中心及其調度機制研究 [D].北京:中國科技技術大學，2011.

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

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

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

[4]胡文波，徐造林.分布式存儲方案的設計與研究[J].計算機技術與發展，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國際信息技術與應用論壇論文集，2011.

[6]黃曉云.基于HDFS的云存儲服務系統研究[D].大連:大連海事大學，2010.