Что такое парадигма MapReduce

Туториал: параллельные вычисления больших данных с MapReduce

Метод MapReduce представляет собой технику, которая используется для обработки огромного количества данных (до нескольких петабайт). Существует много реализаций MapReduce, в том числе известный Apache Hadoop. Здесь я не буду говорить о реализациях MapReduce. Я попытаюсь представить концепцию как можно более интуитивно понятным способом, приведу реальные примеры.

Перевод статьи A Beginners Introduction into MapReduce, автор — Igor Shulga. Ссылка на оригинал — в подвале статьи.

Проблема

Часто в Data Science мы имеем дело с таким с огромным количеством данных, что многие методы их обработки не работают или невозможны в реализации. Огромное количество данных — это хорошо, это очень хорошо, и мы хотим использовать как можно больше.

Давайте начнем с простой задачи. Вам дан список строк, и вам нужно вернуть самую длинную строку. Это довольно легко сделать в Python:

Мы перебираем строки по очереди, вычисляем длину и сохраняем самую длинную строку, пока не закончим.

Для небольших списков это работает довольно быстро:

Даже для списков с более чем 3 элементами это работает довольно хорошо, здесь мы попробуем с 3000 элементами:

Но что если мы попробуем 300 миллионов элементов?

Это уже проблема. В большинстве приложений время ответа в 20 секунд не приемлемо. Один из способов сократить время вычислений — купить гораздо более быстрый процессор. Масштабирование вашей системы путем внедрения более качественного и быстрого оборудования называется «Вертикальное масштабирование». Это, конечно, не будет работать вечно. Во-первых, не так просто найти процессор, который работает в 10 раз быстрее. Во-вторых, наши данные, вероятно, будут увеличиваться, и мы не хотим менять наш процессор каждый раз, когда ощущаем что наш код недостаточно быстрый. Такое решение не масштабируемое. Вместо этого мы можем выполнить «Горизонтальное масштабирование»: мы разработаем наш код так, чтобы он мог работать параллельно, и он станет намного быстрее, когда мы добавим больше процессоров.

Разбиение кода

Нам нужно разбить наш код на более мелкие компоненты и решить, как мы можем распараллелить вычисления. Идея такова: 1) разбить наши данные на множество блоков, 2) выполнить функцию find_longest_string для каждого блока параллельно и 3) найти самую длинную строку среди выходных данных всех блоков.

Наш код функции имеет очень узкое применение, поэтому вместо использования функции find_longest_string мы разработаем более общую структуру, которая поможет нам выполнять различные параллельные вычисления для больших данных.

В нашем коде мы делаем две основные вещи: вычисляем len строки и сравниваем ее с самой длинной до сих пор строкой. Мы разбиваем наш код на два этапа: 1) вычисляем len всех строк и 2) выбираем значение max.

(Рассчитываем длину строк, а затем сворачиваем их вместе функцией zip. Это намного быстрее, чем делать это в одной строке и дублировать список строк)

В этом состоянии код работает на самом деле медленнее, чем раньше, потому что вместо того, чтобы выполнить один проход для всех наших строк, мы делаем это 2 раза, сначала для вычисления len, а затем для поиска max значения. Почему это хорошо для нас? потому что теперь наш «шаг 2» получает в качестве входных данных не исходный список строк, а некоторые предварительно обработанные данные. Это позволяет нам выполнить второй шаг, используя выходные данные другого «второго шага»! Мы лучше поймем это немного позже, сначала давайте дадим имя этим шагам. Мы будем называть первый шаг «mapper», потому что он отображает какое-то одно значение в какое-то другое значение, а второй шаг мы будем называть «reductor», потому что он получает список значений и выдает одно (в большинстве случаев) значение. Вот две вспомогательные функции для mapper и reductor:

mapper — это просто функция len. Он получает строку и возвращает ее длину. reducer получает два кортежа в качестве входных данных и возвращает один с наибольшей длиной.

Давайте перепишем наш код, используя map и reduce, в Python даже есть встроенные функции для этого (в Python 3 мы должны импортировать его из functools):

Код делает то же самое, но выглядит немного изящнее, а главное — он более универсален и поможет нам распараллелить вычисления. Давайте посмотрим на это более внимательно:

Шаг 1 отображает наш список строк в список кортежей с помощью функции mapper (здесь я снова использую zip, чтобы избежать дублирования строк).

Шаг 2 использует функцию reducer, переходит по кортежам с первого шага и применяет их один за другим. Результатом является кортеж с максимальной длиной.

Теперь давайте разберем наш ввод по частям и поймем, как он работает, прежде чем проводить какое-либо распараллеливание (мы будем использовать chunkify, который разбивает большой список на куски одинакового размера):

На первом шаге мы просматриваем фрагменты и находим самую длинную строку в этом фрагменте, используя mapper, и уменьшаем. На втором шаге мы берем выходные данные первого шага, которые представляют собой список уменьшенных значений, и выполняем окончательное уменьшение, чтобы получить самую длинную строку. Мы используем number_of_chuncks=36, потому что это количество CPU на моей машине.

Распараллеливание кода

Мы почти готовы запустить наш код параллельно. Единственное, что мы можем сделать лучше, это добавить первый шаг reduce в mapper. Мы делаем это потому, что хотим разбить наш код на два простых шага, а первый reduce работает на одном фрагменте, и мы хотим его распараллелить. Вот как это выглядит:

Теперь у нас есть красивый двухшаговый код. Если мы выполним это как есть, мы получим то же время вычисления, но теперь мы можем распараллелить шаг 1, используя модуль multiprocessing, просто используя функцию pool.map вместо обычной функции map.

Мы видим, что он работает в 2 раза быстрее! Это не слишком значительное улучшение, но зато мы теперь знаем, что можем улучшить его, увеличив число процессов! Мы можем даже сделать это на более чем одной машине, если наши данные очень большие, мы можем использовать десятки или даже тысячи машин, чтобы сделать наше время вычислений настолько коротким (почти), насколько мы хотим.

Архитектура MapReduce

Наша архитектура построена с использованием двух функций: map и reduce. Каждый вычислительный блок отображает входные данные и выполняет начальное уменьшение. Наконец, некоторое централизованное устройство выполняет окончательное уменьшение и возвращает вывод. Это выглядит так:

Эта архитектура имеет два важных преимущества:

1. 1. Она масштабируема: если у нас есть больше данных, единственное, что нам нужно сделать, это добавить больше единиц обработки. Изменение кода не требуется!

1. Она универсальна: эта архитектура поддерживает широкий спектр задач, мы можем изменить функционал наших map и reduce так, как захотим.

Важно отметить, что в большинстве случаев наши данные будут очень большими и статичными. Это означает, что разбиение на фрагменты каждый раз неэффективно и фактически излишне. Таким образом, в большинстве приложений в реальной жизни мы будем хранить наши данные в виде кусков (или фрагментов) с самого начала. Затем мы сможем выполнять различные вычисления, используя технику MapReduce.

Пример с подсчетом слов

Теперь давайте посмотрим на более интересный пример: Подсчет слов!

Скажем, у нас очень большой набор новостных статей, и мы хотим найти топ-10 используемых слов, не включая стоп-слова. Как бы мы это сделали? Во-первых, давайте получим данные:

Для этого поста я увеличил данные в 10 раз, чтобы мы могли увидеть разницу.

Для каждого текста в наборе данных мы хотим: токенизировать его, очистить, удалить стоп-слова и, наконец, посчитать слова:

Давайте посмотрим, сколько времени это займет без MapReduce:

Теперь давайте напишем наш mapper, reducer и chunk_mapper:

mapper получает текст, разбивает его на лексемы, очищает их и фильтрует стоп-слова и слова, не несущие смысла. В конце концов, он подсчитывает слова внутри этого единого текста документа. Функция reducer получает 2 счетчика и объединяет их. chunk_mapper получает кусок и делает на нем MapReduce. Теперь давайте запустим фреймворк, который мы создали, и посмотрим:

Это в 10 раз быстрее! Здесь мы смогли ощутимо использовать наши вычислительные возможности, потому что задача намного сложнее и требует большего.

Подводя итог, можно сказать, что MapReduce — это интересный и важный метод для обработки больших данных. Он может справиться с огромным количеством задач, включая подсчет, поиск, supervised и unsupervised обучение и многое другое. Сегодня существует множество реализаций и инструментов, которые могут сделать нашу жизнь более комфортной, но я думаю, что очень важно понимать основы.

MapReduce

MapReduce – это модель распределённых вычислений от компании Google, используемая в технологиях Big Data для параллельных вычислений над очень большими (до нескольких петабайт) наборами данных в компьютерных кластерах, и фреймворк для вычисления распределенных задач на узлах (node) кластера [1].

Назначение и области применения

MapReduce можно по праву назвать главной технологией Big Data, т.к. она изначально ориентирована на параллельные вычисления в распределенных кластерах. Суть MapReduce состоит в разделении информационного массива на части, параллельной обработки каждой части на отдельном узле и финального объединения всех результатов.

Программы, использующие MapReduce, автоматически распараллеливаются и исполняются на распределенных узлах кластера, при этом исполнительная система сама заботится о деталях реализации (разбиение входных данных на части, разделение задач по узлам кластера, обработка сбоев и сообщение между распределенными компьютерами). Благодаря этому программисты могут легко и эффективно использовать ресурсы распределённых Big Data систем.

Технология практически универсальна: она может использоваться для индексации веб-контента, подсчета слов в большом файле, счётчиков частоты обращений к заданному адресу, вычисления объём всех веб-страниц с каждого URL-адреса конкретного хост-узла, создания списка всех адресов с необходимыми данными и прочих задач обработки огромных массивов распределенной информации. Также к областям применения MapReduce относится распределённый поиск и сортировка данных, обращение графа веб-ссылок, обработка статистики логов сети, построение инвертированных индексов, кластеризация документов, машинное обучение и статистический машинный перевод. Также MapReduce адаптирована под многопроцессорные системы, добровольные вычислительные, динамические облачные и мобильные среды [2].

История развития главной технологии Big Data

Авторами этой вычислительной модели считаются сотрудники Google Джеффри Дин (Jeffrey Dean) и Санджай Гемават (Sanjay Ghemawat), взявшие за основу две процедуры функционального программирования: map, применяющая нужную функцию к каждому элементу списка, и reduce, объединяющая результаты работы map [3]. В процессе вычисления множество входных пар ключ/значение преобразуется в множество выходных пар ключ/значение [4].

Изначально название MapReduce было запатентовано корпорацией Google, но по мере развития технологий Big Data стало общим понятием мира больших данных. Сегодня множество различных коммерческих, так и свободных продуктов, использующих эту модель распределенных вычислений: Apache Hadoop, Apache CouchDB, MongoDB, MySpace Qizmt и прочие Big Data фреймворки и библиотеки, написанные на разных языках программирования [2]. Среди других наиболее известных реализаций MapReduce стоит отметить следующие [5]:

• Greenplum — коммерческая реализация с поддержкой языков Python, Perl, SQL и пр.;
• GridGain — бесплатная реализация с открытым исходным кодом на языке Java;
• Phoenix — реализация на языке С с использованием разделяемой памяти;
• MapReduce реализована в графических процессорах NVIDIA с использованием CUDA;
• Qt Concurrent — упрощённая версия фреймворка, реализованная на C++, для распределения задачи между несколькими ядрами одного компьютера;
• CouchDB использует MapReduce для определения представлений поверх распределённых документов;
• Skynet — реализация с открытым исходным кодом на языке Ruby;
• Disco — реализация от компании Nokia, ядро которой написано на языке Erlang, а приложения можно разрабатывать на Python;
• Hive framework — надстройка с открытым исходным кодом от Facebook, позволяющая комбинировать подход MapReduce и доступ к данным на SQL-подобном языке;
• Qizmt — реализация с открытым исходным кодом от MySpace, написанная на C#;
• DryadLINQ — реализация от Microsoft Research на основе PLINQ и Dryad.

MapReduce — это разделение, параллельная обработка и свертка распределенных результатов

Как устроен MapReduce: принцип работы

Прежде всего, еще раз поясним смысл основополагающих функций вычислительной модели [2]:

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

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

Сама вычислительная модель состоит из 3-хшаговой комбинации вышеприведенных функций [2]:

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

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

О преимуществах и недостатках вычислительной модели MapReduce, а также возможных альтернативах читайте в нашей отдельной статье.

Blogerator.org

Эксклюзивные ИТ-новости, обзоры и интервью

Объясняем суть MapReduce “на пальцах”

Уж целую неделю мы постепенно разжевываем NoSQL/NewSQL, но вопросы не убывают (как я ожидал), но только нарастают.

Разделавшись намедни с основами команд memcached, сейчас я хочу попытаться максимально просто, насколько это возможно для меня, ответить на частый и важный вопрос — что такое MapReduce.

Что такое MapReduce?

Это типовой подход, алгоритм, ну или паттерн, тут уж как кто назовет, параллельной обработки больших объемов сырых данных, например — результатов работы краулеров или логов веб-запросов.

Вообще по статистике, до 80% задач могут свободно и очень выгодно маппиться на MapReduce, и именно MapReduce драйвит сейчас в NoSQL.

Основы основ

Итак, типичная реализация этого алгоритма получает на вход 3 аргумента: исходную коллекцию, Map-функцию, Reduce-функцию, — и возвращает новую коллекцию данных после обработки.

Алгоритм состоит из нескольких шагов. В качестве первого шага выполняется Map-функция к каждому элементу исходной коллекции. Map вернет ноль либо создаст экземпляры Key/Value объектов.

То есть, можно сказать, что обязанность Map-функции конвертировать элементы исходной коллекции в ноль или несколько экземпляров Key/Value объектов. Это продемонстрировано ниже на изображении:

Следующим шагом, алгоритм отсортирует все пары Key/Value и создаст новые экземпляры объектов, где все значения ( value ) будут сгруппированы по ключу.

Последним шагом выполнится функция Reduce — для каждого сгруппированного экземпляра Key/Value объекта

В заключении, функция Reduce вернет новый экземпляр объекта, который будет включен в результирующую коллекцию.

Пример-реализация

В качестве примера реализуем очень простую и наглядную имплементацию этого алгоритма на C#. Мой пример считает количество гласных построчно в наборе строк.

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

Довесок: Хронология развития технологии MapReduce, также для всех жаждущих серьёзных подробностей могу порекомендовать очень хороший курс на эту тему «MapReduce course at the University of Maryland for Spring 2013», выложенный полностью в онлайн.

8 комментариев

Это перевод? Не надо из каждого зарубежного термина делать кальку. Что это за “драйвит”, “имплементация”? Можно тогда вообще не переводить. А если не перевод, то у автора есть проблемы с терминологическим запасом, как в этом случае верить экспертизе такого автора?

Ничего себе – “на пальцах”. Огромные листинги – это на пальцах? :)))

Руслан, знаете куда ити ?

Отличная статья, всё понятно. Спасибо!

На пальцах это когда каждая запятая объясняется,а тут чисто перевод статьи с иностранного сайта,тот кто сталкивается с mapReduce впервые ничего не поймет.

Чёт вы тупенькие. Я работая тестировщиком, наконец-то понял, что такое Map/Reduce и как он примерно работает.

А тот, кто жалуется на иностранные слова, просто мало работает в компаниях с английской документацией и мало пишет код. Имплементация, Верификация, Баги, Фичи, Дескрипшион, Инвестигировать, Митинг, Драйвить, Хэндлить, маппить, хардкодить и т.д. Все эти слова только упрощают жизнь, а если не знаете их значения, то это ваши проблемы, учитесь работать, а не ныть!

Черти не русские, ботать по фене вы можете в своей узкой компании, а публиковать статьи на нормальном, русском языке. Для упрощения жизни особо умным вообще можно просто мычать )

Более менее понятно как работает, но не повредит ещё рассказать, чем этот подход так хорош, и какую пользу (по сравнению с альтернативами) он приносит.

Источники:

http://neurohive.io/ru/tutorial/mapreduce/
http://www.bigdataschool.ru/wiki/mapreduce
http://blogerator.org/page/objasnjaem-sut-mapreduce-na-palcah-nosql-highload