Какая компания создала технологию mapreduce

Национальная библиотека им. Н. Э. Баумана
Bauman National Library

Персональные инструменты

MapReduce

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

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

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

Библиотеки использующие модель MapReduce написаны на многих языках программирования. Популярная реализация с открытым исходным кодом является частью Apache Hadoop. Название MapReduce изначально было запатентованной технологией Google, но с тех пор было обобщено. К 2014 году в Google больше не использовали MapReduce в качестве своей основной модели обработки больших данных [Источник 1] , а разработка Apache Mahout привела к более функциональным и менее диско-ориентированным механизмам, которые поддерживают возможности MapReduce. [Источник 2]

Содержание

Цель модели

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

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

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

Чаще всего фреймворки реализующие модель MapReduce осуществляют три операции (шага):

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

1. Shuffle: рабочие узлы перераспределяют данные на основе ключей (созданных функцией Map) так, что все данные принадлежащие одному ключу лежат на одном рабочем узле.

1. Reduce: рабочие узлы обрабатывают каждую группу результатов по порядку следования ключей. Главный узел получает промежуточные ответы от рабочих узлов и передаёт их на свободные узлы для выполнения следующего шага. Получившийся после прохождения всех необходимых шагов результат – это решение задачи, которая изначально формулировалась.

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

Функция map — принимает на вход список и некую функцию, затем применяет данную функцию к каждому элементу списка и возвращает новый список.

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

Для обработки данных пользователь библиотеки MapReduce должен только определить две эти функции, а также указать имена входных и выходных файлов и параметры обработки.

Пример алгоритма

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

В этом коде на Map-шаге каждый документ разбивается на слова, и возвращаются пары, где ключом является само слово, а значением – «1». Если в документе одно и то же слово встречается несколько раз, то в результате предварительной обработки этого документа будет столько же этих пар, сколько раз встретилось это слово.
Библиотека объединяет все пары с одинаковым ключом и передает их на вход функции reduce, которой остается сложить их, чтобы получить общее количество вхождений данного слова во все документы. Вызовы операции Map распределены между множеством машин с помощью автоматического деления входных данных на набор из M <\displaystyle M>частей. Входные части могут обрабатываться параллельно несколькими машинами. Вызовы операции Reduce распределены разделением промежуточного пространства ключей на R <\displaystyle R>частей с помощью функции разделения (например, h a s h ( k e y ) m o d R <\displaystyle hash(key)modR>). Количество частей 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. [Источник 3] Они назвали интерфейс реализации слишком низкоуровневым и поставили под сомнение заявление разработчиков о том, что он представляет новый этап развития технологий. [Источник 4] Одним из аргументов стало сравнение MapReduce с Teradata, системой массовой параллельной обработки, существующей уже больше двух десятилетий, а также с языком CODASYL («программирование на низкоуровневом языке, производящее низкоуровневые манипуляции»). [Источник 5] Также отсутствие поддержки схем не позволяет улучшать производительность с помощью присущих обыкновенным базам данных B-деревьев и хэш-разбиения, однако некоторые проблемы позволяют решить такие проекты как Pig, Sawzall, Apache Hive, YSmart, HBase и BigTable.

Грег Йоргенсен опубликовал статью, опровергающую эти взгляды. [Источник 6] Йоргенсен полагает, что анализ ДеВитта и Стоунбрейкера полностью безоснователен, так как MapReduce никогда не разрабатывался и не позиционировался как база данных.

Сначала ДеВитт, а затем и Стоунбрейкер опубликовали в 2009 году детальное исследование производительности реализации MapReduce в Hadoop и подходов СУБД в некоторых аспектах. Они сделали заключение, что реляционные базы данных предлагают настоящие преимущества для многих способов использования данных, особенно для их сложной обработки, или когда данные располагаются в хранилище крупного предприятия, однако использование MapReduce может оказаться проще для начинающих пользователей или несложных задач.

Патент на MapReduce побудил множество споров, так как реализация MapReduce очень похожа на существующие продукты. Например, операции map и reduce могут быть легко реализованы на языке базы данных Oracle PL/SQL, а также неявно предоставляются в таких распределённых базах данных как Clusterpoint XML или MongoDB NoSQL.

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

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

Источник