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

Question

Относится к моему CouchDB вопросу.

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

Answer 1

Переход к основам Map и Reduce.

---

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

предположим, у меня есть список чисел: [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].

---

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

Поиск суммы или средних значений - все это примеры функции снижения. Например, если у вас есть список чисел, скажем, [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 вы можете работать с базой данных без необходимости знать, как данные хранятся в БД для ее использования, вот для чего нужен механизм БД.

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

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

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

Answer 2

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

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

Так что если вы думаете об этом как о SQL-выражении

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

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

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

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

Answer 3

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

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

Например,

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

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

Сложное, но хорошее описание MapReduce см. В Google MapReduce Programming Model - Revisited (PDF) .

Answer 4

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

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

(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))

Тогда мы можем написать наш код СНИЖЕНИЯ КАРТЫ как:

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

 =>   (C 5000/7)

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

Answer 5

Давайте возьмем пример из 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. Переданные значения записываются рабочим в буфер, определенный для рабочего. Затем главная программа делегирует другим работникам выполнение фазы сокращения, как только она получает уведомление о готовности буфера к обработке.

Вывод каждого рабочего (будь то работник Map или Reduce) фактически является файлом, хранящимся в распределенной файловой системе (GFS для Google) или в распределенной базе данных для CouchDB.

Answer 6

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

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

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

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

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

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

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

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

В этом решении будет два основных шага - называемых Map и Reduce - с необязательным шагом между первым и вторым - называемых Combine. Сначала выполняется шаг 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

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

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

• Term Vector на хост

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

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

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

Основные понятия:

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

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

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

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

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

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

Answer 7

Если вы знакомы с 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 (часть map *1005* MapReduce). Основываясь на mapped_result, мы пришли к выводу, что результат будет 42 ( уменьшить часть MapReduce).

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

Answer 8

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

cat input | map | reduce > output