MapReduce and Cloud Computing的實(shí)用學(xué)習(xí)課件

MapReduceandCloudComputing的實(shí)用學(xué)習(xí)課件第1頁/共62頁MapReduce第2頁/共62頁ImperativeProgrammingIncomputerscience,imperativeprogrammingisaprogrammingparadigmthatdescribescomputationintermsofstatementsthatchangeaprogramstate.第3頁/共62頁DeclarativeProgrammingIncomputerscience,declarativeprogrammingisaprogrammingparadigmthatexpressesthelogicofacomputationwithoutdescribingitscontrolflow第4頁/共62頁FunctionalLanguagemapflst:(’a->’b)->(’alist)->(’blist)把f作用在輸入list的每個元素上，輸出一個新的list.foldfx0lst:('a*'b->'b)->'b->('alist)->'b

把f作用在輸入list的每個元素和一個累加器元素上，f返回下一個累加器的值第5頁/共62頁FromFunctionalLanguageViewmapflst:(’a->’b)->(’alist)->(’blist)把f作用在輸入list的每個元素上，輸出一個新的list.foldfx0lst:('a*'b->'b)->'b->('alist)->'b

把f作用在輸入list的每個元素和一個累加器元素上，f返回下一個累加器的值Functional運(yùn)算不修改數(shù)據(jù)，總是產(chǎn)生新數(shù)據(jù)map和reduce具有內(nèi)在的并行性Map可以完全并行Reduce在f運(yùn)算滿足結(jié)合律時，可以亂序并發(fā)執(zhí)行Reducefoldl：(a[a]a)第6頁/共62頁Examplefunfoo(l:intlist)=sum(l)+mul(l)+length(l)funsum(lst)=foldl(fn(x,a)=>x+a)0lstfunmul(lst)=foldl(fn(x,a)=>x*a)1lstfunlength(lst)=foldl(fn(x,a)=>1+a)0lst第7頁/共62頁MapReduceis…“MapReduceisaprogrammingmodelandanassociatedimplementationforprocessingandgeneratinglargedatasets.”[1]J.DeanandS.Ghemawat,"MapReduce:SimplifiedDataProcessingonLargeClusters,"inOsdi,2004,pp.137-150.第8頁/共62頁FromParallelComputingViewMapReduce是一種并行編程模型theessenceisasinglefunctionthatexecutesinparallelonindependentdatasets,withoutputsthatareeventuallycombinedtoformasingleorsmallnumberofresults.f是一個map算子

mapf(x:xs)=fx:mapfxsg是一個reduce算子

reducegy(x:xs)=reduceg(gyx)xshomomorphicskeletons第9頁/共62頁MapreduceFramework第10頁/共62頁TypicalproblemsolvedbyMapReduce讀入數(shù)據(jù):

key/value

對的記錄格式數(shù)據(jù)Map:從每個記錄里extractsomethingmap(in_key,in_value)->list(out_key,intermediate_value)處理inputkey/valuepair輸出中間結(jié)果key/valuepairsShuffle:混排交換數(shù)據(jù)把相同key的中間結(jié)果匯集到相同節(jié)點(diǎn)上Reduce:aggregate,summarize,filter,etc.reduce(out_key,list(intermediate_value))->list(out_value)歸并某一個key的所有values，進(jìn)行計算輸出合并的計算結(jié)果(usuallyjustone)輸出結(jié)果第11頁/共62頁ShuffleImplementation第12頁/共62頁P(yáng)artitionandSortGroupPartitionfunction:hash(key)%reducernumberGroupfunction:sortbykey第13頁/共62頁WordFrequenciesinWebpages輸入：onedocumentperrecord用戶實(shí)現(xiàn)map

function，輸入為key=documentURLvalue=documentcontentsmap輸出(potentiallymany)key/valuepairs.對document中每一個出現(xiàn)的詞，輸出一個記錄<word,“1”>第14頁/共62頁Examplecontinued:MapReduce運(yùn)行系統(tǒng)(庫)把所有相同key的記錄收集到一起(shuffle/sort)用戶實(shí)現(xiàn)reduce

function對一個key對應(yīng)的values計算求和sumReduce輸出<key,sum>

第15頁/共62頁InvertedIndex第16頁/共62頁BuildInvertedIndexMap:<doc#,word>?[<word,doc-num>]Reduce:<word,[doc1,doc3,...]>?<word,“doc1,doc3,…”>第17頁/共62頁BuildindexInput:webpagedataMapper:<url,documentcontent><term,docid,locid>Shuffle&Sort:SortbytermReducer:<term,docid,locid>*<term,<docid,locid>*>Result:Globalindexfile,canbesplitbydocidrange第18頁/共62頁QuizPageRankAlgorithmClusteringAlgorithmRecommendationAlgorithm串行算法表述算法的核心公式、步驟描述和說明輸入數(shù)據(jù)表示、核心數(shù)據(jù)結(jié)構(gòu)MapReduce下的實(shí)現(xiàn)：map,reduce如何寫各自的輸入和輸出是什么第19頁/共62頁StoriesoftheCloud…第20頁/共62頁APictureisWorth…第21頁/共62頁TheInformationFactoriesGoogleplexserversnumber450,000,accordingtothelowestestimate200petabytesofharddiskstoragefourpetabytesofRAMTohandlethecurrentloadof100millionqueriesaday,input-outputbandwidthmustbeintheneighborhoodof3petabitspersecond第22頁/共62頁TheSupercomputerthatConnectsEverythingandEveryoneLARRYPAGE:And,actually,theultimatesearchengine,whichwouldunderstand,youknow,exactlywhatyouwantedwhenyoutypedinaquery,anditwouldgiveyoutheexactrightthingback,incomputersciencewecallthatartificialintelligence.Thatmeansitwouldbesmart,andwe'realongwaysfromhavingsmartcomputers.

第23頁/共62頁ThePrototype(1995)第24頁/共62頁EarlyGoogleSystem第25頁/共62頁Spring2000Design第26頁/共62頁Late2000Design第27頁/共62頁Spring2001Design第28頁/共62頁EmptyGoogleCluster第29頁/共62頁ThreeDaysLater…第30頁/共62頁AgeofDataCentersHigh-endMainFmodityPCCluster性價比高，scaleoutBut可靠性差Scalein可靠性高第31頁/共62頁第32頁/共62頁HighCapabilitySystemSC58325832Gigaflops7776GigabytesECCmemory9726-core64-bitnodes29162GByte/sfabriclinksabout1microsecondMPIlatency1088-lanePCI-Express18KW1Cabinet第33頁/共62頁Millicomputers2007第34頁/共62頁Millicomputers2008第35頁/共62頁Guessesfor2010??第36頁/共62頁P(yáng)ackagingComparisonsin1U第37頁/共62頁CloudComputing“Thedesktopisdead.WelcometotheInternet

cloud,wheremassivefacilitiesacrosstheglobewillstoreallthedatayou'lleveruse.”第38頁/共62頁WhatisCloudComputing?Firstwritedownyourownopinionabout“cloudcomputing”,whateveryouthoughtaboutinyourmind.Question:What?Who?Why?How?Prosandcons?Themostimportantquestionis:Whatistherelationwithme?第39頁/共62頁CloudComputingis…NosoftwareaccesseverywherebyInternetpower--Large-scaledataprocessingAppealforstartupsCostefficiency實(shí)在是太方便了SoftwareasplatformConsSecurityDatalock-inSaaSPaaSUtilityComputing第40頁/共62頁SoftwareasaService(SaaS)amodelofsoftwaredeploymentwherebyaproviderlicensesanapplicationtocustomersforuseasaserviceondemand.第41頁/共62頁P(yáng)latformasaService(PaaS)對于開發(fā)WebApplication和Services，PaaS提供了一整套基于Internet的，從開發(fā)，測試，部署，運(yùn)營到維護(hù)的全方位的集成環(huán)境。特別它從一開始就具備了Multi-tenantarchitecture，用戶不需要考慮多用戶并發(fā)的問題，而由platform來解決，包括并發(fā)管理，擴(kuò)展性，失效恢復(fù)，安全。

第42頁/共62頁UtilityComputing“pay-as-you-go”好比讓用戶把電源插頭插在墻上，你得到的電壓和Microsoft得到的一樣，只是你用得少，payless；utilitycomputing的目標(biāo)就是讓計算資源也具有這樣的服務(wù)能力，用戶可以使用500強(qiáng)公司所擁有的計算資源，只是uselesspayless。這是cloudcomputing的一個重要方面

第43頁/共62頁CloudComputingis…第44頁/共62頁KeyCharacteristicsillusionofinfinitecomputingresourcesavailableondemand;eliminationofanup-frontcommitmentbyCloudusers;創(chuàng)業(yè)啟動花費(fèi)abilitytopayforuseofcomputingresourcesonashort-termbasisasneeded。小時間片的billing，報告指出utilitycomputing在這一點(diǎn)上的實(shí)踐是失敗的verylargedatacenterslarge-scalesoftwareinfrastructureoperationalexpertise第45頁/共62頁Whynow?verylarge-scaledatacenter的實(shí)踐，因?yàn)樾碌募夹g(shù)趨勢和Business模式pay-as-you-gocomputing

第46頁/共62頁KeyPlayersAmazonWebServicesGoogleAppEngineMicrosoftWindowsAzure第47頁/共62頁KeyApplicationsMobileInteractiveapplications,TimO’Reilly相信未來是屬于能夠?qū)崟r對用戶提供信息的服務(wù)。Mobile必定是關(guān)鍵。而后臺在datacenter中運(yùn)行是很自然的模式，特別是那些mashup融合類型的服務(wù)。Parallelbatchprocessing。大規(guī)模數(shù)據(jù)處理使用CloudComputing技術(shù)很自然，MapReduce，Hadoop在這里起到重要作用。這里，數(shù)據(jù)移入/移出cloud是很大的開銷，Amazon開始嘗試hostlargepublicdatasetsforfree。Theriseofanalytics。數(shù)據(jù)庫應(yīng)用中transactionbased應(yīng)用還在增長，而analytics的應(yīng)用增長迅速。數(shù)據(jù)挖掘，用戶行為分析等應(yīng)用的巨大推動。Extensionofcompute-intensivedesktopapplication。計算密集型的任務(wù)，說matlab,mathematica都有了cloudcomputing的擴(kuò)展，woo~第48頁/共62頁CloudComputing=SilverBullet?Google文檔在3月7日發(fā)生了大批用戶文件外泄事件。美國隱私保護(hù)組織就此提請政府對Google采取措施，使其加強(qiáng)云計算產(chǎn)品的安全性。ProblemofDataLock-in第49頁/共62頁Challenges第50頁/共62頁SomeotherVoicesIt’sstupidity.It’sworsethanstupidity:it’samarketinghypecampaign.Somebodyissayingthisisinevitable—andwheneveryouhearsomebodysayingthat,it’sverylikelytobeasetofbusinessescampaigningtomakeittrue.RichardStallman,quotedinTheGuardian,September29,2008TheinterestingthingaboutCloudComputingisthatwe’veredefinedCloudComputingtoincludeeverythingthatwealreadydo....Idon’tunderstandwhatwewoulddodifferentlyinthelightofCloudComputingotherthanchangethewordingofsomeofourads.LarryEllison,quotedintheWallStreetJournal,September26,2008第51頁/共62頁What’smatterwithME?!Whatyouwanttodowith1000pcs,oreven100,000pcs?第52頁/共62頁Cloudiscoming…第53頁/共62頁CloudComputingInitiativeGoogleandIBMteamoncloudcomputinginitiativeforuniversities(2007-1008)provideseveralhundredcomputersaccessthroughtheInternettotestparallelprogrammingprojectsTheideafortheprogramfromGoogleseniorsoftwareengineerChristopheBiscigliaGoogleCodeUniversity第54頁/共62頁M45:OpenAcademicClustersCollaborationwithMajorResearchUniversitiesFosteropenresearchFocusonlarge-scale,highlyparallelcomputingSeedFacility:DatacenterinaBox(DiB)500nodes,4000cores,3TBRAM,1.5PBdiskHighbandwidthconnectiontoInternetLocatedonYahoo!corporatecampusRunsYahoo!/ApacheGridStackCarnegieMellonUniversityisInitialPartnerPublicAnnouncement11/12/07第55頁/共62頁SummaryMapReduceDistributedProgrammingModelIt’sfun!InfrastructureCloudcomputingImagination!第56頁/共62頁Readings[1]J.D.a.S.Ghemawat,"MapReduce:SimplifiedDataProcessingonLargeClusters,"inOsdi,2004,pp.137-150.第57頁/共62頁Resources[Ghemawat,2004] J.D.a.S.Ghemawat,"MapReduce:SimplifiedDataProcessingonLargeClusters,"inOsdi,2004,pp.137-150.[Gruber,2006] F.C.a.J.D.a.S.G.a.W.C.H.a.D.A.W.a.M.B.a.T.C.a.A.F.a