What is the purpose of shuffling and sorting phase in the reducer in Map Reduce Programming?

by

First of all shuffling is the process of transfering data from the mappers to the reducers, so I think it is obvious that it is necessary for the reducers, since otherwise, they wouldn’t be able to have any input (or input from every mapper). Shuffling can start even before the map phase has finished, to save some time. That’s why you can see a reduce status greater than 0% (but less than 33%) when the map status is not yet 100%.

Sorting saves time for the reducer, helping it easily distinguish when a new reduce task should start. It simply starts a new reduce task, when the next key in the sorted input data is different than the previous, to put it simply. Each reduce task takes a list of key-value pairs, but it has to call the reduce() method which takes a key-list(value) input, so it has to group values by key. It’s easy to do so, if input data is pre-sorted (locally) in the map phase and simply merge-sorted in the reduce phase (since the reducers get data from many mappers).

Partitioning, that you mentioned in one of the answers, is a different process. It determines in which reducer a (key, value) pair, output of the map phase, will be sent. The default Partitioner uses a hashing on the keys to distribute them to the reduce tasks, but you can override it and use your own custom Partitioner.

A great source of information for these steps is this Yahoo tutorial (archived).

A nice graphical representation of this is the following (shuffle is called “copy” in this figure):

enter image description here

Note that shuffling and sorting are not performed at all if you specify zero reducers (setNumReduceTasks(0)). Then, the MapReduce job stops at the map phase, and the map phase does not include any kind of sorting (so even the map phase is faster).

UPDATE: Since you are looking for something more official, you can also read Tom White’s book “Hadoop: The Definitive Guide”. Here is the interesting part for your question.
Tom White has been an Apache Hadoop committer since February 2007, and is a member of the Apache Software Foundation, so I guess it is pretty credible and official…

More Related Contents:

  1. How does Hadoop process records split across block boundaries?
  2. data block size in HDFS, why 64MB?
  3. How does Hadoop perform input splits?
  4. Default number of reducers
  5. Is it correct to use JavaScript Array.sort() method for shuffling?
  6. While writing to hdfs path getting error java.io.IOException: Failed to rename
  7. merge output files after reduce phase
  8. Write a file in hdfs with Java
  9. what is natural ordering when we talk about sorting?
  10. Setting the number of map tasks and reduce tasks
  11. Python read file as stream from HDFS
  12. Is it better to use the mapred or the mapreduce package to create a Hadoop Job?
  13. When do reduce tasks start in Hadoop?
  14. Associatively sorting a table by value in Lua
  15. Code an Excel VBA sort with a custom order and a value containing commas
  16. Oozie: Launch Map-Reduce from Oozie action?
  17. Reading file as single record in hadoop
  18. Hadoop speculative task execution
  19. Hive unable to manually set number of reducers
  20. MultipleOutputFormat in hadoop
  21. SQL Sorting and hyphens
  22. Spark iterate HDFS directory
  23. Hadoop: …be replicated to 0 nodes instead of minReplication (=1). There are 1 datanode(s) running and no node(s) are excluded in this operation
  24. Sort a Table[] in Lua
  25. Change File Split size in Hadoop
  26. How to list all files in a directory and its subdirectories in hadoop hdfs
  27. hadoop java.net.URISyntaxException: Relative path in absolute URI: rsrc:hbase-common-0.98.1-hadoop2.jar
  28. Difference between HBase and Hadoop/HDFS
  29. What is Hive: Return Code 2 from org.apache.hadoop.hive.ql.exec.MapRedTask
  30. How to define (and name) the corresponding safe term comparison predicates in ISO Prolog?

Leave a Comment