Содержание к диссертации
Введение
ГЛАВА 1. Обзор и анализ методов автоматизации проектирования распределенных систем и баз данных 9
1.1 Характеристики распределенных систем 9
1.1.1 Прозрачность 9
1.1.2 Открытость 12
1.1.3 Гибкость 12
1.1.4 Масштабируемость 13
1.2 Концепции программных решений 14
1.3 Распределенные базы данных 16
1.3.1 Разновидности распределенных СУБД. 19
1.4 Проектирование базы данных 20
1.4.1 Моделирование локальных представлений 21
1.4.2 Объединение локальных моделей 23
1.4.3 Средства автоматизированного проектирования 24
1.5 Построение модели данных 25
1.5.1 Иерархическая модель 25
1.5.2 Сетевая модель 26
1.5.3 Реляционная модель 26
1.5.4 Модель «Сущность-связь» 26
1.5.5 Многомерная модель данных 27
1.5.6 Объектно-ориентированная модель 27
1.6 Объектные базы данных 30
1.7 Проектирование распределенных БД 31
1.7.1 Проектирование распределенных ООБД 32
1.7.2 Терминология 33
1.8 Фрагментация данных 33
1.9 Размещение данных 37
1.10 Репроекгирование и материализация 39
1.11 Обзор и анализ существующих работ 41
1.11.1 Фрагментаі\ия 42
1.11.2 Размещение 43
1.12 Заключение по главе 1 46
ГЛАВА 2. Разработка моделей распределенных баз данных ... 47
2.1 Выбор и обоснование критерия эффективности 48
2.2 Коэффициент использования ресурсов 50
2.3 Время ответа на запрос 52
2.4 Распределенное исполнение запроса 52
2.4.1 Время исполнения оператора 55
2.4.2 Обновление данных 60
2.4.3 Операция соединения (join) 63
2.5 Расчет временного коэффициента 64
2.6 Заключение по главе 2 68
ГЛАВА 3. Алгоритм решения задачи проектирования распределенной базы данных 69
3.1 Сложность решаемых задач 69
3.2 Генетический алгоритм 71
3.3 Обоснование эффективности генетического алгоритма 73
3.3.1 Теорема шаблонов 75
3.4 Применение генетического алгоритма для решения задачи проектирования РБД 76
3.4.1 Формирование схем фрагментации и размещения 78
3.4.2 Формирование стратегии исполнения запроса 81
3.4.3 Функция приспособленности и критерий останова 84
3.5 Заключение по главе 3 88
ГЛАВА 4. Практическая реализация и результаты исследования 89
4.1 Описание входных данных 89
4.1.1 Логическая модель базы данных 90
4.1.2 Типы данных и структура таблиц 91
4.1.3 Транзакции 93
4.2 Схема фрагментации 95
4.3 Параметры генетического алгоритма 96
4.3.1 Скрещивание 96
4.4 Влияние на работу алгоритма характеристик сети и весовых коэффициентов критерия эффективности 98
4.5 Анализ полученных результатов 99
4.6 Исследование эффективности алгоритма 100
4.7 Заключение по главе 4 104
Заключение 105
Список литературы
- Масштабируемость
- Модель «Сущность-связь»
- Коэффициент использования ресурсов
- Обоснование эффективности генетического алгоритма
Введение к работе
Актуальность темы. Технологии баз данных (БД) в настоящее время используются практически во всех организациях. Следствием возрастающей сложности средств измерения, обработки и представления информации, конструируемых в приборостроении, является увеличение потребностей в управлении все большими объемами информации. Это приводит к том)', что размеры БД превосходят физические ограничения централизованных систем. Все большую значимость приобретают процессы децентрализации, требующие создания приложений, доступ к которым осуществляется из различных географических местоположений. Увеличиваются требования к оперативности и достоверности информации. Задачи информационной интеграции БД и проектирования географически распределенных БД (РБД) являются наиболее актуальными для разработчиков программного обеспечения в течение почти трех десятилетий.
Процесс проектирования прибора или устройства состоит из ряда этапов. Каждый этап, помимо обладания собственной локальной информацией, имеет определенные информационные связи с другими этапами. Например, такие этапы как проектирование конструктивно-функциональных узлов, моделирование работы устройства, построение контролирующих тестов разделяют общие данные (например, элементную базу устройства, информацию о способах использования и т.п.), т.е. каждый этап информационно связан с центральной базой данных, содержащей общие данные.
Базы данных занимают центральное место в автоматизированных информационно-управляющих системах (АИУС). От эффективности и качества их построения во многом зависит эффективность разрабатываемых информационных систем. Поэтому разработка систем
автоматизированного проектирования (САПР) БД является важной и актуальной задачей.
Для достижения высокой производительности распределенных приложений, работающих с базами данных, необходимы эффективные методы проектирования РБД.
Целью работы является разработка методов проектирования распределенной базы данных, которые описывают способ разбиения централизованной БД на фрагменты и размещения полученных фрагментов в узлах заданной вычислительной сети (ВС). На основании полученных методов необходимо создать алгоритмы автоматизированной системы, результатами работы которой, помимо схем фрагментации и размещения БД, будут рекомендации по повышению эффективности обработки запросов к РБД.
Для достижения указанной цели определены следующие задачи исследования:
рассмотрение и анализ характеристик распределенных систем обработки данных;
описание и изучение основных задач, входящих в процесс проектирования РБД;
анализ постановки и исследование зависимостей задач фрагментации БД, размещения фрагментов и формирования стратегий исполнения запросов;
выбор и обоснование критерия эффективности РБД;
разработка алгоритмов проектирования эффективной РБД, описывающих способы фрагментации БД, размещения фрагментов по узлам ВС и формирующих рекомендации по архитектуре РБД;
разработка прикладных программ на основании предложенных алгоритмов.
Объект исследования - распределенные базы данных.
Предметом исследования являются модели и алгоритмы автоматизированной системы, предназначенной для описания методики распределения БД.
Методологическая и теоретическая основа исследования. При выполнении работы использованы элементы теории множеств, теория графов, методы проектирования локальных и распределенных БД, генетические алгоритмы, теория массового обслуживания, теория вычислительных систем.
Научная новизна исследования заключается в следующем:
Сформулирована задача проектирования РБД, учитывающая взаимозависимости схем фрагментации БД, размещения фрагментов и формирования стратегий исполнения запросов;
Выбран и обоснован критерий эффективности РБД, учитывающий влияние степени загрузки ресурсов на время ответа на запрос и коэффициент готовности транзакций. Критерий позволяет проектировщику устанавливать желаемые приоритеты времени ответа на запрос и готовности транзакций;
Проведено исследование и выявлены зависимости влияния репликации фрагментов БД и физических характеристик ВС на время ответа на запрос с учетом применения внутриоператорного параллелизма;
Предложен подход на основании вложенных генетических алгоритмов, позволяющий учесть взаимозависимость NP-полных задач, входящих в процесс проектирования;
Практическая значимость работы состоит в том, что описанный критерий РБД позволяет на этапе проектирования задавать требуемое соотношение среднего времени ответа на запрос и коэффициента
готовности транзакций. Разработанный алгоритм получения схемы фрагментации, схемы размещения и рекомендаций по исполнения запросов учитывает повышение эффективности РБД при применении параллельной обработки. Разработанный алгоритм является научной основой для создания САПР РБД.
Апробация результатов исследования. Основные положения диссертационной работы доложены и обсуждены на IV Межвузовской конференции молодых учёных (г. Санкт-Петербург, 2007 г.), XXXVII научной и учебно-методической конференция СПбГУ ИТМО (г. Санкт-Петербург, 2008 г.), V Межвузовской конференции молодых учёных (г. Санкт-Петербург, 2008 г.), XV Всероссийской научно-методической конференции «Телематика'2008» (г. Санкт-Петербург, 2008 г.).
Публикации. По теме диссертации опубликовано 6 статьей.
Структура и объем работы. Работа состоит из введения, четырех глав, заключения, библиографического списка использованной литературы из 65 наименований.
Масштабируемость
Масштабируемость системы может измеряться по трем различным показателям. Во-первых, система может быть масштабируемой по отношению к ее размеру, что означает легкость подключения к ней дополнительных пользователей и ресурсов. Во-вторых, система может масштабироваться географически, то есть пользователи и ресурсы могут быть разнесены в пространстве. В-третьйх, система может быть масштабируемой в административном смысле, то есть быть проста в управлении при работе во множестве административно независимых организаций. К сожалению, система, обладающая масштабируемостью по одному или нескольким из этих параметров, при масштабировании часто дает потерю производительности [1].
Поскольку проблемы масштабируемости в распределенных системах такие как проблемы производительности, вызываются ограниченной мощностью серверов и сетей, существуют три основные технологии масштабирования: сокрытие времени ожидания связи, распределение и репликация.
Сокрытие времени ожидания связи применяется в случае географического масштабирования. Основная идея проста: постараться по возможности избежать ожидания ответа на запрос от удаленного сервера. Например, если была запрошена служба удаленной машины, альтернативой ожиданию ответа от сервера будет осуществление на запрашивающей стороне других возможных действий. В сущности, это означает разработку запрашивающего приложения в расчете на использование исключительно асинхронной связи.
Следующая важная технология масштабирования — распределение. Распределение предполагает разбиение компонентов на мелкие части и последующее разнесение этих частей по системе.
При рассмотрении проблем масштабирования, часто проявляющихся в виде падения производительности, нередко хорошей идеей является репликация компонентов распределенной системы. Репликация не только повышает доступность, но и помогает выровнять загрузку компонентов, что ведет к повышению производительности. Кроме того, в сильно географически рассредоточенных системах наличие близко лежащей копии позволяет снизить остроту большей части упоминавшихся ранее проблем ожидания завершения связи.
Кэширование представляет собой особую форму репликации, причем различия между ними нередко малозаметны или вообще искусственны. Как и в случае репликации, результатом кэширования является создание копии ресурса, обычно в непосредственной близости от клиента, использующего этот ресурс. Однако в противоположность репликации кэширование — это действие, предпринимаемое потребителем ресурса, а не его владельцем.
На масштабируемость может плохо повлиять один существенный недостаток кэширования и репликации. Поскольку мы получаем множество копий ресурса, модификация одной копии делает ее отличной от остальных. Соответственно, кэширование и репликация вызывают проблемы непротиворечивости [1].
Традиционно, с точки зрения распределенности, операционные системы разделяют на две категории: сильно связанные и слабо связанные системы. Сильно связанные операционные системы обычно называются распределенными операционными системами (Distributed Operating System, DOS) и используются для управления мультипроцессорными и гомогенными мультикомпьютерными системами. Слабо связанные сетевые операционные системы (Network Operating Systems, NOS) используются для управления гетерогенными мультикомпьютерными системами.
Однако, ни распределенные, ни сетевые операционные системы не соответствуют определению распределенных систем, данному в разделе 1.1. Распределенные операционные системы не предназначены для управления набором независимых компьютеров, а сетевые операционные системы не дают представления одной согласованной системы.
В качестве решения, сочетающего масштабируемость и открытость сетевых операционных систем и прозрачность и относительную простоту в использовании распределенных операционных систем, вводится дополнительный уровень программного обеспечения, который получил название программного обеспечения промежуточного уровня [1, 2].
Модель «Сущность-связь»
Сетевая модель базы данных сходна с иерархической моделью, однако в отличие от иерархической модели, записи сетевой модели могут иметь более одного предка. - Преимущества: концептуальная простота, поддержка других типов связей, гибкий доступ к данным, обеспечение целостности базы данных, независимость данных, соответствие стандартам. - Недостатки: сложность системы в целом, недостаточная структурная зависимость.
Реляционная модель реализуется с помощью СУБД, которая берет на себя управление всеми деталями физической реализации БД. Пользователи оперируют лишь с логическим представлением базы данных. - Преимущества: структурная независимость, концептуальная простота, простота проектирования, реализации, управления и использования, возможность нерегламентированных запросов, мощная система управления БД. - Недостатки: существенные требования к оборудованию и системному программному обеспечению.
Модель «сущность-связь» (ER-модель) основана на наглядном представлении данных и их связей. Модель описывает простой интерпретируемый графический инструмент проектирования БД -диаграммы «сущность-связь». - Преимущества: исключительная концептуальная простота, наглядное представление, интеграция с реляционной моделью баз данных. - Недостатки: недостаточные возможности представления ограничений, ограниченные возможности представления отношений, отсутствие языка манипулирования данными, утеря информационного наполнения. Многомерная модель используется в технологии OLAP (OnLine Analytical Processing - оперативная аналитическая обработка). Многомерность модели данных означает здесь многомерное логическое представление структуры информации и не связана с многомерностью визуализации.
Многомерные структуры представляются как гиперкубы данных. Каждая грань куба является размерностью. Основными понятиями, используемыми в многомерных моделях данных, являются «измерение» (dimension) и «ячейка» (cell). Измерение - упорядоченный набор значений, принимаемых конкретным параметром, соответствующий одной из граней гиперкуба. Ячейка или показатель - это поле, соответствующее атрибуту сущности, значение которого однозначно определяется фиксированным набором значений параметров [2].
В объектно-ориентированной модели данных (ООМД) основной моделирующей структурой является класс, который, в отличие от сущности, помимо связей между другими классами включает еще и информацию о связях между сведениями внутри самого класса. Классы организуются в иерархии классов. Классы можно считать основными функциональными блоками для создания структур, позволяющих реализовать модульный принцип проектирования и реализации [6]. - Преимущества: добавление семантического наполнения, целостность базы данных, структурная независимость и независимость по данным. - Недостатки: отсутствие должной стандартизации, высокая трудоемкость доступа к данным.
Рассмотрим подробнее ООМД и в целом объектно-ориентированный подход к построению БД. Возникновение направления объектно-ориентированных баз данных (ООБД) определилось потребностями практики - необходимостью сложных типов данных: текста, графики, данных, аудио и видеоинформации. ООБД тесно связаны с развивающимися объектно-ориентированными языками и системами программирования.
В ООБД информация хранится в форме объектов. Полностью объектно-ориентированная СУБД должна обеспечивать также объектно-ориентированный интерфейс взаимодействия с пользователем. В основе ООБД лежит понятие объекта. Объектно-ориентированные БД характеризуются свойствами инкапсуляции, наследования и полиморфизма [7, 8].
Объектно-ориентированная технология призвана устранить ограничения, присущие реляционной технологии проектирования БД, и предоставить разработчикам более естественные и совершенные средства моделирования предметной области.
Коэффициент использования ресурсов
Коэффициент готовности транзакций отражает вероятность того, что транзакция успешно завершится за ожидаемое время. Сбой при исполнении транзакций может произойти по нескольким причинам [37, 42]: - Произошел отказ оборудования в узле или в сети; - Узел не в состоянии обслужить новый запрос из-за возросшей нагрузки; - Время исполнения транзакции превышено в следствие отказа в обслуживании на других узлах (например, физического отказа в узле или из-за загрузки сети)
Будем считать вероятность отказа пз-за физического сбоя в узле сети или в линии связи известной априори. Для простоты положим, что во всех узлах она одинакова. Таким образом, на готовность транзакций влияет только уровень загрузки узлов и линий связи.
Распределенное исполнение имеет три составляющие: — Обработка в узле, породившем транзакцию. — Передача по сети. — Обработка в удаленных узлах.
В каждом узле в обработку вовлечены центральный процессор и внешнее запоминающее устройство. Передача по сети загружает линии связи и промежуточные узлы. Таким образом, коэффициент использования ресурсов равен сумме коэффициентов использования ЦП и ВЗУ узлов, вовлеченных в операцию, и коэффициента использования сетевых ресурсов: где п - количество узлов, вовлеченных в обработку запроса; Wpu коэффициент использования ЦП А го узла; W - коэффициент использования ВЗУ А го узла; wmt- коэффициент использования сетевых ресурсов.
Необходимо отметить, что коэффициент использования ресурса является величиной относительной, что отражает физические характеристики оборудования. Например, при пересылке 2Мб данных по сети передачи данных, имеющей эффективную пропускную способность 8Мб/сек, загрузка сети будет равна 2/8=0.25, т.е. 25%. При чтении 2Мб данных с ВЗУ, обладающего скоростью чтения 50Мб/сек, загрузка ВЗУ составит 4%.
Далее необходимо разработать модель, описывающую время ответа на запрос.
Время ответа в РБД имеет две составляющие: время локальной обработки и время ответа сети. Время локальной обработки складывается из задержек в центральном процессоре и внешнем запоминающем устройстве, конкурентном доступе к сетевой среде и времени выборки и обработки данных.
Время ответа сети формируется из времени передачи данных, задержек в очередях и промежуточных узлах сети и латентности, т.е. задержки на передачу сигнала [35]. Время передачи данных зависит от пропускной способности сети. Задержки в очередях и промежуточных узлах вызваны обработкой, которая происходит в узлах, находящихся между передающим и принимающим узлами. Латентность напрямую зависит от расстояния между узлом-приемником и передатчиком. Как отмечено в [35] эта составляющая особенно важна в высокоскоростных сетях передачи данных.
Как отмечалось выше, в РБД существует возможность параллельного доступа к ресурсам, поэтому для оценки времени ответа необходимо рассмотреть процесс исполнения запроса в распределенной среде.
Наиболее часто план исполнения запроса представляется в виде дерева операторов, в котором листья представляют отношения, которые участвуют в запросе, а промежуточные вершины — операторы.
Параллельная обработка при таком описании разделяется на нескольких видов ([38, 43]): - межоператорная (inter-operation) - параллельное исполнение операторов, лежащих на разных ветвях дерева; - внутриоператорная (intra-operation) - параллельное исполнение на различных фрагментах одного отношения суб-операторов, полученных в результате декомпозиции оператора; - конвейерная (pipeline) - узел дерева «потребитель» может начать выполнение до того как «производитель» завершит свою работу
Пример дерева операторов для исполнения реляционного запроса показан нарис. 9. Pipeline Существует две стратегии оптимизации запроса для распределенного исполнения: в первой сначала строится оптимальный план последовательного исполнения запроса, который затем параллелизуется ([44]). Во второй стратегии оптимизация производится с учетом параллельного исполнения ([45]). Как показано в [31], для систем
Обоснование эффективности генетического алгоритма
Эффективность генетических алгоритмов может быть обоснована теоремой шаблонов. Шаблоном называется строка длины L (т. е. той же длины, что и любая строка популяции), состоящая из символов {0, 1, } (где - любой символ). Будем говорить, что строка является представителем данного шаблона, если в позициях, где знак шаблона равен 0 или 1, она имеет тот же символ. Порядком шаблона называется количество фиксированных битов в нем. Определяющей длиной шаблона называется расстояние между его крайними фиксированными битами. Например, для шаблона 1 01 порядок о = 3, а определяющая длина А = 5.
Очевидно, что количество представителей шаблона Н равно 2L—(H), а количество шаблонов равно З1 (действительно, шаблоны — это строки, у которых на каждой позиции может находиться один из трех символов).
Если представить пространство поиска в виде гиперкуба, то строки это его вершины, а шаблон определяет в нем гиперплоскость. К примеру, шаблон 1 определяет правую грань этого трехмерного куба:
Поэтому термины «гиперплоскость» и «шаблон» взаимозаменяемы. Приспособленностью шаблона называется средняя приспособленность строк из популяции, являющихся его представителями. Следует заметить, что эта величина зависит от популяции, и поэтому меняется со временем.
С первого взгляда может казаться, что генетический алгоритм при отборе выбирает строку, однако при этом неявным образом происходит выборка шаблонов, представителем которых она является. Это означает, что на каждом поколении количество представителей шаблона изменяется в соответствии с текущей приспособленностью этого шаблона. У «хороших» шаблонов представители в среднем более приспособленные, а значит, они чаще будут выбираться в промежуточную популяцию.
«Плохие» шаблоны имеют много шансов вымереть. Одна строка является представителем сразу многих шаблонов (а именно 2 : на каждой позиции либо остается бит строки, либо заменяется на « »). Поэтому при отборе одной строки отбирается сразу целое множество шаблонов. Это явление получило название неявный параллелизм.
Пусть M(H,t) — число представителей шаблона Н в /-ом поколении. В силу того, что при построении промежуточной популяции используется пропорциональный отбор, в ней количество представителей данного шаблона будет М(Н, /+intermediate) =М(Н, t)f(H, t)/ f(t) где j{H,t) — приспособленность шаблона Н в /-ом поколении, a j{f) — средняя приспособленность f-го поколения.
Особи промежуточной популяции с вероятностью рс подвергаются скрещиванию. Одноточечное скрещивание может разрушить шаблон, что означает, что один из родителей был представителем рассматриваемого шаблона, но, ни один из детей уже таковым являться не будет. Вероятность разрушения меньше, чем Д(Я)(1-/ (#, t)f{H,ty M y{L-l) где Р(Н, t) — доля представителей шаблона Н в /-ом поколении. Первый множитель произведения равен вероятности точки раздела попасть между фиксированными битами шаблона, а второй - вероятности выбрать в пару представителя другого шаблона.
Действительно, скрещивание разрушает шаблон не чаще, чем когда второй родитель (а он выбирается в промежуточной популяции) не является представителем этого шаблона, и при этом точка раздела попадает между фиксированными битами шаблона. Даже в этих ситуациях он не обязательно разрушается, например, если мы рассматриваем шаблон 11 , а скрещиванию подвергаются строки 110101 и 100000, и точка раздела попадает между первыми двумя битами, то, хотя вторая строка не является представителем нужного шаблона, все равно один из потомков окажется подходящим и шаблон не разрушится.
Таким образом, после скрещивания, переходя от количества представителей к их доле, получаем следующее неравенство: P(H,t+l) P(H,t)f(H,t)[l-PcA(H)(l-P(H,t)f(H,t f(t) )/(L-l)]/ f(t)
Теперь учтем влияние мутации. Для каждого фиксированного бита вероятность того, что он не будет инвертирован, равна (1 -рт). Поскольку всего в шаблоне фиксированных битов о(Н), то верна следующая итоговая формула теоремы шаблонов: р(н, t+i) p(H, от t)[i -Рсл (н) (і -р(н, от о/ /(о у(ь-іжі -Ртг(н)/ ко
Полученное неравенство хорошо описывает ситуацию для следующего поколения особей в генетическом алгоритме. Необходимо отметить, что теорема шаблонов верна только для генетического алгоритма с пропорциональным отбором и одноточечным скрещиванием [59].
