Содержание к диссертации
Введение
Глава 1. Анализ моделей и методов моделирования информационных систем и распределенных баз данных 13
1.1 Методы моделирования и архитектура информационных систем 13
1.2 Организация обработки распределенных данных 25
1.3 Технологии моделирования и анализа для оптимизации производительности информационной системы 37
1.4 Средства моделирования информационных систем 38
1.5 Анализ существующих алгоритмов распределения баз данных в информационных системах 42
1.6 Обобщенная постановка задачи распределения реплицированных баз данных в информационной системе 49
Выводы по главе 1 53
Глава 2. Создание моделей распределения реплицированных баз данных 54
2.1 Моделирование репликации данных в системах с дублирующими серверами 54
2.2 Анализ моделей информационных систем с избыточными репликами данных 84
2.3 Комплекс программ моделирования рационального размещения реплик баз данных 90
Выводы по главе 2 94
Глава 3. Разработка алгоритма распределения реплицированных баз данных 96
3.1 Постановка задачи распределения реплицированных баз данных в информационной системе 96
3.2 Генетический алгоритм распределения реплицированных баз данных в информационной системе 114
3.3 Проведение экспериментальных исследований 131
Выводы по главе 3 136
Глава 4. Практическая реализация моделей распределения реплицированных баз данных 138
4.1 Реализация репликации данных в образовательном Интернет-портале Богословского алюминиевого завода 138
4.2 Реализация репликации данных в системе документооборота корпоративной вычислительной сети ЮРГТУ (НПИ) 148
Выводы по главе 4 156
Заключение 157
Список использованной литературы
- Технологии моделирования и анализа для оптимизации производительности информационной системы
- Анализ моделей информационных систем с избыточными репликами данных
- Генетический алгоритм распределения реплицированных баз данных в информационной системе
- Реализация репликации данных в системе документооборота корпоративной вычислительной сети ЮРГТУ (НПИ)
Введение к работе
Моделирование современных информационных систем в качестве одной из ключевых проблем содержит задачу обеспечения качества обслуживания обработке запросов пользователей между различными компонентами системы. При этом под моделью информационной системы понимается адекватная ей схема комплекса программно-технических средств, включающая схему потоков данных между компонентами системы. Эта задача требует создания оптимальной схемы репликации данных, создавая наряду с техническими ограничениями, требования к минимизации стоимости всей системы.
Теоретической базой моделирования информационных систем являются работы ряда отечественных и зарубежных специалистов. Среди отечественных к ним относятся работы Бржезовского А.В., Вишневского В.М., Во-ройского Ф.С., Галахова И.В., Гламаздина Е.С., Новикова Д.А., Цветкова А.В, Зиндера Е.З., Клещева Н.Т., Романова А.А., Кузнецова Н.А., Кульбы В.В., Ковалевского С.С., Косяченко С.А., Тихоненко О.М. Среди зарубежных над данной тематикой работали Буч Г., Гейн К., Сарсон Т., Баркер Р., Лонг-ман Ц., Росс Т., Меллор, Гоуэн К., Марк Д., Йорден И.
Эти работы создают методологическую базу разработки информационных систем на основе заданной предметной области и существующих в организации потоков данных. Однако в настоящее время одним из ключевых факторов создания информационной системы в крупных организациях является разработка оптимальной модели репликационной схемы распределенной базы данных, поскольку крупные компании требуют поддержки высокой актуальности информации в своих филиалах, которые географически удалены друг от друга. Технология репликации необходима для систем, использующихся в областях с высокими требованиями к гарантированной доставке, своевременности и целостности передаваемых данных, таких как системы международных безналичных банковских расчетов, системы обработки дан-
5 ных распределенных технологических процессов реального времени, билин-
говые системы, а также для специализированных корпоративных систем.
Среди отечественных ученых работы по данной проблеме проводили Когаловский М.Р., Филиппов В.А., Цимбал А.А., Аншина М.Л., Шрайберг Я.Л., Мазов Н.А., а среди зарубежных - Коннолли Т., Бегг К., Ролланд Ф., Спирли Э., Столлингс В., Таненбаум Э., Стен М. Ван., Шекхар Ш, Чаула С, Дейт К., Вальдерас П. Однако данная тематика, несмотря на множество разработок моделей тиражирования данных, до сих пор содержит множество нерешенных проблем:
отсутствие моделей распределения баз данных в информационных системах, которые могли бы решить проблему разделения логически интегрированных групп пользователей в рамках однородных потоков данных с учетом дифференцированных требований на скорость обслуживания;
отсутствие методики оптимальной трансформации моделей при добавлении и удалении сервера с реплицированной базой данных;
отсутствие алгоритмов распределения реплик БД и серверов для них в информационных системах, обеспечивающие заданное качество обслуживания запросов пользователей к реплицированным базам данных при минимизации стоимости.
Данные проблемы, а также особенности учета качества обработки запросов пользователей в информационных системах, требующих обеспечения заданного времени обработки отдельных потоков, приводят к необходимости построения соответствующих моделей. Таким образом, существует необходимость в развитии методов композиции и декомпозиции фрагментов информационных систем, которые позволяли учитывать дифференцирован-ность требований пользователей к скорости обработки запросов в рамках однородных фрагментов. Для решения данной задачи, как основы выбора степени репликации распределенной базы данных, необходимо создание комплекса соответствующих моделей и оценка качества их функционировании.
Таким образом, задача разработки моделей распределения реплик БД при моделировании ИС и эффективных алгоритмов их конструирования с учетом дифференцированных требований к скорости обработки различных запросов к реплицированным БД в условиях минимизации стоимости сетевого оборудования является актуальной.
Диссертационная работа выполнена в рамках Федеральной целевой программы "Интеграция науки и высшего образования России на 2002-2006 годы", утвержденной постановлением Правительства РФ № 660 от 5.09.01, научно-технической программы "Научные исследования высшей школы по приоритетным направлениям науки и техники", а также в соответствии с научным направлением Южно-Российского государственного технического университета (НПИ), раздел "Проблемы автоматизации обработки информации в тренажерно-обучающих, информационных и управляющих комплексах" по теме 7.05 «Разработка теоретических основ проектирования корпоративных информационных систем» (утверждено решениями ученого совета ЮРГТУ от 25.04.2001 и 21.03.2006).
Целью диссертационной работы является повышение эффективности функционирования информационных систем, включающих распределенные базы данных, за счет разработки и использования математических моделей распределенных баз данных информационных систем и алгоритмов построения данных моделей, позволяющих создавать информационные системы с заданным временем обработки запросов к реплицированным данным.
Для достижения этой цели в диссертационной работе решаются следующие задачи:
анализ процесса построения модели информационной системы с учетом моделирования распределенной базы данных;
создание аналитико-имитационных моделей для рационального распределения копий баз данных по узлам информационной системы с целью достижения заданного времени обращения пользователей к базам данных;
- определение временных характеристик распределенных баз данных
информационных систем на основе разработанных моделей;
разработка алгоритма для распределения реплицированных баз данных в информационной системе;
проведение апробаций и оценки эффективности разработанных моделей и алгоритмов на основе их программной реализации.
Предметом исследования являются модели распределения реплик баз данных в информационных системах и алгоритмы их конструирования, влияние процесса репликации баз данных на моделирование информационной системы.
Методы исследования и достоверность результатов. В работе использованы методы теории принятия решений, теории систем массового обслуживания, имитационного моделирования, исследования операций, а также методы теории вероятностей и теории генетических алгоритмов.
Достоверность научных результатов и выводов, сформулированных в диссертации, подтверждается согласованием теоретических положений с результатами имитационных экспериментов, расхождение аналитических и имитационных данных не превышало 7-10%, адекватностью результатов моделирования реальным параметрам БД ИС, непротиворечивостью математических выкладок и преобразований.
На защиту выносятся следующие положения:
Математическая модель распределения реплик БД в ИС, отражающая репликационную структуру распределенной базы данных, позволяющая минимизировать затраты на создание информационной системы при рациональном размещении серверов с реплицированными данными.
Метод выбора сервера с реплицированной базой данных на основе данных по его производительности.
Модифицированный генетический алгоритм распределения реплицированных баз данных в информационной системе.
8 Научная новизна диссертационной работы заключается в том, что
сконструирована математическая модель распределения реплик баз данных в информационной системе, отражающая репликационную структуру распределенной базы данных, отличающаяся от известных учетом роли серверов для реплицированной распределенной базы данных, а также учетом наличия территориально распределенных интегрированных клиентских и клиент-серверных множеств. Установлены аналитические зависимости выбора производительности серверов для реплицированных баз данных, отличающиеся от классических методов учетом законов поступления и обработки запросов, производительности серверов, полученной на основе международных тестов, наличием дифференцированных требований пользователей ко времени обработки запросов к реплицированным базам данных. Предложен модифицированный генетический алгоритм конструирования репликационной структуры информационной системы, отличающийся учетом времени обработки запросов в логически интегрированных фрагментах информационной системы и особенностей построения реплицированной структуры распределенной базы данных.
Теоретическая ценность работы заключается в построении и исследовании концептуальных моделей распределения реплицированных БД в ИС и алгоритмов их конструирования с учетом требований по времени обработки запросов и стоимости систем, построении моделей композиции и декомпозиции фрагментов ИС.
Практическая ценность работы состоит в возможности использования разработанных моделей и алгоритмов на разных этапах моделирования распределенных баз данных информационных систем, а также для анализа процессов функционирования существующих информационных систем. Данные модели и алгоритмы позволяют за счет модернизации структуры информационной системы повысить эффективность работы информационных систем в целом, что дает прямой экономический эффект.
Разработанные модели и алгоритмы моделирования применены в процессе разработки информационных систем в ФГНУ ВНИИ "Радуга" (г. Коломна), перспективной системы документооборота ЮРГТУ (НПИ) и образовательного Интернет-портала профессиональной подготовки кадров Богословского алюминиевого завода Сибирско-уральской алюминиевой компании (г. Краснотурьинск). Эти математические модели также используются в учебном процессе на кафедре «Автоматизированные системы управления» Южно-Российского государственного технического университета.
Апробация работы. Основные положения диссертации и отдельные ее результаты докладывались и получили подтверждение на:
III международной научно-практической конференции "Теория, методы проектирования, программно-техническая платформа корпоративных информационных систем" (Новочеркасск, 2003);
научно-технической конференции студентов и аспирантов ЮРГТУ (НПИ) "Студенческая научная весна -2004" (Новочеркасск, 2004);
IV всероссийской научно-практической конференции: "Модернизация системы профессионального образования на основе регулируемого эволюционирования" (Челябинск, 2005);
всероссийской научно-методической конференции: "Открытое образование и информационные технологии" (Пенза, 2005);
научно-технической конференции студентов и аспирантов ЮРГТУ (НПИ) "Студенческая научная весна -2005" (Новочеркасск, 2005);
II международной Интернет-конференции "Информационные и коммуникационные технологии как инструмент повышения качества профессионального образования" (Екатеринбург, 2006);
IV международной научно-практической конференции "Теория, методы проектирования, программно-техническая платформа корпоративных информационных систем" (Новочеркасск, 2006).
Предложенные математические модели и алгоритмы моделирования информационных систем использованы в процессе построения информаци-
10 онной системы ФГНУ ВНИИ "Радуга" (г.Коломна), корпоративной информационной системы ЮРГТУ(НПИ) и образовательного Интернет-портала профессиональной подготовки кадров Богословского алюминиевого завода (г. Краснотурьинск). Разработанные математические модели также внедрены в учебный процесс на кафедре «Автоматизированные системы управления» Южно-Российского Государственного Технического Университета.
Публикации. По результатам выполненных исследований опубликовано 30 научных работ, в том числе 2 свидетельства Роспатента об официальной регистрации баз данных - "Процессно-ориентированная система дистанционного обучения" и свидетельство "Образовательный Интернет-портал для профессиональной подготовки персонала" и 3 свидетельства об официальной регистрации программ для ЭВМ.
Структура и содержание диссертации. Работа содержит 159 страниц основного текста, 37 рисунков, 42 таблицы и состоит из введения, четырех глав, заключения, списка использованной литературы и приложений, содержащих основной код разработанного комплекса программ и акты о внедрении результатов диссертационной работы.
Во введении обоснована актуальность рассматриваемых задач, определена цель работы, рассмотрена структура работы и основные положения, выносимые на защиту.
В главе 1 приводится обзор современных методов моделирования информационных систем, основные понятия распределенных баз данных. Анализируются архитектуры современных информационных систем и современные требования, предъявляемые к моделям и алгоритмам их создания. Формулируется обобщенная постановка задачи моделирования ИС на основе ре-пликационной схемы распределенной базы данных.
В главе 2 предлагается ряд моделей, детализирующих проблемы композиции и декомпозиции фрагментов информационных систем для установки в них серверов репликации с учетом индивидуальных потоков запросов пользователей. Вводится ряд штрафных функций, позволяющих учесть диффе-
ренцированность требований пользователей к обработке данных. Предложенные аналитические и имитационные методы позволяют принимать решения о добавлении или удалении серверов БД в ИС.
В главе 3 предлагается новый метод распределения реплик данных и серверов с реплицированными данными в информационной системе. Конструируется постановка задачи распределения реплик данных в ИС, отличающаяся учетом времени обработки запросов в логически интегрированных фрагментах информационной системы и особенностей построения реплици-рованной структуры распределенной базы данных.
В главе 4 рассматривается применение результатов диссертационной работы при моделировании репликационных схем в системе документооборота Южно-Российского Государственного Технического Университета и в Интернет-портале профессиональной подготовки кадров Богословского алюминиевого завода.
В заключении приведены основные результаты работы.
В приложениях приведены листинги основных функций разработанного комплекса программ, технические характеристики серверов ИС, патенты и акты о внедрении.
В работе используются следующие сокращения и аббревиатуры: БД -база данных, ВС - вычислительная система, ГА - генетический алгоритм, ИС
информационная система, КВС - корпоративная вычислительная система, КИС - корпоративная информационная система, РИС - распределенная информационная система, ЛБмД - локальная база метаданных, ЛБД - локальная база данных, ЛВС-локальная вычислительная система, МГА - модифицированный генетический алгоритм, ООМ - объектно-ориентированное моделирование, ОС - операционная система, ПО - программное обеспечение, РБД - распределенная база данных, СОД - система обработки данных, СМО
система массового обслуживания, СУБД - система управления базами данных, СУРБД - система управления распределенной базой данных, ТП - технический проект, РП - рабочий проект, CASE - средства разработки про-
12 граммных систем, DB - database (база данных), DFD - data flow diagrams
(диаграммы потоков данных), ERD - entity-relationship diagrams (диаграммы сущность-связь), ШЕЕ - institute of electrical and electronics, engineers (Институт инженеров по электротехнике и радиоэлектронике), IP - internet protocol (Интернет протокол), IDEF - ICAM DEFinition (методология моделирования), OSPF - open shortest path first (протокол состояния связей), STD - state transition diagrams (диаграммы переходов состояний), SAP R/3 - система управления предприятием, SADT - structured analysis design technique (технология структурного анализа), SNMP - simple network management protocol (простой сетевой протокол управления), SQL - structure query language (структурированный язык запросов), SUN Solaris - операционная система компании Sun, TCP - transfer common protocol (протокол передачи данных).
Технологии моделирования и анализа для оптимизации производительности информационной системы
В настоящее время для получения характеристик систем используются методы аналитического и имитационного моделирования [40-45]. Эти модели используются для оптимизации работы сетей, причем само функционирование информационной системы рассматривается как синтез множества событий -порождение заявок на обработку от клиентов, выполнение обработки множества запросов на серверах и обслуживание заявок на промежуточных узлах информационной системы.
Аналитическое моделирование позволяет определить характеристики ИС до момента ее ввода в эксплуатацию. Моделирование представляется в определении функциональных зависимостей между входными и выходными характеристиками сети. Его недостатком является необходимость пренебрегать отдельными деталями структуры сети, связанная с требованием построения модели в строгих математических терминах. Как следствие, построенная модель носит вероятностный характер. Эти модели основаны на применении аппарата теории массового обслуживания и марковских процессов и диффузной аппроксимации.
Системы массового обслуживания описываются при помощи классификации Кендалла [40], имеющей вид A/B/V/K/N. Знак А характеризует процесс поступления вызовов, который характеризуется функцией распределения промежутков между вызовами. A=G - означает произвольный закон распределения, A=D - детерминированный, А=М - экспоненциальный, A=R - равномерный. Знак В означает тип распределения времени обслуживания вызовов (с аналогичными буквенными обозначениями), V — число обслуживающих приборов или линий, К — емкость накопителя, N — число источников, создающих поток вызовов.
Если какой-либо из параметров классификации Кендалла является бесконечно большим, то используется соответствующий символ оо, если данные параметры занимают последние места, то этот символ не указывается. Использование данных моделей целесообразно сочетать с имитационными, поскольку они позволяют рассмотреть будущую систему в комплексе, а не в первом приближении.
Имитационное моделирование позволяет в реальном времени отразить процесс функционирования исследуемой системы. Для этого используются специальные среды программирования, отражающие логическую структуру систе мы и процессы, протекающие в ней. Недостатками данных моделей являются их повышенная сложность, трудоемкость и ресурсоемкость при их реализации.
Применяя имитационную модель, разработчик системы сможет обнаружить критические элементы сети и ее характеристики в целом. Задача моделирования системы сводится к задаче формирования модели, отладки моделирующей программы и проверки корректности выбранной модели. Предметно-ориентированные программы направлены на решение конкретной задачи, на основе созданного интерфейса, что снижает их гибкость. Однако ни один из данных пакетов не предусматривает возможность разработки моделей репликации встроенными методами. Такие модели можно строить только на основе собственных программ и моделей.
Для определения базовых принципов работы универсальных пакетов имитационного моделирования рассмотрим систему статистического моделирования GPSS, пакет моделирования Model Vision Studium, систему имитационного моделирования ARENA. Эти программные комплексы являются одними из наиболее часто используемых в процессе моделирования информационных систем.
Система моделирования GPSS (General Purpose Simulating System) специализирована для построения статистических моделей сложных дискретных технических и производственных систем [49]. Эта среда предполагает наличие множества дискретных состояний исследуемой системы, смена которых происходит в определенные моменты, по истечении некоторых промежутков времени, являющихся случайными или детерминированными величинами.
Главным преимуществом данной среды является возможность моделирования очередей разнообразного рода. С помощью этого возможно создание модели движения заявок по информационной системе и ее представление как системы массового обслуживания. Создав алгоритм функционирования системы, визуализируется влияние заданных факторов на систему. Состояние системы массового обслуживания характеризуется состояниями приборов, узлов, источников заявок, транзактов и очередей к приборам, и дисциплин обслуживания этих очередей.
Сформировав имитационную модель СМО, которая отображает поведение СМО, исследователь рассчитывает поведение системы при различных ти 41 пах входных потоков и интенсивностях поступления заявок на входы, при различных характеристиках приборов и различных дисциплинах обслуживания заявок. Варьируя параметры модели, производится расчет статистически достоверных оценок показателей качества функционирования. Эти оценки служат для выработки оптимальной структуры СМО и рациональной схемы работы системы. Однако данная среда не содержит конкретных решений по обеспечению пользователя эффективными алгоритмами моделирования структуры той или иной системы, предоставляя их создание непосредственному разработчику.
Пакет визуального объектно-ориентированного моделирования Model Vision Studium представляет собой интегрированную графическую оболочку быстрого создания интерактивных визуальных моделей сложных динамических систем и проведения с ними вычислительных экспериментов [49-51]. Автором среды является исследовательская группа «Экспериментальные объектные технологии» при кафедре «Распределенные вычисления и компьютерные сети» факультета технической кибернетики Санкт-Петербургского государственного политехнического университета.
Анализ моделей информационных систем с избыточными репликами данных
Модель, рассмотренная далее, необходима для решения задачи, обратной рассмотренной в п.2.1. Процесс перехода к совместно используемому серверу двумя и более независимыми подмножествами клиентов необходимо рассматривать при композиции отдельных фрагментов ИС с целью более рационального использования имеющегося сетевого оборудования.
Рассматривается задача, когда для экономии необходимо провести согласование систем, таким образом, чтобы обе очереди шли к одному прибору (рис.2.8в). Данные системы характеризуются равномерным распределением моментов поступления заявок и экспоненциальным распределением времени обслуживания заявок в приборе.
Исходные системы в общем случае принадлежат к классу G/G/1 и характеризуются соответственными произвольными параметрами. Синтез множества подобных систем в общем случае с произвольными законами генерации и обслуживания заявок при учете дифференцированной оценки качества не позволяет получить точные аналитические выражения для принятия решения (возможны только частные расчеты по разным комбинациям). Поэтому представляется целесообразным использовать имитационный метод решения задачи.
Имитационный метод решения задачи. Пусть в ИС существует 2 фрагмента с собственными серверами БД, характеризующимися индивидуальными параметрами генерации и обработки запросов (табл. 2.21). Необходимо установить возможность их синтеза при условии нахождения в наличии трех серверов с известными параметрами обслуживания заявок (табл. 2.22 и 2.23). Минимальная модельная единица времени задается равной 1мс, модельное время проведения эксперимента равным 500 с (на основе стандартов ШЕЕ [57]), размеры очередей к серверам БД фиксированы.
Комбинируя различные сочетания исходных фрагментов для возмож ного синтеза к общему серверу БД, формируются варианты объединенных фрагментов для их дальнейшей проверки на качество обработки запросов. При этом устанавливается изменение времени на распространение обновления в зависимости от синтезируемых фрагментов (для фрагментов с однородными законами время уменьшается, для неоднородных - увеличивается, увеличивая время обработки).
Также при создании комплекса моделей учтем возможные комбинации синтезированного фрагмента с 3 возможными серверами. Дополнительный штрафной предел определяется следующим образом: количество недопустимых по времени обработки запросов не должно превышать 10 %, а количество потерянных из-за ограниченности размера буфера запросов не должно превышать 5 %. Моделирование производилось в системе статистического моделирования GPSS, на основе разработанной концептуальной модели и приведенных исходных данных.
Распределение времени ожидания обработки запросов по серверам По данным модельных экспериментов, приведенных выше, можно провести анализ потенциальных схем включения серверов БД и принять решение о выборе сервера.
Анализ результатов решения. Представленная модель синтеза двух систем массового обслуживания в одну позволяет интегрировать отдельные компоненты ИС. Данная проблема представляется актуальной при решении задач моделирования ИС в условиях ограниченности серверов необходимой мощности. Анализируя данные по результатам штрафных функций и ограничения, наложенные на них ранее, можно принять решения по допустимости синтеза фрагментов с тем или иным сервером (табл. 2.27). Принятие решений о синтезе фрагментов на основе данных по допустимости распределения времени ожидания необходимо совмещать с данными по ценам включаемых серверов.
Анализируя рассмотренные данные по процессам синтеза фрагментов ИС, возможно принятие решения по выделению избыточных серверов репликации для более рационального использования имеющегося сетевого оборудования. Рекомендуется следующая схема выбора решений: в случае, если сервер №2 имеет меньшую цену, чем сервер №1, и требования к качеству обработки запросов устанавливают допустимое значение потерянных запросов на уровне 5 %, то целесообразна установка сервера №2. В случае, если цены
отличаются незначительно, целесообразен ввод сервера №1. При этом сервер №3 не рассматривается по причине недопустимого распределения времени ожидания обработки запросов.
Представленный график описывает конкретную задачу моделирования. При других исходных данных можно, рассуждая по аналогии, смоделировать пересечение разнородных по характеру генерации запросов от нескольких фрагментов ИС и принять решение о выборе единого сервера. Применение данных рекомендаций позволит обеспечить заданное распределение времени обработки запросов, повышая эффективность введения дополнительных серверов хранения информации при заданном уровне доступности.
Разработанный программный комплекс предназначен для построения и анализа репликационных моделей ИС. В качестве единичной модели распределения реплик для выбора рациональных параметров серверов с реплициро-ванными БД выступает отдельная GPSS программа, содержащая варьируемые параметры интенсивностей запросов от клиентов и изменяемые параметры их обработки на сервере (варьирование может происходить, как на основе жестко заданных пользователем величин, так и на основе аналитически рекомендованных зависимостей). Комплекс разработан применительно к условиям моделирования и расчета фрагментов ИС с реплицированными БД и реализован на базе сред VBA, MS Access, GPSS. С помощью программного комплекса решаются следующие задачи: Расчет рациональных параметров обращений клиентов к серверам баз данных. Анализ текущего состояния системы, выявление узких мест (на основе данных по допустимому времени обработки запросов) и моделирование рекомендаций по их устранению. Моделирование системы с внедряемым сервером с реплицирован-ной базой данных. Моделирование удаления сервера с реплицированной БД из системы (синтез идентичных фрагментов с БД). Расчет допустимой интенсивности обработки запросов на реплици-рованном сервере и части общего потока запросов, направляемой к нему, для обеспечения заданного времени обработки запросов. Программный комплекс состоит из двух частей: 1. Расчетно-аналитический модуль, выполняющий функции анализа и генерации новых репликационных схем, путем выбора рациональных параметров производительности для серверов с реплицированными БД и рационального дробления потоков запросов от пользователей. Модуль реализован в среде Delphi. 2. Моделирующая часть, выполняющая функции имитационного моделирования выбранного фрагмента системы. Работает в среде GPSS World, GPSS - программы хранятся в СУБД Access. В общем виде логическую структуру программного комплекса отображает схема, приведенная на рис. 2.10, схема распределения клиентов и серверов приведена на рис.2.11. В процессе работы комплекса на основании вводимых пользователем исходных данных о параметрах фрагмента ИС и его сервера БД формируются GPSS-программы, являющиеся имитационными моделями выбранных репликационных схем. Они предназначены для имитации процессов композиции и декомпозиции фрагментов ИС, ориентированных на репликацию данных.
Генетический алгоритм распределения реплицированных баз данных в информационной системе
Разработанный алгоритм сконструирован путем отображения множества схем расположения реплик БД в ИС на множество решений - хромосом популяции. Для непосредственной разработки алгоритма вводятся понятия хромосома, ген, популяция, а также оператор случайных изменений [65, 79-83].
Конструирование хромосомы. Поскольку пространство состояний дискретно, предполагается целесообразным выбор двоичного представления структуры хромосомы. Необходимо выполнить конструирование генов для каждой значимой переменной.
При решении задачи учитывается, что оптимизация топологии серверов не производится, т.е. матрица пропускных способностей ps = {ps, у}, отражающая все существующие каналы связи между узловыми фрагментами к, и KSn жестко фиксируется и используется при расчете времени передачи обновлений.
Непосредственная структура хромосомы состоит из генов, образованных соединительными матрицами, а также генов, полученных на основе преобразования множеств индексов элементарных реплик, размещаемых на серверах, rpSj, rpsu , rpKSj в бинарные логические матрицы. При этом генерация генов требует учета того, что сервера S и SU могут быть установлены только в один из узловых фрагментов к или KS, из которых связь с другими фрагментами осуществляется согласно топологической матрице пропускных способностей ps. Кроме того, синтез фрагментов к и KS также производится на основе матрице пропускных способностей ps только в том случае, если данная линия связи существует. Таким образом, возможно формирование множества генов, входящих в хромосому: Поставленная задача при выборе одного из критериев (3.1-3.12) принадлежит к классу комбинаторных задач с инвариантной целевой функцией и переменным количеством ограничений. Решение может быть получено путем выбора из конечного множества возможных вариантов решений. Размерность задачи зависит от количества исходных серверов, которые доступны для установки в качестве серверов БД, и количества однородных по характеру генерации запросов фрагментов ИС. Пространство состояний, определяющее решение, можно записать на основе пересечения осей, детализирующих исходные множества фрагментов ИС и множества неопределенных точек подключения серверов.
Таким образом, задача моделирования ИС ориентированной на поддержку распределенной базы данных, включая механизмы репликации, заключается в создании модели, адекватной существующим в организации потокам данных, которая при этом предоставляла бы возможность манипулирования параметрами ее серверов с репликами данных и направлений альтернативных потоков информации на основе заданных требований к качеству обработки запросов.
Для выбора метода решения необходимо провести расчет количества возможных вариантов решений V и сконструированного набора критериев. Исходя из того, что переменные задачи являются булевыми, и, анализируя матрицы переменных вместе с постановкой задачи, количество вариантов решений можно определить при репликации полной БД V = 2d r+d q+dz+zr+2 q, а при дроблении исходной базы данных на реплики V = 2 я +,г+2.д).{г+д+г).м.
Анализ критериев показывает возможность адаптации задачи к ее решению стандартными методами ветвей и границ или итерационными методами. Однако такая постановка задачи ставит ее в класс трудноразрешимых по причине «проклятия размерности» [65-72]. Поэтому представляется более целесообразным использовать для решения модифицированный генетический алгоритм.
Для решения подобных задач либо вводят допущения при уменьшении размерности и дальнейшем сведении к базовым задачам комбинаторной оптимизации, либо разбивают задачи на этапы с индивидуальными подзадачами и целевыми функциями. Задачи с подобными постановками задачи конструирования рациональной репликационной модели ИС рассматривались в ряде работ [29-33, 73-79], но рассмотренные в данных исследованиях подходы характеризуются либо чрезмерной трудоемкостью и длительностью, либо значительными допущениями в ходе решения. В отличие от них приведенная постановка характеризуется учетом сформировавшихся на более раннем этапе фрагментов ИС (это необходимо, прежде всего, при повторном моделировании и развитии существующих систем), а также учетом существующего серверного оборудования.
Результаты решения данной задачи синтеза позволят: определить места включения вакантных серверов БД в фрагменты с множеством клиентов; установить дополнительные репликационные сервера БД в уже сформированные клиент-серверные фрагменты ИС для повышения скорости обработки запросов, найти оптимальные точки установки и подключения серверов, поддерживающих распространение обновлений и глобальную целостность данных в рамках всей РБД, а также схему распределения реплик данных.
Основным критерием эффективности определен минимум интегрированной функции времени обслуживания, а ключевыми ограничениями - размеры памяти, предоставляемой на серверах для размещения БД, стоимость подклю 114 чаемых серверов, а также время обработки запросов на уровне отдельных фрагментов ИС.
На основе постановки задачи конструирования модели ИС путем оптимального размещения реплик баз данных и выбора рациональных характеристик серверов БД, заключающейся в анализе комбинаторных вероятностей точек подключения вакантных фрагментов ИС друг к другу, можно разработать эффективный алгоритм решения. Рациональным подходом при решении данной задачи представляется применение современных алгоритмов поиска, таких как генетические алгоритмы (ГА) [79-88]. Данный класс алгоритмов базируется на организации эволюционного процесса, запуск которого позволяет получить оптимальное, или близкое оптимальному, решение комбинаторной задачи большой размерности.
Создание ГА включает установку законов эволюции для оптимизации времени получения решения [89-101]. Генетические алгоритмы применяются при решении многих NP-трудных задач и являются адаптивными поисковыми методами. Они не предъявляет требований к виду функционала и ограничений, и предоставляют возможность использования целевой функции в процессе оптимизации, а не её оценок или приближений. Работа ГА заключается в обработке множества альтернативных решений, формируя вектор поиска в ориентации на перспективные с точки зрения используемого функционала и ограничений варианты решений.
Схемы реализации ГА подразделяются на классические - "двухродитель-ский кроссинговер - двухродительская рекомбинация" и на схемы с самоорганизацией, в которых осуществляется выбор и настройка операторов случайных изменений, наряду со стратегией выбора родительских пар.
Реализация репликации данных в системе документооборота корпоративной вычислительной сети ЮРГТУ (НПИ)
Топология КВС ЮРГТУ (НПИ) состоит из нескольких сегментов. Основным является сегмент КВС базового вуза, состоящий из корпусных ЛВС, объединяющих их магистральных каналов. Выход КВС и отдельных подразделений университета в сеть internet осуществляется по выделенному 4-х проводному телефонному каналу через Новочеркасский узел электросвязи, по высокоскоростному каналу между ЮРГТУ (НПИ) и ЮГИНФО РГУ и по коммутируемым телефонным каналам. Логическая структура корпоративной сети ЮРГТУ (НПИ) - звезда, ядро которой расположено в вычислительном центре, который размещается в корпусе энергетического факультета. Магистральная сеть построена на основе технологии Gigabit Ethernet, среда передачи - оптический кабель (4-х жильный MMF).
Центральным коммутационным устройством сети ЮРГТУ (НПИ) является коммутатор 3Com 4900SX, к которому подключены 6 корпусных устройств 3Com 3300SM посредством оптических кабелей, соединяющих корпуса. Технические характеристики коммутатора 3Com 4900SX приведены в приложении 4. При этом пропускная способность линия связи между корпусами центрального вуза составляет 1 ГГб/с, между центральным вузом и филиалами 2 Мбит/с. Центральными устройствами корпусов являются коммутаторы 3Com 3300SM.
Коммутационное оборудование магистральной сети составляют коммутаторы 3Com 3300SM, по одному коммутатору в каждом корпусе. В составе КВС можно выделить набор подсистем документооборота, доступа в Интернет, кадров, абитуриент и другие. Одной из важнейших является система документооборота. Однако объемы баз данных постоянно увеличиваются (это связано с накоплением данных о сотрудниках и студентах, расширением сети филиалов, а также формированием множества внутренних документов). При этом требуется обеспечить синхронизацию и актуальность данных, находящихся в различных филиалах и в центральном вузе.
Современные системы документооборота являются центрами оперативного движения данных внутри организаций [109-119]. Данные системы должны непрерывно реагировать на изменения интенсивностей потоков информации и своевременно перераспределять их между пользователями. В ЮРГТУ при разработке корпоративной системы разработчики столкнулись с проблемой репли 150 кации данных в распределенной системе, подсистемы которой расположены в различных подразделениях и филиалах вуза (филиалы расположены в городах Шахты, Каменск-Шахтинский, Волгодонск, Белая Калитва и других). Система автоматизации делопроизводства поддерживает формирование документов во всех подразделения вуза: в подсистеме "абитуриент" - электронное автоматизированное ведение личных дел абитуриентов и студентов вуза с информацией о ходе набора абитуриентов и конкурсах на специальностях, в подсистеме "расписание" - создание учебных и рабочих планов специальностей и индивидуальных планов преподавателей с расписанием занятий, формирование графика учебного процесса, в подсистеме "касса" - формирование платежных ведомостей.
Существующая система реализована на базе стандартной двухуровневой архитектуры «сервер БД - клиент», в которой сервером БД является MS Sql Server, в а клиентом - система 1С, репликация моделируется на уровне серверов БД. При этом модель для реализации функциональности современных ИС также должна учитывать проблемы возможного дублирования работы в разных подразделениях при доступе к единой РБД [120-125].
При разработке модели учтем, что первичные данные (а соответственно и менеджеры журналы транзакций и центральные репозитории) находятся в хранилищах шаблонов и документов, физически расположенных в центральном вузе. В филиалах репликационные сервера создают подписки на соответствующее описание тиражирования. По информации журнала транзакций происходит изменение данных на всех репликационных серверах, в соответствии с установленными подписками (рис. 4.8).
Рассмотрим процесс выбора серверов с реплицированными БД для схемы тиражирования с децентрализацией задач с синхронным распространением обновлений, в которой на серверах центрального вуза и в филиалов выполняются те запросы, которые связаны с непосредственным ведением кадрового и бухгал 151 терского учета (зависящие от числа студентов и преподавателей).
Модель РБД ЮРГТУ Требуемое время обработки запросов во всех филиалах установлено равным 0,1 с (согласно ISO/IEC WD 9579, ISO/IEC 9945, IEEE POSIX Realime [57]). Задержки передачи пакетов t3 к филиалам определены на основе проведения комплекса экспериментальных исследований по трассировке к городам филиалов и их внутренним линиям связи с использованием программного пакета Visual Route [126] для анализа всех задержек IP-пакетов, а географическое ме 152 стоположение определено на основе использования БД IpGeoBase [127]. На основе данных задержек, среднего размера реплики и = 60 Кб (средний размер документа) и вероятности модификации данных при обращении к БД p = \s% (на основе статистических отчетов) рассчитывается множество времен передачи обновлений для филиалов (филиалы находятся на разных расстояниях и линии связи характеризуются индивидуальными задержками) (табл. 4.4). При этом об„,і =P, " среднее время, определенное на основе вероятностного подхода, а на основе /06н2=/3 (среднее время, определенное на основе максимальных требований к быстроте синхронизации данных) рассчитывается дополнительный критерий 7 2=7 ,,-/,, который из-за задержек на синхронизацию, превышающих 0,1 с, рассчитан в качестве альтернативного критерия rma„=250 мс.
Далее, на основе аналитических зависимостей, приведенных в главе 2, статистической интенсивности запросов к серверам БД в филиалах, параметров линий связи, приведенных в табл.4.4, считая, что законы генерации и обработки запросов являются экспоненциальными, определяются (табл. 4.5, 4.6) параметры реплицированных серверов. При этом в качестве сервера-издателя, контролирующего процесс репликации, в модели учитывается существующий сервер HP ProLiant ML370 G3 отдела бухгалтерии ЮРГТУ (БД Microsoft SQL Server) с производительностью /4а равной 54096 транзакций в минуту или 901,6 транзакций в секунду (по тесту ТРС-С[106]).
Интенсивность множества поступающих запросов в центральном вузе от отделов кадров и бухгалтерии определена на основе статистических данных, собранных пакетом StatWin Enterprise, а также анализа журнала транзакций SQL-сервера, а для филиалов - на основе делегирования им соответствующих операций, рассчитываемых пропорционально количеству преподавательского состава и студентов.
