Обработка данных, подход «MapReduce»

В 2004 году Google рассказал о модели обработки данных которую они использую. Основана она на том что данные обрабатывает пара простых функций Map и Reduce. Первая их которых выделяет множество пар Ключ/Значений из входящих данных (тоже являющихся парами Ключ/Значение), а вторая производит объединение/группировку этих пар, и, опять же, выдает наружу таки пары, чаще всего в меньшем количестве чем пришло на вход. Дополнительным элементом является распределенная файловая система GoogleFS, благодаря которой обрабатываемый файл, и вся промежуточная информация, становится легко доступной с любого компьютера в кластере.

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

Так же эту идею можно встретить под названием Split/Aggregate. Т.е. суть в том что входные данные (неважно какого размера) разбиваются на отдельные элементы (этап split), к примеру построчно, каждая строка как отдельное значение для обработки. Эти блоки строк раcпределяются по кластеру для обработки, где для каждой строки вызывается функция обработки (map). Результат выполнения опять объединяется (reduce/aggregate) в выходной файл. Если нужно, то данные сохраняются отсортироваными в определенном порядке, к примеру по внешнему ключу.

Область применения

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

Например это очень подходит когда нам нужно обработать стопку csv файлов. Ну или один, но большой. В каждой строке несколько колонок с данными, на основе этого получаем результат, тоже в csv. Так вот обработку такого файла легко распаралелить на нескольких машинах, построчно, или блоками, скажем по 100 строк, равномерно раскидать по серверам, обработать, а потом результирующие строки склеить в выходной файл. Если надо можно еще отсортировать чтобы было в том же порядке что и во входящих данных. Все это требует гораздо меньше ресурсов чем сама обработка данных.

Есть мнение что при обработке данные не стоит перегонять в текстовые файлы, пусть все хранится в БД, и читать оттуда поблочно, тут же складывая полученные результаты. В этом тоже есть свои плюсы и минусы, тут каждый решает сам, в зависимости от задач. Распределенная ФС, кстати, очень хорошо заменяет БД как центральное хранилище данных, а привести в структурный вид, удобный для БД можно уже и отдельным этапом (например отдельной задачей mapreduce). Хотя загрузку и средствами БД можно легко и быстро сделать.

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

Приведу один простой пример, может понятней будет.

mapNumbers («1, 4 and 3»)
Пусть он выделит все цифры в тексте, например регэкспом \d+, не суть важно. В нашем случае выдаст пары {num:1, num:4, num:3}, где num — имя ключа, а 1,4 и 3 — его значения
reduceSum (num[])
На вход придет список пар с одинаковым ключем, в нашем случае ключ num. Пусть метод выполняет суммирование всех цифр для переданного списка пар. Т.е. в нашем случае ему на вход придут те три пары num:#, и он произведет суммирование 1 + 4 + 3, выдав 8

На самом деле функции иногда в сотни раз сложнее, но суть та же.

Реализации MapReduce кластера под java

Apache Hadoop

Apache Hadoop — одна из основных реализаций системы для такой обработки. Поддерживает как MapReduce так и распределенную файловую систему (HDFS). Подпроектом еще идет как минимум реализация BigTable. map/reduce могут быть написаны не обязательно на Java, вполне подойдет все что может запускаться под этой ОС. Кстати, базовой ОС является Unix, хотя как я понимаю под Windows тоже работает, через cygwin.

Недавно Yahoo! сообщил что они успешно используют Hadoop для обработки объемов порядка 300 терабайт на кластере из 10 000 серверов. Из чего можно сделать вывод что для повседневных задач по обработки текущих данных Hadoop хватит с лихвой.

GridGain

GridGain скорее рассчитан(но не ограничивается этим) не на обработку терабайтов данных, а разбиение на кучу задач, не важно каких. Больше подходит название SplitAggregate. Т.е. мы задаем объем задач, GridGain раскидывает это по кластеру, и далее передает нам результат. И здесь уже хоть сразу все через БД делай, хоть используй поверх распределенной ФС (от того же Hadoop даже), не суть важно. Авторы к примеру предлагают так юнит тесты запускать, т.е. разбиваем по методам на кластер, и все они параллельно тестируются. Надо это попробовать, если окажется десяток лишних компов под рукой 🙂

А еще эти товарищи очень не любят писать лишний код сами, а предпочитают интегрировать готовые, зарекомендовавшие себя решения. Что я считаю очень правильно, зачем лишний раз изобретать велосипед? Так вот, я к тому что система получается очень гибкая, красиво написанная, настраиваемая в спринге и интегрируется с кучей прочих около grid решений.

Cloud Computing

В свете последнего расцвета cloud computing, сервисов типа Amazon S3 и EC2 все это становится довольно интересным. Сейчас можно не ждать несколько часов для обработки, когда можно запустить все это на кластере из сотен серверов, получить результат через несколько минут заплатив за аренду этого кластера совсем небольшую сумму.