论文部分内容阅读
摘 要： 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
关键词： 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阶段负责将数据按一定规则整理成
针对MapReduce编程模型，目前大多数的研究是在MapReduce编程思想结合现有分布式平台的使用。对于MapReduce自身思想的改进并不很多[5-6]。本文通过分析MapReduce编程模型中Map阶段与Reduce阶段任务的处理过程，发现会存在Key值数量少但Value值数量多的情况，针对此类任务处理的负载不均衡现象，给出一种MapReduce编程模型中key值二次分类的算法，通过增加Key值的标记，使Value值能够更加均匀的分布在集群不同处理节点上，提高了集群节点的利用率与数据处理效率。
1 MapReduce模型
1.1 基本原理
MapReduce编程模型[7-8]是一个处理和生成超大数据集的算法模型的相关实现。此模型首先创建一个Map函数处理一个基于
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任务是将待处理数据处理为为
（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