Как работает MapReduce и происходит распределение данных на воркеры и объединение результатов

Что проверяют

Понимаете ли вы, где в распределённой обработке рождается основная цена: в перетасовке данных между машинами. Классический MapReduce сегодня нужен как фундамент для Spark, поэтому следом часто спрашивают, где shuffle в Spark и чем reduceByKey лучше groupByKey.

Как отвечать

Разберите путь данных по шагам на примере подсчёта слов:

• разбиение входа: файл в HDFS хранится блоками (по умолчанию 128 МБ), вход режется на input splits, обычно по блоку на split. На каждый split запускается map-задача, и YARN старается поставить её на узел, где блок уже лежит. Это data locality: код едет к данным, а не наоборот;
• map: функция вызывается на каждую запись и выдаёт пары ключ-значение, для подсчёта слов (слово, 1);
• партиционирование: каждая пара получает номер редьюсера, по умолчанию хэш ключа по модулю R, где R задаёт пользователь. Так все значения одного ключа гарантированно попадут в одно место;
• combiner: необязательная локальная свёртка на стороне map, сокращает объём передачи;
• shuffle и sort: вывод map сортируется и сбрасывается на локальный диск узла, а не в HDFS. Редьюсеры сами забирают свои партиции со всех map-узлов по сети и сливают их сортировкой слиянием;
• reduce: на вход приходит ключ и все его значения, результат пишется в HDFS, по файлу part-r-NNNNN на каждый редьюсер.

Упавшая задача перезапускается на другом узле, это безопасно, потому что вход неизменяем. Для отстающих задач есть speculative execution: дубль запускается параллельно, и берётся результат того, кто закончил первым.

Где спотыкаются

Говорят, что в конце воркеры отправляют результаты главному узлу и он всё агрегирует. ResourceManager и ApplicationMaster только планируют задачи, данные через них не идут.

Забывают про перекос ключей. Если один ключ встречается в половине записей, один редьюсер работает за всех, и задача висит на последних процентах.

Не могут объяснить, почему groupByKey в Spark тяжелее reduceByKey: первый гонит по сети все значения, второй сначала сворачивает их на месте, как combiner.