門 威，呂書林

（河南廣播電視大學信息技術(shù)中心，鄭州　450000）

淺談基于Hadoop平臺的大規(guī)模數(shù)據(jù)排序

門 威，呂書林

（河南廣播電視大學信息技術(shù)中心，鄭州450000）

據(jù)IDC統(tǒng)計，2011年全球處理的數(shù)據(jù)量達到1.8 ZB，預計到2020年達到40 ZB。如何對海量數(shù)據(jù)進行高效分析和有效管理已成為大數(shù)據(jù)時代亟需解決的問題之一。商業(yè)數(shù)據(jù)、科學數(shù)據(jù)和網(wǎng)頁數(shù)據(jù)這3類海量數(shù)據(jù)的異構(gòu)性（充滿著非結(jié)構(gòu)化、半結(jié)構(gòu)化和結(jié)構(gòu)化數(shù)據(jù)）進一步增加了海量數(shù)據(jù)的處理難度。海量數(shù)據(jù)排序是海量數(shù)據(jù)處理的基本內(nèi)容之一。Hadoop曾利用3 658個節(jié)點的集群在16.25小時內(nèi)完成1PB數(shù)據(jù)的排序，獲得Daytona類GraySort和MinuteSort級別的冠軍。本文在設計層面上對Hadoop平臺上海量數(shù)據(jù)排序策略進行分析。

Hadoop平臺；海量數(shù)據(jù)排序；基準排序；云計算

1　基準排序

Jim Gray基準排序包含若干種基準，每個基準由多個規(guī)則構(gòu)成，用于度量不同記錄排序時間。約定情況下，每條記錄長度為100字節(jié)，其中前10個字節(jié)是鍵，后面部分是值。MinuteSort用于比較一分鐘內(nèi)執(zhí)行排序的數(shù)據(jù)量大小，而GraySort用于比較100TB以上的大規(guī)模數(shù)據(jù)的排序速度（TBs/minute）?；鶞室?guī)則約定如下：

1）輸入數(shù)據(jù)和生成數(shù)據(jù)匹配且輸入/輸出數(shù)據(jù)都是未壓縮的；

2）任務開始前不允許在操作系統(tǒng)內(nèi)緩存數(shù)據(jù)；

3）分發(fā)程序到集群上的時間和抽樣時間都要計入總時長；

4）如果輸出多個文件，就必須是有序的；

5）必須計算出每個Key/Value對的CRC32校驗值（128位），保證輸入輸出相對應；

6）輸出文件保存到磁盤上；

7）輸出數(shù)據(jù)不能改寫輸入數(shù)據(jù)。

根據(jù)Yahoo！測試結(jié)果顯示：利用Hadoop平臺下3 658個集群節(jié)點排列1PB數(shù)據(jù)用了975分鐘，具體如表1所示。

2　Hadoop排序策略

首先設計3個Hadoop應用程序用于數(shù)據(jù)排序：TeraGen、 TeraSort和TeraValidate。在此，給出概括分析論述如下。

1）TeraGen。用于生成數(shù)據(jù)，可根據(jù)待執(zhí)行任務數(shù)目給所有map分配任務，每個map生成所分配的行數(shù)范圍內(nèi)的數(shù)據(jù)。TeraGen利用1 800個map任務產(chǎn)生100億行數(shù)據(jù)并存儲到HDFS中，每個存儲塊設定為512MB；

2）TeraSort。是map/reduce程序，用于數(shù)據(jù)排序。首先利用N-1個有序的抽樣值為reduce任務分配待排序數(shù)據(jù)行數(shù)范圍。比如，把鍵值在［sample［i-1］，sample［i］）范圍內(nèi)的數(shù)據(jù)分配給第i個任務，因此第i個任務任意輸出數(shù)據(jù)比第i+ 1個任務輸出數(shù)據(jù)小。這里采用兩層索引樹策略加速數(shù)據(jù)分配。由于數(shù)據(jù)不需要復制到多個節(jié)點，可以將副本數(shù)設成1。在本實驗中，相應分配1 800個map和reduce任務進行排序，為防止中間數(shù)據(jù)溢出，需要為任務的棧分布足夠的空間；

3）TeraValidate。用于驗證輸出數(shù)據(jù)，具體為每個輸出文件分配一個map任務（如圖1所示），用于檢查當前值是否全部大于等于前面的值，同時驗證第i個輸出文件中的最小值是否大于等于第i-1個文件中的最大值，否則拋出錯誤。

表1　排序時間和數(shù)據(jù)規(guī)模測驗表Tab.1 Test results of sorting time and data size

圖1　各個階段的任務量Fig.1 Number of tasks at each stage

該測試中，Hadoop集群配置如下：

1）910個節(jié)點；

2）節(jié)點配置：8 GB內(nèi)存、1 GB以太網(wǎng)帶寬，4個2.0 GHz雙核處理器和4個SATA硬盤；

3）40節(jié)點/rack，rack到核心有8 GB帶寬的以太網(wǎng)；

4）Red Hat Enterprise Linux Server 5.1操作系統(tǒng)；

5）JDK1.6.0，整個排序使用209 s。

依托910個節(jié)點的集群，Hadoop在209 s（3.48 min）完成了對1TB數(shù)據(jù)的排序。

3　Hadoop在GraySort基準排序中的改進

為適應于GraySort基準排序時，研究員在原map/reduce程序的基礎上，對Hadoop進行適應性修改，將整個程序劃分成4個模塊：TeraGen、TeraSort、TeraSum和TeraValidate。各模塊實現(xiàn)功能如下：

1）TeraGen利用map/reduce方法生成數(shù)據(jù)；

2）TeraSort負責數(shù)據(jù)取樣，并使用map/reduce進行數(shù)據(jù)排序；

3）TeraSum負責計算每個Key/Value對的CRC32校驗和，用于檢查排序輸出的正確性；

4）TeraValidate負責驗證輸出數(shù)據(jù)是否有序，計算校驗和之總和。

本次基準排序測試運行在Yahoo！的Hammer集群上，集群配置如下：

1）3800個節(jié)點（大規(guī)模集群下需要冗余節(jié)點）；

2）每個節(jié)點配備4個SATA硬盤、2.5 GHz的Xeons CPU、8 GB內(nèi)存、1 GB以太網(wǎng)；

3）每個rack放置40個節(jié)點，rack到核心以太網(wǎng)帶寬8 GB；

4）采用Red HatEnterprise Linux Server Realease 5.1操作系統(tǒng)；

5）采用Sun Java JDK 1.6.0 05（32 or 64 bit）。

在Hadoop平臺方面的改進主要呈現(xiàn)在如下研究設計中：

1）重新構(gòu)建Hadoopshuffle階段的reducer部分，提高了shuffle性能，增加了代碼的可維護性和易讀性；

2）重構(gòu)后shuffle過程可以從某一個節(jié)點獲取多個map結(jié)果，減少了連接和傳輸開銷；

3）允許配置shuffle連接建立時超時時間。小規(guī)模排序時減少shuffle超時時間，減少任務延遲時間；

4）把TCP設置成無延遲，增加JobTracker和TaskTracker之間的頻率（配置成默認值的2倍，2秒/1 000節(jié)點），減少延遲時間；

5）增加用于檢測shuffle數(shù)據(jù)正確性的代碼塊，防止reduce任務的失?。?/p>

6）在map輸出時采用LZO壓縮；

7）在shuffle階段，在內(nèi)存聚集輸出map結(jié)果集的時候?qū)崿F(xiàn)內(nèi)存到內(nèi)存的聚集，減少reduce運行工作量；

8）使用多線程進行抽樣并建立一個基于鍵平均值的分配器；

9）JobTracker為TaskTracker分配任務的默認策略時先來先服務（FCFS），這種貪心算法不能很好地適應分布式數(shù)據(jù)。TeraSort實現(xiàn)了一次性分配的全局調(diào)度策略；

10）刪除硬編碼等待循環(huán)，禁用Hadoop 0.20的自動安裝/清除任務功能以減少開始和結(jié)束的任務延遲；

11）日志級別設置成WARN以減少日志內(nèi)容，提高系統(tǒng)性能。

實驗表明，Hadoop經(jīng)過改進后可以在更短時間內(nèi)處理更多的數(shù)據(jù)。小規(guī)模的數(shù)據(jù)需要更快的網(wǎng)絡和更短的延遲，因此使用集群的小部分節(jié)點進行計算；小規(guī)模計算過程短、集群規(guī)模小，節(jié)點故障率低，因此可以把計算輸出副本數(shù)量設置為1。對于大規(guī)模計算，節(jié)點故障率高，需將輸出副本數(shù)量設成2，且放置在不同節(jié)點上，保證某個節(jié)點出現(xiàn)故障時，數(shù)據(jù)不致丟失。

圖2顯示了不同時間點下的任務數(shù)量。maps只有一個階段，reduces有shuffle、merge和reduce3個階段.其中，shuffle用于從maps中轉(zhuǎn)移數(shù)據(jù)，reduce負責將聚集數(shù)據(jù)寫入到HDFS中。在圖1中，Hadoop每次心跳只能建立一個任務，所有任務的建立需要40 s，而現(xiàn)在每次心跳可以設置一個TaskTracker，明顯降低了任務開銷。與圖1比較發(fā)現(xiàn)，任務建立的速度明顯變快了。

圖2　不同時間段的任務數(shù)（1TB數(shù)據(jù)量）Fig.2 Number of tasks in different time periods

值得注意的是，數(shù)據(jù)傳輸規(guī)模和次數(shù)對數(shù)據(jù)排序性能的影響很大。例如在PB級別的數(shù)據(jù)排序中，把每個map處理的數(shù)據(jù)設成15GB，而不是默認的128 MB。因此，為了增加吞吐量，拓延每個塊容量則至關(guān)重要。隨著Hadoop的不斷改進和優(yōu)化，其在處理大規(guī)模數(shù)據(jù)排序方面的能力也將不斷完善與增強。

［1］陸嘉恒.Hadoop實戰(zhàn)［M］.北京：機械工業(yè)出版社，2011.

［2］Tom White.Hadoop權(quán)威指南［M］.2版.北京：清華大學出版社，2011.

［3］蔡斌，陳湘萍.Hadoop技術(shù)內(nèi)幕［M］.北京：機械工業(yè)出版社，2013.

Research on large scale data sorting based on Hadoop platform

MEN Wei，LV Shulin
（Information Technology Centre，Henan Radio and Television University，Zhengzhou 450000，China）

According to IDC statistics，in 2011 the amount of data processing in the world has reached 1.8ZB，and is expected to reach 40ZB in 2020.It is an urgent problem how to analyze and manage the massive data efficiently during the time of big data.The heterogeneity of these 3 kinds of massive data，such as business data，scientific data，and web data（full of unstructured，semi-structured and structured data），has further increased the difficulty of processing massive data.The sorting of massive data is one of the basic contents of massive data processing.Hadoop has used the cluster with 3 658 nodes in 16.25 hours to complete the sorting of 1PB data，and gotten the champion of the Daytona class GraySort and Minutesort level.This paper designs and analyzes the massive data scheduling strategy based on Hadoop platform.

Hadoop platform；the sorting of massive data；benchmark sorting；cloud computing

TP391

A

2095-2163（2016）03-0130-03

2016-05-03

門 威（1988-），男，碩士，助教，主要研究方向：軟件工程、云計算；呂書林（1987-），男，碩士，助教，主要研究方向：軟件工程。