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




glossary (6)

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

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


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

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

Например,

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

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

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


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


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

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

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

Чем меньше я объясняю картину, тем проще она остается.