WIXLIB

Tutorials,June 19th 2009MapReduceThe Programming Model and PracticeJerry ZhaoTechnical LeadJelena Pjesivac-GrbovicSoftware Engineer

Yet another MapReduce tutorial?Some tutorials you might have seen:Introduction to MapReduce Programming ModelHadoop Map/Reduce Programming Tutorialand more.What makes this one different:Some complex "realistic" MapReduce examplesBrief discussion of trade-offs between alternativesGoogle MapReduce implementation internals, tuning tipsAbout this presentationEdited collaboratively on Google Docs for domains

Tutorial OverviewMapReduce programming modelBrief intro to MapReduceUse of MapReduce inside GoogleMapReduce programming examplesMapReduce, similar and alternativesImplementation of Google MapReduceDealing with failuresPerformance & scalabilityUsability

What is MapReduce?A programming model for large-scale distributed dataprocessingSimple, elegant conceptRestricted, yet powerful programming constructBuilding block for other parallel programming toolsExtensible for different applicationsAlso an implementation of a system to execute suchprogramsTake advantage of parallelismTolerate failures and jittersHide messy internals from usersProvide tuning knobs for different applications

Programming ModelInspired by Map/Reduce in functional programminglanguages, such as LISP from 1960's, but not equivalent

MapReduce Execution Overview

Tutorial OverviewMapReduce programming modelBrief intro to MapReduceUse of MapReduce inside GoogleMapReduce programming examplesMapReduce, similar and alternativesImplementation of Google MapReduceDealing with failuresPerformance & scalabilityUsability

Use of MapReduce inside GoogleStats for Month Aug.'04Number of jobsAvg. completion time (secs)Machine years ,00039511,081Map input data (TB)Map output data (TB)reduce output data (TB)Avg. machines per 4,018394Unique From "MapReduce: simplified data processing on large clusters"

MapReduce inside GoogleGooglers' hammer for 80% of our data crunchingLarge-scale web search indexingClustering problems for Google NewsProduce reports for popular queries, e.g. Google TrendProcessing of satellite imagery dataLanguage model processing for statistical machinetranslationLarge-scale machine learning problemsJust a plain tool to reliably spawn large number of taskse.g. parallel data backup and restoreThe other 20%? e.g. Pregel

Use of MR in System Health MonitoringMonitoring service talks to everyserver frequentlyCollectHealth signalsActivity informationConfiguration dataStore time-series data foreverParallel analysis of repository dataMapReduce/Sawzall

Investigating System Health IssuesCase studyHigher DRAM errors observed in a new GMail clusterSimilar servers running GMail elsware not affectedSame version of the software, kernel, firmware, etc.Bad DRAM is the initial culprit. but that same DRAM model was fairly healthy elsewhereActual problem: bad motherboard batchPoor electrical margin in some memory bus signalsGMail got more than its fair share of the bad batchAnalysis of this batch allocated to other services confirmed thetheoryAnalysis possible by having all relevant data in one placeand processing power to digest itMapReduce is part of the infrastructure

Tutorial OverviewMapReduce programming modelBrief intro to MapReduceUse of MapReduce inside GoogleMapReduce programming examplesMapReduce, similar and alternativesImplementation of Google MapReduceDealing with failuresPerformance & scalabilityUsability

Application ExamplesWord count and frequency in a large set of documentsPower of sorted keys and valuesCombiners for map outputComputing average income in a city for a given yearUsing customized readers toOptimize MapReduceMimic rudimentary DBMS functionalityOverlaying satellite imagesHandling various input formats using protocol bufers

Word Count ExampleInput: Large number of text documentsTask: Compute word count across all the documentSolutionMapper:For every word in a document output (word, "1")Reducer:Sum all occurrences of words and output (word, total count)

Word Count Solution//Pseudo-code for "word counting"map(String key, String value):// key: document name,// value: document contentsfor each word w in value:EmitIntermediate(w, "1");reduce(String key, Iterator values):// key: a word// values: a list of countsint word count 0;for each v in values:word count ParseInt(v);Emit(key, AsString(word count));No types, just strings*

Word Count Optimization: CombinerApply reduce function to map output before it is sent toreducerReduces number of records outputted by mapper!

Word Frequency ExampleInput: Large number of text documentsTask: Compute word frequency across all the documentFrequency is calculated using the total word countA naive solution with basic MapReduce model requirestwo MapReducesMR1: count number of all words in these documentsUse combinersMR2: count number of each word and divide it by the totalcount from MR1

Word Frequency ExampleCan we do better?Two nice features of Google's MapReduceimplementationOrdering guarantee of reduce keyAuxiliary functionality: EmitToAllReducers(k, v)A nice trick: To compute the total number of words in alldocumentsEvery map task sends its total world count with key ""to ALL reducer splitsKey "" will be the first key processed by reducerSum of its values total number of words!

Word Frequency Solution:Mapper with Combinermap(String key, String value):// key: document name, value: document contentsint word count 0;for each word w in value:EmitIntermediate(w, "1");word count ;EmitIntermediateToAllReducers("", AsString(word count));combine(String key, Iterator values):// Combiner for map output// key: a word, values: a list of countsint partial word count 0;for each v in values:partial word count ParseInt(v);Emit(key, AsString(partial word count));

Word Frequency Solution: Reducerreduce(String key, Iterator values):// Actual reducer// key: a word// values: a list of countsif (is first key):assert("" key); // sanity checktotal word count 0;for each v in values:total word count ParseInt(v)else:assert("" ! key); // sanity checkint word count 0;for each v in values:word count ParseInt(v);Emit(key, AsString(word count / total word count ));

Application ExamplesWord frequency in a large set of documentsPower of sorted keys and valuesCombiners for map outputComputing average income in a city for a given yearUsing customized readers toOptimize MapReduceMimic rudimentary DBMS functionalityOverlaying satellite imagesHandling various input formats using protocol bufers

Average Income In a CitySSTable 1: (SSN, {Personal Information})123456:(John Smith;Sunnyvale, CA)123457:(Jane Brown;Mountain View, CA)123458:(Tom Little;Mountain View, CA)SSTable 2: (SSN, {year, income})123456:(2007, 70000),(2006, 65000),(2005, 6000),.123457:(2007, 72000),(2006, 70000),(2005, 6000),.123458:(2007, 80000),(2006, 85000),(2005, 7500),.Task: Compute average income in each city in 2007Note: Both inputs sorted by SSN

Average Income in a City Basic SolutionMapper 1a:Input: SSN Personal InformationOutput: (SSN, City)Mapper 1b:Input: SSN Annual IncomesOutput: (SSN, 2007 Income)Reducer 1:Input: SSN {City, 2007 Income}Output: (SSN, [City, 2007 Income])Mapper 2:Input: SSN [City, 2007 Income]Output: (City, 2007 Income)Reducer 2:Input: City 2007 IncomesOutput: (City, AVG(2007 Incomes))

Average Income in a City Basic SolutionMapper 1a:Input: SSN Personal InformationOutput: (SSN, City)Mapper 1b:Input: SSN Annual IncomesOutput: (SSN, 2007 Income)Reducer 1:Input: SSN {City, 2007 Income}Output: (SSN, [City, 2007 Income])Mapper 2:Input: SSN [City, 2007 Income]Output: (City, 2007 Income)Reducer 2:Input: City 2007 IncomesOutput: (City, AVG(2007 Incomes))

Average Income in a Joined SolutionMapper:Input: SSN Personal Information and IncomesOutput: (City, 2007 Income)ReducerInput: City 2007 IncomeOutput: (City, AVG(2007 Incomes))

Application ExamplesWord frequency in a large set of documentsPower of sorted keys and valuesCombiners for map outputComputing average income in a city for a given yearUsing customized readers toOptimize MapReduceMimic rudimentary DBMS functionalityOverlaying satellite imagesHandling various input formats using protocol bufers

Stitch Imagery Data for Google MapsA simplified version could be:Imagery data from different content providersDifferent formatsDifferent coveragesDifferent timestampsDifferent resolutionsDifferent exposures/tonesLarge amount to data to be processedGoal: produce data to serve a "satellite" view to users

Stitch Imagery Data Algorithm1. Split the whole territory into "tiles" with fixed location IDs2. Split each source image according to the tiles it covers3. For a given tile, stitch contributions from different sources,based on its freshness and resolution, or other preference4. Serve the merged imagery data for each tile, so they can beloaded into and served from a image server farm.

Using Protocol Buffersto Encode Structured DataOpen sourced from Google, among many others:http://code.google.com/p/protobuf/It supports C , Java and Python.A way of encoding structured data in an efficient yet extensibleformat. e.g. we can definemessage Tile {required int64 location id 1;group coverage {double latitude 2;double longitude 3;double width 4;// in kmdouble length 5;// in km}required bytes image data 6; // Bitmap Image datarequired int64 timestamp 7;optional float resolution 8 [default 10];optinal string debug info 10;}Google uses Protocol Buffers for almost all its internal RPCprotocols, file formats and of course in MapReduce.

Stitch Imagery Data Solution: Mappermap(String key, String value):// key: image file name// value: image dataTile whole image;switch (file type(key)):FROM PROVIDER A: Convert A(value, &whole image);FROM PROVIDER B: Convert B(.);.// split whole image according to the grid into tilesfor each Tile t in whole imagestring r(t.location id(),v);

Stitch Imagery Data Solution: Reducerreduce(String key, Iterator values):// key: location id,// values: tiles from different sourcessort values according v.resolution() and v.timestamp();Tile merged tile;for each v in values:overlay pixels in v to merged tile based onv.coverage();Normalize merged tile to be the serve tile size;Emit(key, ProtobufToString(merged tile));

Tutorial OverviewMapReduce programming modelBrief intro to MapReduceUse of MapReduce inside GoogleMapReduce programming examplesMapReduce, similar and alternativesImplementation of Google MapReduceDealing with failuresPerformance & scalabilityUsability

Distributed Computing LandscapeDimensions to compare Apples and OrangesData organizationProgramming modelExecution modelTarget applicationsAssumed computing environmentOverall operating cost

My Basket of Fruit

Nutritional Information of My BasketMPIWhat they areProgramming ModelData organizationA general parrellelprogramming paradigmMapReduceDBMS/SQLA programming paradigmA system to store, manipulateand its associated execution and serve data.systemMessages passing between Restricted to Map/ReducenodesoperationsDeclarative on dataquery/retrieving;Stored proceduresNo assumption"files" can be shardedOrganized datastructuresk,v pairs: string/protomsgTables with rich typesData to be manipulated AnyExecution modelNodes are hysical data localityTransactionQuery/operation optimizationMaterialized viewUsabilitySteep learning curve*;difficult to debugSimple conceptCould be hard to optimizeDeclarative interface;Could be hard to debug inruntimeFlexible to accommodatevarious applicationsPlow through large amountof data with commodityhardwareInteractive querying the data;Maintain a consistent viewacross clientsKey selling pointSee what others say: [1], [2], [3]