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

Вид материала

Документы

Содержание 2. Технологии обработки больших массивов данных на кластерных системах 2.2 Технологии Google 2.3 Платформа Apache Hadoop 3. Опыт обучения рассматриваемым технологиям

Подобный материал:

• Обработка больших научных массивов данных, 11.46kb.
• Роль поисковых технологий в крупных информационных системах и системах документооборота, 205.97kb.
• Рабочей программы дисциплины Структуры и алгоритмы обработки данных по направлению, 21.62kb.
• Понятия о базах данных и системах управления ими. Классификация баз данных. Основные, 222.31kb.
• «Проблематика отображения на электронных картах больших массивов геопространственного, 115.74kb.
• Примерная рабочая программа по дисциплине: базы данных, 104.62kb.
• Использование программных массивов для обработки большого числа однотипных данных (на, 94.99kb.
• Методы анализа данных, 17.8kb.
• Курс лекций Преподаватель Бондаренко А. А. Рыбинск 2001, 568.31kb.
• Представление о программе, 1104.33kb.

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

О.В. Сухорослов
Центр Грид-технологий и распределенных вычислений ИСА РАН
os@isa.ru

1. Введение

В современном мире все большую роль играют технологии, обеспечивающие эффективную обработку больших массивов данных. Связано это с наблюдаемым с конца прошлого века лавинообразным ростом информации. Современные задачи и приложения, связанные с анализом данных, предъявляют особые требования к вычислительным ресурсам, значительно превышающие возможности отдельных компьютеров. Для достижения приемлемого времени работы подобным приложениям часто необходимы ресурсы уровня кластеров с сотнями и тысячами узлов. В последние годы сформировались новые технологии, позволяющие организовать распределенное хранение и параллельную обработку больших объемов данных в крупномасштабных кластерных системах [1].

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

В данной статье кратко рассматриваются современные технологии обработки больших массивов данных на кластерных системах и описывается опыт обучения этим технологиям в рамках спецкурса, читаемого автором в Школе Яндекса [2]. В отличие от западных университетов, рассматриваемые технологии пока не представлены в учебных программах российских вузов. Статья призвана привлечь внимание к данной тематике и восполнить указанный пробел.

2. Технологии обработки больших массивов данных на кластерных системах

2.1 Модель вычислений MapReduce

MapReduce [3] – модель вычислений для пакетной обработки больших объемов данных, разработанная и используемая в компании Google для широкого круга приложений. Модель MapReduce отличается простотой и удобством использования, скрывая от пользователя детали организации вычислений на кластерной системе. Пользователю достаточно описать процедуру обработки данных в виде двух функций – map и reduce, после чего система автоматически распределяет вычисления по кластеру, обрабатывает отказы машин, балансирует нагрузку и координирует взаимодействия между машинами.

В рамках MapReduce вычисления принимают на вход и производят на выходе данные, состоящие из множества пар “ключ-значение”. Обозначим входные данные как list(k1,v1), а выходные – как list(k2,v2). Пользователь описывает вычисления в виде двух функций - map и reduce. Функция map(k1,v1)→list(k2,v2) применяется к каждой паре входных данных и возвращает набор промежуточных пар. Далее реализация MapReduce группирует промежуточные значения v2, связанные с одним ключом k2, и передает эти значения функции reduce. Функция reduce(k2,list(v2))→list(v2) преобразует промежуточные значения в окончательный набор значений для данного ключа. Как правило, это одно агрегированное значение, например, сумма.

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

2.2 Технологии Google

Используемая в Google реализация модели вычислений MapReduce является закрытой разработкой. Тем не менее, основные принципы данной реализации хорошо известны по публикациям в научных изданиях (например, [3]) и докладам разработчиков на конференциях.

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

Эффективная реализация MapReduce невозможна без эффективной организации хранения данных на кластерной системе. Для этой цели в Google применяется распределенная файловая система Google File System (GFS) [4].Как и любая распределенная файловая система, GFS ориентирована на обеспечение высокой производительности, масштабируемости, надежности и доступности. Отличия архитектуры GFS от других распределенных файловых систем обусловлены спецификой приложений и вычислительной инфраструктуры Google. Отметим главные особенности распределенной файловой системы GFS: высокая отказоустойчивость, ориентация на хранение файлов большого размера, оптимизация под операции записи в конец файла, эффективное использование сетевых ресурсов и оптимизация под высокую агрегированную пропускную способность, нестандартный интерфейс файловой системы, ослабленная модель целостности данных.

Запуском MapReduce-заданий на кластере управляет планировщик, который отслеживает состояние машин и подбирает группу машин для выполнения задания. Вызовы функции map распределяются между несколькими машинами путем автоматического разбиения входных данных, хранящихся в GFS, на M частей. Полученные порции данных могут обрабатываться параллельно различными машинами. Вызовы reduce распределяются путем разбиения пространства промежуточных ключей на R частей, определяемых с помощью заданной функции разбиения. Каждый из reduce-процессов загружает со всех map-процессов порции обработанных данных с соответствующими значениями промежуточных ключей, производит сортировку и объединение этих данных, после чего выполняет функцию reduce. Результаты вычислений записываются в виде файлов в GFS. В случае если заданные пользователем функции map и reduce являются детерминированными функциями своих входных значений, распределенная реализация MapReduce гарантирует получение такого же результата, что и при последовательном выполнении программы. В ходе вычислений система автоматически обрабатывает отказы map- и reduce-процессов, неизбежно возникающих в кластерных системах из большого количества ненадежных серверов.

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

2.3 Платформа Apache Hadoop

Платформа распределенных вычислений Hadoop [5] разрабатывается на принципах open source в рамках организации Apache Software Foundation. Платформа ориентирована на поддержку обработки больших объемов данных на кластерных системах и заимствует многие идеи у закрытых технологий Google, таких как MapReduce, GFS и BigTable, фактически предоставляя их открытые реализации.

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

Hadoop MapReduce является открытой реализацией модели вычислений MapReduce. Система реализована на языке Java. Для создания приложений используется интерфейс прикладного программирования на Java. Функции map и reduce описываются в виде классов, реализующих стандартные интерфейсы. Hadoop также позволяет указать в качестве реализаций map и reduce произвольные программы. Взаимодействие между Hadoop и программой осуществляется при помощи стандартных потоков ввода-вывода. Отметим, что, в отличие от Google MapReduce, реализация функции reduce может возвращать пары с произвольными ключами, не совпадающими с переданным на вход функции промежуточным ключом.

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

3. Опыт обучения рассматриваемым технологиям

В ходе преподавания в 2008-2009 годах спецкурса “Параллельные и распределенные вычисления” в Школе Яндекса автором был накоплен опыт обучения рассматриваемым технологиям. Главной целью курса является выработка практических навыков использования современных технологий параллельных и распределенных вычислений, в первую очередь при решении задач, связанных с обработкой и анализом данных. Рассматриваемые технологии занимают центральное место в курсе, включая четыре лекции, два семинара и два домашних задания. При подготовке лекций и практических заданий использовались материалы курсов по данной тематике, читаемых в западных университетах [6, 7].

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

Вторая лекция посвящена знакомству с платформой Hadoop. Описывается архитектура платформы и ее основные элементы – распределенная файловая система HDFS и реализация модели MapReduce. Рассматриваются интерфейс прикладного программирования и общие принципы реализации приложений для Hadoop на языке Java на примере задачи подсчета частоты встречаемости слов в тексте. Описывается процесс установки Hadoop на локальной машине, с последующей компиляцией и запуском приложения. Рассматриваются принципы реализации функций map и reduce на языках, отличных от Java. Даются инструкции по работе с данными и запуску приложений на учебном кластере, а также рекомендации по выбору значений параметров запуска заданий и отладке приложений.

В третьей лекции рассматриваются примеры использования MapReduce в задачах обработки и анализа данных. Первая часть лекции посвящена реализации процедуры кластерного анализа. Описывается общая постановка задачи, приводятся примеры приложений и существующих методов кластерного анализа. Подробно описывается алгоритм canopy clustering, позволяющий снизить сложность вычислений при анализе данных большого объема и размерности. Рассматривается реализация алгоритма canopy clustering в рамках модели MapReduce на примере задачи кластеризации фильмов из набора данных Netflix Prize. Вторая часть лекции посвящена реализации алгоритмов на графах. Рассматриваются принципы реализации обхода и эффективного представления графов в MapReduce, описывается реализация поиска кратчайших путей в графе. В качестве основного примера алгоритма на графах рассматривается задача вычисления значений PageRank, - рейтинга Web-страницы, определяемого через количество ведущих на нее ссылок и рейтинги ссылающихся страниц. Описывается лежащая в основе PageRank математическая модель и последовательный алгоритм вычисления значений PageRank. Рассматриваются принципы распараллеливания алгоритма и его реализация в рамках MapReduce.

Четвертая лекция посвящена описанию других технологий, входящих в состав платформы Hadoop или основанных на ней. Рассматривается распределенная система хранения данных HBase, особенности ее архитектуры, отличия от реляционных СУБД, области применения, а также приводятся примеры других подобных систем, получивших широкое распространение в последнее время. Описывается высокоуровневый язык Pig Latin, реализованный поверх модели MapReduce и призванный упростить описание процедур обработки данных. Рассматриваются открытая реализация поисковой машины Nutch и использование модели MapReduce в работе Nutch. Описываются библиотека Mahout, содержащая масштабируемые реализации алгоритмов машинного обучения на базе Hadoop, и библиотека Hama, содержащая реализации матричных вычислений.

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

Первое задание, предназначенное для выработки практических навыков работы с большими наборами данных на платформе Hadoop, включает две задачи:

1. Определить 100 наиболее часто встречающихся слов в русской (только русские слова) и английской версиях Википедии.

2. Построить инвертированный индекс для русской и английской версий Википедии вида “слово [tab] статья{частота слова}...”. Статьи должны быть отсортированы в порядке убывания частоты встречаемости слова

В качестве исходных данных для выполнения домашнего задания использовались тексты статей русской (около миллиона статей, 3 Гб данных) и английской (около 8 млн. статей, 20 Гб данных) версий Википедии. Отчет по домашнему заданию включает исходный код программ, параметры запуска заданий, время выполнения заданий и пути к результатам в файловой системе HDFS.

Второе задание призвано закрепить и развить практические навыки работы с платформой Hadoop и позволяет студентам проявить их интересы. В рамках задания предлагается реализовать любую нетривиальную процедуру обработки и анализа данных на учебном кластере. Поскольку для эффективного использования мощности кластера необходим достаточно большой объем исходных данных, который не всегда есть в распоряжении студентов, то предлагается два готовых набора данных: тексты статей из Википедии (см. первое задание) и обучающая выборка Netflix Prize (более 100 млн. оценок 17700 фильмов, около 2 Гб данных). Примерами выбранных студентами задач являются вычисление значений PageRank для статей Википедии и кластеризация фильмов из выборки Netflix.

Для реализации MapReduce-программ разрешается использовать любой распространенный язык программирования. Однако на практике большинство студентов использует базовый для платформы Hadoop язык Java или язык Python, для которого существует удобный интерфейс программирования Dumbo.

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

4. Заключение

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

Литература

[1] Сухорослов О.В. Новые технологии распределенного хранения и обработки больших массивов данных. // Всероссийский конкурсный отбор обзорно-аналитических статей по приоритетному направлению "Информационно-телекоммуникационные системы", 2008. - 40 с.

du.ru/lib/index.php?id_res=5652

[2] Школа Яндекса. andex.ru/academic/school/

[3] Dean, J. and Ghemawat, S. MapReduce: Simplified data processing on large clusters. In Proceedings of Operating Systems Design and Implementation (OSDI). San Francisco, CA. 137-150, 2004.

[4] Ghemawat, S., Gobioff, H., and Leung, S.-T. The Google file system. In 19th Symposium on Operating Systems Principles, Lake George, NY, pp. 29-43, 2003.

[5] Apache Hadoop. ache.org/

[6] Учебные материалы по распределенным вычислениям, Google Code University. le.com/edu/parallel/index.php

[7] Курс “Problem Solving on Large Scale Clusters”, Университет штата Вашингтон. shington.edu/education/courses/490h/