[Nutch Wiki] Trivial Update of "MapReduce" by LewisJohnMcgibbney

[Apache Wiki <wi...@apache.org>]

Dear Wiki user,

You have subscribed to a wiki page or wiki category on "Nutch Wiki" for change notification.

The "MapReduce" page has been changed by LewisJohnMcgibbney:
http://wiki.apache.org/nutch/MapReduce?action=diff&rev1=7&rev2=8

+ = How Map and Reduce operations are actually carried out =
+ == Introduction ==
+ 
+ This document describes how MapReduce operations are carried out in Hadoop. If you are not familiar with the Google [[http://labs.google.com/papers/mapreduce.html|MapReduce]] programming model you should get acquainted with it first.
+ 
  [[http://weblogs.java.net/blog/tomwhite/archive/2005/09/mapreduce.html#more|"Excerpt from TomWhite's blog: MapReduce"]]<<BR>>
- 
-  * MapReduce is the brainchild of Google and is very well documented by Jeffrey Dean and Sanjay Ghemawat in their paper [[http://labs.google.com/papers/mapreduce.html|"MapReduce: Simplified Data Processing on Large Clusters"]].
  
   * In essence, it allows massive data sets to be processed in a distributed fashion by breaking the processing into many small computations of two types:
    1. A Map operation that transforms the input into an intermediate representation.
@@ -10, +13 @@

  
   * This processing model is ideal for the operations a search engine indexer like Nutch or Google needs to perform - like computing inlinks for URLs, or building inverted indexes - and it will [[attachment:Presentations/mapred.pdf|"transform Nutch"]] into a scalable, distributed search engine.
  
+ <<TableOfContents(3)>>
+ 
+ == Map ==
+ 
+ As the Map operation is parallelized the input file set is first
+ split to several pieces called [[http://hadoop.apache.org/core/docs/current/api/org/apache/hadoop/mapreduce/lib/input/FileSplit.html|FileSplits]]. If an individual file
+ is so large that it will affect seek time it will be split to
+ several Splits. The splitting does not know anything about the
+ input file's internal logical structure, for example
+ line-oriented text files are split on arbitrary byte boundaries.
+ Then a new map task is created per !FileSplit.
+ 
+ When an individual map task starts it will open a new output
+ writer per configured reduce task. It will then proceed to read
+ its !FileSplit using the [[http://hadoop.apache.org/core/docs/current/api/org/apache/hadoop/mapred/RecordReader.html|RecordReader]] it gets from the specified
+ [[http://hadoop.apache.org/core/docs/current/api/org/apache/hadoop/mapreduce/InputFormat.html|InputFormat]]. !InputFormat parses the input and generates
+ key-value pairs. !InputFormat must also handle records that may be split on the !FileSplit boundary. For example [[http://hadoop.apache.org/core/docs/current/api/org/apache/hadoop/mapreduce/lib/input/TextInputFormat.html|TextInputFormat]] will read the last line of the !FileSplit past the split boundary and, when reading other than the first !FileSplit, !TextInputFormat ignores the content up to the first newline.
+ 
+ It is not necessary for the !InputFormat to
+ generate both meaningful keys ''and'' values. For example the
+ default output from !TextInputFormat consists of input lines as
+ values and somewhat meaninglessly line start file offsets as
+ keys - most applications only use the lines and ignore the
+ offsets.
+ 
+ As key-value pairs are read from the !RecordReader they are
+ passed to the configured [[http://hadoop.apache.org/core/docs/current/api/org/apache/hadoop/mapreduce/Mapper.html|Mapper]]. The user supplied Mapper does
+ whatever it wants with the input pair and calls	[[http://hadoop.apache.org/core/docs/current/api/org/apache/hadoop/mapred/OutputCollector.html#collect(org.apache.hadoop.io.WritableComparable,%20org.apache.hadoop.io.Writable)|OutputCollector.collect]] with key-value pairs of its own choosing. The output it
+ generates must use one key class and one value class.  This is because
+ the Map output will be written into a SequenceFile
+ which has per-file type information and all the records must
+ have the same type (use subclassing if you want to output
+ different data structures). The Map input and output key-value
+ pairs are not necessarily related typewise or in cardinality.
+ 
+ When Mapper output is collected it is partitioned, which means
+ that it will be written to the output specified by the
+ [[http://hadoop.apache.org/core/docs/current/api/org/apache/hadoop/mapreduce/Partitioner.html|Partitioner]]. The default [[http://hadoop.apache.org/core/docs/current/api/org/apache/hadoop/mapreduce/lib/partition/HashPartitioner.html|HashPartitioner]] uses the
+ hashcode function on the key's class (which means that this hashcode function must be good in order to achieve an even workload across the reduce tasks).  See [[http://svn.apache.org/viewcvs.cgi/hadoop/core/trunk/src/mapred/org/apache/hadoop/mapred/MapTask.java?view=markup|MapTask]] for details.
+ 
+ N input files will generate M map tasks to be run and each map
+ task will generate as many output files as there are reduce
+ tasks configured in the system. Each output file will be
+ targeted at a specific reduce task and the map output pairs from
+ all the map tasks will be routed so that all pairs for a given
+ key end up in files targeted at a specific reduce task.
+ 
+ == Combine ==
+ When the map
+ operation outputs its pairs they are already available in
+ memory. For efficiency reasons, sometimes it makes sense to
+ take advantage of this fact by supplying a combiner class
+ to perform a reduce-type function. If a combiner is used then the
+ map key-value pairs are not immediately written to the output. Instead they
+ will be collected in lists, one list per each key value. When a
+ certain number of key-value pairs have been written, this buffer
+ is flushed by passing all the values of each key to the
+ combiner's reduce method and outputting the key-value pairs of
+ the combine operation as if they were created by the original map
+ operation.
+ 
+ For example, a word count !MapReduce application whose map
+ operation outputs (''word'', 1) pairs as words are encountered in
+ the input can use a combiner to speed up processing. A combine
+ operation will start gathering the output in in-memory lists (instead
+ of on disk), one list per word. Once a certain number of
+ pairs is output, the combine operation will be called once per
+ unique word with the list available as an iterator. The combiner
+ then emits (''word'', count-in-this-part-of-the-input) pairs. From
+ the viewpoint of the Reduce operation this contains the same
+ information as the original Map output, but there should be far fewer
+ pairs output to disk and read from disk.
+ 
+ == Reduce ==
+ When a reduce task starts, its input is scattered in many files across all the nodes where map tasks ran. If run in
+ distributed mode these need to be first copied to the local
+ filesystem in a ''copy phase'' (see [[https://svn.apache.org/viewcvs.cgi/hadoop/core/trunk/src/mapred/org/apache/hadoop/mapred/ReduceTaskRunner.java?view=markup|ReduceTaskRunner]]).
+ 
+ Once all the data is available locally it is appended to one
+ file in an ''append phase''. The file is then merge sorted so that the key-value pairs for
+ a given key are contiguous (''sort phase''). This makes the actual reduce operation simple: the file is
+ read sequentially and the values are passed to the reduce method
+ with an iterator reading the input file until the next key
+ value is encountered. See [[http://svn.apache.org/viewcvs.cgi/hadoop/core/trunk/src/mapred/org/apache/hadoop/mapred/ReduceTask.java?view=markup|ReduceTask]] for details.
+ 
+ At the end, the output will consist of one output file per executed reduce
+ task. The format of the files can be specified with
+ [[http://hadoop.apache.org/core/docs/current/api/org/apache/hadoop/mapred/JobConf.html#setOutputFormat(java.lang.Class)|JobConf.setOutputFormat]]. If !SequentialOutputFormat is used then the output key and value
+ classes must also be specified.
+