М. В. Гладкий Белорусский государственный технологический университет модель распределенных вычислений mapreduce
 Скачать 0.73 Mb.
|
|
194 Òðóäû ÁÃÒÓ, 2016, № 6, ñ. 194–198 Òðóäû ÁÃÒÓ № 6 2016 УДК 519.6 М. В. Гладкий Белорусский государственный технологический университет МОДЕЛЬ РАСПРЕДЕЛЕННЫХ ВЫЧИСЛЕНИЙ MAPREDUCE Предмет исследования данной статьи – алгоритмы и методы эффективной обработки и ана- лиза данных большого объема, основанных на использовании парадигмы распределенных вы- числений в компьютерных кластерах MapReduce. Рассмотрена общая схема работы, область применения и принципы параллельной реализа- ции MapReduce вычислений на кластерных системах. Выявлены основные стадии обработки информации в исследуемой модели: Map (предварительная обработка данных), Combine (час- тичная агрегация данных по ключу), Shuffle (разделение данных на секции и сортировка проме- жуточных пар по ключу), Reduce (свертка обработанных данных). Разработана классификация алгоритмов и методов решения задач, использующих описан- ную модель распределенных вычислений. В качестве классификаторов выступают стадии обра- ботки MapReduce, а также возможные сценарии прикладного использования решаемых задач. Данная классификация позволила разбить совокупность решаемых задач на четыре категории: MapReduce (задачи, для решения которых применяются функции Map и Reduce), MapOnly (зада- чи, для решения которых можно обойтись только стадией Map), цепочки MapReduce (задачи, для решения которых необходимо последовательно использовать несколько моделей MapReduce) и ReduceJoin (задачи, в которых необходимо объединять содержимое нескольких документов по ключу). Для каждой из групп приводятся различные примеры и сценарии. Ключевые слова: распределенные вычисления, компьютерный кластер, MapReduce, Com- bine, Shuffle. M. V. Gladkiy Belarusian State Technological University THE MODEL OF DISTRIBUTED COMPUTING MAPREDUCE The subject of the research in this article is algorithms and methods of effective processing and analysis data. It is based on the paradigm of distributed computing in computer clusters MapReduce. The General scheme of work, scope and principles of parallel implementations of the MapReduce computing on cluster systems have been considered. The main stages of the information processing identified in the study model: Map (data preprocessing), Combine (partial data aggregation key), Shuf- fle (time-dividing the data into sections and sorting the intermediate pairs by key), Reduce (compress the processed data). Algorithms classification and methods for task solution, which use the model of distributed compu- ting has been developed. The stages of MapReduce processing act as classifiers, and possible scenarios of application of tasks. This classification allowed us to divide the aggregate a set of tasks into four ca- tegories: MapReduce (tasks for which apply Map and Reduce functions), MapOnly (for which you can get by with just a stage Map), chaining MapReduce (tasks, for the solution of which is necessary to consistently apply multiple models MapReduce) and ReduceJoin (tasks that you want to merge the con- tents of multiple documents by key). Various examples and scenarios are given for each group. Key words: distributed computing, cluster computing, MapReduce, Combine, Shuffle. Введение. В современном мире все боль- шую роль играют технологии, обеспечивающие эффективную обработку больших массивов данных. Мировой объем информации увеличи- вается более чем в 2 раза каждые два года, что говорит о лавинообразном росте общего коли- чества данных. Современные программные средства предъявляют серьезные требования к вычислительным ресурсам, значительно пре- вышающие возможности отдельных компьюте- ров. Особое значение уделяется алгоритмам и методам, применяемым для обработки и анали- за данных с использованием компьютерных кластеров, состоящих из сотен или тысяч узлов. Однако реализация процедур обработки дан- ных на кластерных системах сопряжена с ре- шением таких задач, как разбиение и распреде- ление данных между процессорами, баланси- ровка нагрузки, обработка отказов, сбор и агрегация промежуточных результатов [1]. Кроме того, на данном этапе развития средств распараллеливания вычислений отсут- ствует детальное описание алгоритмов, мето- дов и подходов распределенной обработки дан- ных, что связано с бизнес-моделью многих компаний. Данная область исследования требует Ì. Â. Ãëàäêèé 195 Òðóäû ÁÃÒÓ № 6 2016 детального изучения: необходимо рассмотреть и исследовать парадигму эффективной обра- ботки и анализа данных большого объема Map- Reduce; классифицировать совокупность ре- шаемых задач в исследуемой области по раз- личным критериям. Основная часть. Одним из самых эффек- тивных методов обработки больших объемов данных в распределенных средах является па- радигма MapReduce, предложенная компанией Google в начале 2000-х для сканирования и об- работки большого количества страниц из сети Интернет. Впервые такая парадигма была реа- лизована в составе распределенной файловой системы GFS (Google File System) и в высоко- производительной нереляционной базе данных Big Table [1]. Данная модель отличается простотой и удобством использования, скрывает от пользо- вателя детали организации вычислений на кла- стерной системе. Преимущество MapReduce за- ключается в том, что она позволяет распреде- ленно выполнять операции предварительной обработки и свертки. Операции предваритель- ной обработки работают независимо друг от друга и могут производиться параллельно. Аналогичным образом множество рабочих уз- лов осуществляют операцию свертки – для это- го необходимо, чтобы все результаты предва- рительной обработки с одним конкретным зна- чением ключа обрабатывались одним рабочим узлом в один момент времени [2]. Параллелизм также дает некоторые воз- можности восстановления после частичных сбоев серверов: если в рабочем узле, произво- дящем операцию предварительной обработки или свертки, возникает сбой, то его работа мо- жет быть передана другому рабочему узлу (при условии, что входные данные для проводимой операции доступны). Пользователю достаточно описать процедуру обработки данных в виде нескольких функций, после чего система авто- матически распределяет вычисления по класте- ру, обрабатывает отказы машин, балансирует нагрузку и координирует взаимодействия меж- ду машинами. В рамках концепции MapReduce предпола- гается, что данные организованы в виде неко- торого набора упорядоченных записей, а их об- работка происходит в три стадии: Map, Shuffle и Reduce (рис. 1). Стадия Map. На этой стадии выполняется предварительная обработка и фильтрация дан- ных при помощи функции Map, которую опре- деляет пользователь. Принцип работы подобен операции Map в функциональных языках про- граммирования – пользовательская функция применяется к каждой входной записи и воз- вращает множество пар ключ – значение. Все запуски функции работают независимо и могут работать параллельно, в том числе на разных машинах кластера. Функция Map, как правило, применяется на той же машине, на которой хранятся данные. Это позволяет снизить пере- дачу данных по сети (принцип локальности данных) [3]. Рис. 1. Стадии работы парадигмы MapReduce Стадия Shuffle. На этой стадии вывод функции Map разбивается на специальные сек- ции (корзины). Каждая корзина соответствует одному ключу вывода стадии Map. Кроме того, она принимает на вход совокупность записей, соответствующих данному ключу, и общее ко- личество Reduce-задач, а возвращаемым значе- нием является номер задачи, в которой обра- батывалась каждая запись. Каждая секция формируется на основе функции хеширования, которая вызывается для каждого ключа и за- висит от определенных критериев, например от номера задачи. Для ускорения процесса об- работки информации очень часто на данной стадии применяют алгоритмы параллельной сортировки. В первую очередь они требуются в тех случаях, когда разные атомарные обра- ботчики возвращают наборы с одинаковыми ключами, при этом правила сортировки на этой фазе могут быть заданы программно и использовать какие-либо особенности внут- ренней структуры ключей разделения (partition key) [4]. Стадия Reduce. Каждая корзина со значе- ниями, сформированная на стадии Shuffle, по- падает на вход функции Reduce. Эта функция вычисляет финальный результат для каждой отдельной секции. Все запуски Reduce, как и функция Map, работают независимо и могут работать параллельно, в том числе на разных машинах кластера. Для некоторых видов обра- ботки свертка не требуется, и каркас возвраща- ет в этом случае набор отсортированных пар, полученных базовыми обработчиками. 196 Ìîäåëü ðàñïðåäåëåííûõ âû÷èñëåíèé MapReduce Òðóäû ÁÃÒÓ № 6 2016 Парадигма MapReduce достаточна гибкая и может легко адаптироваться под разные типы задач, включая в себя дополнительные стадии обработки информации. Например, стадия Combine применяется в тех случаях, когда в ре- зультатах функции Map содержится значитель- ное число повторяющихся значений промежу- точного ключа, а определенная пользователем задача Reduce является коммутативной и ассо- циативной. В таких случаях необходимо осу- ществить частичную агрегацию данных до их передачи по сети. Функция Combine выполня- ется на той же машине, что и задача Map. Ре- зультаты функции Combine помещаются в про- межуточные файлы, которые впоследствии пе- ресылаются в задачи Shuffle или Reduce [5]. Парадигма распределенных вычислений MapReduce в настоящее время широко исполь- зуется не только для эффективной обработки больших объемов данных, но и для решения прикладных задач, связанных с расширенной обработкой текста, сортировкой данных, ин- дексированием документов, вычислением ин- дексов цитируемости, статистическим анали- зом, машинным обучением, обработкой изо- бражений. Классифицировать многообразие этих задач только по области применения не представляется возможным по причине того, что многие области знаний тесно взаимодейст- вуют между собой. Имеет смысл добавить дру- гой критерий, связанный со стадиями обработ- ки данных парадигмой MapReduce. В результа- те исследования было выделено четыре класса задач, при решении которых применяют дан- ную модель распределенных вычислений. К первому классу, называемому MapReduce, необходимо отнести все возможные методы, алгоритмы, использующие в исследуемой па- радигме минимум две стадии: Map и Reduce. При решении практических задач зачастую стадии Shuffle или Combine не нужны. В таком случае общая схема работы парадигмы MapRe- duce упрощается и будет иметь следующий вид: 1. В модель распределенных вычислений подается коллекция документов (записей). 2. Функция Map применяется к каждой паре входных данных и возвращает набор промежу- точных пар. 3. MapReduce-контейнер группирует про- межуточные значения, связанные с одним клю- чом, и передает эти значения функции Reduce. Она преобразует промежуточные значения в окончательный набор значений для данного ключа. Как правило, это одно агрегированное значение, например сумма. К группе MapOnly относят задачи, для ре- шения которых можно обойтись только стадией Map (рис. 2). Примерами таких задач являются фильтрация данных (например, поиск нужной информации в лог-файлах по определенному критерию), преобразование данных (например, удаление определенного свойства в JSON- документе или перевод текста в нижний ре- гистр), загрузка и выгрузка данных из внешне- го источника (например, вставка записей в NoSQL-базу данных). В описанных типах задач пользователю требуется получить набор пар ключ – значение, поэтому другие стадии, такие как Combine, Reduce, ему не нужны [6]. Рис. 2. Схема работы MapOnly Цепочки MapReduce. К данной группе отно- сят ситуации, когда для решения определенных задач реализации одной MapReduce-модели не- достаточно. Тогда их объединяют в цепочки, которые могут выполняться либо линейно, ли- бо представлять собой более сложный направ- ленный ациклический граф. Для линейной це- почки проще всего запускать задания одно за другим, дожидаясь успешного завершения за- дания перед запуском следующего. Если одно из заданий завершается неудачно, то после- дующие задания в конвейере выполняться не будут. Когда их последовательность сложнее линейной цепочки, то необходимо определен- ным образом организовать поток операций, учитывая информацию о зависимости между вызовами MapReduce-задач. Если одно из зада- ний завершается с ошибкой, планировщик должен прекратить анализ зависимостей и пре- рвать выполнение всей цепочки задач (рис. 3). Рис. 3. Цепочки MapReduce ReduceJoin. К данному классу относят зада- чи, в которых необходимо объединить содер- жимое нескольких документов по некоторому ключу в выходном потоке данных. Результат работы этих задач очень похож на принцип Ì. Â. Ãëàäêèé 197 Òðóäû ÁÃÒÓ № 6 2016 работы с реляционными базами данных, где часто используют очень удобную операцию Join, позволяющую совместно обрабатывать содержание некоторых таблиц, объединив их по некоторому ключу. Примером таких задач является объединение двух или более лог- файлов сервера в один итоговый документ либо определение, на какой из двух серверов пользо- ватель чаще заходит по его IP-адресу [4]. Модель ReduceJoin функционирует, исполь- зуя следующий алгоритм (рис. 4): 1. На вход поступает две коллекции доку- ментов (записей). 2. Каждая из коллекций запускает отдель- ную MapOnly-задачу, преобразующую входные данные к паре ключ – значение. В качестве ключа используется поле, по которому нужно объединять записи коллекций, а в качестве зна- чений выступает пара Type (тип коллекции) и Value (любые дополнительные данные, привя- занные к ключу). 3. Результат работы MapOnly подается на вход следующей модели MapReduce. Эта це- почка должна содержать пустую функцию Map, которая копирует входные данные. Далее на стадии Shuffle данные разделяются по ключам и подаются на вход функции Reduce в виде па- ры, где в качестве значения используется мас- сив элементов Type и Value. Рис. 4. Схема работы ReduceJoin Модель MapReduce накладывает ряд огра- ничений на реализующее ее программное сред- ство в связи с необходимостью автоматизиро- вать распараллеливание, запуск и управление вычислениями на кластере. Кроме того, данная парадигма всегда требует полного сканирова- ния данных, поэтому использование индексов здесь недопустимо. Это означает, что подход MapReduce плохо применим и требует допол- нительных оптимизаций, когда необходимо по- лучить ответ в режиме реального времени. Эффективная реализация MapReduce не- возможна без эффективной организации спосо- ба хранения данных на кластерной системе. Для этой цели используются распределенные файловые системы (DFS), обеспечивающие вы- сокую производительность, масштабируемость, надежность и доступность данных. Эти файло- вые системы должны быть оптимизированы для хранения файлов большого размера, эффек- тивного использования сетевых ресурсов и оп- тимизации под высокую агрегированную про- пускную способность, нестандартный интер- фейс файловой системы, а также ослабленную модель целостности данных, связанную с хра- нением слабоструктурированной или не струк- турированной информации [6]. Запуском MapReduce-задач на кластере должен управлять планировщик, который от- слеживает состояние всех узлов и подбирает группу машин для выполнения задания. Вызо- вы функции Map распределяются между не- сколькими машинами путем автоматического разбиения входных данных, хранящихся в рас- пределенной файловой системе, на несколько частей. Полученные порции данных могут об- рабатываться параллельно различными маши- нами. Вызовы Reduce распределяются путем разбиения пространства промежуточных клю- чей на совокупность частей, определяемых с помощью заданной функции разбиения. Каж- дый из Reduce-процессов загружает со всех Map-процессов порции обработанных данных с соответствующими значениями промежуточ- ных ключей, производит сортировку и объеди- нение этих данных, после чего выполняет функцию Reduce. Результаты вычислений запи- сываются в виде файлов в DFS [5]. Парадигма MapReduce используется мно- гими компаниями, такими как: Google (служит для параллельных вычислений над очень боль- шими, несколько петабайт, наборами данных в компьютерных кластерах), CouchDB (использу- ет MapReduce для определения представлений поверх распределенных документов), MongoDB (позволяет применять MapReduce для парал- лельной обработки запросов на нескольких серверах), Apache Hadoop (фреймворк для раз- работки и выполнения распределенных про- грамм), Nvidia (распараллеливание вычислений на видео-ядрах с использованием технологий CUDA), Яндекс (обработка и анализ данных Интернет-сайтов). Каждая компания имеет свои закрытые реализации моделей MapReduce, по- зволяющие выполнять задачи, написанные на языках Java, C++, C, Python, JavaScript, C#, Perl, Erlang, Ruby. Заключение. В данной статье рассмотрена одна из основных моделей распределенных 198 Ìîäåëü ðàñïðåäåëåííûõ âû÷èñëåíèé MapReduce Òðóäû ÁÃÒÓ № 6 2016 вычислений MapReduce, применяемая для об- работки и анализа больших массивов данных на кластерных системах. Выявлено, что отли- чительными особенностями рассматриваемой парадигмы являются ее высокая гибкость, про- стота и удобство использования. Она скрывает от пользователя детали организации вычисле- ний на кластерной системе и открывает новые возможности по применению данных систем в научных и прикладных исследованиях для ре- шения задач, связанных с обработкой изобра- жений и текстовой информации, сортировкой данных, искусственным интеллектом. В статье также была представлена класси- фикация задач, решаемых с использованием ис- следуемой модели. В качестве классификаторов применялись стадии работы MapReduce-кон- тейнера, а также учитывались возможные сце- нарии прикладного использования решаемых задач в распределенных компьютерных средах. Литература 1. Евстигнеева И. Революция в аналитике. Как в эпоху Big Data улучшить ваш бизнес с помо- щью операционной аналитики? М.: Альпина Паблишер, 2016. 320 с. 2. Натан М. Большие данные. Принципы и практика построения масштабируемых систем обра- ботки данных в реальном времени. М.: Вильямс, 2015. 368 с. 3. Фрэнкс Б. Укрощение больших данных. Как извлекать знания из массивов информации с по- мощью глубокой аналитики? М: Манн, Иванов и Фербер, 2014. 352 с. 4. Сухобоков А. А. Влияние инструментария Big Data на развитие научных дисциплин, связан- ных с моделированием. М.: МГТУ им. Н. Э. Баумана, 2015. 51 c. 5. Dean J., Ghemawat S. MapReduce: Simplified data processing on large clusters // Proceedings of Operating Systems Design and Implementation (OSDI). 2004. P. 137–150. 6. Том У. Hadoop: Подробное руководство. СПб.: Питер, 2015. 670 c. References 1. Evstigneeva I. Revolyutsiya v analitike. Kak v epokhu Big Data uluchshit' vash biznes s pomoshch'yu operatsionnoy analitiki [The revolution in Analytics. As in the era of Big Data to improve your business with operational Analytics?]. Moscow, Al'pina Pablisher Publ., 2016. 320 p. 2. Natan M. Bol'shiye dannyye. Printsipy i praktika postroeniya masshtabiruemykh sistem obrabotki dannykh v real'nom vremeni [Big data. Principles and practice of building highly scalable data processing systems in real time]. Moscow, Vil'yams Publ., 2015. 368 p. 3. Frenks B. Ukroshcheniye bol'shikh dannykh. Kak izvlekat' znaniya iz massivov informatsii s po- moshch'yu glubokoy analitiki [The taming of big data. How to extract knowledge from the massive amounts of information using deep Analytics?]. Moscow, Mann, Ivanov i Ferber Publ., 2014. 352 p. 4. Sukhobokov A. A. Vliyaniye instrumentariya Big Data na razvitie nauchnykh distsiplin, svyazan- nykh s modelirovaniem [The impact of Big Data tools for the development of scientific disciplines related to modeling]. Moscow, MGTU imeni N. E. Baumana Publ., 2015. 51 p. 5. Dean J., Ghemawat S. MapReduce: Simplified data processing on large clusters. Proceedings of Operating Systems Design and Implementation (OSDI), 2004, pp. 137–150. 6. Tom U. Hadoop: Podrobnoye rukovodstvo [Hadoop: The Definitive Guide]. St. Petersburg, Piter Publ., 2015. 670 p. Информация об авторе Гладкий Максим Валерьевич – ассистент кафедры информационных систем и технологий. Бе- лорусский государственный технологический университет (220006, г. Минск, ул. Свердлова, 13а, Республика Беларусь). E-mail: MaksHladki@gmail.com Gladkiy Maksim Valer’yevich – assistant lecturer, the Department of Information Systems and Tech- nologies. Belarusian State Technological University (13a, Sverdlova str., 220006, Minsk, Republic of Be- larus). E-mail: MaksHladki@gmail.com Поступила 10.03.2016 |