Ответ 1

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

Например, в SQL с учетом даты рождения выяснить, сколько людей в возрасте> 30 лет на миллион записей потребуется некоторое время, и это увеличится только на порядок при увеличении сложности запроса. Map Reduce предоставляет кластерную реализацию, где данные обрабатываются распределенным образом.

Вот статья в Википедии, объясняющая, что такое map-reduce

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

Лично я нашел эту ссылку весьма полезной для понимания концепции

Копирование объяснения, предоставленного в блоге (в случае, если ссылка устарела)

Найти друзей

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

Я зачеркну детали, но все сводится к определению двух функций: функции карты и функции уменьшения. Функция map принимает значение и выводит пары ключ: значение. Например, если мы определим функцию карты, которая принимает строку и выводит длину слова в качестве ключа, а само слово в качестве значения, тогда map (steve) вернет 5: steve, а map (savannah) вернет 8: savannah, Возможно, вы заметили, что функция map не имеет состояния и требует только входного значения для вычисления ее выходного значения. Это позволяет нам запускать функцию map параллельно со значениями и дает огромное преимущество. Прежде чем мы перейдем к функции Reduce, каркас mapreduce группирует все значения вместе по ключу, поэтому, если функции карты выводят следующие пары ключ: значение:

3 : the
3 : and
3 : you
4 : then
4 : what
4 : when
5 : steve
5 : where
8 : savannah
8 : research

Они группируются как:

3 : [the, and, you]
4 : [then, what, when]
5 : [steve, where]
8 : [savannah, research]

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

3 : 3
4 : 3
5 : 2
8 : 2

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

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

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

Легко, правда? Если вы когда-либо читали о mapreduce, приведенный выше сценарий не является чем-то новым... это "Hello, World" из mapreduce. Итак, вот реальный пример использования (Facebook может на самом деле или не может делать следующее, это всего лишь пример):

У Facebook есть список друзей (обратите внимание, что друзья - это двунаправленная вещь на Facebook. Если я твой друг, то ты мой). У них также много дискового пространства, и они ежедневно обслуживают сотни миллионов запросов. Они решили предварительно вычислить вычисления, когда они могут сократить время обработки запросов. Одним из распространенных запросов обработки является функция "У вас с Джо 230 общих друзей". Когда вы заходите в профиль кого-то, вы видите список общих друзей. Этот список не часто меняется, поэтому было бы расточительно пересчитывать его каждый раз, когда вы посещаете профиль (конечно, вы можете использовать приличную стратегию кэширования, но тогда я не смогу продолжать писать о mapreduce для этой проблемы). Мы собираемся использовать mapreduce, чтобы мы могли вычислять всех общих друзей один раз в день и сохранять эти результаты. Позже это просто быстрый поиск. У нас много дисков, это дешево.

Предположим, что друзья хранятся как Person-> [Список друзей], тогда наш список друзей:

A -> B C D
B -> A C D E
C -> A B D E
D -> A B C E
E -> B C D

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

For map(A -> B C D) :

(A B) -> B C D
(A C) -> B C D
(A D) -> B C D

For map(B -> A C D E) : (Note that A comes before B in the key)

(A B) -> A C D E
(B C) -> A C D E
(B D) -> A C D E
(B E) -> A C D E
For map(C -> A B D E) :

(A C) -> A B D E
(B C) -> A B D E
(C D) -> A B D E
(C E) -> A B D E
For map(D -> A B C E) :

(A D) -> A B C E
(B D) -> A B C E
(C D) -> A B C E
(D E) -> A B C E
And finally for map(E -> B C D):

(B E) -> B C D
(C E) -> B C D
(D E) -> B C D
Before we send these key-value pairs to the reducers, we group them by their keys and get:

(A B) -> (A C D E) (B C D)
(A C) -> (A B D E) (B C D)
(A D) -> (A B C E) (B C D)
(B C) -> (A B D E) (A C D E)
(B D) -> (A B C E) (A C D E)
(B E) -> (A C D E) (B C D)
(C D) -> (A B C E) (A B D E)
(C E) -> (A B D E) (B C D)
(D E) -> (A B C E) (B C D)

Каждая строка будет передана в качестве аргумента редуктору. Функция Reduce просто пересечет списки значений и выведет ту же клавишу с результатом пересечения. Например, Reduce ((AB) → (ACDE) (BCD)) выведет (AB): (CD) и означает, что у друзей A и B есть C и D в качестве общих друзей.

Результат после сокращения:

(A B) -> (C D)
(A C) -> (B D)
(A D) -> (B C)
(B C) -> (A D E)
(B D) -> (A C E)
(B E) -> (C D)
(C D) -> (A B E)
(C E) -> (B D)
(D E) -> (B C)

Теперь, когда D посещает профиль B, мы можем быстро посмотреть вверх (BD) и увидеть, что у них есть три общих друга (ACE).

Ответ 2

Один из лучших примеров реализации Hadoop-подобной MapReduce.

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

Ответ 3

Один набор знакомых операций, которые вы можете делать в MapReduce, - это набор обычных операций SQL: SELECT, SELECT WHERE, GROUP BY, ect.

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

Ответ 4

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

Обычно я беру две вещи:

• Групповые/агрегирования. Здесь преимущество шагания ясно. Объяснение того, что перетасовка также распределяется sort +, также помогает объяснение алгоритма распределенного сортирования.

• Соединение двух таблиц. Люди, работающие с БД, знакомы с концепцией и ее проблемой масштабируемости. Покажите, как это можно сделать в MR.