您现在的位置 >> Hadoop教程 >> Hadoop实战 >> mapreduce专题  
 

MapReduce Online ?

【作者:Hadoop实战专家】【关键词:中间结果 数据 MapReduce 】 【点击:48289次】【2013-02-2】
比如现在已经处理完成了30%的数据,那么这30%的数据能产生的结果如何?这也是MapReduce语义带来的一个问题:Reduce接受的输入是 (k2,list(v2)), 并不带有前一次计算的结果,即便有方法知晓前一次计算的中间结果,现在reduce的语义也无法对中间结果进行利用。  

相关热门搜索:hadoop reduce hbase mapreduce

大数据标签:hadoop hdfs mapreduce hive bigdata

MapReduce Online ?

标签:大数据云计算HadoopMapReduceHOP

EMC中国研究院 向东

  2004年,Google发布了划时代的 MapReduce 计算模型论文 [1?],学术界和工业界就此开始了漫漫的追赶之路。这期间,工业界试图做的事情就是要实现一个能够媲美或者比GoogleMR更好的系统,多年的努力下来,Hadoop脱颖而出,成为外界实现MapReduce计算模型事实上的标准,围绕着Hadoop,已经形成了一个庞大的生态系统。随着“大数据”的概念的深入人心,各IT巨头也看中了这一块蛋糕,纷纷推出了自己的解决方案。最新的例子就是EMC把HDFS和自己的横向扩展NAS解决方案Isilon进行了整合,大大提高了HDFS的可扩展性和和可用性[2?]。另一方面,学术界对MapReduce计算模型进行了详细探讨,针对各种特定的应用场景,科学家们提出了不同的优化方案,比如来自加州大学伯克利分校的HOP(HadoopOnline Prototype)[3?]就引起了广泛的关注。

  HOP 设想的应用场景很吸引人: 能不能有一种可能,让用户在处理大数据的时候,能实时或者近乎实时的知晓处理的结果呢? 比如现在已经处理完成了30%的数据,那么这30%的数据能产生的结果如何?对于有经验的数据分析人员,这个功能可以帮助他们根据当前产生的部分结果,迅速的做出决策,大大的节省时间和计算资源。

  要实现这个功能,有两大难题需要解决:

  1. Map Reduce的计算模型并不支持这么做,该如何修改和升级Hadoop,使得其能够支持这个功能?

  2. 如果实现了这个功能,又如何保证根据部分数据产生的结果能够正确的反映最终结果?

  总结下来,第一个难题是可能性的问题,就是说,这样做可能么? 第二个难题则关注正确性问题。

  可能性

  HOP对第一个问题进行了探讨,其设计思想在论文《MapReduceOnline》[4?]有详细描述。提出在线MapReduce的概念后,论文总结了当前最流行的MapReduce计算模型实现Hadoop要支持该功能的现实困难:

  1. 在Hadoop中,Map Task产生的中间结果并不是即时推送到Reduce Task的,相反,是ReduceTask监听MapTask的完成情况,然后去问tasktracker获取相应的数据。 这一来一去,对“在线”这一概念的支持就大大不同。

  2. Map Reduce的语义使得这种行为不可能。 根据MapReduce的语义,reduce是这么处理数据的:Reduce(k2,list (v2)) →list(v3), 请注意,这里的k2 对应的是V2的list,就是说,所有k2对应的v2应该都被汇总到这个list里来。这个汇总的过程,必须等到所有的maptask都完成以后才能完成,所以被称为Stagebarrier[5?]。

  在Hadoop的基础上,HOP对这两个困难都进行了研究和实验。 针对第一个挑战,提出了pipeline的思想:Map产生的中间结果,应该尽快的传输到Reduce端。 在这个思想的指导下,HOP尝试了不同的数据传输模式,比如Map产生KV对以后,直接传输到Reduce端,这种方式显然会带来很多问题。不同尝试和折中之后,HOP提出了自适应pipeline:和原来一样,KV对首先会保存在缓冲区中,达到阈值以后被保存到磁盘,同时Maptask会通过RPCcall来注册spillfile。TaskTracker则负责把spillfile  推送到Reduce端。 如果Reduce端接收数据的速度能够跟上Map端产生数据的速度,则一切安好。如果Reduce端接收数据的速度落后了,Map端在产生Spillfile的时候,会检测当前还没发送出去的spillfile的数量,如果大于一个阈值(HOP实验中,阈值是两个spillfile没有被发送),Maptask则会停止向TaskTracker注册新的spillfile,当阈值回落到规定值内以后,MapTask将会把所有没有注册的spillfile进行merge和combine操作,形成一个新的spillfile,并向TaskTracker注册这个文件。 同样的,对于MapTask内部的combine操作,也采用了类似的机制来保证数据传输和数据处理之间的平衡,值得一提的是,某些情况下,combine操作极大的降低了数据冗余,所以HOP采用把压缩比(combine前后buffer大小的比率)也作为其中的一个阈值。

  第二个挑战,HOP采用了一种非常直接的方法:用户可以在提交job的时候,指定一个步进比例,比如10%。 当Reduce检测到自己收到的Map处理是这个步进比例的倍数时,比如30%,就在收到的这些数据的基础上,进行一次Reduce计算,得到一个中间结果。HOP把这个过程叫做“snapshot”。这种方式没有去考虑Map如何对数据进行取样,也没有考虑数据skew的问题,但是无论如何,”snapshot”提供了一种可能,让用户有可能得到某种形式的反馈。“snapshot”还有一个问题: 提前进行reduce操作所产生的中间结果,对于最终结果的计算并没有帮助。这也是MapReduce语义带来的一个问题:Reduce接受的输入是 (k2,list(v2)), 并不带有前一次计算的结果,即便有方法知晓前一次计算的中间结果,现在reduce的语义也无法对中间结果进行利用。实际上,学术界对如何通过MapReduce进行增量式计算有不少讨论,这里就不列举了。

  HOP发表以后,引起了大量关注,HOP的源代码也被Host在GoogleCode上[3?],可惜的是,在此基础上并没有发展出来一个具有活力的community,GoogleCode上最后一次提交代码的日期也定格在2010年10月。

  正确性

  但是HOP是并没有涉及本文开头提出的第二个问题,就是如何保证中间结果能正确的反应最终结果。 这在很大程度上是一个统计学问题,由于MapReduce提供的接口非常底层,用户自己实现的Map/Reduce千变万化,给出一个通用的理论来评估正确性显然非常困难。但是考虑到某些特定应用,还是能给出漂亮的解决方案的。发表在VLDB’11题为《OnlineAggregation for Large MapReduce Jobs》[6?] 的一篇文章就针对onlineaggregation的情况进行了讨论。下图很好的说明了取样方式的重要性:每一幅小图代表了处理一定百分比的数据以后所产生的结果。 小图中的黑色竖线代表了正确结果,红色和兰色曲线分别代表了两种不同取样方式所产生的结果,优劣一目了然。这篇论文还讨论了如何对结果进行修正,本文就不累述了。

  Online?

  用一句流行语来说,“理想很丰满,现实很骨感”,OnlineMapReduce  这个概念非常吸引人,但是由于种种原因,实现一个成熟可靠的OnlineMapReduce方案异常的难。回过头来,重新思考问题的本源,一个自然的疑问就是,如果系统性能极大提高,用户的提交的job能很快的返回结果,online与否还重要么? 以GoogleTenzing[7?]和Dremel[8?]为例,这两者都具有数秒内处理TB级别数据的能力,在这种情况下,用户的提交的查询不需要等待漫长的时间,在可接受的范围内(比如0-30秒),用户能得到最后的结果,随时查看中间结果这个功能,自然也就可有可无了。

  不过,计算机系统的发展,任何人都无法预测,或许在不久的将来,人们会找到一个两全其美的方法,及能充分利用到MapReduce进行分布式大规模数据的种种便利,又能方便的得到各种中间结果,方便人们更早更快的做出决策。

Reference:

[ 1 ]. MapReduce: Simplied Data Processing on Large Clusters, JeffreyDean and Sanjay Ghemawat, http://research.google.com/archive/mapreduce.html

[ 2 ]. http://stor-age.zdnet.com.cn/stor-age/2012/0202/2076729.shtml

[ 3 ]. http://code.google.com/p/hop/

[ 4 ]. http://www.neilconway.org/

[ 5 ]. http://www.ideals.illinois.edu/bitstream/handle/2142/14819/breaking.pdf

[ 6 ]: http://hyracks.googlecode.com/files/OnlineAggregationForLargeMapReduceJobs.pdf

[ 7 ] http://research.google.com/pubs/pub37200.html.google.com/pubs/pub37200.html

[ 8 ]  http://research.google.com/pubs/pub36632.htmlgoogle.com/pubs/pub36632.html

大数据系列mapreduce相关文章:

最新评论
Daniel2014-09-09 07:47:14
Hadoop已经成为大数据的代名词。短短几年间,Hadoop从一种边缘技术成为事实上的标准。而另一方面,MapReduce在谷歌已不再显赫。当企业瞩目MapReduce的时候,谷歌好像早已进入到了下一个时代。 http://t.cn/zWuMv33
疑思乱神2014-09-09 02:44:34
mapreduce/yarn/hive/hbase/storm/...
坚持2014-09-08 07:06:00
Nodejs学习路线图 | 粉丝日志 跨界的IT博客,核心IT技术包括:Hadoop,R,RHadoop,Nodejs,AngularJS,KVM,NoSQL,IT金融 http://t.cn/RvYchYx
xiaoli2014-09-08 12:34:12
测什么?
2014-09-07 08:28:05
没有
天宇天奇2014-09-06 10:07:19
你很适合做开发
yangen_RUC2014-09-06 04:42:31
别迟到了
寻爱2014-09-05 12:25:22
u
七七OK2014-09-04 02:49:47
在Arm上构建的hadoop和hbase的冷数据存储集群获得硬蛋硬件创新大赛十佳奖。今天场面很大,让我想起前年参加首届阿里云开发者大赛获奖的情形。
疯子2014-09-04 03:06:57
#如何整合Hadoop为企业移动信息化所用# 为了满足移动应用开发的需求,现有的Hadoop应用程序应该得到充分利用。 根据CIMI公司最新的一项研究调查显示 ……
 
  • Hadoop生态系统资料推荐