Как точно работает разбиение на MapReduce?

Я думаю, что я хорошо разбираюсь в модели программирования MapReduce в целом, но даже после прочтения оригинальной статьи и некоторых других источников для меня неясны многие детали, особенно в отношении разделения промежуточных результатов.

Я быстро подытожу свое понимание MapReduce до сих пор: у нас есть потенциально очень большой набор входных данных, который автоматически разбивается на M разных частей с помощью MR-Framework. Для каждой части фреймворк планирует одну задачу карты, которая выполняется одним из доступных процессоров/машин в моем кластере. Каждая из задач M-карты выводит набор пар ключей-значений, которые хранятся локально на той же машине, которая выполняла эту задачу карты. Каждая машина делит свой диск на разделы R и распределяет пары вычисленных промежуточных ключей на основе промежуточных ключей между разделами. Затем среда начинается для каждого отдельного промежуточного ключа, который уменьшает задачу, которая снова выполняется любой из доступных машин.

Теперь мои вопросы:

В некоторых учебных пособиях звучит так, будто может быть карта и уменьшить задачи, выполняемые параллельно. Это правильно? Как это могло быть, если предположить, что для каждого отдельного промежуточного ключа запускается только одна задача сокращения? Не нужно ли ждать завершения последней задачи карты, прежде чем мы сможем начать первую задачу сокращения?
Поскольку у нас есть одна задача сокращения на отдельный промежуточный ключ, правильно ли, что каждая задача сокращения требует, чтобы исполняющая машина загружала соответствующий раздел из любой другой машины? Потенциально, каждая машина может иметь пару "ключ-значение" с требуемым промежуточным ключом, поэтому для каждой задачи сокращения мы потенциально должны запрашивать все остальные машины. Это действительно эффективно?
В оригинальной статье указано, что количество разделов (R) указано пользователем. Но не является ли раздел для задачи сокращения? Или, точнее: не является ли объединение всех разделов с одинаковым числом среди всех машин вводом одной задачи сокращения? Это будет означать, что R зависит от количества отдельных промежуточных ключей, которые пользователь обычно не знает.

Концептуально ясно, какие входные и выходные данные карты и уменьшить функции/задачи. Но я думаю, что я еще не понял MapReduce на техническом уровне. Может кто-нибудь, пожалуйста, помогите мне понять?

Ответ 1

Вы можете запускать задачи редуктора, пока задачи карты все еще работают (с использованием функции, известной как slowstart), но редукторы могут выполнять только фазу копирования (получение завершенных результатов из завершенных задач карты. для того, чтобы все мапперы заполнили, прежде чем он сможет фактически выполнить окончательный сортировку и уменьшить.
Задача уменьшения фактически обрабатывает нуль, один или несколько ключей (а не отдельные задачи для каждого ключа). Каждый редуктор должен будет получить вывод карты из каждой задачи карты, относящейся к ее разделу, до того, как эти промежуточные выходы будут отсортированы, а затем будет уменьшено на один набор ключей за раз.
Назад к примечанию в 2 - задача редуктора (по одному для каждого раздела) работает на ноль, один или несколько ключей, а не одна задача для каждого дискретного ключа.

Также важно понять разброс и изменение вашего промежуточного ключа, поскольку он хэшируется и modulo'd (если используется HashPartitioner по умолчанию), чтобы определить, какой из уменьшенных разделов должен обрабатывать этот ключ. Скажем, у вас было четное количество заданий редуктора (10) и выходных ключей, которые всегда хэшировали до четного числа - тогда в этом случае по модулю этих чисел хэш и 10 всегда будет четное число, что означает, что нечетные нумерованные редукторы никогда не обрабатывать какие-либо данные.

Ответ 2

Добавление к тому, что сказал Крис,

В принципе, класс разделителя в Hadoop (например, по умолчанию HashPartitioner)

должен реализовать эту функцию,

int getPartition(K key, V value, int numReduceTasks)

Эта функция отвечает за возврат вам номера раздела, и вы получаете количество восстановителей, которое вы исправили при запуске задания из переменной numReduceTasks, как показано в HashPartitioner.

На основании того, какое целое число возвращает функция, Hadoop выбирает node, где должна выполняться задача сокращения для определенного ключа.

Надеюсь, что это поможет.