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

李千慧，魏海平，竇雪英

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

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

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

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

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

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

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

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

1　Hadoop中的排序

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

1.1Hadoop中排序機制及排序算法

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

1.1.1Quicksort

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

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

1.1.2Heapsort

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

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

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

1.1.3Mergesort

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

1.2Hadoop平臺處理流程

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

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

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

Map階段：

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

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

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

在Reduce階段分為3個部分：

1）復制來自若干個map任務的輸出文件。

2）對從map階段復制過來的文件進行歸并排序，形成一個大而有序的文件。

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

1.3Hadoop中排序性能分析

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

在Hadoop集群中，MapReduce的自動排序有m個map，r個reduce。數(shù)據(jù)被分割成m塊的時間復雜度為O（m），每個map進行Quicksort時間復雜度為O（n/mlog（n/m））。當排序任務負載均衡度不高，排序對磁盤反復的操作，加之集群運行時間消耗及網(wǎng)絡傳輸，則Hadoop下Quicksort效率可能低于O（nlog（n））。

2　一種改進的置換選擇算法

2.1改進算法的描述

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

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

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

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

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

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

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

2.2算法性能分析

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

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

3　實　驗

3.1實驗環(huán)境

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

3.2實驗結果與分析

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

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

4　結束語

本文針對Hadoop框架實現(xiàn)大規(guī)模數(shù)據(jù)處理的排序進行了研究。首先，基于搭建好的Hadoop偽分布式環(huán)境分析了排序算法，提出了改進算法——置換選擇算法，然后運行MapReduce程序比較了在具有相同輸入量的情況下數(shù)據(jù)處理的時間。實驗結果表明，在對相同的較大數(shù)據(jù)量進行排序時，置換選擇算法優(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］．電子學報，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稿件編號：201503462

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

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