Организация распределенного хранилища, оптимизированного под статический анализ

Министерство образования и науки Российской ФедерацииФедеральное государственное автономное образовательное учреждение высшего профессионального образования«Московский физико-технический институт(государственный университет)»Факультет управления и прикладной математикиКафедра теоретической и прикладной информатикиОРГАНИЗАЦИЯ РАСПРЕДЕЛЕННОГО ХРАНИЛИЩА,ОПТИМИЗИРОВАННОГО ПОД СТАТИСТИЧЕСКИЙ АНАЛИЗВыпускная квалификационная работа(магистерская диссертация)Направление подготовки: 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.