大数据运算系统（1）--- MapReduce

一、MapReduce/Hadoop 简介： MapReduce是目前云计算中最广泛使用的计算模型，由Google提出。 Hadoop是MapReduce的一个开源实现。 1、编程模型 （1）整体思路 程序员写串行程序。 由 系统完成并行分布式执行。 程序员保证串行程序的正确性，系统负责并行分布执行的正确性和效率。 （2）数据模型 <key, value>：数据由一条一条的记录组成；记录之间是无序的；每一条记录有一个key和一个value；key：可以不唯一；key与value的具体类型和内部结构由程序员决定，系统基本上把它们看作黑匣。 （3）Map-shuffle-Reduce Map(ik, iv) -> {<mk, mv>}  输入是一个key-value记录，输出是0~多个key-value记录， mk和ik可能完全不同。 shuffle：由系统完成。shuffle=group by mk。对于所有Map函数的输出，进行 group by。 将相同mk的所有mv都一起提供给Reduce。 Reduce(mk, {mv}) -> {<ok,ov>}  输入是 一个mk和与之对应的所有mv，输出是0~多个key-value记录， ok与mk可能不同。 程序员编制串行的Map函数和Reduce函数，系统完成shuffle功能。 （4）Word count举例 （5）与SQL Select语句的关系 Map：类似Selection/projection Shuffle：类似Group by Reduce：类似Aggregation，Having 2、系统实现 （1）MapReduce系统架构 master/worker （2）MapReduce/Hadoop系统架构 JobTracker：控制协调作业的运行 TaskTracker：执行Map Task或Reduce Task JobTracker，TaskTracker， Name Node， Data Node都是进程，所以可以在一台机器上同时运行JobTracker/Name Node，TaskTracker/Data Node。 （3）MR运行 提交作业：包括Map函数、Reduce函数（Jar）、配置信息（例如，几个Mappers，几个Reducers）、输入路径、输出路径等。 Map Task读数据：Split为一个HDFS数据块；Split的个数可能多余Mappers个数。 Map Task执行：对于一个Split，进行Mapper操作生成<mk, mv>。属于同一个Reduce task的<mk, mv>存储于同一个文件，放在本地硬盘上。 Shuffle：Rdeucer从每个Map task传输中间结果文件。对多个文件进行归并，从而实现group by。 Reduce：对每个<mk, {mv}>调用一次Reduce函数，产生<ok, ov>写入输出文件。 Combiner：partical reducer。 3、典型算法 （1）Grep（找到符合特定模式的文本） （2）Sorting 利用MapReduce系统的shuffle/sort功能完成sorting。identity指将输入拷贝到输出。 （3）Join 一组Mapper处理R，一组Mapper处理S；利用shuffle/group by把匹配的record放到一起；Reducer调用时，{mv}包含同一个join key的所有匹配的R和S记录。