Core Programming Paradigm

MapReduce is a distributed computing framework originally conceived by Google to handle massive datasets. It breaks down complex data processing tasks into two fundamental functions: Map and Reduce. This abstraction allows developers to focus on business logic while the framework handles parallelization, fault tolerance, and data distribution.

Map Phase

The Map function processes raw input records. It takes a key-value pair as input and emits a list of intermediate key-value pairs.

• Input: A single record identified by a key and a value.
• Logic: Transforms the input data into intermediate tuples.
• Output: Zero or more intermediate key-value pairs.

map(inputKey, inputValue) -> collection(intermediateKey, intermediateValue)

Reduce Phase

The Reduce function aggregates the intermediate data. It reecives a specific key and a list of all values associated with that key from the Map phase.

• Input: An intermediate key and an iterator of corresponding values.
• Logic: Merges, filters, or summarizes the value list.
• Output: Final processed key-value pairs.

reduce(intermediateKey, listOfValues) -> collection(finalKey, finalValue)

Execution Lifecycle

A MapReduce job progresses through a strict sequence of stages within the cluster:

1. Data Partitioning: The input file is split into logical chunks. Each chunk is assigned to a specific Map task.
2. Mapping: Worker nodes execute the Map function on their assigned chunks, generating intermediate data.
3. Shuffling & Sorting: The framework partitions the intermediate data by key, sorts it, and transports it across the network to the appropriate Reducer nodes.
4. Reducing: Reducers process the grouped values for each key to produce the final output.
5. Persistence: The results are written to the distributed file system.

Hadoop Architecture

Apache Hadoop is the primary open-source implementation of this model. Its architecture relies on a master-slave structure:

• ResourceManager (Modern YARN): The master daemon responsible for negotiating resources and scheduling tasks across the cluster.
• NodeManager: The slave daemon running on worker nodes, responsible for launching and monitoring containers that execute the Map and Reduce tasks.

Code Example: Frequency Counting

The following example demonstrates a classic text analysis task using the Hadoop API. It counts the occurrences of every unique word in a dataset.

Mapper Implementation

import org.apache.hadoop.io.*;
import org.apache.hadoop.mapreduce.*;
import java.io.IOException;
import java.util.StringTokenizer;

public class WordMapper extends Mapper<LongWritable, Text, Text, IntWritable> {
    private final static IntWritable unitCount = new IntWritable(1);
    private Text term = new Text();

    @Override
    public void map(LongWritable offset, Text line, Context ctx) throws IOException, InterruptedException {
        StringTokenizer parser = new StringTokenizer(line.toString().toLowerCase());
        while (parser.hasMoreTokens()) {
            term.set(parser.nextToken());
            ctx.write(term, unitCount);
        }
    }
}

Reducer Implementtaion

import org.apache.hadoop.io.*;
import org.apache.hadoop.mapreduce.*;
import java.io.IOException;

public class WordReducer extends Reducer<Text, IntWritable, Text, IntWritable> {
    private IntWritable total = new IntWritable();

    @Override
    public void reduce(Text key, Iterable<IntWritable> counts, Context ctx) throws IOException, InterruptedException {
        int aggregate = 0;
        for (IntWritable val : counts) {
            aggregate += val.get();
        }
        total.set(aggregate);
        ctx.write(key, total);
    }
}

Job Configuration

import org.apache.hadoop.conf.Configured;
import org.apache.hadoop.fs.Path;
import org.apache.hadoop.io.*;
import org.apache.hadoop.mapreduce.*;
import org.apache.hadoop.mapreduce.lib.input.FileInputFormat;
import org.apache.hadoop.mapreduce.lib.output.FileOutputFormat;
import org.apache.hadoop.util.Tool;

public class FrequencyCounter extends Configured implements Tool {
    public int run(String[] args) throws Exception {
        Job job = Job.getInstance(getConf(), "Frequency Count");
        job.setJarByClass(FrequencyCounter.class);
        
        job.setMapperClass(WordMapper.class);
        job.setReducerClass(WordReducer.class);
        job.setCombinerClass(WordReducer.class);
        
        job.setOutputKeyClass(Text.class);
        job.setOutputValueClass(IntWritable.class);
        
        FileInputFormat.addInputPath(job, new Path(args[0]));
        FileOutputFormat.setOutputPath(job, new Path(args[1]));
        
        return job.waitForCompletion(true) ? 0 : 1;
    }
}

Characteristics and Trade-offs

Strengths:

• Horizontal Scalability: Capable of processing petabytes of data by adding more commodity hardware.
• Fault Tolerance: Automatically reassigns failed tasks to healthy nodes.
• Abstraction: Shields developers from the complexities of network programming and concurrent thread management.

Limitations:

• Latency: High overhead in task startup makes it unsuitable for real-time streaming or interactive queries.
• Disk I/O: Frequent writing to disk between the Map and Reduce stages creates significant I/O bottlenecks.
• Complexity: Implementing complex logic often requires chaining multiple MapReduce jobs together.

Common Use Cases

• Log Analysis: Parsing and aggregating server logs to extract insights on traffic or errors.
• Web Indexing: Building inverted indexes for search engines by processing crawled web content.
• ETL Operations: Transforming raw, unstructured data into structured formats for data warehouses.