Сортировка больших данных с помощью MapReduce / Hadoop

java hadoop mapreduce

24067 просмотра

6 ответа

4525 Репутация автора

Я читаю о MapReduce, и следующее смущает меня.

Предположим, у нас есть файл с 1 миллионом записей (целых чисел), и мы хотим отсортировать их с помощью MapReduce. Я понял, как это сделать:

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

Я сомневаюсь, что если у нас есть один редуктор, то как он использует распределенную структуру, если, в конце концов, нам нужно объединить результат в одном месте? Проблема сводится к объединению 1 миллиона записей в одном месте. Это так или я что-то упустил?

Спасибо чандер

Автор: Chander Shivdasani Источник Размещён: 02.09.2010 06:46

Ответы (6)


23 плюса

29968 Репутация автора

Решение

Проверьте сортировку слиянием.

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

Если редуктор получает 4 отсортированных списка, ему нужно только найти наименьший элемент из 4 списков и выбрать его. Если число списков является постоянным, это уменьшение является операцией O (N).

Также, как правило, редукторы также «распределены» по дереву, поэтому работа может быть распараллелена.

Автор: Peter Tillemans Размещён: 02.09.2010 06:51

1 плюс

7320 Репутация автора

Я думаю, что объединение нескольких отсортированных элементов является более эффективным, чем объединение нескольких несортированных элементов. Таким образом, мапперы выполняют задачу сортировки кусков, а редуктор объединяет их. Если бы картографы не выполнили сортировку, редуктору будет сложно выполнить сортировку.

Автор: Gopi Размещён: 02.09.2010 06:52

12 плюса

17131 Репутация автора

Как уже упоминали другие, слияние намного проще, чем сортировка, поэтому здесь есть большая победа.

Однако выполнение O (N) последовательной операции с гигантским набором данных также может быть непозволительным. Как вы правильно заметили, лучше также найти способ выполнять слияние параллельно.

Один из способов сделать это - заменить функцию разделения на случайный разделитель (что обычно используется) на что-то более умное. Например, Pig делает для этого выборку вашего набора данных, чтобы получить приблизительное приближение распределения ваших значений, а затем назначать диапазоны значений различным редукторам. Редуктор 0 получает все элементы <1000, редуктор 1 получает все элементы> = 1000 и <5000 и так далее. Затем вы можете выполнить слияние параллельно, и конечный результат сортируется по количеству каждой задачи редуктора.

Автор: SquareCog Размещён: 10.09.2010 07:41

7 плюса

1519 Репутация автора

Таким образом, самый простой способ сортировки с использованием map-Reduce (хотя и не самый эффективный) состоит в следующем

Во время фазы карты (Input_Key, Input_Value) выбрасывается (Input_Value, Input Key)

Редуктор - редуктор личности

Так, например, если наши данные представляют собой базу данных учеников и возрастов, то ваши данные для картографа будут ('A', 1) ('B', 2) ('C', 10) ... и выходные данные будут (1, А) (2, В) (10, С)

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

Автор: rOrlig Размещён: 11.04.2011 07:26

2 плюса

682 Репутация автора

Извините за опоздание, но для будущих читателей, да, Чандер, вы ошибаетесь

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

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

«TeraSort - это стандартная сортировка карты / сокращения, за исключением пользовательского разделителя, который использует отсортированный список из N - 1 выборочных ключей, которые определяют диапазон ключей для каждого сокращения. В частности, все ключи, такие как [i - 1] <= ключ Автор: Alok Nayak Размещён: 27.06.2013 05:26

1 плюс

388 Репутация автора

Сортировка может быть эффективно реализована с помощью MapReduce. Но вы, кажется, думаете о реализации сортировки слиянием с использованием mapreduce для достижения этой цели. Возможно, это не идеальный кандидат.

Как вы намекали, сортировка слиянием (с map-Reduce) будет включать следующие шаги:

  1. Разделите элементы на небольшие группы и распределите каждую группу по картографическим методам.
  2. Каждый сопоставитель будет сортировать подмножество и возвращать {K, {subset}}, где K одинаково для всех сопоставителей.
  3. Поскольку один и тот же K используется во всех преобразователях, только один понижающий и, следовательно, только один восстановитель. Редуктор может объединить данные и вернуть отсортированный результат

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

Нашел объяснение на http://www.chinacloud.cn/upload/2014-01/14010410467139.pdf

Возвращаясь к сортировке слиянием, это было бы возможно, если бы инструмент hadoop (или эквивалентный) предоставлял иерархию редукторов, где выходные данные одного уровня редукторов переходят на следующий уровень редукторов, или возвращают его к тому же набору редукторов

Автор: prabhakar palanivel Размещён: 29.08.2016 06:07
Вопросы из категории :
32x32