MapReduce

Distributed computing with MapReduce.

MapReduce

MapReduce is a programming model for processing large data on distributed clusters. It has three stages: map, shuffle and reduce.

The map stage transforms each input piece into (key, value) pairs. The shuffle stage groups pairs with the same key to the same worker. The reduce stage aggregates each group.

This model is widely used for word count, inverted index and log analysis tasks.

Shuffle and reduce

The shuffle stage groups all (key, value) pairs from the map output by key. All values with the same key are sent to the same reduce worker.

The reduce stage aggregates each group; for example, in word count it sums the values. This separation enables parallel execution in a distributed setting.

Page ranking, inverted index and statistical computation fit this structure easily.

Exercise mapreduce_count function

Write mapreduce_count(documents). Map each document's words to (word, 1) pairs and count them. Return a sorted list of (word, count) pairs. Print [('armut', 1), ('elma', 3), ('muz', 1)] with print(mapreduce_count(['elma elma armut', 'elma muz'])).

Show example solution

def mapreduce_count(documents):
    # Word count with MapReduce
    mapped = []
    for doc in documents:
        for word in doc.split():
            mapped.append((word, 1))
    counts = {}
    for word, one in mapped:
        counts[word] = counts.get(word, 0) + one
    return sorted(counts.items())
print(mapreduce_count(['elma elma armut', 'elma muz']))

Test yourself

map output

for word in doc.____():
    mapped.append((word, 1))

Show answer

for word in doc.split():
    mapped.append((word, 1))

MapReduce concepts

map

Produces (key, value)
shuffle

Groups same keys
reduce

Aggregates
big data

Distributed cluster
What does the reduce stage do?
```
for word, one in mapped:
    counts[word] = counts.get(word, 0) + one
```
- It sorts the data
- It splits the data
- It aggregates values with the same key
- It filters the data
Show answer

It aggregates values with the same key — Reduce aggregates values with the same key.

Next lesson: Summary - Game theory and parallel

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies