Одним из основных примеров, который используется для демонстрации возможностей MapReduce, является тест Terasort . Мне сложно понять основы алгоритма сортировки, используемого в среде MapReduce.
Для меня сортировка просто включает определение относительного положения элемента по отношению ко всем другим элементам. Таким образом, сортировка предполагает сравнение «всего» со «всем». Ваш средний алгоритм сортировки (быстрый, пузырьковый, ...) просто делает это разумно.
На мой взгляд, разделение набора данных на множество частей означает, что вы можете отсортировать один фрагмент, а затем вам все равно придется интегрировать эти части в «полный» полностью отсортированный набор данных. Учитывая терабайтный набор данных, распределенный по тысячам систем, я ожидаю, что это будет огромной задачей.
Так как же это сделать на самом деле? Как работает этот алгоритм сортировки MapReduce?
Спасибо, что помогли мне понять.
У меня возник тот же вопрос, когда я читал статью Google MapReduce. @Yuval F «s ответ довольно много решить мою загадку.
Одна вещь, которую я заметил при чтении статьи, - это то, что волшебство происходит при разбиении (после карты, до уменьшения).
В документе используется
hash(key) mod R
в качестве примера разделения, но это не единственный способ разделить промежуточные данные для различных задач сокращения.Просто добавьте граничные условия для @Yuval F «s ответа , чтобы сделать его полным: предположит , что мин (S) и максимальный (S) является минимальным ключом и максимальным ключ среди выбранных ключей; все ключи <min (S) разделены на одну задачу сокращения; наоборот, все ключи> = max (S) разделены на одну задачу сокращения.
Нет никаких жестких ограничений на выборку ключей, таких как min или max. Просто, более равномерно эти R-ключи распределяются между всеми ключами, более «параллельна» эта распределенная система и менее вероятно, что оператор сокращения имеет проблему переполнения памяти.
источник
Просто догадываюсь ...
Учитывая огромный набор данных, вы должны разделить данные на несколько частей, которые будут обрабатываться параллельно (возможно, по номеру записи, например, запись 1 - 1000 = раздел 1 и т. Д.).
Назначьте / запланируйте каждый раздел конкретному узлу в кластере.
Каждый узел кластера дополнительно разбивает (отображает) раздел на свой собственный мини-раздел, возможно, в алфавитном порядке ключей. Итак, в разделе 1 достаньте мне все, что начинается с A, и выведите его в мини-раздел A из x. Создайте новый A (x), если в настоящее время уже существует A (x). Замените x порядковым номером (возможно, это задание планировщика). Т.е. дайте мне следующий уникальный идентификатор A (x).
Передать (запланировать) задания, выполненные картографом (предыдущий шаг), узлам кластера «уменьшить». Затем сокращение кластера узлов будет дополнительно уточнять вид каждой части A (x), что произойдет только тогда, когда будут выполнены все задачи сопоставителя (на самом деле невозможно начать сортировку всех слов, начиная с A, когда все еще существует вероятность того, что все еще есть будет еще один мини-раздел в процессе создания). Выведите результат в окончательный отсортированный раздел (например, Sorted-A, Sorted-B и т. Д.)
После этого снова объедините отсортированный раздел в единый набор данных. На данный момент это просто объединение n файлов (где n может быть 26, если вы выполняете только A - Z) и т. Д.
Между ними могут быть промежуточные шаги ... Я не уверен :). Т.е. дальнейшее отображение и сокращение после первого шага уменьшения.
источник