Всегда ли Reduce требуется для удаления дубликатов в MapReduce?

Question

Почему требуется уменьшение в MapReduce?Если такая работа, как подсчет количества слов в книге, приведет к тому же результату, если она выполняется одним процессом или MapReduced над фермой серверов, существует ли какая-либо возможность удаления дубликатов?Я предполагаю, что шаг Сокращения, по крайней мере в этом примере, просто суммирует результаты каждого рабочего процесса и выдает общее количество слов в книге.Я не понимаю, где дубликаты чего-либо входят в картину.

Answer 1

Уменьшение - гораздо более общая операция.Это не обязательно означает «агрегирование набора числовых значений путем многократного применения операции (например, суммирование)».Формальное определение Map-Reduce состоит в том, что это преобразование состоит из следующих этапов:

1. Map: (K k, V v) -> (K' k, V' v1 [, v2,...]) - операция, которая принимает на входе пару ключ-значение типов K и V соответственнои выдает ключ-значение или список ключей-значений, являющийся результатом потенциально разных типов.
2. Фаза тасования, в которой выполняется разбиение.
3. Reduce: (K' k, V' v1 [, v2,...]) -> (K' k, V'' v1 [, v2,...]) - операция, выполняющая вводпара ключей-значений, где «список значений» - это список всех значений, соответствующих ключу k, которые были сгенерированы фазой Map, и создает пару значений-ключей или пару ключей-значений, в которой выходной ключ должен иметьтот же тип, что и клавиша ввода, а значение произвольного типа.

Это, как вы видите, операция «Уменьшить» гораздо более гибкая и общая.

Answer 2

Шаг Reduce не предназначен для удаления дубликатов (хотя в некоторых ситуациях это возможный вариант использования). Редукция предназначена для агрегирования выходов различных картографов с одним и тем же ключом.

Например, в примере подсчета слов узел 1 может получить 10 экземпляров слова, скажем, "школа", а узел 2 может иметь 15 экземпляров, узел 3 - 12 экземпляров. Как будет рассчитываться сумма? Результаты 10, 15 и 12 находятся на разных узлах. Существует фаза тасования, которая переносит все эти значения на один узел (который представляет собой редуктор, выделенный разделителю для ключа "school"). Тогда у редуктора будут все значения для этого ключа, и он может суммировать их.

РЕДАКТИРОВАТЬ: Как упоминал Тудор, под агрегацией я подразумеваю агрегацию в более общем смысле "объединения"

РЕДАКТИРОВАТЬ 2: Чтобы прояснить сомнения RaffiM: Продолжая приведенный выше пример, скажем, в узле 1 были страницы 1-10, в узле 2 - страницы 11-20, а в узле 3 - страницы 21-30. Итак, после фазы Мао мы знаем, что на страницах 1-10 слово «школа» встречается 10 раз, на страницах 11–20 это слово появляется 15 раз, а также 15 раз на страницах 21–30. Теперь нам нужно общее количество раз, когда слово появляется во всей книге, поэтому нам нужно все же добавить их. Нам нужно 10 + 15 + 12 + цифры для других диапазонов страниц ...

Если вы не используете объединитель, картограф просто отправляет «1» при каждом появлении слова. Таким образом, для страниц 1-10 он будет отправлять <"school", 1> как значение ключа вывода 10 раз. Чтобы сделать его более эффективным, мы используем сумматор, который суммирует его на уровне картографа. Поэтому, если вы используете комбинатор, он будет использовать его в самом узле 1 и сгенерирует консолидированный вывод <"school", 10> для узла 1.