Q20Cloud Computing

MapReduce divides a processing task into two main phases, allowing a single logical computation to be executed in parallel across hundreds or thousands of machines in a cluster without the programmer having to write any explicit networking, synchronization, or scheduling code.

1. Map Phase

The input data is divided into independent chunks which are processed by the map tasks in a completely parallel manner. The framework sorts the outputs of the maps, which are then input to the reduce tasks. The Map function takes a set of data and converts it into another set of data, where individual elements are broken down into key/value pairs. Each mapper runs on the node where its input chunk is physically stored whenever possible (a principle called data locality), which avoids saturating the network by moving data to compute and instead moves the tiny map code to the data.

2. Shuffle and Sort Phase

Between the Map and Reduce phases, the framework performs an intermediate Shuffle and Sort step. All key/value pairs emitted by every mapper are partitioned by key (typically via a hash function) and transferred across the network so that all values for a given key end up at the same reducer. Within each partition, the pairs are sorted by key, which lets the reducer process each key's values as a contiguous group rather than scanning the whole dataset repeatedly.

3. Reduce Phase

The Reduce task takes the output from the Map task as input and combines those data tuples into a smaller set of tuples. A reducer receives all values associated with one key and applies an aggregation function (sum, count, average, etc.) to produce the final output, which is written back to the distributed file system.

Worked Example: Word Count

Consider input text: 'Hello World Hello'. - Map phase emits: (Hello, 1), (World, 1), (Hello, 1). - Shuffle & Sort aggregates by key: Hello -> [1, 1], World -> [1]. - Reduce phase sums values: (Hello, 2), (World, 1). If this input text were instead a 10 GB log file split across 100 blocks, the framework would launch roughly 100 map tasks (one per block) running concurrently on different nodes, each emitting local word counts, followed by a shuffle that groups identical words across all mappers' outputs, and a set of reducers that sum the counts in parallel to produce the final word-frequency table.

This paradigm abstracts away the complexities of distributed computing, such as network communication, synchronization, and fault tolerance. If a map or reduce task fails partway through, the master (JobTracker/ApplicationMaster) simply reschedules that task on another node using the replicated input data, without affecting tasks that have already completed. This combination of automatic parallelization, data locality, and transparent fault recovery is what allows MapReduce to process petabyte-scale datasets reliably on clusters of unreliable commodity hardware, making it the foundational programming model that popularized big-data processing before being extended by newer, faster in-memory engines like Apache Spark that reduce the disk I/O overhead between the map and reduce stages.