MapReduce

Procedure

HDFS(Hadoop Distributed File System)(stored in blocks)->Split(# of split=# of map tasks)->Map(Assign each key with value; generate (key, value) pairs)->Shuffle->Reduce(aggregate value)->HDFS

Shuffle

Let’s focus on shuffle part.

All the data in the map node will be partitioned(hash to different reduce node). Reduce node will get all the data in the corresponding partitions from different map nodes and perform reduce task only once.

Shuffle taken on map node = Partition(# of partition=# of reduce node) + merge sort(based on key) + (optional) combiner

Output will be stored in a Ring Buffer(up to 80%). Then reduce nodes will capture spill files via HTTP. Reduce node will get data from memory and disk of map node. If the map task is not completed yet, reduce node will merge sort data in time and wait for map task to finish.

Shuffle taken on reduce node = all the spill file generated by this map task will be merged (based on partition number) and generate (key, {value_list}) pair.

Merge will generate value list (key, {value_list}). Combiner will perform reduce task to compress data (key, value). Combiner is designed to decrease the IO pressure (from map node to reduce node). Reduce node only need to load a combined file instead of many small spill file.