Google的三大核心技术MapReduce_第1页
Google的三大核心技术MapReduce_第2页
Google的三大核心技术MapReduce_第3页
Google的三大核心技术MapReduce_第4页
Google的三大核心技术MapReduce_第5页
已阅读5页,还剩4页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、mapreduce:超大机群上的简单数据处理摘要mapreduce个编程槌豐和处理,产生大数抵蹊的相关实现用户拆定一个map国数处理个key/value对,从而产生中间的key/value 集撚后押抬定一个reduce胡数合并所有的貝有和何中间key的中间value.tifti将列举许多可以用这个模型來衣示的现实世界的工作.以这种方式写的程序能自动的在大规棋的普通机器上实现并行化这个运行时系统关心这些细节:分刘输入故押;在机稱上的说皮,机器的错误处理岸理机器之间必耍的 通借这样就可以讣挥些没有井行分布式处理系统经脸的程序员利用大竝分伽式系统的轻流我们的mapreduce实现运行在規换可以灵活调

2、做的由普通机器组成的机样1卜典翹的mapreduce计算处理儿千台机右上的以tb计昴的数据程序员发现这个系 统狂常好用:已经实规了数以百计的跑preduce程序,毎天在google的机群上都有1000多个mapreduce程序在执行.在过丈的5年里作若和google的许多人已经实现数以百计的为专门目的而写的计録來处理大址的脈始数据比如爬行的文档.web请求h志弟等为了计妙各种类 吃的派生数妣比饥倒排索引,web文档的图结构的乞种表示冉个mil用行的页面数丘的慨毎每夭被请求数盘量多的集合,等等很多这样的»念上很容易理解然而, 綸入的数据址很大,并口只仃计算彼分布左成百上千的机容上才能在

3、可以接受的时间内完成怎样并行计算份发数据,处理惜氓所有这些问題竦合在一起,便得原本很简介的计 舐因为要大师的复杂代码來处理这代树題,而变得让人难以处理.作为对这个复杂性的回应,我们设计一个新的抽色俱型,它讣我们衣示找们将耍执行的简单汁算,而唸藏并行化,容错傲掘分布负毀均衡的那些杂乱的细节,花一个库也 我们的抽象按住的灵憋來自lisp和许筝英他函数语言的map和reduce的甑始表示.我们认识到我们的许芬计片都包含这样的操作:在我们输入数据的逻辑记录上应用map操 作,來计算出一个屮间key/value対集,存所有具有郴同key的value上应用reduce操作來适当的合并派生的数抵功能模型的使

4、用再结合用户捋定的map和reduce操作,让我 们可以ie常容易的实现人观模并行化计歟和使用再次执行作为初级机制来实现容惜这个工作的主要页献足通过简单有力的接门来实现自动的并fj化和大规模分布式计结合这个接ii的实现来在大m普通的pc机卜.实现高件能计弘第二部分描述培本的编程棋型.并ii.给一牝例子第三部分描述符合我们的培于集於的计愆环境的mapreduce的接11的实现第四部分描述我们觉御编程楔型中一些冇 用的技巧第五部分对于并种不同的任务测竝我们实現的性能第八部分探究ft: google内部使用mapreduce作为基础来礙写我们的鑒引系统产品第七部分讨论相关的和耒来 的工作.2 编程模

5、型计算利用 个输入key/value对集來产生 个输出key/value对%.mapreduce朋的用户用两个诵数衣达这个计算:map和reduce.用户白定义的map函数,按受一个输入对撚后产生一个中间key/value对如mapreduce郎把所有具有相同中间key i的中间value疑合在一起撚后把它们传递给 reduce 浙数.用户自定义的reduce函数,接受一个中(hjkeyl和相关的一个value集它合并这些value,形成一个比较小的value集股的,每次reduce调用只产生0或1个慟岀value. 通过一个迭代器把中何value提供绐用门£1定义的reduce函数

6、这样可以便我们很抵内存來控制value列表的大小.2.1实例考虑这个问题:计算在一个夫的文档集合中毎个词出现的次数用户将写和下面类似的伪代码:map(string key.string value):/key:文档的名字"value:文档的内容for each v/ord w in value:emitlntermediatecw;*! ”);reduce (string key.lterator values):/key:-个i可/values:个计数列&int re$ult=o;for each v m values:result+=parselnt(v);emit( a

7、sstring(resut);map詢数产生毎个词和这个词的出現次数(在这个简单的例子里就是"reduce函数把产生的毎-个特定的词的计数加在一远.另外,用户用输入纳出文件的名字和可选的调节参数來境充 个mapreduce规范对線ju户然后询川mapreduce闻数,并把规范对毀传递给它ju户的代码利 mapreduce库傩接在-血(用c+实现)附录a包仔这个实例的全部文本.2.2类型即使前面的伪代讯写成了字符申丝入和输出的term俗氏,但足概念上用户写的map和reduce函数冇关联的类型:map(k1,v1) ->list(k2,v2)reduce(k2,li$t(v2)

8、->list(v2)例如拗入的key,value和输出的keytvalue的域不同此外冲间key,value和愉岀key.values的域相同.我们的c*实现传递字符申来和用戶自定义的函数交互,并把它留给用户的代码,来在字符申和适当的类型间迓行转换.2.3更多实例这里有一些让人感兴趣的简单程帛可以容易的川mapreduce计煤來茨示.分布式的grep(unix匸具程序,可做文件内的字符串查找):如變绍入行匹配给定的样儿map曲数就输岀这行.reduce函数就是把中间数据交巾倒输出.计算url访问頻率:map函数处理web眞面说求的记老输出(url,".reduce函数把相同ur

9、l的value都加起来,产生-个(url,记录总数)的对.倒转网络链接图:map抽数为毎个铉接标湖)对,个url叫做冃标倒含这个url的页曲叫做源.reduce函数痕据给定的和关ii标urls连接所冇的滋urls 形成一个列农产生(目标,源列农)对.每个主机的术语向童:一个术语向位用一个(词频率)列表来概述出现在一个文档或一个文档集中的垠重要的一些词.map歯数为毎-个输入文档产生一个(主机名,术语 向址)对住机名来自文档的url)reduce函数接收给定主机的所有文档的术语向址它把这些术语向量加在起,丢弃低频的术语,然后产生个垠终的(主机名,术语向禺对.创样索引:map俑数分析何个文档撚后产

10、生-个(诃,文宿号)对的序列.reduce臥数按受 个给定诃的所有对扌丰庁相战的文档ids,并且产生一个(叭文档id列淤)对.所 有的紛出对集形成个简单的傅if索引它可以简单的増加跟炼词位?i!的计舁.分布式排序:map函数从毎个记录捉取key,并r产生一个(key.record)cj.reduce函数不改变任何的对这个计郭依極分在4.1描述)和排序屈性(在4.2描述).mapreduce接口对能有许多不同的实现根期坏境进行正确的选择例如,一个实现对一个共享内心牧小的机器是合込的,另外的适合一个a numa的多处理器的机線 而育的适合一个更大的网络机器的集合.这朗分描述一个在google广泛使

11、用的计妹环境的实现:用交换机连接的普通pc机的大机群我们的坏境是:1丄inux操作系统,双处理器,2ygb内存的机器.2 普通的网络发件每个机器的帯宽或者足白兆或者千兆但卅平均小于全部诒宽的一卜3因为 个机群包含诫百上千的机器,所有机器会经帝出现何越.4心储用血按连创毎个机器上的暖价ide换盘.个从内部文件察统发廉起來的分布式文件察统被用來管理"储在这些感盘上的数据文件系统用复初的方式在不可媒 的峻件上来保证可绥性和仔效性.5 用户捉交丄作给调度系统毎个丄作包含一个任务集毎个工作披调度若映射対机群中一个可用的机器集上.3.1执行预览通过自动分割締入数抵成个存胡个splil的集,map

12、円用被分布创多台机器上输入的split能够在不同的机器上被并行处理通过用分割函数分割中间key,來形成r 个片(例如,hash(key) mod r),reduce调用被分加到多台机器上分割数et(r)和分割函数由用户来指定.图1显示了我们丈现的mapreduce操作的仝部滋程当用户的程序逍用mapreduce的凶数的时低将发生下面的一系列动作(下面的数字和图1中的数宇标签郴对应): 1 在用户程用里的mapreduce牢百先分別输入文件成m个片个片的大小一憑从16到64mb(用户可以通过可选的參数來控制)然后在机样中开始夫鱼的拷贝程序.2这些程堺拷贝中的 个是masterjc他的都尼由mas

13、ter分配任务的worker.有m个map任务和r个reduce任务将被分兀管理者分配 个map任务或reduce任务给 一个空闪的worker.3 -个玻分配f map任务的worker读取相关輸入split的内疔它从输入数卅中分析出key/value对撚后把keya/alue对传递给用户白定义的map函数由map m 产生的中何key/value对被级存在内存中.4.缓存在内存中的key/value对被周期性的写入到本定凰我上,通过分割函数把它们写入r个区城在本地磁權上的缓存对的位置被传送给master.master负贵把这些位理传送给reduce worker.5当一个reduce wo

14、rker得到master的位汽通知的时候,它ft川远程过程调川来从map worker的磁丹上读联缓存的数据当reduce worker读取所有的中间数据后, 它通过排睜使具有相同key的内容聚令在一起因为许多不同的key映射到相同的reduce任务所以桦用足必须的如保中何数据比内存还人那么还咼耍一个外部州序.6.reduce worker迭代列:过序的,|:何数据对j:遇到的每个毗的中间key它把xey和相关的,:,fil value集传递给用八自定义的reduce ik.reduce甬数的尬出坡潦加至:; 这个reduce分割的jb终的爼岀文件中.7当所有的map和reduce任务都完成了

15、,管理者唤能用户和在这个时候,在用户程序里的mapreduce调用返何倒用户代珠在成功完成之后,mapreduce执行的输出存放在r个输出文件中(侮一个reduce任务产生一个由用户折定名鼻的文件)一般,用八水滞要合并这r个输出文件成一个文 件他们经常把这些文件当作一个输入怙递洽其他的mapreduce调用或若在可以处理多个分割文件的分布式应用中使用他们.3.2master数据结构master保持"匕数据结枸它为毎 个map和reduce任务冇储它们的状态(宇闲,工作中,完成),和worker机辭(非宇闲任务的机器)的标识.master就像-个管迄通过它冲何文件区域的位掘从map任务

16、传递创reduce任务因此对于每个左成的map任务,easier w储山map任务产生的r个中间文卅区域 的大小和位*当map任务完成的阳丸位咒和大小的更新佶息彼接受这生佶息被逐步增加的传递给那些正在t作(fj reduce任务.3.3容错因为mapreduce库被设计用來使用成百上千的机器来帝助处理非密人規模的数据历以这个库必须要能很好的处理机器故障.worker故障master fh期性的ping侮个worker.如果master在一个确定的时何段内没右攻到worker返冋的伎色那么它将把这个worker标记成失效.1为为毎个由这个欠效的 worker %成的map任务被霓新设汽成它初始的

17、空闲状态,所以它可以被安揩给其他的worker.同样的,毎一个在失敗的worker上正在运行的map或reduce任务,也被載新设汽 成空闲状态井且将敲觅新调搜.在一个火败机器上已经完成的map ft务将披再次执行,因为它的输出存储在它的磁fil上历以不可访问已经完成的reduce任务将不会再次执行,因为它的输出存储在全 局文件系统中.当 个map任务首先被worker a执行z后,乂秋b执行了 (因为a欠效了),型新执行这个帖况皱逋知绐所有执行reduce任务的worker.任何还没有从a啖数据的reduce 任务将从worker b读取数据.mapreduce吋以处理大规棋worker失败

18、的情况例姐在一个mapreduce操作期间,在正在运行的机桥上进行网络细护引起80台机器在几分件内不对访何 /.mapreduce master只是简单的再次执行已经被不町访问的worker完成的匸作繕续执行用终完成这个mapreduce操作.master失败可以很容易的il询理齐周期的写入上面描述的数据结构的checkpoints如果这个master j > ;妝j:|以从上次最后一个checkpoint开始启动另个master进程然 而,因为只有一个master,所以它的失歎是比较麻烦的,冈此我们现在的实现是,如果master失败曲中止mapreduce计峯客户可以检仓这个状态,幷且

19、可以根垢需要尬新执行 mapreduce 操作.在错课面前的处理机制当用户提供的map和reduce操作对它的输出值绘碗定的函数时我们的分布式实现产生和全部程畀没有错決的顺丿丫执行一样相同的输出.我们依较对map和reduce任务的纳出进行甌子提交來完成这个件质的个工作中的任务把它的纳出写到私有临时文件中.个reduce任务产生 个这样的文件,而 个map任务产生r个这样的文件(一个reduce任务对应一个文件)当一个map任务完成的时k.worker发送一个消息给master,在这个消息中包含这r个临时文件的名字如 果master从一个已经完成的map任务再次收到一个沱成的消息它将忽吼这个消

20、息告则,它在master的数州结构里记录这r个文件的名字.当一个reduce任务完成的时悦这个reduce worker原子的把临时文件里和名成址终的输出文件如果相同的reduce任务在多个机器上执行多个重命名调用将玻执行. 并产生和同的辂出文件.我们依赖由底泾文杵系统捉供的原子币命名操作來保证用终的文件系统状态仅仅包會一个reduce任务产生的数据.我们的map和reduce操作大部分都足确定的,并且我们的处卿机制等价于 个顺序的执行的这个"实,使得程序员可以很容易的却解程序的行为当map或/和reduce 操作是不确定的时仗我们捉供1a热比较沥们址仔啲处理机亂当在一个非确定操作的

21、曾面厂个reduce任务r1的输出筹价于个尊确定黒序程序执行产生的输出然而厂个 不冋的reduce任务r2的枪出也许符合一个不i可的非确定k?序程序执行产生的输出.考也map任务m利reduce任务r1.r2的恰况我的设定e(ri)为己经捉交的ri的执行(有ii.仅有一个这样的执行这个比较弱的语义出现,因为e(fu)也许己经i矣取了 111 m的执行产生的输出而e(r2)tli许已经读取了由m的不同执行产生的输出.3.4存储位置:比们的计只机h境忆购络带宽是个相当紋乏的资源我们利用把输入数据(由gfs管理)存储在机器的本地硝盘上来保心网络挣宦.gfs把郃个文件分成64mb的 一些块撚后毎个块的

22、儿个拷贝存储在不同的机器上(-殻定3个拷贝).mapreduce的master考虑细入文件的位咒信0并且努力在一个包含相关输入数据的机湍上安排一个 map任务如果这样做失败了它尝试在那个任务的输入数据的附近安舛-个map任务(闌如,分配到一个和包含输入数据块在一个switch电的worker机滦上执行)当运行巨人 的mapreduce操作在个机群中的擁分机器上的时傾大探分输入数据在本览披读取从而不消耗网络帯宽.35任务粒度0上面描述的那样,我们细分map阶段成m个片,reduce阶段成r个片m和r应当比worker机湍的数谕大许多毎个worker执行许鉴水同的t.作来提商动态负越均 術也可以加

23、速从一个worker失效中的恢更这个机器上的许筝己经完成的map任务可以被分配到所有其他的worker机器上.在我们的实现jilm和r的范例足有大小限制的因为master必须做0(m+r)次调必井ii保«o(mr)个状态在内“中(这个因薰使用的内“绘很少的在o0vtr)个状 态片里,大约毎个map任务/reduce任务对使用 个字节的数据).此外,r经常被用户限;臥因为每一个reduce任务加终邯是一个號立的沦出文件实际上,我们倾向于选抒m,以便每一个单独的任务犬槪都丛16 i«j 64mb的綸入数据(以 便上而播述的位先优化兄越存效的),我们把r设朮成我们希里便用的wor

24、ker机器数凤的小侶数.我们经常执行mapreduce计隽,在心200000,45000,使用2000台t作者机 器的恃况下.3.6备用任务个落忘者足延长mapreduce操作吋何的瓯因之:个机器花负 个界乎7常地的长时间來完成城后的吐map或reduce任务中的 个有很多驗因可能产生落 后断例如,一个仔坏应盘的机器经常发生可以纠正的错叽这样就使谨性能从30mr/s降低创3mb/s 机群调度系统也许已经安排瓦他的任务在这个机器上,由于计算翌使用cpu, 内存,本地 w,m络帯宣的加因,弓血它执疔mapreduce代罔很慢我们燧近遇到的一个何題兄,一个在机器祈贻化刖的bug引绘处理器缓存的失效:

25、在个被彩刑的机器上的讣 聲性能有上百倍的龙响.我们有一个-般的机制來賊轻这个落后再的问題当一个mapreduce 作将要完成的时低master谶度备川进程來执行那些制下的还在执行的任务无论是氐来的还是 备用的执行完诫了,工作都被标记成完成我们已经调整了这个机制,通常只会占用多几个百分点的机器塚源我们发现这可以显善的减少完成大规模mapreduce操作的时间作 为-个例子,将嬰在5.3掃述的排序胃庁,在关闪掉备用任务的悄况下供比有备用任务的情况下多花44%的时何.尽管简单的map和reduce甬数的功能対人多数潘求足足够的了血足我们开发了一些有用的扩充这些将在这个卸分描述.4.1分割曲数mapr

26、educe用户抬定reduce任务和reduce任务需要的输出文件的数址在中何key卜.使用分割函数,使数据分割后通过这些任务.个缺省的分割前数使用hash方 法(fh4m.hash(key) mod r)这个导致非常电的分割然后,有的时候出丄.他的key分割函数来分割数世仔非常有用的例如有时1対ft出的key楚urls,井且我们希雄每个主 机的所有条【i保持在同 个输出文件中为广支持似这样的恬况.mapreduce阵的用户可以捉供专门的分割函数.例如,他用”hash(hoslname(iklkey) mod r”作为分割函数,使 所冇來自网一个主机的urls保存在冋一个纽出文件屮.4.2噸序

27、保证我们保证在 个给定的分割里i虬中间key.-value対以key递增的歟序处理这个顺序保证可以使毎个分割产出 个有序的输出文件笛输出文件的恪式需要支持有效率 的随机访树key的时値或者对输出数抵集再件排庁的时忱就很容易.4.3combiner 函数在果弋侪况下,允许中间结果key重复会讥据相当的比舐并且用门定义的reduce函数满足结合律利交换律个很好的例了旗是在2部分的词统计程序因为词频率愉向于 个zipf分布侪犬分布)列个map任务将产生成百i:千个这样的记s<the,1>.所有的这 些计数将通过网络被传输创一个巾独的reduce任务撚坊由reduce函数加在一起产生一个数

28、字我们允许用户抬定一个可选的combiner数洗在本地进行合并一下撚后再通 过网络发送.在毎丿个执行map任务的机器上combiner瞬数披执行-恢的,相i可的代码枝用combinerreduce函数在combiner和reduce函数z间唯-的x)列定mapreduce 库怎样控制函数的输出.reduce函数的输出玻保存呆终输出文件里.combiner两数的输出戒写到中何文件里,然后戒发送给reduce任务.部分使用combiner可以泉沟的捉岛歧mapreduce操作的速度附录a包含 个使川combiner的数的例f4.4输入输出类型mapreduce库支持以儿种不冋的恪式欣取输入数抠例如

29、,文本模式细入把每 疔看作足个key/value对.key尼文件的他移斌value是加行的内容其他普通的支 持恪式以key的顺序存储key/value对序列每一个鞭入类型的歩现知道怎样把输入分割成对每个单独的map任务來说足冇迂义的(例如文本棋式的范田分刘呦保仅仅在毎行 的边界进行范园分割)虽保许多川户仅仅使川很少的预定慰输入类型的一个m足用户可以通过提供一个简单的reader按口來支持一个新的锐入类型.个reader不必要从文件里读数恨例如,我们可以很容易的定义它从数辦库里读记老或从内存中的数据结枸读臥4.5刷作用仔的时悅mapreduce的用八发现在map探作或/和reduce操作时产生辅

30、助文件作为个附加的输出尼很方便的我们依靠应用程序写来便这个別作用成为處子的. 发的,应用程序写一个临时文件傑后一旦这个文件全部产生龙就自动的被觅命名.对于单个任务产生的多个输出文件來说我们没有捉供其上的两阶段捉交的脈子操作支持因此,一个产生需要交叉文件连按的多个输出文件的任务应该ft确定性的任 务不过这个礙制在实际的工作中并不是个河逼46跳过错误记录冇的时候因为用户的代码电有bug行致在某一个记录上map或reduce函数究然crash掉这样的bug使得mapreduce操作不能完成.虽然一般起條复这个bug,但足 有时保这足不现实的;也许这个bug足在源代码不可得到的第二方库里冇的时族也可以

31、忽略一些记录例如,当在一个犬的数据集上进行统计分析.我们提供一个町选的执行僕式. 在这个hi at.mapreduce库檢测加灼记录引起的crash 然后跳过那歧记洗來继续执行程序.何个worker程序安装一个佶号处理器*获取内心段异常和总线错沃在调用一个用户自定义的map或reducemapreduce咋把记录的序列兮心储在一个全局变m里如果用户代码产生 个信纨那个伫兮处理器漑会发送 个包含序号的1aslgasp“udp包给mapreduce的master.当masler不止 次看到间 个记录的时饥它就会 指出当和关的map或reduce任务再次执行的时候这个记录应当被跳kt4.7木览执行调

32、试在map或reduce函数中树題是很困堆的,因为实际的计算发生在 个分布式的系统中,经陆是有 个master动态的分配工作给儿千台机器.为了简化诚试和测试, 我们开发了一个可醤换的实肥这个实现在本堆执行所有的mapreduce操件用户可以控制执疔,这样计算可以限制创特定的map任务上川户以一个标志调用他们的程序撚后 可以容易的使用他们认为好用的任何调试和测试工具例如gdb).4.8状态侑息master运行一个http hit务冰并且可以输出-组状况页来供人们便用.状态页显示计嫌进阪皱多少个任务已经完成多少个还在逑fj输入的字节数冲间数据字节歡 綸岀字节数,处理百分比,等等这个页也包含到标准糾

33、课的链按,和由衬个任务产生的标准输出的琏按用户可以根撫这"匕数据瀆测计算需要花费的吋徇,和是否需要更多的资源. 当计并比预期的发慢很多的时候,这些页面也可以彼用來刈斯是不是这样.比外闽上血的状态页显示己经仔多少个工作者失敗了,和当它们失败的时恢,那个map和reduce任务正在运行当试图诊晰在用户代硏里的bug时,这个仁息也是有用 的.4.9计数器mapreduce库提供一个计数搭匸具.來计録备种爭件的发生次数例飢用户代码想耍计算所有处理的词的个数或者玻索引的徳文文档的数5l为了使用这个工具,用户代码创建 个命名的计数器対彖撚后在map或/和reduce函数里适当的壻加计数器.例如:

34、counter * uppercase;uppercase=getcounter(muppercasem);map(string name.string contents):for each word w in contents:if(lscapitalized(w):u ppercase->lncreme nt():emitlntermediate(w,n1 ”);来自不列worker机器上的汁数器(ft坡周期性的传送給master(在ping回应»h).master把来自成功的map和reduce任务的计数器伯加起來,4: mapreduce嫌作完成 的时侯,把它返回给用八

35、代码当询计数器的值也被显示在m astern态页里,以便人们可以杏看实际的计摊进喪当计舁计数器值的时像酒险鱼复执行的影响js免数据的跻加(在 备用任务的使用,和由于出出的里新执行,可以产生sfewd有些计数器值被mapreduce阵自动的维护,比如,被处理的输入keya<alue对的数鼠和杖产生的输岀key/value对的数民用户发坯计数湍匸典对于檢杏mapreduce探作的龙整性很有用例如,在 些mapreduce操作中,川户代码也许想妾确探徐出对的数点完全竽于输入对的数比或者处 理过的他文文档的数虽雄在全部被处理的文档数嚴屮钛于合理的范国.5性能在本节,我们用在一个大星集群上运行的两

36、个计算来衡彊mapreduce的性能一个计算用来在-个大概1tb的数期中住找特定的匹配虫另一个计算排序大概1tb的 数据.这两个程序代衣了 mapreduce的用户实现的西实的程序的一个大子集一类是把数据从一种衣示转化到刃种液示另一类眉从一个大的数押;集屮提1r少眾的关心 的数据.5机群配置所有的現序在包含人概1800台机器的机群上执行.机器的配朮是:2个2g的intel xeon超线程处理器,4gb内存,两个160gb ide磴徵个千兆网卡这些机器部聊在个由漪层的翎形交换网络中,在根节点上大槪仔100到2000g的带宽册冇这瞇机器邵冇相同的部署(对竽部署)因比任慰两点之间的來回时间小于1珏抄

37、.在4gb的内存也大酬冇h.5gb彼用来运行在机群中共他的任务这个程序是在周末的下午开始执行的,这个时候cpu,懺盘,网络丛本上是宇闲的5.2grep这个grep程序打描大肚10a10个,毎个100字节的记此査找比牧少的3字符的査找趴这个15找申川现在92337个记录屮)紛入数据被分割成大槻64mb的片 (m.15000),全部的输出存放在一个文件屮(r-1).图2昱示计隽过程的时间变化的悄况丫轴农示输入数据囲1描的連喪随苕更多的机样祓分配给这个mapreduce讣0連喪在逐步的他版当有1764个worker的时 候这个速度达到炽高的30gb/s当map任务完成的时候,速度开始下降,在计算开始

38、后80秒,输入的速度降到0这个计昴持续的时间犬概尼150砂这包抵了能向大概 分钟的 启动时间启动时间用来把程序传播创所有的机器匕等待gfs打开1000个输入文件,得倒必婴的位益优化佶h5.3拮序这个sori程序井序10m0个记录裔个记录100个了节(大戦1tb的数州)这个裡序浪棋仿terasort的.这个排屏仙字只包會不到50行的川八代础!;:中仃3行map函数用來从文本行提取10字节的井序key,并且产生一个由这个key和心始文木行纠成的中何key/value 対我们使用 个内置的identity函数作为reduce操作这个函数血按把中间key/value対作为釧卄的key.-value对履

39、终的扑游输出写到 个2路奴制的gfs文件中(也就是, 甩序的纽出合写2tb的数抵&以谊 样越入数据被分割成64mb的/r(m=15000).我们把打:序后的紛出写到4000个文件中(r=4000).分区函数使用key的廉始字节来把数抵分区到r个小片中.找们以这个恭准的分剳函数知道key的分布情况在一般的搏序程序屮,我们会増加一个俺处理的mapreduce操作,这个操作用于釆样key的情况井冃用这个采样的 key的分加俏况來计摊対屋终捋序处理的分割点。图3(a)®示这个松序程序的正常执行怙况左hisyzjc输入数据的读取連度这个連度城高到达13gbs并且在不到200抄所有map

40、任务完成之后迅速滑落到0許慰到 这个输入速度小j grep.这是因为这个拮序map任务花费人槪-半的时间和带宽,來把中间效据写到木地破做中血grep相关的中间数据可以忽略不计.左中图显示数据通过m络从map任务传紛给reduce任务的速度当第 个map任务完成氐这个州序过程就开始了图示i:的第个高峰足启动了第 批大飯1700个 reduce任务(整个mapreduce任务坡分配到1700台机器上毎个机器一次只执行一个reduce任务)大槪开始汁算后的300仪第一批reduce任务屮的一些完成了我们开始执 行樹下的reduce任务全部的并库过程持续了夫穩600秒的时间.左下图显示扌丰序后的数re

41、duce任务写入殂终文件的速度因为机器忙干排序屮间數据,所以存笫一个排序阶殿的结束和写阶段的开始有一个廷迟写的述度天概是 24gb/s.人概开妳|算后的850秒写过程结束.也括館面的启动过程,全部的计谢务持续的891隹这个利terasort benchmark的处岛纪录1057抄差不多.需要注适的事悄是:因此位丘优化的原因很多数据都足从本也毬盘读収的而没冇通过我们仔限带宽的络,所以细入速度比出序速度和紛出速度部要快肿序速度比细 出速哎快的原因足筑出阶段写两个排序麻数据的样贝俄们写啊个開木的帧因足为了昨性和町用性)我们写曲份的原因足因为底层文件系统的靠性和町用性的耍求如果底 层文件系统用类似容错

42、編码(erasure coding)3<j方式而不采用貝制写的方式,在写保阶段可以降低河络帯世的要求.5.4备用任务的形响在图3(b)iis怒"丿:j剖:h务的幷序程序的执彳讨存况.除了它¥个很k的儿f没动作发工的圮巴外执行流程和图3相帆4 960少有5个reduce 任务没有完成釈而漑是这fit后儿个落后者如道300秋品才完成金部的计厲任务执行r 1283秒,多花了 44%的时间.55机器失效在图3(c)中支示我们冇总的在处序程序讣隽过程中停止1746台worker中的200台机器上的程庠的俏况底层机群调度若在这些机器上勺上重新开始新的worker程 序(因为仅仪程

43、序彼停止,而机器仍然在正常运行).因为已经完成的map u作丢失了(由j相关的map worker被杀掉了),需唤輛再作.所以worker死掉会导致一个负数的输入速率相关map任务的販新执行很快就 酿新执行了快个计算过程在933秒内完成,包抵了前边的启动时间(只比正常执行时何多了 5%的时何).6经验我们在2003年的2月写了 mapreduce年的第一个版木并且在2003年的8月懺了显著的增强包括位置优化.worker机器间任务执行的动念负战均衡,等笹.从那个时 候起我们惊奇的发% mapreduce函数库广泛用于我们i空处腔的问题它现金在google内部各个领域内广泛应用,包括:人戏模机器

44、学习何融google news和froogle户品的机器何也提取数挹产生一个流行査询的报丹如,google zeugeis"为新的试验和产品提取网页的届性(例如从一个web页的大集合中捉取位置信息 用在位盘含询).大規镇的图计并.图4显示了我的主52的渝代码管理系统中翩着时何推移,辰preduce程序的显著期饥从2003年早先时候的0个增长到2004年9月份的羞不多900个不同的程序.mapreduce z所以这样的成功,是因为他能够任不到半小时时间内写出个简单的能够应用于卜.干台机器的大戏模并发程序,并il极大的提商了开发和原形设计的周期效率. 并比他nju.it-个兄全没有分布式

45、和/或并行系统经验的程序员,能够很容易的利用大虽的宙源.在邯一个任务絡束的时忱mapreduce说数咋记求使用的计埒蛰源的统计佶息在的1里我们列出了 2004年8月份在google运行的一些mapreduce的工作的统计侑息.6.1大规模索引到目询为止刃成功的mapreduce的应用就浪匝写了 google web搜索i及务历使用到的index系统索引系统处理祀虫系统孤冋來的趙大&的文档無这些文档集保存 在gfs文件里这些文档的脈始内容的大小,超过1 20tb该引程序兄通过一系列的/、抵5到10次mapreduce探作来建立索引通过利用mapreduce(«换*上一个版本的

46、持别设计的分布处理的索引程序版木)有这样一些好处:索引的代码简单,斌少,容易理解,因为容惜,分布式,并行处理都站城在mapreduce库中了.例如,当使用mapreduce筒效库的时帳,计算的代码行数从原來的3800行c+十代码 下械少到大槪700行代码.mapreduce的函数库的性能己经非常好历以我们可以把戦念上不相关的讣步界分开处理,而不衆混在一起以期蔽少在数据上的处理这使得改变索引过程很容易例如,找 们对老索引系统的一个小更改可能要好儿个月的时间但是在新系统内只需要花儿天时何就可以了.索引系统的操作更容易了,这是因为机器的失效,速度慢的机器以及网络失效都已绍山mapreduce自己解决

47、了,而不需要撫作人员的交互另外,我们对以简单的通过对索引系 统刑"i机器的方式握高处理性能.很多系统都捉供了严格的设计倶式,并h通过对编程的严恪限制來实现n动的并行计算例如一个结合函数可以通过n卜元素的数組的丽缀在n个处理器上使用并行 询络计算在log n的时何内讣乳完.mapreduce足里于我们的大型现实计算的经脸,对这些模型的一个徇化和粘炼.并且,我们还從供了羞于上千台处理器的客铅实现而大部分并 发处埋系统都只在小规模的尺度i:实现,并且机器的移tft还足程序员来控制的bulk synchronous programming以及一些mpi primitives握供了更岛级别的抽

48、紀可以史客易写出并疔处理的程序这些系统和mapreduce禺统的不问z处 在.mapreduce利用严格的编程模式白动灾现川户程序的并发处理,并且提佻了透明的客错处理.找们本地的优化策略定受active disks啄技术的启发,在active disks屮计算任务足尽筮推送到皐近本地凰盘的处理单元上,这样就碱少了通过uo子系统或网络的数据 乩我们在少虽磁福宜接遥按砒通处理机运行來代替宜接违按到穗出控制器的处理机上但是一般的步骤足相似的.我们的备用任务的机制和在chariotte系统i:的积极调度机制和似这个简巾的枳极诚度的 个缺陷是向果 个任务引起f 个重父竹的失败,那个整个计算将无法完 成我

49、们通过在故做情况下跳过故障记录的机制,在某种甩度上够决了这个同题.mapreduce实现依炊个内咒的机祥背理系统來在 个大坝找其亨机器细上分布和运行用门任务爪然这个不足本论文的霓点,但兄集祥笞理系统在理念上和condor 導具他系统足一样的.在mapreduce库中的井库t具在操作上和now-sort相似.源机崔(map worker)分割将要被排序的故据撚后把它发送到r个reduce worker中的一个上每个reduce worker來木地排序它的数据(如果可能,就在内冇中)当然.now sort没冇用户自应义的map利reduce惭数使御我们的库可以广泛的应用.river捉供一个编程模住

50、,在这个模凰下,处理进程可以靠在分布式的队列上发送数据进行彼此通讯和mapreduce 一样,river系统尝试捉供对不同炮用有近似平均的性 能,即便在小对等的w!件环境下或咅在系统慚簸的恬况下也能提供近似半均的性.river泉通过韬心调度帔能和网络的通讯,来半衡任务的充成対间mapreduce和它的可利川 严恪编程模犁,mapreduce构架來把问逊分刘成大戢的任务这些任务坡自动的在5用的worker上说鹰以便速哎快的worker珂以处理更多的任务这个产格編程棋型也止我幻 可以在丁作快要结束的时帙安於冗余的执行來在非一致处理的悄况械少完成时何(比如在育慢机或者阻塞的worker的时肉.bad

51、-fs足 卜很mapreduce完全不同的缩程怏他它的h标是在 个广阔的网络i.执行工作.然而,它们右两个基本原理是和同的这两个系统使用冗余的执行来 从由矢效引起的数抵丢欠中恢狂(2)这网个系统使用本地化调度笫略,来减少遇过拥挤的网络连扱发:送的数期数蛋tacc是 个祓设计用來简化高有效忙网络服务结构的泵统和mapreduce 样,它通过再次执行来实现容错.8结束语mapreduce已绅农google成功的用在不同的目的我们把这个成功01于以下儿个原因:第,这个模裂使用简单占至対没有并行和分布式绅鮒的程序员也是如此因为它阻裁了并行化溶错,位益优化和负我均衡的细节第,大蛋不问的何題可以用mapr

52、educe计算來衣达.例如,mapreduce秋用*,为google的产品web搜索服务, 排序,数抵挖霸,肌器学习,和其他许多系统,产生敎姊第二,我们己经在一个好儿千台计算机的大型皱卅上开发实现这个mapreduce.这个实现便得对于这些机5s资激的利川非 常简单因此也适用解次google遇到的其他很多需耍人址计算的何魏.从这个工作中我们也学习到了一些东风首先,严格的編程按魁使術片行化和分布式计舜简单并r也易于佝造这样:的容错计舜环境第.网络带宽足系统的瓶效珂此在 我们的系统中大址的优化h标是减少通过网络发送的数据!瓦木地优化使用我们从木定維盘读取数號并且把中间数抵写到木定磯盘,以保用网络帯邀第三冗余的执行可以用來 瞇少速度慢的机器的彫响,和控制机器矢效和数抵丢失.josh levenbergfx定和扩展门iid级别的mapreduce api,井1l结合他的适用经禺剧其他人的改进理议肺加门bl多新的功能mapreduce从gfs中i类取和每入数据.我们要憋谢 mo hit aron. howard gobioff.markus gutschke.david krame.shun-tak leung.fil josh redstone 他勺在开发 gfs 以的匸卄我"j 还够谢 percy liang oleansercinoglu 在片发川

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论