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


3 Answers

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

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

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

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

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

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

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

Question

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

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




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 (оценка наизнанку), поэтому она называется уменьшением карты .




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




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




Related