Google MapReduce

Статья из цикла «Google Platform»

MapReduce – это программная модель, описанная инженерами Google в research paper [2], и ассоциированная с этой программной моделью реализация (фреймворк), позволяющий обрабатывать большие объемы данных распределено.

В простейшем случае в программной модели MapReduce выделяют 2 фазы:

• map(ƒ, c): принимает функцию ƒ и список c. Возвращает выходной список, являющийся результатом применения функции ƒ к каждому элементу входного списка c.
  
• reduce(ƒ, c): принимает функцию ƒ и список c. Возвращает объект, образованный через свертку коллекции c через функцию ƒ.
  

Реализация

В программной реализации модели MapReduce выделяют следующие этапы работы программы:

1. Input read
   Входные данные делятся на блоки данных предопределенного размера (от 16 Мб до 64 Мб) – сплиты (от англ. split). За каждой функцией Map закрепляется определенный сплит.
2. Map
   Каждая функция map() получает на вход список пар «ключ/значение» <k,v>, обрабатывает их и на выходе получает ноль или более пар <k',v'>, являющихся промежуточным результатом. map(k, v) -> [(k', v')] де k' - в общем случае, произвольный ключ, не совпадающий с k. Все операции map() выполняются параллельно и не зависят от результатов работы друг друга. Каждая функция map() получает на вход свой уникальный набор данных, не повторяющийся ни для какой другой функции map().
3. Partition
   Целью этапа partition (разделение) является распределение промежуточных результатов, полученных на этапе map, по reduce-заданиям. Важная цель этапа partition – это балансировка нагрузки. Так некорректно реализованная функция partition может привести к неравномерному распределению данных между reduce-узлами.
4. Reduce
   Функция reduce() вызывается для каждого уникального ключа k' в отсортированном списке значений. reduce(k', [v']) -> [v''] Все операции reduce(), также как и map(), выполняются параллельно и не зависят от результатов работы друг друга.
5. Output write
   Результаты, полученные на этапе reduce, записываются в выходной поток (в общем случае, файловые блоки в GFS). Каждый reduce-узел пишет в собственный выходной поток.

Источник иллюстрации [2]

Достоинства и ограничении программной модели MapReduce, в общем, и фреймворков, реализующих эту программную модель (например, Hadoop MapReduce), в частности, уже довольно подробно описаны в технической литературе, в том числе [15].
Ниже обсудим только основные из них.

Достоинства

Работу по получению входных данных, распараллеливанию работы программы, планированию выполнения, межмашинной коммуникации и обработке отказов выполняет фреймворк MapReduce.

MapReduce проявила себя как прекрасно масштабирующая и крайне простая модель распределенного исполнения приложений. Устойчивость к проваленным заданиям для программной модели MapReduce реализуется довольно просто.

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

Ограничения

• Смешение ответственности для Reducer (сортировка и агрегация данных). Таким образом, Reducer – это все, что «не map»;
• Отсутствие контроля над потоком данных у разработчика (поток данных управляется фреймворком Hadoop MapReduce автоматически);
• Как следствие предыдущего пункта, невозможность простыми средствами организовать взаимодействие между параллельно выполняющимися потоками.
• Применение MapReduce по производительности менее эффективно, чем специализированные решения;
• Эффективность применение MapReduce снижается при малом количество машин в кластере (высоки издержки на взаимодействие, а степень распараллеливания невелика);
• Невозможно предсказать окончание стадии map;
• Этап свертки не начинается до окончания стадии map;
• Как следствие предыдущего пункта, задержки в исполнении любого запущенного map-задания ведут к задержке выполнения задачи целиком.

Влияние на Open source

Влияние работ, опубликованных Google, на первые шаги становления отрасли Big Data сложно переоценить.

Программная модель MapReduce была реализована во многих коммерческих (таких как Greenplum) и некоммерческих программных продуктах (CouchDB, MongoDB). Наиболее известным примером реализации концепций, описанных Google, является фреймворк вычислений Hadoop MapReduce.

Список источников*

• [2] Jeffrey Dean, Sanjay Ghemawat. MapReduce: simplified data processing on large clusters. Proceedings of OSDI, 2004.
• [15] Hadoop Insight и другие статьи ресурса. 0xСode.in: { Big Data, Cloud Computing, HPC } Blog.

* Полный список источников, используемый для подготовки цикла.