門(mén) 威，呂書(shū)林

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

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

門(mén) 威，呂書(shū)林

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

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

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

1　基準(zhǔn)排序

Jim Gray基準(zhǔn)排序包含若干種基準(zhǔn)，每個(gè)基準(zhǔn)由多個(gè)規(guī)則構(gòu)成，用于度量不同記錄排序時(shí)間。約定情況下，每條記錄長(zhǎng)度為100字節(jié)，其中前10個(gè)字節(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ù)開(kāi)始前不允許在操作系統(tǒng)內(nèi)緩存數(shù)據(jù)；

3）分發(fā)程序到集群上的時(shí)間和抽樣時(shí)間都要計(jì)入總時(shí)長(zhǎng)；

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

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

6）輸出文件保存到磁盤(pán)上；

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

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

2　Hadoop排序策略

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

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

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

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

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

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

該測(cè)試中，Hadoop集群配置如下：

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

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

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，整個(gè)排序使用209 s。

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

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

為適應(yīng)于GraySort基準(zhǔn)排序時(shí)，研究員在原map/reduce程序的基礎(chǔ)上，對(duì)Hadoop進(jìn)行適應(yīng)性修改，將整個(gè)程序劃分成4個(gè)模塊：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é)計(jì)算每個(gè)Key/Value對(duì)的CRC32校驗(yàn)和，用于檢查排序輸出的正確性；

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

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

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

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

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

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

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

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

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

5）增加用于檢測(cè)shuffle數(shù)據(jù)正確性的代碼塊，防止reduce任務(wù)的失敗；

6）在map輸出時(shí)采用LZO壓縮；

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

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

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

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

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

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

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

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

值得注意的是，數(shù)據(jù)傳輸規(guī)模和次數(shù)對(duì)數(shù)據(jù)排序性能的影響很大。例如在PB級(jí)別的數(shù)據(jù)排序中，把每個(gè)map處理的數(shù)據(jù)設(shè)成15GB，而不是默認(rèn)的128 MB。因此，為了增加吞吐量，拓延每個(gè)塊容量則至關(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

門(mén) 威（1988-），男，碩士，助教，主要研究方向：軟件工程、云計(jì)算；呂書(shū)林（1987-），男，碩士，助教，主要研究方向：軟件工程。