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

Я не ищу фрагменты кода, просто "текстовые" примеры.

Сокращение карт - это структура, которая была разработана для эффективной обработки огромных объемов данных. Например, если у нас есть 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, чтобы мы могли вычислить всех Общайтесь с друзьями один раз в день и сохраняйте эти результаты. Позже это просто быстрый поиск. У нас много дисков, это дешево.

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

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, мы можем быстро посмотреть (B D)и увидеть, что у них есть три общих друга (A C E).

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

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

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

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

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

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

1. Группировка по / агрегации. Здесь преимущество этапа перетасовки очевидно. Объяснение, что перемешивание также является распределенной сортировкой, также помогает объяснение алгоритма распределенной сортировки.

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