- 浏览: 890932 次
- 性别:
- 来自: 杭州
-
文章分类
最新评论
-
u013146595:
楼主你人呢,搬家了吗。还想看你的文章
读代码的“深度优先”与“广度优先”问题 -
zjut_ywf:
写的不错,比书上还具体,受益匪浅
MapReduce:详解Shuffle过程 -
sxzheng96:
seandeng888 写道Combiner阶段应该是在Par ...
MapReduce:详解Shuffle过程 -
sxzheng96:
belivem 写道你好,大神,我也是这一点不是很清楚,看了你 ...
MapReduce:详解Shuffle过程 -
jinsedeme0881:
引用77 楼 belivem 2015-07-11 引用你 ...
MapReduce:详解Shuffle过程
/**
* author : 冶秀刚
* mail : dennyy99@gmail.com
*/
Shuffle过程是MapReduce的核心,也被称为奇迹发生的地方。要想理解MapReduce, Shuffle是必须要了解的。我看过很多相关的资料,但每次看完都云里雾里的绕着,很难理清大致的逻辑,反而越搅越混。前段时间在做MapReduce job 性能调优的工作,需要深入代码研究MapReduce的运行机制,这才对Shuffle探了个究竟。考虑到之前我在看相关资料而看不懂时很恼火,所以在这里我尽最大的可能试着把Shuffle说清楚,让每一位想了解它原理的朋友都能有所收获。如果你对这篇文章有任何疑问或建议请留言到后面,谢谢!
Shuffle的正常意思是洗牌或弄乱,可能大家更熟悉的是Java API里的Collections.shuffle(List)方法,它会随机地打乱参数list里的元素顺序。如果你不知道MapReduce里Shuffle是什么,那么请看这张图:

这张是官方对Shuffle过程的描述。但我可以肯定的是,单从这张图你基本不可能明白Shuffle的过程,因为它与事实相差挺多,细节也是错乱的。后面我会具体描述Shuffle的事实情况,所以这里你只要清楚Shuffle的大致范围就成-怎样把map task的输出结果有效地传送到reduce端。也可以这样理解, Shuffle描述着数据从map task输出到reduce task输入的这段过程。
在Hadoop这样的集群环境中,大部分map task与reduce task的执行是在不同的节点上。当然很多情况下Reduce执行时需要跨节点去拉取其它节点上的map task结果。如果集群正在运行的job有很多,那么task的正常执行对集群内部的网络资源消耗会很严重。这种网络消耗是正常的,我们不能限制,能做的就是最大化地减少不必要的消耗。还有在节点内,相比于内存,磁盘IO对job完成时间的影响也是可观的。从最基本的要求来说,我们对Shuffle过程的期望可以有:
- 完整地从map task端拉取数据到reduce 端。
- 在跨节点拉取数据时,尽可能地减少对带宽的不必要消耗。
- 减少磁盘IO对task执行的影响。
OK,看到这里时,大家可以先停下来想想,如果是自己来设计这段Shuffle过程,那么你的设计目标是什么。我想能优化的地方主要在于减少拉取数据的量及尽量使用内存而不是磁盘。
我的分析是基于Hadoop0.21.0的源码,如果与你所认识的Shuffle过程有差别,不吝指出。我会以WordCount为例,并假设它有8个map task和3个reduce task。从上图看出,Shuffle过程横跨map与reduce两端,所以下面我也会分两部分来展开。
先看看map端的情况,如下图:

上图可能是某个map task的运行情况。拿它与官方图的左半边比较,会发现很多不一致。官方图没有清楚地说明partition, sort与combiner到底作用在哪个阶段。我画了这张图,希望让大家清晰地了解从map数据输入到map端所有数据准备好的全过程。
整个流程我分了四步。简单些可以这样说,每个map task都有一个内存缓冲区,存储着map的输出结果,当缓冲区快满的时候需要将缓冲区的数据以一个临时文件的方式存放到磁盘,当整个map task结束后再对磁盘中这个map task产生的所有临时文件做合并,生成最终的正式输出文件,然后等待reduce task来拉数据。
当然这里的每一步都可能包含着多个步骤与细节,下面我对细节来一一说明:
1. 在map task执行时,它的输入数据来源于HDFS的block,当然在MapReduce概念中,map task只读取split。Split与block的对应关系可能是多对一,默认是一对一。在WordCount例子里,假设map的输入数据都是像“aaa”这样的字符串。
2. 在经过mapper的运行后,我们得知mapper的输出是这样一个key/value对: key是“aaa”, value是数值1。因为当前map端只做加1的操作,在reduce task里才去合并结果集。前面我们知道这个job有3个reduce task,到底当前的“aaa”应该交由哪个reduce去做呢,是需要现在决定的。
MapReduce提供Partitioner接口,它的作用就是根据key或value及reduce的数量来决定当前的这对输出数据最终应该交由哪个reduce task处理。默认对key hash后再以reduce task数量取模。默认的取模方式只是为了平均reduce的处理能力,如果用户自己对Partitioner有需求,可以订制并设置到job上。
在我们的例子中,“aaa”经过Partitioner后返回0,也就是这对值应当交由第一个reducer来处理。接下来,需要将数据写入内存缓冲区中,缓冲区的作用是批量收集map结果,减少磁盘IO的影响。我们的key/value对以及Partition的结果都会被写入缓冲区。当然写入之前,key与value值都会被序列化成字节数组。
整个内存缓冲区就是一个字节数组,它的字节索引及key/value存储结构我没有研究过。如果有朋友对它有研究,那么请大致描述下它的细节吧。
3. 这个内存缓冲区是有大小限制的,默认是100MB。当map task的输出结果很多时,就可能会撑爆内存,所以需要在一定条件下将缓冲区中的数据临时写入磁盘,然后重新利用这块缓冲区。这个从内存往磁盘写数据的过程被称为Spill,中文可译为溢写,字面意思很直观。这个溢写是由单独线程来完成,不影响往缓冲区写map结果的线程。溢写线程启动时不应该阻止map的结果输出,所以整个缓冲区有个溢写的比例spill.percent。这个比例默认是0.8,也就是当缓冲区的数据已经达到阈值(buffer size * spill percent = 100MB * 0.8 = 80MB),溢写线程启动,锁定这80MB的内存,执行溢写过程。Map task的输出结果还可以往剩下的20MB内存中写,互不影响。
当溢写线程启动后,需要对这80MB空间内的key做排序(Sort)。排序是MapReduce模型默认的行为,这里的排序也是对序列化的字节做的排序。
在这里我们可以想想,因为map task的输出是需要发送到不同的reduce端去,而内存缓冲区没有对将发送到相同reduce端的数据做合并,那么这种合并应该是体现是磁盘文件中的。从官方图上也可以看到写到磁盘中的溢写文件是对不同的reduce端的数值做过合并。所以溢写过程一个很重要的细节在于,如果有很多个key/value对需要发送到某个reduce端去,那么需要将这些key/value值拼接到一块,减少与partition相关的索引记录。
在针对每个reduce端而合并数据时,有些数据可能像这样:“aaa”/1, “aaa”/1。对于WordCount例子,就是简单地统计单词出现的次数,如果在同一个map task的结果中有很多个像“aaa”一样出现多次的key,我们就应该把它们的值合并到一块,这个过程叫reduce也叫combine。但MapReduce的术语中,reduce只指reduce端执行从多个map task取数据做计算的过程。除reduce外,非正式地合并数据只能算做combine了。其实大家知道的,MapReduce中将Combiner等同于Reducer。
如果client设置过Combiner,那么现在就是使用Combiner的时候了。将有相同key的key/value对的value加起来,减少溢写到磁盘的数据量。Combiner会优化MapReduce的中间结果,所以它在整个模型中会多次使用。那哪些场景才能使用Combiner呢?从这里分析,Combiner的输出是Reducer的输入,Combiner绝不能改变最终的计算结果。所以从我的想法来看,Combiner只应该用于那种Reduce的输入key/value与输出key/value类型完全一致,且不影响最终结果的场景。比如累加,最大值等。Combiner的使用一定得慎重,如果用好,它对job执行效率有帮助,反之会影响reduce的最终结果。
4. 每次溢写会在磁盘上生成一个溢写文件,如果map的输出结果真的很大,有多次这样的溢写发生,磁盘上相应的就会有多个溢写文件存在。当map task真正完成时,内存缓冲区中的数据也全部溢写到磁盘中形成一个溢写文件。最终磁盘中会至少有一个这样的溢写文件存在(如果map的输出结果很少,当map执行完成时,只会产生一个溢写文件),因为最终的文件只有一个,所以需要将这些溢写文件归并到一起,这个过程就叫做Merge。Merge是怎样的?如前面的例子,“aaa”从某个map task读取过来时值是5,从另外一个map 读取时值是8,因为它们有相同的key,所以得merge成group。什么是group。对于“aaa”就是像这样的:{“aaa”, [5, 8, 2, …]},数组中的值就是从不同溢写文件中读取出来的,然后再把这些值加起来。请注意,因为merge是将多个溢写文件合并到一个文件,所以可能也有相同的key存在,在这个过程中如果client设置过Combiner,也会使用Combiner来合并相同的key。
至此,map端的所有工作都已结束,最终生成的这个文件也存放在TaskTracker够得着的某个本地目录内。每个reduce task不断地通过RPC从JobTracker那里获取map task是否完成的信息,如果reduce task得到通知,获知某台TaskTracker上的map task执行完成,Shuffle的后半段过程开始启动。
简单地说,reduce task在执行之前的工作就是不断地拉取当前job里每个map task的最终结果,然后对从不同地方拉取过来的数据不断地做merge,也最终形成一个文件作为reduce task的输入文件。见下图:

如map 端的细节图,Shuffle在reduce端的过程也能用图上标明的三点来概括。当前reduce copy数据的前提是它要从JobTracker获得有哪些map task已执行结束,这段过程不表,有兴趣的朋友可以关注下。Reducer真正运行之前,所有的时间都是在拉取数据,做merge,且不断重复地在做。如前面的方式一样,下面我也分段地描述reduce 端的Shuffle细节:
1. Copy过程,简单地拉取数据。Reduce进程启动一些数据copy线程(Fetcher),通过HTTP方式请求map task所在的TaskTracker获取map task的输出文件。因为map task早已结束,这些文件就归TaskTracker管理在本地磁盘中。
2. Merge阶段。这里的merge如map端的merge动作,只是数组中存放的是不同map端copy来的数值。Copy过来的数据会先放入内存缓冲区中,这里的缓冲区大小要比map端的更为灵活,它基于JVM的heap size设置,因为Shuffle阶段Reducer不运行,所以应该把绝大部分的内存都给Shuffle用。这里需要强调的是,merge有三种形式:1)内存到内存 2)内存到磁盘 3)磁盘到磁盘。默认情况下第一种形式不启用,让人比较困惑,是吧。当内存中的数据量到达一定阈值,就启动内存到磁盘的merge。与map 端类似,这也是溢写的过程,这个过程中如果你设置有Combiner,也是会启用的,然后在磁盘中生成了众多的溢写文件。第二种merge方式一直在运行,直到没有map端的数据时才结束,然后启动第三种磁盘到磁盘的merge方式生成最终的那个文件。
3. Reducer的输入文件。不断地merge后,最后会生成一个“最终文件”。为什么加引号?因为这个文件可能存在于磁盘上,也可能存在于内存中。对我们来说,当然希望它存放于内存中,直接作为Reducer的输入,但默认情况下,这个文件是存放于磁盘中的。至于怎样才能让这个文件出现在内存中,之后的性能优化篇我再说。当Reducer的输入文件已定,整个Shuffle才最终结束。然后就是Reducer执行,把结果放到HDFS上。
上面就是整个Shuffle的过程。细节很多,我很多都略过了,只试着把要点说明白。当然,我可能也有理解或表述上的很多问题,不吝指点。我希望不断地完善和修改这篇文章,能让它通俗、易懂,看完就能知道Shuffle的方方面面。至于具体的实现原理,各位有兴趣就自己去探索,如果不方便的话,留言给我,我再来研究并反馈。
评论
81 楼
zjut_ywf
2017-11-18
写的不错,比书上还具体,受益匪浅
80 楼
sxzheng96
2017-10-20
seandeng888 写道
Combiner阶段应该是在Partitioner之前。
不是的,在缓冲区中存储的数据是一个三元组的形式,数据在内存中就以<key,value,partition>的形式存在,所以partition是在map之后输出数据的时候就发生,combine操作是在溢写之前发生,所以combine在partition之后。
79 楼
sxzheng96
2017-10-20
belivem 写道
你好,大神,我也是这一点不是很清楚,看了你的博客,受益匪浅,但是有一点有点迷茫,在文中你也没有指清楚,在map过程的shuffle中,partition过后,缓冲区中每个key/value对多一个标志位,标志所属的reduce端(同一个reduce作为一个分区),之后是不是应该这样,每个分区都有sort和combine进行操作,这样才感觉更快,更合理一点!请问,对吗,大神?

我想你说的之后是指spill过程吧,溢写之前内存缓冲区的数据会先按照分区编号排序,然后按照键排序。之后开始溢写过程,如果定义了combiner,则在排序后,溢写之前会对每个分区中的数据进行一次combine操作。
78 楼
jinsedeme0881
2017-09-21
引用
77 楼 belivem 2015-07-11 引用
你好,大神,我也是这一点不是很清楚,看了你的博客,受益匪浅,但是有一点有点迷茫,在文中你也没有指清楚,在map过程的shuffle中,partition过后,缓冲区中每个key/value对多一个标志位,标志所属的reduce端(同一个reduce作为一个分区),之后是不是应该这样,每个分区都有sort和combine进行操作,这样才感觉更快,更合理一点!请问,对吗,大神?
你好,大神,我也是这一点不是很清楚,看了你的博客,受益匪浅,但是有一点有点迷茫,在文中你也没有指清楚,在map过程的shuffle中,partition过后,缓冲区中每个key/value对多一个标志位,标志所属的reduce端(同一个reduce作为一个分区),之后是不是应该这样,每个分区都有sort和combine进行操作,这样才感觉更快,更合理一点!请问,对吗,大神?
很期待这个问题的回复啊
77 楼
belivem
2015-07-11
你好,大神,我也是这一点不是很清楚,看了你的博客,受益匪浅,但是有一点有点迷茫,在文中你也没有指清楚,在map过程的shuffle中,partition过后,缓冲区中每个key/value对多一个标志位,标志所属的reduce端(同一个reduce作为一个分区),之后是不是应该这样,每个分区都有sort和combine进行操作,这样才感觉更快,更合理一点!请问,对吗,大神?

76 楼
seandeng888
2015-05-02
75 楼
seandeng888
2015-05-02
Combiner阶段应该是在Partitioner之前。
74 楼
liyuxia713
2015-02-03
很细致,感谢!
73 楼
langyu
2014-12-10
era_misa 写道
map端的第4步中写道:“从另外一个map 读取时值是8”,是不是笔误?
应该是:从map的另一个溢写文件读取时值是8
应该是:从map的另一个溢写文件读取时值是8
是的,你的理解是对的
72 楼
era_misa
2014-12-09
map端的第4步中写道:“从另外一个map 读取时值是8”,是不是笔误?
应该是:从map的另一个溢写文件读取时值是8
受益匪浅,感谢楼主的分享…
应该是:从map的另一个溢写文件读取时值是8
受益匪浅,感谢楼主的分享…
71 楼
gucasboy
2014-07-23
请教一下,看了你的文章我有这样的理解,不知道对不对。在map端执行了两次 combine,一次是在溢写的过程中,这个过程在内存中执行,也就是针对这80M的的缓冲区执行了partition,sort和combine;还有一次是在merge阶段,是在disk中进行。
不知道这样理解对不对,请指教。
不知道这样理解对不对,请指教。
70 楼
panrui5
2014-04-28

69 楼
1753684005
2014-04-23
写的好 ,希望楼主多写写心得,小弟刚接抽hadoop。
68 楼
recruits
2014-03-28
看完了,解了很多疑惑。但是还有一个问题,希望楼主能够帮忙解答:
如果我在启动单词统计任务的时候,设置了5个REDUCE任务。我最终肯定是希望得到一个文件结果集,5个Reduce的结果集怎么进行合并呢?是需要再进行一次只有一个mapreduce的操作么?
很困惑,希望楼主能够解答,谢谢。
如果我在启动单词统计任务的时候,设置了5个REDUCE任务。我最终肯定是希望得到一个文件结果集,5个Reduce的结果集怎么进行合并呢?是需要再进行一次只有一个mapreduce的操作么?
很困惑,希望楼主能够解答,谢谢。
67 楼
啦登2010
2014-02-12
刚接触hadoop,看后加强理解,多谢楼主分享
。。。

66 楼
tclcx111
2014-01-16

65 楼
langyu
2013-11-19
ljq5132 写道
哈哈,师兄是ZJU,这边文章我在期刊上看过,解析的很详细
期刊?什么期刊?
64 楼
ljq5132
2013-11-17
哈哈,师兄是ZJU,这边文章我在期刊上看过,解析的很详细
63 楼
langyu
2013-11-04
XJAVASunjava 写道
楼主的图是用什么工具画的,效果这么好?
PPT

62 楼
XJAVASunjava
2013-11-04
楼主的图是用什么工具画的,效果这么好?
发表评论
-
对Hadoop的SWOT分析
2012-06-01 09:46 10940在当前大数据研究与应 ... -
对Hadoop的SWOT分析
2012-05-31 17:39 10在当前大数据研究与应 ... -
MapReduce:Job性能调优总结
2012-01-11 13:41 18860是时候把去年早期MapReduce调优工作的结果放出来了,丢在 ... -
MapReduce:计算Job运行时的CPU与内存平均利用率
2011-09-23 14:00 9103Hadoop集群上运行有 ... -
MapReduce:默认Counter的含义
2011-09-13 17:52 21109MapReduce Counter为提供我们一个窗口 ... -
MapReduce:Fair Scheduler PPT分享
2011-03-22 12:50 4377分享为公司小组内部交流所做的Fair scheduler PP ... -
MapReduce:Fair Scheduler前传
2011-03-15 09:11 4119Fair Scheduler是由Facebo ... -
MapReduce:job在Job Tracker上的初始化
2011-03-04 15:07 3910这篇来说道 ... -
扩展MapReduce架构的一种尝试
2011-02-28 18:08 2562假设有这样 ... -
MapReduce: 提高MapReduce性能的七点建议[译]
2011-02-22 15:28 27142Cloudera提供 ... -
MapReduce: JT默认task scheduling策略
2011-02-19 16:30 5498如果没有自己定制的调度策略, ... -
MapReduce: Job提交过程
2011-02-17 17:52 29999初学Hadoop,准备用几篇日 ...
相关推荐
内容概要:本文详细介绍了基于MATLAB GUI界面和卷积神经网络(CNN)的模糊车牌识别系统。该系统旨在解决现实中车牌因模糊不清导致识别困难的问题。文中阐述了整个流程的关键步骤,包括图像的模糊还原、灰度化、阈值化、边缘检测、孔洞填充、形态学操作、滤波操作、车牌定位、字符分割以及最终的字符识别。通过使用维纳滤波或最小二乘法约束滤波进行模糊还原,再利用CNN的强大特征提取能力完成字符分类。此外,还特别强调了MATLAB GUI界面的设计,使得用户能直观便捷地操作整个系统。 适合人群:对图像处理和深度学习感兴趣的科研人员、高校学生及从事相关领域的工程师。 使用场景及目标:适用于交通管理、智能停车场等领域,用于提升车牌识别的准确性和效率,特别是在面对模糊车牌时的表现。 其他说明:文中提供了部分关键代码片段作为参考,并对实验结果进行了详细的分析,展示了系统在不同环境下的表现情况及其潜在的应用前景。
嵌入式八股文面试题库资料知识宝典-计算机专业试题.zip
嵌入式八股文面试题库资料知识宝典-C and C++ normal interview_3.zip
内容概要:本文深入探讨了一款额定功率为4kW的开关磁阻电机,详细介绍了其性能参数如额定功率、转速、效率、输出转矩和脉动率等。同时,文章还展示了利用RMxprt、Maxwell 2D和3D模型对该电机进行仿真的方法和技术,通过外电路分析进一步研究其电气性能和动态响应特性。最后,文章提供了基于RMxprt模型的MATLAB仿真代码示例,帮助读者理解电机的工作原理及其性能特点。 适合人群:从事电机设计、工业自动化领域的工程师和技术人员,尤其是对开关磁阻电机感兴趣的科研工作者。 使用场景及目标:适用于希望深入了解开关磁阻电机特性和建模技术的研究人员,在新产品开发或现有产品改进时作为参考资料。 其他说明:文中提供的代码示例仅用于演示目的,实际操作时需根据所用软件的具体情况进行适当修改。
少儿编程scratch项目源代码文件案例素材-剑客冲刺.zip
少儿编程scratch项目源代码文件案例素材-几何冲刺 转瞬即逝.zip
内容概要:本文详细介绍了基于PID控制器的四象限直流电机速度驱动控制系统仿真模型及其永磁直流电机(PMDC)转速控制模型。首先阐述了PID控制器的工作原理,即通过对系统误差的比例、积分和微分运算来调整电机的驱动信号,从而实现转速的精确控制。接着讨论了如何利用PID控制器使有刷PMDC电机在四个象限中精确跟踪参考速度,并展示了仿真模型在应对快速负载扰动时的有效性和稳定性。最后,提供了Simulink仿真模型和详细的Word模型说明文档,帮助读者理解和调整PID控制器参数,以达到最佳控制效果。 适合人群:从事电力电子与电机控制领域的研究人员和技术人员,尤其是对四象限直流电机速度驱动控制系统感兴趣的读者。 使用场景及目标:适用于需要深入了解和掌握四象限直流电机速度驱动控制系统设计与实现的研究人员和技术人员。目标是在实际项目中能够运用PID控制器实现电机转速的精确控制,并提高系统的稳定性和抗干扰能力。 其他说明:文中引用了多篇相关领域的权威文献,确保了理论依据的可靠性和实用性。此外,提供的Simulink模型和Word文档有助于读者更好地理解和实践所介绍的内容。
嵌入式八股文面试题库资料知识宝典-2013年海康威视校园招聘嵌入式开发笔试题.zip
少儿编程scratch项目源代码文件案例素材-驾驶通关.zip
小区开放对周边道路通行能力影响的研究.pdf
内容概要:本文探讨了冷链物流车辆路径优化问题,特别是如何通过NSGA-2遗传算法和软硬时间窗策略来实现高效、环保和高客户满意度的路径规划。文中介绍了冷链物流的特点及其重要性,提出了软时间窗概念,允许一定的配送时间弹性,同时考虑碳排放成本,以达到绿色物流的目的。此外,还讨论了如何将客户满意度作为路径优化的重要评价标准之一。最后,通过一段简化的Python代码展示了遗传算法的应用。 适合人群:从事物流管理、冷链物流运营的专业人士,以及对遗传算法和路径优化感兴趣的科研人员和技术开发者。 使用场景及目标:适用于冷链物流企业,旨在优化配送路线,降低运营成本,减少碳排放,提升客户满意度。目标是帮助企业实现绿色、高效的物流配送系统。 其他说明:文中提供的代码仅为示意,实际应用需根据具体情况调整参数设置和模型构建。
少儿编程scratch项目源代码文件案例素材-恐怖矿井.zip
内容概要:本文详细介绍了基于STM32F030的无刷电机控制方案,重点在于高压FOC(磁场定向控制)技术和滑膜无感FOC的应用。该方案实现了过载、过欠压、堵转等多种保护机制,并提供了完整的源码、原理图和PCB设计。文中展示了关键代码片段,如滑膜观测器和电流环处理,以及保护机制的具体实现方法。此外,还提到了方案的移植要点和实际测试效果,确保系统的稳定性和高效性。 适合人群:嵌入式系统开发者、电机控制系统工程师、硬件工程师。 使用场景及目标:适用于需要高性能无刷电机控制的应用场景,如工业自动化设备、无人机、电动工具等。目标是提供一种成熟的、经过验证的无刷电机控制方案,帮助开发者快速实现并优化电机控制性能。 其他说明:提供的资料包括详细的原理图、PCB设计文件、源码及测试视频,方便开发者进行学习和应用。
基于有限体积法Godunov格式的管道泄漏检测模型研究.pdf
嵌入式八股文面试题库资料知识宝典-CC++笔试题-深圳有为(2019.2.28)1.zip
少儿编程scratch项目源代码文件案例素材-几何冲刺 V1.5.zip
Android系统开发_Linux内核配置_USB-HID设备模拟_通过root权限将Android设备转换为全功能USB键盘的项目实现_该项目需要内核支持configFS文件系统
C# WPF - LiveCharts Project
少儿编程scratch项目源代码文件案例素材-恐怖叉子 动画.zip
嵌入式八股文面试题库资料知识宝典-嵌⼊式⼯程师⾯试⾼频问题.zip