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




glossary (9)

Связано с моим вопросом CouchDB .

Может ли кто-нибудь объяснить MapReduce в терминах, которые могут быть поняты numbnuts?


Answers

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

cat input | map | reduce > output

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

Шаг 2 - это карта. Шаг 3 - Уменьшить.

Например,

  1. Получите время между двумя импульсами на паре счетчиков давления на дороге
  2. Сопоставьте эти времена на скорости, основанные на расстоянии метров
  3. Уменьшите скорость до средней скорости

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

Для сложного, но хорошего описания MapReduce см.: Модель программирования MapReduce от Google - Пересмотренная (PDF) .


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

Публикация некоторых материалов:

Прежде всего, почему был создан MapReduce?

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

Каковы истинные сильные стороны MapReduce?

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

Немного больше на бумаге:

MapReduce изначально упоминался в документе Google (Dean & Ghemawat, 2004 - ссылка здесь) в качестве решения для расчета в Big Data с использованием параллельного подхода и кластеров товаров и компьютеров. В отличие от 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:

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

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

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

• Распределенный Греп

• Термин Vector для каждого узла

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

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

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

Ключевые идеи:

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

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

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

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

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

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


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

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

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

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

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

(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, мы можем теперь найти город с наибольшей плотностью населения.

(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 следующим образом:

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

 =>   (C 5000/7)

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


Если вы знакомы с 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 работает в параллельных вычислениях.


Переход к основам карты и сокращению.

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

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

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

и у меня было бы A = [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  

поэтому после выполнения функции отображения с (x => x * 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 и функция с x и y). Чтобы функция уменьшения была полезной, она должна иметь возможность принимать 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 вы можете работать с базой данных, не зная, как данные хранятся в БД для ее использования, для чего нужен механизм БД.

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

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

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


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

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

Поэтому, если вы думаете об этом, как о выражении SQL

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

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

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

просто выщипывал это из моих заметок в университете на бумаге Google


Давайте возьмем пример из бумаги Google . Цель 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

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

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