Map/reduce

Question 1

what is Map/Reduce?

Answer 1

a programming framework for which any solution must be expressed using map & reduce functions

Question 2

what is the function of the map function?

Answer 2

to emit intermediate key/value pairs when called on an input item

Question 3

what is the function of the reduce function?

Answer 3

to emit results for a key when called on groups of pairs with the same key

Question 4

what are the benefits of MapReduce? (3)

Answer 4

1. provides a high-level parallel programming abstraction
2. the framework implementations provide good performance results
3. greatly reduces parallel programming complexity

Question 5

where are the opportunities for parallelism when using MapReduce? (2)

Answer 5

1. input data can be partitioned into chunks, each of which can be assigned to a different mapper
2. the map stage produces collections of key/value pairs, that are grouped by key. Each distinct key-group can be sent to a different reducer

Question 6

what does the reduce function receive?

Answer 6

a key/value pair (intermediate keys), where the new value is a list of all the input values from the grouped key/value pairs with the same key

Question 7

when will reduce jobs run?

Answer 7

only once all map jobs are completed and the synchronisation step occurs

Question 8

what occurs during the synchronisation step? (6)

Answer 8

1. Every key-value item generated by the mappers is collected
2. Items are transferred over the network
3. Same key items are grouped into a list of value
4. Data is partitioned among the number of Reducers
5. Data is copied over the network to each Reducer
6. The data provided to each Reducer is sorted according to the keys

Question 9

how does the framework partition key value pairs to the reducers?

Answer 9

randomly, based on the number of distinct keys generated

Question 10

why is it not possible to always achieve load balancing between reducers?

Answer 10

some distinct keys may appear more times than others so the reducer that the distinct key is assigned to will have more values to work with

Question 11

what are the two bottlenecks associated with the map/reduce framework?

Answer 11

the synchronisation step & the network (communication speed)

Question 12

where are key/value pairs produced by the map function stored?

Answer 12

in memory when up to 100MB, then remaining key/value pairs are stored on hard disk

Question 13

what is partitioning?

Answer 13

the process of dividing the all the intermediate key/value pairs produced by the map functions into groups or partitions based on the keys (each partition is typically associated with a range of keys)

Question 14

what is the number of partitions equal to?

Answer 14

the total number of reducers/reduce jobs

Question 15

what is the purpose of the combiner?

Answer 15

to improve efficiency by reducing the communication volume, acting as a preliminary reducer to perform a local aggregation of the output from the mappers

Question 16

when does partitioning occur?

Answer 16

after mapping and before shuffle & sort

Question 17

what is shuffle & sort?

Answer 17

the process of transferring the relevant partitions to the appropriate nodes, and it sorting the data based on keys

Question 18

when does shuffle & sort occur?

Answer 18

after partitioning and before reducing

Question 19

is the combiner mandatory?

Answer 19

no

Question 20

give some examples of map/reduce implementations (4)

Answer 20

1. top-k
2. inverted index
3. filtering
4. numerical sumarisation

Question 21

why can top-k only run with one reducer?

Answer 21

because all key/value pairs need to be sent to a single reducer for sorting

Question 22

what is the minimum requirement for top-k?

Answer 22

the ranking data for a whole input split must fit into memory of a single reducer

Question 23

is calculating an average using map/reduce an associative operation?

Answer 23

no