MapReduce简介

MapReduce简介

最近测试到了一个用到Hadoop的项目，略有接触，稍有了解，总结了这么篇日志。

一个Map/Reduce作业（job）通常会把输入的数据集切分为若干独立的数据块，由map任务（task）以完全并行的方式处理它们。框架会对map的输出先进行排序，然后把结果输入给reduce任务。通常作业的输入和输出都会被存储在文件系统中。整个框架负责任务的调度和监控，以及重新执行已经失败的任务。[2][6]

Mapper将输入键值对(key/value pair)映射到一组中间格式的键值对集合。

Map是一类将输入记录集转换为中间格式记录集的独立任务。这种转换的中间格式记录集不需要与输入记录集的类型一致。一个给定的输入键值对可以映射成0个或多个输出键值对。

Reducer将与一个key关联的一组中间数值集归约（reduce）为一个更小的数值集。[2]

MapReduce架构中的Reduce这一步分为Shuffle、Sort、Reduce这三步。[2]

所以放在Hadoop上运行的批处理作业必须要能够用MapReduce这种算法架构来处理。

MapReduce是一个编程模式，最初似乎起源于函数式编程语言。

Map就是把一个操作施加到一个列表的每个元素上，得到一个列表，许多程序设计语言里都有map这样的函数[10]，

Reduce更像是一个Merge的过程[11]，具体解释可以参考[6]。

MapReduce最常用来示范的例子就是求一段文本中的词频，Hadoop自带的示例叫做WordCount，求词频就是用Map操作把输入的文本看作一个一个词组成的列表，映射成<词，1>这样的中间结果，然后经过sort使得同一词的记录彼此相邻(实际上在Hadoop的Reduce的Shuffle这一步就已经做到了)，再在reduce这一步里将词频累计起来，成为<词，词频>这样的记录(一个用Python写的示例可以参考[9])。

在Hadoop上执行的程序实际上和下述命令是几乎一样的：

cat INPUT_DATA | perl map_script.pl | sort | perl reducer_script.pl > OUTPUT_DATA

采用hadoop的话可以更好的分发到节点机器上运行，利用集群的运算资源，

而且在HDFS的文件系统上，可以更好地可靠容错地处理大数据量的文件。

当然也有人对MapReduce架构不以为然，认为这个软件不过是能够组建一个多节点集群用多个低配置机器完成巨量的运算。

而MapReduce的架构使得它只能蛮力进行遍历计算，不能像数据库那样利用索引等高级技术提高计算效率[5]。

reference:

1, [Hadoop快速入门]

2, [Hadoop Map/Reduce教程]

3, [Hadoop Streaming]

4, http://blog.sina.com.cn/s/blog_62a9902f0100gs4q.html [MapReduce: 一个巨大的倒退] (此为转帖，原帖所在网站被封禁)

5, [命令手册]

6, http://developer.yahoo.com/hadoop/tutorial/module4.html [yahoo Hadoop MapReduce 讲解]

7, http://developer.yahoo.com/hadoop/tutorial/ [Yahoo! Hadoop Tutorial]

8, [Hadoop Wiki]

9, [Writing An Hadoop MapReduce Program In Python]

10, [Map函数]

11, [common lisp reduce函数]

12, [水木上的讨论帖]