MapReduce

MapReduce是一种分布式计算模型，是Google提出的，主要用于搜索领域，解决海量数据的计算问题。
MR有两个阶段组成：Map和Reduce，用户只需实现map()和reduce()两个函数，即可实现分布式计算。
应用例子：词频统计（Word Count）
写一个简单的MapReduce程序就可以用来统计不同的词在一个文件集中出现的次数。
比如，我们有这样的文件：
foo.txt: Sweet, this is the foo file
bar.txt: This is the bar file
我们期望输出会是这样子：
sweet 1
this 2
is 2
the 2
foo 1
bar 1
file 2
当然没问题，我们可以写一个 MapReduce 程序来计算得到这个输出。高层结构看起
来会是这样子：
mapper (filename, file-contents):
for each word in file-contents:
emit (word, 1)
reducer (word, values):
sum = 0
for each value in values:
sum = sum + value
emit (word, sum)
列表 4.1 MapReduce 词频统计伪代码
若干个 mapper 函数的实例会被创建在我们的集群的不同机器上，每个实例接收一个
不同的输入文件（这里假设我们有很多个文件）。 mappers 输出的（word， 1）键值对会
被转到 reducers 那里去。若干个 reducer 方法实例也会在不同机子上被实例化。每个
reducer 负责处理关联到不同词的数值列表，数值列表中的值都是 1； reducer 把这些“1”
值总和到一个关联了某个词的最终计数里。 reducer 然后生成最终的（word， count）输
出，并把它写到一个输出文件里。
Hadoop 自带了好几个输入格式。其中有一个抽象类叫 FileInputFormat，所有操作
文件的 InputFormat 类都是从它那里继承功能和属性。当开启 Hadoop 作业时，
FileInputFormat 会得到一个路径参数，这个路径内包含了所需要处理的文件，
FileInputFormat 会读取这个文件夹内的所有文件（译注：默认不包括子文件夹内的），
然后它会把这些文件拆分成一个或多个的 InputSplit。你可以通过 JobConf 对象的
setInputFormat()方法来设定应用到你的作业输入文件上的输入格式。
输入块（InputSplit）：一个输入块描述了构成 MapReduce 程序中单个 map 任务的一个单元。把一个 MapReduce 程序应用到一个数据集上，即是指一个作业，会由几个（也可能几百个）任务组成。
记录读取器（RecordReader）： InputSplit 定义了如何切分工作，但是没有描述
如何去访问它。 RecordReader 类则是实际的用来加载数据并把数据转换为适合 mapper读取的键值对。 RecordReader 实例是由输入格式定义的，默认的输入格式，
Partition & Shuffle：当第一个 map 任务完成后，节点可能还要继续执行更多的
map 任务，但这时候也开始把 map 任务的中间输出交换到需要它们的 reducer 那里去，
这个移动 map 输出到 reducer 的过程叫做 shuffle。每一个 reduce 节点会分派到中间输
出的键集合中的一个不同的子集合，这些子集合（被称为“partitions”）是 reduce 任务的
输入数据。每一个 map 任务生成的键值对可能会隶属于任意的 partition，有着相同键的
数值总是在一起被 reduce，不管它是来自那个 mapper 的。因此，所有的 map 节点必须
就把不同的中间数据发往何处达成一致。 Partitioner 类就是用来决定给定键值对的去向，
默认的分类器（partitioner）会计算键的哈希值并基于这个结果来把键赋到相应的
partition 上，自定义的分类器在第五部分有详细描述。
排序：每一个 reduce 任务负责归约（reduceing）关联到相同键上的所有数值，每一
个节点收到的中间键集合在被送到具体的 reducer 那里前就已经自动被 Hadoop 排序过了。
归约（Reduce）：每个 reduce 任务都会创建一个 Reducer 实例，这是一个用户自
定义代码的实例，负责执行特定作业的第二个重要的阶段。对于每一个已赋予到 reducer
的 partition 内的键来说， reducer 的 reduce()方法只会调用一次，它会接收一个键和关
联到键的所有值的一个迭代器，迭代器会以一个未定义的顺序返回关联到同一个键的值。
reducer 也要接收一个 OutputCollector 和 Report 对象，它们像在 map()方法中那样被
使用。

相关推荐