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

Question

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

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

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

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

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

Answer 1

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

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

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

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

Answer 2

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

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

Эта ссылка содержит ссылку на PDF и HTML-слайд.

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

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

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

Answer 3

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

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

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

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

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

Answer 4

Просто угадай ...

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

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

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

Передать (запланировать) задания, выполненные преобразователем (предыдущий шаг), в узлы «сокращения» кластера. Затем кластер сокращения узла будет дополнительно улучшать сортировку каждой части A (x), которая будет происходить только после того, как все задачи маппера будут выполнены. будет еще один мини раздел в разработке). Выведите результат в конечном отсортированном разделе (то есть Sorted-A, Sorted-B и т. Д.)

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

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