MapReduce - Week 7

Question 1

Batch Processing

Answer 1

jobs that can run without end user interaction, or can be scheduled to run as resources permit

Question 2

Examples of batch processing for data sets that build over time

Answer 2

Web crawling
Transaction logs, for analysing trends
Equipment logs, for predicting faults

Huge data sets that may need to be processed on parallel architectures

Question 3

Who originally developed map reduce

Answer 3

Google

Question 4

What two functions make up map reduce?

Answer 4

map and reduce

Question 5

MapReduce - map function definition

Answer 5

map(key1, value1) -> [(key2, value2)]

Given a key and a value, generates a collection of key value pairs

Question 6

MapReduce - reduce function definition

Answer 6

reduce(key2, [value2]) -> [(key3,value3)]

given a key key2 output by map, and a collection of all the values value2 associated with that key, return a new collection of key-value pairs

Question 7

Word count with map reduce - what do the two functions do?

Answer 7

Map takes a document, and returns a set of word counts for that document.
e.g.
“the map operation given…” -> {“the”: 1, “map”:1, …}

Reduce takes outputs from map and collates them into one thing
{“the”: [1,1], “map”:[1,1} -> {“the”: 2, “map”: 2}

Question 8

MapReduce provider, extensions and competitors

Answer 8

Hadoop, …

Extensions: Cloudera

Competitors: Apache Spark

Question 9

AWS EC2

Answer 9

Purchase of virtual machines of different capabilities, with different operating systems and for different periods

IaaS

Question 10

AWS S3

Answer 10

Purchase of storage that is accessed through a simple file system style interface

IaaS

Question 11

EMR (Elastic Map Reduce)

Answer 11

The ability to run scalable applications written using the map reduce programming model over EC2 and S3 infrastructure

PaaS

Question 12

How is S3 used for AWS MapReduce?

Answer 12

The input to the map/reduce problem

The Jar that contains the program

The output from the execution of the program

Logging information

Question 13

Use Map reduce or RDB for single batch tasks?

Answer 13

MapReduce, perhaps the effort of loading the data into a relational database isn’t worth it

Question 14

Use Map Reduce or RDB for data using online transactional processing and analytical tasks?

Answer 14

Map reduce won’t help with the OLTP tasks.

A relational database is more flexible and may be able to handle both, though often different systems are used for OLTP and analytics to avoid contention for resources.

Question 15

Use Map Reduce or RDB for data that needs fine-grained access control

Answer 15

MapReduce itself doesn’t provide much in the way of security - the hosting environment does that.

Certain relational databases will provide fine-grained access control

Question 16

MapReduce - what is a job?

Answer 16

The unit of work to be performed (the data and the program)

Can consist of several map and reduce tasks

Question 17

MapReduce - what is a split?

Answer 17

A part of the input (e.g. a 64mb filesystem block)

Question 18

MapReduce - what is a task?

Answer 18

Map or reduce functions created and run for each split/partition

Question 19

MapReduce - what is a task tracker?

Answer 19

Tracks the progress of each of the map or reduce tasks on a node

Keeps the job tracker informed of progress

Question 20

MapReduce - what is a job tracker?

Answer 20

Coordinates the different tasks comprising a job

Question 21

MapReduce - How many map tasks are created?

Answer 21

One for each split (each part of the input, e.g. a 64mb filesystem block)

Question 22

MapReduce - What are the steps of the map function?

Answer 22

1. The map task runs on the split, creating key-value pairs
2. The output of the map is partitioned into groups, for sending to reduce functions, typically by hashing.
3. The partitions are sorted by key
4. The outputs are written to the local file system
5. The task manager notifies the job manager that the task is completed

Question 23

MapReduce - What are the steps of the reduce function?

Answer 23

1. Relevant map partitions are copied to the associated reduce nodes
2. Data from different maps is merged to produce the inputs for individual reduce operations
3. The reduce task is run
4. Outputs are written to the distributed filesystem

Question 24

What are the MapReduce performance issues to look out for?

Answer 24

Memory usage - The space required by the code within map and reduce

Skew - The likelihood that data is not distributed evenly across reduce nodes

Intermediate result size - The amount of data that is produced by map or reduce compared to the size of their inputs

Question 25

Write the Basket analysis average problem as MapReduce pseudocode

Answer 25

A list of the prices of the baskets a user has purchased, e.g.

001 - £26
002 - £30
001 - £40
002 - £35

A simple analysis involves getting the average a user has spent

Map receives a key (identifying the location of an input split) and a value (a section of memory, a list of the users and values)
It emits those user and value pairs

The reduce function gets a customer id and a list of basket values for that customer from the map function, it emits the average of these values with the key of the customer id it received

Question 26

MapReduce - summarisation patterns

Answer 26

Summarization aims to send as little information to reducers as possible, e.g.
“hello hello hello” -> {“hello”, 3}

instead of
“hello hello hello” -> {“hello” 1, “hello” 1, “hello” 1}

To do this numerically the operation must be both:
associative - (axb)xc = ax(bxc)
commutative - axb = bxa

Question 27

MapReduce - combiners

Answer 27

An optional reducer that is local to a map, and that summarises its results in some way

Must have inputs and outputs that are semantically compatible with the output of a map

In word count, the normal reducer can be used as a combiner, in this case it has the same effect as summarisation

Question 28

MapReduce - inverted index pattern

Answer 28

supports the construction of an index from the contents of a document to the document

Map returns emits a key for each token, and a value of the document identifier

Reduce is application specific, might compute tf-idf or write to an index structure

Question 29

MapReduce - Filtering pattern

Answer 29

Discard some of the information in the input

Sampling - producing representative examples

Top-k - choosing the best examples

Distinct - removing duplicates

For word count - may only be interested in counting occurrences of dictionary words

Question 30

MapReduce - Join Pattern

Answer 30

Implements a relational join

In Hadoop a job can be associated with two mappers that read from different inputs; then the infrastructure does most of the join

Need to label tuples with their table table, so we can distinguish them in the reduce.

For full explanation see “Join Pattern” slide in the “Map Reduce Programming - Week 7” notes