call(back)
Algorithms & Data StructuresmediumSign in to star problems

Implement MapReduce

Implement MapReduce as a single-machine model of the real thing, with the parts named explicitly:

mapReduce(records, mapper, reducer, combiner, partition, numReducers, chunkSize)
  ->  { results: { key: reducedValue }, reducers: [[keys of reducer 0, sorted], [reducer 1], ...] }
  • Map tasks: records are processed in chunks of chunkSize records; each chunk is one map task. mapper(record) returns a list of [key, value] pairs.
  • Combiner: when combiner is given, run it once per chunk — group that chunk's pairs by key and replace them with [key, combiner(key, values)] — before anything is shuffled. When it is null, pairs are shuffled as emitted.
  • Partitioner: every pair goes to reducer partition(key) % numReducers.
  • Sort within each partition: each reducer handles its keys in ascending order, and reducers[i] reports them in that order.
  • Reduce: reducer(key, values) produces results[key].
records ["a b a", "b c", "a"], word-count job, numReducers 2, chunkSize 2, with a combiner:
  chunk 1 emits a:1 b:1 a:1 b:1 c:1  ->  combined a:2 b:2 c:1
  chunk 2 emits a:1
  reducer for "a" sees [2, 1]  ->  results { a: 3, b: 2, c: 1 }

The harness supplies jobs (word count, max word length by first letter, mean by group) and a partitioner, wraps your reducer to record how many values it received per key, and reports { results, reducers, reducerInputs }.

Hints

Hint 1

Keep one map-of-lists per reducer. For each chunk: run the mapper over its records, optionally fold the chunk's pairs through the combiner grouped by key, then append each value to partitions[partition(key) % numReducers][key].

Hint 2

Finish by walking each partition's keys in sorted order and calling the reducer once per key. The combiner changes how many values the reducer sees, not the answer — which is exactly why it is only legal for reducers like sum and max.

Asked at

Apple