Какова цель фазы перетасовки и сортировки в редукторе в программе Map Reduce?

В программировании Map Reduce фаза сокращения включает в себя перемешивание, сортировку и сокращение в качестве своих частей. Сортировка - дело затратное.

Какова цель фазы перетасовки и сортировки в редукторе в программе Map Reduce?

Прежде всего, shufflingэто процесс передачи данных от картографов редукторам, поэтому я думаю, что очевидно, что это необходимо редукторам, так как в противном случае они не могли бы иметь никаких входных данных (или входных данных от каждого преобразователя). . Перемешивание может начаться даже до завершения фазы карты, чтобы сэкономить время. Вот почему вы можете увидеть статус уменьшения больше 0% (но меньше 33%), когда статус карты еще не равен 100%.

Sortingэкономит время для редуктора, помогая ему легко определить, когда должна начаться новая задача сокращения. Он просто запускает новую задачу сокращения, когда следующий ключ в отсортированных входных данных отличается от предыдущего, проще говоря. Каждая задача уменьшения принимает список пар ключ-значение, но должна вызывать метод reduce (), который принимает ввод списка ключей (значения), поэтому он должен группировать значения по ключу. Это легко сделать, если входные данные предварительно отсортированы (локально) на этапе отображения и просто отсортированы слиянием на этапе сокращения (поскольку редукторы получают данные от многих картографов).

Partitioning, о котором вы упомянули в одном из ответов, - это другой процесс. Он определяет, в каком редукторе будет отправлена ​​пара (ключ, значение), вывод фазы карты. По умолчанию Partitioner использует хеширование ключей, чтобы распределять их по задачам уменьшения, но вы можете переопределить его и использовать свой собственный Partitioner.

Отличный источник информации для этих шагов - это руководство Yahoo .

Хорошее графическое представление этого - следующее (на этом рисунке перемешивание называется «копией»):

Обратите внимание, что shufflingи sortingне выполняются вообще, если вы укажете нулевые редукторы (setNumReduceTasks (0)). Затем задание MapReduce останавливается на этапе отображения, а этап отображения не включает никакой сортировки (поэтому даже этап отображения выполняется быстрее).

ОБНОВЛЕНИЕ. Поскольку вы ищете что-то более официальное, вы также можете прочитать книгу Тома Уайта «Hadoop: The Definitive Guide». Вот интересная часть вашего вопроса.
Том Уайт является коммиттером Apache Hadoop с февраля 2007 года и является членом Apache Software Foundation, так что я думаю, что это довольно надежно и официально ...

Давайте еще раз вернемся к ключевым этапам программы Mapreduce.

Фаза карты осуществляется картографами. Картографы работают с несортированными парами "ключ / значение" ввода. Каждый преобразователь выдает ноль, одну или несколько пар выходных ключей / значений для каждой пары входных ключей / значений.

Фаза комбината осуществляется комбайнеров. Комбайнер должен сочетать в себе пары ключ / значение с тем же ключом. Каждый комбайнер может запускаться ноль, один или несколько раз.

Фаза перетасовать и сортировка осуществляется в рамках. Данные от всех преобразователей группируются по ключу, разделяются между редукторами и сортируются по ключу. Каждый редуктор получает все значения, связанные с одним и тем же ключом. Программист может предоставить специальные функции сравнения для сортировки и разделитель для разделения данных.

Разметки решают , какой редуктор получит определенную пару ключей значения.

В редукторе Получает отсортирован ключ / [список значений] пар, отсортированный по ключу. Список значений содержит все значения с одним и тем же ключом, созданные сопоставителями. Каждый редуктор выдает ноль, одну или несколько пар выходных ключей / значений для каждой пары входных ключей / значений .

Для лучшего понимания ознакомьтесь с этой статьей javacodegeeks Марии Юрковичовой и статьей mssqltips от Datta.

Ниже приведено изображение из статьи safaribooksonline.

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

Если я снова скажу настоящую цель

• Разделение: улучшает параллельную обработку, распределяя нагрузку обработки между разными узлами (Mappers), что позволяет сэкономить общее время обработки.

• Комбинировать: уменьшает вывод каждого Mapper. Это сэкономит время, затрачиваемое на перенос данных с одного узла на другой.

• Sort (Shuffle & Sort): упрощает во время выполнения планирование (создание / запуск) новых редукторов, где при просмотре отсортированного списка элементов всякий раз, когда текущий ключ отличается от предыдущего, он может порождать новый редуктор .

Некоторые требования к обработке данных вообще не нуждаются в сортировке. Syncsort сделал сортировку в Hadoop подключаемой. Вот хороший блог от них о сортировке. Процесс перемещения данных из картографов в редукторы называется перетасовкой, дополнительную информацию можно найти в этой статье.

Я всегда предполагал, что это необходимо, так как вывод сопоставителя является входом для редуктора, поэтому он был отсортирован на основе пространства ключей, а затем разделен на сегменты для каждого входа редуктора. Вы хотите, чтобы все одни и те же значения ключа попадали в одну корзину, идущую к редуктору, чтобы они сокращались вместе. Нет смысла отправлять K1, V2 и K1, V4 в разные редукторы, поскольку они должны быть вместе, чтобы их можно было уменьшить.

Пытался объяснить это как можно проще

Перемешивание - это процесс, с помощью которого промежуточные данные от сопоставителей передаются 0,1 или более редукторам. Каждый редуктор получает 1 или несколько ключей и связанных с ним значений в зависимости от количества редукторов (для сбалансированной нагрузки). Далее значения, связанные с каждым ключом, сортируются локально.

Есть только две вещи, которые MapReduce делает ЕСТЕСТВЕННО: сортировка и (реализовано путем сортировки) масштабируемый GroupBy.

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

Это хорошее чтение. Надеюсь, поможет. Что касается сортировки, которая вас интересует, я думаю, что это для операции слияния на последнем шаге Map. Когда операция сопоставления завершена и необходимо записать результат на локальный диск, будет выполнено множественное слияние с разбиениями, созданными из буфера. А для операции слияния полезна расширенная сортировка каждого раздела.

Что ж, в Mapreduce есть две важные фразы: Mapper и reducer, оба слишком важны, но Reducer является обязательным. В некоторых программах редукторы необязательны. А теперь переходим к вашему вопросу. Перемешивание и сортировка - две важные операции в Mapreduce. Первая структура Hadoop принимает структурированные / неструктурированные данные и разделяет данные на ключ и значение.

Теперь программа Mapper разделяет и упорядочивает данные по ключам и значениям для обработки. Создайте значения ключа 2 и значения 2. Эти значения следует обработать и перестроить в надлежащем порядке, чтобы получить желаемое решение. Теперь это перемешивание и сортировка выполняется в вашей локальной системе (Framework позаботится об этом) и обрабатываются в локальной системе после очистки данных в локальной системе. Хорошо

Здесь мы также используем комбайнер и разделение, чтобы оптимизировать этот процесс перемешивания и сортировки. После правильного размещения эти ключевые значения передаются в Reducer для получения желаемого результата клиента. Наконец, редуктор получит желаемый результат.

K1, V1 -> K2, V2 (мы напишем программу Mapper), -> K2, V '(здесь перемешайте и смягчите данные) -> K3, V3 Сгенерируйте вывод. К4, В4.

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

Ваш вопрос: какова цель фазы перетасовки и сортировки в редукторе в программе Map Reduce?

Краткий ответ: обработать данные для получения желаемого результата. Перемешивание - это агрегирование данных, уменьшение - получение ожидаемого результата.