What Is MapReduce and How Does It Work?

We will go forth explaining MapReduce. This posting is divided into total two or three parts and this Part.1 consists of introduction and structure.

MapReduce is a programming model and an associated implementation for processing and generating large data sets. Users specify a map function that processes a key/value pair to generate a set of intermediate key/value pairs, and a reduce function that merges all intermediate values associated with the same intermediate key.

Programs written in this functional style are automatically parallelized and executed on a large cluster of commodity machines. The run-time system takes care of the details of partitioning the input data, scheduling the program’s execution across a set of machines, handling machine failures, and managing the required inter-machine communication.

Below Figure 1 shows the overall flow of a MapReduce operation in implementation.

Step 1: Split Input

Core of parallel processing is to divide the input into several pieces. It is called split or shard. If only the input data is larger than block size (Default: 64MB), split is generated. When we split the input data, operational time is shorted and the more we split it, the more it brings dispersion effect. But, too small split may generate larger load as managing and creating map task.

Step 2: Fork Processes

Next step is to generate master and worker. A role of master assigns workers for a job and traces the progress situation and returns the result. Master also assign idle worker for a work.

Step 3: Map

Each map task reads data of key/value pairs from the input shard(split). It does parsing and analysis to Read data, and generates key/value pairs for the data. It can also raise performance by carrying out Map function in parallel.

Step 4: Map worker – Partition

Key/value pairs, generated in each worker, are transferred to stream and are stored in local disk for a time. Partitioning function simply hashes key module R, but it can be substituted for partitioning function in case of specific key.

Step 5: Reduce – Sort (Shuffle)

If every map task completes the work, master starts to reduce task. Reduce task need to have all output data of map task. Reduce task reads buffered data from the local disk by RPC(Remote Procedure Calls). If it sorts larger data than the memory, it uses external sort.

Step 6: Reduce function

Reduce task copies and merges the output data of all map tasks. After finishing merge, it calls out and analyzes the reduce function.

Step 7: Done!

After finishing all performance, master hands over the control to user program. Output of MapReduce is stored in HDFS.

In conclusion, all process of MapReduce is the above. Just, if you would like to operate process user wanted, use the above process or reply in spare moments.

[References] 1. http://www.cs.rutgers.edu/~pxk/417/notes/content/mapreduce.html 2. MapReduce: Simplied Data Processing on Large Clusters, Jeffrey Dean and Sanjay Ghemawat