9 / 17
лученных на этапе map, по reduce-заданиям: (
k
0
, reducers_count)
→
→
reducer
_
id
, где reducers_count — число узлов, на которых запус-
кается операция свeртки; reducer_id — идентификатор целевого узла
[(
k
0
, v
0
)]
→
(
k
0
,
[
v
0
])
.
Действие
: в простейшем случае, reducer_id = hash(
k
0
) mod reducers_co-
unt, где hash(
k
’) — хеш-фукнция от ключа
k
0
,
А
mod
B
— вычисление
остатка от деления
А
на
B.
Основная цель этапа partition — это балансировка нагрузки. Не-
корректно реализованная функция может привести к неравномерному
распределению данных между reduce-узлами.
Данная формула — это частный пример, в котором для распре-
деления данных по узлам свертки используется хеш-функция. Она
позволяет равномерно распределять нагрузку между узлами, которые
будут выполнять свертку. Если, например, вместо использования хеш-
функции поставить статическое значение, то все данные попадут на
один узел свертки. Таким образом, распределение данных будет не-
равномерным. Работать будет только один узел, остальные будут “про-
стаивать”. В некоторых случаях имеет смысл разработать свою функ-
цию распределения нагрузки. Например, для распределения данных
по месяцам. Если в качестве ключа
k
0
будет использоваться порядко-
вый номер месяца в году (1. . . 12), а число узлов для операции будет
выставлено на 12 (чтобы каждый узел обрабатывал свой месяц), то
чтобы выполнить свертку по каждому месяцу на одном узле, функ-
ция вычисления номера узла может быть следующей: reducer_id =
k
0
mod educers_count. Некорректно реализованная функция может приве-
сти к неравномерному распределению данных между reduce-узлами.
Функция
combine
запускается после map-фазы. В ней происходит про-
межуточная свертка локальных по отношению к функции map значе-
ний. Основное значение функции combine – комбинирование проме-
жуточных данных, что, в свою очередь, ведет к уменьшению объема
передаваемой между узлами информации.
Выполнение операций Copy
/
Сompare
/
Merge.
Реализуемая функция
: compare
(
k
0
n, k
0
n
+ 1)
→ {−
1
,
0
,
+1
}
.
Действие: сopy
— копирование данных, полученных в результате рабо-
ты функций map и combine (если такая была определена), с map-узлов
на reduce-узлы;
compare (или sort)
— сортировка, группировка по ключу
k
получен-
ных в результате операции copy промежуточных значений на reduce-
узле.
merge
— “слияние” данных, полученных от разных узлов, для опе-
рации свeртки.
Выполнение функции Reduce.
Реализуемая функция
: framework вызывает функцию reduce для каждо-
го уникального ключа
k
0
в отсортированном списке значений.
54 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2015. № 6