Какие проблемы решает MapReduce?

Я читал о MapReduce некоторое время - но я не могу понять, как кто-то может принять решение использовать (или не использовать) MapReduce.

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

Это в основном проблемы, которые огромные, но не сложные. Торговый продавец в решающей степени зависит от расстояния между любой данной парой городов, поэтому, хотя его можно разбить на множество частей, частичные результаты не могут быть объединены так, чтобы появилось глобально оптимальное решение (ну, вероятно, нет; если вы знаете способ, пожалуйста, подайте заявку на медаль Поля сейчас).

С другой стороны, подсчет частот слов в гигантском корпусе является тривиально разделяемым и тривиально рекомбинируемым (вы просто складываете векторы, вычисленные для сегментов корпуса), так что map-Reduction является очевидным решением.

На практике больше проблем, как правило, легко рекомбинировать, чем нет, поэтому решение о том, следует ли распараллеливать задачу или нет, больше связано с тем, насколько она велика, а не с тем, насколько она трудна.

Может ли проблема быть эффективно решена с помощью распределенных вычислений?

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

Ваша задача: разобрать эту книгу

Пример хорошо работает, чтобы проиллюстрировать это. У вас есть большой документ ( Moby Dick от Herman Melville ), и ваша задача - провести частотный анализ всех используемых в нем слов.

Последовательный подход

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

Подход MapReduce

Подходя к этому с другой точки зрения, вы заметите, что у вас есть все эти запасные машины, и вы можете разбить эту задачу на куски. Дайте каждой машине блок текста размером 1 Мб для анализа в хэш-карту, а затем соберите все хеш-карты из каждого в один результат. Это многоуровневое решение MapReduce.

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

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

Резюме

Итак, подведем итог: если ваша проблема поддается представлению ключами, значениями, агрегированными операциями над этими значениями изолированно, то у вас есть проблема-кандидат для MapReduce.

Шаблон MapReduce взят из мира функционального программирования. Это процесс параллельного применения так называемого катаморфизма к структуре данных. Функциональные программисты используют катаморфизмы практически для каждого простого преобразования или суммирования.

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

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

Этот WPI - Приложения Map Reduce (ppt) может быть вам интересен. В нем рассматриваются различные приложения MR, а в качестве одного из обсуждавшихся случаев показано, как с помощью 100 экземпляров EC2 и 24 часов New York Times удалось преобразовать 4 ТБ отсканированных статей в 1,5 ТБ документов PDF.

Другой набор примеров, в которых MR помогал в повышении производительности, приведен по адресу: Aster - SQL Map Reduce показывает некоторые тематические исследования технологии SQL-Map Reduce, включая обнаружение мошенничества, преобразования и другие.

Map / Reduce - это особая форма алгоритма определенного вида. Вы используете его для преобразования одного огромного набора данных в другой набор данных. (Результирующий набор данных может быть или не быть огромным.) Если вы не хотите, чтобы статический вывод данных устанавливался в результате ввода статических данных, то Map / Reduce не подходит. Map / Reduce может легко сказать, сколько Джонов Смитов находится в телефонной книге Манхэттена, но это не очень подходит для создания веб-сервера.

Способ Map / Reduce работает так:

• Карта берет пары ключей (k1) и значений (v1) и отображает их в новый набор ключей (k2) и значений (v2).
• Reduce берет все значения v2 с одним и тем же ключом k2 и создает новое значение (v3).

В результате список (k1, v1) пар превращается в список (v3) s. (Конечно, значение «v3» может быть составным, которое включает в себя k2, которое может быть определено равным k1.)

Итак, вы используете это:

1. Если у вас есть так много данных, чтобы начать с того, чтобы все это последовательно проходило через один или два сервера, это заняло бы слишком много времени, и

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

3. Какими бы ни были отношения, вы уверены, что каждый фрагмент входных данных влияет только на выходное значение для одного ключа вывода.

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

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

Если вы не можете понять, как превратить ваше преобразование данных в карту / уменьшить, то, конечно, это не решение.

Существует реальное искусство выяснить, можно ли разложить проблему на что-то, с чем может справиться Map / Reduce. Например, v1 и v2 могут вообще отсутствовать во входных или выходных наборах данных. Если вы просто хотите подсчитать уникальные элементы во входных данных, тогда k1 = k2 = элемент и v1 = v2 = 1 или 0 или что-нибудь еще. Снижение только производит v3 как сумму числа k2, которое это было дано.

Поэтому трудно сказать наверняка, что преобразование данных не может быть выполнено с использованием Map / Reduce, но приведенное выше дает вам некоторые ориентиры.

MapReduce работает над любой проблемой, которая состоит из ровно 2 функций на некотором уровне абстракции. Первая функция применяется к каждому из элементов входного набора, а вторая функция объединяет результаты.

Таким образом, в любое время, когда вы хотите получить (1) результат из (n) входов, и все входы могут быть изучены / использованы функцией (1), вы можете использовать MapReduce. Опять же, это на определенном уровне абстракции. Функция (1) может быть некоторой функцией группировки, которая проверяет ввод и решает, какую из нескольких других функций использовать.

Это полезно, когда вы заранее не знаете, сколько у вас будет входных данных, когда вам нужно поделиться незаметными «единицами» работы или когда вы хотите, чтобы один результат представлял весь результат (IE выполняет пять тысяч юнит-тестов). , и если менее чем x% не удастся, верните успех).

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

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

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

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

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

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

Как пример того, который недавно появился у меня, я работал над парсером в Хаскеле. Чтобы проверить мой синтаксический анализатор, я прокачиваю список фрагментов строки через синтаксический анализатор, и затем я хочу получить единственную строку, которую я могу вывести из своих результатов, чтобы проверить, правильно ли она проанализирована. Так это выглядит так:

--my initial set of test data, a list
tests = ["string1", "string2", "string3", ...]

--Map Step: turn strings into parsed results
--note the type, which demonstrates the map
applyParser :: [String] -> [Token]
--The actual function
applyParser input = map parser input

--Second map, turn tokens into output
showTokens :: [Token] -> [String]
showTokens t = map show t

--Reduce step, concat the results
combineResults :: [String] -> String
--In haskell, reduce is the foldl function, which takes an operation to fold with, a starting element, and a list to fold on
combineResults strings = foldl concat "" strings

--Finished program
testParser = print (combineResults(showTokens(applyParser tests)))

Конечно, это просто педагогическое. Мой реальный код выглядит немного по-другому и использует больше внутренних функций (например, в fold concatэтом нет необходимости, поскольку Haskell уже включает unlinesэто [String]->String). Моя главная мысль заключалась в том, что я не ожидал использовать карту / уменьшение при запуске, она просто соответствовала моим потребностям. Я хотел сделать что-то со списками, а затем превратить мой список в один элемент вывода. Использование карты / уменьшить возникло естественным образом.

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

Это параллелизуемо?

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

Скажем, вы ищете кластер серверов, и один не может ответить в данный момент. То, что сделает mapReduce, так это то, что он не смог получить доступ к этому узлу дерева к более крупной Карте, если он перенесет его на более поздний срок и затем выполнит Map или Reduce. По сути, он пытается гарантировать, что вся информация доступна с непредсказуемостью программного и аппаратного обеспечения в средах.

Вот основные вопросы, которые я использую для проверки решения использовать (или не использовать) MapReduce.

• Является ли достижение разумной производительности параллельного выполнения с минимальными усилиями программиста важным для данной проблемы?
• Имеется ли у меня большое количество (сотни) элементов параллельного выполнения?
• Существует ли отличная пропускная способность / пропускная способность связи между элементами параллельного выполнения?
• Нужно ли обрабатывать огромное количество (ТБ) данных?

• Разлагается ли проблема, которую я пытаюсь решить, на операции Map and Reduce?

  • Карта: выполнить одну и ту же операцию для всех данных.
  • Уменьшить: выполнить одну и ту же операцию для каждой группы данных, созданных картой.

по сути, это общий шаблон «разделяй и властвуй», так что решения для распределения вычислений могут быть написаны в общем виде.

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

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