Top N values by Hadoop Map Reduce code

17
votes

I am very new in hadoop world and struggling to achieve one simple task.

Can anybody please tell me how to get top n values for word count example by using only Map reduce code technique?

I do not want to use any hadoop command for this simple task.

1
hadoopmapreduce
What do you mean "I do not want to use any hadoop command for this simple task"? - Donald Miner
In Hadoop, the reducer sorts the output on the basis of the value of keys. So while writing the output, if we just swap the key and value, i. e., write the value (which will be the count) as the key and the key as the value, then it'll sort on the basis of values. Then all we have to do is run the command: hadoop fs -cat <file_location_in_hdfs> | tail -n where n is the top n values you want to know. But I donot want to use the above command to accomplish the task.I just want to do it by map reduce progamming only. - user3078014
Wrong. The reducer does not sort the output. The reducer sorts its input from the mappers! Big difference! - Donald Miner
Also, you are selling yourself short by not wanting to do tail -n. Why solve a problem that doesn't require parallel programming with parallel programming? You really want to run a M/R job over a few thousand records?? - Donald Miner

1 Answers

23
votes

You have two obvious options:

Have two MapReduce jobs:

  1. WordCount: counts all the words (pretty much the example exactly)
  2. TopN: A MapReduce job that finds the top N of something (here are some examples: source code, blog post)

Have the output of WordCount write to HDFS. Then, have TopN read that output. This is called job chaining and there are a number of ways to solve this problem: oozie, bash scripts, firing two jobs from your driver, etc.

The reason you need two jobs is you are doing two aggregations: one is word count, and the second is topN. Typically in MapReduce each aggregation requires its own MapReduce job.

First, have your WordCount job run on the data. Then, use some bash to pull the top N out.

hadoop fs -cat /output/of/wordcount/part* | sort -n -k2 -r | head -n20

sort -n -k2 -r says "sort numerically by column #2, in descending order". head -n20 pulls the top twenty.

This is the better option for WordCount, just because WordCount will probably only output on the order of thousands or tens of thousands of lines and you don't need a MapReduce job for that. Remember that just because you have hadoop around doesn't mean you should solve all your problems with Hadoop.

One non-obvious version, which is tricky but a mix of both of the above...

Write a WordCount MapReduce job, but in the Reducer do something like in the TopN MapReduce jobs I showed you earlier. Then, have each reducer output only the TopN results from that reducer.

So, if you are doing Top 10, each reducer will output 10 results. Let's say you have 30 reducers, you'll output 300 results.

Then, do the same thing as in option #2 with bash:

hadoop fs -cat /output/of/wordcount/part* | sort -n -k2 -r | head -n10

This should be faster because you are only postprocessing a fraction of the results.

This is the fastest way I can think of doing this, but it's probably not worth the effort.