Reduce
, которые пишутся пользователем для обработки пар элементов данных «ключ/значение». Входные данные хранятся в наборе разделов в распределенной файловой системе, развернутой в каждом узле кластера. Затем программа вводится в инфраструктуру распределенной обработки и выполняется так, как описывается ниже.
Функция Map читает некоторый набор «записей» из входного файла, производит любые требуемые фильтрации и/или трансформации и выводит некоторый набор промежуточных записей в форме новых пар «ключ/значение». По мере того как функция Map производит эти выходные записи, функция «расщепления» (split) разделяет их на R непересекающихся бакетов, применяя некоторую функцию к значению ключа каждой записи. Эта функция расщепления обычно является хэш-функцией, хотя можно использовать любую детерминированную функцию. Каждый сформированный бакет записывается на локальный диск обрабатывающего узла. Функция Map завершается, произведя R выходных файлов, по одному на каждый бакет.
В общем случае имеется несколько экземпляров функции Map, выполняющихся в разных узлах вычислительного кластера. Термин экземпляр (instance) здесь означает индивидуальный выполняемый вызов либо функции Map, либо функции Reduce. Каждому экземпляру Map планировщиком MR назначается для обработки отдельная часть входного файла. Если имеется M таких отдельных частей, то каждая из M задач Map образует R файлов в дисковой памяти, т.е. всего образуется M × R файлов Fij, 1 ≤ i ≤ M, 1 ≤ j ≤ R. Ключевое наблюдение состоит в том, что во всех экземплярах Map используется одна и та же хэш-функция. Поэтому все эти экземпляры сохранят все выходные записи с одним и тем же значение хэш-функции в результирующем файле с одним и тем же номером.
На второй фазе MR-программа выполняет R экземпляров функции Reduce, где R обычно – это число узлов. Входные данные каждого экземпляра Reduce Rj состоят из файлов Fij, 1 ≤ i ≤ M. Эти файлы передаются по сети с локальных дисков узлов Map. Снова заметим, что все выходные записи фазы Map с одним и тем же значением хэш-функции попадают в один и тот же экземпляр Reduce независимо от того, какой экземпляр Map произвел эти данные. Каждый экземпляр Reduce обрабатывает или комбинирует назначенные ему записи и затем пишет записи в выходной файл (в распределенной файловой системе), образующий часть окончательного вывода данного вычисления.
Входные данные существуют в распределенной файловой системе в виде набора из одного или большего числа разделов. MR-планировщик решает, сколько нужно запустить экземпляров Map, и как распределить их по доступным узлам. Аналогично, планировщик должен принять решение о числе и распределении по узлам экземпляров Reduce. Центральный контроллер MR отвечает за координацию системных действий в каждом узле. MR-программа завершает выполнение, как только окончательный результат записывается в виде новых файлов в распределенной файловой системе.
