MapReduce編程模型中key值二次分類算法

劉帥

摘 要： MapReduce編程模型是分布式計算中最常用的編程模型，其主要目的是將單個巨大計算任務(wù)分割成多個小計算任務(wù)，并分別交由不同的計算機去處理。MapReduce將任務(wù)分成map階段和reduce階段，每個階段都是用key/value鍵值對作為輸入和輸出。針對MapReduce中Map數(shù)量少，Reduce數(shù)量多的情況，文章將Map階段任務(wù)中的Key值進行二次劃分，提出一種MapReduce編程模型中Key二次分類的方法。實驗，證明該方法能夠在原有基礎(chǔ)上提高數(shù)據(jù)處理效率。

關(guān)鍵詞： MapReduce； Key/value； 二次分類

中圖分類號：TP301 文獻標(biāo)志碼：A 文章編號：1006-8228（2018）03-58-02

Two times classification algorithm of Key value in MapReduce programming model

Liu Shuai

（Department of Computer Application， Xinzhou Vocational and Technical College， Xinzhou， Shanxi 034000， China）

Abstract： MapReduce programming model is the most commonly used programming model in the distributed computing. It divides a single huge computing task into multiple small computing tasks， which are processed by different computers respectively. MapReduce divides the task into the Map phase and the Reduce phase， each of which is used as input and output with the key/value key value pair. In view of the fact that the number of Map in MapReduce is small and the number of Reduce is large， the Key value of Map phase task is divided in two times， and a method of two times classification of Key value in MapReduce programming model is proposed. Experiments show that the method can improve the efficiency of data processing on the original basis.

Key words： MapReduce； Key/Value； two times classification

0 引言

MapReduce是由google公司提出的一種并行計算框架[1-2]，其“分而治之”的思想被廣泛用于Hadoop與Spark分布式計算平臺。MapReduce處理任務(wù)過程中，將任務(wù)分為Map階段與Reduce階段，Map階段負責(zé)將數(shù)據(jù)按一定規(guī)則整理成鍵值對的形式，Reduce階段負責(zé)將相同Key值的鍵值對進行規(guī)約處理，從而使任務(wù)相對獨立，方便于進行分布式處理[3-4]。

針對MapReduce編程模型，目前大多數(shù)的研究是在MapReduce編程思想結(jié)合現(xiàn)有分布式平臺的使用。對于MapReduce自身思想的改進并不很多[5-6]。本文通過分析MapReduce編程模型中Map階段與Reduce階段任務(wù)的處理過程，發(fā)現(xiàn)會存在Key值數(shù)量少但Value值數(shù)量多的情況，針對此類任務(wù)處理的負載不均衡現(xiàn)象，給出一種MapReduce編程模型中key值二次分類的算法，通過增加Key值的標(biāo)記，使Value值能夠更加均勻的分布在集群不同處理節(jié)點上，提高了集群節(jié)點的利用率與數(shù)據(jù)處理效率。

1 MapReduce模型

1.1 基本原理

MapReduce編程模型[7-8]是一個處理和生成超大數(shù)據(jù)集的算法模型的相關(guān)實現(xiàn)。此模型首先創(chuàng)建一個Map函數(shù)處理一個基于鍵值對的數(shù)據(jù)集合，輸出中間的基于鍵值對的數(shù)據(jù)集合；然后再創(chuàng)建一個Reduce函數(shù)用來合并所有的具有相同中間key值的中間value值?；贛apReduce架構(gòu)所設(shè)計的程序能夠在大量的普通配置的計算機上實現(xiàn)數(shù)據(jù)的并行化處理，并且處理過程著重于輸入數(shù)據(jù)分割、任務(wù)調(diào)度、容錯處理和計算機通信管理等。

1.2 處理過程

圖1 MapReduce處理過程

MapReduce編程模型中，Map與Reduce處理過程如圖1所示。若有多個任務(wù)等待處理，Map任務(wù)的主要功能是將數(shù)據(jù)處理成以“key=n”為基礎(chǔ)的鍵值對的形式（以key=1和key=2為例），Reduce任務(wù)的主要功能是將不同Key的鍵值對進行整合。則有如下定義。

定義1 若不同key值為基礎(chǔ)的鍵值對數(shù)量相差不大，則執(zhí)行Reduce任務(wù)的計算節(jié)點的負載相差不大，稱為集群呈負載均衡狀態(tài)（LBS狀態(tài)），反之則稱為集群呈負載不均衡狀態(tài)（LIS狀態(tài)）。

2 key值二次分類

2.1 key值傳統(tǒng)分類（TC）

在傳統(tǒng)MapReduce編程模型中，Map任務(wù)是將待處理數(shù)據(jù)處理為為鍵值對的形式，而Reduce任務(wù)是收集具有相同key值的鍵值對，并對分別其進行處理。當(dāng)不同key值對應(yīng)的value值的個數(shù)相差很大時，會出現(xiàn)數(shù)據(jù)分布不均勻的情況。

{value1，value2，value3，…valuen}>（n為10^3數(shù)量級）

{value1，value2，value3，…valuem}>

（m為10^9數(shù)據(jù)量級）

明顯地，key1所對應(yīng)的value數(shù)據(jù)量遠小于key2所對應(yīng)的value數(shù)據(jù)量。數(shù)據(jù)處理過程中，key值往往選擇明顯區(qū)分的標(biāo)記，而不會對key的值進行改變，因此在分布式處理過程常存在LIS狀態(tài)。

2.2 二次分類（TTC）

雖然MapReduce框架只能機械地按key值對數(shù)據(jù)進行劃分，然而，在Map過程之后，檢測到同一key值的value數(shù)據(jù)量（N）超過閾值ε，則對該key值添加二級標(biāo)號（例如key1，會轉(zhuǎn)化為key11，key12，…，key1n），進行二次分類，使得所有key值具有相似數(shù)量的value數(shù)據(jù)量，集群呈LBS狀態(tài)。

其主要過程如下。

Step1：輸入數(shù)據(jù)集DS，設(shè)計Map函數(shù)，將數(shù)據(jù)集處理為鍵值對。

Step2：設(shè)計Reduce函數(shù)，計算每個key值所對應(yīng)的value值數(shù)據(jù)量；選出所有key值中，value數(shù)據(jù)量的最大值Max所對應(yīng)的key。

Step3：設(shè)計Map函數(shù)，將具有Max的key值做二級標(biāo)記，進行二次劃分。

Step4：若value數(shù)據(jù)量N>ε，返回Step3。

3 實驗結(jié)果及分析

3.1 實驗準備

實驗選用CentOS6.1系統(tǒng)，Hadoop2.7.1作為實驗平臺，算法實現(xiàn)使用Java語言編寫。分別使用Abalone數(shù)據(jù)集、Arrhythmia數(shù)據(jù)集、Chess數(shù)據(jù)集、Multiple數(shù)據(jù)集作為處理對象，分別使用TC思想與TTC思想實現(xiàn)最大值算法。

3.2 實驗結(jié)果及分析

不同數(shù)據(jù)集在兩種不同思想算法下的時間開銷如表1所示。

表1 時間開銷

[數(shù)據(jù)集 時間開銷T（s） TC TTC Abalone 29.2 20.3 Arrhythmia 24.6 16.2 Chess 13.4 8.4 Multiple 100.6 76.4 ]

由實驗結(jié)果可以得出，TTC算法比TC算法效率高，大約節(jié)省30%的時間。因此，TTC算法彌補了傳統(tǒng)MapReduce編程模型中對key值分類的不足，使集群盡量趨于LBS狀態(tài)，對于分布式計算性能的提升提供了一種較為有效的借鑒方案。

參考文獻（References）：

[1] Kumar R， Moseley B， Vassilvitskii S， et al. Fast Greedy

Algorithms in MapReduce and Streaming[J]. Acm Transactions on Parallel Computing，2015.2（3）：14

[2] 張衛(wèi)平，劉紀平，仇阿根等.一種分布式計算的空間離群點挖

掘算法[J].測繪科學(xué)，2017.42（8）：85-90

[3] 潘景昌，王杰，姜斌等.一種基于Map/Reduce分布式計算的

恒星光譜分類方法[J].光譜學(xué)與光譜分析，2016.36（8）：2651-2654

[4] Verma A， Cherkasova L， Campbell R H. Resource

Provisioning Framework for MapReduce Jobs with Performance Goals[J]. Lecture Notes in Computer Science，2015.7049：165-186

[5] 李成華，張新訪，金海等.MapReduce：新型的分布式并行計算

編程模型[J].計算機工程與科學(xué)，2011.33（3）：129-135

[6] 盧鑫，陳華輝，董一鴻等.MapReduce框架下的不確定數(shù)據(jù)

Top-k查詢計算[J].模式識別與人工智能，2013.26（7）：688-694

[7] 翟俊海，張明陽，王婷婷等.基于哈希技術(shù)和MapReduce的大

數(shù)據(jù)集K-近鄰算法[J].計算機科學(xué)，2017.44（7）：210-214

[8] 毛典輝.基于MapReduce的Canopy-Kmeans改進算法[J].

計算機工程與應(yīng)用，2012.48（27）：22-26