Distributed mining: MapReduce and Spark
How mining is computed across machines: map, shuffle, reduce, combiner and partitions, then Spark (lazy narrow or wide transformations, and actions) and the five mining tasks.
- 23 cards
- 5 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
- Scenarios
- Understand
A few cards from the deck
MapReduce: what is it?
Show the answer
A distributed computing model in three phases: turn each record into key-value pairs, group pairs by key, then summarise each group.
To count HTTP codes in a log, map emits (code, 1) for each line, the shuffle puts all the 404s together, reduce adds up the 1s.
Two blocks of a web log hold these codes: block 1 = 200, 404, 200; block 2 = 404, 404, 500. What is the total for key 404 after reduce?
- 3
- 2
- 6
- 1
Show the answer
3
Map emits one (code, 1) pair per line: one 404 in block 1, two in block 2. The shuffle gathers them and reduce adds 1 + 1 + 1 = 3. 6 is the total number of lines.
A … reduces pairs locally on each machine before the shuffle, which lowers the data exchanged over the network.
Show the answer
A combiner reduces pairs locally on each machine before the shuffle, which lowers the data exchanged over the network.
For a count, the machine sends (404, 5000) instead of 5000 pairs (404, 1). This only works if the operation is associative and commutative, like addition.
Shuffle phase: what is it?
Show the answer
The step that sends, across the network, all pairs with the same key to the same machine.
It is the costliest step: it moves data between machines. Hence the value of reducing locally first with a combiner.
A word count over 500 GB is slow because of the volume exchanged at the shuffle. Which change helps most?
- Add a combiner that adds pairs locally before the shuffle
- Replace the sum with an average in the reduce
- Increase the number of reduce tasks to spread the work
- Compress the input file with gzip before processing
Show the answer
Add a combiner that adds pairs locally before the shuffle
Without a combiner, every occurrence of a word produces a pair (word, 1) that crosses the network. With one, each machine sends one total per word. More reducers spread the same pairs without reducing their number, compressing the input lightens the read, not the exchange, and a mean cannot be combined as is.