MapReduce — модельраспределённых вычислений, представленная компаниейGoogle, используемая дляпараллельных вычислений над очень большими, вплоть до несколькихпетабайт^[1], наборами данных в компьютерныхкластерах.

MapReduce — этофреймворк для вычисления некоторых наборов распределенных задач с использованием большого количества компьютеров (называемых «нодами»), образующихкластер.

Работа MapReduce состоит из двух шагов: Map и Reduce, названных так по аналогии с одноименнымифункциями высшего порядка,map иreduce.

На Map-шаге происходит предварительная обработка входных данных. Для этого один из компьютеров (называемый главным узлом — master node) получает входные данные задачи, разделяет их на части и передает другим компьютерам (рабочим узлам — worker node) для предварительной обработки.

На Reduce-шаге происходитсвёртка предварительно обработанных данных. Главный узел получает ответы от рабочих узлов и на их основе формирует результат — решение задачи, которая изначально формулировалась.

Преимущество MapReduce заключается в том, что он позволяет распределенно производить операции предварительной обработки и свертки. Операции предварительной обработки работают независимо друг от друга и могут производиться параллельно (хотя на практике это ограничено источником входных данных и/или количеством используемых процессоров). Аналогично, множество рабочих узлов может осуществлять свертку — для этого необходимо только чтобы все результаты предварительной обработки с одним конкретным значением ключа обрабатывались одним рабочим узлом в один момент времени. Хотя этот процесс может быть менее эффективным по сравнению с более последовательными алгоритмами, MapReduce может быть применен к большим объёмам данных, которые могут обрабатываться большим количеством серверов. Так, MapReduce может быть использован для сортировки петабайта данных, что займет всего лишь несколько часов. Параллелизм также дает некоторые возможности восстановления после частичных сбоев серверов: если в рабочем узле, производящем операцию предварительной обработки или свертки, возникает сбой, то его работа может быть передана другому рабочему узлу (при условии, что входные данные для проводимой операции доступны).

Фреймворк в большой степени основан на функциях map иreduce, широко используемых вфункциональном программировании^[2], хотя фактически семантика фреймворка отличается от прототипа^[3].

Канонический пример приложения, написанного с помощью MapReduce, — это процесс, подсчитывающий, сколько раз различные слова встречаются в наборе документов:

// Функция, используемая рабочими нодами на Map-шаге// для обработки пар ключ-значение из входного потокаvoidmap(Stringname,Stringdocument):// Входные данные://   name - название документа//   document - содержимое документаforeachwordindocument:EmitIntermediate(word,"1");// Функция, используемая рабочими нодами на Reduce-шаге// для обработки пар ключ-значение, полученных на Map-шагеvoidreduce(IteratorpartialCounts):// Входные данные://   partialCounts - список группированных промежуточных результатов. Количество записей в partialCounts и есть//     требуемое значениеintresult=0;foreachvinpartialCounts:result+=parseInt(v);Emit(AsString(result));

В этом коде на Map-шаге каждый документ разбивается на слова, и возвращаются пары, где ключом является само слово, а значением — «1». Если в документе одно и то же слово встречается несколько раз, то в результате предварительной обработки этого документа будет столько же этих пар, сколько раз встретилось это слово. Сформированные пары отправляются на дальнейшую обработку, система группирует их по ключу (в данном случае — ключом является само слово) и распределяет по множеству процессоров. Наборы объектов с одинаковым ключом в группе попадают на вход функции reduce, которая перерабатывает поток данных, сокращая его объёмы. В данном примере функция reduce просто складывает вхождения данного слова по всему потоку, и результат — только одна сумма — отправляется дальше в виде выходных данных.

• MapReduce: Simplified Data Processing on Large Clusters
• MapReduce и параллельные СУБД: друзья или враги?, citforum.ru
• IBM MapReduce Tools for Eclipse

• Google
• Функциональное программирование
• Параллельные вычисления

• Страницы, использующие устаревший тег source
• Википедия:Cite web (не указан язык)