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

Question

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

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

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

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

Спасибо, Чандер

Answer 1

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

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

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

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

Answer 2

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

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

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

Answer 3

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

Во время фазы карты (Input_Key, Input_Value) излучать (Input_Value, Input Key)

Reducer - это Identity Reduceer

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

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

Answer 4

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

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

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

"TeraSort - это стандартная сортировка карты / сокращения, за исключением пользовательского разделителя, который использует отсортированный список из N - 1 выборочных ключей, которые определяют диапазон ключей для каждого сокращения. В частности, все ключи такиечто выборка [i - 1] <= key <sample [i] отправляется для сокращения i. Это гарантирует, что все выходные данные для Reduce i меньше, чем выходные данные для Reduction i + 1. "</p>

Answer 5

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

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

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

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

Находите объяснение в http://www.chinacloud.cn/upload/2014-01/14010410467139.pdf

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

Answer 6

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