MAPREDUCE — ПАРАДИГМА РАСПРЕДЕЛЕННЫХ ВЫЧИСЛЕНИЙ ДЛЯ БОЛЬШИХ ДАННЫХ

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

С помощью MapReduce вычисления пишутся в виде функций предварительной обработки и консолидации, манипулирующих парами “ключ-значение”. Эти примитивы достаточно выразительны для реализации практически любой функции, а каркас MapReduce выполняет их над главным массивом данных распределенным и надежным способом. Благодаря подобным свойствам MapReduce оказывается не только превосходной парадигмой для предварительных вычислений, требующихся на уровне пакетной обработки, но и для низкоуровневой абстракции, когда выражение вычислений может потребовать немалых трудов.

Каноническим примером применения MapReduce служит подсчет слов. С этой целью берется массив текстовых данных и определяется, сколько раз каждое слово встречается в тексте. Функция предварительной обработки в MapReduce выполняется один раз на каждую строку текста и порождает любое количество пар “ключ-значение”. При подсчете слов функция предварительной обработки порождает пару “ключ-значение” для каждого слова в тексте, устанавливая ключ равным найденному слову, а значение — единице, как показано ниже. А затем MapReduce организует результат, возвращаемый функцией предварительной обработки таким образом, чтобы все значения по одному и тому же ключу были сгруппированы вместе.

function wordCountMap(sentence) {

     for (word in sentence.split(" ")) {

                 emit(word, 1)

     }

}

Функция консолидации данных берет весь список значений по одному и тому же общему ключу и порождает новые пары “ключ-значение” в качестве окончательного результата. При подсчете слов в качестве входных данных функции консолидации служит список значений, равных 1 для каждого слова, а сама функция просто суммирует эти значения, чтобы произвести подсчет этого слова, как показано ниже.

function wordCountReduce(word, values) {

     sum = 0

     for (val in values) {

                 sum += val

     }

     emit(word, sum)

}

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

Масштабируемость

Эффективность парадигмы MapReduce объясняется тем, что написанные на ней программы внутренне масштабируемы. Так, программа, обрабатывающая 10 гигабайт данных, может обработать и 10 петабайт данных.

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

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

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

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

По завершении задач предварительной обработки каждая порожденная пара “ключ-значение” направляется задаче консолидации, отвечающей за обработку значений по данному ключу. Следовательно, каждая задача предварительной обработки распределяет свои выходные данные по всем задачам консолидации. Такой перенос промежуточных пар “ключ-значение” называется перетасовкой.

Как только задача консолидации получит все пары “ключ-значение” из каждой задачи предварительной обработки, она отсортирует их по ключу. В итоге все значения буду сгруппированы вместе по заданному ключу. Затем по каждому ключу и группе его значений вызывается функция консолидации.

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

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

Список литературы:

1. Марц, Натан, Уорен, Джеймс. Большие данные: принципы и практика построения масштабируемых систем обработки данных в реальном времени.: Пер. с англ. — М.: ООО “И.Д.Вильямс”, 2016 – 368 с.