MapReduce Model

¢Programmersspecify two functions:

map (k, v) → <k’, v’>*

reduce (k’, v’) → <k’, v’>*

All values with thesame key are sent to the same reducer

¢The execution framework handles everything else…

What’s“everything else”?

MapReduce “Runtime”

¢Handlesscheduling

Assigns workers tomap and reduce tasks

¢Handles“data distribution”

Moves processes todata

¢Handlessynchronization

Gathers, sorts, andshuffles intermediate data

¢Handleserrors and faults

Detects workerfailures and restarts

¢Everythinghappens on top of a distributed FS (later)

Programmersspecify two functions:

map (k, v) → <k’, v’>*

reduce (k’, v’) → <k’, v’>*

All values with thesame key are reduced together

¢The execution framework handles everything else…

¢Not quite…usually, programmers also specify:

partition (k’, number of partitions) →partition for k’

Often a simple hashof the key, e.g., hash(k’) mod n

Divides up keyspace for parallel reduce operations

combine (k’, v’) → <k’, v’>*

Mini-reducers thatrun in memory after the map phase

Used as anoptimization to reduce network traffic