Пространство имён файловой системы

Министерство образования республики Беларусь

Учреждение образования

Белорусский государственный университет информатики и радиоэлектроники

Факультет компьютерных систем и сетей

Кафедра информатики

Дисциплина: Архитектура вычислительным систем

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к курсовой работе

на тему

«Решение задачи мультиклассификации научных статей с применением кластера Apache Spark»

Студент: гр.353502 Метлицкий Е.А.

Руководитель: Плехова Т.В.

Минск

Оглавление

Оглавление. 2

1 Введение. 4

2 Получение обучающей выборки. 5

3 HDFS. 6

3.1 Введение. 6

3.2 Предположения и цели. 6

3.2.1 Устойчивость к отказам аппаратного обеспечения. 6

3.2.2 Потоковый доступ к данным.. 6

3.2.3 Большие объёмы данных. 6

3.2.4 Простая модель согласованности. 6

3.2.5 "Перемещение вычислений дешевле перемещений данных". 7

3.2.6 Кроссплатформенность. 7

3.3. Архитектура. 7

3.4. Пространство имён файловой системы.. 8

3.5. Репликация данных. 9

3.5.1 Распределение реплик. 9

3.5.2 Выбор реплик. 10

3.5.3 Защищённый режим.. 10

3.6. Постоянность метаданных файловой системы.. 11

3.7. Протоколы взаимодействия. 11

3.8. Устойчивость. 11

3.8.1 Отказы дисков, heartbeat и процесс перереплицирования. 12

3.8.2 Перебалансировка кластера. 12

3.8.3 Целостность данных. 12

3.8.4 Отказ хранилища метаданных. 12

3.9.Организация данных. 13

3.9.1 Блоки данных. 13

3.9.2 Staging. 13

3.9.3 Replication Pipelining. 13

5 Классификатор. 15

5.1. Задача мультиклассовой классификации. Наивный Байесовский классификатор. 15

5.2. Проблема арифметического переполнения. 16

5.3. Проблема неизвестных слов. 16

6 Предобработка данных. 18

7 Отбор признаков. 19

7.1 TF-IDF. 19

7.2 Алгоритм выявления важных признаков, основанный на TF-IDF. 19

7.3 Алгоритм выявления важных признаков, основанный на деревьях решений. 20

8 Преобразование классов. 21

9 Список литературы.. 23

10 Приложение 1. Исходный код. 24

10.1 Предобработка данных. 24

10.2 Метрики. 27

10.3 Наивный байесовский классификатор. 28

10.4 Построение модели. 28

10.5 Кросс-валидация. 29

Введение

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

Актуальность проблемы обусловлена стремительным ростом объема информации в мире. Обработка больших данных является одной из самых развивающихся направлений в IT-индустрии, а следовательно увеличивается востребованность навыков работы с системами хранения и обработки больших объёмов данных.

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

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

Получение обучающей выборки

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

Обучающий набор должен удовлетворять следующим требованиям: каждому объекту должен соответствовать один и более классов и всё множество предсказываемых классов должно быть покрыто.

В качестве обучающей выборки были выбраны статьи интернет-ресурса технического содержания http://habrahabr.ru, отнесенные к одному или более разделам и помеченные тэгами.

«"Хабрахабр" одинаково интересен программистам и разработчикам, администраторам и тестировщикам, дизайнерам и верстальщикам, аналитикам и копирайтерам, владельцам крупных компаний и небольших стартапов, менеджерам, а также всем тем, для кого IT — это не просто две буквы алфавита.»[1]

Было принято решение написания программы на языке C# для выкачивания статей.

Принцип работы программы:

– Выкачивание одной веб-страницы (статьи) представляется как одна задача.

– Создаётся пул потоков, запускающий задачи и регулирующий количество одновременно выполняющихся задач.

– После завершения выкачивания к каждой задаче прикрепляется задача разбора html-страницы с использованием библиотеки Html Agility Pack и регулярных выражений в объект статьи, содержащий название, текст, номер, хабы, тэги, комментарии, и сохранения их в базу данных.

– Объекты статей сохраняются в базу данных блоками.

– Общее время работы программы – 72 часа

HDFS

Введение

HDFS – распределённая файловая система (РФС), разработанная для запуска на серверах среднего уровня. Имеет много общего с существующими РФС, однако имеет значительные различия. HDFS имеет высокую отказоустойчивость и спроектирована для запуска на серверах нижнего ценового диапазона. Обеспечивает высокую пропускную способность данных и подходит для приложений, оперирующих большими объёмами данных. Изначально HDFS была построена в качестве инфраструктуры для Apache Nutch – поисковый движок. На сегодняшний день HDFS является проектом Apache Hadoop.

Предположения и цели

Устойчивость к отказам аппаратного обеспечения

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

Потоковый доступ к данным

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

Большие объёмы данных

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

Простая модель согласованности

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

3.2.5 "Перемещение вычислений дешевле перемещений данных"

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

Кроссплатформенность

HDFS была разработана для легко переноса с одной платформы на другую. Это облегчает широко распространённое принятие HDFS как предпочтительной платформы для большого набора приложений.

Архитектура

NameNode-сервер и DataNode-сервер

HDFS имеет master/slave архитектуру. HDFS кластер состоит из единственной NameNode, master-сервера, которая управляет пространством имен файловой системы и регулирует доступ к файлам со стороны клиентов. В дополнение, существует множество DataNode-серверов, обычно один на физическую машину, который управляет хранилищем данных на конкретном узле. HDFS предоставляет пространство имен файловой системы и позволяет пользователям хранить данные в файлах. Внутри файлы разбиты на один и более блоков и эти блоки хранятся на множестве DataNode-серверов. NameNode-сервер выполняет операции над пространством имен файловой системы, такие как открытие, закрытие и перемеименование файлов и директорий. Он также определяет отображение блоков на DataNode-сервера. DataNode-сервера отвечают за обработку запросов от клиентов на чтение и запись. DataNode-серверы также ответственны за создание, удаление и реплицирование блоков по инструкциям поступающим от NameNode-сервера.

NameNode-сервер и DataNode-сервер являются частью программного обеспечения разработанного для запуска на серверах народного потребления. Такие машины обычно работают под управлением операционной системы GNU/Linux. HDFS разработана на языке программирования Java; HDFS может быть запущен на любой машине поддерживающей Java. Типичный сценарий развертывания имеет единственный сервер предназначенный исключительно для выполнения NameNode-сервера. Все остальные сервера в кластере выполняют по одному экземпляру DataNode-сервера. Архитектура не препятствует запуску нескольких экземпляров DataNode-сервера на одной машине. Однако в реальных сценариях развёртывания это редкий случай.

Существование единственного NameNode-сервера в кластере значительно упрощает архитектуру системы. NameNode-сервер является и арбитром и репозиторием для всех метаданных. Система разработана таким образом, что поток пользовательских данных не проходит через NameNode-сервер.

Пространство имён файловой системы

HDFS поддерживает традиционную иерархическую организацию данных. Пользователь или приложение может создавать директории и сохранять файлы внутри них. Иерархия пространства имён файловой системы схожа с большинством других файловых систем; имеется возможность создавать и удалять файлы, перемещать их из одной директории в другую и переименовывать. На данный момент HDFS не поддерживает пользовательские квоты. HDFS не поддерживает символические и жёсткие ссылки [2]. Тем не менее архитектура позволяет реализовать эти функциональные возможности.

NameNode-сервер поддерживает пространство имён файловой системы. Любое изменение пространства имён файловой системы или его свойства фиксируется NameNode-сервером. Приложение может определять количество реплик (копий) файла, которые должно поддерживаться HDFS. Количество копий файла называется уровнем репликации. Информация об этом сохраняется на NameNode-сервере.

Репликация данных

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

NameNode-сервер принимает все решения, касающиеся репликации блоков. Он периодически получает heartbeat и отчет о блоках от каждого DataNode-сервера в кластере. Получение heartbeat от DataNode-сервера свидетельствует о его корректной работе. Отчет о блоках содержит список всех блоков DataNode-сервера.

Распределение реплик

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

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

NameNode-сервер определяет Id стойки для каждого DataNode-сервера. Простейшей, но не оптимальной политикой является размешенный реплик на разных стайках. Это предотвращает потерю данных, когда отказывает вся стойка и позволяет использовать пропускную способность нескольких стоек при чтении данных. Эта политика равномерного распределения реплик на кластере делает легкой балансировку нагрузки при отказе компонентов. Тем не менее эта политика увеличивает стоимость записи из-за того, что запись требует перемещения блоков между различными стойками.

В общем случае, когда уровень репликации равен трём политика размещения реплик HDFS заключается в расположении реплик на DataNode-серверах трёх разных стоек. Эта политика уменьшает трафик внутри стойки, а это как правило увеличивает производительность записи. Вероятность отказа стойки целиком значительно меньше чем вероятность отказа одного узла; эта политика не оказывает влияния на гарантии надежности и доступности. Такая политика уменьшает совокупную сетевую пропускную способность при чтении данных. С этой политикой реплики файла неравномерно распределяются между стойками. Такая политика увеличивает производительность записи без ущерба надёжности и производительности чтения.

Выбор реплик

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

Защищённый режим

Во время запуска NameNode-сервер входит в специальное состояние, называемое защищённым режимом. В этом состоянии не производится реплицирование. NameNode-сервер получает heartbeat и отчёт о состоянии блоков каждого DataNode-сервера. Отчёт о блоках состоит из списка блоков данных, размещённых на DataNode-сервера. Каждый блок имеет определённый минимальный набор реплик. Состояние блока является безопасным, если количество его реплик соответствует его уровню репликации. После проверки необходимого уровня репликации NameNode-сервер (с задержкой 30 секунд) выходит из защищённого режима. Формируется список блоков, имеющих недостаточное количество реплик. Затем NameNode-сервер начинает репликацию недостающих данных.

Не нашли, что искали? Воспользуйтесь поиском по сайту: