分布式数据库大作业Hadoop MapReduce云计算模型研究学院: 软件学院专业: 软件工程2014年01月02日大连理工大学Hadoop MapReduce云计算模型研究1.引言Hadoop[1]就是一个分布式系统基础架构,由Apache基金会开发。

用户可以在不了解分布式底层细节的情况下,开发分布式程序。

充分利用集群的威力高速运算与存储。

简单地说来,Hadoop就是一个可以更容易开发与运行处理大规模数据的软件平台。

其包括两个部分:HDFS[2]与MapReduce[3]。

DFS即HadoopDistributed(Hadoop分布式文件系统),HDFS具有高容错性,并且可以被部署在低价的硬件设备之上。

HDFS很适合那些有大数据集的应用,并且提供了对数据读写的高吞吐率。

HDFS就是一个master/slave的结构,就通常的部署来说,在master上只运行一个Namenode,而在每一个slave上运行一个Datanode。

HDFS支持传统的层次文件组织结构,同现有的一些文件系统在操作上很类似,比如您可以创建与删除一个文件,把一个文件从一个目录移到另一个目录,重命名等等操作。

Namenode管理着整个分布式文件系统,对文件系统的操作(如建立、删除文件与文件夹)都就是通过Namenode来控制[4]。

MapReduce就是由Google提出的一种并行分布式编程模型[5-7]。

用以进行大数据量的计算。

对于大数据量的计算,通常采用的处理手法就就是并行计算。

至少现阶段而言,对许多开发人员来说,并行计算还就是一个比较遥远的东西。

MapReduce就就是一种简化并行计算的编程模型,它让那些没有多少并行计算经验的开发人员也可以开发并行应用。

MapReduce的名字源于这个模型中的两项核心操作:Map与Reduce。

也许熟悉FunctionalProgramming(函数式编程)的人见到这两个词会倍感亲切。

简单的说来,Map就是把一组数据一对一的映射为另外的一组数据,其映射的规则由一个函数来指定,比如对[1,2,3,4]进行乘2的映射就变成了[2,4,6,8]。

Reduce就是对一组数据进行归约,这个归约的规则由一个函数指定,比如对[1,2,3,4]进行求与的归约得到结果就是10,而对它进行求积的归约结果就是24。

2.MapReduce的基本原理MapReduce就是云计算的核心技术之一,它为并行系统的数据处理提供了一个简单、优雅的解决方案。

其主要目的就是为了大型集群的系统能在大数据集上进行并行工作,并用于大规模数据的并行运算。

Divide and Conquer”就是Mapreduce的核心思想[8]。

面对一个规模庞大的问题,要处理就是以TB计的数据,Mapreduce采用“输入”------“分解”------“解决”------“聚合”------“输出结果”的基本过程。

在MapRedcue 模型中用户只须指定一个map函数来处理一个输入的key/value对,产生中间结果key/value对集,再通过一个由用户指定的reduce函数来处理中间结果中具有相同key值的value。

适合用MapReduce 来处理的数据集(或任务)有一个基本要求: 待处理的数据集可以分解成许多小的数据集,而且每一个小数据集都可以完全并行地进行处理[9-10]。

MapReduce通过把对数据集的大规模操作分发给网络上的每个节点实现可靠性;每个节点会周期性的把完成的工作与状态的更新报告回来。

如果一个节点保持沉默超过一个预设的时间间隔,主节点(类同Google 中的主服务器)记录下这个节点状态为死亡,并把分配给这个节点的数据发到别的节点。

每个操作使用命名文件的原子操作以确保不会发生并行线程间的冲突;当文件被改名的时候,系统可能会把她们复制到任务名以外的另一个名字上去。

(避免副作用)。

化简操作工作方式很类似,但就是由于化简操作在并行能力较差,主节点会尽量把化简操作调度在一个节点上,或者离需要操作的数据尽可能近的节点上了;这个特性可以满足Google的需求,因为她们有足够的带宽,她们的内部网络没有那么多的机器。

在Google,MapReduce用在非常广泛的应用程序中,包括“分布grep,分布排序,web连接图反转,每台机器的词矢量,web访问日志分析,反向索引构建,文档聚类,机器学习,基于统计的机器翻译、、、”值得注意的就是,MapReduce实现以后,它被用来重新生成Google的整个索引,并取代老的ad hoc程序去更新索引。

MapReduce会生成大量的临时文件,为了提高效率,它利用Google文件系统来管理与访问这些文件。

3.框架的结构与工作流程Mapreduce框架的主要程序分为三种即Master,Map与Reduce。

Master的主要功能有两个,任务的分割与任务的调度。

Master把输入文件切成许多个split,每个split文件一般为几十M。

Master同时还要调度任务监视各个map worker与reduce worker的工作状态,以做出相应的安排。

Master还要监视各个子任务的完成进展情况。

Map的主要功能就是读取经过切割split文件形成一个map任务,分析map任务,得到中间结构并且将同一类型的中间文件存放在同一个区域内等待特定的reduce程序读取。

另外不同的Reduce读取各个Map得到的特定的中间文件,将所有相同的中间文件整合成最后的输出文件。

说明:1、单向箭头表示控制,双向箭头表示控制与反馈2、某些操作中Mapworker硬盘上的key/value在被Reducerworker读取之前可以有combine 操作,将相同key的value合并以减少读取次数3、分散的输出文件也可以合并成一个输出文件而对于有些操作如求最大值则必须合并输出文件才能得到最终结果。

首先输入收据文件被Mapreduce库函数分割成M个split集。

用户定义的程序被拷贝到机群中,其中一个就是master,其它的都就是worker。

M个map任务与R个reduce任务将被分配。

Master负责调度任务与过程监视。

随时检测worker 的工作状况,任务的完成进度。

Map worker每完成一个子任务向master报告。

一个被分配了map任务的worker读取一个split集,该worker从这个split 集中分析出key/value对,然后有map函数来处理这些key/value对并得到中间key/value对,这些key/value对将最终存放在map worker的本地硬盘上。

每完成一个任务报告master。

中间key/value对被存在本地硬盘的R个不同的区域中,由于可能的key值很可能不止R个,故必须利用一个分割函数来划分中间文件,常用的就是散列的方法(如hash(key) mod R)。

保证key值相同的key/value对被存放同一区域中,并且将位置报告给master。

如果同一个key的中间文件多而小可以考虑用cmobine函数在本地进行合并。

当所有的split都被分析完成之后,reduce worker开始工作,每个reduce 根据master的安排与信息指示利用机群的内部文件系统读取map worker本地磁盘中特定位置的中间文件。

Reduce开始聚合中间文件,得到自己的输出文件。

在聚合的过程中由于有很多key值,一般将用到排序。

Reduce worker完成自己的工作后向master报告。

4.实验及测试本文选取了三台Ubuntu虚拟机模拟分布式环境,搭建并完成了Hadoop自带的wordcount程序的测试。

搭建环境如下:Ubuntu10、10、Hadoop1、0、4、jdk1、6、0_30Namenode:UB01(ip:192、168、1、106)Datanode:UB02(ip:192、168、1、104) UB03(ip:192、168、1、107)按如下步骤进行配置,此过程参考了文献[11]、[12]。

（1）配置NameNode与DataNode修改每台机器的/etc/hosts(包括namenode与datanode)如下:127、0、0、1 localhost、localdomain localhost192、168、1、106 UB01192、168、1、104 UB02192、168、1、107 UB03::1 localhost6、localdomain6 localhost6(2) 在所有的机器上建立相同的用户useradd peterpasswd 123456输入密码后即可成功建立并设置peter用户与密码。

(3) SSH设置由于启动hadoop时及任务执行过程中需要远程访问各主机,因此为了避免多次输入密码,应首先配置各主机的SSH使其能免输入的登录其她主机。

配置如下:在所有机器的/home/peter目录下ssh-keygen -t rsa //一路回车到底cd 、ssh然后在UB01上执行:scp id_rsa、pub peter@UB02:/home/peter/、ssh/id_rsa、pub、UB01 scp id_rsa、pub peter@UB03:/home/peter/、ssh/id_rsa、pub、UB01 在UB02上执行:scp id_rsa、pub peter@UB01:/home/peter/、ssh/id_rsa、pub、UB02 scp id_rsa、pub peter@UB03:/home/peter/、ssh/id_rsa、pub、UB02 在UB03上执行:scp id_rsa、pub peter@UB01:/home/peter/、ssh/id_rsa、pub、UB03 scp id_rsa、pub peter@UB02:/home/peter/、ssh/id_rsa、pub、UB03 这样就把各自的密钥文件全部拷贝到每台机器上了,然后:在UB01上执行:cat id_rsa、pub id_rsa_pub、UB02 id_rsa、pub、UB03 >> authorized_keys在UB02上执行:cat id_rsa、pub id_rsa_pub、UB01 id_rsa、pub、UB03 >> authorized_keys在UB03上执行:cat id_rsa、pub id_rsa_pub、UB02 id_rsa、pub、UB01 >> authorized_keys 这样向其她机器发起SSH连接,只有第一次登录时需要输入密码,以后就不需要。

(4) 在所有机器上安装JDK下载并解压jdk1、6、0_30到/usr/develop目录下,然后在/etc/profile 最后追加下面内容:JAVA_HOME=/usr/develop/jdk1、6、0_30export JRE_HOME=/usr/develop/jdk1、6、0_30/jreexport CLASSPATH=、:$JAVA_HOME/lib:$JRE_HOME/lib:$CLASSPATHexport PATH=$JAVA_HOME/bin:$JRE_HOME/bin:$PATH保存退出,然后执行source /etc/profile即可。