中财网兰州马子禄牛肉面总店:[转]MapReduce执行流程
来源：百度文库 编辑：中财网 时间：2024/04/29 14:33:00
MapReduce的概念：
- 处理和生成海量数据的并行编程模型；
- 用于大规模数据集(通常大于1TB)的并行运算；
- MapReduce的核心是Map和Reduce两个函数：
- Map,映射,对列表中的所有元素进行指定的操作,返回基于这个处理的中间结果集；
- Reduce,化简,对中间结果集进行分类和归纳得到最终的计算结果；
- 两个函数可能会并行运行普通的PC机集群上；
MapReduce算法的调用过程：
1.在用户的应用程序中,MapReduce库首先将计算所需的输入文件分割成M块(每块从16MB到64MB不等,可由用户指定),然后在集群上的多台机器上启动相同程序的副本;
2.在启动的所有程序副本中,有一个比较特殊,作为Master程序,剩下的机器被称为Worker,(假设有M个Map任务,R个Reduce任务),Master会挑选所有空闲中的Worker来指派给其Map或者Reduce任务;
3. 分配到Map任务的Worker会自动去读取被分割过的文件,通过运行用户定义的Map操作,来解析处理输入的数据,生成键值对,并不断的抛出;这些中间键值对构成中间结果集,会被缓存在内存中;
4.因为内存的大小有限,每隔段时间,缓存的中间结果集会被写到执行Map任务的及其的硬盘上,在写之前,这些中间结果集会被Partition函数分隔成块,这些块的位置会报告给Master程序,因为这些文件将会作为Reduce任务的输入;
5.当Reduce Worker受到Master程序发来的中间结果集任务时,通过远程调用来读取Map Worker上缓存的中间结果集,读取完毕之后,Reduce Worker会将中间结果集排序,所以相同的Key的键值对会排到一块,如果中间结果集太大,则使用外部程序来排序;
6.Reduce Worker通过遍历排序过的中间结果集,对于相同key的键值对进行合并化简,Reduce任务的结果将会被作为结果写入到GFS文件系统中;
7.当所有的Map和Reduce操作都完成的时候,Master程序会唤醒用户的程序,通知其任务已经完成,继而执行其他的任务;
执行过程中的文件存储位置：
- 源文件:GFS
- Map处理结果:本地存储
- Reduce处理结果:GFS
- 日志:GFS
MapReduce示例：单词统计
- 案例:单词记数问题(WordCount)
- 给定巨大的文本文件(大于1TB),如何计算文件中所有单词出现的数目？
- 使用MapReduce求解该问题
- 定义Map和Reduce函数(Pseudo Code)
- Map函数,以键值对作为输入,经过处理后抛出中间结果的键值对(key,value),MapReduce库会收集Map函数抛出的结果,并且把具有相同的键的键值对分组;
- Reduce函数接受MapReduce库分过组的(key,value[]),然后对具有相同键的中间结果集进行规约,返回给MapReduce库,最后得到计算结果;
- Step 1: 自动对文本进行分割
- Step 2: 在分割之后的每一对
- Step 3: 对Map返回的中间结果集归拢排序
- Step 4: 将分组过的中间结果集传给Reduce操作,通过计数生成最后结果
