1. Последовательное и параллельное программирование

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

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

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

1.1 Основы параллельного программирования

Первый шаг в построении параллельной программы — определить набор задач, которые могут быть запущены одновременно и/или порции данных, которые могут быть обработаны одновременно. Иногда это просто невозможно, например, если наша задача — вычислить член последовательности Фибоначчи. В рекуррентром виде записи этой последовательности формула члена последовательности с номером n выглядит так:

Fn = Fn-1 + Fn-2

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

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

Если один и тот же процесс (обработка) требуется для каждого элемента массива без завистимости от всех остальных, то это — идеальная задача для параллельного программирования. Самая распространенная техника реализации называется параллельного программирования MASTER/WORKER (Мастер/Рабочий)

Мастер:

1. Инициализирует массив и разбивает его согласно количеству свободных рабочих

2. Посылает каждому рабочему его субмассив

3. Получает результат от каждого рабочего

Рабочий:

1. Получает субмассив от мастера

2. Выполняет вычисления над субмассивом

3. Возвращает результаты мастеру

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

Статический балансировщик нагрузки присваивает процессы процессорам в момент запуска и не берет во внимание текущую загрузку сети. Динамические алгоритмы более гибкие, хотя и требуют большего количество вычислений, они берут во внимание загрузку сети перед тем, как раздавать задачи процессорам.

В качестве примера техники мастер/рабочий можно привести один из способов аппроксимации (то есть приблизительного вычисления) числа пи.

Для начала впишем круг в квадрат.

pi = Ac / r²

As = 4r²

r² = As / 4

pi = 4 * Ac / As

As — плозадь квадрата, Ac — площадь круга.

Несложно выразить pi: 4* Ac/As

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

1. Сгенерируем произвольные точки внутри квадрата

2. Считаем количество точек, которые попали одновременно в круг и в квадрат

3. r= количество точек в круге, деленное на количество точек в квадрате

4. pi=4*r

Легко видеть, что чем больше точек мы возьмем, тем точнее реультат получим. Если мы будем генерировать, скажем, миллион точек на одном процессоре, это может занять очнь много времени. Однако заметим, что все 4 шага можно выполнять параллельно на многих машинах. А значит мы сможем получить результат намного быстрее.

[Приложение 1]

2. Модель программирования MapReduce

Теперь, когда мы разобрали несколько базовых примеров параллельного программирования, мы можем посмотреть на модель программирования MapReduce. Эта модель берет свое происхождение от функций map и reduce из функционального языка типа лисп.

В лиспе функция map берет на входе функцию и последовательность значений, затем она применяет функцию к каждому значению в последовательности. Функция reduce объединяет все элементы последовательности, используя бинарный оператор. Например, она может использовать «+», чтобы сложить все элементы в последовательности.

MapReduce был вдохновлен этими концепциями. Его разработали в компании Google в качестве механизма для обработки большого объема данных, например, для сохраненных из сети документов или логов веб-запросов. Эти данные настолько большие, что их нужно распределить между тысячами машин для того, чтобы их можно было обработать в адекватное время. Такое распределение предполагает параллельное вычисление, так как над всеми данными проводятся одни и те же вычисления. MapReduce — абстракция, которая позволяет инженерам компании Google выполнять простые вычисления, при этом оставляя за кадром детали распараллеливания задач, распределения данных, распределения нагрузки и отказоустойчивости.

Функция Map, написанная пользователем, берет на вход часть данных и производит набор промежуточных пар key/value. [Приложение 2]

Затем библиотека MapReduce группирует все промежуточные значения, ассоциированные с одним ключом, и передает их в функцию reduce. [Приложение 3]

Функция reduce, также написанная пользователем, берет на вход обработанные данные и производит над ними операции с целью уменьшения количества значений (чаще всего это суммирование, но может быть и простая сортировка). [Приложение 4]

Представьте себе проблему подсчета количества вхождений каждого слова внутри большого количества документов.

map(String key, String value):

// key: document name

// value: document contents

for each word w in value:

EmitIntermediate(w, "1");

reduce(String key, Iterator values):

// key: a word

// values: a list of counts

int result = 0;

for each v in values:

result += ParseInt(v);

Emit(AsString(result));

Функция map «выпуливает» каждое слово и ассоциированное с ним количество вхождений (в данном примере 1). Функция reduce складывает вместе все подсчитанные значения для каждого слова.

2.1 Как работает MapReduce

Функция map выполняется на множестве компьютеров. Входные данные делятся на m частей (шардов). Затем эти шарды могут быть обработаны параллельно на разных машинах. И только после того, как все задачи на map будут выполнены, начнет выполняться reduce.

Вызовы функции reduce также распределены посредством разбиения промежуточных ключей на R частей с помощью функции разбиения (например, hash(key) mod R). Количество честей R и функция разбиения также заданы пользователем.

Когда пользовательская программа вызывает функцию MapReduce, происходит следующее:

1. Библиотека MapReduce сначала делит входящие файлы на m шардов, обычно от 16 до 64 мб на кусок (особенности файловой системы Google), а потом запускает нужное количество копий программы на кластер из машин.

2. Одна из копий программы — специальная (мастер), остальные — воркеры, которым мастер назначает работу. Есть m задач на map и R задач на reduce. Мастер выбирает свободных рабочих и присваивает каждому из них задау на map или задачу на reduce.

3. Рабочий, которму назначили задачу на map, считывает содержимое соотвествущего шарда; затем он делит шард на на пары key/value (например, название документа и его содержимое, это нужно, чтобы инициализировать данные) и передает каждую пару в функцию map, заданную пользователем. Промежуточные пары key/value, которые получаются в результате выполнения пользовательской функции map, складываются в память (буфферизуются).

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

5. Когда воркер, который занимается reduce, мастер говорит о местоположении данных, он их считывает с локальных дисков map воркеров и сортирует их по промежуточному ключу таким образом, чтобы все вхождения одного и того же ключа былли сгрупированы вместе (если количество промежуточных данных слишком больше, используется внешняя сортировка).

6. Затем reduce-воркер проходит по всем отсортированным промежуточным данным и для каждого уникального ключа, которых он встречает, он передает ключ и соответсвующий сет промежуточных значений в пользовательскую функцию reduce. Результат работы функции reduce затем добавляется в конец результирующего файла для этой части reduce.

7. Когда все задачи на map и reduce были выполнены, мастер будит пользовательску программу, в этот момент мы возвращаемся к той точке, с которой был вызван MapReduce.

[Приложение 5]

2.2 Отказоустойчивасть

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

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

2.3 Примеры применения MapReduce

Вот несколько простых примеров интересных программ, которые могут быть с легкостью выражены через MapReduce:

1. Распределенный Grep: функция map выпуливает строку, если она удовлеворяет указанному регулярному выражению. Фнкция reduce в данном случае порсто копирует предоставленные данные на выход (ничего не делает).

2. Подсччет количества запросов к веб-странице: функция map обрабатывает логи веб-запросов и в качестве промежуточных ключей выпуливает пару url,1 функция reduce складывает вместе все значения для одного url и выдает на выходе key/value: url и общее количество запросов

3. Индексирование: функция map, обрабатывая каждый дкумент, выпуливает набор пар слово/id документа, функция reduce принимает все эти пары по заданному слову, сортирует список всех id и выдает слово и список id.

2.4 Оптимизация

Некоторые задачи можно оптимизировать с помощью функций-комбинаторов. Комбинатор — функция, которая работает так же, как reduce, но в пределах только одной функции map, чтобы облегчить задачу reduce. Например, если мы считаем количество слов в документе, функция map считается для каждого документа и от каждого возвращает пару «слово/1». Комбинатор посчитает количество одинаковых слов для одного документа, и reduce получит не m единичик, а пару «слово/m».

Однако комбинаторы хороши не для всех задач. Например, если мы хотим для каждого слова получить все id документов, где содержится это слово, то функция map на одном документе вернет пару «слово/id», где все id буду одинаковыми и разумеется, мы не сможем применить к этому результату комбинатор.

Выводы

1. MapReduce доказал на практике в Google, что он удобен в использовании;

2. MapReduce сильно упрощает крупномасштабные вычисления для инженеров компании Google, но также может быть удобен и для решения ряда других задач. Сейчас MapReduce ипользуется в таких компаниях как Mail.ru, Microsoft и во многих других;

3. MapReduce позволяет сфокусироваться на основной задаче, а всю «грязную» работу отдать библиотеке.

Список использованных источников

1. Свободная энциклопения «Википедия», ru.wikipedia.org

2. Статьи с сайта информационных технологий «Хабрахабр», http://habrahabr.ru/

3. Введение в параллельное программирование и MapReduce, http://code.google.com/edu/parallel/mapreduce-tutorial.html

4. Лекция о MapReduce в видео-формате, http://www.youtube.com/watch?v=-vD6PUdf3Js&feature=youtube_gdata_player

Приложение 1

Приложение 2

Приложение 3

Приложение 4

Приложение 5