What is MapReduce and How Does It Work?

The act of processing data, which requires a lot of memory consumption, needs many physical machines to enable it. That is not always possible in the real world. Even the largest data centers in the early 2000s, despite having huge machine setups, still had the question of how the data could be split across these machines to conduct computation.

In today’s data-driven world, algorithms and applications are constantly collecting data, resulting in huge volumes of data. The big challenge is how to process this massive amount of data with speed and efficiency, and without sacrificing meaningful insights. To facilitate this, a programming model named MapReduce was initiated.

What is MapReduce?

MapReduce is a programming paradigm that allows us to perform distributed and parallel processing on large data sets in a distributed environment.

MapReduce facilitates concurrent processing by splitting petabytes of data into smaller chunks and processing them in parallel on commodity servers. In the end, it aggregates all the data from multiple servers to return a consolidated output back to the application.

MapReduce program works in two phases: Map and Reduce. Map tasks deal with splitting and mapping data, while Reduce tasks shuffle and reduce the data. The input to each phase is key-value pairs, which are then sorted out by the map and reduce functions.

MapReduce programming offers several benefits to help gain valuable insights from big data:

• Scalability - Businesses can process petabytes of data
• Flexibility - It enables easier access to multiple sources of data and multiple types of data
• Speed - With parallel processing and minimal data movement, it offers fast processing of massive amounts of data
• Simple - Developers can write code in a choice of languages, including Java, C++, and Python

Mapper step in MapReduce shuffles the input data.

What is Hadoop?

MapReduce is a component of the Apache Hadoop ecosystem, a framework that enhances massive data processing. Other components of Apache Hadoop include Hadoop Distributed File System (HDFS), Yarn and Apache Pig.

Some organizations rely on public cloud services for Hadoop and MapReduce, which offer enormous scalability with minimal capital costs or maintenance overhead.

For example, Amazon Web Services (AWS) provides Hadoop as a service through its Amazon Elastic MapReduce. Microsoft Azure offers its HDInsight service, which enables users to provision Hadoop, Apache Spark, and other clusters for data processing tasks. Google Cloud Platform provides its Cloud Dataproc service to run Spark and Hadoop clusters.

Example of MapReduce

You can better understand, how MapReduce works by taking an example where we would have a text file called example.txt whose contents are:

Deer, Bear, River, Car, Car, River, Deer, Car, Bear

Now, we can perform a word count on the sample.txt using MapReduce. So, we will be finding unique words and the number of occurrences of those unique words.

1. Divide the input into three splits as shown in the diagram. This will distribute the work among all the map nodes
2. Tokenize the words in each of the mappers and give a hardcoded value (1) to each of the tokens or words
3. A list of key-value pairs is created where the key is nothing but the individual words and the value is one. So, for (Deer Bear River) we have — Deer, 1; Bear, 1; River, 1
4. Sorting and shuffling happen so that all the tuples with the same key are sent to the corresponding reducer
5. After the sorting and shuffling phase, each reducer will have a unique key and a list of values corresponding to that very key. For example, Bear, [1,1]; Car, [1,1,1]...
6. Each Reducer counts the values which are present in that list of values, and gives the final output as — Bear, 2
7. All the output key/value pairs are collected and written in the output file

Code examples of MapReduce

Let's take the same example with the file sample.txt and code it into a program that will perform MapReduce. For the purpose of this example, the code will be written in Java, but MapReduce programs can be written in any language.

The entire MapReduce program can be fundamentally divided into three parts:

- Mapper Code The Map class extends the class Mapper which is already defined in the MapReduce Framework, and we define the input/output types.

public static class Map extends Mapper<LongWritable,Text,Text,IntWritable> {
    public void map(LongWritable key, Text value, Context context) throws IOException, InterruptedException {
        String line = value.toString();
        StringTokenizer tokenizer = new StringTokenizer(line);
        while (tokenizer.hasMoreTokens()) {
            value.set(tokenizer.nextToken());
            context.write(value, new IntWritable(1));
        }
    }
}

class Map {
    map(key, value, context) {
        const line = value.toString();
        const tokenizer = line.split(/\s+/);
        tokenizer.forEach(token => {
            value.set(token);
            context.write(value, 1);
        });
    }
}

class Map:
    def map(self, key, value, context):
        line = value.decode('utf-8')
        tokenizer = line.split()
        for token in tokenizer:
            value.set(token)
            context.write(value, 1)

class Map {
public:
    void map(LongWritable &key, Text &value, Context &context) {
        std::string line = value.toString();
        std::istringstream tokenizer(line);
        std::string token;
        while (tokenizer >> token) {
            value.set(token);
            context.write(value, IntWritable(1));
        }
    }
};

type Map struct{}

func (m *Map) Map(key LongWritable, value Text, context Context) {
    line := value.ToString()
    tokenizer := strings.Fields(line)
    for _, token := range tokenizer {
        value.Set(token)
        context.Write(value, IntWritable(1))
    }
}

** - Reducer Code** Reducer class which extends class Reducer like that of Mapper. We define the data types of input and output key/value pairs and we aggregate the values in each of the list corresponding to each key and produce the final answer.

public static class Reduce extends Reducer<Text,IntWritable,Text,IntWritable> {
    public void reduce(Text key, Iterable<IntWritable> values, Context context)
    throws IOException, InterruptedException {
        int sum = 0;
        for (IntWritable x: values) {
            sum += x.get();
        }
        context.write(key, new IntWritable(sum));
    }
}

class Reduce {
    reduce(key, values, context) {
        let sum = 0;
        values.forEach(x => {
            sum += x;
        });
        context.write(key, sum);
    }
}

class Reduce:
    def reduce(self, key, values, context):
        sum = 0
        for x in values:
            sum += x
        context.write(key, sum)

class Reduce {
public:
    void reduce(Text &key, std::vector<IntWritable> &values, Context &context) {
        int sum = 0;
        for (IntWritable &x : values) {
            sum += x.get();
        }
        context.write(key, IntWritable(sum));
    }
};

type Reduce struct{}

func (r *Reduce) Reduce(key Text, values []IntWritable, context Context) {
    sum := 0
    for _, x := range values {
        sum += x.Get()
    }
    context.Write(key, IntWritable(sum))
}

** - Driver Code ** In the driver class, we set the configuration of our MapReduce job to run in Hadoop. The given code snippet is specific to configuring a MapReduce job in Hadoop using Java. This type of code is typically not directly translated into other languages like JavaScript, Python, C++, or Go, as it is specific to the Hadoop Java API.

However, if you want to run similar MapReduce jobs in other languages, you would typically use a language-specific library or framework designed to interact with Hadoop or another distributed computing system.

Configuration conf= new Configuration();  
Job job = new Job(conf,"My Word Count Program");  
job.setJarByClass(WordCount.class);  
job.setMapperClass(Map.class);  
job.setReducerClass(Reduce.class);  
job.setOutputKeyClass(Text.class);  

job.setOutputValueClass(IntWritable.class);  
job.setInputFormatClass(TextInputFormat.class);  
job.setOutputFormatClass(TextOutputFormat.class);  
Path outputPath = new Path(args[1]);  

FileInputFormat.addInputPath(job, new Path(args[0]));  
FileOutputFormat.setOutputPath(job, new Path(args[1]));

The command for running a MapReduce code in Hadoop cmd prompt is:

_hadoop jar hadoop-mapreduce-example.jar WordCount /sample/input /sample/output_

import java.io.IOException;
import java.util.StringTokenizer;

import org.apache.hadoop.conf.Configuration;
import org.apache.hadoop.fs.Path;
import org.apache.hadoop.io.IntWritable;
import org.apache.hadoop.io.LongWritable;
import org.apache.hadoop.io.Text;
import org.apache.hadoop.mapreduce.Job;
import org.apache.hadoop.mapreduce.Mapper;
import org.apache.hadoop.mapreduce.Reducer;
import org.apache.hadoop.mapreduce.lib.input.FileInputFormat;
import org.apache.hadoop.mapreduce.lib.output.FileOutputFormat;
import org.apache.hadoop.mapreduce.lib.input.TextInputFormat;
import org.apache.hadoop.mapreduce.lib.output.TextOutputFormat;

public class WordCount {

    // Mapper Code
    public static class Map extends Mapper<LongWritable, Text, Text, IntWritable> {

        public void map(LongWritable key, Text value, Context context) throws IOException, InterruptedException {
            String line = value.toString();
            StringTokenizer tokenizer = new StringTokenizer(line);
            while (tokenizer.hasMoreTokens()) {
                value.set(tokenizer.nextToken());
                context.write(value, new IntWritable(1));
            }
        }
    }

    // Reducer Code
    public static class Reduce extends Reducer<Text, IntWritable, Text, IntWritable> {

        public void reduce(Text key, Iterable<IntWritable> values, Context context) throws IOException, InterruptedException {
            int sum = 0;
            for (IntWritable x : values) {
                sum += x.get();
            }
            context.write(key, new IntWritable(sum));
        }
    }

    // Driver Code
    public static void main(String[] args) throws Exception {
        Configuration conf = new Configuration();
        Job job = Job.getInstance(conf, "My Word Count Program");
        job.setJarByClass(WordCount.class);
        job.setMapperClass(Map.class);
        job.setReducerClass(Reduce.class);
        job.setOutputKeyClass(Text.class);
        job.setOutputValueClass(IntWritable.class);
        job.setInputFormatClass(TextInputFormat.class);
        job.setOutputFormatClass(TextOutputFormat.class);
        Path outputPath = new Path(args[1]);
        FileInputFormat.addInputPath(job, new Path(args[0]));
        FileOutputFormat.setOutputPath(job, outputPath);
        System.exit(job.waitForCompletion(true) ? 0 : 1);
    }
}

Before moving on, zoom out from the code. A MapReduce word-count job is easier to read when you separate what each file is responsible for.

Notice the three roles: the Mapper emits (word, 1), the framework groups values by word, the Reducer sums them, and the Driver tells Hadoop how to run the whole job.

After seeing the mapper, reducer, and driver code, zoom out and track the shape of the data.

The key idea: the mapper emits many small key/value pairs, Hadoop groups matching keys during the shuffle, and the reducer combines each group into the final answer.

Below, I'll provide a brief description of how you might approach a MapReduce word count task in each of the requested languages without translating the exact Java code.

JavaScript

In JavaScript, you could use a library like Hadoop-Streaming to run MapReduce jobs. A possible mapper and reducer written in Node.js might look like:

Mapper

process.stdin.on('data', function(chunk) {
  chunk.toString().split(/\s+/).forEach(word => {
    console.log(word + "\t1");
  });
});

Reducer

var counts = {};
process.stdin.on('data', function(chunk) {
  chunk.toString().trim().split("\n").forEach(line => {
    var parts = line.split("\t");
    var word = parts[0];
    var count = parseInt(parts[1]);
    counts[word] = (counts[word] || 0) + count;
  });
});

process.stdin.on('end', function() {
  for (var word in counts) {
    console.log(word + "\t" + counts[word]);
  }
});

Python

Python provides Hadoop Streaming for MapReduce. You could write your mapper and reducer like:

Mapper

#!/usr/bin/env python
import sys
for line in sys.stdin:
    words = line.strip().split()
    for word in words:
        print(f"{word}\t1")

Reducer

#!/usr/bin/env python
import sys

current_word = None
current_count = 0
word = None

for line in sys.stdin:
    line = line.strip()
    word, count = line.split('\t', 1)
    count = int(count)
    if current_word == word:
        current_count += count
    else:
        if current_word:
            print(f"{current_word}\t{current_count}")
        current_word = word
        current_count = count

if current_word == word:
    print(f"{current_word}\t{current_count}")

C++

C++ doesn't have a direct equivalent for Hadoop MapReduce, but you could use MPI (Message Passing Interface) for parallel processing or find a specific library tailored for distributed computing.

Go

Similarly, Go doesn't have a direct MapReduce framework like Hadoop for Java. However, you could build a distributed system using Go's native concurrency features or use a library like Glow for MapReduce-style processing.

Please note that these examples are quite high-level and may require additional code, configuration, and dependencies to run in a real distributed environment.

The last step of the MapReduce process is:

MapReduce programs have to be coded in Java.

The part of the MapReduce program where we set the configuration of our MapReduce job to run in Hadoop is called:

The language examples differ in syntax, but they are all obeying the same MapReduce contract.

For Hadoop Streaming-style jobs, the framework does not need to understand your whole program. It mainly needs predictable input and output shapes: read records in, emit key-value pairs, then reduce grouped values by key.

Whether the job is written in Java, JavaScript, Python, or another language, the interview-worthy concept is the same contract.

Your program must produce and consume key/value records in the expected format. Hadoop handles distribution, grouping, and task coordination around that contract.

One Pager Cheat Sheet

• To enable the efficient processing of large amounts of data, MapReduce was created to help alleviate the difficulty of splitting data across multiple physical machines.
• MapReduce is a programming paradigm that splits and maps large data sets into smaller chunks, processes them in parallel across commodity servers, and aggregates the data to return a consolidated output, providing benefits such as scalability, flexibility, speed and simplicity.
• No, the Mapper step does not shuffle the data, but instead it splits and maps it into key-value pairs before being further processed by the Map and Reduce functions.
• Apache Hadoop is an ecosystem that enhances massive data processing, and is a popular choice in public cloud services such as Amazon Elastic MapReduce, Microsoft HDInsight and Google Cloud Dataproc.
• Using MapReduce, you can tokenize, sort, shuffle, and reduce the unique words in an input file with a given value to create a new output file of key-value pairs of the unique words and their occurrences.
• The MapReduce program can be written in any language and can be divided into three main parts: a Mapper Code, Reducer Code, and a Driver Code, which sets the configuration of the program to be run in Hadoop using the command hadoop jar hadoop-mapreduce-example.jar WordCount /sample/input /sample/output.
• - MapReduce code usually splits into Mapper, Reducer, and Driver responsibilities.
• - MapReduce code is easiest to reason about as a pipeline: input split → map → shuffle/group → reduce → output.
• The last step of the MapReduce process is Reducing, where the data is aggregated and the output is computed by iterating over all values associated with a single key.
• Hadoop Streaming allows MapReduce programs to be written in various languages such as Python, C++ and Ruby, and to parse the input/output data format as specified by the protocol.
• The Driver Code defines the necessary configuration settings for Hadoop to execute a MapReduce job efficiently, by assigning tasks to the workers in the cluster.
• - MapReduce is language-flexible because the framework coordinates data flow through a shared key-value contract.
• - MapReduce is language-flexible, but the contract stays fixed: mapper emits key/value pairs, reducer aggregates grouped values, driver configures the job.