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

Ответ 1

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

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

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

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

Ответ 2

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

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

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

Ответ 3

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

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

Редуктор - это уменьшитель идентичности

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

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

Ответ 4

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

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

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

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

Ответ 5

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

Ответ 6

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

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

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

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

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

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