李千慧，魏海平，竇雪英

（1．遼寧石油化工大學(xué) 計(jì)算機(jī)與通信工程學(xué)院，遼寧 撫順 113001；2．中國(guó)寰球工程公司遼寧分公司信息中心 遼寧 撫順 113006）

基于Hadoop的排序性能優(yōu)化研究

李千慧1，魏海平1，竇雪英2

（1．遼寧石油化工大學(xué) 計(jì)算機(jī)與通信工程學(xué)院，遼寧 撫順 113001；2．中國(guó)寰球工程公司遼寧分公司信息中心 遼寧 撫順 113006）

如何高效排序是在對(duì)大數(shù)據(jù)進(jìn)行快速有效的分析與處理時(shí)的一個(gè)重要問(wèn)題。首先對(duì)基于Hadoop平臺(tái)的幾種高效的排序算法（Quicksort，Heapsort和Mergesort算法）進(jìn)行了研究。再通過(guò)對(duì)Hadoop平臺(tái)的幾種現(xiàn)有的排序算法的分析比較，發(fā)現(xiàn)頻繁的讀寫(xiě)磁盤(pán)降低數(shù)據(jù)處理的效率，提出了一種優(yōu)化現(xiàn)有排序算法的置換選擇算法，并進(jìn)行了測(cè)試。測(cè)試結(jié)果表明，該算法簡(jiǎn)化了運(yùn)行過(guò)程，可實(shí)現(xiàn)更快速的合并，從而提高數(shù)據(jù)處理的效率，對(duì)Hadoop的性能優(yōu)化具有現(xiàn)實(shí)意義。

Hadoop；排序優(yōu)化；置換選擇算法；大數(shù)據(jù)

隨著互聯(lián)網(wǎng)等信息技術(shù)的飛速發(fā)展，網(wǎng)絡(luò)用戶(hù)的快速增加，各行各業(yè)中的數(shù)據(jù)也日益增長(zhǎng)，形成了海量數(shù)據(jù)。這些數(shù)據(jù)是不但數(shù)據(jù)體量巨大，而且是高價(jià)值的，具有多樣化和持續(xù)性等特點(diǎn)。其非結(jié)構(gòu)化的特性，使得數(shù)據(jù)的存儲(chǔ)和處理成了當(dāng)前面臨的挑戰(zhàn)。這些數(shù)據(jù)需要在大型的分布式集群上來(lái)處理。如何有效地處理這些并行的計(jì)算，管理海量分布式的數(shù)據(jù)以及對(duì)大數(shù)據(jù)進(jìn)行分析與處理，成為急需解決的重點(diǎn)問(wèn)題。MapReduce是一個(gè)廣泛應(yīng)用于大數(shù)據(jù)分析和處理的計(jì)算框架［1-2］。Hadoop作為Apache開(kāi)源組織的一個(gè)分布式計(jì)算并行編程框架［3］，能夠?qū)崿F(xiàn)MapReduce計(jì)算模式的分布式并行編程，逐漸成為業(yè)界使用的標(biāo)準(zhǔn)。Hadoop已經(jīng)應(yīng)用在許多國(guó)內(nèi)外的知名網(wǎng)站上，如Facebook、雅虎和百度等。其分布式文件系統(tǒng)的高容錯(cuò)性和高擴(kuò)展性，能夠滿足數(shù)據(jù)量迅速增長(zhǎng)的需要，所以已經(jīng)廣泛的用來(lái)解決海量數(shù)據(jù)的處理問(wèn)題［4］。

本文經(jīng)過(guò)對(duì)MapReduce計(jì)算模式研究后發(fā)現(xiàn)，MapReduce中的缺省排序本身既是一種對(duì)數(shù)據(jù)普遍的處理方式，也是一種預(yù)處理。但是針對(duì)日益增長(zhǎng)的海量數(shù)據(jù)的分析處理，傳統(tǒng)的排序方法由于大多是基于關(guān)鍵字的比較和交換兩種操作，導(dǎo)致多次讀取磁盤(pán)，所以消耗時(shí)間較多，難以有效地處理數(shù)據(jù)。本文通過(guò)優(yōu)化排序減少對(duì)磁盤(pán)的讀寫(xiě)操作，能使得后續(xù)處理更加高效、快捷。

1　Hadoop中的排序

排序算法分為兩類(lèi)：內(nèi)部排序和外部排序［5-6］。內(nèi)部排序是指輸入數(shù)據(jù)在內(nèi)存中進(jìn)行排序，包括Quicksort，Heapsort和Mergesort等算法。當(dāng)需要對(duì)一個(gè)非常大的文件中的內(nèi)容進(jìn)行排序時(shí)，由于計(jì)算機(jī)內(nèi)存是有限的，數(shù)據(jù)不能完全存入內(nèi)存時(shí)，則無(wú)法使用內(nèi)部排序算法一次完成排序，需要利用磁盤(pán)空間進(jìn)行外部排序。

1.1Hadoop中排序機(jī)制及排序算法

在Hadoop分布式環(huán)境中，Hadoop的排序功能是非常強(qiáng)大的，能夠?qū)B級(jí)數(shù)據(jù)進(jìn)行排序。當(dāng)輸入記錄的規(guī)模較大時(shí)，利用快速排序、堆排序、歸并排序這些時(shí)間復(fù)雜度為O （nlog（n））的排序算法。

1.1.1Quicksort

快速排序（Quicksort）是一個(gè)交換的排序算法，在實(shí)際中經(jīng)常被使用，例如Microsoft．NET框架中。該算法被遞歸地應(yīng)用到每個(gè)子集，直到所有記錄都在它們的最終位置，其核心是分區(qū)操作。在Hadoop中的快速排序算法是通過(guò)自定義分區(qū)函數(shù)以保證數(shù)據(jù)整體有序。數(shù)據(jù)經(jīng)過(guò)map函數(shù)操作后，通過(guò)分區(qū)函數(shù)進(jìn)行數(shù)據(jù)等距劃分后進(jìn)行快速排序，不同范圍內(nèi)的數(shù)據(jù)劃分到不同分區(qū)后由對(duì)應(yīng)的reduce處理，最后按序收集各個(gè)reduce的數(shù)據(jù)。

Quicksort在最壞情況下的復(fù)雜度為O（n2），但是在實(shí)際中，通常比其他復(fù)雜度為O（nlog（n））的算法快。

1.1.2Heapsort

堆排序是基于堆的排序，分為最大堆和最小堆，可以用完全二叉樹(shù)來(lái)表示。如圖1所示是一個(gè)最大堆（由一個(gè)數(shù)組構(gòu)成）及其相應(yīng)的二叉樹(shù)。

圖1　數(shù)組與相對(duì)的完全二叉樹(shù)Fig．1　Array and the corresponding complete binary tree

本質(zhì)上講，堆排序是一種選擇排序，只不過(guò)堆排序選擇元素的方法更為先進(jìn)，時(shí)間復(fù)雜度更低，效率更高。堆排序主要用于形成和處理優(yōu)先級(jí)隊(duì)列，以及類(lèi)優(yōu)先級(jí)隊(duì)列。

1.1.3Mergesort

歸并排序的排序方式是基于歸并操作的，是將兩個(gè)或兩個(gè)以上的有序排列合并成一個(gè)大的有序文件。雖然它與快速排序和堆排序相比更加穩(wěn)定，時(shí)間復(fù)雜度在最壞的情況下也是O（nlog（n）），但卻需要O（n）的輔助空間。

1.2Hadoop平臺(tái)處理流程

Hadoop框架實(shí)現(xiàn)了 MapReduce的分布式并行編程，MapReduce的處理流程圖如圖2所示［7］。

圖2　MapReduce的處理流程Fig．2　The processing of MapReduce

MapReduce框架分為 Map與Reduce兩個(gè)核心處理階段。

Map階段：

1）將輸入數(shù)據(jù)做切片處理后交給map函數(shù)。

2）運(yùn)行map函數(shù)，其產(chǎn)生的中間輸出結(jié)果（key/value對(duì)）存入內(nèi)存緩沖區(qū)中。

3）根據(jù)最終被傳送到的reduce對(duì)中間結(jié)果進(jìn)行分區(qū)，排序后寫(xiě)入本地磁盤(pán)。

在Reduce階段分為3個(gè)部分：

1）復(fù)制來(lái)自若干個(gè)map任務(wù)的輸出文件。

2）對(duì)從map階段復(fù)制過(guò)來(lái)的文件進(jìn)行歸并排序，形成一個(gè)大而有序的文件。

3）將歸并后的有序文件交給reduce（）函數(shù)處理，將輸出寫(xiě)入Hadoop的分布式文件系統(tǒng)。

1.3Hadoop中排序性能分析

Hadoop集群環(huán)境中的應(yīng)用程序只需要實(shí)現(xiàn) map和reduce方法即可，但是由于需要sort，必須等記錄全部接收完，才能開(kāi)始排序，排序完了才能調(diào)用reduce（）函數(shù)，嚴(yán)重影響了程序運(yùn)行效率。對(duì)于大文件的排序，Hadoop現(xiàn)有的排序方式是將大文件分成n個(gè)小文件，分別對(duì)這些小文件利用內(nèi)部排序（快速排序、堆排序等）算法排序。然后再對(duì)這些文件進(jìn)行兩兩歸并，直至歸并成一個(gè)大的有序文件。這樣歸并的趟數(shù)比較多，導(dǎo)致讀寫(xiě)文件的I/O次數(shù)增多。相對(duì)于內(nèi)存中的運(yùn)算，對(duì)文件的讀寫(xiě)操作是特別費(fèi)時(shí)間的。

在Hadoop集群中，MapReduce的自動(dòng)排序有m個(gè)map，r個(gè)reduce。數(shù)據(jù)被分割成m塊的時(shí)間復(fù)雜度為O（m），每個(gè)map進(jìn)行Quicksort時(shí)間復(fù)雜度為O（n/mlog（n/m））。當(dāng)排序任務(wù)負(fù)載均衡度不高，排序?qū)Υ疟P(pán)反復(fù)的操作，加之集群運(yùn)行時(shí)間消耗及網(wǎng)絡(luò)傳輸，則Hadoop下Quicksort效率可能低于O（nlog（n））。

2　一種改進(jìn)的置換選擇算法

2.1改進(jìn)算法的描述

本文提出一種優(yōu)化Hadoop現(xiàn)有排序的算法，用于生成較長(zhǎng)的順串（初始?xì)w并段），以減少歸并段的段數(shù)。在接收輸入數(shù)據(jù)時(shí)使用改進(jìn)的排序算法生成初始段，用敗者樹(shù)從已經(jīng)傳遞到內(nèi)存中的記錄中找到關(guān)鍵值最小的記錄并輸出，得到一個(gè)順串，暫時(shí)放到磁盤(pán)，最后將多個(gè)順串進(jìn)行歸并直到最終完成排序。歸并的同時(shí)，就可以回調(diào)reduce（）函數(shù)，這樣就可以一邊接收數(shù)據(jù)，一邊部分排序，實(shí)現(xiàn)MapReduce的并行化。具體步驟如下：

步驟1：從輸入文件中讀取n條記錄到內(nèi)存里。

步驟2：用敗者樹(shù)篩選出關(guān)鍵字最小的記錄記為MIN，輸出到一個(gè)臨時(shí)文件中（或緩存區(qū)）。

步驟3：從輸入文件中再讀取一條記錄到內(nèi)存里 ，用敗者樹(shù)的一次調(diào)整過(guò)程找到關(guān)鍵字大于MIN的最小值輸出到MIN所在的文件（或緩存區(qū)）并作為新的MIN。

步驟4：重復(fù)步驟3，直到在內(nèi)存中選不出關(guān)鍵字大于MIN的記錄，生成一個(gè)順串，并輸出一個(gè)歸并段結(jié)束標(biāo)簽到輸出文件。

步驟5：重復(fù)步驟2、3、4，直至內(nèi)存為空，得到全部歸并段。將生成的順串做歸并處理，形成一個(gè)大的排好序的文件。

利用敗者樹(shù)在內(nèi)存中篩選MIN細(xì)節(jié)：1）敗者樹(shù)的外部節(jié)點(diǎn)為內(nèi)存空間中的記錄，而敗者樹(shù)中根節(jié)點(diǎn)的雙親節(jié)點(diǎn)為內(nèi)存中關(guān)鍵字最小的記錄。2）為每個(gè)記錄設(shè)一個(gè)所在歸并段的序號(hào)，簡(jiǎn)稱(chēng)為段號(hào)。篩選MIN記錄時(shí)，比較段號(hào)的大小即可，段號(hào)小的為勝者；段號(hào)相同的，關(guān)鍵字小的為勝者。

2.2算法性能分析

改進(jìn)的算法在排序過(guò)程中創(chuàng)建初始?xì)w并段，總數(shù)據(jù)量一定的情況下，初始?xì)w并段的平均長(zhǎng)度變長(zhǎng)，從而減小了初始?xì)w并段的段數(shù)n。處理過(guò)程中的歸并趟數(shù)為logkn，雖然增大歸并路數(shù)k可以減少對(duì)磁盤(pán)的操作，但是歸并時(shí)的算法復(fù)雜度也會(huì)增加。改進(jìn)后的算法由于減小了歸并段數(shù)，可以在O（logk）的復(fù)雜度下得到最小的數(shù)，每次只需比較log2k次，算法復(fù)雜度將為O（（n-1）*logk）。對(duì)于數(shù)據(jù)量超大的排序來(lái)說(shuō)，這是可觀的提高。

改進(jìn)后的算法能夠從map task端完整的把數(shù)據(jù)復(fù)制到reduce task端，尤其是跨節(jié)點(diǎn)復(fù)制數(shù)據(jù)，最大化的降低了復(fù)制數(shù)據(jù)的量以及對(duì)帶寬的消耗，以盡量減少磁盤(pán)I/O對(duì)Job完成時(shí)間的影響，減少了不必要的消耗。

3　實(shí)　驗(yàn)

3.1實(shí)驗(yàn)環(huán)境

本文實(shí)驗(yàn)在一臺(tái)PC機(jī)上搭建偽分布式環(huán)境，包含3個(gè)節(jié)點(diǎn)，一個(gè)Master，兩個(gè)slave節(jié)點(diǎn)，而且兩個(gè)slave的配置保持一致：PC內(nèi)存8G，64位WIN8系統(tǒng)，虛擬硬件為1G內(nèi)存，雙核處理器，IDE硬盤(pán)；以 centOS6．5作為操作系統(tǒng)，JDK 1．7．0作為基礎(chǔ)平臺(tái)，搭建Hadoop1．1．2平臺(tái)作為底層架構(gòu)，Eclipse作為編程環(huán)境，集群各節(jié)點(diǎn)之間SSH免密碼登錄，虛擬機(jī)之間的通信通過(guò)虛擬網(wǎng)橋?qū)崿F(xiàn)。數(shù)據(jù)來(lái)源為搜狗搜索引擎：http://www．datatang．com/data/43846。

3.2實(shí)驗(yàn)結(jié)果與分析

由圖3可以看出，在相同輸入量的情況下，經(jīng)過(guò)優(yōu)化后的置換選擇算法比傳統(tǒng)快速排序算法的速度快。在數(shù)據(jù)規(guī)模較大的排序過(guò)程中改進(jìn)后的效率明顯好于傳統(tǒng)排序方式。

圖3　優(yōu)化前后性能對(duì)比Fig．3　The performance comparison before and after optimization

4　結(jié)束語(yǔ)

本文針對(duì)Hadoop框架實(shí)現(xiàn)大規(guī)模數(shù)據(jù)處理的排序進(jìn)行了研究。首先，基于搭建好的Hadoop偽分布式環(huán)境分析了排序算法，提出了改進(jìn)算法——置換選擇算法，然后運(yùn)行MapReduce程序比較了在具有相同輸入量的情況下數(shù)據(jù)處理的時(shí)間。實(shí)驗(yàn)結(jié)果表明，在對(duì)相同的較大數(shù)據(jù)量進(jìn)行排序時(shí)，置換選擇算法優(yōu)化了基于Hadoop的排序。

［1］EKANAYAK J，PALLICKARA S，F(xiàn)OX G．MapReduce for data intensive scientific analyses［J］．Fourth IEEE International Conference on eScience，2008，7（12）:277-284．

［2］李建江，崔健，王聃，等．MapReduce并行編程模型研究綜述［J］．電子學(xué)報(bào)，2011，39（11）:2635-2642．

［3］Dhruba B．Apache Hadoop filesystem and its usage in facebook project lead［EB/OL］．［2014-11-20］．http://cloud．berkeley．edu/data/hdfs．pdf．

［4］KONSTANTINS，HAIRONGK，SANJAYR，etal．The Hadoop distributed file system［C］//Proceedings of IEEE 26th Symposium on Mass Storage Systems and Technologies．Incline Village:［s．n］，2010:1-10．

［5］JACK D，F(xiàn)RANCIS S．Guest editors′introduction:The top 10 algorithms［J］．Computing in Science&Engineering，2000，2（1）:22-23．

［6］VITTER J S．Algorithms and data structures for external memory［J］．Foundations&Trends in Theoretical Computer Science，2006，2（4）:29-56．

［7］TOM W．Hadoop:The definitive guide［M］．3rd ed．The United States of America:O′Reilly Media，Inc，2009．

Optimization of sorting performance based on Hadoop

LI Qian-hui1，WEI Hai-ping1，DOU Xue-ying2
（1．School of Computer and Communication Engineering，Liaoning University of Petroleum&Chemical Technology，F(xiàn)ushun 113001，China；2．Information Center HQC（Liaoning）CO.，F(xiàn)ushun 113006，China）

When people analysising and processing big data fast and efficiently，how to efficiently sorting is an important issue．There have several efficient sorting algorithms，including Quicksort，Heapsort and Mergesort algorithm，ware studied based on Hadoop platform．Through analysis and the differences of several existing sorting algorithms in Hadoop platform，frequently operating on disk reducing the efficiency of data processing was discovered，so a new sorting algorithm，replacement and selection algorithm，was proposed to optimize the existing sorting algorithm．New algorithm has been tested，and the test results have shown that the new algorithm simplified the process of running，could achieve a more rapidly consolidation，improving the efficiency of data processing，so had practical significanceon Hadoop performance optimization．

Hadoop；optimization of sorting；replacement selection algorithm；big data

TN919

A

1674－6236（2016）02-0045-03

2015-03-31稿件編號(hào)：201503462

遼寧省教育科學(xué)“十二五”規(guī)劃立項(xiàng)課題（JG12DB279；JG13DB077）

李千慧（1989—），女，內(nèi)蒙古自治區(qū)赤峰人，碩士研究生。研究方向：計(jì)算機(jī)網(wǎng)絡(luò)與多媒體技術(shù)。