Технология Google MapReduce и ее реализация с открытым исходным кодом Hadoop

Владимир Орлов, Киев, Украина, vorl@softwarium.net

Проблема обработки большого количества данных

С каждым годом растут объемы обрабатываемых данных. По оценкам IDC, данных, хранимых в электронном виде, в 2011 году будет 1.8 зеттабайт ¹. Откуда берется эта цифра? Ситуацию проясняют следующие факты:

FaceBook на своих серверах хранит примерно 10 млрд. картинок;
Фондовая биржа Нью-Йорка ежедневно генерирует около 1 Тб новых данных;
В 2008 году Google обрабатывал ежемесячно 400 ПБ.

В то же время за последние 20 лет быстродействие винчестеров не увеличилось настолько, чтобы справляться с их объемами: в 1990 году данные с винчестера объемом 1370 Мб и скоростью доступа 4,4 Мб/с можно было прочесть за 2,5 минуты, а у современных винчестеров скорость доступа около 100 Мб/с при среднем объеме в 1 Тб. Получается, что все данные с жесткого диска можно прочесть за 2,5 часа ². Но если мы сможем обрабатывать 1 Тб параллельно, читая его, скажем, со ста машин одновременно, то на обработку данных нам потребуется около 2 минут.

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

MapReduce от Google

Технология MapReduce была создана Google для сканирования и обработки большого количества страниц из Интернет, и применяется для решения различных задач в рамках самой компании. Идея технологии проста: вы определяете функцию map, которая обрабатывает пары ключ/значение, генерирует промежуточные пары ключ/значение, которые далее агрегируются и обрабатываются в функции reduce ³.

Как оказалось, кроме сканирования и обработки страниц из Интернет, парадигма MapReduce очень хорошо подходит для других распространенных задач – в частности, это распределенный «grep» ³, классификация книг, писем, файлов, различные алгоритмы интеллектуального анализа данных (data-mining) ⁴.

После того, как Google опубликовала описание технологии MapReduce ³, стали появляться ее реализации в таких проектах как GridGain, GreenPlum, Twister. Но наибольшую известность из них приобрел проект Hadoop.

Слоненок и его зоопарк

Проект Hadoop был начат в компании Yahoo в 2004 г. Большую роль в его создании сыграл Doug Cutting — создатель технологии поиска с открытым исходным кодом. Потребность в Hadoop возникла во время написания им проекта Nutch — системы, позволяющей сканировать и индексировать веб-страницы из Интернет.

Символом проекта является желтый слоненок (любимая игрушка дочки разработчика). Кроме самого Hadoop в его зоопарк входят такие проекты как Pig, Hive, Hbase, HDFS, ZooKeeper. Все они являются в какой-то мере open source копией проектов Google ⁵.

HDFS (аналог GFS от Google) – это масштабируемая распределенная файловая система, предназначенная для быстрого чтения данных большого объема. Как и Hadoop, она может быть развернута на обычных машинах.

Hive и Pig (аналоги Google Sawzall) – проекты, созданные чтобы облегчить процесс обработки большого количества данных на кластерах Hadoop.

Hbase (аналог Big Table) – построенная на HDFS база данных, в которой все данные хранятся в колонках. Потенциально в этой базе данных можно держать многотерабайтные объемы данных.

ZooKeeper (аналог Chubby) – система распределенной синхронизации приложений. С помощью этой системы можно легко реализовать такие задачи, как выбор лидера, обнаружение сервисов, распределенную блокировку.

Чтобы написать минимальную MapReduce-программу, потребуется создать 2 класса, наследуемых от org.apache.hadoop.mapred.MapReduceBase. Один класс должен реализовать интерфейс org.apache.hadoop.mapred.Mapper (с вашей map-функцией), а второй класс – интерфейс org.apache.hadoop.mapred.Reducer (с вашей reduce-функцией). Далее, вы должны сконфигурировать MapReduce-задание, создав экземпляр класса org.apache.hadoop.mapred.JobConf и выставив с его помощью параметры:

путь к входному файлу на HDFS;
путь к директории, где будет лежать результат;
формат входных и выходных данных;
ваш класс с map-функцией;
ваш класс с reduce-функцией.

После этого можно запустить задание на выполнение методом JobConf.runJob(). Hadoop сделает за вас остальное, а именно – копирование jar-файла с заданием, разбиение входных данных на части, назначение каждому рабочему узлу своей части на обработку, координация между узлами, сортировка и перетасовка промежуточных пар ключ/значение, перезапуск задач в случае ошибок, извещение клиента об окончании обработки.

Роль Hadoop в современных облачных вычислениях

Проект получил признание не только в Yahoo, но и за пределами этой компании. Сейчас Hadoop используют Facebook, LinkedIn, Amazon, Twitter и др., а Amazon был создан специальный сервис в облаке, называемый Elastic Map Reduce, который построен на версии Hadoop 0.18 и работает вместо HDFS с их собственной файловой системой S3.

Больше узнать о проекте можно по адресу http://hadoop.apache.org/. Также много полезной информации можно найти на сайте компании, занимающейся обучением технологии и поддержкой кластеров Hadoop: http://www.cloudera.com/

Источники
¹ Gantz et al. 2008. The Diverse and Exploding Digital Universe
² White T. 2009. Hadoop: The Definitive Guide. O’Reilly Media, Inc., 1005 Gravenstein Highway North, Sebastopol, CA 95472
³ Dean J., Ghemawat S. 2004. MapReduce: Simplied Data Processing on Large Clusters
⁴ Cloudera Inc. 2009. MapReduce Algorythms
⁵ Cloudera Inc. 2009. Hadoop Ecosystem Tour