Question

A Hadoop job consists of the input file(s) on HDFS, \(m\) map tasks and \(n\) reduce tasks, and the output is \(n\) files. The stages of one map-reduce iteration are:

• mapper (written by programmer)
• combiner (written by programmer)
• sort and shuffle (done by Hdaoop framework)
• reduce (written by programmer)

At each such iteration, there is input read in from HDFS and given to the mapper, and output written out to HDFS by the reducer. Optimizing the MapReduce pipeline often consists of minimizing the I/O tranfers.

Illustrating ideas behind MapReduce with a toy example of counting the number of each character in a string

Input

s = 'aabaabcdeda'

Map to create a key-value pair

xs = map(lambda x: [x, 1], s)
xs

[['a', 1],
 ['a', 1],
 ['b', 1],
 ['a', 1],
 ['a', 1],
 ['b', 1],
 ['c', 1],
 ['d', 1],
 ['e', 1],
 ['d', 1],
 ['a', 1]]

Sort and shuffle (aggregate and transfer data)

xs = sorted(xs)
ys = []
seen = []
for x in xs:
    if x[0] not in seen:
        seen.append(x[0])
        ys.append([x[0], [x[1]]])
    else:
        ys[-1][1].append(x[1])
ys

[['a', [1, 1, 1, 1, 1]], ['b', [1, 1]], ['c', [1]], ['d', [1, 1]], ['e', [1]]]

Reduce

for y in ys:
    print y[0], reduce(add, y[1])

a 5
b 2
c 1
d 2
e 1