MapReduce是Google三大论文中与应用方面最接近的一层,应该说,也是我们在学习和应用分布式系统基础架构(如hadoop)时唯一关心的。
简单点说,MapReduce是一种编程模型,在处理和生成TB级数据时非常有用:通过简单的接口来实现自动的并行化合大规模的分布式运算,并且不用考虑容错、负载均衡等等繁琐而麻烦的细节。
MapReduce借用了函数式编程的概念,它的实现的思路是:将庞大但是相似(这在分布式处理中很常见)的小的Task,通过Map函数分给不同的主机运算,最后,通过Reduce函数收集并合并计算结果,得到所需。
其基本模型是:利用一个输入Key/Value pair集合来产生一个输出的Key/Value pair集合。如下所示:
(input) <k1, v1> -> map -> <k2, v2> -> combine -> <k2, v2> -> reduce -> <k3, v3> (output)
举一个简单的例子。在Google,好吧,为了体现我的爱国,说百度。百度的日常工作中每天会处理大量的原始数据,比如:文档抓取、网站排序、Web请求统计和日志管理。这些操作本身很简单,甚至许多像我一样的菜鸟都能实现。然而,《算法的分析和设计》这门课程告诉我们,当n本身趋于大数时,即使是O(n)的复杂度也不是一台普通的主机所能完成的。
假设我们要统计Web请求。
现在,将这项工作交给一个实现了GFS(分布式文件系统)的主机集群。百度在各地的服务器执行Map函数,处理其周边范围的“小任务”,输入为每次Web站点请求,输出为(“URL”,1),即每有一次访问便将之记录下来。Reduce函数将各地的结果收集起来并进行统计。
注意,在整个MapReduce过程中我们并没有指定执行Map函数的主机和执行Reduce函数的主机,他的实现完全是在GFS的帮助下自动完成的,应用程序员并不需要关心。我们同样并不需要关心多台主机间的通信问题。这有点像网络下的Socket编程,我们并不需关心数据传输的底层实现。
其具体流程图如下:
下面是一些简单的扩展问题
一、容错问题
由于MapReduce本身是设计应用于大规模的分布式计算的(至少得有多台计算机吧),因此一个基本观点是故障是常态。虽然用户本身不用关心容错问题,但简单了解一下MapReduce库在容错方面的措施还是有好处的。
1)worker错误
worker是实际进行计算工作的主机,也是计算集群中最多的一部分,因此,worker出现故障的概率是最高的。
master通常会和所有的worker结点保持心跳信号,如果在规定的时间内未收到worker返回的信号,那该worker会被标记为无效。所有应该由这些worker完成的task(包括已经完成的task)都会被重置为初始化状态,并动态分配给其余的worker处理。
2)master错误
master故障是比较麻烦的事情,因为在原则上MapReduce的信息缓存和管理工作都是由master完成的。一旦master出现错误,那么现行的MapReduce任务就崩溃了。
比较直观的解决办法有2个。一是定期将master数据结构写入磁盘,形成一个checkpoint。一旦发生错误,可以从最后一个checkpoint开始启动新的master进程。二是一旦master出错,整个任务就被终止。客户可以根据日志来检查错误原因,并重新启动。在实际当中,第二种方式是更常用的。
二、任务粒度
如前所述,我们把Map分为M个小Task,把Reduce分为R个小Task。一般来说,M+R >> 主机数量。
M和R值都是需要限制的,因为,master结点的调度动作的时间复杂度是O(M+R),而空间复杂度是O(M*R)。由于对每个状态用一个byte就可以表示,所以空间复杂度倒是其次,关键是对于有限的带宽来说,时间复杂度一般接受不了。对Google的业务来说,M=200000,R=5000,主机数=2000比较合适。
三、备用任务
在实际测试当中,MapReduce的整体完成时间通常取决于“落后者”。即可能有某些Map任务和Reduce任务需要额外花费几倍的时间来处理。可能是原因有多种,比如带宽竞争,或者某台主机过热导致CPU失常等等。
一个有效的机制是:当一个MapReduce任务接近完成时,master会为剩余的“落伍”任务调度备用的进程来完成。不管是正式的主机完成了任务还是备用的主机完成了任务,该任务都会被标记为已经完成。测试表明,这种调优策略通常只占总时间的很少一部分,但在关闭备用任务之后,要多花44%的时间来完成一个排序任务。
分享到:
相关推荐
谷歌在03到06年间连续发表了三篇很有影响力的文章,分别是03年SOSP的GFS,04年OSDI的MapReduce,和06年OSDI的BigTable。SOSP和OSDI都是操作系统领域的顶级会议,在计算机学会推荐会议里属于A类。SOSP在单数年举办,...
Google三大论文之一Mapreduce的中文翻译版,海量数据处理模型。
Google大数据三大论文中文版下载,Google三篇论文MapReduce、GFS、Bigtable pdf下载
Hadoop开发基础 : Google三大论文: MapReduce超大机群上的简单数据处理.doc Hadoop开发基础 : Google三大论文: MapReduce超大机群上的简单数据处理.doc Hadoop开发基础 : Google三大论文: MapReduce超大机群上的简单...
MapReduce 谷歌实验室论文--大规模集群下的数据处理,英文版
谷歌三大论文中文版 mapReduce,fileSystem,BIgtable.zip
Google 提供的广告 Google Google推广 Google代理 C# Mapreduce Google优化 Google 提供的广告 Google AD Word Get on Google Google優化 Google广告 Download Google Analytics Gain traffic and optimize your...
Google大数据三大论文英文版下载,Google三篇论文MapReduce、GFS、Bigtable pdf下载
GFS、MapReduce 和 BigTable。作为 Google 早期三驾马车,这三项革命性的技术不仅在大数据领域广为人知,更直接或间接性的推动了大数据、云计算、乃至如今火爆的人工智能领域的发展。
Google的三大论文, Google_BigTable、Goods_File_System、Google_MapReduce。中文版
google三大论文 gfs bigtable mapreduce hadoop hdfs hbase原型,学hadoop 必看
谷歌三大论文
Google_云计算三大论文中文版 Google 云计算 论文 中文版 BigTable GFS MapReduce PDF格式,一共60页。 学习云计算必读的资料!
google云计算三大论文之MapReduce
google mapreduce
云计算三大论文(GFS,MapReduce,BigTable),中文及英文
2. 紧随其后的就是2004年公布的 MapReduce论文,论文描述了大数据的分布式计算方式,主要思想是将任务分解然后在多台处理能力较弱的计算节点中同时处理,然后将结果合并从而完成大数据处理。 3. 最后就是谷歌发布于...
谷歌DFS+Mapreduce+Bigtable三大论文中英文版本 已经整理完成
Google大数据三大论文 三合一 中文版 GFS MapReduce BigTable
谷歌三大论文,bigtable,File-system, mapreduce的中文版论文