Есть ли каноническая проблема, которую, очевидно, нельзя помочь с картой / уменьшить?

Question

Я пытаюсь понять границы Hadoop и Map / Reduce, и это помогло бы узнать нетривиальную проблему или класс проблем, в которых мы знаем, что Map / Reduction не может помочь.1002 * Конечно, было бы интересно, если бы изменение одного фактора проблемы позволило бы упростить карту / уменьшить.

Спасибо

Answer 1

На ум приходят две вещи:

1. Все, что требует в режиме реального времени / интерактивного / низкого времени отклика. За любую работу, переданную в Hadoop, взимается фиксированная стоимость.

2. Любая проблема, которая не смущающе параллельна . Hadoop может справиться с множеством проблем, которые требуют некоторой простой взаимозависимости между данными, поскольку записи объединяются на этапе сокращения. Однако некоторые алгоритмы обработки графиков и машинного обучения сложно написать в Hadoop, поскольку существует слишком много операций, зависящих друг от друга. Некоторые алгоритмы машинного обучения требуют очень малой задержки, произвольного доступа к большому набору данных, который Hadoop не предоставляет «из коробки».

Answer 2

Не совсем понятно, что вы подразумеваете под «мы знаем, что карта / уменьшение не может помочь». Другие ответы кажутся довольными некоторыми примерами, когда нетривиально, легко или не слишком сложно, как использовать карту «Уменьшить», чтобы получить некоторое существенное ускорение, но то, что легко для одного, может быть не для кого-то другого, и то же самое со значительным. Я лично был бы более удовлетворен теоремой, которая говорит, что что-то не может быть сделано. Если мы посмотрим на сложность вычислений, то есть класс сложных для распараллеливания задач, P-полных задач. Хорошо известны такие проблемы, как распознавание грамматики без контекста (важно для компиляторов), линейное программирование и некоторые проблемы со сжатием. Запись в Википедии содержит больше.

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

Другой вопрос: можем ли мы имитировать какой-либо параллельный алгоритм в редукте карт? Конечно, мы не можем отобразить карту, чтобы преодолеть наши проблемы P-complete, но, возможно, есть некоторые проблемы, которые решаются параллельно, но не в mapreduce. Я не знаю каких-либо таких проблем, но я знаю о бумаге, которая указывает в противоположном направлении, хотя и с некоторыми предположениями «Моделирование параллельных алгоритмов в среде MapReduce с приложениями к параллельной вычислительной геометрии», Майкл Т. Гудрич

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

Answer 3

Ответ Гангадхару (извините, недостаточно места в поле для комментариев):

Мне нравится ваш ответ о разделяй и властвуй, но я хочу добавить предостережение.Mapreduce не очень хорошо справляется с рекурсивным аспектом алгоритмов «разделяй и властвуй», потому что комбинация подзадач для определенных алгоритмов Ц / Ц зависит от того, что в конечном итоге сведется к одному ключу.Возьмем, к примеру, алгоритм сортировки слиянием (игнорируя на момент, что сортировка в Hadoop тривиальна из-за ключевых свойств упорядочения его реализации Mapreduce): вы использовали бы ваш картограф для разделения данных на две частииспользуя произвольный идентификатор для ключа.Ваша фаза сокращения будет объединять списки значений для соответствующих ключей.

7 3 2 4 1 5 8 9 would map to 
1->[[7],[3]] 2->[[2],[4]] 3->[[1],[5]] 4->[[8],[9]] would reduce to
3,7 2,4 1,5 8,9 would map to 
1->[[3,7],[2,4]] 2->[[1,5],[8,9]] 
etc.

Вы видите, что количество ключей уменьшается на два (или любой другой коэффициент разбиения, который вы используете для алгоритма Ц / Ц) и в конечном итогеследует перейти к одному ключу для отсортированного списка.Это плохо для параллелизма.

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

Answer 4

Как утверждают другие: проблему нужно легко нарезать на кусочки, которые можно обрабатывать независимо.

Итак, позвольте мне привести два примера из моего прошлого как архитектора WebAnalytics (по сути, я пытался сделать то, что предлагает Hadoop сейчас ... без Hadoop ... используя сценарии оболочки bash в одной системе с несколькими ядрами ЦП). Я надеюсь, что эти двое дадут вам некоторое представление о том, как эти границы могут выглядеть в действительности.

Контекст:

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

Два моих примера:

1. Свойство, которое вы хотите использовать для корреляции поведения, является плохим в некоторых частях (скажем, sessionid). Это часто случается, если сайт размещает этот фактор с помощью JavaScript (YUCK!). Тогда становится чрезвычайно трудно (из моего опыта: почти невозможно) разделить работу по исправлению этого коррелирующего свойства. Это «необходимо» сделать в «одном огромном разделе», и поэтому MapReduce не может вам помочь.
2. Теперь свойство, необходимое для разбиения всех данных на управляемые куски, является надежным (т. Е. Все, что один отдельный браузер делал на сайте), становится чрезвычайно легко создавать множество подмножеств ваших данных. Вы можете легко масштабировать обработку для большого сайта до сотен систем.

В прошлом кто-то однажды сказал мне, что уравнения динамики жидкости (Навье-Стокса) не могут быть разбиты на «восстанавливаемые» части. Хотя я вижу некоторую логику в том, почему это было бы верно (каждая часть жидкости влияет на любую другую часть жидкости); Я должен дать понять, что я даже не собираюсь пытаться понять эти уравнения.

Я надеюсь, что эти примеры помогут вам найти границы.

Answer 5

Я думаю, что любая проблема, которая не может быть решена до разделяй и властвуй , не будет работать так хорошо с hadoop.Если алгоритм можно изменить, чтобы он мог создавать подзадачи, то я думаю, что он может хорошо работать под Hadoop.

Чтобы добавить к вашему вопросу (а не к ответу, я делаю эту часть комментария?), что, если есть подзадачи, в которые я могу разбить проблему, но нет четкого способа сделать фазу filter hadoop?Я предполагаю, что все еще можно использовать hadoop для фазы map и выполнить сокращение на одной машине.