[MAPREDUCE-4039] Sort Avoidance

• Type: New Feature
• Status: Open
• Priority: Minor
• Resolution: Unresolved
• Affects Version/s: 0.23.2
• Fix Version/s: 0.23.2
• Component/s: mrv2
• Target Version/s: 2.0.0-alpha
• Assignee: anty
• Reporter: anty.rao
• Created: 20/Mar/12 07:58
• Updated: 28/Jan/13 21:31

Description

Inspired by Tenzing, in 5.1 MapReduce Enhanceemtns:

Sort Avoidance. Certain operators such as hash join
and hash aggregation require shuffling, but not sorting. The
MapReduce API was enhanced to automatically turn off
sorting for these operations. When sorting is turned off, the
mapper feeds data to the reducer which directly passes the
data to the Reduce() function bypassing the intermediate
sorting step. This makes many SQL operators significantly
more ecient.

There are a lot of applications which need aggregation only, not sorting.Using sorting to achieve aggregation is costly and inefficient. Without sorting, up application can make use of hash table or hash map to do aggregation efficiently.But application should bear in mind that reduce memory is limited, itself is committed to manage memory of reduce, guard against out of memory. Map-side combiner is not supported, you can also do hash aggregation in map side as a workaround.

the following is the main points of sort avoidance implementation

1. add a configuration parameter mapreduce.sort.avoidance, boolean type, to turn on/off sort avoidance workflow.Two type of workflow are coexist together.
2. key/value pairs emitted by map function is sorted by partition only, using a more efficient sorting algorithm: counting sort.
3. map-side merge, use a kind of byte merge, which just concatenate bytes from generated spills, read in bytes, write out bytes, without overhead of key/value serialization/deserailization, comparison, which current version incurs.
4. reduce can start up as soon as there is any map output available, in contrast to sort workflow which must wait until all map outputs are fetched and merged.
5. map output in memory can be directly consumed by reduce.When reduce can't catch up with the speed of incoming map outputs, in-memory merge thread will kick in, merging in-memory map outputs onto disk.
6. sequentially read in on-disk files to feed reduce, in contrast to currently implementation which read multiple files concurrently, result in many disk seek. Map output in memory take precedence over on disk files in feeding reduce function.

I have already implement this feature based on hadoop CDH3U3 and done some performance evaluation, you can reference to https://github.com/hanborq/hadoop for details. Now,I'm willing to port it into yarn. Welcome for commenting.

Issue Links

• is related to: MAPREDUCE-2454 Allow external sorter plugin for MR