mapreduce原理_MapReduce原理及WordCount实践

参考链接&＃xff1a;

https://www.cnblogs.com/laowangc/p/8961946.html

一、MapReduce流程

1.1 Mapreduce整体流程&＃xff1a;

1&＃xff0e;在Job客户端启动一个作业。

2&＃xff0e;向JobTracker请求一个Job ID。

3&＃xff0e;将运行作业所需要的资源文件复制到HDFS上&＃xff0c;包括MapReduce程序打包的jar文件、配置文件和客户端计算所得的计算划分信息。这些文件都存放在JobTracker专门为该作业创建的文件夹中。文件夹名为该作业的Job ID。jar文件默认会有10个副本&＃xff08;mapred.submit.replication属性控制&＃xff09;&＃xff1b;输入划分信息告诉了JobTracker应该为这个作业启动多少个map任务等信息。

4&＃xff0e;JobTracker接收到作业后&＃xff0c;将其放在一个作业队列里&＃xff0c;等待作业调度器对其进行调度&＃xff08;这里是不是很像微机中的进程调度呢&＃xff09;&＃xff0c;当作业调度器根据自己的调度算法调度到该作业时&＃xff0c;会根据输入划分信息为每个划分创建一个map任务&＃xff0c;并将map任务分配给TaskTracker执行。对于map和reduce任务&＃xff0c;TaskTracker根据主机核的数量和内存的大小有固定数量的map槽和reduce槽。这里需强调的是&＃xff1a;map任务不是随随便便地分配给某个TaskTracker的&＃xff0c;这里有个概念叫&＃xff1a;数据本地化&＃xff08;Data-Local&＃xff09;。意思是&＃xff1a;将map任务分配给含有该map处理的数据块的TaskTracker上&＃xff0c;同事将程序jar包复制到该TaskTracker上来运行&＃xff0c;这叫“运算移动&＃xff0c;数据不移动”。而分配reduce任务时并不考虑数据本地化。

5&＃xff0e;TaskTracker每隔一段时间会给JobTracker发送一个心跳&＃xff0c;告诉JobTracker它依然在运行&＃xff0c;同时心跳中还携带着很多信息&＃xff0c;比如当前map任务完成的进度等信息。当JobTracker收到作业的最后一个任务完成信息时&＃xff0c;便把该作业设置成“成功”。当JobTracker查询状态时&＃xff0c;它将得知任务已完成&＃xff0c;便显示一条消息给用户。

1.2 MapReduce任务的shuffle和排序过程

1. 每个输入分片会让一个map任务来处理&＃xff0c;默认情况下&＃xff0c;以HDFS的一个块的大小&＃xff08;默认64M&＃xff09;为一个分片&＃xff0c;当然我们也可以设置块的大小。map输出的结果会暂且放在一个环形内存缓冲区中&＃xff08;该缓冲区的大小默认为100M&＃xff0c;由io.sort.mb属性控制&＃xff09;&＃xff0c;当该缓冲区快要溢出时&＃xff08;默认为缓冲区大小的80%&＃xff0c;由io.sort.spill.percent属性控制&＃xff09;&＃xff0c;会在本地文件系统中创建一个溢出文件&＃xff0c;将该缓冲区中的数据写入这个文件。

2. 在写入磁盘之前&＃xff0c;线程首先根据reduce任务的数目将数据划分为相同数目的分区&＃xff0c;也就是一个reduce任务对应一个分区的数据。这样做是为了避免有些reduce任务分配到大量数据&＃xff0c;而有些reduce任务却分到很少数据&＃xff0c;甚至没有分到数据的尴尬局面。其实分区就是对数据进行hash的过程。然后对每个分区中的数据进行排序&＃xff0c;如果此时设置了Combiner&＃xff0c;将排序后的结果进行Combianer操作&＃xff0c;这样做的目的是让尽可能少的数据写入到磁盘。

3. 当map任务输出最后一个记录时&＃xff0c;可能会有很多的溢出文件&＃xff0c;这时需要将这些文件合并。合并的过程中会不断地进行排序和combiner操作&＃xff0c;目的有两个&＃xff1a;1、尽量减少每次写入磁盘的数据量&＃xff1b;2、尽量减少下一复制阶段网络传输的数据量。最后合并成了一个已分区且已排序的文件。为了减少网络传输的数据量&＃xff0c;这里可以将数据压缩&＃xff0c;只要将mapred.compress.map.out设置为true就可以。

数据压缩&＃xff1a;Gzip、Lzo、snappy。

4. 将分区中的数据拷贝给相对应的reduce任务。有人可能会问&＃xff1a;分区中的数据怎么知道它对应的reduce是哪个呢&＃xff1f;其实map任务一直和其父TaskTracker保持联系&＃xff0c;而TaskTracker又一直和obTracker保持心跳。所以JobTracker中保存了整个集群中的宏观信息。只要reduce任务向JobTracker获取对应的map输出位置就OK了。

1.3 Shuffle过程

Shuffle过程&＃xff1a;

Collections.shuffle(List list)&＃xff1a;随机打乱list里的元素顺序。

MapReduce里的Shuffle&＃xff1a;描述着数据从map task输出到reduce task输入的这段过程。

(1) Map端的shuffle过程&＃xff1a;

1&＃xff0e;每个map task都有一个内存缓冲区&＃xff0c;存储着map的输出结果&＃xff0c;当缓冲区快满的时候需要将缓冲区的数据以一个临时文件的方式存放到磁盘&＃xff0c;当整个map task结束后在对磁盘中这个map task产生的所有临时文件做一个合并&＃xff0c;生成最终的正式输出文件&＃xff0c;然后等待reduce task来拉数据。

2&＃xff0e;在map task执行时&＃xff0c;它的输入数据来源于HDFS的block&＃xff0c;当然在MapReduce概念中&＃xff0c;map task只读取split。split与block对应关系可能是多对一&＃xff0c;默认是一对一。在wordcount例子里&＃xff0c;假设map的输入数据都是是像“aaa”这样的字符串。

3&＃xff0e;在经过mapper的运行后&＃xff0c;我们得知mapper的输出是这样一个key/value对&＃xff1a;key是“aaa”&＃xff0c;value是数值1。因为当前map端只做加1的操作&＃xff0c;在reduce task里采取合并结果集。前面我们知道这个job有3个reduce task。那到底当前的“aaa”究竟该丢给哪个reduce去处理呢&＃xff1f;是需要现在做决定的。

4&＃xff0e;MapReduce提供Partitioner接口&＃xff0c;作用就是根据key或value及reduce的数量来决定当前的输出数据最终应该交由哪个reduce task处理。默认对key hash后再以reduce task数据取模。默认的取模方式只是为了平均reduce的处理能力&＃xff0c;如果用户自己对Partitioner有需求&＃xff0c;可以定制并设置到job上。

5&＃xff0e;在例子中&＃xff0c;“aaa”经过Partition后返回0&＃xff0c;也就是这对值应当交由第一个reduce来处理。接下来&＃xff0c;需要将数据写入内存缓冲区中&＃xff0c;缓冲区的作用是批量收集map结果&＃xff0c;减少磁盘IO的影响。我们的key/value对以及Partition的结果都会被写入缓冲区。当然&＃xff0c;写入之前&＃xff0c;key与value值都会被序列化成字节数组。

6&＃xff0e;内存缓冲区是有大小限制的&＃xff0c;默认是100MB。当map task的输出结果很多时&＃xff0c;就可能会撑爆内存&＃xff0c;所以需要在一定条件下将缓冲区中的数据临时写入磁盘&＃xff0c;然后重新利用这块缓冲区。这个从内存往磁盘写数据的过程被称为spill&＃xff0c;中文可理解为溢写。溢写是由单独线程来完成&＃xff0c;不影响往缓冲区写map结果的线程。溢写线程启动时不应该阻止map的结果输出&＃xff0c;所以整个缓冲区有个溢写的比例spill.percent。比例默认是0.8&＃xff0c;也就是当缓冲区的数据值已经达到阈值&＃xff08;buffer size * spill percent &＃61; 100MB * 0.8 &＃61; 80MB&＃xff09;&＃xff0c;溢写线程启动&＃xff0c;锁定这80MB的内存&＃xff0c;执行溢写过程。map task的输出结果还可以往剩下的20MB内存中写&＃xff0c;互不影响。

7&＃xff0e;当溢写线程启动后&＃xff0c;需要对这80MB空间内的key做排序&＃xff08;sort&＃xff09;。排序是MapReduce模型默认的行为&＃xff0c;这里的排序也是对序列化的字节做的排序。

8&＃xff0e;因为map task的输出是需要发送到不同的reduce端去&＃xff0c;而内存缓冲区没有对将发送到相同reduce端的数据做合并&＃xff0c;那么这种合并应该是体现在磁盘文件中的。从官方图上也可以看到写到磁盘中的一些文件是对不同的reduce端的数值做过合并。所以溢写过程一个很重要的细节在于&＃xff0c;如果有很多个key/value对需要发送到某个reduce端去&＃xff0c;那么需要将这些key/value值拼接到一块&＃xff0c;减少与partition相关的索引记录。

　　在针对每个reduce端而合并数据时&＃xff0c;有些数据可能像这样&＃xff1a;“aaa”/1&＃xff0c;“aaa”/1。对于wordcount例子&＃xff0c;只是简单地统计单词出现的次数&＃xff0c;如果在同一个map task的结果中有很多像“aaa”一样出现多次的key&＃xff0c;我们就应该把它们的值合并到一块&＃xff0c;这个过程叫reduce也叫combine。但MapReduce的术语中&＃xff0c;reduce只从reduce端执行从多个map task取数据做计算的过程。除reduce外&＃xff0c;非正式地合并数据只能算作combiner了。其实大家知道的&＃xff0c;MapReduce中将Combiner等同于Reducer。

　　如果client设置过Combiner&＃xff0c;那么现在就是使用Combiner的时候了。将有相同key的key/value对的value加起来&＃xff0c;减少溢写到磁盘的数据量。Combiner会优化MapReduce的中间结果&＃xff0c;所以它在整个模型中会多次使用。那哪些场景才能使用Combiner呢&＃xff1f;从这里分析&＃xff0c;Combiner的输出是Reducer的输入&＃xff0c;Combiner绝不能改变最终的计算结果。所以从我的想法来看&＃xff0c;Combiner只应该用于那种Reduce的输入key/value与输出key/value类型完全一致&＃xff0c;且不影响最终结果的场景。比如累加&＃xff0c;最大值等。Combiner的使用一定得慎重&＃xff0c;如果用好&＃xff0c;它对job执行效率有帮助&＃xff0c;反之会影响reduce的最终结果。

9. 每次溢写会在磁盘上生成一个溢写文件&＃xff0c;如果map的输出结果真的很大&＃xff0c;有多次这样的溢写发生&＃xff0c;磁盘上相应的就会有多个溢写文件存在。当map task真正完成时&＃xff0c;内存缓冲区中的数据也全部溢写到磁盘中形成一个溢写文件。最终磁盘中会至少有一个这样的溢写文件存在&＃xff08;如果map的输出结果很少&＃xff0c;当map执行完成时&＃xff0c;只会产生一个溢写文件&＃xff09;&＃xff0c;因为最终的文件只有一个&＃xff0c;所以需要将这些溢写文件归并到一起&＃xff0c;这个过程就叫Merge。Merge是怎样的&＃xff1f;如前面的例子&＃xff0c;“aaa”从某个map task读取过来时值是5&＃xff0c;从另外一个map读取时值是8&＃xff0c;因为他们有相同的key&＃xff0c;所以要merge成group。

　　什么是group&＃xff1a;对于“aaa”就是像真阳的&＃xff1a;{“aaa”&＃xff0c;[5,8,2,...]}&＃xff0c;数组中的值就是从不同的溢写文件中读取出来的&＃xff0c;然后再把这些值加起来。请注意&＃xff0c;因为merge是将多个溢写文件合并到一个文件&＃xff0c;所以可能也有相同的key存在&＃xff0c;在这个过程中&＃xff0c;如果client设置过Combiner&＃xff0c;也会使用Combiner来合并相同的key。

至此&＃xff0c;map端的所有工作都已经结束&＃xff0c;最终生成的这个文件也存放在TaskTracker够得到的某个本地目录中。每个reduce task不断地通过RPC从JobTRacker那获取map task是否完成的信息&＃xff0c;如果reduce task得到通知&＃xff0c;获知某台TaskTracker上的map task执行完成&＃xff0c;Shuffle的后半段过程开始启动。

(2) Reduce端的shuffle过程&＃xff1a;

1&＃xff0e;copy过程&＃xff0c;简单地拉取数据。Reduce进程启动一些数据copy线程&＃xff08;Fetcher&＃xff09;&＃xff0c;通过http方式请求map task所在的TaskTracker获取map task的输出文件。因为map task早已结束&＃xff0c;这些文件就归TaskTracker管理在本地磁盘中。

2&＃xff0e;Merge阶段。这里的merge和map端的merge动作相同&＃xff0c;只是数组中存放的是不同map端copy来的数值。copy过来的数据会先放入内存缓冲区中&＃xff0c;这里的缓冲区大小要比map端更为灵活&＃xff0c;它基于JVM的heap size设置&＃xff0c;因为Shuffle阶段Reducer不运行&＃xff0c;所以应该把绝大部分的内存都给Shuffle使用。

3&＃xff0e;Merge有三种形式&＃xff1a;1、内存到内存&＃xff1b;2、内存到磁盘&＃xff1b;3、磁盘到磁盘。默认情况下第一种形式不启用&＃xff0c;让人比较困惑。当内存中的数据量到达一定阈值&＃xff0c;就启动内存到磁盘的merge。与map端类似&＃xff0c;这也是溢写的过程&＃xff0c;在这个过程中如果你设置有Combiner&＃xff0c;也是会启用的&＃xff0c;然后在磁盘中生成了众多溢写文件。第二种merge方式一直在运行&＃xff0c;直到没有map端的数据时才结束&＃xff0c;然后启动第三种磁盘到磁盘的merge方式生成最终的那个文件。

1.4 reduce端流程分析

(1) reduce会接收到不同map任务传来的数据&＃xff0c;并且每个map传来的数据都是有序的。如果reduce端接收的数据量相当小&＃xff0c;则直接存储在内存中&＃xff08;缓冲区大小由mapred.job.shuffle.input.buffer.percent属性控制&＃xff0c;表示用作此用途的堆空间百分比&＃xff09;&＃xff0c;如果数据量超过了该缓冲区大小的一定比例&＃xff08;由mapred.job.shuffle.merg.percent决定&＃xff09;&＃xff0c;则对数据合并后溢写到磁盘中。

(2) 随着溢写文件的增多&＃xff0c;后台线程会将它们合并成一个更大的有序的文件&＃xff0c;这样做是为了给后面的合并节省空间。其实不管在map端还是在reduce端&＃xff0c;MapReduce都是反复地执行排序&＃xff0c;合并操作&＃xff0c;现在终于明白了有些人为什么会说&＃xff1a;排序是hadoop的灵魂。

(3) 合并的过程中会产生许多的中间文件&＃xff08;写入磁盘了&＃xff09;&＃xff0c;但MapReduce会让写入磁盘的数据尽可能地少&＃xff0c;并且最后一次合并的结果并没有写入磁盘&＃xff0c;而是直接输入到reduce函数。

(4) Reducer的输入文件。不断地merge后&＃xff0c;最后会生成一个“最终文件”。为什么加引号&＃xff1f;因为这个文件可能存在于磁盘上&＃xff0c;也可能存在于内存中。对我们来说&＃xff0c;希望它存放于内存中&＃xff0c;直接作为Reducer的输入&＃xff0c;但默认情况下&＃xff0c;这个文件是存放于磁盘中的。当Reducer的输入文件已定&＃xff0c;整个Shuffle才最终结束。然后就是Reducer执行&＃xff0c;把结果放到HDSF上。

注意&＃xff1a;对MapReduce的调优在很大程度上就是对MapReduce Shuffle的性能的调优。

2. 内存缓冲区

两层索引结构&＃xff1a;

1&＃xff0e;kvoffsets缓冲区&＃xff1a;也叫偏移量索引数组&＃xff0c;用于保存key/value信息在位置索引kvindices中的偏移量。当kvoffsets的使用率超过io.sort.spill.percent&＃xff08;默认为80%&＃xff09;后&＃xff0c;便会触发一次SpillThread线程的“溢写”操作&＃xff0c;也就是开始一次spill阶段的操作。

2&＃xff0e;kvindices缓冲区&＃xff1a;也叫位置索引数组&＃xff0c;用于保存key/value在数据缓冲区kvbuffer中的起始位置。

3&＃xff0e;kvbuffer数据缓冲区&＃xff1a;用于保存实际的key/value的值。

3. 说明

(1) hdfs:文件存储在hdfs上&＃xff0c;每个文件切分成多个一定大小&＃xff08;默认128M&＃xff09;的block&＃xff08;默认3个备份&＃xff09;存储在这个节点。

(2) 吞吐量很大&＃xff1a;指的是很多用户请求同一份数据&＃xff0c; 因hadoop默认保存3份相同数据&＃xff0c;三台机子同时可以对外提供服务&＃xff0c;会降低网络IO等因素对查询用户的影响。

(3) Hadoop中&＃xff1a; map和reduce都是进程【map结束后进入shuffle阶段&＃xff0c;shuffle结束后进行reduce】

spark中&＃xff1a; map和reduce都是线程 【可以把数据放到共同进程的内存中&＃xff0c;降低数据传输带来的性能消耗】

(4) MapReduce中一共有三次排序&＃xff1a;

第一次是在环形缓冲区达到默认阈值80M时&＃xff0c;溢出的数据到达磁盘前会根据key进行快速排序&＃xff0c;每次溢出都会生成一个数据文件&＃xff1b;

第二次是在多个溢出文件发送到reduce端时进行&＃xff0c;进行归并排序&＃xff0c;减少数据传输量&＃xff1b;

第三次是在reduce过程中&＃xff0c;根据不同map中产生的相同partition进行归并排序。

二、代码实现wordcount

1、数据准备

链接&＃xff1a;https://pan.baidu.com/s/16OviT3PaO5cKWafhIU-MgQ

提取码&＃xff1a;4s4u

2、代码实践

(1) python实现map过程计数

pycharm中编辑:

如果脚本是放在终端运行的时候&＃xff0c;py文件的代码如下&＃xff1a;

终端运行代码&＃xff1a;

其中&＃xff1a;sys.stdin接受标准输入&＃xff0c;将cat输出的txt所有内容&＃xff0c;逐行传递进python的map文件进行处理。

终端运行代码&＃xff1a;

按照k1进行排序之后&＃xff0c;相同的单词将在一起&＃xff0c;方便接下来的reduce函数处理。

(2) python实现reduce过程

接着map的输出&＃xff0c;pycharm里面编辑&＃xff1a;

Xshell终端新建reduce.py文件&＃xff1a;

还是传进来接收数据用sys.stdin&＃xff0c;value在shell里面需要转化成int类型。

Xshell执行&＃xff1a;

前两步是为了测试脚本的正确性&＃xff0c;虚拟机本地执行。

(3) 集群执行wordcount

查看集群文件路径&＃xff1a;

将文件上传至hadoop集群:

创建文件输出路径&＃xff1a;

虚拟机中执行文件路径&＃xff1a;/home/badou/python&＃xff0c;路径下面放置三个文件&＃xff1a;map.py、reduce.py和run.sh。其中run.sh脚本内容如下&＃xff1a;&＃xff08;如果路径不同&＃xff0c;代码中请对应修改&＃xff09;

代码参数说明&＃xff1a;

输入路径&＃xff1a;支持使用*通配符&＃xff0c;支持指定多个文件或目录&＃xff0c;可多次使用

如&＃xff1a;/data/*、/output/part-*

mapper参数&＃xff1a;用户自己写的mapper程序&＃xff1b;

reducer参数&＃xff1a;用户自己写的reducer程序&＃xff1b;

file参数&＃xff1a;将本地文件分发到计算节点&＃xff1b;

cacheFile参数&＃xff1a;将HDFS中已经存在的文件发送到对应计算节点&＃xff1b;

cacheArchive参数&＃xff1a;将HDFS中已经存在的压缩文件发送到对应计算节点并解压&＃xff1b;

jobconf参数&＃xff1a;提交作业的一些配置属性。常见配置&＃xff1a;

(1) mapred.map.tasks&＃xff1a;map task数目&＃xff1b;

(2) mapred.reduce.tasks&＃xff1a;reduce task数目&＃xff1b;

(3) stream.num.map.output.key.fields&＃xff1a;指定map task输出记录中key所占列的数目&＃xff1b;

(4) num.key.fields.for.partition&＃xff1a;指定对key分出来的前几部分做partition&＃xff0c;而不是整个key&＃xff1b;

(4) 输出查看

输出路径下面有1个文件&＃xff0c;表明只有1个reduce&＃xff1a;

/data/output/part-00000

查看统计结果前100&＃xff1a;

三、彩蛋

1、确定map任务数依次优先考虑&＃xff1a;

(1) 每个map任务使用的内存不超过800M&＃xff0c;尽量在500M以下&＃xff1b;

(2) 每个map任务运行时间控制在20分钟之内&＃xff0c;最好1-3分钟&＃xff1b;

(3) 每个map任务处理的最大数据量为HDFS块大小&＃xff08;当前为256M&＃xff09;&＃xff0c;一个map处理的输入不能跨文件&＃xff1b;

(4) map任务总数不超过平台可用的任务槽位。

2、配置加载问题

简单配置通过提交作业时 -file分发

复杂较大配置&＃xff1a;传入hdfs、map中打开文件读取、建立内存结构。

3、确定reduce任务数依次优先考虑&＃xff1a;

(1) 每个map任务使用的内存不超过800M&＃xff0c;尽量在500M以下&＃xff1b;

(2) 每个map任务运行时间控制在20分钟之内&＃xff0c;最好1-3分钟&＃xff1b;

(3) 整个reduce阶段的输入数据总量&＃xff1b;

(4) map任务数与reduce任务数的乘积&＃xff1b;

(5) 输出数据的要求&＃xff1b;

reduce个数设置参数mapred.reduce.tasks&＃xff1a;

reduce个数太少-单次执行慢&＃xff0c;出错再试成本高&＃xff1b;

reduce太多-shuffle开销大&＃xff0c;输出大量小文件。

4、map个数为split份数&＃xff0c;压缩文件不可切分&＃xff0c;非压缩文件和sequence文件可以切分&＃xff0c;dfs.block.size决定block大小。

5、文件分发与打包

如果程序运行所需要的可执行文件、脚本或者配置在hadoop集群的计算节点上不存在&＃xff0c;则需要首先将这些文件分发到集群上才能成功计算。Hadoop提供了自动分发文件和压缩包机制&＃xff0c;只需要在启动streaming作业时配置对应参数即可。

1. 若分发文件在本地且没有目录结构&＃xff0c;可以使用-file 文件路径/文件 进行分发。

(2) 如果文件存放在HDFS中&＃xff0c;希望计算时在每个节点上将文件当作本地文件处理&＃xff0c;使用

其中&＃xff1a;“#”是给要分发的文件起别名&＃xff0c;在Mapreduce程序中直接使用该别名就可访问该文件。

(3) 如果存放在hdfs上面是压缩文件&＃xff0c;使用

其中&＃xff1a;“#”是给要分发的文件起别名&＃xff0c;在Mapreduce程序中直接使用该别名就可访问该文件。

6、输出数据压缩

输出数据量较大时&＃xff0c;可以使用hadoop提供的压缩机制对数据进行压缩&＃xff0c;减少网络传输带宽和存储的消耗。

(1) 可以对map的输出即中间结果进行压缩&＃xff1b;对map输出进行压缩主要是为了减少shuffle过程中网络传输数据量&＃xff1b;

(2) 可以对reduce的输出即最终输出进行压缩&＃xff1b;对reduce输出进行压缩主要是为了减少输出结果占用的hdfs存储空间。

(3) 可以指定是否压缩以及采用哪种方式压缩。

(4) 具体压缩参数