CS 61C Lab 2

MapReduce

Setup

You may work on this lab in partners. It will be especially helpful if one of the partners has some experience in coding Java.

The MapReduce programming framework is primarily designed to be used on large distributed clusters. However, large distributed jobs are harder to debug. So instead, for this lab, we’ll be using Hadoop -- an open source platform which implements MapReduce programming -- in “local mode”, where your Map and Reduce routines are run entirely within one process. (Never fear, the next lab will involve running your code on distributed clusters on EC2!)

You should complete this lab on the machines in 330 Soda. If you are not sitting physically in front of one of these lab machines, you can access one of them remotely by following these instructions.

Copy the template files for this lab from ~cs61c/lab/02 using

$ cp -R ~cs61c/labs/02 lab02

Exercise 0: Running Word Count

First, compile the code by

$ make

The make command follows the instructions inside of Makefile to compile the source in WordCount.java into wc.jar. Next, run the word count example

$ hadoop jar wc.jar WordCount ~cs61c/data/billOfRights.txt.seq wc-out

This will run word count over a sample input file (US Bill of Rights). Your output should be visible in wc-out/part-r-00000. If you had multiple reduces, then the output would be split across part-r-[id. num], where Reducer "id. num" outputs to the corresponding file. The plain-text for the test code is in ~cs61c/data/billOfRights.txt. For the input to your MapReduce job, the key for map() is the document identifier and the value is the actual text.

Once you have things working on the small test case, try your code on the larger input file ~cs61c/data/sample.seq (approx. 34 MiB). This file contains the text of one week's worth of newsgroup posts (corpus).

$ rm -rf wc-out
$ hadoop jar wc.jar WordCount ~cs61c/data/sample.seq wc-out

Hadoop requires the output directory not to exist when a MapReduce job is executed, which is why we deleted the wc-out directory. Alternatively, we could have chosen a different output directory.

You may notice that the Reduce percentage-complete percentage moves in strange ways. There’s a reason for it. Your code is only the last third of the progress counter. Hadoop treats the distributed shuffle as the first third of the Reduce and the sort as the second third. Locally, the sort is quick and the shuffle doesn’t happen at all. So don’t be surprised if progress jumps to 66% and then slows.

Exercise 1: Document Word Count

Copy WordCount.java to DocWordCount.java. Rename the class (in the file) from 'WordCount' to 'DocWordCount'. Modify it to count the number of documents containing each word rather than the number of times each word occurs in the input. Run make to compile your modified version, and then run it on the same inputs as before.

You should only need to modify the code inside the map() function for this part. Each call to map() gets a single document, and each document is passed to exactly one map().

Exercise 2: Full Text Index Creation

Create a new file (and class) called Index.java based on WordCount.java. Modify it to output, for each word, a list of the locations (word number in the document and identifier for the document) in which the word occurs. (An identifier for each document is provided as the key to the mapper.) Your output should have lines that look like:

word       document1-id:word#,word#,word#...

Minor line formatting details don’t matter. You should number words in a document starting with zero. The output for each word should be together in your output file. You can assume that there’s just one reducer and hence just one output file. For each word, there should be one line for each document containing that word. To lower the output size and memory requirements, don't output more than a thousand locations for any given word.

For this exercise, you probably need to modify map(), reduce() and the type signature for Reduce. You will also need to make a minor edit to main() to tell the framework about the new type signature for Reduce.

Compile and run this MapReduce program on the same inputs as the previous exercises.

Checkoff

Show the TA your DocWordCount.java 
Show the TA your Index.java 
Show the TA the output from running your Index on sample.seq 

Before you leave, be sure to save your code since you may need it for lab 3. We recommend deleting output directories when you have completed the lab, so you don't run out of your 500MB of disk quota

Additional Resources