谭浩的博客

Simple is beauty.

理解MapReduce

基本介绍

MapReduce是一种编程模型,用于简化集群上的数据处理。用户使用一个 map 函数处理一个键值对产生一系列中间键值对,使用 reduce 函数将相同的中间键的值合并处理。按照此种方式编写的程序可以自动地在多机上并行执行。

编程模型

Mapreduce 库将计算过程分为两个函数:MapReduce

这两个函数都由用户进行定义,Map 函数接收一个输入对,产生一系列中间键值对。 Mapreduce 库将中间键相同的值发送给同一个 Reduce 函数。Reduce 函数接收一个中间键和与其关联的值作为输入,它合并这些值为更小的值。且这些值以迭代器的方式传递给 Reduce 函数,从而使其能够处理超过内存容量的数据。

单词计数

考虑一个处理大量文件的单词计数的问题,则用户需要编写以下格式的伪代码:

1
2
3
4
5
6
7
8
9
map(String key, String value):
for each word w in value:
EmitIntermediate(w, "1");

reduce(String key, Iterator values):
int result = 0;
for eache v in values:
result += ParseInt(v);
Emit(AsString(result));

面向多机环境的实现

Mapreduce 接口的实现是可以多种多样的,Google 的 Mapreduce 实现则是面向 google 内部的使用环境的:以以太网交换机连接的普通商用 PC 机集群。

编程模型的加强

应用场景

它将计算过程表达为两个部分,Map和Reduce。这两个功能都需要用户自己编写和定义:

  • Map:接受一个输入对,处理之后产生一系列中间键值对。
  • Reduce:接受一个键和该键的对应的一系列值,并将值合并成为一个更小系列的值。中间键值对在提供给Reduce时会使用迭代器,这样可以允许处理无法再内存中储存的大数据集。

考虑统计一系列文档中的单词词频。则Map,Reduce的伪代码如下:

1
2
3
4
5
6
7
8
9
10
11
map(String key, String value):
//key: 文档名
//value: 文档内容
for each word w in value:
EmitIntermediate(w, '1')

reduce(String key, Iterator values):
result = 0
for eache v in values:
result += parseInt(v)
Emit(str(result))

MapReduce执行流程

MapReduce执行流程

  • 用户程序通过MapReduce库将输入文件分割成M份,每份大小为16MB到64MB,这个大小可以由用户通过可选参数设置,然后在一些机器启动运行用户程序的副本。
  • 这些程序副本中有一个是特殊的,称为master。其余的worker由master分配任务。一共有M个map任务和R个Reduce任务,master选取空闲的worker并给每一个worker分配一个map或者reduce任务。
  • 被分配map的worker读取相应分块的内容,解析输入内容获取key/value对传递给用户定义的Map函数。由map函数处理得到的中间键值对缓存在内存中。
  • 缓存对定期写入本地磁盘,被分区函数分成R个区。这些缓存对的地址被传送给master,并由master转发给Reduce worker。
  • 当Reduce worker被告知缓存对的地址后,它使用远程过程调用从map workers的磁盘地址读取缓存对。当Reduce worker读取了所有的中间数据,它将数据通过中间键排序把相同键的值聚合在一起。当中间数据太大时需要使用外排序。
  • Reduce worker遍历已经排序的中间数据,对于每一个唯一的键,它将键和相应的一系列值传递给用户自定义的Reduce函数。Reduce函数的输出值将被添加到该Reduce分区的输出文件中。
  • 当所有的map和Reduce工作结束后,master唤醒用户程序。此时,用户程序中的MapReduce调用返回用户代码。

当一切成功结束后,将会产生R份输出文件,通常这些输出文件可以作为另一个MapReduce过程的输入。

Master数据结构
master存储每一个map和Reduce任务的状态(空闲,处理中,已完成)以及每一个空闲的worker机器。

容错机制

  • worker失败
    master定期ping worker,如果worker没有在固定时间回应,则master则将该worker标记为失败。每一个完成的worker以及失败的worker都被重置为空闲状态。worker故障时,map任务的输出不可访问需要重新执行map任务,Reduce任务的输出存储在全局文件上不需要再次执行。
  • master失败
    定期地将master上的数据结构写入磁盘中去,即检查点。master任务失败时则从最近的检查点处重新启动一个master进程。