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

Переходя полностью к основам для Map и Reduce.

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

предположим, у меня есть список чисел: [1,2,3] и я хочу удвоить каждое число, в этом случае функция до "double every number"-это функция 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  

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

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

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

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

Но если у вас есть доступ к функции reduce, вы можете написать ее следующим образом

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

Теперь немного непонятно, почему есть 2 аргумента (0 и функция с x и y), переданные. Для того чтобы функция reduce была полезной, она должна иметь возможность взять 2 элемента, вычислить что-то и "reduce" что 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 )

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

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

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

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

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

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

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

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

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

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

просто взял это из моих университетских заметок в google paper

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

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

Например,

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

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

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

Карта и 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 (оценка наизнанку), поэтому его называют map reduce .

Давайте возьмем пример из 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

Вокруг этого у вас будет мастер-программа, которая разделит набор документов в "splits", который будет обрабатываться параллельно для фазы карты. Излучаемые значения записываются работником в буфер, специфичный для данного работника. Затем мастер-программа делегирует другим работникам выполнение фазы сокращения, как только будет получено уведомление о том, что буфер готов к обработке.

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

Очень простое, быстрое и "for dummies" введение в MapReduce доступно по адресу: http://www.marcolotz.com/?Р=67

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

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

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

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

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

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

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

В этом решении было бы два основных шага - так называемые Map и Reduce – с дополнительным шагом между первым и вторым – называемым Combine. Шаг Map будет выполняться сначала, выполнять вычисления в паре входной ключ-значение и генерировать новый выходной ключ-значение. Следует иметь в виду, что формат входных пар ключ-значение не обязательно должен совпадать с форматом выходных пар. Шаг уменьшения будет собирать все значения одного и того же ключа, выполняя над ним другие вычисления. В результате на последнем шаге будут выведены пары ключ-значение. Одним из самых тривиальных приложений 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 Как значение. В дальнейшем reduce сгруппирует все значения одного и того же ключа. Давайте приведем пример: представьте себе, что слово " дом " появляется в записи три раза. Вход редуктора был бы [дом, [1,1,1]]. В редукторе он суммирует все значения для ключевого дома и выдает на выходе следующее ключевое значение: [house, [3]].

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

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

* Отсчет частоты доступа URL

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

* Распределенные Grep

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

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

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

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

основных принципа:

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

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

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

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

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

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

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

cat input | map | reduce > output

Если вы знакомы с 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 maps [1, 2, 3] и thread_2 maps [4, 5, 6], конечный результат обоих потоков все равно будет [2, 4, 6, 8, 10, 12] , но мы вдвое сократили время обработки для этого. То же самое можно сказать и о операции reduce, которая является сутью того, как MapReduce работает в параллельных вычислениях.