MapReduce

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

Обзор

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

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

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

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

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

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

Пример

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

// Функция, используемая рабочими нодами на Map-шаге
// для обработки пар ключ-значение из входного потока
void map(String name, String document):
    // Входные данные:
    //   name - название документа
    //   document - содержимое документа
    for each word w in document:
        EmitIntermediate(w, "1");
 
// Функция, используемая рабочими нодами на Reduce-шаге
// для обработки пар ключ-значение, полученных на Map-шаге
void reduce(String word, Iterator partialCounts):
    // Входные данные:
    //   word - слово
    //   partialCounts - список группированных промежуточных результатов. Количество записей в partialCounts и есть 
    //     требуемое значение
    int result = 0;
    for each v in partialCounts:
        result += parseInt(v);
    Emit(AsString(result));

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

Библиотека объединяет все пары с одинаковым ключом и передает их на вход функции reduce, которой остается сложить их, чтобы получить общее количество вхождений данного слова во все документы.

Ссылки

• [research.google.com/archive/mapreduce.html MapReduce: Simplified Data Processing on Large Clusters]
• [citforum.ru/database/articles/mr_vs_dbms-2/ MapReduce и параллельные СУБД: друзья или враги?, citforum.ru]
• [alphaworks.ibm.com/tech/mapreducetools IBM MapReduce Tools for Eclipse]

Отрывок, характеризующий MapReduce

Вскоре после святок Николай объявил матери о своей любви к Соне и о твердом решении жениться на ней. Графиня, давно замечавшая то, что происходило между Соней и Николаем, и ожидавшая этого объяснения, молча выслушала его слова и сказала сыну, что он может жениться на ком хочет; но что ни она, ни отец не дадут ему благословения на такой брак. В первый раз Николай почувствовал, что мать недовольна им, что несмотря на всю свою любовь к нему, она не уступит ему. Она, холодно и не глядя на сына, послала за мужем; и, когда он пришел, графиня хотела коротко и холодно в присутствии Николая сообщить ему в чем дело, но не выдержала: заплакала слезами досады и вышла из комнаты. Старый граф стал нерешительно усовещивать Николая и просить его отказаться от своего намерения. Николай отвечал, что он не может изменить своему слову, и отец, вздохнув и очевидно смущенный, весьма скоро перервал свою речь и пошел к графине. При всех столкновениях с сыном, графа не оставляло сознание своей виноватости перед ним за расстройство дел, и потому он не мог сердиться на сына за отказ жениться на богатой невесте и за выбор бесприданной Сони, – он только при этом случае живее вспоминал то, что, ежели бы дела не были расстроены, нельзя было для Николая желать лучшей жены, чем Соня; и что виновен в расстройстве дел только один он с своим Митенькой и с своими непреодолимыми привычками.
Отец с матерью больше не говорили об этом деле с сыном; но несколько дней после этого, графиня позвала к себе Соню и с жестокостью, которой не ожидали ни та, ни другая, графиня упрекала племянницу в заманивании сына и в неблагодарности. Соня, молча с опущенными глазами, слушала жестокие слова графини и не понимала, чего от нее требуют. Она всем готова была пожертвовать для своих благодетелей. Мысль о самопожертвовании была любимой ее мыслью; но в этом случае она не могла понять, кому и чем ей надо жертвовать. Она не могла не любить графиню и всю семью Ростовых, но и не могла не любить Николая и не знать, что его счастие зависело от этой любви. Она была молчалива и грустна, и не отвечала. Николай не мог, как ему казалось, перенести долее этого положения и пошел объясниться с матерью. Николай то умолял мать простить его и Соню и согласиться на их брак, то угрожал матери тем, что, ежели Соню будут преследовать, то он сейчас же женится на ней тайно.
Графиня с холодностью, которой никогда не видал сын, отвечала ему, что он совершеннолетний, что князь Андрей женится без согласия отца, и что он может то же сделать, но что никогда она не признает эту интригантку своей дочерью.
Взорванный словом интригантка , Николай, возвысив голос, сказал матери, что он никогда не думал, чтобы она заставляла его продавать свои чувства, и что ежели это так, то он последний раз говорит… Но он не успел сказать того решительного слова, которого, судя по выражению его лица, с ужасом ждала мать и которое может быть навсегда бы осталось жестоким воспоминанием между ними. Он не успел договорить, потому что Наташа с бледным и серьезным лицом вошла в комнату от двери, у которой она подслушивала.
– Николинька, ты говоришь пустяки, замолчи, замолчи! Я тебе говорю, замолчи!.. – почти кричала она, чтобы заглушить его голос.
– Мама, голубчик, это совсем не оттого… душечка моя, бедная, – обращалась она к матери, которая, чувствуя себя на краю разрыва, с ужасом смотрела на сына, но, вследствие упрямства и увлечения борьбы, не хотела и не могла сдаться.
– Николинька, я тебе растолкую, ты уйди – вы послушайте, мама голубушка, – говорила она матери.
Слова ее были бессмысленны; но они достигли того результата, к которому она стремилась.
Графиня тяжело захлипав спрятала лицо на груди дочери, а Николай встал, схватился за голову и вышел из комнаты.
Наташа взялась за дело примирения и довела его до того, что Николай получил обещание от матери в том, что Соню не будут притеснять, и сам дал обещание, что он ничего не предпримет тайно от родителей.
С твердым намерением, устроив в полку свои дела, выйти в отставку, приехать и жениться на Соне, Николай, грустный и серьезный, в разладе с родными, но как ему казалось, страстно влюбленный, в начале января уехал в полк.
После отъезда Николая в доме Ростовых стало грустнее чем когда нибудь. Графиня от душевного расстройства сделалась больна.
Соня была печальна и от разлуки с Николаем и еще более от того враждебного тона, с которым не могла не обращаться с ней графиня. Граф более чем когда нибудь был озабочен дурным положением дел, требовавших каких нибудь решительных мер. Необходимо было продать московский дом и подмосковную, а для продажи дома нужно было ехать в Москву. Но здоровье графини заставляло со дня на день откладывать отъезд.