понедельник, 12 декабря 2011 г.

Кратко о MapReduce

Среди всех параллельных алгоритмов, реализации которых легко масштабируются на произвольное количество ядер, MapReduce можно назвать одним из самым свежих. Компания Google представила его в 2004 году. Давайте попробуем разобраться: что это такое и зачем оно нужно.

Что такое MapReduce?

На самом деле MapReduce – это скорее целая схема построения разнообразных алгоритмов для многопоточной обработки больших объёмов данных. Единственное условие: вычисления должны быть представимы в виде 2-ух последовательных операций, называемых Map и Reduce. Но обо всём по порядку.

Основными фигурантами реализации MapReduce являются: master-агент, множество map-агентов и ещё большее множество reduce-агентов. Как не сложно будет заметить: каждый из этих агентов может выполняться независимо от большинства других, то есть параллельно.

На первом шаге master-агент принимает задание, например: список файлов, подлежащих обработке. Затем он создаёт некоторое количество map-агентов – их число определяется объёмом и расположением входных данных, например: по одному map-агенту для каждого файла, поступившего на вход. Каждый агент получает свою порцию входного задания, например: одно имя файла из общего списка. После этого master засыпает в ожидании результатов от агентов.

На втором шаге каждый map-агент должен обработать свою порцию данных некоторым специфичным образом и вернуть результат мастеру в виде списка пар (ключ, значение). В самом простейшем случае в качестве ключей могут выступать слова из обрабатываемого текстового файла. Значение – это любая информация, которая потребуется на следующих шагах. Например, чтобы посчитать, сколько раз каждое слово встречается во всех входных файлах, каждый map-агент для каждого слова из обрабатываемого им файла должен вернуть: (слово, 1). То есть, для такого файла:
Hello, mad, mad, mad, mad world! Hello!
map-агент должен вернуть:
(Hello, 1), (mad, 1), (mad, 1), (mad, 1), (mad, 1) (world, 1), (Hello, 1)

На третьем шаге master принимает ответы от всех map-агентов и группирует их по ключам, собирая значения для одного ключа в единый список. Возвращаясь к нашему примеру, получается следующее:
{Hello, (1, 1)}, {mad, (1, 1, 1, 1)}, {world, (1)}

На практике этот шаг, может быть частично совмещён с предыдущим (и как правило это всегда так и бывает). Дело в том, что map-агенты вместо того, чтобы формировать ответ в виде законченного списка, могут отправлять каждую пару мастеру независимо, например в виде асинхронного сообщения. Таким образом мастер может выполнять группировку данных, параллельно с работающими map-агентами.

На четвёртом шаге для каждого ключа мастер создаёт своего reduce-агента и передаёт ему на обработку ключ и список ассоциированных с ним значений. Reduce-агентам остаётся обработать список значений и вернуть мастеру результат в виде одной пары (ключ, новое значение). То есть, в случае нашего примера мастер создаст 3 reduce-агента и передаст им соответственно:
{Hello, (1, 1)}
{mad, (1, 1, 1, 1)}
{world, (1)}
Чтобы подсчитать количество вхождений каждого слова, reduce-агентам нужно всего лишь сложить все значения из списка и вернуть полученный результат мастеру:
(Hello, 2)
(mad, 4)
(world, 1)

Этот список пар и будет конечным результатом.

А оно надо?

Не сложно заметить, что MapReduce является частным случаем Data Flow подхода, который, как известно, позволяет распараллелить обработку зависимых данных без Lock Convoys и при этом достаточно неплохо масштабируется.

Есть ещё один – не такой очевидный плюс. Представьте себе, что файлов, которые нужно обработать, несколько сотен тысяч. Объём каждого измеряется сотнями мегабайт. Даже просто проиндексировать все слова в этом случае будет проблематично: вам банально не хватит объёма памяти, доступной на вашей машине. Агенты в рамках MapReduce настолько не зависимы друг от друга, что это позволяет легко выносить их работу на другие сервера, тем самым распределяя вычисления не только между потоками, но и между хостами. В этом случае проблемы с недостатком памяти уже не будет.

3 комментария:

Никита комментирует...

хорошее описание.
небольшое уточнение - а какой случай ты имеешь ввиду под "не хватит памяти"?
такое может случиться, если, например, делаем "в лоб" и в память не влезет полный набор уникальных слов (+ счетчик и специфичные для коллекции накладные расходы), но как тогда та же мастер машина сможет скопить все пары вида {Hello, (1, 1)}?

Алексей Коротаев комментирует...

Она будет накапливать результат, одновременно сортируя его по ключу, пока хватит памяти. Зате сбросит текущее состояние в файл и начнет накапливать очередную порцию. В результате получим множество отсортированных файлов с ответами. Выбрать для определенного ключа все ответы из всех ОТСОРТИРОВАННЫХ файлов не составляет труда (предполагаем, что список ответов для одного ключа влезает в память :) ). Далее все очевидно и не так мрачно.
Все попытки оптимизировать аналогичным образом решение "в лоб" (с хэш таблицей) приведут вас в конце концов к тому или иному аналогу MapReduce :).

Никита комментирует...

Под решением 'в лоб' я понимал простое накопление, без сброса на диск. Обрати внимание, что описанное тобой решение применимо и в случае с тупым индексирующим алгоритмом, который точно так же может сортировать, сбрасывать и выгребать в итоге. Обрати также внимание, что в худшем случае, при достаточной уникальности слов, память будет заполняться в основном парами вида (слово, 1), причем в обоих алгоритмах, а в лучшем, при маленьком словаре, оба алгоритма избегут сброса.

Отправить комментарий