DOC PREVIEW
UT CS 372 - MapReduce

This preview shows page 1-2-3-4-5-6 out of 17 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Slide 1You are an engineer at: Hare-brained-scheme.comOne solutionAnother solutionThird Time’s a charmStringFinder was the easy part!MapReduceMapReduce Programming ModelExample: Counting Words…How does parallelization work?All you have to do is…Your Project: A Search EngineSearch Engine ComponentsSearch Engine OverviewExample: Indexing (2)Example: Indexing (3)Have fun!MapReduceWith a heavy debt to:Google Map Reduce OSDI 2004 slidescode.google.comYou are an engineer at:Hare-brained-scheme.comYour boss, comes to your office and says:“We’re going to be hog-nasty rich! We just need a program to search for strings in text files...”Input: <search_term>, <files>Output: list of files containing <search_term>One solutionpublic class StringFinder { int main(…) {foreach(File f in getInputFiles()) { if(f.contains(searchTerm)) results.add(f.getFileName()); }}System.out.println(“Files:” + results.toString()); }“But, uh, marketing says we have to search a lot of files. More than will fit on one disk…”Another solution•Throw hardware at the problem!•Use your StringFinder class as is… but get lots of disks!“But, uh, well, marketing says it’s too slow…and besides, we need itto work on the web…”Third Time’s a charmWeb ServerStringFinderIndexed dataSearchquery1. How do we distribute the searchable files on our machines?2. What if our webserver goes down?3. What if a StringFinder machine dies? How would you know it was dead?4. What if marketing comes and says, “well, we also want to show pictures of the earth from space too! Ooh..and the moon too!”StringFinderIndexed dataStringFinderIndexed dataStringFinder was the easy part!You really need general infrastructure.•Many different tasks•Want to use hundreds or thousands of PC’s•Continue to function if something breaks•Must be easy to program…MapReduce addresses this problem!MapReduce•Programming model + infrastructure•Write programs that run on lots of machines• Automatic parallelization and distribution • Fault-tolerance • Scheduling, status and monitoring Cool. What’s the catch?MapReduce Programming Model•Input & Output: sets of <key, value> pairs•Programmer writes 2 functions:map (in_key, in_value) -> list(out_key, intermediate_value)•Processes <k,v> pairs•Produces intermediate pairsreduce (out_key, list(interm_val)) -> list(out_value)•Combines intermediate values for a key•Produces a merged set of outputsExample: Counting Words…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"); reduce(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));MapReduce handles all the other details!How does parallelization work?INPUTFILE(s)All you have to do is…•Make all your programs into MapReduce algorithms…MapReduce is Turing complete!•Can we really make any program this way?Your Project: A Search Engine$> hadoop -j search.jar “out damned spot”Search Complete10 relevant files foundTerms: out, damned, spotmacbeth (MAX_RELEVANCE)...Out, damned spot!......Like Valor's minion carved out his passage......What hands are here? Ha, they pluck out mine eyes!......MACBETH. Hang out our banners on the outward walls;......Lady Macbeth is carried out....…Search Engine Components•Use Hadoop (open source MapReduce)•5 pairs of Map/Reduce classes–Search Index: make the search fast–Summary Index: make summarizing fast–Search: the actual search–Winnow: choose the most relevant results–Present: generate some pretty outputSearch Engine OverviewExample: Indexing (2)public void map() { String line = value.toString(); StringTokenizer itr = new StringTokenizer(line); if(itr.countTokens() >= N) { while(itr.hasMoreTokens()) { word = itr.nextToken()+“|”+key.getFileName(); output.collect(word, 1); } }}Input: a line of text, e.g. “mistakes were made” from myfile.txtOutput: mistakes|myfile.txtwere|myfile.txtmade|myfile.txtExample: Indexing (3) public void reduce() {int sum = 0;while(values.hasNext()) { sum += values.next().get();}output.collect(key, sum); }Input: a <term,filename> pair, list of occurrences (e.g. {1, 1,..1})Output: mistakes|myfile.txt 10were|myfile.txt 45made|myfile.txt 2Have fun!(Read the


View Full Document

UT CS 372 - MapReduce

Documents in this Course
Processes

Processes

19 pages

MapReduce

MapReduce

17 pages

Load more
Download MapReduce
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view MapReduce and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view MapReduce 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?