Back to Subject

Unit 3: Map Reduce and YARN

INT312 — Big Data Fundamentals 8 min read

I. MapReduce Foundations

MapReduce is a distributed programming model introduced by Google (2004) and implemented in Hadoop for processing large datasets across a cluster. A job transforms input records into intermediate key–value pairs, groups values having the same key, and reduces each group to final output.

  • Core abstraction: Data is processed as key–value pairs:
    TEXT
      map(K1, V1) → list(K2, V2)
  reduce(K2, list(V2)) → list(K3, V3)

    K1 and V1 are input types; K2 and V2 are intermediate types; K3 and V3 are output types.
  • Processing sequence: Hadoop performs input splitting, mapping, optional combining, partitioning, shuffling, sorting, reducing, and output writing.
  • Data locality: YARN attempts to run map tasks near the HDFS blocks they process, reducing network transfer.
  • Parallelism: Multiple mappers process separate input splits concurrently; reducers process different key partitions concurrently.
  • Fault tolerance: Failed tasks are re-executed, while HDFS replication protects input data.
  • Java conventions: Hadoop commonly uses Writable types such as Text, IntWritable, LongWritable, and NullWritable instead of ordinary Java types during serialization.

II. MapReduce Java API — Mapper, Reducer, and Driver

A. Review of the Java code required to handle the Mapper class

A Mapper reads one input record at a time and emits zero or more intermediate key–value pairs.

  • Class declaration: Mapper<K1,V1,K2,V2> fixes the mapper’s input and output types.
  • Lifecycle methods:
    • setup() runs once before records are processed.
    • map() runs once per input record.
    • cleanup() runs once after all records assigned to the mapper.
  • Default text input: With TextInputFormat, the key is the byte offset (LongWritable) and the value is one line (Text).
  • Emission: context.write(key, value) sends a pair to the shuffle phase.
  • Object reuse: Reusing writable objects reduces temporary-object creation.
JAVA
public static class TokenMapper
    extends Mapper<LongWritable, Text, Text, IntWritable> {

    private static final IntWritable ONE = new IntWritable(1);
    private final Text outKey = new Text();

    @Override
    protected void map(LongWritable offset, Text line, Context context)
            throws IOException, InterruptedException {
        for (String token : line.toString().toLowerCase().split("\\W+")) {
            if (!token.isEmpty()) {
                outKey.set(token);
                context.write(outKey, ONE);
            }
        }
    }
}
  • Concrete transformation: The line "Big data, big value" produces (big,1), (data,1), (big,1), and (value,1).
  • Restriction: Mapper output types configured in the job must exactly match Text and IntWritable in this declaration.

B. Review of the Java code required to handle the Reducer class

A Reducer receives one intermediate key and an iterable containing all values associated with that key.

  • Class declaration: Reducer<K2,V2,K3,V3> identifies intermediate input and final output types.
  • Shuffle guarantee: All values for a key are sent to one reducer; keys arrive in sorted order.
  • Iterable handling: Values should be consumed inside reduce() because Hadoop may reuse writable objects.
  • Aggregation: Operations such as sum, minimum, maximum, and count are common reductions.
JAVA
public static class SumReducer
    extends Reducer<Text, IntWritable, Text, IntWritable> {

    private final IntWritable result = new IntWritable();

    @Override
    protected void reduce(Text key, Iterable<IntWritable> values,
                          Context context)
            throws IOException, InterruptedException {
        int sum = 0;
        for (IntWritable value : values) {
            sum += value.get();
        }
        result.set(sum);
        context.write(key, result);
    }
}
  • Concrete transformation: (big,[1,1]) becomes (big,2).
  • Combiner use: This reducer can also be a combiner because integer addition is associative and commutative; a combiner is an optimization, not guaranteed to execute.

C. Program driver needed to access MapReduce

The driver creates and configures a Job, identifies its Java classes and data types, and submits it to YARN.

  • Configuration duties: The driver specifies the JAR, mapper, reducer, optional combiner, input path, output path, and key–value classes.
  • Output requirement: The output directory must not already exist; Hadoop normally refuses to overwrite it.
  • Exit status: waitForCompletion(true) returns true for success and false for failure.
JAVA
public class WordCount extends Configured implements Tool {
    public int run(String[] args) throws Exception {
        Job job = Job.getInstance(getConf(), "word count");
        job.setJarByClass(WordCount.class);

        job.setMapperClass(TokenMapper.class);
        job.setCombinerClass(SumReducer.class);
        job.setReducerClass(SumReducer.class);

        job.setMapOutputKeyClass(Text.class);
        job.setMapOutputValueClass(IntWritable.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;
    }

    public static void main(String[] args) throws Exception {
        System.exit(ToolRunner.run(new Configuration(),
                                   new WordCount(), args));
    }
}
  • Execution: A typical command is:
    BASH
      hadoop jar app.jar WordCount /input /output

III. YARN — Cluster Resource Management

A. YARN model

YARN, or Yet Another Resource Negotiator, separates cluster resource management from application-specific processing so that MapReduce and other distributed frameworks can share a Hadoop cluster.

  • ResourceManager: The cluster-wide authority that accepts applications and allocates resources through its scheduler.
  • NodeManager: Runs on each worker node, launches containers, monitors resource use, and reports node health.
  • ApplicationMaster: One is created per application; it requests containers, coordinates tasks, and handles task failures.
  • Container: A bounded execution environment described by resources such as memory and virtual CPU cores.
  • Submission sequence:
    1. The client submits the job to the ResourceManager.
    2. The ResourceManager allocates a container for the ApplicationMaster.
    3. The ApplicationMaster negotiates mapper and reducer containers.
    4. NodeManagers launch tasks in those containers.
    5. Progress and status are reported to the client.
  • Scheduling: Capacity Scheduler and Fair Scheduler allocate shared cluster resources according to queue policies.
  • MapReduce relationship: YARN manages resources and execution, while the MapReduce framework manages input splits, shuffle, sort, and task logic.
  • Limitation: A container is a resource allocation rather than a virtual machine; poorly selected memory settings can cause container termination or wasted capacity.

IV. MapReduce Programming Patterns

The following programs use Hadoop’s org.apache.hadoop.io and org.apache.hadoop.mapreduce classes. Each mapper and reducer is configured in a driver using the pattern already shown.

A. Java code for word count

Word count emits (word,1) for every normalized token and adds the values associated with each word.

  • Mapper: Use TokenMapper from Section II-A.
  • Reducer: Use SumReducer from Section II-B.
  • Driver settings:
    JAVA
      job.setMapperClass(TokenMapper.class);
  job.setCombinerClass(SumReducer.class);
  job.setReducerClass(SumReducer.class);
  job.setOutputKeyClass(Text.class);
  job.setOutputValueClass(IntWritable.class);
  • Example: Input "data grows data" produces:
    TEXT
      data    2
  grows   1
  • Normalization choice: toLowerCase() merges Data and data, while split("\\W+") treats non-word characters as separators.

B. Java code for sum of even numbers

A global even-number sum maps every even integer to one common key and reduces all emitted values by addition.

  • Mapper rule: Emit NullWritable as the common key only when n % 2 == 0, where n is the parsed integer.
  • Single reducer: One reducer is required for one global total.
JAVA
public static class EvenMapper extends
    Mapper<LongWritable, Text, NullWritable, LongWritable> {

    protected void map(LongWritable k, Text line, Context c)
            throws IOException, InterruptedException {
        for (String s : line.toString().trim().split("\\s+")) {
            if (!s.isEmpty()) {
                long n = Long.parseLong(s);
                if (n % 2 == 0)
                    c.write(NullWritable.get(), new LongWritable(n));
            }
        }
    }
}

public static class EvenReducer extends
    Reducer<NullWritable, LongWritable, NullWritable, LongWritable> {

    protected void reduce(NullWritable k, Iterable<LongWritable> values,
                          Context c)
            throws IOException, InterruptedException {
        long sum = 0;
        for (LongWritable value : values) sum += value.get();
        c.write(NullWritable.get(), new LongWritable(sum));
    }
}
  • Configuration: Set EvenReducer as both combiner and reducer and call job.setNumReduceTasks(1).
  • Example: For 3 4 8 9, the output is 12.

C. Java code for palindrome

A palindrome program tests normalized tokens and counts occurrences of tokens that read identically from left to right and right to left.

  • Test condition: For string s of length m, require s.charAt(i) == s.charAt(m-1-i) for every i < m/2.
  • Output meaning: Each key is a palindrome and its value is its frequency.
JAVA
public static class PalindromeMapper extends
    Mapper<LongWritable, Text, Text, IntWritable> {

    protected void map(LongWritable k, Text line, Context c)
            throws IOException, InterruptedException {
        for (String s : line.toString().toLowerCase().split("\\W+")) {
            if (s.isEmpty()) continue;
            boolean palindrome = true;
            for (int i = 0; i < s.length() / 2; i++)
                if (s.charAt(i) != s.charAt(s.length() - 1 - i))
                    palindrome = false;
            if (palindrome)
                c.write(new Text(s), new IntWritable(1));
        }
    }
}
  • Reduction: Reuse SumReducer; configure it as combiner and reducer.
  • Example: "level data level civic" produces civic 1 and level 2.

D. Java code for factorial

Factorial is defined for a non-negative integer n by n! = 1 × 2 × ... × n, with 0! = 1.

  • Representation: BigInteger prevents the overflow that occurs quickly with long; for example, 21! exceeds Long.MAX_VALUE.
  • Map-only design: Each input number is independent, so no shuffle or reducer is required.
JAVA
public static class FactorialMapper extends
    Mapper<LongWritable, Text, IntWritable, Text> {

    protected void map(LongWritable k, Text line, Context c)
            throws IOException, InterruptedException {
        for (String s : line.toString().trim().split("\\s+")) {
            int n = Integer.parseInt(s);
            if (n < 0) continue;

            BigInteger fact = BigInteger.ONE;
            for (int i = 2; i <= n; i++)
                fact = fact.multiply(BigInteger.valueOf(i));

            c.write(new IntWritable(n), new Text(fact.toString()));
        }
    }
}
  • Configuration: Use job.setNumReduceTasks(0) and set output types to IntWritable and Text.
  • Example: Input 5 gives 5 120.
  • Practical limit: Very large n creates extremely large output and expensive multiplication.

E. Java code for Armstrong number

An Armstrong number equals the sum of its decimal digits, each raised to the number of digits; thus 153 = 1³ + 5³ + 3³.

  • Variables: d is the number of digits and each character supplies one digit value.
  • Map-only filter: Emit only numbers satisfying the Armstrong equality.
JAVA
public static class ArmstrongMapper extends
    Mapper<LongWritable, Text, Text, Text> {

    protected void map(LongWritable k, Text line, Context c)
            throws IOException, InterruptedException {
        for (String s : line.toString().trim().split("\\s+")) {
            if (!s.matches("\\d+")) continue;

            BigInteger number = new BigInteger(s);
            int d = s.length();
            BigInteger sum = BigInteger.ZERO;

            for (char ch : s.toCharArray()) {
                int digit = ch - '0';
                sum = sum.add(BigInteger.valueOf(digit).pow(d));
            }

            if (sum.equals(number))
                c.write(new Text(s), new Text("Armstrong"));
        }
    }
}
  • Configuration: Set ArmstrongMapper as the mapper, select Text output types, and use zero reducers.
  • Examples: 0, 153, 370, 371, and 407 satisfy the test.
  • Input convention: The regular expression \d+ accepts non-negative decimal strings; signs and decimal points are excluded.
Previous
Unit 2
Next
Unit 4