MapReduce

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Обзор[править | править вики-текст]

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

Работа MapReduce состоит из двух шагов: Map и Reduce.

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

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

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

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

Пример[править | править вики-текст]

Канонический пример приложения, написанного с помощью 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 word in partialCounts:
        result += parseInt(v);
    Emit(AsString(result));

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

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

Реализации[править | править вики-текст]

  • Google реализовал MapReduce на C++ с интерфейсами на языках Python и Java.
  • Greenplum — коммерческая реализация с поддержкой языков Python, Perl, SQL и других[4].
  • GridGain — бесплатная реализация с открытым исходным кодом на языке Java.
  • Проект Apache Hadoop — бесплатная реализация MapReduce с открытым исходным кодом на языке Java.
  • Phoenix[5] — реализация MapReduce на языке Си с использованием разделяемой памяти.
  • MapReduce также реализована Cell Broadband Engine на языке Си[6].
  • MapReduce реализована в графических процессорах Nvidia с использованием CUDA[7].
  • Qt Concurrent[8] — упрощённая версия фреймворка, реализованная средствами Qt на C++, которая используется для распределения задачи между несколькими ядрами одного компьютера.
  • CouchDB использует MapReduce для определения представлений поверх распределённых документов
  • MongoDB позволяет использовать MapReduce для параллельной обработки запросов на нескольких серверах
  • Skynet[9] — реализация с открытым исходным кодом на языке Ruby
  • Disco[10] — реализация, созданная компанией Nokia, её ядро написано на языке Erlang, а приложения для неё можно писать на языке Python.
  • Apache Hive — надстройка с открытым исходным кодом от Facebook, позволяющая комбинировать Hadoop и доступ к данным на SQL-подобном языке.
  • Qizmt[11] — реализация с открытым исходным кодом от MySpace, написанная на C#.
  • DryadLinq[12] — реализация, созданная подразделением Microsoft Research на основе параллельного варианта Linq и Microsoft Dryad[13].
  • YAMR (yet another mapreduce)[14]  — реализация от компании Яндекс для внутреннего использования.

Примечания[править | править вики-текст]

  1. Google spotlights data center inner workings | Tech news blog — CNET News.com
  2. «Our abstraction is inspired by the map and reduce primitives present in Lisp and many other functional languages.» -«MapReduce: Simplified Data Processing on Large Clusters», by Jeffrey Dean and Sanjay Ghemawat; from Google Labs
  3. «Google’s MapReduce Programming Model — Revisited» — paper by Ralf Lammel; from Microsoft
  4. Parallel Programming in the Age of Big Data
  5. The Phoenix System for MapReduce Programming. Проверено 30 марта 2013. Архивировано из первоисточника 5 апреля 2013.
  6. MapReduce on Cell | Free Development software downloads at SourceForge.net. Проверено 30 марта 2013. Архивировано из первоисточника 5 апреля 2013.
  7. Mars
  8. QtDoc 5.0: Qt 5.0 | Documentation | Qt Project. Проверено 30 марта 2013. Архивировано из первоисточника 5 апреля 2013.
  9. space
  10. home | Disco Project. Проверено 30 марта 2013. Архивировано из первоисточника 5 апреля 2013.
  11. MySpace Qizmt - MySpace's Mapreduce Framework. Проверено 9 апреля 2013. Архивировано из первоисточника 18 апреля 2013.
  12. DryadLINQ - Microsoft Research. Проверено 30 марта 2013. Архивировано из первоисточника 5 апреля 2013.
  13. Dryad - Microsoft Research. Проверено 30 марта 2013. Архивировано из первоисточника 5 апреля 2013.
  14. YAMR

Ссылки[править | править вики-текст]