Как работает алгоритм сортировки MapReduce?

одним из основных примеров, который используется для демонстрации силы MapReduce является terasort benchmark. У меня возникли проблемы с пониманием основ алгоритма сортировки, используемого в среде MapReduce.

для меня сортировка просто включает в себя определение относительного положения элемента по отношению ко всем другим элементам. Поэтому сортировка включает в себя сравнение "всего" со "всем". Ваш средний алгоритм сортировки (быстрый, пузырьковый,...) просто делать это по-умному.

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

Так как же это на самом деле делается? Как работает этот алгоритм сортировки MapReduce?

Спасибо, что помогли мне понять.

4 97
sorting algorithm hadoop parallel-processing mapreduce

4 ответа:

вот некоторые подробности о реализация Hadoop для Terasort:

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

Так что их трюк заключается в том, как они определяют ключи во время фазы карты. По существу, они гарантируют, что каждое значение в одном редукторе гарантированно будет "предварительно Отсортировано" по отношению ко всем другим редукторам.

Я нашел бумажную ссылку через сообщение в блоге Джеймса Гамильтона.

54

Ссылка На Google:MapReduce: упрощенная обработка данных на больших кластерах

на:
OSDI ' 04: шестой симпозиум по разработке и внедрению операционных систем,
Сан-Франциско, Калифорния, декабрь 2004 года.

эта ссылка имеет ссылку на PDF и HTML-слайд.

есть еще и страница Википедии с описанием С реализации ссылки на литературу.

также критика,

Дэвид Девитт и Майкл Стоунбрейкер, пионеры в области параллельных баз данных и общих архитектур nothing, сделали несколько спорных утверждений о широте проблем, для которых может использоваться MapReduce. Они назвали его интерфейс слишком низкоуровневым и задались вопросом, действительно ли он представляет собой сдвиг парадигмы, о котором заявляли его сторонники. Они оспаривают утверждения сторонников MapReduce о новизне, ссылаясь на Teradata в качестве примера предшествующего уровня техники, который существует уже более двух десятилетий; они сравнили программистов MapReduce с программистами Codasyl, отметив, что оба они "пишут на языке низкого уровня, выполняя низкоуровневую обработку записей". Использование MapReduce входных файлов и отсутствие поддержки схемы предотвращает повышение производительности, обеспечиваемое общими функциями системы баз данных, такими как B-деревья и хэш-секционирование, хотя такие проекты, как PigLatin и Sawzall, начинают решать эти проблемы проблемы.

2

У меня был тот же вопрос, когда я читал статью Google MapReduce. @Yuval F ' s ответ в значительной степени решить мою головоломку.

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

в статье используется hash(key) mod R как пример разбиения, но это не единственный способ разбить промежуточные данные на различные задачи сокращения.

просто добавьте границу условия для @Yuval F ' s ответ чтобы сделать его полным: предположим, что min(S) и max(S) - это минимальный ключ и максимальный ключ среди выбранных ключей; все ключи = max (S) разделены на одну задачу сокращения.

нет жестких ограничений на выборку ключей, таких как min или max. Просто, более равномерно эти R ключи распределены между всеми ключами, более "параллельна" эта распределенная система и менее вероятно, что оператор reduce имеет проблему переполнения памяти.

1

только гадать...

учитывая огромный набор данных, вы бы разделили данные на некоторые куски, которые будут обрабатываться параллельно (возможно, по номеру записи, т. е. запись 1 - 1000 = раздел 1 и т. д.).

назначить / запланировать каждый раздел для конкретного узла в кластере.

каждый узел кластера дополнительно разбивает (сопоставляет) раздел на свой собственный мини-раздел, возможно, по ключевому алфавитному порядку. Итак, в разделе 1, Дайте мне все то, что начинается с A и выводит его в мини-раздел A из x. создайте новый A(x), если в настоящее время уже есть A(x). Замените x последовательным номером (возможно, это задание планировщика для этого). Т. е. Дайте мне Следующий уникальный идентификатор A(x).

передать (запланировать) задания, выполненные картографом (предыдущий шаг), узлам кластера "уменьшить". Затем Reduce Node cluster будет дополнительно уточнять вид каждой части A (x), которая будет происходить только тогда, когда все задачи mapper выполнены (на самом деле не могут начните сортировать все слова, начиная с w / A, когда есть еще возможность, что все еще будет еще один мини-раздел в процессе создания). Выведите результат в финальной отсортированной части (т. е. Sorted-A, Sorted-B и т. д.)

после этого снова объедините отсортированную секцию в один набор данных. На данный момент это просто простая конкатенация n файлов (где n может быть 26, Если вы делаете только A - Z) и т. д.

между ними могут быть промежуточные шаги... Я не уверенный.): Т. е. дальнейшее отображение и уменьшение после начального шага уменьшения.

0