WIXLIB

Note to other teachers and users of these slides: We would be delighted if you found this ourmaterial useful in giving your own lectures. Feel free to use these slides verbatim, or to modifythem to fit your own needs. If you make use of a significant portion of these slides in your ownlecture, please include this message, or a link to our web site: ttp://www.mmds.org

¡ ¡ rdataminingChallenges:§ Howtodistributecomputa6on?§ Distributed/parallelprogrammingishard¡ Map- ‐reduceaddressesalloftheabove§ Google’scomputa6onal/datamanipula6onmodel§ g2

ngofMassiveDatasets,hJp://www.mmds.org3

¡ ¡ 20 billionwebpagesx20KB 400 TB1computerreads30- ‐35MB/secfromdisk§ 4monthstoreadtheweb¡ ¡ ¡ orsuchproblemsisemerging:§ ClusterofcommodityLinuxnodes§ /www.mmds.org4

2- nodesinarackSwitchSwitchCPUMemDisk SwitchCPUCPUMemMemDiskDiskCPU MemDiskEachrackcontains16- ‐64nodesIn 2011 it was guestimated that Google had 1M machines, n:MiningofMassiveDatasets,hJp://www.mmds.org5

asets,hJp://www.mmds.org6

¡ ¡ Large- rdwareChallenges:§ Howdoyoudistributecomputa-on?§ Howcanwemakeiteasytowritedistributedprograms?§ Machinesfail:§ Oneservermaystayup3years(1,000days)§ Ifyouhave1,000servers,expecttoloose1/day§ Peoplees6matedGooglehad 1Mmachinesin2011§ 7

¡ ¡ Issue:Copyingdataoveranetworktakes-meIdea:§ Bringcomputa6onclosetothedata§ Storefilesmul6ple6mesforreliability¡ Map- ‐reduceaddressestheseproblems§ Google’scomputa6onal/datamanipula6onmodel§ Elegantwaytoworkwithbigdata§ StorageInfrastructure–Filesystem§ Google:GFS.Hadoop:HDFS§ Programmingmodel§ Map- assiveDatasets,hJp://www.mmds.org8

¡ Problem:§ Ifnodesfail,howtostoredatapersistently?¡ Answer:§ DistributedFileSystem:§ Providesglobalfilenamespace§ GoogleGFS;HadoopHDFS;¡ TypicalusagepaIern§ Hugefiles(100sofGBtoTB)§ Dataisrarelyupdatedinplace§ llman:MiningofMassiveDatasets,hJp://www.mmds.org9

¡ Chunkservers§ § § § ¡ 16- replicasindifferentracksMasternode§ a.k.a.NameNodeinHadoop’sHDFS§ Storesmetadataaboutwherefilesarestored§ Mightbereplicated¡ Clientlibraryforfileaccess§ Talkstomastertofindchunkservers§ p://www.mmds.org10

¡ ¡ ¡ entmachines§ C5C5C2C5C3D0D1Chunk server 1Chunk server 2 Chunk server 3C0C5D0C2Chunk server man:MiningofMassiveDatasets,hJp://www.mmds.org11

Warm- ‐uptask:¡ Wehaveahugetextdocument¡ le¡ Sampleapplica-on:§ www.mmds.org12

Case1:§ Filetoolargeformemory,butall word,count pairsfitinmemoryCase2:¡ Countoccurrencesofwords:§ words(doc.txt) sort uniq -c§ aline¡ Case2capturestheessenceofMapReduce§ Jp://www.mmds.org13

¡ ¡ Sequen6allyreadalotofdataMap:§ Extractsomethingyoucareabout¡ ¡ Groupbykey:SortandShuffleReduce:§ Aggregate,summarize,filterortransform¡ MiningofMassiveDatasets,hJp://www.mmds.org14

Inputkey-value pairskvkv kIntermediatekey-value pairskvkvkvmapmap Datasets,hJp://www.mmds.org15

Intermediatekey-value pairskKey-value groupsvkvkvkGroupbykeyvvvreducereducekvvkvkv kOutputkey-value pairsvk tasets,hJp://www.mmds.orgkv16

¡ ¡ Input:asetofkey- ‐valuepairsProgrammerspecifiestwomethods:§ Map(k, v) k’, v’ *§ Takesakey- ‐valuepairandoutputsasetofkey- ‐valuepairs§ e§ ThereisoneMapcallforevery(k,v)pair§ Reduce(k’, v’ *) k’, v’’ *§ rocessedinv’order§ Jp://www.mmds.org17

MAP:Readinputandproducesasetofkey- ‐valuepairsThe crew of the spaceshuttle Endeavor recentlyreturned to Earth asambassadors, harbingers ofa new era of spaceexploration. Scientists atNASA are saying that therecent assembly of theDextre bot is the first step ina long-term space-basedman/mache partnership.'"The work we're doing now-- the robotics we're doing-- is what we're going toneed .Big documentProvided by deavor,1)(recently,1) uttle,1)(recently,1) (crew,2)(space,1)(the,3)(shuttle,1)(recently,1) (key, value)(key, value)(key, quentiallyreadtrhedataProvided by theprogrammer18

map(key, value):// key: document name; value: text of the documentfor each word w in value:emit(w, 1)reduce(key, values):// key: a word; value: an iterator over countsresult 0for each count v in values:result vemit(key, siveDatasets,hJp://www.mmds.org19

Map- ‐Reduceenvironmenttakescareof:¡ Par66oningtheinputdata¡ es¡ Performingthegroupbykeystep¡ Handlingmachinefailures¡ Managingrequiredinter- man:MiningofMassiveDatasets,hJp://www.mmds.org20

BigdocumentMAP:Readinputandproducesasetofkey- mds.org21

ets,hJp://www.mmds.org22

¡ Programmerspecifies:§ MapandReduceandinputfiles¡ Input1Input2Map0Map1Map2Workflow:§ Readinputsasasetofkey- ‐value- ‐pairs§ Maptransformsinputkv- ‐pairsintoanewsetofk'v'- ‐pairs§ Sorts&Shufflesthek'v'- ‐pairstooutputnodes§ Allk’v’- ‐pairswithagivenk’aresenttothesamereduce§ Reduceprocessesallk'v'- ‐pairsgroupedbykeyintonewk''v''- ‐pairs§ Writetheresul6ngpairstofiles¡ mds.org23

¡ stem(FS):§ calstorageloca6onofinputdata¡ eworkers¡ /www.mmds.org24

¡ Masternodetakescareofcoordina-on:§ Taskstatus:(idle,in- ‐progress,completed)§ Idletasksgetscheduledasworkersbecomeavailable§ dsizesofitsRintermediatefiles,oneforeachreducer§ Masterpushesthisinfotoreducers¡ s,hJp://www.mmds.org25

¡ Mapworkerfailure§ Maptaskscompletedorin- ‐progressatworkerareresettoidle§ therworker¡ Reduceworkerfailure§ Onlyin- ‐progresstasksareresettoidle§ Reducetaskisrestarted¡ Masterfailure§ ://www.mmds.org26

¡ ¡ Mmaptasks,RreducetasksRuleofathumb:§ MakeMmuchlargerthanthenumberofnodesinthecluster§ OneDFSchunkpermapiscommon§ mworkerfailures¡ UsuallyRissmallerthanM§ mmds.org27

¡ Finegranularitytasks:maptasks machines§ Minimizes6meforfaultrecovery§ Candopipelineshufflingwithmapexecu6on§ 8

¡ Problem§ e:§ Otherjobsonthemachine§ Baddisks§ Weirdthings¡ Solu-on§ Nearendofphase,spawnbackupcopiesoftasks§ Whicheveronefinishesfirst“wins”¡ Effect§ mmds.org29

¡ ,v2), forthesamekeyk§ E.g.,popularwordsinthewordcountexample¡ Cansavenetwork-mebypre- ‐aggrega-ngvaluesinthemapper:§ combine(k, list(v1)) à v2§ Combinerisusuallysameasthereducefunc6on¡ sets,hJp://www.mmds.org30

¡ Backtoourwordcoun-ngexample:§ singlemachine):§ /www.mmds.org31

¡ Wanttocontrolhowkeysgetpar--oned§ file§ atekeyendupatthesameworker¡ Systemusesadefaultpar--onfunc-on:§ hash(key) mod R¡ Some-mesusefultooverridethehashfunc-on:§ E.g.,hash(hostname(URL)) mod s,hJp://www.mmds.org32

¡ ¡ § Linesoftheform:(URL,size,date, )¡ Foreachhost,findthetotalnumberofbytes§ ularhost¡ Otherexamples:§ Linkanalysisandgraphprocessing§ 4

¡ Sta-s-calmachinetransla-on:§ Needtocountnumberof6mesevery5- ‐wordsequenceoccursinalargecorpusofdocuments¡ VeryeasywithMapReduce:§ Map:§ Extract(5- ‐wordsequence,count)fromdocument§ Reduce:§ ningofMassiveDatasets,hJp://www.mmds.org35

¡ ¡ ¡ ComputethenaturaljoinR(A,B) a4c3 atasets,hJp://www.mmds.org36

¡ ¡ Useahashfunc-onhfromB- ‐valuesto1.kAMapprocessturns:§ EachinputtupleR(a,b)intokey- ‐valuepair(b,(a,R))§ EachinputtupleS(b,c)into(b,(c,S))¡ Mapprocessessendeachkey- ‐valuepairwithkeybtoReduceprocessh(b)§ Hadoopdoesthisautoma6cally;justtellitwhatkis.¡ rg37

¡ gCommunica9oncost totalI/OofallprocessesElapsedcommunica9oncost us,butcountonlyrunning6meofprocessesNote that here the big-O notation is not the most useful(adding more machines is always an siveDatasets,hJp://www.mmds.org38

¡ Foramap- ‐reducealgorithm:§ Communica-oncost inputfilesize 2 educeprocesses) thesumoftheoutputsizesoftheReduceprocesses.§ Elapsedcommunica-oncostisthesumofthelargestinput Datasets,hJp://www.mmds.org39

¡ costdominates§ Ignoreoneortheother¡ hborhoodcloud¡ Elapsedcostiswall- g40

¡ ¡ Totalcommunica-oncost O( R S R S )Elapsedcommunica-oncost O(s)§ ttheI/Olimitsisrespected§ ocesscanhave.scouldbe:§ Whatfitsinmainmemory§ Whatfitsonlocaldisk¡ Withproperindexes,computa6oncostislinearintheinput outputsize§ s.org41

¡ Google§ NotavailableoutsideGoogle¡ ¡ Hadoop§ Anopen- ‐sourceimplementa6oninJava§ UsesHDFSforstablestorage§ § Cluster- sets,hJp://www.mmds.org43

¡ Abilitytorentcompu6ngbythehour§ Addi6onalservicese.g.,persistentstorage¡ Amazon’s“Elas6cComputeCloud”(EC2)¡ AsterDataandHadoopcanbothberunonEC2¡ iningofMassiveDatasets,hJp://www.mmds.org44

¡ dDataProcessingonLargeClusters§ hJp://labs.google.com/papers/mapreduce.html¡ SanjayGhemawat,HowardGobioff,andShun- ‐TakLeung:TheGoogleFileSystem§ ww.mmds.org45

¡ HadoopWiki§ Introduc6on§ hJp://wiki.apache.org/lucene- ‐hadoop/§ GexngStarted§ hJp://wiki.apache.org/lucene- ‐hadoop/GexngStartedWithHadoop§ Map/ReduceOverview§ hJp://wiki.apache.org/lucene- ‐hadoop/HadoopMapReduce§ hJp://wiki.apache.org/lucene- ‐hadoop/HadoopMapRedClasses§ EclipseEnvironment§ hJp://wiki.apache.org/lucene- ‐hadoop/EclipseEnvironment¡ Javadoc§ //www.mmds.org46

¡ ReleasesfromApachedownloadmirrors§ ¡ Nightlybuildsofsource§ /¡ Sourcecodefromsubversion§ hJp://lucene.apache.org/hadoop/version ofMassiveDatasets,hJp://www.mmds.org47

¡ ¡ esPar66oning/shufflingsimilartomanylarge- ‐scalesor6ngsystems§ NOW- ‐Sort['97]¡ Re- ‐execu6onforfaulttolerance§ BAD- ‐FS['04]andTACC['97]¡ ndwork§ Ac6veDisks['01],Diamond['04]¡ m§ CharloJe['96]¡ istributedqueues§ MassiveDatasets,hJp://www.mmds.org48

Largescalecompung for% datamining&& problemson commodityhardware Challenges:! Howdoyoudistributecomputaon?&! How&can&we&make&it&easy&to&write&distributed& programs .