开发笔记:谷歌技术"三宝"之MapReduce！

篇首语：本文由编程笔记#小编为大家整理，主要介绍了谷歌技术"三宝"之MapReduce！相关的知识，希望对你有一定的参考价值。

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

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




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




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




• 让MapReduce来帮帮我们！

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




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

  
  

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

• 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函数，这是用于前面提到的优化的，比如统计词频时，如果每个要读一次，因为reduce和map通常不在一台机器，非常浪费时间，所以可以在map执行的地方先运行一次combiner，这样reduce只需要读一次了。




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