Анализ технологии MapReduce

Размещено на http://www.allbest.ru/

АВТОНОМНАЯ НЕКОММЕРЧЕСКАЯ ОБРАЗОВАТЕЛЬНАЯ

ОРГАНИЗАЦИЯ ВЫСШЕГО ОБРАЗОВАНИЯ

ЦЕНТРОСОЮЗА РОССИЙСКОЙ ФЕДЕРАЦИИ

«РОССИЙСКИЙ УНИВЕРСИТЕТ КООПЕРАЦИИ»

КРАСНОДАРСКИЙ КООПЕРАТИВНЫЙ ИНСТИТУТ (ФИЛИАЛ)

Факультет: Среднего профессионального образования

Кафедра: Бухгалтерского учета и информационных технологий

Специальность: 09.02.04 Информационные системы (по отраслям)

Курс: 2 Форма обучения очная

Курсовая работа

Дисциплина: Основы архитектуры, устройство и функционирование вычислительной системы

Тема: Произвести анализ технологии MapReduce и привести примеры использования

Выполнил:

Клемпарский Максим Владимирович

Руководитель:

Богачев А.Ю.

Краснодар 2018



АВТОНОМНАЯ НЕКОММЕРЧЕСКАЯ ОБРАЗОВАТЕЛЬНАЯ

ОРГАНИЗАЦИЯ ВЫСШЕГО ОБРАЗОВАНИЯ

ЦЕНТРОСОЮЗА РОССИЙСКОЙ ФЕДЕРАЦИИ

«РОССИЙСКИЙ УНИВЕРСИТЕТ КООПЕРАЦИИ»

КРАСНОДАРСКИЙ КООПЕРАТИВНЫЙ ИНСТИТУТ (ФИЛИАЛ)

Факультет: среднего профессионального образования

Кафедра: Бухгалтерского учета и информационных технологий

Специальность: 09.02.04 Информационные системы (по отраслям)

УТВЕРЖДАЮ

Заведующий кафедрой

__________к.э.н. Н.В. Ходаринова

ЗАДАНИЕ

ПО КУРСОВОЙ РАБОТЕ

Клемпарский Максим Владимирович

1 Тема работы: «Анализ технологии MapReduce и привести примеры»

2 Срок сдачи законченной работы на кафедру «____» _____ 2018 г.

3 Содержание пояснительной записки (перечень подлежащих разработке вопросов):

1 Основные понятия MapReduce

2 Принципы работы MapReduce

3 Оценка технологии MapReduce

4 Реализация технологии MapReduce

5 Способы реализации технологии MapReduce



Содержание

Введение

1. Основные понятия технологии MapReduce

2. Принципы работы технологии MapReduce

3. Оценка технологии MapReduce

4. Реализации технологии MapReduce

5. Способы реализации технологии MapReduce

Заключение

Список использованных источников



Введение

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

Задачи курсовой работы:

- Произвести анализ технологии MapReduce.

- Дать оценку технологии MapReduce.

- Рассмотреть надёжность технологии MapReduce, её критику, где используется, её преимущества, реализацию и особенности.

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

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



1. Основные понятия технологии MapReduce

MapReduce - это представленная компанией Google модель распределённых вычислений, а также её реализации, используемые для параллельной обработки больших объёмов информации.

Работа MapReduce состоит из шагов Map и Reduce, названных аналогично функциям высшего порядка из многих языков программирования, применяемым на этих шагах.

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

Модель MapReduce применима в широкой области задач, включая распределённый поиск, распределённую сортировку, обращение графа веб-ссылок, обработку статистики логов сети, построение инвертированных индексов, кластеризацию документов, машинное обучение и статистический машинный перевод. Более того, MapReduce была адаптирована под такие вычислительные среды, как многопроцессорные системы, добровольные вычислительные, динамические облачные и мобильные среды. В компании Google модель MapReduce была использована, чтобы полностью сгенерировать индекс Всемирной паутины, однако вскоре стали применяться другие технологии, например, Percolator, Flume и MillWheel, которые позволяют производить потоковые операции вместо пакетной обработки, что дало возможность реализовать «живой» поиск без перепостроения всего индекса.

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

Преимущество MapReduce заключается в том, что он позволяет распределённо производить операции предварительной обработки и свертки. Операции предварительной обработки работают независимо друг от друга и могут производиться параллельно. Аналогично множество рабочих узлов могут осуществлять свертку: для этого необходимо только чтобы все результаты предварительной обработки с одним значением ключа обрабатывались одним рабочим узлом в один момент времени. Хотя этот процесс может быть менее эффективным по сравнению с более последовательными алгоритмами, MapReduce может быть применен к большим объёмам данных, которые невозможно обработать последовательно в разумное время из-за недостатка памяти. Так, MapReduce может быть использован для сортировки петабайта данных, и это займет всего несколько часов. Параллелизм также дает некоторые возможности восстановления после частичных сбоев серверов: если в рабочем узле возникает сбой, то его работа может быть передана другому рабочему узлу (при условии, что входные данные для проводимой операции доступны).

2. Принципы работы технологии MapReduce

Функция map принимает на вход список и некую функцию, затем применяет данную функцию к каждому элементу списка и возвращает новый список. Функция reduce (свёртка) преобразует список к единственному атомарному значению при помощи заданной функции, которой на каждой итерации передаются новый элемент списка и промежуточный результат. Для обработки данных пользователь библиотеки MapReduce должен только определить две эти функции, а также указать имена входных и выходных файлов и параметры обработки.

Шаг Map:

1Входные данные решаемой задачи представляют большой список значений, и на Map-шаге происходит его предварительная обработка. Для этого главный узел кластера (master node) получает этот список, делит его на части и передает рабочим узлам (worker node). Далее каждый из рабочих узлов преобразует элементы полученной коллекции в ноль или несколько промежуточных пар «ключ-значение».

Шаг Reduce:

На Reduce-шаге главный узел получает промежуточные ответы от рабочих узлов и передаёт их на свободные узлы для выполнения следующего шага. Система сортирует и группирует по ключу все пары «ключ-значение» и затем для каждой пары «ключ-группа значений» сворачивает значения, часто в одно или в пустой список. Получившийся результат - это решение задачи, которая изначально формулировалась.

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

Канонический пример приложения, написанного с помощью MapReduce - это программа на псевдокоде, подсчитывающая количество различных слов в наборе документов (рисунок 1).

// Функция, используемая рабочими узлами на Map-шаге для обработки пар ключ-значение из входного потока

voidmap(String name, String document):

// Входные данные:

// name - название документа

// document - содержимое документа

for each word w in document:

EmitIntermediate(w, "1");

// Функция, используемая рабочими узлами на Reduce-шаге для обработки пар ключ-значение, полученных на Map-шаге

void reduce(String word, Iterator partialCounts):

// Входные данные:

// word - слово

// partialCounts - список группированных промежуточных результатов. Количество записей в partialCounts и есть требуемое значение

int result =0;

for each v in partialCounts:

result += parseInt(v);

Emit(AsString(result));

Рисунок 1 Пример алгоритма на псевдокоде

В этом коде на Map-шаге каждый документ разбивается на слова, и возвращаются пары, где ключом является само слово, а значением - «1». Если в документе одно и то же слово встречается несколько раз, то в результате предварительной обработки этого документа будет столько же этих пар, сколько раз встретилось это слово. Библиотека объединяет все пары с одинаковым ключом и передает их на вход функции reduce, которой остается сложить их, чтобы получить общее количество вхождений данного слова во все документы. Вызовы операции Map распределены между множеством машин с помощью автоматического деления входных данных на набор из M{\displaystyle M} частей. Входные части могут обрабатываться параллельно несколькими машинами. Вызовы операции Reduce распределены разделением промежуточного пространства ключей на R{\displaystyle R} частей с помощью функции разделения (например, hash(key)modR{\displaystyle hash(key)modR} ). Количество частей R и функция разделения задаются пользователем. На схеме показан полный процесс операции MapReduce в реализации Google.

Рисунок 2 Полный процесс операции MapReduce в реализации Google

Когда программа пользователя вызывает функцию MapReduce, происходит следующая последовательность операций (их номера в схеме соответствуют списку ниже):

1.Сначала библиотека MapReduce в программе пользователя делит входные файлы на M частей, каждая из которых обычно занимает от 16 до 64 мегабайт (этот параметр может задаваться пользователем). Затем она запускает множество копий программы на кластере.

2.Одна из копий программы (master) особенная, она задаёт работу остальным экземплярам (workers). Всего нужно задать M задач map и R задач reduce. Мастер ищет неактивные рабочие экземпляры и назначает каждой из них одну задачу.

3.Рабочий экземпляр программы, которому была присвоена задача map, читает содержимое соответствующей части входных данных, разбирает его и передаёт каждый элемент функции пользователя Map.

4.Промежуточные пары «ключ-значение» затем сохраняются в памяти.

5.Через некоторые промежутки времени сохранённые пары записываются на локальный диск и разбиваются на R областей функцией разделения.

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

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

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

9.Рабочий экземпляр проходит по отсортированным промежуточным данным и передаёт функции Reduce каждый уникальный ключ и соответствующий ему список значений.

10.Результат присоединяется к конечному файлу для этой части промежуточных данных.

11.Когда все задачи map и reduce будут выполнены, вызов MapReduce будет завершён, и произойдёт возврат обратно к пользовательскому коду. После успешного завершения обработки выходные данные будут доступны в R результирующих файлов (один файл на каждую задачу reduce) с названиями, заданными пользователем. Обычно пользователям не нужно соединять эти R файлов в один - часто бывает, что эти файлы передаются очередному вызову MapReduce уже в качестве входа или обрабатываются в других распределённых приложениях, которым на вход также передаются несколько файлов.

Надёжность MapReduce достигается за счёт распределения операции обработки данных по всем узлам сети. Мастер периодически опрашивает каждый рабочий узел для получения статуса или результата работы. Если узел не отвечает в течение установленного времени, мастер начинает считать его аварийным и назначает его работу другому узлу. В узлах применяются атомарные операции именования выходных файлов для проверки, что в каждый момент не запущены конфликтующие параллельные потоки. Так как операция свёртки плохо распараллеливается, и именно в узле хранится обрабатываемая часть данных, мастер предпринимает попытки запуска свёртки на том же самом или на близлежащих узлах. Не все реализации MapReduce обязательно обладают высокой надёжностью. Например, в ранних версиях Hadoop примитив мастер-узла NameNode был единой точкой отказа распределённой файловой системы. Более поздние версии Hadoop стали обладать большей активной и пассивной отказоустойчивостью.

Дэвид ДеВитт и Майкл Стоунбрейкер, компьютерные специалисты, специализирующиеся на параллельных базах данных и распределённых архитектурах, критиковали ширину области задач, для которых может применяться MapReduce. Они назвали интерфейс реализации слишком низкоуровневым и поставили под сомнение заявление разработчиков о том, что он представляет новый этап развития технологий. Одним из аргументов стало сравнение MapReduce с Teradata, системой массовой параллельной обработки, существующей уже больше двух десятилетий, а также с языком CODASYL («программирование на низкоуровневом языке, производящее низкоуровневые манипуляции»). Также отсутствие поддержки схем не позволяет улучшать производительность с помощью присущих обыкновенным базам данных B-деревьев и хэш-разбиения, однако некоторые проблемы позволяют решить такие проекты как Pig (или PigLatin), Sawzall, Apache Hive, YSmart, HBase и BigTable. Грег Йоргенсен опубликовал статью, опровергающую эти взгляды. Йоргенсен полагает, что анализ ДеВитта и Стоунбрейкера полностью безоснователен, так как MapReduce никогда не разрабатывался и не позиционировался как база данных.

Сначала ДеВитт, а затем и Стоунбрейкер опубликовали в 2009 году детальное исследование производительности реализации MapReduce в Hadoop и подходов СУБД в некоторых аспектах. Они сделали заключение, что реляционные базы данных предлагают настоящие преимущества для многих способов использования данных, особенно для их сложной обработки, или когда данные располагаются в хранилище крупного предприятия, однако использование MapReduce может оказаться проще для начинающих пользователей или несложных задач. Патент на MapReduce побудил множество споров, так как реализация MapReduce очень похожа на существующие продукты. Например, операции map и reduce могут быть легко реализованы на языке базы данных Oracle PL/SQL, а также неявно предоставляются в таких распределённых базах данных как Clusterpoint XML или MongoDB NoSQL. Ограниченные возможности фреймворка.

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

Реализация MapReduce компанией Google запатентована, однако существует множество других, как коммерческих, так и свободных продуктов, использующих эту модель, таких как Apache Hadoop, Apache CouchDB, MongoDB, MySpace Qizmt и другие. Для сравнения рассмотрим моделиApacheHadoop и ApacheCouchDB. Apache Hadoop -- проект фонда Apache Software Foundation, свободно распространяемый набор утилит, библиотек и фреймворк для разработки и выполнения распределённых программ, работающих на кластерах из сотен и тысяч узлов. Используется для реализации поисковых и контекстных механизмов многих высоконагруженных веб-сайтов, в том числе, для Yahoo! и Facebook. Разработан на Java в рамках вычислительной парадигмы MapReduce, согласно которой приложение разделяется на большое количество одинаковых элементарных заданий, выполнимых на узлах кластера и естественным образом сводимых в конечный результат.

По состоянию на 2014 год проект состоит из четырёх модулей -- Hadoop Common (связующее программное обеспечение -- набор инфраструктурных программных библиотек и утилит, используемых для других модулей и родственных проектов), HDFS(распределённая файловая система), YARN (система для планирования заданий и управления кластером) и Hadoop MapReduce (платформа программирования и выполнения распределённых MapReduce-вычислений), ранее в Hadoop входил целый ряд других проектов, ставших самостоятельными в рамках системы проектов Apache Software Foundation. Считается одной из основополагающих технологий «больших данных». Вокруг Hadoop образовалась целая экосистема из связанных проектов и технологий, многие из которых развивались изначально в рамках проекта, а впоследствии стали самостоятельными. Со второй половины 2000-х годов идёт процесс активной коммерциализации технологии, несколько компаний строят бизнес целиком на создании коммерческих дистрибутивов Hadoop и услуг по технической поддержке экосистемы, а практически все крупные поставщики информационных технологий для организаций в том или ином виде включают Hadoop в продуктовые стратегии и линейки решений.

История Hadoop

Разработка была инициирована в начале 2005 года Дугом Каттингом с целью построения программной инфраструктуры распределённых вычислений для проекта Nutch -- свободной программной поисковой машины на Java, её идейной основой стала публикация сотрудников Google Джеффри Дина и Санжая Гемавата о вычислительной концепции MapReduce. Новый проект был назван в честь игрушечного слонёнка ребёнка основателя проекта. В течение 2005--2006 годов Hadoop развивался усилиями двух разработчиков -- Каттинга и Майка Кафареллы (Mike Cafarella) в режиме частичной занятости, сначала в рамках проекта Nutch, затем -- проекта Lucene.

В январе 2008 года Hadoop становится проектом верхнего уровня системы проектов Apache Software Foundation. В апреле 2008 года Hadoop побил мировой рекорд производительности в стандартизованном бенчмарке сортировки данных -- 1 Тбайт был обработан за 209 сек. на кластере из 910 узлов. В апреле 2010 года корпорация Google предоставила Apache Software Foundation права на использование технологии MapReduce, через три месяца после её защиты в патентном бюро США, тем самым избавив организацию от возможных патентных претензий.Начиная с 2010 года Hadoop неоднократно характеризуется как ключевая технология «больших данных», прогнозируется его широкое распространение для массово-параллельной обработки данных, и, наряду с Cloudera, появилась серия технологических стартапов, целиком ориентированных на коммерциализацию Hadoop.

В течение 2010 года несколько подпроектов Hadoop -- Avro, HBase, Hive, Pig, Zookeeper -- последовательно стали проектами верхнего уровня фонда Apache, что послужило началом формирования экосистемы вокруг Hadoop. В марте 2011 года Hadoop удостоен ежегодной инновационной награды медиагруппы Guardian, на церемонии вручения технология была названа «швейцарским армейским ножом XXI века». Реализация в вышедшем осенью 2013 года Hadoop 2.0 модуля YARN оценена как значительный скачок, выводящий Hadoop за рамки парадигмы MapReduce и ставящая технологию на уровень универсального решения для организации распределённой обработки данных.

3. Оценка технологии MapReduce

Возможности

Изначально Hadoop был, в первую очередь, инструментом для хранения данных и запуска MapReduce-задач, сейчас же Hadoop представляет собой большой стек технологий, так или иначе связанных с обработкой больших данных (не только при помощи MapReduce).

Основными (core) компонентами Hadoop являются:

Hadoop Distributed File System (HDFS) - распределённая файловая система, позволяющая хранить информацию практически неограниченного объёма.

Hadoop YARN - фреймворк для управления ресурсами кластера и менеджмента задач, в том числе включает фреймворк MapReduce.

Hadoop common.

Также существует большое количество проектов непосредственно связанных с Hadoop, но не входящих в Hadoop core:

Hive - инструмент для SQL-like запросов над большими данными (превращает SQL-запросы в серию MapReduce-задач);

Pig - язык программирования для анализа данных на высоком уровне. Одна строчка кода на этом языке может превратиться в последовательность MapReduce-задач;

HBase - колоночная база данных, реализующая парадигму BigTable;

Cassandra - высокопроизводительная распределенная key-value база данных;

ZooKeeper - сервис для распределённого хранения конфигурации и синхронизации изменений этой конфигурации;

Mahout - библиотека и движок машинного обучения на больших данных. ссылка сеть кластеризация инвертированный

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

Одной из основных целей Hadoop изначально было обеспечение горизонтальной масштабируемости кластера посредством добавления недорогих узлов, без использования мощных серверов и дорогих сетей хранения данных. Функционирующие кластеры размером в тысячи узлов подтверждают осуществимость и экономическую эффективность таких систем, так, по состоянию на 2011 год известно о крупных кластерах Hadoop в Yahoo (более 4 тыс. узлов с суммарной ёмкостью хранения 15 Пбайт), Facebook (около 2 тыс. узлов на 21 Пбайт) и Ebay (700 узлов на 16 Пбайт)]. Тем не менее, считается, что горизонтальная масштабируемость в Hadoop-системах ограничена, для Hadoop до версии 2.0 максимально возможно оценивалась в 4 тыс. узлов при использовании 10 MapReduce-заданий на узел. Во многом этому ограничению способствовала концентрация в модуле MapReduce функций по контролю за жизненным циклом заданий, считается, что с выносом её в модуль YARN в Hadoop 2.0 и децентрализацией -- распределением части функций по мониторингу на узлы обработки -- горизонтальная масштабируемость повысилась.

Ещё одним ограничением Hadoop-систем является размер оперативной памяти на узле имён, хранящем всё пространство имён кластера для распределения обработки, притом общее количество файлов, которое способен обрабатывать узел имён -- 100 млн. Для преодоления этого ограничения ведутся работы по распределению узла имён, единого в текущей архитектуре на весь кластер, на несколько независимых узлов. Другим вариантом преодоления этого ограничения является использование распределённых СУБД поверх HDFS, таких как HBase, роль файлов и каталогов в которых с точки зрения приложения играют записи в одной большой таблице базы данных. По состоянию на 2011 год типичный кластер строился из однопроцессорных многоядерных x86-64-узлов под управлением Linux с 3-12 дисковыми устройствами хранения, связанных сетью с пропускной способностью 1 Гбит/с. Существуют тенденции как к снижению вычислительной мощности узлов и использованию процессоров с низким энергопотреблением (ARM, Intel Atom), так и применения высокопроизводительных вычислительных узлов одновременно с сетевыми решениями с высокой пропускной способностью (InfiniBand в Oracle Big Data Appliance[en], высокопроизводительная сеть хранения данных на Fibre Channel и Ethernet пропускной способностью 10 Гбит/с в шаблонных конфигурациях FlexPod для «больших данных»). Масштабируемость Hadoop-систем в значительной степени зависит от характеристик обрабатываемых данных, прежде всего, их внутренней структуры и особенностей по извлечению из них необходимой информации, и сложности задачи по обработке, которые, в свою очередь, диктуют организацию циклов обработки, вычислительную интенсивность атомарных операций, и, в конечном счёте, уровень параллелизма и загруженность кластера. В руководстве Hadoop (первых версий, ранее 2.0) указывалось, что приемлемым уровнем параллелизма является использование 10-100 экземпляров базовых обработчиков на узел кластера, а для задач, не требующих значительных затрат процессорного времени -- до 300; для свёрток считалось оптимальным использование их по количеству узлов, умноженному на коэффициент из диапазона от 0,95 до 1,75. С большим значением коэффициента наиболее быстрые узлы, закончив первый раунд сведения, раньше получат вторую порцию промежуточных пар для обработки, таким образом, увеличение коэффициента избыточно загружает кластер, но при этом обеспечивает более эффективную балансировку нагрузки. В YARN вместо этого используются конфигурационные константы, определяющие значения доступной оперативной памяти и виртуальных процессорных ядер, доступных для планировщика ресурсов, на основании которых и определяется уровень параллелизма.

Hadoop MapReduce

Hadoop MapReduce -- программный каркас для программирования распределённых вычислений в рамках парадигмы MapReduce. Разработчику приложения для Hadoop MapReduce необходимо реализовать базовый обработчик, который на каждом вычислительном узле кластера обеспечит преобразование исходных пар «ключ -- значение» в промежуточный набор пар «ключ -- значение» (класс, реализующий интерфейс Mapper, назван по функции высшего порядка Map), и обработчик, сводящий промежуточный набор пар в окончательный, сокращённый набор (свёртку, класс, реализующий интерфейс Reducer). Каркас передаёт на вход свёртки отсортированные выводы от базовых обработчиков, сведемние состоит из трёх фаз:

shuffle (тасовка, выделение нужной секции вывода)

sort (сортировка, группировка по ключам выводов от распределителей -- досортировка, требующаяся в случае, когда разные атомарные обработчики возвращают наборы с одинаковыми ключами, при этом, правила сортировки на этой фазе могут быть заданы программно и использовать какие-либо особенности внутренней структуры ключей).

reduce (свёртка списка) -- получения результирующего набора. Для некоторых видов обработки свёртка не требуется, и каркас возвращает в этом случае набор отсортированных пар, полученных базовыми обработчиками.

Hadoop MapReduce позволяет создавать задания как с базовыми обработчиками, так и со свёртками, написанными без использования Java: утилиты Hadoop streaming позволяют использовать в качестве базовых обработчиков и свёрток любой исполняемый файл, работающий со стандартным вводом-выводом операционной системы (например, утилиты командной оболочки UNIX), есть также SWIG-совместимый прикладной интерфейс программирования Hadoop pipes на C++. Также, в состав дистрибутивов Hadoop входят реализации различных конкретных базовых обработчиков и свёрток, наиболее типично используемых в распределённой обработке. В первых версиях Hadoop MapReduce включал планировщик заданий (JobTracker), начиная с версии 2.0 эта функция перенесена в YARN, и начиная с этой версии модуль Hadoop MapReduce реализован поверх YARN. Программные интерфейсы по большей части сохранены, однако полной обратной совместимости нет (то есть для запуска программ, написанных для предыдущих версий API, для работы в YARN в общем случае требуется их модификация или рефакторинг, и лишь при некоторых ограничениях возможны варианты обратной двоичной совместимости).

4. Реализации технологии MapReduce

Использование

Теперь покажем как запустить MapReduce-задачу на Hadoop. В качестве задачи воспользуемся классическим примером WordCount, который был разобран в предыдущей статье цикла. Напомню формулировку задачи: имеется набор документов. Необходимо для каждого слова, встречающегося в наборе документов, посчитать, сколько раз встречается слово в наборе.

Решение: Map разбивает документ на слова и возвращает множество пар (word, 1). Reduce суммирует вхождения каждого слова:

functionmap*(source){

for(constwordinsource.split(' ')){

yield[word,1];

}

}

Рисунок 3 Функция map

functionreduce*(word,values){

yield[word,values.length];

}

Рисунок 4 Функция reduce

Теперь задача запрограммировать это решение в виде кода, который можно будет исполнить на Hadoop и запустить. Самый простой способ запустить MapReduce-программу на Hadoop -- воспользоваться streaming-интерфейсом Hadoop. Streaming-интерфейс предполагает, что map и reduce реализованы в виде программ, которые принимают данные с stdin и выдают результат на stdout. Программа, которая исполняет функцию map называется mapper. Программа, которая выполняет reduce, называется, соответственно, reducer. Streaming интерфейс предполагает по умолчанию, что одна входящая строка в mapper или reducer соответствует одной входящей записи для map. Вывод mapper'a попадает на вход reducer'у в виде пар (ключ, значение), при этом все пары соответствующие одному ключу: Гарантированно будут обработаны одним запуском reducer'a; Будут поданы на вход подряд (то есть если один reducer обрабатывает несколько разных ключей - вход будет сгруппирован по ключу).

Итак, реализуем mapper и reducer на JavaScript

// mapper.js

process.stdin.setEncoding('utf8');

letinput='';

process.stdin.on('readable',function(){

constchunk=process.stdin.read();

if(chunk!==null){

input+=chunk;

}

});

process.stdin.on('end',function(){

input

.split(' ')

.forEach(word=>process.stdout.write(`${word}\t1\n`));

});

// reducer.js

process.stdin.setEncoding('utf8');

letinput='';

process.stdin.on('readable',function(){

constchunk=process.stdin.read();

if(chunk!==null){

input+=chunk;

}

});

process.stdin.on('end',function(){

constresult=input

.split('\n')

.reduce((result,line)=>{

const[word,value]=line.split('\t');

result[word]=(result[word]||0)+(+value);

returnresult;

},{});

Object.keys(result)

.forEach(word=>process.stdout.write(`${word}\t${result[word]}\n`));

});

5. Способы реализации технологии MapReduce

Данные, которые будет обрабатывать Hadoop должны храниться на HDFS. Загрузим наши статьи и положим на HDFS. Для этого нужно воспользоваться командой hadoop fs (рисунок 5).

$ hadoop fs -put input_text.txt

$ yarn jar /usr/lib/hadoop-mapreduce/hadoop-streaming.jar\

-input input_text.txt\

-output output\

-file mapper.js\

-file reducer.js\

-mapper "node mapper.js"\

-reducer "node reducer.js"

Команда hadoop fs

Утилита yarn служит для запуска и управления различными приложениями (в том числе map-reduce based) на кластере. hadoop-streaming.jar -- это как раз один из примеров такого yarn-приложения.

Дальше идут параметры запуска:

input - папка с исходными данными на hdfs;

output - папка на hdfs, куда нужно положить результат;

file - файлы, которые нужны в процессе работы map-reduce задачи;

mapper - консольная команда, которая будет использоваться для map-стадии;

reduce - консольная команда которая будет использоваться для reduce-стадии.

После запуска в консоли можно будет увидеть прогресс выполнения задачи и URL для просмотра более детальной информации о задаче. В интерфейсе доступном по этому URL можно узнать более детальный статус выполнения задачи, посмотреть логи каждого маппера и редьюсера (что очень полезно в случае упавших задач). Результат работы после успешного выполнения складывается на HDFS в папку, которую мы указали в поле output. Просмотреть её содержание можно при помощи команды hadoop fs -ls lenta_wordcount.

CouchDB -- документированная система управления базами данных с открытым исходным кодом, не требующая описания схемы данных. Данный продукт написан на языке Erlang и распространяется свободно. Первый релиз состоялся в 2005 году. В 2008 CouchDB стал проектом фонда Apache Software Foundation.

История

Couch - это сокращение от «Сluster Of Unreliable Commodity Hardware». Проект CouchDB был создан в апреле 2005 года Дэмиеном Кацем, бывшим разработчиком Lotus Notes в IBM. Он сам финансировал проект в течение почти двух лет и выпустил его как проект с открытым исходным кодом по стандартной общественной лицензии GNU. В феврале 2008 года данный продукт стал проектом Apache Incubator и был предложен по лицензии Apache. Через несколько месяцев он приобрел статус проекта верхнего уровня. Первая стабильная версия продукта была выпущена в июле 2010 года. В начале 2012 года Кац покинул проект, чтобы сосредоточиться на проекте Couchbase Server. После ухода Каца работа над проектом Apache CouchDB продолжилась, в апреле 2012 года была выпущена версия 1.2, а в апреле 2013 - версия 1.3. В июле 2013, сообщество СouchDB совместило его кодовую базу с BigCouch, и с кластерной версией СouchDB Сloudant в рамках проекта Apache. Кластерная платформа BigCouch включена в текущую версию продукта. Встроенная кластеризация поддерживается в версии 2.0.0., а новый сервер запросов Mango предоставляет простой способ выполнения запросов CouchDB без JavaScript или MapReduce.

Особенности

ACID - семантика. CouchDB поддерживает ACID-семантику (модель построения языка, обладающую совокупностью свойств и функций, обеспечивающих корректность работы системы даже в случае ошибок, сбоев питания и т.п.).

· Работа в offline

CouchDB может реплицироваться на различные устройства (например, смартфоны), где может перейти в автономный режим и синхронизировать данные, когда устройство снова будет в сети.

· Распределенная архитектура с репликацией

CouchDB был cконструирован с возможностью двунаправленной репликации (или синхронизацией). Это означает, что несколько копий одних и тех же данных могут иметь собственные копии, изменять их, а потом синхронизировать эти изменения.

· Хранение документов

CouchDB хранит документы, как одну или несколько пар полей/значений, представленных как коллекция документов JSON. Значения полей могут быть простыми элементами (такими как строки, числа или даты), но также могут использоваться упорядоченные списки и ассоциативные массивы. В базе данных CouchDB не требуется схема описания данных, а каждый документ имеет уникальный идентификатор.

· HTTP API

Все элементы имеют уникальный URI, доступ к которому предоставляется через HTTP. Он использует методы HTTP POST, GET, PUT и DELETE для четырех основных операций CRUD (Create, Read, Update, Delete) на всех ресурсах. CouchDB также предлагает встроенный интерфейс администрации, доступный через вызываемую сеть Futon.

Архитектура:

- Подобно иным документно-ориентированным СУБД (Mnesia, Lotus Notes, MongoDB) и в отличие от реляционных СУБД, CouchDB предназначена для работы с полу структурированной информацией и имеет следующие особенности: данные сохраняются не в строках и колонках, а в виде JSON-подобных документов, моделью которых является не таблицы, а деревья; типизация элементов данных, то есть сопоставление отдельным полям документов типов INTEGER, DATE и пр., не поддерживается -- вместо этого пользователь может написать функцию-валидатор; целостность базы данных обеспечивается исключительно на уровне отдельных записей (но не на уровне связей между ними); связи между таблицами или записями принципиально не поддерживаются, соответственно операция объединения (JOIN) между таблицами не определена.

- Для построения индексов и выполнения запросов используются функции представления (view);функции-валидаторы, функции-представления, функции-фильтры сохраняются в текстовом виде в самой базе данных эти функции, как правило, написаны на языках JavaScript или Erlang, а для их выполнения запускается отдельный сервер запросов, взаимодействие с которым происходит посредством сокетов и текстового JSON-протокола каждой базе данных в системе CouchDB соответствует единственное B-дерево (не путать с двоичным деревом);каждое B-дерево хранится в виде отдельного файла на диске одновременно может быть запущено несколько потоков для чтения базы данных и только один -- для записи целостность базы данных обеспечивается только при записи данных на диск представления хранятся в БД и их индексы обновляются непрерывно, однако при каждом обновлении функций представления или отображения обновляется всё B-дерево целиком при обработке данных с помощью функций-представлений используется упрощённая модель технологии MapReduce, что позволяет производить параллельные вычисления, в том числе и на многоядерном процессоре; распределение вычислений на несколько узлов не поддерживается -- вместо этого используется механизм репликации обработка данных с помощью цепочки последовательных функций MapReduce не поддерживается; поддерживается вертикальное масштабирование; внешний интерфейс (API) к данной СУБД построен на основе архитектуры REST, то есть сама база данных, отдельные записи, отображения и запросы -- суть ресурсы, которые имеют уникальный адрес (URL) и поддерживают операции GET, PUT, POST, DELETE.

- Поэтому для взаимодействия с базой данных было написано много клиентских библиотек, в том числе на таких языках: JavaScript, PHP, Ruby, Python и Erlang.

- Взаимодействие между отдельными компонентами СУБД, то есть с серверами представлений осуществляется опять-таки с помощью текстового протокола, а данные передаются в формате JSON; это позволило использовать различные языки программирования для написания этих компонентов -- Java, Python, JavaScript и пр.

Масштабирование

Одна из ключевых и самых интересных особенностей CouchDB -- его репликации. CouchDB поддерживает как master/slave, так и master/master репликации.

Master-slave

Является наиболее распространенной архитектурой баз данных, когда имеется более одного cервера базы данных. В отношениях master-slave существует одна база данных, которая выполняет роль ведущего, а остальные базы данных выступают в качестве её подчиненного. Это означает, что:

Приложение будет подключаться к мастер для обновления данных.

Затем данные будут пульсировать через подчиненные устройства, пока все данные не будут согласованы на серверах.

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

Master-master

Репликация master-master уникальна тем фактом, что не существует постоянной базы данных master; каждый сервер базы данных может выступать в роли мастера одновременно с другими серверами. В какой-то момент все ведущие синхронизируются, чтобы убедиться, что они все имеют правильные и обновленные данные. Репликация master-master позволяет:

В случае сбоя одного ведущего сервера другие серверы баз данных могут нормально функционировать и забирать слабину. Когда сервер базы данных снова подключится к сети, он догонит остальных, используя репликацию. Мастера могут размещаться на нескольких физических серверах и ??могут быть распределены по сети. Проблемой такой репликации в реляционных базах данных являются потенциальные конфликты. Поэтому CouchDB (обладающий свойством MVCC (multiversion concurrency control)), при возникновении конфликта сохраняет все конфликтующие версии и умеет эти конфликты разрешать, по сконфигурированным правилам (либо отдать это дело в руки вашего приложения -- как вы захотите этим воспользоваться, зависит только от вашей фантазии)

Понятие View

В CouchDB можно определять view. View -- это функции, которые могут быть написаны на любом языке программирования, которые получают на вход все документы из БД по очереди и выбирают некоторые из них по какому-либо условию. По умолчанию функции пишутся на Javascript, но можно писать на PHP, Python и других языках). View хранятся в CouchDB в виде документов, как и обычные данные. Каждый документ, хранящий view, может содержать в себе неограниченное количество view-функций, это своего рода способ группировать view-функции. Обычно в один документ помещаются функции, возвращающие похожие наборы данных.

Практический пример

Рассмотрим пример запроса, возвращающего всех пользователей из БД. Т.к. документов может быть много, чтобы их кластеризовать, целесообразно ввести свойство type в документы, которое для документов, хранящих информацию о пользователях, будет type = "user", что мы и используем при выборке (рисунок 7).

Эта простая функция, которая получает по очереди каждый из документов, и те, у которых свойство type="user" передает в специальную функцию emit(). Функция emit получает в качестве аргументов пару ключ-значение и создает индекс из полученных ключей.

function ( doc )

{

if ( doc.type =='user' )

{

emit( doc._id, doc._id );

}

}

Рисунок 6 Функция doc

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

Возвращаемые view данные всегда сортируются по ключу.

Использование

Возможности репликации и синхронизации CouchDB делают его идеальным для использования на мобильных устройствах.

В случае, если сетевое подключение прервется, приложение будет продолжать работать в автономном режиме.

CouchDB хорошо подходит для приложений с накапливающимися и время от времени изменяющимися данными, на которых должны выполняться предопределенные запросы и где важно управление версиями (например для cистем управления взаимоотношениями с клиентами (CRM), сиcтем управления содержимым (CMS)).

На сегодняшний день CouchDB используют:

· Amadeus IT Group, в некоторых серверных системах;

· Meebo, для их социальной платформы (веб и приложения). Meebo был приобретен Google, и закрыт 12 июля 2012 г;

· Npm, для их реестра пакетов;

· Sophos, для некоторых серверных систем;

· BBC, для своих динамических контентных платформ;

· Canonical использовали CouchDB для своего сервиса "Ubuntu One", в период с 2009 по ноябрь 2011;

· CANAL+ для своей международной портативной платформы CANAL+ Overseas;

· Commusoft, для управления автономными мобильными данными;

· Muzzley, для своего основного хранилища данных.



Заключение

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

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

Однако вскоре выяснилось, что технология MapReduce может быть полезна для самих параллельных СУБД.

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

В процессе выполнения курсовой работы выполнены следующие задачи:

ь Дана оценка технологии MapReduce.

ь Произведён анализ технологии MapReduce.

ь Рассмотрены надёжность технологии MapReduce, её критика, где она используется, её преимущества, реализация и особенности.



Список использованных источников

1. Архитектура ЭВМ и вычислительные системы : учебник / В.В. Степина. -- М.: КУРС: ИНФРА-М, 2017. -- 384 с.

2. Гребенюк, Е. И. Технические средства информатизации [Текст] : учебник для использования в учебном процессе образовательных учреждений, реализующих программы СПО по специальностям "Информационные системы по отраслям", "Программирование в компьютерных системах" / Е. И. Гребенюк, Н. А. Гребенюк. - 6-е изд., перераб. и доп. - Москва : Академия, 2014. - 350 с.

3. Новожилов, О.П. Информатика: учебное пособие для вузов / О.П. Новожилов.- М.: Юрайт, 2017 . - 564с.

4. Партыка Т.Л., Попов И.И. Информационная безопасность. Учебное пособие для студентов учреждений СПО. - М.:ФОРУМ: ИНФРА - М, 2017.

5. Свободно распространяемые программные средства OpenOffice.org Calc и Google: Лабораторный практикум / Клецова Т.В., Прохоров И.В. - М.:НИЯУ "МИФИ", 2011. - 156 с.

Размещено на Allbest.ru

...