MapReduce

MapReduce — модель пакетной обработки, где независимые map-задачи создают пары (key, value), система группирует значения по ключу, а reduce агрегирует каждую группу.

flowchart LR
    I["Входные блоки"] --> M["Map"]
    M --> S["Shuffle + sort/group by key"]
    S --> R["Reduce"]
    R --> O["Результат"]

Word count

Input:
"java notes"
"java code"
 
Map:
(java, 1), (notes, 1), (java, 1), (code, 1)
 
Shuffle:
java -> [1, 1]
notes -> [1]
code -> [1]
 
Reduce:
(java, 2), (notes, 1), (code, 1)

Map должен обрабатывать partition независимо. Shuffle — дорогой сетевой этап: сериализация, передача, сортировка и группировка. Reduce для одного ключа видит все его значения.

Свойства

• framework повторяет упавшие задачи, поэтому side effects mapper/reducer должны быть идемпотентными или отсутствовать;
• skewed key способен отправить огромную группу одному reducer и создать straggler;
• combiner может локально сократить данные, только если операция допускает частичную агрегацию;
• число output records и объем shuffle часто важнее CPU map-функции.

Java Stream map(...).reduce(...) использует похожие функциональные идеи, но не является автоматически распределенным MapReduce: там нет обязательного shuffle, fault tolerance и данных на кластере.

На собеседовании

• Что находится между map и reduce? Shuffle/grouping по ключу.
• Почему reduce должен быть ассоциативным для параллельного объединения? Порядок группировки частей не фиксирован.
• Что такое data skew? Несколько ключей получают непропорционально много данных.
• Stream API равен MapReduce? Нет, это локальная модель вычисления без распределенной инфраструктуры.