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

劉帥

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

關鍵詞： MapReduce； Key/value； 二次分類

中圖分類號：TP301 文獻標志碼：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處理任務過程中，將任務分為Map階段與Reduce階段，Map階段負責將數據按一定規則整理成鍵值對的形式，Reduce階段負責將相同Key值的鍵值對進行規約處理，從而使任務相對獨立，方便于進行分布式處理[3-4]。

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

1 MapReduce模型

1.1 基本原理

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

1.2 處理過程

圖1 MapReduce處理過程

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

定義1 若不同key值為基礎的鍵值對數量相差不大，則執行Reduce任務的計算節點的負載相差不大，稱為集群呈負載均衡狀態（LBS狀態），反之則稱為集群呈負載不均衡狀態（LIS狀態）。

2 key值二次分類

2.1 key值傳統分類（TC）

在傳統MapReduce編程模型中，Map任務是將待處理數據處理為為鍵值對的形式，而Reduce任務是收集具有相同key值的鍵值對，并對分別其進行處理。當不同key值對應的value值的個數相差很大時，會出現數據分布不均勻的情況。

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

{value1，value2，value3，…valuem}>

（m為10^9數據量級）

明顯地，key1所對應的value數據量遠小于key2所對應的value數據量。數據處理過程中，key值往往選擇明顯區分的標記，而不會對key的值進行改變，因此在分布式處理過程常存在LIS狀態。

2.2 二次分類（TTC）

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

其主要過程如下。

Step1：輸入數據集DS，設計Map函數，將數據集處理為鍵值對。

Step2：設計Reduce函數，計算每個key值所對應的value值數據量；選出所有key值中，value數據量的最大值Max所對應的key。

Step3：設計Map函數，將具有Max的key值做二級標記，進行二次劃分。

Step4：若value數據量N>ε，返回Step3。

3 實驗結果及分析

3.1 實驗準備

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

3.2 實驗結果及分析

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

表1 時間開銷

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

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

參考文獻（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] 張衛平，劉紀平，仇阿根等.一種分布式計算的空間離群點挖

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

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

恒星光譜分類方法[J].光譜學與光譜分析，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].計算機工程與科學，2011.33（3）：129-135

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

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

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

數據集K-近鄰算法[J].計算機科學，2017.44（7）：210-214

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

計算機工程與應用，2012.48（27）：22-26