門 威，呂書林

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

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

門 威，呂書林

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

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

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

1　基準(zhǔn)排序

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

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

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

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

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

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

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

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

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

2　Hadoop排序策略

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

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

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

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

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

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

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

1）910個節(jié)點(diǎn)；

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

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

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

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

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

3　Hadoop在GraySort基準(zhǔn)排序中的改進(jìn)

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

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

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

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

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

本次基準(zhǔn)排序測試運(yùn)行在Yahoo！的Hammer集群上，集群配置如下：

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

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

3）每個rack放置40個節(jié)點(diǎn)，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平臺方面的改進(jìn)主要呈現(xiàn)在如下研究設(shè)計中：

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

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

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

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

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

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

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

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

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

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

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

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

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

圖2　不同時間段的任務(wù)數(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ù)設(shè)成15GB，而不是默認(rèn)的128 MB。因此，為了增加吞吐量，拓延每個塊容量則至關(guān)重要。隨著Hadoop的不斷改進(jìn)和優(yōu)化，其在處理大規(guī)模數(shù)據(jù)排序方面的能力也將不斷完善與增強(qiáng)。

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

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

［3］蔡斌，陳湘萍.Hadoop技術(shù)內(nèi)幕［M］.北京：機(jī)械工業(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-），男，碩士，助教，主要研究方向：軟件工程。