Can I get invidually sorted Mapper outputs from Hadoop when using zero Reducers?

Question

I have a job in Hadoop 0.20 that needs to operate on large files, one at a time. (It's a pre-processing step to get file-oriented data into a cleaner, line-based format more suitable for MapReduce.)

I don't mind how many output files I have, but each Map's output can be in at most one output file, and each output file must be sorted.

• If I run with numReducers=0, it runs quickly, and each Mapper writes out its own output file which is fine - but the files aren't sorted.
• If I add one reducer (plain Reducer.class) this adds an unnecessary global sort step to a single file, which takes many hours (much longer than the Map tasks take).
• If I add multiple reducers, the results of individual map jobs are mixed together so one Map's output ends up in multiple files.

Is there any way to persuade Hadoop to perform a map-side sort on the output of each job, without using Reducers, or any other way of skipping the slow global merge?

Answer 1

One way of doing global sorting is to have a custom partitioner and do range partitioning for your reducers. For this to work you have to know the range of your mapper output key. You could divide your key range into n buckets where n is the number of reducers. Depending on the bucket the key maps into, the mapper output gets routed to a specific reducer.

Output of each reducer is sorted. Collection of all reducer output is globally sorted, because of the range partitioning. All you have to do is to take the reducer output files in the same order as the 5 digits in the file name.

One thing to watch out for is the skew in your key distribution, which will result in uneven reducer load in the cluster. This problem can be alleviated if you have distribution information i.e., histogram of the key. Then you could make your bucket length unequal and each one holding approximately same number of keys.

Hope it helps.