Какая новинка в MapReduce?

68

Несколько лет назад MapReduce был провозглашен революцией в распределенном программировании. Также были критики но в целом был восторженный ажиотаж. Он даже запатентован! [1]

Название напоминает mapи о reduceфункциональном программировании, но когда я читаю (Википедия)

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

Шаг сокращения: главный узел затем собирает ответы на все подзадачи и каким-то образом объединяет их для формирования выходных данных - ответа на проблему, которую он первоначально пытался решить.

или [2]

Внутренние элементы MAP: [...] MAP разбивает входное значение на слова. [...] MAP предназначен для связывания каждой данной пары ключ / значение ввода с потенциально большим количеством промежуточных пар ключ / значение.

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

Я не могу не думать: это разделяй и властвуй (в смысле Mergesort), просто и понятно! Итак, есть ли в MapReduce (концептуальная) новизна или это просто новая реализация старых идей, полезная в определенных сценариях?


  1. Патент США № 7650331: «Система и способ эффективной крупномасштабной обработки данных» (2010 г.)
  2. Модель программирования Google MapReduce - Пересмотр R. Lämmel (2007)
Рафаэль
источник
7
Там нет новизны. Я не буду отвечать на этот вопрос, но я твердо убежден, что MapReduce не обнаружил ничего нового в вычислениях или даже в распределенных вычислениях.
edA-qa mort-ora-y
@ Арьябхата: Если есть новизна, у этого вопроса есть хороший, конструктивный ответ. Если нет, то можно сказать, что это мало что доказывает (за исключением, возможно, явного сокращения MapReduce до более старой техники), правда. Но если вы так чувствуете, во что бы то ни стало, проголосуйте!
Рафаэль
@ edA-qamort-ora-y: В этом случае мы должны быть в состоянии выразить MapReduce в более старых терминах, и это даст хороший ответ!
Рафаэль
1
@ Рафаэль, я согласен, но я не уверен, что смогу это сделать. Тем не менее, я могу заметить, что, как описано здесь (первая цитата), сортировка слиянием использует точный метод отображения / уменьшения. Это действительно может быть распределено с нулевым изменением.
edA-qa mort-ora-y

Ответы:

47

Я не могу не думать: это разделяй и властвуй, просто и понятно!

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


Итак, есть ли в MapReduce (концептуальная) новизна или это просто новая реализация старых идей, полезная в определенных сценариях?

MapReduce не открывает новых основ в теории вычислений - он не показывает новый способ разложения задачи на более простые операции. Это показывает, что конкретные более простые операции полезны для определенного класса задач.


В MapReduce газеты вклад был

  1. оценка конвейера из двух хорошо понятных ортогональных операторов, которые можно эффективно и безошибочно распределить по конкретной проблеме: создание текстового индекса большого корпуса
  2. сравнительный анализ карты-сокращения для этой проблемы, чтобы показать, сколько данных передается между узлами и как различия в задержках по этапам влияют на общую задержку
  3. показывающий, как сделать систему отказоустойчивой, чтобы сбои машины во время вычислений можно было компенсировать автоматически
  4. определение конкретных полезных вариантов реализации и оптимизаций

Некоторые критики попадают в эти классы:

  1. «Карта / уменьшение не открывает новых основ в теории вычислений». Правда. Вклад оригинальной статьи заключался в том, что эти хорошо понятые операторы с определенным набором оптимизаций были успешно использованы для решения реальных проблем более легко и безошибочно, чем одноразовые решения.
  2. Msgstr "Это распределённое вычисление нелегко разложить на операции отображения и сокращения". Справедливо, но многие так и делают.
  3. «Для конвейера с n этапами отображения / уменьшения требуется задержка, пропорциональная количеству шагов сокращения конвейера, прежде чем будут получены какие-либо результаты». Наверное, правда. Оператор Reduce должен получить все свои входные данные, прежде чем он сможет произвести полный вывод.
  4. «Карта / уменьшение является излишним для этого варианта использования». Может быть. Когда инженеры находят новый блестящий молоток, они стремятся найти что-нибудь похожее на гвоздь. Это не означает, что молот не является хорошим инструментом для определенной ниши.
  5. «Карта / уменьшение - плохая замена реляционной БД». Правда. Если реляционная БД масштабируется до вашего набора данных, тогда это замечательно для вас - у вас есть варианты.
Майк Самуэль
источник
Ну, они называют оригинальную статью «оригинальной», так что я ожидаю чего-то нового. Я не понимаю ваш первый абзац: очевидно, что существует множество алгоритмических методов, которые не разделяют и не побеждают . Если MapReduce является «единственной» эффективной реализацией d & c для определенного набора задач, это, конечно, не является чем-то оригинальным или патентным в алгоритмике (imho). Это не говорит, что это не хорошая система. Обратите внимание, что моя критика меньше связана с самим MapReduce (я думаю, это хорошо для того, для чего он сделан), чем с его приемом сообществом.
Рафаэль
1
@ Рафаэль, я не думаю, что M / R - это разделяй и властвуй в том смысле, на который ты ссылаешься. Он не предусматривает повторного применения алгоритма к меньшему подмножеству исходного ввода. Это конвейер, где этапы конвейера чередуются и сокращают операции.
Майк Самуэль
Да, правда. Я интерпретировал: «Рабочий узел может сделать это снова по очереди, что приведет к многоуровневой древовидной структуре». таким образом, но это, конечно, не означает, что то же самое происходит на каждом уровне.
Рафаэль
1
@ ex0du5, я думаю, что вы, возможно, осуждаете его за заявления, которые он не предъявляет. «Многие системы предоставили ограниченные модели программирования и использовали ограничения для автоматического распараллеливания вычислений. ... MapReduce можно считать упрощением и анализом некоторых из этих моделей на основе нашего опыта с большими вычислениями в реальном мире. ... В отличие от этого Большинство систем параллельной обработки были реализованы только в меньших масштабах и оставляют детали обработки машинных сбоев программисту ». Он ссылается на статьи Рабина и Валианта об этом, но не на статью Лискова.
Майк Сэмюэл
1
@ ex0du5, Достаточно справедливо. Я подумал: «Карта / уменьшение не открывает новых основ в теории вычислений.« Верно ». было достаточно ясно, но я переписал список вкладов.
Майк Самуэль
21

РЕДАКТИРОВАТЬ (март 2014 г.) Я должен сказать, что с тех пор я больше работал над алгоритмами для моделей вычислений типа MapReduce, и мне кажется, что я был слишком негативен. Техника «разделяй-сжимай-властвуй», о которой я говорю ниже, удивительно универсальна и может стать основой алгоритмов, которые, на мой взгляд, нетривиальны и интересны.


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

О(Nε)о(журналN)

О(1)

  • Разделите экземпляр проблемы (часто случайным образом)
  • Сделайте некоторое вычисление на каждом разделе параллельно и представьте результат вычисления компактно
  • Объедините все компактно представленные решения подзадач на одном процессоре и завершите вычисления

NО(N)N

Теперь я думаю, что на самом деле это интересный поворот на принцип «разделяй и властвуй», заключающийся в том, что после этапа разделения нужно сжимать решения подзадач, чтобы один процессор мог победить. Тем не менее, это действительно единственная техника, которую мы придумали до сих пор. Это терпит неудачу на проблемах с разреженными графами, такими как разреженная связь, например. Сравните это с потоковой моделью, которая привела к появлению множества новых идей, таких как оригинальный алгоритм сэмплирования Флайолета и Мартина, детерминированный алгоритм спаривания Мисры и Гриса, мощь простых приемов создания эскизов и т. Д.

Как парадигма программирования, уменьшение карты было очень успешным. Мои комментарии рассматривают карту редукции как интересную модель вычислений. Хорошие теоретические модели немного странные. Если они следуют реальности слишком близко, они становятся громоздкими, но, что более важно, теоремы (заимствовать термин из машинного обучения), доказанные для моделей, которые являются слишком конкретными, не обобщаются, т.е. не выполняются в других моделях. Вот почему мы хотим абстрагироваться как можно больше деталей, оставляя при этом достаточно, чтобы бросить вызов нам, чтобы придумать новые алгоритмы. Наконец, эти новые идеи должны в конечном итоге вернуться в реальный мир. PRAM - одна нереалистичная модель, которая привела к интересным идеям, но эти идеи оказались редко применимыми к параллельным вычислениям в реальном мире. С другой стороны, потоковое вещание также нереально, но это вдохновило алгоритмические идеи, которые фактически используются в реальном мире. Видетьмини-набросок . Методы рисования на самом деле также используются в системах, основанных на уменьшении карты.

Сашо Николов
источник
Возможно, M / R является более реалистичной (полезной) моделью, чем PRAM или потоки. (По крайней мере, для некоторых достаточно больших проблем.)
Xodarap
«вам нужно сжать решения подзадач, чтобы один процессор мог победить» - вы, кажется, говорите, что набор проблем, которые могут быть решены с помощью M / R, является подмножеством тех, для которых существует управляемая кэш-память или кэш решения Если это так, то мне кажется, что это утверждение одинаково хорошо применимо к большинству схем распределенных вычислений.
Майк Самуэль
1
@Xodarap, что вполне может быть. здесь я использую чисто теоретическую точку зрения алгоритмов: модель полезна, если она ведет к новым алгоритмическим перспективам. по этой причине потоковая передача не является полностью реалистичной, но привела к появлению многочисленных новых методов, которые на самом деле полезны на практике. Дело в том, какая правильная абстракция ведет к новому мышлению. текущие MR-абстракции имеют смешанный успех (но, думаю, некоторый успех)
Сашо Николов
1
@MikeSamuel «потребность» в этом предложении означает, что это то, чего требует техника, а не то, что это единственно возможная вещь. я не знаю теоретических отрицательных результатов для МР. Моя жалоба не в том, что MR строго менее мощен, чем CO. Это то, что мы не видели много нового алгоритмического мышления, вдохновленного моделью (что хорошо для системы, но разочаровывает для модели вычислений). с другой стороны, само по себе кеширование - это удивительная идея
Сашо Николов
@SashoNikolov, Понял. Спасибо за объяснение.
Майк Сэмюэль
6

Я полностью согласен с вами. С концептуальной точки зрения нет ничего действительно нового: Map / Reduce изначально был известен в Parallel Computing как модель программирования потока данных. Однако с практической точки зрения Map / Reduce, предложенный Google и последующими реализациями с открытым исходным кодом, также поддерживает Cloud Computing и в настоящее время довольно популярен для очень простых параллельных декомпозиций и обработки. Конечно, он не подходит для чего-либо еще, требующего сложной области или функциональных разложений.

Массимо Кафаро
источник
3

Я думаю, что вы ударили по голове своим комментарием.

Неверно, что в любом функциональном языке карты можно распараллелить - язык должен быть чистым . (Я считаю, что Haskell - единственный не совсем понятный, чисто функциональный язык. Lisp, OCaml и Scala не являются чистыми.)

Мы знали о преимуществах чистого кода еще с момента разделения времени, когда инженеры впервые конвейеризировали свои процессоры. Так почему же никто не использует чистый язык?

Это действительно очень сложно. Программирование на чистом языке часто ощущается как программирование, когда обе руки связаны за спиной.

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

NСзнак равноп

Xodarap
источник
Я не знаком с MapReduce, но ваше представление о нем не отличается от того, что я помню, когда его представляли как идеальный случай в параллелизме 101 в предыдущем столетии.
Жиль "ТАК - перестань быть злым"
@Gilles: Мое намерение было просто показать , что «разделяй и властвуй»! = « Распространяемый разделяй и властвуй». M / R менее тривиален, хотя, возможно, все еще не оригинален.
Xodarap
В функциональном программировании все карты могут быть распараллелены (смущающе), так почему бы не придерживаться этой парадигмы? Я не вижу, как countразделяемая переменная в вашем псевдокоде; просто передать его текущее значение do_somethingдолжно работать. Можете ли вы привести пример «реального» алгоритма обработки данных (Mergesort, Quicksort, ...), для которого рекурсивные вызовы зависят друг от друга (после вызова)?
Рафаэль
@ Рафаэль: я переписал свой ответ, чтобы лучше ответить на ваш комментарий. Я могу добавить пример, когда чистота раздражает, если вы все еще хотите.
Xodarap
1
@Raphael: Я согласен, что мой ответ был бы намного лучше, если бы я мог привести какую-то статью, показывающую, что время программирования уменьшается с X часов до Y с помощью M / R, или увеличивается с A до B за счет обеспечения чистоты, но я думаю, что все, что я могу, Я бешено машу руками и настаиваю на том, что различия нетривиальны.
Xodarap