MapReduce и Spark: параллелизм на кластере

Урок про то, как примитивы map и reduce масштабируются до кластеров и петабайтов данных.

MapReduce — модель распределённой обработки: фаза map применяет функцию к каждому куску данных параллельно, фаза reduce сворачивает результаты по ключам. Spark — её более быстрый наследник с вычислениями в памяти.

От примитивов к кластеру

В разделе 4 мы видели map и reduce на массиве. MapReduce берёт ту же идею и растягивает на тысячи машин, обрабатывающих данные, которые не влезают на один диск. Фреймворк сам разбивает данные, рассылает задачи, переживает падения узлов и собирает результат. Программист пишет лишь две функции — map и reduce — а вся распределённая машинерия скрыта.

Три фазы

Map: каждый узел применяет функцию к своему куску данных, выдавая пары (ключ, значение). Shuffle: фреймворк группирует все значения с одинаковым ключом и свозит их на один узел (это дорогой сетевой этап). Reduce: для каждого ключа сворачивает его значения в результат. Классический пример — подсчёт слов: map выдаёт (слово, 1) для каждого слова, shuffle собирает одинаковые слова вместе, reduce складывает единицы.

# эмуляция MapReduce: подсчёт слов
from collections import defaultdict

docs = ["кот пёс кот", "пёс пёс кот", "рыба кот"]

# MAP: (слово, 1) для каждого слова
pairs = []
for d in docs:
    for word in d.split():
        pairs.append((word, 1))

# SHUFFLE: группируем по ключу
groups = defaultdict(list)
for k, v in pairs:
    groups[k].append(v)

# REDUCE: сумма значений по ключу
result = {k: sum(v) for k, v in groups.items()}
for word in sorted(result):
    print(word, result[word])

Вывод:

кот 4
пёс 3
рыба 1

На кластере фазы map шли бы параллельно на разных узлах над разными документами, shuffle пересылал бы пары по сети, а reduce складывал бы значения каждого ключа — но логика ровно эта.

Почему Spark быстрее

Классический Hadoop MapReduce между этапами пишет промежуточные данные на диск — это надёжно, но медленно. Spark держит данные в оперативной памяти и строит граф вычислений (DAG) из преобразований, выполняя их лениво. Для итеративных алгоритмов (машинное обучение, графы), где данные проходят много раундов, Spark в разы быстрее, потому что не сбрасывает всё на диск между итерациями. Абстракция Spark — RDD/DataFrame: распределённая коллекция, над которой делают map, filter, reduceByKey, join.

Связь с примитивами

MapReduce и Spark — это масштабирование тех же map и reduce, что мы изучили на массиве, до распределённой памяти. Reduce по ключу — это группировка плюс редукция. Shuffle — это all-to-all коммуникация (как в sample sort и MPI). То есть вся теория параллельных примитивов и стоимости коммуникации применима один в один, просто масштаб другой: не ядра, а узлы; не кэш, а сеть.

Как работает под капотом

Фреймворк хранит данные распределённо (HDFS, S3), бьёт их на блоки и старается запустить map-задачу на том узле, где лежит её блок (locality — счёт идёт к данным, а не наоборот, экономя сеть). Если узел упал, его задачу перезапускают на другом — отказоустойчивость встроена. Shuffle — самая дорогая фаза, потому что данные физически перемещаются по сети между всеми узлами; оптимизация shuffle (комбинирование, сжатие) — главный рычаг производительности.

Революция MapReduce была не в алгоритме — map и reduce известны десятилетиями, — а в том, что фреймворк взял на себя всю распределённую боль. Раньше, чтобы посчитать что-то на сотне машин, инженер вручную писал рассылку данных, обработку падений узлов, повторные попытки, сбор результатов — месяцы работы, полные тонких ошибок. MapReduce свёл это к двум функциям, отдав остальное движку. Это classический приём: спрятать сложную, повторяющуюся машинерию за простой моделью, чтобы прикладной программист думал о задаче, а не об инфраструктуре. Spark пошёл дальше, добавив выразительность (целый граф преобразований вместо жёсткой пары map-reduce) и скорость (память вместо диска), но идея осталась той же — освободить человека от ручного управления кластером.

Частые ошибки

• Недооценивать стоимость shuffle — он часто доминирует над map и reduce.
• Использовать Hadoop для итеративных задач — диск между итерациями убьёт скорость, нужен Spark.
• Писать reduce с неассоциативной операцией — распределённое сворачивание даст неверный результат.

Итоги

• MapReduce масштабирует map и reduce на кластер: map → shuffle → reduce.
• Shuffle (группировка по ключу, all-to-all обмен) — самая дорогая, сетевая фаза.
• Spark держит данные в памяти и строит DAG — кратно быстрее на итеративных задачах.
• Это те же параллельные примитивы, но в масштабе узлов и сети, а не ядер и кэша.