云计算是并行计算、分布式计算和网格计算的发展。文中详细地阐述了MapReduce的编程思想、工作原理、步骤和方法。探讨了来自Apache开源的分布式计算平台Hadoop的核心设计MapReduce编程模型，并通过算法实验分析和研究了MapReduce模型的工作方式和应用方法。

引言

云计算(Cloud Computing)是一种新兴的商业计算模型。它将计算任务分布在大量计算机构成的资源池上，使各种应用系统能够根据需要获取计算力、存储空间和各种软件服务。云计算是网格计算(Grid Computing)、分布式计算(Distributed Computing)、并行计算(ParallelComputing)、效用计算(Utility Computing)、网络存储(Network Storage Technologies)、虚拟化(Virtualization)，负载均衡(Load Balance)等传统计算机技术和网络技术发展融合的产物。

它的数据存储是采用分布式存储方式实现的，这就可以保证高可靠性、高可用性和经济性，数据存储的高可靠性是采用冗余存储的方式来保证的，用可靠的软件来弥补硬件的不足，从而提供廉价可靠的海量分布式存储服务和计算服务。另外，数据存储技术必须具有高吞吐率和高传输率的特点。这样云计算系统就可同时满足大量用户的需求，才能为大量用户并行地提供服务。云计算的数据存储系统最著名的是谷歌研发的非开源系统GFS(Google File System)和Hadoop开发团队开发的开源系统HDFS(Hadoop Distributed FileSystem)。

1. MapReduce编程模型

并行计算技术是云计算的核心技术，也是最具战性的技术之一。MapReduce是Google公司的核心计算模型，名字源于函数式编程模型中的两项核心操作：Map和Reduce操作。Map操作独立地对每个元素进行操作，且操作没有副作用;Reduce操作对N个Map结果进行归约，也就是Map[1，2.。.，N]的结果是Reduce操作的参数。在一个指令式语言中求值顺序是确定的，每个函数都有可能会变更或依赖于外部状态，所以必须有序地执行这些函数。在MapReduce编程模型中，只要没有函数修改或依赖千全局变量，N个Map操作的执行顺序可以是无序的，这种特性使得MapReduce模型适合于对大规模数据进行并行处理。

在MapReduce计算模型中，有两个关键过程：映射过程Map和聚集过程Reduce。因此需要用户提供两个关键函数，映射(Map)函数和聚集(Reduce)函数，这两个函数对一组输人的键值对(key/value)进行计算，得出另一组输出键值对，即有：

Map：(in_key， in_value)-{(keyj， valuej)j=l.。.k}

Reduce ：(key，[valuel，。..，valuem])一(key， fina_value)

在不同的应用中，Map和Reduce的输人参数和输出结果是不相同的。Map的输入参数in_key和in_value，给S了Map函数要处理的是哪些数据。每个Map函数计算完与后输出结果一组键/值对，它们是经过Mad任务执行完成后所返回的中间结果。系统在执行Reduce任务之前，先检查前面Map任务返回的中间结果，根据Key进行分类处理，把相同key值所对应的value合并在一起把它们送给同一个Reduce任务进行处理，从而可以看出Reduce的输入参数是(key，[ valuel，…，valuem])

Reduc任务主要对这些有着相同key值所对应的value值进行归字处理，在Reduce任务执行完成后输出(key， finaLvalue)的f果。一个key值对应了一个Reduce任务，把所有Reduce千务执行的结果合并连接在一起就形成了最终的输出结果。

典型的MapReduce计算过程如图1

(4)MapReduce库把所有具有相同中间key值I的中间value值集合在一起后传递给reduce函数;

(5)用户自定义的Reduce函数接受一个中间key的值I和相关的一个value值的集合。Reduce函数将这些value值合并成一个较小的value值的集合。正常的，每次Reduce函数调用只产生0或I个输出value值。可以通过一个迭代器把中间value值提供给Reduce函数，这样就可以处理无法全部放入内存中的大量的value值的集合。

2. Hadoop框架的工作机制

Hadoop是Apache软件基金会(Apache SoftwareFoundation)组织下的一个开源项目，提供分布式计算环境下的可靠、可扩展软件。Hadoop平台拥有自己的分布式文件系统(HDFS)，具体实现采用MapReduce模式。Hadoop采取文件备份的方式，为每份数据制作若干拷贝，拥有较高的安全可靠性。作为一个开源的分布式系统平台，Hadoop除了拥有开源所带来的更新速度快、应用广泛等优势外，还具有以下一些其它分布式云计算框架所共有的优点：高度的可扩展性、经济实用性、高速有效性、高可靠性。

HDFS采用Master/Slave架构，一个HDFS集群由一个命名节点((NameNode)和一组数据节点(DataNode)组成。命名节点是一个中心服务器，负责管理文件系统的名字空间(NameSpace)以及客户端对文件的访问。在集群系统中，一般在一个节点上运行一个数据节点，负责管理它所在节点上的数据存储，并负责处理文件系统客户端的读写请求，在命名节点的统一调度下进行数据块的创建、删除和复制。Hadoop还实现了Google的MapReduce分布式计算模型，MapReduce把应用程序的总任务分割成许多子任务，每个子任务可以在任何集群节点(数据节点，通常也作为计算节点)上并行处理。HDFS创建了多份数据块(Data Blocks)的副本(Replicas)，以保证各个子任务节点计算的可靠性((Reliability)。由于采用了分布式文件系统和MapRedace模型，因此Hadoop框架具有高容错性及对数据读写的高吞吐率，能自动处理失败节点。图2是Hadoop集群系统架构的示意图。

由图2可知，HDFS是由一个命名节点和多个数据节点组成的。数据节点存储着文件系统的元数据，它的作用就像是文件系统的总指挥，维护文件系统命名空间、规范客户对于文件的存取和提供对于文件目录的操作，数据节点中存储着实际的数据，负责管理存储节点上的存储空间和来自客户的读写请求。数据节点也执行块创建、删除和来自命名节点的复制命令。

3.算法实例

3.1实验环境

(1)硬件环境配里

根据上面分析的Hadoop架构体系，Hadoop集群可以分成两大类角色：Master和Slave，前者主要配置NameNode和JobTracker节点;后者配置DataNode和TaskTracker节点。例如在我们的实验中，配置Hadoop集群一共有4台PC，一台部署为NameNode和JobTracker，另外两台部署为DataNode和TaskTracker。使用的操作系统为Fedora 8Linux，Java环境为jdk-1.6.0-14， Hadoop版本为Hadoop0.20，并在各节点的//etc/hosts文件中添加节点IP及对应机器名。

如果该台机器作NameNode节点用，则需要在hosts文件中加上集群中所有机器的IP地址及其对应的机器名，例如在我们的实验中，NameNode节点的/etc/hosts文件内容如下：

202.115. 5 .0 lin-1

202.115 。 5 .1 lin-2

202.115. 5 .2 lin-3

202.115. 5. 3 lin-4

如果该台机器作DataNode节点用，则只需要在hosts文件中加上本机IP地址和NameNode节点的IP地址，如：

202.115 .5.0 lin-1

202.115.5.1 lin-2

(2)建立SSH受信证书

在Hadoop启动以后，Namenode通过SSH(SecureShell)来启动和停止各个节点上的各和守护进程，这就需要在节点之间执行指令的时候是不需要输人密码的方式，所以我们需要配置SSH使用无密码公钥认证的方式。

(3) Hadoop平台搭建

①将Hadoop部署至其它主机。

②在Hadoop上格式化一个新的分布式文件系统。

③在Hadoop上启动Hadoop进程。

④启动完成之后，运行ps-ef命令应该可以看到Hadoop上启动了2个新的Java进程(NameNode， JobTracker)，同时，我们可以到Hadoop2等机器上用ps-ef查看，这些机器上应该已经启动了2个新的java进程(DataNode，TaskTracker)

(4)运行Hadoop程序

1)编写完成Map任务的程序，处理输人的KeyValue对，输出中间结果。

2)编写完成Reduce任务的程序，对中间结果进行规约，输出最终结果。

3)定义InputFormat和OutputFormat， InputFormat的主要职责是验证输人的类型是否符合配置类型;

OutputFormat的职责是验证输出目录是否已经存在和输出结果类型是否符合配置类型，如果都成立，则输出Reduce汇总后的结果。

3.2实验结果分析

本实验所用的节点均为同等配置，各节点名分别为master， slave01， slave02， slave03 ， master作为NameNode和JobTracker也参与了计算，所以它也作为DataNode和TaskTracker，而slave01-slave03既作为DataNode也作为TaskTracker。在搭建的Hadoop集群系统上运行了本文开发的并行随机数发生器，实验中线性比作为一个重要的衡量标准，定义如公式3-1：

结果数据如表1所示。

从上表的分析表明：

表1 单机与Hadoop集群性能对比表

(1)单机计算数据规模较大时，算法性能呈现明显的下降趋势。随着输入数据的成倍增长，单机提取算法处理这些输入数据所消耗的时间以更快的速度增长。这是因为单机上随着输人数据的增长，机器上内存等资源消耗过大，致使机器性能明显下降，因而出现算法性能变“慢”的现象。

(2)输入数据量小时，Hadoop集群上并行化算法的处理效率低于单机上非并行化算法的处理效率。这是因为Hadoop集群的启动和交互需要消耗一定的资源。随着输人数据量的增大，Hadoop集群运行速度比单机运行速度明显加快。这是因为随着输人数据量的增大，集群启动与交互的消耗相对于实际业务逻辑的消耗比率大大降低，但是单机资源消耗过快，出现速度瓶颈。

(3)由此可见，MapReduce模型适用于解决具有高度内在并行性的数据密集型并行计算问题。用户只需分解出单个节点应完成的计算单元，按传统串行算法写出计算函数和数据收集函数，在Hadoop平台下就可方便地进行并行计算。Hadoop平台无需用户掌握复杂的消息传递机制的并行程序设计方法，显著简化了并行计算的软件开发难度，有助于普及并行计算。

4.结束语

本文介绍了云计算的定义和关键技术，对云计算环境下的MapReduce并行编程模式进行了研究，分析了MapReduce的编程思想，编程原理和步骤。研究了在架构Hadoop集群的数据分配方式，提出一种基于计算比率的数据分配机制，以提高MapReduce在架构Hadoop集群中的性能。研究为数据挖掘领域相关算法提供了可行的MapReduce化方案，实验结果证明了上述方案的切实有效性。