4 - MapReduce

Question 1

MapReduce is what kind of model? Developed by who?

Answer 1

Simple data-parallel programming model for scalability and fault tolerance

Google

Question 2

How is MapReduce used by Google?

Answer 2

Index construction for Google Search
Article clustering for Google News
Statistical machine translation

Question 3

Functional Programming

Answer 3

Computation as application of functions

Question 4

How is functional programming different?

Answer 4

Traditional notions of data and instruction not applicable
Data flows are implicit in program
Different orders of execution possible

Question 5

Lisp

Answer 5

List Processing

Lists are primitives and functions written in prefix notation

Question 6

Concept: Map

Answer 6

Do something to everything on a list to make a new list from the results

Question 7

Concept: Fold

Answer 7

Combine or accumulate results in a list

Question 8

How does “fold” work?

Answer 8

Accumulator set to init value
Func applied to list elem and the accumulator
Result stored in the accumulator
Repeated for every item in the list
Result is the final value in accumulator

Question 9

Map example
(map (lambda(x) (*x x))
‘(1 2 3 4 5 ) -> ???

Answer 9

‘(1 4 9 16 25)

Question 10

Fold example

Ignore this card for now

Question 11

When can we reorder folding?

Answer 11

If the fold function is cumulative and associative (order is irrelevant)

Question 12

Is there a limit to map parallelisation?

Answer 12

No since maps are independent

Question 13

Apache Hadoop Architecture: Master

Answer 13

communicates with workers, tracks resources and orchestrates work

Question 14

Apache Hadoop: Worker

Answer 14

Launches and tracks processes spawned on worker host

Question 15

For a job to be parallelisable, its tasks need to be …

Answer 15

Independent

Question 16

What does it mean for a task to be independent?

Answer 16

Must not depend on the input or output of other tasks