Организация распределенного хранилища, оптимизированного под статический анализ (1187410)
Текст из файла
Министерство образования и науки Российской ФедерацииФедеральное государственное автономное образовательное учреждение высшего профессионального образования«Московский физико-технический институт(государственный университет)»Факультет управления и прикладной математикиКафедра теоретической и прикладной информатикиОРГАНИЗАЦИЯ РАСПРЕДЕЛЕННОГО ХРАНИЛИЩА,ОПТИМИЗИРОВАННОГО ПОД СТАТИСТИЧЕСКИЙ АНАЛИЗВыпускная квалификационная работа(магистерская диссертация)Направление подготовки: 03.04.01 Прикладная математика и физикаВыполнила:студентка 973 группы ___________ Алексеева Мария АндреевнаНаучный руководитель:д.ф.-м.н., профессор_________ Тормасов Александр ГеннадьевичНаучный консультант:_______ Непорада Андрей ЛеонидовичМосква 2015ОглавлениеВведение ...........................................................................................................
41. Постановка задачи...................................................................................... 51.1. Распределенные хранилища ............................................................... 51.1.1. Традиционное хранилище данных ...............................................
51.1.2. Big data ............................................................................................ 91.1.3. NoSQL ............................................................................................ 101.1.4. Map-Reduce (Hadoop) ................................................................... 111.2. Статистический анализ.......................................................................
131.2.1. Основные методы статистического анализа .............................. 131.2.2. Репрезентативная выборка и статистический анализ................ 161.3. Статистический анализ в распределенном хранилище и постановказадачи .......................................................................................................... 172. Математическая модель ..........................................................................
192.1. Формализация задачи ....................................................................... 192.2. Критерии однородности .................................................................... 193. Создание модели хранилища .................................................................. 233.1.
Модель распределенного хранилища .............................................. 233.2. Модуль распределения данных ........................................................ 243.3. Модуль контроля репрезентативности данных ............................... 253.4. Алгоритм случайного распределения данных ................................. 253.5.
Собственный алгоритм распределения данных .............................. 263.6. Вычисление функции распределения хи-квадрат............................ 283.7. Проблема заполнения пустого хранилища ...................................... 303.8. Оптимизация алгоритма распределения данных ............................ 304. Результаты проведенных тестов ................................................................ 334.1. Тесты для случайного распределения ................................................ 334.2. Тесты для собственного алгоритма распределения .......................... 395.
Расширение задачи .................................................................................. 465.1. Репрезентативность по двум и более распределениям на одномузле 465.2. Репрезентативность двух и более измерений на разных узлах ...... 48Заключение ..................................................................................................... 49Список литературы .........................................................................................
50ВведениеДанная работа посвящена вопросу организации распределенного хранилища, оптимизированного под статистический анализ. Впоследнее время широко востребована тема хранения большихобъемов данных, предназначенных не для быстрого доступа, а дляанализа в практике принятия бизнес-решений. Именно для этой задачи служат хранилища (data warehouses). Когда количество данных становится особенно большим, данные все сложнее хранить водном месте, а операции над ними занимают значительно большеевремя.
Тогда выбор делается в сторону распределенного хранилища, которое позволяет не только оптимизировать хранение большого объема данных, но и улучшить скорость анализа данных засчет распараллеливания работы над ними.Вид анализа, производящегося над данными, зависит от целии задач принятия решений. В данной работе рассмотрен статистический анализ. Этот вид анализа обладает одним важным свойством: результат анализа, произведенного над репрезентативнойвыборкой из всех данных, будет совпадать с результатом этого жеанализа над всеми данными. Именно это свойство лежит в основеподхода к организации нашего хранилища, оптимизированного подстатистический анализ.1. Постановка задачиВ этой главе ведется обсуждение постановки самой задачи, рассматриваются проблемы и вопросы, связанные с возможным решением, а такжеприводится краткая теория, касающаяся распределенных хранилищ данных и статистического анализа.1.1.Распределенные хранилищаПрежде чем говорить о распределенных хранилищах данных, следует рассмотреть классическое хранилище, как общий случай хранения данных.1.1.1.
Традиционное хранилище данныхТрадиционное хранилище данных — это предметно-ориентированнаябаза данных, предназначенная для подготовки отчетов и бизнес-анализа[1]. Обычное хранилище строится на базе систем управления базами данных и систем поддержки принятия решений. Данные, поступающие в хранилище, доступны только для чтения и анализа. Выделяется 4 основныхпринципа организации хранилища [1]:1.
Проблемно-предметная ориентация: данные хранятся в соответствии с областями, которые они описывают;2. Интегрированность: данные удовлетворяют всем требованиямпредприятия в целом;3. Некорректируемость: данные в хранилище не корректируютсяи не удаляются;4. Зависимость от времени: данные корректны только в том случае, когда они привязаны к определенному промежутку и моменту времени.Схема организации традиционного хранилища представлена на рис.
1 [2].Рисунок 1. Стандартная архитектура традиционного хранилища данныхВ организации хранилища выделяется пять уровней [2]:• Уровень сбора данных состоит из модулей для получения данных отсистем-источников, но не занимается обработкой и распределением;• Уровень интеграции данных интегрирует данные для передачи науровень хранения данных от источника (от уровня сбора данных);• Уровень хранилища данных получает данные от уровня интеграциии хранит их согласно выбранной модели;• Аналитический уровень представляет данные в формате куба дляупрощения анализа пользователем;• Уровень представления – это приложения или порталы, отображающие данные в читабельном и удобном для анализа виде для пользователя посредством, например, веб-страниц.Существуют два архитектурных направления в организации хранилищаданных — нормализованные хранилища данных и хранилища с измерениями.
В нормализованных хранилищах данные находятся в предметно-ориентированных таблицах третьей нормальной формы. В таких хранилищахесть определенное достоинство — простота создания и управления, однако их недостатком является большое количество таблиц (как следствиенормализации).Хранилища с измерениями используют схему «звезда» (рис. 2) или схему«снежинка» (рис. 3). При этом в центре «звезды» находятся данные, а измерения образуют лучи. Различные таблицы фактов совместно используюттаблицы измерений, что значительно облегчает операции объединенияданных из нескольких предметных таблиц фактов. Достоинства данной архитектуры — это простота и понятность для разработчиков, пользователейи скорость доступа к данным при сложном анализе.
Недостатками же являются более сложные процедуры подготовки и загрузки данных, а такжеуправление и изменение измерений данных.Рисунок 2. Схема организации хранилища "звезда"Рисунок 3. Схема "снежинка"Основными источниками данных для хранилища являются традиционныесистемы регистрации операций, отдельные документы, наборы данных.Так же стоит отметить, что если хранилище используется в исследователь-ской работе, а не только в бизнесе, источниками могут быть записи показаний некоторых приборов или записи об исследовании некоторых объектов.
Таким образом, вид данных, поступающих в хранилище для анализа ихранения, определяется областью их применения.В хранилище над данными возможны следующие операции:• Извлечение — перемещение информации от источников данных вотдельную БД, приведение их к единому формату;• Преобразование — подготовка информации к хранению в оптимальной форме для реализации запроса, необходимого для принятия решений;• Загрузка — помещение данных в хранилище, производиться атомарно, путем добавления новых фактов или корректировкой существующих;• Анализ: OLAP, Data Mining, сводные отчеты;• Представление результатов анализа.Однако в последнее время в области обработки данных происходят значительные изменения, приводящие к новым требованиям к организации хранилищ: объем данных, как и частота их поступления, растут; повышаетсяспрос на ресурсоемкие вычисления. Так как основной проблемой этих требований является большой объем данных, то область технологий, работающая с этими требованиями, называется «большие данные» (big data).1.1.2.
Big dataОдной из технологий, работающей в рамках задачи «big data», являетсяраспределенное хранилище. Такие хранилища данных представляют собой архитектуру клиент-сервер, где клиент – это уровень интеграции ипредставления, а сервер – набор узлов, осуществляющих хранение данныхи выполняющих вычисления над этими данными. Такая организация хранилища позволяет хранить как можно большие объемы данных и легкомасштабироваться в случае переполнения узлов путем добавления новогоузла, а также производить параллельный анализ над данными на каждомузле, предоставляя ресурсоемкие и точные вычисления.Граница области применения традиционного и распределенного хранилищ сильно размыта. Но рекомендуется переходить к решению задачибольших данных, когда существенны [2]:•необходимость анализировать данные из новых источников;•повышение сложности данных (разнообразие типов данных; объемыданных; скорость создания данных; достоверность данных, поступающих из нескольких источников);•усложнение задач анализа;•растущая доступность экономически эффективных вычислительных;средств и систем хранения данных.В решении задачи хранения и анализа больших данных можно выделитьдва основных подхода: NoSQL и Map-Reduce (Hadoop).1.1.3.
NoSQLРассматривать NoSQL подход необходимо в сравнении с подходом использования реляционной базы данных. Известно [4], что стандартная реляционная база данных не обладает существенным для решения вопроса bigdata свойством – масштабируемостью. NoSQL выгодно отличается на фонеRDBMS именно благодаря своей высокой производительности и гибкойобработке больших масс данных. Это достигается за счет отказа от высокой структурированности, присущей реляционным базам данных.Хранилища данных, построенных на системе NoSQL, подразделяют на следующие типы [5]:• Хранилище «ключ – значение» используется для хранения изображений, создания специализированных файловых систем, в качествекэшей для объектов и в системах, спроектированных с прицелом намасштабируемость.• Хранилище семейств колонок (или Bigtable-подобные базы данных), где данные хранятся в виде разреженной матрицы, строки истолбцы которой используются как ключи.• Документно-ориентированные СУБД служат для хранения иерархических структур данных, используются в системах управления содержимым, документальном поиске и т.п.• Базы данных на основе графов применяются для задач, в которыхданные имеют большое количество связей: социальные сети и прочее.Помимо NoSQL существует и другой подход – MapReduce парадигма, о которой будет рассказано в следующем пункте.1.1.4.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.