MapReduce: Processing Big Data

• Map Reduce is a programming model for processing big data

Development and Design

• Developed by Dean and Ghemawat at Google in 2004
• Designed to efficiently process large volumes of data
• Uses commodity computers working in parallel
• Divides workload into multiple independent tasks
• Schedules tasks across cluster nodes
• Works in isolation

Handling features

• Parallelization
• Data distribution
• Load balancing
• Fault tolerance

Map stage function

• Input shard transforms in intermediate key or value pairs
• Input data is automatically partitioned into M shards
• Discards unnecessary data and generates (key, value) sets
• Framework groups intermediate values with the same intermediate key and passes them to the Reduce function

Reduce stage function

• Intermediate key or value pairs convert to result files
• Input comprises a key and set of values.
• Merges the values to form a smaller set of values.
• Reduce workers are distributed by partitioning the intermediate key space, using R pieces via a partitioning function

Step 1: Split Input Files

• Input data divides into M pieces
• Results in M workers; each worker processes one shard
• Two files results in 2 workers; each worker will have to process 2 shards only

Step 2: Fork Processes

• Multiple copies of the program start on a cluster of machines
• One master acts as scheduler and coordinator
• Many workers map or reduce workers
• Idle workers assigned map tasks, each shard has M map tasks
• Reduces tasks of intermediate files where there are R partitions, defined by user

Step 3: Run Map tasks

• Reads content of the assigned input shard.
• Parses key or value pairs from the input data.
• Passes each pair to a user-defined map function to produce intermediate key or value pairs - buffered in memory

Step 4: Partitioning

• It occurs after intermediate key/value pairs are produced
• The user map function stores buffered memory, periodically written to the local disk
• The map worker partitions the data by keys
• Partition into R -number of reduces- regions by using a partitioning function
• Map data is processed by reduce workers
• User reduce functions are called once for each unique key generated

Step 5: Reduce Task

• Reduce worker is notified by the master of the location of intermediate files for partitioning
• Shuffles RPCs to read data from local disks from the Map worker
• Arranges data by intermediate key
• Gathers occurrences of the same key

Step 6: Reduce Task

• The sort phase groups data with a unique intermediate key
• User's Reduce function receives the key and set of intermediate values
• The Reduce function output appends to an output file

Step 7: Return to User

• When all map and reduce tasks finish, the master wakes up the user
• The MapReduce call in the user program returns and allows the program to resume execution
• The output of MapReduce is available in R output files

Map and Reduce Worker definitions

• Map worker parses data into key value, then writes to an intermediate file
• Shuffle and sort fetches relevant partitions of output from mappers: Sorts by keys
• Reduce inputs sorted outputs of mappers. The program calls a reduce function for each key with values to aggregate the results

Example function

• Maps counts occurrences of each count in the collection of documents, parses and outputs data for each with a count of one
• Reduce will sort by keys or words, and sum counts of each word

Fault Tolerance in Map Reduce

• To achieve fault tolerance map reduces periodically pings each worker
• If no response occurs in a set time, the worker is marked as failed
• Assigned map and reduce tasks will reset, and be rescheduled to other works
• Map tasks are re-executed
• All workers will be notified if any re-execution occurs