MapReduce编程模型

标签: mapreduce 编程 模型 | 发表时间:2014-01-07 15:39 | 作者:tao_sun
出处:http://blog.csdn.net

MapReduce是一个Google发明的编程模型,也是一个处理和生成超大规模数据集的算法模型的相关实现。用户首先创建一个Map函数处理一个基于<Key,Value>对的数据集合,输出的中间结果基于<k,v>对的数据集合,然后再创建一个Reduce函数用来合并所有的具有相同中间Key值的中间Value值。

MapReduce架构的程序可以实现在大量普通配置的设备上实现分布式计算。在Google的集群中,每天都有1000多个MapReduce程序在执行。

例如下面的例子:计算系一个大的文档集合中每个单词出现的次数,伪代码如下:(代码来自Google的论文)

map(String key, String value):
	//key: document name
	//value: document contents
	for each word w in value
		EmitIntermediate(w,"1");

reduce(String key, Iterator values):
	//key: a word
	//values: a list of counts
	int result = 0;
	for each v in values:
		result += ParseInt(v);
	Emit(AsString(result));
Map函数输出文档中的每个单词、以及这个词的出现次数。Reduce函数把Map函数产生的每一个特定的词的计数累加起来。


MapReduce的执行概括:

通过将Map调用的输入数据自动分割为M个数据片断的集合,Map调用被分布到多台机器上执行。输入的数据片断能够在不同的机器上并行处理。使用分区函数将Map调用产生的中间key值分成R个不同的分区(例如,hash(key)mod R),Reduce调用好也被分布到多台机器上执行。分区数量R和分区函数由用户来指定。

下图展示了MapReduce的执行流程:


1)用户程序首先调用MapReduce库将将输入文件分成M个数据片断,每个数据片断的大小一般从16MB到64MB。然后用户程序在集群中创建大量的程序副本。

2)程序副本包括一个Master程序,若干个Worker程序,master负责分配任务,M个map任务,和R个reduce任务。master将一个Map任务或Reduce任务分配给一个空闲的worker。

3)worker程序收到分配到的map任务后将读取相关的数据片断,解析出<k,v>对,然后传递给用户定义的map函数,由map函数生成中间的<k,v>对,并缓存在内存中。

4)缓存中的<k,v>对通过分区函数分成R个区域,然后周期性的写入到本地磁盘中。并且缓存中的<k,v>对在本地磁盘上的存储位置将被回传给master,由master再负责把这些存储位置传送给负责reduce任务的worker们。

5)但负责reduce的worker们收到master程序送来的数据存储位置信息后,使用RPC(远程程序调用)从负责map的woker们所在的主机上的磁盘里读取缓存数据。负责reduce的worker们得到中间数据后,对key进行排序后将具有相同key值的数据聚合在一起。

6)然后reduce worker将按key将中间value值传递给用户自定义的reduce函数。reduce函数的输出被追加到所属分区的输出文件。

7)当所有的map和reduce任务都完成后,master唤醒用户程序。这时,用户程序对MapReduce的调用将返回到用户代码中。


计数器

MapReduce库使用计数器统计不同事件的发生次数。例如,用户可能想统计已经处理了多少个单词,已经索引了多少篇German文章等。为了使用这个特性,用户在程序中创建一个命名的计数器对象,在map和reduce函数中相应的增加计数器的值。例如:

Counter* uppercase;
uppercase = getCounter("uppercase");

map(String name, String contents):
	for each word w in contents:
		if (IsCapitalized(w))
			uppercase->Increment();
		EmitIntermediate(w,"1");

计数器的值周期性的从各个单独的worker机器上传递给master。master把执行成功的Map和Reduce任务的计数器值进行累加,但MapReduce操作完成后,返回给用户代码。计数器对于MapReduce操作的完整性检查非常有用。


作者:tao_sun 发表于2014-1-7 15:39:07 原文链接
阅读:77 评论:0 查看评论

相关 [mapreduce 编程 模型] 推荐:

MapReduce编程模型

- - CSDN博客云计算推荐文章
MapReduce是一个Google发明的编程模型,也是一个处理和生成超大规模数据集的算法模型的相关实现. 用户首先创建一个Map函数处理一个基于对的数据集合,输出的中间结果基于对的数据集合,然后再创建一个Reduce函数用来合并所有的具有相同中间Key值的中间Value值.

Hadoop MapReduce高级编程

- - 互联网 - ITeye博客
•combine函数把一个map函数产生的对(多个key, value)合并成一个新的. 将新的作为输入到reduce函数中,其格式与reduce函数相同. •这样可以有效的较少中间结果,减少网络传输负荷. •什么情况下可以使用Combiner.

MapReduce编程实战之“高级特性”

- - CSDN博客云计算推荐文章
本篇介绍MapReduce的一些高级特性,如计数器、数据集的排序和连接. 计数器是一种收集作业统计信息的有效手段,排序是MapReduce的核心技术,MapReduce也能够执行大型数据集间的“”连接(join)操作. 计数器是一种收集作业统计信息的有效手段,用于质量控制或应用级统计. 计数器还可用于辅助诊断系统故障.

Hadoop MapReduce编程入门案例

- - CSDN博客云计算推荐文章
Hadoop入门例程简析中. (下面的程序下载地址: http://download.csdn.net/detail/zpcandzhj/7810829). (1)Hadoop新旧API的区别. 新的API倾向于使用虚类(抽象类),而不是接口,因为这更容易扩展. 例如,可以无需修改类的实现而在虚类中添加一个方法(即用默认的实现).

MapReuce 编程总结-多MapReduce执行

- - CSDN博客云计算推荐文章
学习hadoop,必不可少的就是写MapReduce程序,当然,对于简单的分析程序,我们只需一个MapReduce就能搞定,这里就不提单MapReuce的情况了,网上例子很多,大家可以百度Google一下. 对于比较复杂的分析程序,我们可能需要多个Job或者多个Map或者Reduce进行分析计算.         多Job或者多MapReduce的编程形式有以下几种:.

MapReduce 编程之 倒排索引

- - CSDN博客云计算推荐文章
本文调试环境: ubuntu 10.04 , hadoop-1.0.2. hadoop装的是伪分布模式,就是只有一个节点,集namenode, datanode, jobtracker, tasktracker...于一体. 本文实现了简单的倒排索引,单词,文档路径,词频,重要的解释都会在代码注视中.

文章: Apache Crunch:用于简化MapReduce编程的Java库

- - InfoQ cn
Apache Crunch(孵化器项目)是基于Google的 FlumeJava库编写的Java库,用于创建MapReduce流水线. 与其他用来创建MapReduce作业的高层工具(如Apache Hive、Apache Pig和Cascading等)类似,Crunch提供了用于实现如连接数据、执行聚合和排序记录等常见任务的模式库.

Mapreduce小结

- MAGI-CASPER/Peter Pan - 博客园-唯有前进值得敬仰
读完mapreduce论文小结一下. 1.MapReduce是一个编程模型,封装了并行计算、容错、数据分布、负载均衡等细节问题. 输入是一个key-value对的集合,中间输出也是key-value对的集合,用户使用两个函数:Map和Reduce. Map函数接受一个输入的key-value对,然后产生一个中间key-value 对的集合.

Hadoop MapReduce技巧

- - 简单文本
我在使用Hadoop编写MapReduce程序时,遇到了一些问题,通过在Google上查询资料,并结合自己对Hadoop的理解,逐一解决了这些问题. Hadoop对MapReduce中Key与Value的类型是有要求的,简单说来,这些类型必须支持Hadoop的序列化. 为了提高序列化的性能,Hadoop还为Java中常见的基本类型提供了相应地支持序列化的类型,如IntWritable,LongWritable,并为String类型提供了Text类型.

MapReduce原理

- - C++博客-牵着老婆满街逛
       MapReduce 是由Google公司的Jeffrey Dean 和 Sanjay Ghemawat 开发的一个针对大规模群组中的海量数据处理的分布式编程模型. MapReduce实现了两个功能. Map把一个函数应用于集合中的所有成员,然后返回一个基于这个处理的结果集. 而Reduce是把从两个或更多个Map中,通过多个线程,进程或者独立系统并行执行处理的结果集进行分类和归纳.