《火龙果软件-MapReduce课件.ppt》由会员分享，可在线阅读，更多相关《火龙果软件-MapReduce课件.ppt（29页珍藏版）》请在三一办公上搜索。
1、MapReduce课件,Outline,MapReduce overviewDiscussion QuestionsMapReduce,Motivation,200+processors200+terabyte database1010 total clock cycles0.1 second response time5 average advertising revenue,From:www.cs.cmu.edu/bryant/presentations/DISC-FCRC07.ppt,Motivation:Large Scale Data Processing,Want to proce
2、ss lots of data(1 TB)Want to parallelize across hundreds/thousands of CPUs Want to make this easy,Google Earth uses 70.5 TB:70 TB for the raw imagery and 500 GB for the index data.,MapReduce,Automatic parallelization&distributionFault-tolerantProvides status and monitoring toolsClean abstraction for
3、 programmers,Programming Model,Borrows from functional programmingUsers implement interface of two functions:map(in_key,in_value)-(out_key,intermediate_value)listreduce(out_key,intermediate_value list)-out_value list,map,Records from the data source(lines out of files,rows of a database,etc)are fed
4、into the map function as key*value pairs:e.g.,(filename,line).map()produces one or more intermediate values along with an output key from the input.,reduce,After the map phase is over,all the intermediate values for a given output key are combined together into a listreduce()combines those intermedi
5、ate values into one or more final values for that same output key(in practice,usually only one final value per key),Parallelism,map()functions run in parallel,creating different intermediate values from different input data setsreduce()functions also run in parallel,each working on a different outpu
6、t keyAll values are processed independentlyBottleneck:reduce phase cant start until map phase is completely finished.,Example:Count word occurrences,map(String input_key,String input_value):/input_key:document name/input_value:document contents for each word w in input_value:EmitIntermediate(w,1);re
7、duce(String output_key,Iterator intermediate_values):/output_key:a word/output_values:a list of counts int result=0;for each v in intermediate_values:result+=ParseInt(v);Emit(AsString(result);,Example,Page 1:the weather is goodPage 2:today is goodPage 3:good weather is good.,Map output,Worker 1:(the
8、 1),(weather 1),(is 1),(good 1).Worker 2:(today 1),(is 1),(good 1).Worker 3:(good 1),(weather 1),(is 1),(good 1).,Reduce Input,Worker 1:(the 1)Worker 2:(is 1),(is 1),(is 1)Worker 3:(weather 1),(weather 1)Worker 4:(today 1)Worker 5:(good 1),(good 1),(good 1),(good 1),Reduce Output,Worker 1:(the 1)Wor
9、ker 2:(is 3)Worker 3:(weather 2)Worker 4:(today 1)Worker 5:(good 4),Some Other Real Examples,Term frequencies through the whole Web repositoryCount of URL access frequencyReverse web-link graph,Implementation Overview,Typical cluster:100s/1000s of 2-CPU x86 machines,2-4 GB of memory Limited bisectio
10、n bandwidth Storage is on local IDE disks GFS:distributed file system manages data(SOSP03)Job scheduling system:jobs made up of tasks,scheduler assigns tasks to machines Implementation is a C+library linked into user programs,Architecture,Execution,Task Granularity,Fine granularity tasks:many more m
11、ap tasks than machines Minimizes time for fault recovery Better dynamic load balancing Often use 200,000 map/5000 reduce tasks w/2000 machines,Locality,Master program divides up tasks based on location of data:(Asks GFS for locations of replicas of input file blocks)tries to have map()tasks on same
12、machine as physical file data,or at least same rack,Effect:Thousands of machines read input at local disk speed,Fault Tolerance,On worker failure:Detect failure via periodic heartbeats Re-execute completed and in-progress map tasks Re-execute in progress reduce tasks Task completion committed throug
13、h master Master failure:Could handle,but dont yet(master failure unlikely),Robust:lost 1600 of 1800 machines once,but finished fine,Optimizations,No reduce can start until map is complete:A single slow disk controller can rate-limit the whole processMaster redundantly executes“slow-moving”map tasks;
14、uses results of first copy to finish,(one finishes first“wins”),Why is it safe to redundantly execute map tasks?Wouldnt this mess up the total computation?,Slow workers significantly lengthen completion time Other jobs consuming resources on machine Bad disks with soft errors transfer data very slow
15、ly Weird things:processor caches disabled(!),Optimizations,“Combiner”functions can run on same machine as a mapperCauses a mini-reduce phase to occur before the real reduce phase,to save bandwidth,Performance,Tests run on cluster of 1800 machines:4 GB of memory Dual-processor 2 GHz Xeons with Hypert
16、hreading Dual 160 GB IDE disks Gigabit Ethernet per machine Bisection bandwidth approximately 100 Gbps,Two benchmarks:MR_GrepScan 1010 100-byte records to extract records matching a rare pattern(92K matching records)MR_SortSort 1010 100-byte records(modeled after TeraSort benchmark),MR_Grep,Locality
17、 optimization helps:1800 machines read 1 TB of data at peak of 31 GB/s Without this,rack switches would limit to 10 GB/s Startup overhead is significant for short jobs,MR_Sort,Backup tasks reduce job completion time significantly System deals well with failures,Normal,No Backup Tasks,200 processes k
18、illed,More and more MapReduce,MapReduce Programs In Google Source Tree,Example uses:distributed grepdistributed sortweb link-graph reversalterm-vector per hostweb access log statsinverted index constructiondocument clustering machine learningstatistical machine translation,MapReduce Conclusions,MapR
19、educe has proven to be a useful abstraction Greatly simplifies large-scale computations at Google Functional programming paradigm can be applied to large-scale applicationsFun to use:focus on problem,let library deal w/messy details,Further Improvement,“Improving MapReduce Performance in Heterogeneous Environments”in OSDI08,
