MapReduce Algorithm Design Adapted from Jimmy Lin’s slides MapReduce: Recap Programmers must specify: map (k, v) → <k’, v’>* reduce (k’, v’) → <k’, v’>* All values with the same key are reduced together Optionally, also: partition (k’, number of partitions) → partition for k’ Often a simple hash of the key, e.g., hash(k’) mod n Divides up key space for parallel reduce operations combine (k’, v’) → <k’, v’>* Mini-reducers that run in memory after the map phase Used as an optimization to reduce network traffic The execution framework handles everything else… “Everything Else” The execution framework handles everything else… Scheduling: assigns workers to map and reduce tasks “Data distribution”: moves processes to data Synchronization: gathers, sorts, and shuffles intermediate data Errors and faults: detects worker failures and restarts Limited control over data and execution flow All algorithms must expressed in m, r, c, p You don’t know: Where mappers and reducers run When a mapper or reducer begins or finishes Which input a particular mapper is processing Which intermediate key a particular reducer is processing k1 v1 k2 v2 map a 1 k4 v4 map b 2 c 3 combine a 1 k3 v3 c 6 a 5 map c 2 b 7 combine c 9 partition k6 v6 map combine b 2 k5 v5 a 5 partition combine c 2 b 7 partition 1 5 b 2 7 c 8 partition Shuffle and Sort: aggregate values by keys a c 8 c 2 9 8 reduce reduce reduce r1 s1 r2 s2 r3 s3 Tools for Synchronization Cleverly-constructed data structures Bring partial results together Sort order of intermediate keys Control order in which reducers process keys Partitioner Control which reducer processes which keys Preserving state in mappers and reducers Capture dependencies across multiple keys and values Preserving State Mapper object Reducer object one object per task state configure map state API initialization hook one call per input ke