MapReduce and distributed processing notes — Unit 3

MapReduce is a programming model and an associated implementation for processing and generating large data sets with a parallel, distributed algorithm on a cluster.

⇒1.1 The Paradigm

The model is inspired by the `map` and `reduce` functions commonly used in functional programming. The framework hides the messy details of parallelization, fault-tolerance, data distribution, and load balancing from the programmer.

A MapReduce job executes in three primary phases: Map, Shuffle and Sort, and Reduce.

⇒2.1 Input Data

Data is read from HDFS blocks. The framework parses the data into Key-Value pairs (e.g., `LineNumber : Text of the line`) and feeds these pairs to the Mapper.

The Map phase is where the initial processing occurs. The programmer writes a `map()` function that is applied to every single input Key-Value pair independently.

⇒3.1 Operation

The Map function takes an input pair and produces zero or more intermediate Key-Value pairs. Because each pair is processed independently, millions of map tasks can run in parallel across the cluster.

Example (Word Count): Input `(1, "Hello World Hello")`. The Mapper splits the text and outputs `("Hello", 1)`, `("World", 1)`, `("Hello", 1)`.

This is the 'magic' phase handled entirely by the Hadoop framework behind the scenes. It acts as the bridge between Map and Reduce.

⇒4.1 Operation

The framework takes all the intermediate Key-Value pairs generated by the Mappers, sorts them by Key, and groups together all values associated with the same key.

Example (Word Count): The framework groups the outputs to form `("Hello", [1, 1])` and `("World", [1])`. It then transfers these grouped pairs over the network to the appropriate Reducer nodes.

The Reduce phase performs the aggregation or summarization of the data.

⇒5.1 Operation

The programmer writes a `reduce()` function. The framework calls this function once for each unique Key, passing it the Key and the list of all Values associated with that key.

Example (Word Count): The Reducer receives `("Hello", [1, 1])`. The reduce logic iterates through the list, sums the values, and outputs the final result: `("Hello", 2)` to HDFS.

Transferring massive amounts of intermediate data over the network during the Shuffle phase is the biggest bottleneck in MapReduce.

⇒6.1 Local Aggregation

A Combiner is essentially a 'mini-reducer' that runs directly on the Mapper node before data is sent across the network. It aggregates the output of the Mappers locally to save bandwidth.

If a single Mapper processes a document with the word 'the' appearing 1000 times, sending 1000 `("the", 1)` pairs over the network is wasteful. A Combiner aggregates it locally to `("the", 1000)` before network transfer.

Because MapReduce runs on commodity hardware, node failures are expected.

⇒7.1 Task Failures

If a worker node executing a Map task crashes, the framework (YARN) detects the failure (via missed heartbeats) and simply reschedules that specific Map task on another node that holds a replica of the necessary data block.

⇒7.2 Stragglers (Speculative Execution)

Sometimes a node doesn't crash but runs very slowly (a 'straggler'). Hadoop notices this and launches a duplicate 'speculative' task on a different node. Whichever task finishes first is used, and the other is killed, ensuring the overall job doesn't hang on one slow machine.

While MapReduce was revolutionary, it is slow for iterative algorithms (like machine learning) because it writes intermediate results to disk after every Map and Reduce phase.

⇒8.1 In-Memory Processing

Apache Spark emerged as the successor to MapReduce. Spark processes data in-memory (in RAM) rather than reading and writing to disk at every step.

This makes Spark up to 100x faster than Hadoop MapReduce for certain workloads. Spark supports Java, Scala, and Python, making it highly accessible.

The core abstraction in Spark is the RDD.

⇒9.1 Concept

An RDD is a fault-tolerant collection of elements that can be operated on in parallel. It is distributed across the nodes of the cluster. Crucially, RDDs are immutable—once created, they cannot be changed. You transform one RDD into a new RDD.

Because they are kept in memory, chaining operations (filter, map, reduce) is incredibly fast.

⇒10.1 Transformations

Operations like `map()`, `filter()`, or `join()` that create a new RDD from an existing one. Transformations in Spark are lazy—they are not computed immediately. Spark just remembers the lineage of operations.

⇒10.2 Actions

Operations like `count()`, `collect()`, or `save()` that return a value to the driver program or write data to storage. When an Action is called, Spark optimizes the execution plan and finally runs all the deferred Transformations.

• MapReduce Model: Map phase applies logic to independent records; Shuffle phase groups by key; Reduce phase aggregates the groups.
• Optimization: Combiners reduce network bandwidth during the shuffle phase.
• Fault Tolerance: Managed automatically via task rescheduling and speculative execution.
• Apache Spark: The modern evolution of distributed processing. Uses RDDs and lazy evaluation to perform in-memory computations significantly faster than disk-bound MapReduce.