MapReduce

Материал из Seo Wiki - Поисковая Оптимизация и Программирование

Перейти к: навигация, поиск

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

Содержание

Обзор

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

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

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

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

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

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

Пример

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

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

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

На Reduce-шаге происходит объединение пар с одинаковым значением ключа (слова) и передача этих пар для свертки, где суммируются вхождения слов в отдельные документы и получается искомый результат — общее количество вхождений каждого слова во все документы.

Имеющиеся реализации

  • Google реализовал MapReduce на C++ с интерфейсами на языках Python и Java.
  • Greenplum — это коммерческая реализация MapReduce с поддержкой языков Python, Perl, SQL и других.[4]
  • GridGain — это бесплатная реализация MapReduce с открытыми исходными кодами на языке Java.
  • Проект Apache Hadoop — это бесплатная реализация MapReduce с открытыми исходными кодами на языке Java.
  • Phoenix [1] — это реализация MapReduce на языке С с использованием разделяемой памяти.
  • MapReduce также реализована Cell Broadband Engine на языке C. [2]
  • MapReduce реализована в графических процессорах NVIDIA с использованием CUDA [3].
  • Qt Concurrent — это упрощенная версия фреймворка, реализованная на C++, которая используется для распределения задачи между несколькими ядрами одного компьютера.
  • CouchDB использует MapReduce для определения представлений поверх распределенных документов
  • Skynet — это реализация с открытыми исходныим кодами на языке Ruby
  • Disco — это реализация MapReduce, созданная компанией Nokia. Ее ядро написано на языке Erlang и приложения для нее можно писать на языке Python.
  • Hive framework — реализация с открытыми исходными кодами от Facebook.
  • Qizmt — это реализация MapReduce с открытым исходным кодом от MySpace, написанная на C#.

См. также

Примечания

  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

Ссылки

cs:MapReduce

de:MapReduce en:MapReduce es:MapReduce fr:MapReduce ja:MapReduce ko:MapReduce nl:MapReduce zh:MapReduce

Источник — «http://www.sbup.com/wiki/MapReduce»
Личные инструменты

Served in 0.288 secs.