Map Reduce

Map Reduce是一种编程模型，是一种可以处理和生成超大数据集的算法模型。它通过指定一个Map函数处理分布式的基于key/value对的数据集合，输出基于key/value对的中间数据集；然后使用一个reduce函数在分布式的机器上合并上一步中间集合具有相同key的value。

例子

计算一个大文档集合每个单词出现的次数

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     (k1,v1)       ->list(k2,v2) 
reduce  (k2,list(v2)) ->list(v2)

实现原理

mr-arch

• 输入集合自动分割成M个数据片段的集合
• master节点把Map函数分发到多台worker机器上执行
• master通知Map worker需要读取的文件
• Map worker读取分配给自己的输入文件，并调用map函数
• map函数输入中间结果，并把结果切分成R个分片和保存到磁盘，并把中间结果的路径通知master
• master把reduce函数分配到若干个worker机器，并分配数据分片给reduce worker
• Reduce worker从多个R个分片的中间结果中读取自己的分片，并调用reduce函数
• Reduce输出最终结果到文件

容错

worker失效

master周期的ping每个worker。如果在约定时间内ping失败，master会把worker标志为失效。失效的worker相关的任务标志为空闲，此后这些任务会安排其他worker执行。

当Map worker失效，由于输出是存在本地磁盘，失效后会导致map的输出不可访问，因此需要重新执行，没有此前输出的reduce worker会从新worker中读取分片并处理

当Reduce worker失效，如果worker已经执行完毕，由于输出存在hdfs上，因此不必重复执行reduce；如果没有执行完毕，则需要重新调度

master失效

master拥有WAL，通过WAL重启master进程，可以让任务继续；

或者可以重新执行map reduce操作。

任务执行位置

worker会安排在数据机器或者靠近数据的机器上执行，以减少网络上大量的网络数据拷贝

后备任务

在大规模执行worker的时候，难免有些机器由于各种不可预知的因素导致执行过慢，导致整个任务执行时间过长。

后备任务通过对某些执行过长的worker分配另外一台worker执行相同的任务，取最先完成任务的结果为最终数据。

分区函数

map输出的默认分区函数是对key进行hash。

当对于某些特定任务，用户可以自定义分区函数，把同一类的key分配到相同的reduce函数中处理

key排序

map输出的key/value pair，是对key排序的文件

合并函数

由于map输出的中间结果有大量相同的key，如果等到reduce执行的时候才把相同的key合并，会带来严重的网络开销。

合并函数通过在map完后，在本地执行合并操作，并输出R个分片的数据。这样当reduce函数取中间结果的时候，网络的开销将会大大减少

忽略坏记录

当worker处理文件时，难免会遇到不可预知的数据

此时worker有可能发生crash。

此时Map Reduce提供一种模式，在此模式下，会忽略crash的记录，并处理到最后一条记录