云计算的安全架构与技术补充材料1

1、MapReduce:Simplified Data Processing on Large ClustersThese are slides from Dan Welds class at U. Washington(who in turn made his slides based on those by Jeff Dean, Sanjay Ghemawat, Google, Inc.)Motivation Large-Scale Data ProcessingqWant to use 1000s of CPUs But dont want hassle of managing things

2、 MapReduce providesqAutomatic parallelization & distributionqFault toleranceqI/O schedulingqMonitoring & status updatesMap/Reduce Map/Reduce qProgramming model from Lisp q(and other functional languages) Many problems can be phrased this way Easy to distribute across nodes Nice retry/failure semanti

3、csMap in Lisp (Scheme) (map f list list2 list3 ) (map square (1 2 3 4)q(1 4 9 16) (reduce + (1 4 9 16)q(+ 16 (+ 9 (+ 4 1) ) )q30 (reduce + (map square (map l1 l2)Unary operatorBinary operatorMap/Reduce ala Google map(key, val) is run on each item in setqemits new-key / new-val pairs reduce(key, vals

4、) is run for each unique key emitted by map()qemits final outputcount words in docsqInput consists of (url, contents) pairsqmap(key=url, val=contents): For each word w in contents, emit (w, “1”)qreduce(key=word, values=uniq_counts): Sum all “1”s in values list Emit result “(word, sum)”Count, Illustr

5、atedmap(key=url, val=contents):For each word w in contents, emit (w, “1”)reduce(key=word, values=uniq_counts):Sum all “1”s in values listEmit result “(word, sum)”see bob throwsee spot runsee1bob1 run1see 1spot 1throw1bob1 run1see 2spot 1throw1GrepqInput consists of (url+offset, single line)qmap(key=

6、url+offset, val=line): If contents matches regexp, emit (line, “1”)qreduce(key=line, values=uniq_counts): Dont do anything; just emit lineReverse Web-Link Graph MapqFor each URL linking to target, qOutput pairs ReduceqConcatenate list of all source URLsqOutputs: pairsInverted Index Map ReduceExample

7、 uses: distributed grepdistributed sort web link-graph reversal term-vector / hostweb access log stats inverted index construction document clustering machine learning statistical machine translation . . .Model is Widely ApplicableMapReduce Programs In Google Source Tree Typical cluster: 100s/1000s

8、of 2-CPU x86 machines, 2-4 GB of memory Limited bisection 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 Implementati

9、on OverviewExecutionHow is this distributed?1.Partition input key/value pairs into chunks, run map() tasks in parallel2.After all map()s are complete, consolidate all emitted values for each unique emitted key3.Now partition space of output map keys, and run reduce() in parallelIf map() or reduce()

10、fails, reexecute!Job ProcessingJobTrackerTaskTracker 0TaskTracker 1TaskTracker 2TaskTracker 3TaskTracker 4TaskTracker 51. Client submits “grep” job, indicating code and input files2. JobTracker breaks input file into k chunks, (in this case 6). Assigns work to ttrackers.3. After map(), tasktrackers

11、exchange map-output to build reduce() keyspace4. JobTracker breaks reduce() keyspace into m chunks (in this case 6). Assigns work.5. reduce() output may go to NDFS“grep”Execution Parallel Execution Task Granularity & Pipelining Fine granularity tasks: map tasks machinesqMinimizes time for fault reco

12、veryqCan pipeline shuffling with map executionqBetter dynamic load balancing Often use 200,000 map & 5000 reduce tasks Running on 2000 machines Handled via re-executionqDetect failure via periodic heartbeatsqRe-execute completed + in-progress map tasksWhy?qRe-execute in progress reduce tasksqTask co

13、mpletion committed through master Robust: lost 1600/1800 machines once finished okSemantics in presence of failures: see paperFault Tolerance / WorkersMaster Failure Could handle, ? But dont yet q(master failure unlikely)Slow workers significantly delay completion time qOther jobs consuming resource

14、s on machine qBad disks w/ soft errors transfer data slowly qWeird things: processor caches disabled (!) Solution: Near end of phase, spawn backup tasks qWhichever one finishes first wins Dramatically shortens job completion time Refinement: Redundant ExecutionRefinement: Locality Optimization Maste

15、r scheduling policy: qAsks GFS for locations of replicas of input file blocks qMap tasks typically split into 64MB (GFS block size) qMap tasks scheduled so GFS input block replica are on same machine or same rack EffectqThousands of machines read input at local disk speed Without this, rack switches

16、 limit read rateRefinementSkipping Bad Records Map/Reduce functions sometimes fail for particular inputs qBest solution is to debug & fix Not always possible third-party source libraries qOn segmentation fault: Send UDP packet to master from signal handler Include sequence number of record being pro

17、cessed qIf master sees two failures for same record: Next worker is told to skip the record Sorting guarantees qwithin each reduce partition Compression of intermediate data CombinerqUseful for saving network bandwidth Local execution for debugging/testing User-defined countersOther RefinementsTests

18、 run on cluster of 1800 machines: q4 GB of memory qDual-processor 2 GHz Xeons with Hyperthreading qDual 160 GB IDE disks qGigabit Ethernet per machine qBisection bandwidth approximately 100 Gbps Two benchmarks:MR_GrepScan1010 100-byte records to extract records matching a rare pattern (92K matching

19、records) MR_SortSort 1010 100-byte records (modeled after TeraSort benchmark)PerformanceMR_GrepLocality optimization helps: 1800 machines read 1 TB at peak 31 GB/s W/out this, rack switches would limit to 10 GB/s Startup overhead is significant for short jobs Normal No backup tasks 200 processes kil

20、ledMR_Sort Backup tasks reduce job completion time a lot! System deals well with failures Rewrote Googles production indexingSystem using MapReduce qSet of 10,14,17,21,24 MapReduce operations qNew code is simpler, easier to understand 3800 lines C+ 700qMapReduce handles failures, slow machines qEasy

21、 to make indexing faster add more machinesExperienceNumber of jobs 29,423 Average job completion time634 secs Machine days used 79,186 days Input data read 3,288 TB Intermediate data produced 758 TB Output data written 193 TB Average worker machines per job 157Average worker deaths per job 1.2Average map tasks per job 3,351 Average reduce tasks per job 55 Unique map implementations 395 Uni