Простое объяснение MapReduce?

30

Возьмите кучу данных
Выполнить какие-то преобразование, которое преобразует каждую опорную точку на другой вид опорной точки
Объединить эти новые данные в еще более простые данные

Шаг 2 является картой. Шаг 3 - Уменьшить.

Например,

Получить время между двумя импульсами на пару метров давления на дороге
Карты тех времен на скорость, основанной на расстоянии метров
уменьшить эти скорости до средняя скорость

Причина, по которой MapReduce разделяется между Map и Reduce, заключается в том, что различные части можно легко выполнить параллельно. (Особенно, если у Сокращения есть определенные математические свойства.)

Для комплексного, но хорошего описания MapReduce см .: Google's MapReduce Programming Model -- Revisited (PDF).

источник

2008-08-26 20:04:46

14

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

Типичная реализация: реализация

for each document 
    for each word in the document 
     get the counter associated to the word for the document 
     increment that counter 
    end for 
end for

MapReduce:

Map phase (input: document key, document) 
for each word in the document 
    emit an event with the word as the key and the value "1" 
end for 

Reduce phase (input: key (a word), an iterator going through the emitted values) 
for each value in the iterator 
    sum up the value in a counter 
end for

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

Каждый рабочий выход (являющийся Работой Map или Сокращением) фактически является файлом, хранящимся в распределенной файловой системе (GFS для Google) или в распределенной базе данных для CouchDB.

источник

2008-08-26 21:47:21

52

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

map Функция принимает данные и выводит результат, который удерживается в барьере. Эта функция может работать параллельно с большим числом тех же map задача. Затем набор данных может быть равен , уменьшенному до скалярного значения.

Так что если вы думаете о нем, как SQL заявление

SELECT SUM(salary) 
FROM employees 
WHERE salary > 1000 
GROUP by deptname

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

Уменьшить будет суммировать каждую из этих групп. Предоставление вам вашего результирующего набора.

только набрался это из моих university отмечает исследование бумаги Google

источник

2008-08-26 22:21:28

161

Идя весь путь вниз к основам для карты и Reduce.

Карта является функцией, которая «превращает» вещи в каком-то списке другого рода пункта и положил их обратно в том же виде списка.

Предположим, у меня есть список чисел: [1,2,3], и я хочу удвоить каждое число, в этом случае функция «удвоить каждое число» - это функция x = x * 2. И без отображений , я мог бы написать простой цикл, скажу

A = [1, 2, 3] 
foreach (item in A) A[item] = A[item] * 2

и я а = [2, 4, 6], но вместо того чтобы писать петли, если у меня есть функция карты я мог бы написать

A = [1, 2, 3].Map(x => x * 2)

x => x * 2 - функция, выполняемая против элементов в [1,2,3]. Случается, что программа берет каждый элемент, выполняет (x => x * 2) против него, делая x равным каждому элементу и выдает список результатов.

1 : 1 => 1 * 2 : 2 
2 : 2 => 2 * 2 : 4 
3 : 3 => 3 * 2 : 6

поэтому после выполнения функции карты с (х => х * 2) вы бы [2, 4, 6].

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

Поиск суммы или нахождения средних значений - это все экземпляры функции уменьшения. Такие, как, если у вас есть список номеров, скажем, [7, 8, 9], и вы хотите, чтобы они подвели итоги, вы бы написать цикл, как этот

A = [7, 8, 9] 
sum = 0 
foreach (item in A) sum = sum + A[item]

Но, если у вас есть доступ к снижению функции , вы могли бы написать это

A = [7, 8, 9] 
sum = A.reduce(0, (x, y) => x + y)

Теперь это немного сбивает с толку, почему есть 2 аргументы (0 и функция х и у) прошло. Чтобы функция уменьшения была полезной, она должна иметь возможность принимать 2 элемента, вычислять что-то и «уменьшать», что 2 элемента до одного единственного значения, таким образом, программа могла бы уменьшить каждую пару до тех пор, пока у нас не будет единственного значения.

выполнение будет следующим образом:

result = 0 
7 : result = result + 7 = 0 + 7 = 7 
8 : result = result + 8 = 7 + 8 = 15 
9 : result = result + 9 = 15 + 9 = 24

Но вы не хотите, чтобы начать с нулями все время, так что первый аргумент там, чтобы указать начальное значение конкретно значение в первом result = линия.

говорит, что вы хотите, чтобы подвести 2 списков, это может выглядеть следующим образом:

A = [7, 8, 9] 
B = [1, 2, 3] 
sum = 0 
sum = A.reduce(sum, (x, y) => x + y) 
sum = B.reduce(sum, (x, y) => x + y)

или версию вы бы больше шансов найти в реальном мире:

A = [7, 8, 9] 
B = [1, 2, 3] 

sum_func = (x, y) => x + y 
sum = A.reduce(B.reduce(0, sum_func), sum_func)

Это хорошо в программном обеспечении БД, потому что с поддержкой Map \ Reduce вы можете работать с базой данных, не зная, как данные хранятся в БД для ее использования, для чего нужен механизм БД.

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

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

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

источник

2008-08-27 17:09:09 chakrit

17

MAP и REDUCE являются старыми функциями Лиспа от времени, когда человек убил последних динозавров.

Представьте у вас есть список городов с информаций о наименовании, количестве людей, живущих там, и размер города:

(defparameter *cities* 
    '((a :people 100000 :size 200) 
    (b :people 200000 :size 300) 
    (c :people 150000 :size 210)))

Теперь вы можете найти город с самой высокой плотностью населения ,

Сначала мы создаем список названий городов и плотности населения с использованием карты:

(map 'list 
    (lambda (city) 
     (list (first city) 
       (/ (getf (rest city) :people) 
        (getf (rest city) :size)))) 
    *cities*) 

=> ((A 500) (B 2000/3) (C 5000/7))

Использование СНИЖЕНИЯ теперь мы можем найти город с наибольшей плотностью населения.

(reduce (lambda (a b) 
      (if (> (second a) (second b)) 
      a 
      b)) 
     '((A 500) (B 2000/3) (C 5000/7))) 

=> (C 5000/7)

Объединяя обе части мы получаем следующий код:

(reduce (lambda (a b) 
      (if (> (second a) (second b)) 
      a 
      b)) 
     (map 'list 
      (lambda (city) 
       (list (first city) 
        (/ (getf (rest city) :people) 
         (getf (rest city) :size)))) 
      *cities*))

Введем функции:

(defun density (city) 
    (list (first city) 
     (/ (getf (rest city) :people) 
      (getf (rest city) :size)))) 

(defun max-density (a b) 
    (if (> (second a) (second b)) 
      a 
      b))

Тогда мы можем записать наш MAP СНИЖЕНИЯ код, как:

(reduce 'max-density 
     (map 'list 'density *cities*)) 

=> (C 5000/7)

Он называет MAP и REDUCE (оценка наизнанку), поэтому он называется map уменьшить.

источник

2009-04-17 22:29:41

3

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

cat input | map | reduce > output

источник

2011-07-05 14:52:54

9

Действительно легко, быстро и «для чайников» введение в MapReduce доступен по адресу: http://www.marcolotz.com/?p=67

проводки некоторые из его содержание:

Во-первых, почему был создан MapReduce?

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

Что такое MapReduce true strengths?

Можно сказать, что магия MapReduce основана на приложении Map and Reduce functions. Должен признаться, товарищ, что я категорически не согласен. Основная особенность, которая сделала MapReduce настолько популярной, - это возможность автоматической распараллеливания и распределения в сочетании с простым интерфейсом. Этот фактор, суммированный с прозрачной обработкой ошибок для большинства ошибок, сделал эту структуру настолько популярной.

Чуть больше глубины на бумаге:

MapReduce первоначально был упомянут в статье Google (Dean & Ghemawat, 2004 - ссылка здесь) в качестве решения, чтобы сделать вычисления в больших данных с использованием параллельного подхода и товарно-компьютерные кластеры. В отличие от Hadoop, написанного на Java, структура Google написана на C++. В документе описывается, как будет работать параллельная структура с использованием функций Map и Reduce от функционального программирования на больших наборах данных.

В этом решении было бы два основных этапа - «Карта» и «Уменьшить» - с необязательным шагом между первым и вторым - «Объединить». Сначала будет выполняться шаг «Карта», выполняются вычисления во входной строке «ключ-значение» и генерируются новые значения ключа вывода. Следует иметь в виду, что формат входных пар ключ-значение не обязательно должен совпадать с парами выходных форматов. На шаге «Уменьшение» будут собраны все значения одного и того же ключа, выполняя другие вычисления над ним. В результате на этом последнем этапе будут выводиться пары ключ-значение. Одним из самых тривиальных приложений MapReduce является выполнение подсчетов слов.

Псевдо-код для этого приложения, приведен ниже:

map(String key, String value): 

// key: document name 
// value: document contents 
for each word w in value: 
EmitIntermediate(w, “1”); 

reduce(String key, Iterator values): 

// key: a word 
// values: a list of counts 
int result = 0; 
for each v in values: 
    result += ParseInt(v); 
Emit(AsString(result));

Как можно заметить, карта читает все слова в записи (в этом случае запись может быть линия) и испускает слово как ключ, а число 1 - как значение. Позже, сокращение будет группировать все значения одного и того же ключа. Приведем пример: представьте, что слово «дом» появляется три раза в записи. Вход редуктора будет [дом, [1,1,1]]. В редукторе он суммирует все значения для ключевого дома и дает в качестве выходного значения следующее значение ключа: [house, [3]].

Вот образ того, как это будет выглядеть в рамках MapReduce:

Image from the Original MapReduce Google paper

Как несколько других классических примеров MapReduce приложений, можно сказать:

• Количество доступа URL частота

• График обратного веб-ссылки

• Распределенная Grep

• Термин вектор на хост

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

В документе также описывается, как элементы каркаса должны вести себя в случае сбоев. Эти элементы в документе называются рабочими и мастерами. Они будут разделены на более конкретные элементы в реализациях с открытым исходным кодом. Поскольку Google только описал подход в документе и не выпустил его проприетарное программное обеспечение, для реализации модели было создано множество фреймворков с открытым исходным кодом. В качестве примеров можно указать Hadoop или ограниченную функцию MapReduce в MongoDB.

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

Ключевые понятия:

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

Населенный пункт: Во избежание сетевого трафика инфраструктура пытается убедиться, что все входные данные доступны локально для машин, которые будут выполнять вычисления на них. В исходном описании он использует файловую систему Google (GFS) с коэффициентом репликации, установленным в 3 и размером блока 64 МБ. Это означает, что тот же блок размером 64 МБ (который составляет файл в файловой системе) будет иметь одинаковые копии на трех разных машинах. Мастер знает, где находятся блоки, и попытайтесь запланировать задания на карте на этом компьютере. Если это не удается, мастер пытается выделить машину рядом с репликой входных данных задач (то есть рабочий компьютер в той же стойке машины данных).

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

• Резервные задачи: Иногда работник Map или Reducer может вести себя намного медленнее, чем другие в кластере. Это может привести к суммарному времени обработки и сделать его равным времени обработки этой единственной медленной машины. В оригинальной статье описывается альтернатива «Задачи резервного копирования», которые назначаются мастером, когда операция MapReduce близка к завершению. Это задачи, которые запланированы Мастером выполняемых задач. Таким образом, операция MapReduce завершается, когда основное или резервное копирование завершается.

• Счетчики: Иногда бывает необходимо посчитать события событиями. По этой причине подсчитывается, где создано. Значения счетчиков в каждом рабочем месте периодически распространяются на мастер. Затем мастер суммирует (например, похоже, что агрегаторы Pregel пришли из этого места) значения счетчика успешной карты и уменьшают задачу и возвращают их в код пользователя, когда операция MapReduce завершена. Существует также текущее значение счетчика, доступное в статусе мастера, поэтому человек, наблюдающий за процессом, может отслеживать, как он себя ведет.

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

источник

2014-11-18 11:47:08 Prometheus

4

Если вы знакомы с Python, следуя является самым простым из возможных объяснений MapReduce:

In [2]: data = [1, 2, 3, 4, 5, 6] 
In [3]: mapped_result = map(lambda x: x*2, data) 

In [4]: mapped_result 
Out[4]: [2, 4, 6, 8, 10, 12] 

In [10]: final_result = reduce(lambda x, y: x+y, mapped_result) 

In [11]: final_result 
Out[11]: 42

Посмотрите, как обрабатывался каждый сегмент исходных данных по отдельности, в этом случае, умноженное на 2 (карте часть MapReduce). Основываясь на mapped_result, мы пришли к выводу, что результатом будет 42 (уменьшить часть MapReduce).

Важным результатом этого примера является тот факт, что каждый кусок обработки не зависит от другого фрагмента. Например, если thread_1 отображает [1, 2, 3] и thread_2 отображает [4, 5, 6], конечный результат обоих потоков будет по-прежнему [2, 4, 6, 8, 10, 12], но у нас есть , уменьшенный, время обработки для этого. То же самое можно сказать и о операции сокращения, а также о том, как MapReduce работает в параллельных вычислениях.

источник

2016-02-22 06:05:24 Rafay

13

Это простейшее объяснение MapReduce, которое я нашел.