Title

MapReduce: Simplified Data Processing on Large Clusters

What

Programming model designed for efficiently processing and generating large datasets.
Defines two functions:
- Map: Processes key/value pairs to generate a set of intermediate key/value pairs.
- Reduce: Merges all intermediate values associated with the same intermediate key.
Example tasks: simple counting and filtering operations to more complex data transformations and statistical analyses.

Prior to MapReduce, computations involving large datasets required dealing with the parallelization, data distribution, and failure handling.
MapReduce abstracts these complexities.

Automatically parallelizes the execution of the map and reduce functions across a large cluster of commodity hardware.
The runtime system handles the partitioning of input data, scheduling of tasks across the machines, managing machine failures, and facilitating the necessary inter-machine communication. This process involves several key steps:

Input Splitting: The input data is divided into manageable chunks, which are then processed independently by different machines.
Mapping: The map function is applied to each input chunk, producing intermediate key/value pairs.
Shuffling: Intermediate pairs are distributed across machines such that all values associated with the same key are brought together.
Reducing: The reduce function is applied to each group of values associated with the same key, merging them into a smaller set of values or a single value.
Output: The results of the reduce function are collected and stored, forming the output of the MapReduce job.

Leader pings each worker periodically. If a specific worker fails to respond within a "pre-decided" time stipulation, this worker is marked as non-responsive and failed.
All map tasks completed by this worker node are set to "Idle state".
- They can be picked up by a different worker node.
All map tasks marked "In Progress" are reset to "Idle state" and eligible for re-scheduling.
Both, Completed and In Progress jobs are handled in the same way, since the output is stored in a local disk and there is no way to fetch this data from the failed node.

Periodic checkpoints of the leader's state is performed.
- Upon failure, the previously checkpointed state can be instantly recovered.
Paper mentions in case of a "Leader failure", the entire MapReduce operation will have to be performed again from scratch.

Within a given partition, the intermediate key value pairs are processed in increasing key order.

Straggler tasks can slow down the entire MapReduce operation, and can be alleviated by running "backup tasks".
Whenever a MapReduce operation is nearing completion, the master schedules backup execution of all "in-progress" tasks.
- This ensures multiple worker nodes are executing the same operation, removing a "single point of failure".

The leader node also instantiates and runs an HTTP server where the following information can be monitored:
- Progress of the computation
- Links to the standard error and output files generated by each worker node.
- Details on the nodes that have failed, along with the "map" and "reduce" tasks they were processing.

Map Function: A user-defined function that processes input key/value pairs to generate a set of intermediate key/value pairs.
Reduce Function: A user-defined function that merges all intermediate values associated with the same intermediate key.
Fault Tolerance: The ability of a system to continue operating without interruption when one or more of its components fail.
Straggler: A machine that takes an unusually long time to complete one of the few "Map" or "Reduce" tasks in the computation.