vlambda博客
学习文章列表

大家好，我是勾叔。今天整理了MapReduce的资料，分享给大家。

• 写一个小程序。把论文按序遍历一遍，统计遇到单词的出现次数，确认热门单词。

• 写一个多线程程序，并发遍历论文。

• 把作业交给多个计算机完成。使用方法一的程序，部署到N台机器上去，把论文集分成N份，一台机器跑一个作业。

• 让MapReduce来帮帮我们！

• map函数：接受一个键值对（key-value pair），产生一组中间键值对。MapReduce框架会将map函数产生的中间键值对里键相同的值传递给一个reduce函数。

• reduce函数：接受一个键，以及相关的一组值，将这组值进行合并产生一组规模更小的值（通常只有一个或零个值）。

  
  

仍以统计词频为例来讲解。

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

reduce(String key, Iterator values):// key: a word// values: a list of countsint result = 0;for each v in values:result += ParseInt(v);Emit(AsString(result));

• MapReduce库先把user program的输入文件划分为M份（M为用户定义），每一份通常有16MB到64MB。
  

• user program副本中有一个称为master，其余称为worker，master是负责调度的，为空闲worker分配作业（Map作业或者Reduce作业），worker的数量也是可以由用户指定的。
  

• 被分配了Map作业的worker，开始读取对应分片的输入数据，Map作业数量是由M决定的，和split一一对应；Map作业从输入数据中抽取出键值对，每一个键值对都作为参数传递给map函数，map函数产生的中间键值对被缓存在内存中。
  

• 缓存的中间键值对会被定期写入本地磁盘，而且被分为R个区，R的大小是由用户定义的，将来每个区会对应一个Reduce作业；这些中间键值对的位置会被通报给master，master负责将信息转发给Reduce worker。
  

• master通知分配了Reduce作业的worker它负责的分区在什么位置（不止一个位置，每个Map作业产生的中间键值对都可能映射到所有R个不同分区），当Reduce worker把所有它负责的中间键值对都读过来，先进行排序使得相同键的键值对聚集在一起。），排序是必须的。
  

• reduce worker遍历排序后的中间键值对，对于每个唯一的键，都将键与关联的值传递给reduce函数，reduce函数产生的输出会添加到这个分区的输出文件中。
  

• 当所有的Map和Reduce作业都完成了，master唤醒正版的user program，MapReduce函数调用返回user program的代码。
  

• 所有执行完毕后，MapReduce输出放在了R个分区的输出文件中（分别对应一个Reduce作业）。用户通常并不需要合并这R个文件，而是将其作为输入交给另一个MapReduce程序处理。整个过程中，输入数据是来自底层分布式文件系统（GFS）的，中间数据是放在本地文件系统的，最终输出数据是写入底层分布式文件系统（GFS）的。而且我们要注意Map/Reduce作业和map/reduce函数的区别：Map作业处理一个输入数据的分片，可能需要调用多次map函数来处理每个输入键值对；Reduce作业处理一个分区的中间键值对，期间要对每个不同的键调用一次reduce函数，Reduce作业最终也对应一个输出文件。

• an input reader。这个函数会将输入分为M个部分，并且定义了如何从数据中抽取最初的键值对，比如词频的例子中定义文件名和文件内容是键值对。

• a partition function。这个函数用于将map函数产生的中间键值对映射到一个分区里去，最简单的实现就是将键求哈希再对R取模。

• a compare function。这个函数用于Reduce作业排序，这个函数定义了键的大小关系。

• an output writer。负责将结果写入底层分布式文件系统。

• a combiner function。实际就是reduce函数，这是用于前面提到的优化的，比如统计词频时，如果每个<w, "1">要读一次，因为reduce和map通常不在一台机器，非常浪费时间，所以可以在map执行的地方先运行一次combiner，这样reduce只需要读一次<w, "n">了。

• map和reduce函数（不做展开）。