MapReduce

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 12:47, 6 марта 2017.

MapReduce – это представленная компанией Google модель распределённых вычислений, а также её реализации, используемые для параллельной обработки больших объёмов информации. Работа MapReduce состоит из шагов Map и Reduce, названных аналогично функциям высшего порядка из многих языков программирования, применяемым на этих шагах.
Программы, использующие реализацию MapReduce, автоматически распараллеливаются и исполняются на кластере, состоящем из множества связанных между собой компьютеров. Исполнительная система сама заботится о деталях разбития входных данных на части, планировании исполнения программы на наборе машин, обработке сбоев и управлении необходимым сообщением между машинами. Это позволяет программистам даже без опыта работы с параллельными и распределёнными системами с лёгкостью использовать ресурсы больших распределённых систем.

Цель модели

Входные данные обычно имеют большой объём, и вычисления приходится распределять по сотням или даже тысячам машин, чтобы иметь возможность решить задачу в разумный промежуток времени. Проблемы распараллеливания вычислений, распределения данных и обработки сбоев заставляют отказаться от простой модели вычислений с большим объёмом сложного кода. В Google отреагировали на эту сложность и разработали новую абстракцию, которая позволяет легко производить необходимые вычисления, но скрывает все детали распараллеливания, отказоустойчивости, распределения данных и балансировки нагрузки в своих библиотеках.

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

Принцип работы

Описание связанных функций высшего порядка

Функция map принимает на вход список и некую функцию, затем применяет данную функцию к каждому элементу списка и возвращает новый список. Функция reduce (свёртка) преобразует список к единственному атомарному значению при помощи заданной функции, которой на каждой итерации передаются новый элемент списка и промежуточный результат.
Для обработки данных пользователь библиотеки MapReduce должен только определить две эти функции, а также указать имена входных и выходных файлов и параметры обработки.

Шаг Map

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

Шаг Reduce

На 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));
Детальный обзор работы реализации от Google

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

  1. Сначала библиотека MapReduce в программе пользователя делит входные файлы на M частей, каждая из которых обычно занимает от 16 до 64 мегабайт (этот параметр может задаваться пользователем). Затем она запускает множество копий программы на кластере.
  2. Одна из копий программы (master) особенная, она задаёт работу остальным экземплярам (workers). Всего нужно задать M задач map и R задач reduce. Мастер ищет неактивные рабочие экземпляры и назначает каждой из них одну задачу.
  3. Рабочий экземпляр программы, которому была присвоена задача map, читает содержимое соответствующей части входных данных, разбирает его и передаёт каждый элемент функции пользователя Map. Промежуточные пары «ключ-значение» затем сохраняются в памяти.
  4. Через некоторые промежутки времени сохранённые пары записываются на локальный диск и разбиваются на R областей функцией разделения. Местоположение этих пар на диске передаются обратно мастеру, который отвечает за дальнейшее сообщение этих местоположений рабочим экземплярам.
  5. Когда рабочий экземпляр оповещается о местоположении промежуточных данных, он читает данные с локальных дисков экземпляров, применявших функцию map. Когда все данные прочитаны, они сортируются по ключу и группируются вместе. Если объём данных слишком велик, используется внешняя сортировка.
  6. Рабочий экземпляр проходит по отсортированным промежуточным данным и передаёт функции Reduce каждый уникальный ключ и соответствующий ему список значений. Результат присоединяется к конечному файлу для этой части промежуточных данных.
  7. Когда все задачи map и reduce будут выполнены, вызов MapReduce будет завершён, и произойдёт возврат обратно к пользовательскому коду.

После успешного завершения обработки выходные данные будут доступны в R результирующих файлов (один файл на каждую задачу reduce) с названиями, заданными пользователем. Обычно пользователям не нужно соединять эти R файлов в один – часто бывает, что эти файлы передаются очередному вызову MapReduce уже в качестве входа или обрабатываются в других распределённых приложениях, которым на вход также передаются несколько файлов.

Производительность

Программы, использующие MapReduce, не всегда будут работать быстро. Главным преимуществом этой модели программирования является оптимизированное распределение данных между узлами и небольшое количество кода, которое требуется написать программисту. Однако на практике пользователь программы должен принять во внимание этап распределения данных, в частности, функция разделения данных и количество данных на выходе функции Map могут очень сильно влиять на производительность. Дополнительные модули, такие как функция Combiner, могут помочь уменьшить количество данных, записываемых на диск и передаваемых через сеть.
При написании программы пользователь должен найти и выбрать хороший компромисс между вычислительной и коммуникационной сложностью. Коммуникационная сложность превосходит над вычислительной сложностью, и многие реализации MapReduce были разработаны, чтобы записывать сведения обо всех коммуникациях в распределённое хранение для аварийного восстановления.
Для задач, которые решаются быстро на нераспределённых системах, а входные данные помещаются в оперативную память одного компьютера или небольшого кластера, использование фреймворка MapReduce неэффективно. Так как эти фреймворки разработаны, чтобы иметь возможность восстановления целых узлов кластера во время вычислений, они записывают в распределённое хранилище промежуточные результаты работы. Такая защита от сбоев – очень дорогая процедура и окупается, только когда в вычислениях участвует множество компьютеров, а при выходе одного из них из строя проще всего перезапустить присвоенную ему задачу на другом узле.

Надёжность

Надёжность MapReduce достигается за счёт распределения операции обработки данных по всем узлам сети. Мастер периодически опрашивает каждый рабочий узел для получения статуса или результата работы. Если узел не отвечает в течение установленного времени, мастер начинает считать его аварийным и назначает его работу другому узлу.
В узлах применяются атомарные операции именования выходных файлов для проверки, что в каждый момент не запущены конфликтующие параллельные потоки. Так как операция свёртки плохо распараллеливается, и именно в узле хранится обрабатываемая часть данных, мастер предпринимает попытки запуска свёртки на том же самом или на близлежащих узлах.
Не все реализации MapReduce обязательно обладают высокой надёжностью. Например, в ранних версиях Hadoop примитив мастер-узла NameNode был единой точкой отказа распределённой файловой системы. Более поздние версии Hadoop стали обладать большей активной и пассивной отказоустойчивостью.

Использование

Модель MapReduce применима в широкой области задач, включая распределённый поиск, распределённую сортировку, обращение графа веб-ссылок, обработку статистики логов сети, построение инвертированных индексов, кластеризацию документов, машинное обучение и статистический машинный перевод. Более того, MapReduce была адаптирована под такие вычислительные среды, как многопроцессорные системы, добровольные вычислительные, динамические облачные и мобильные среды.
В компании Google модель MapReduce была использована, чтобы полностью сгенерировать индекс Всемирной паутины, однако вскоре стали применяться другие технологии, например, Percolator, Flume и MillWheel, которые позволяют производить потоковые операции вместо пакетной обработки, что дало возможность реализовать «живой» поиск без перепостроения всего индекса.

Реализации

Реализация MapReduce компанией Google запатентована, однако существует множество других, как коммерческих, так и свободных продуктов, использующих эту модель, таких как Apache Hadoop, Apache CouchDB, MongoDB, MySpace Qizmt и другие.

Преимущества

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

Критика

Отсутствие новых идей

Дэвид ДеВитт и Майкл Стоунбрейкер, компьютерные специалисты, специализирующиеся на параллельных базах данных и распределённых архитектурах, критиковали ширину области задач, для которых может применяться MapReduce. Они назвали интерфейс реализации слишком низкоуровневым и поставили под сомнение заявление разработчиков о том, что он представляет новый этап развития технологий. Одним из аргументов стало сравнение MapReduce с Teradata, системой массовой параллельной обработки, существующей уже больше двух десятилетий, а также с языком CODASYL («программирование на низкоуровневом языке, производящее низкоуровневые манипуляции»). Также отсутствие поддержки схем не позволяет улучшать производительность с помощью присущих обыкновенным базам данных B-деревьев и хэш-разбиения, однако некоторые проблемы позволяют решить такие проекты как Pig (или PigLatin), Sawzall, Apache Hive, YSmart, HBase и BigTable.
Грег Йоргенсен опубликовал статью, опровергающую эти взгляды. Йоргенсен полагает, что анализ ДеВитта и Стоунбрейкера полностью безоснователен, так как MapReduce никогда не разрабатывался и не позиционировался как база данных.
Сначала ДеВитт, а затем и Стоунбрейкер опубликовали в 2009 году детальное исследование производительности реализации MapReduce в Hadoop и подходов СУБД в некоторых аспектах. Они сделали заключение, что реляционные базы данных предлагают настоящие преимущества для многих способов использования данных, особенно для их сложной обработки, или когда данные располагаются в хранилище крупного предприятия, однако использование MapReduce может оказаться проще для начинающих пользователей или несложных задач.
Патент на MapReduce побудил множество споров, так как реализация MapReduce очень похожа на существующие продукты. Например, операции map и reduce могут быть легко реализованы на языке базы данных Oracle PL/SQL, а также неявно предоставляются в таких распределённых базах данных как Clusterpoint XML или MongoDB NoSQL.

Ограниченные возможности фреймворка

Программы MapReduce должны описывать ациклический поток данных: этапы Map и Reduce, управляемые пакетным планировщиком задач, строго следуют один за другим. Эта парадигма делает сложными повторяющиеся запросы данных и налагает ограничения, которые ощутимы в таких областях, как машинное обучение, которое состоит их итеративных алгоритмов, обращающихся к одному и тому же набору данных много раз.

Ссылки