Содержание к диссертации
Введение
Глава 1 Анализ проблемной области и постановка задачи диссертации 5
1.1 Актуальность проблемы 5
1.2 Архитектура распределенных СУБД 6
1.3 Анализ принципов построения распределенных баз данных 9
1.4 Проблемы проектирования распре деленных баз данных 12
1,5 Основы проектирования распределенной базы данных 19
1.6 Обзор состояния области исследований 30
1.7 Постановка задачи 36
Глава 2 Разработка и выбор аппарата для исследовательской части 37
2.1 Обзор оценок эффективности 37
2.2 Идеология обработки запросов в РБД 33
2.3 Общиепонятия и термины, необходимые для описания распре делепюй системы обработки информации 39
2.4 Критерии оценки рациональности размещения файлов распределенной системы по узлам сети .41
2.5 Выводы по главе 46
Глава 3 Разработка и исследование алгоритма размещения 47
3.1 Разработка алгоритма размещения файлов распределенной системы по узлам сети 48
3.2 Исследование раэраеоташюго алгоритма 56
Выводы по главе 82
Глава 4 Практическая реализация 83
4.1 Применение разработанного алгоритма в системах обработки гидюлкустических данных 83
4.2 Практическая эффективность разработанного алгоритма 90
4.3 Выводы по главе 99
Заключение 100
Библиографический список 101
Приложения 108
- Актуальность проблемы
- Архитектура распределенных СУБД
- Обзор оценок эффективности
- Разработка алгоритма размещения файлов распределенной системы по узлам сети
Введение к работе
Системы распределенной обработки информации в виде сетей ЭВМ представляют собой наиболее прогрессивную форму организации средств вычислительной техники. При широком использовании средств вычислительной техники особое значение имеют способы организации, обработки и хранения огромных объемов необходимой информации, В каждом отдельном случае информация, необходимая для решения конкретной задачи или круга задач, организованная определенным образом, представляет собой различные базы данных.
Современная база данных определяется как система информационных математических, программных, организационных и технических средств, предназначенная для централизованного накопления и коллективного многоаспектного использования данных с целью получения необходимой информации.
Таким образом, базы данных представляют собой определенным образом организованные объемы данных с общим информационным полем, предназначенные для решения различных информационных задач в интересах многих пользователей. Базы данных представляют собой информационную модель того объекта (фирмы, системы, предприятия, организации), информация о котором требуется пользователю для обеспечения эффективного управления. Чем точнее и достовернее эта модель отражает свойства объекта, информация о которых необходима пользователю, тем эффективнее можно обеспечить процесс управления этим объектом.
Эффективность обработки информации в базах данных в значительной степени определяет производительность информационных систем и зависит, главным образом, от внутреннего уровня систем обработки данных. Обеспечение роста производительности информационных систем связано с решением множества задач, одной из которых является рациональное распределение
информационных ресурсов по узлам вычислительной системы и организация доступа к информации.
Основными задачами в данной области являются:
Рациональное распределение файлов РБД по узлам вычислительной сети;
Рациональный выбор внешних запоминающих устройств дня хранения файлов в каждом узле;
Рациональная организация хранения и поиска информации на внешних запоминающих устройствах в каждом узле.
Основой большинства работ, посвященных первой задаче, является теория очередей. Поэтому для решения задач размещения получаются или достаточно сложные модели, точных методов реализации которых не существует, или учитываются нереальные ограничения. Для сложных топологических структур сети достаточно трудно построить реальные модели на основе теории очередей. Кроме того, существующие алгоритмы размещения данных дают недостаточно высокие результаты работы в жестких условиях - при дефиците каких-либо ресурсов. В связи с этим рассмотрен другой подход к решению задачи, в основе которого лежит минимизация среднего времени пересылаемых по линиям связи данных, общей стоимости трафика, порожденного функционированием системы, общего времени обслуживания запросов. При этом предложена и методика реализации построенных моделей, и алгоритм, адаптированный под ужесточенные исходные данные. Эти результаты рассмотрены в главах 2? 3 настоящей работы.
Актуальность проблемы
Развитие средств вычислительной техники привело к возможности и необходимости организации их взаимосвязи между отдельными ЭВМ с использованием средств передачи данных и распределения информации. Таким образом, появилась новая технология - распределенная обработка данных, при которой вычислительные или интеллектуальные машины, территориально рассредоточенные, взаимодействуют через каналы связи или через сеть.
Создание вычислительных сетей явилось новым этапом в развитии одной из важнейших областей человеческой деятельности - обработке информации. Среди причин и обстоятельств, вызвавших появление вычислительных сетей, можно назвать следующие: 1 Необходимость получения оперативного доступа к базам данных. 2. Для выполнения работ, в которых участвуют территориально удаленные организации, необходимо тесное взаимодействие, быстрый и удобный обмен информацией. 3. В единственной ЭВМ практически невозможно создать и хранить все множество необходимых информационно-справочных данных. 4. Обеспечение высокой готовности и достоверности обработки информации на одной машине практически невозможно, так как даже при кратковременном ее отказе прекращаются все процессы, 5. Повышение надежности функционирования разработанной системы обслуживания сформированной базы данных, сохранности исходной информации и промежуточных результатов.
Все описанное выше, а также лавинная тенденция развития аппаратных средств вычислительной техники и снижение стоимости ресурсов связи, обусловили качественный скачок от использования отдельных ЭВМ к обработке информации в распределенных многомашинных ассоциациях.
Таким образом, хранимая информация носит распределенный характер, то есть, распределена по всей сети,
Программное обеспечение систем управления распределенными базами данных (СУРБД) обычно имеет многоуровневую архитектуру. Как показано на рисунке 1, в такой архитектуре существует пять уровней, которые могут быть подразделены на две основные части- Верхние четыре уровня процессоров — пользовательский, глобальный логический, фрагментный и распределенный уровни представлений могут быть сгруппированы вместе и названы сетевой СУБД, Нижний уровень — процессор узлового уровня представления может быть назван локальной СУБД» Межузловая связь связывает узлы сетевой СУБД с узлами локальной СУБД. Интерфейсы
Каждый из этих уровней поддерживает различные представления базы данных. Каждый уровень взаимодействует только с непосредственно смежными уровнями представления. Самым верхним уровнем структуры является интерфейс прикладной программы, или интерфейс процессора запроса. Каждый уровень представления базы данных необходим для того, чтобы в явном виде представлять определенный аспект логической или физической структуры базы данных.
Конечное, или локальное, представление есть представление части базы данных, существующей в конкретном узле. Другими словами, оно описывает базу данных, доступную локальной СУБД. Безусловно, база данных, расположенная в узле, может рассматриваться как с точки зрения логической, так и физической структуры. Локальное представление, как было определено, является логической структурой, а физическая структура при этом является скрытой, В свою очередь локальная СУБД имеет несколько уровней представления данных, однако в данном рассмотрении такие детали не учитываются, 1.2.1 Логическая структура базы данных
Модель данных, соответствующая логической структуре базы данных, является вариантом реляционной модели. Она достаточно мощная для представления как реляционных структур, так и логических структур других моделей данных. В расширенной реляционной модели база данных состоит из нескольких таблиц. Для заданных множеств значений Dfr D2, ..., Dn таблица определяется как множество строк, в каждой из которых первый элемент берется из Df9 второй из 2 ... и /7-й элемент из Dn. Множества Д называются доменами. Допустимыми типами данных для этих доменов являются символьные строки, целые и действительные числа, логические переменные. Каждая строка таблицы должна иметь первичный ключ, состоящий из значений одного или нескольких столбцов, которые однозначно определяют строку. Все строки таблицы являются различными (первичные ключи не дублируются).
Архитектура распределенных СУБД
Базы данных с древовидной структурой явно определяются в момент определения данных посредством промежуточной таблицы, называемой ассоциацией. Ассоциации есть явно определенные связи между двумя таблицами. Они используются для представления связи типа 1:М в древовидных базах данных. В этой связи одна таблица может быть названа «владелец», а другая «член». Для строк таблицы-члена, которые связаны со строками таблицы-владельца, может быть определен один или более критериев упорядочивания.
Существуют два типа представлений логической структуры базы данных: глобальное логическое представление и пользовательское представление. Глобальное логическое представление содержит логическую структуру всей распределенной базы данных. Пользовательское представление является подмножеством глобального логического представления, которое администратором базы данных объявляется доступным конкретному пользователю. Это упрощенное представление содержит только те таблицы, столбцы и строки, которые требуются конкретному пользователю. С одним и тем же глобальным логическим представлением может быть связано несколько пользовательских представлений. Для администратора базы данных пользовательское представление является средством управления доступом и безопасности. Для пользователя его представление есть средство упрощения структуры базы данных. 1.2.2 Физическая структура базы данных
Часть базы данных, распределенная в одном узле, называется хранимым фрагментом. Хранимый фрагмент, как реализация логического фрагмента, содержит подмножество строк таблицы. Таблица должна быть расчленена на не пересекающиеся между собой фрагменты. Наименьшим фрагментом таблицы является одиночная строка. Каждая строка фрагмента является полной в том случае, когда она содержит все столбцы, определенные в таблице. Фрагмент может повторяться с целью повышения надежности и производительности. Может существовать любое количество копий отдельного фрагмента, каждая из которых размещается в отдельном узле. При запросе таблицы в первую очередь необходимо определить, какие фрагменты таблицы могут содержать запрашиваемые строки, а затем расположение «лучшей» копии фрагмента или «лучших» копий фрагментов.
Гибкость проектирования обеспечивается наличием возможности сочетать копирование и расчленение базы данных. Определение логических фрагментов и размещения копий хранимых фрагментов позволяет проектировщику удовлетворять предъявляемые к времени отклика и надежности системы требования, управляя при этом дублированием базы данных. 13 Анализ принципов построения распределенных баз данных
Под распределенной (Distributed DataBase - DDB) обычно подразумевают базу данных, включающую фрагменты из нескольких баз данных, которые располагаются на различных узлах сети компьютеров, и, возможно, управляются различными СУБД, Распределенная база данных выглядит с точки зрения пользователей и прикладных программ как обычная локальная база данных, В этом смысле слово "распределенная" отражает способ организации базы данных, но не внешнюю ее характеристику ("распределенность" базы данных невидима извне). 1.3,1 Определение Дэйта
Одно из лучших определений распределенных баз данных предложил Дэйт (CJ. Date). Он установил 12 свойств или качеств идеальной DDB [3]:
1. Локальная автономия (local autonomy). Это качество означает, что управление данными на каждом из узлов распределенной системы выполняется локально. База данных, расположенная на одном из узлов, является неотъемлемым компонентом распределенной системы. Будучи фрагментом общего пространства данных, она, в то же время функционирует как полноценная локальная база данных; управление ею выполняется локально и независимо от других узлов системы,
2. Независимость узлов (по reliance on central site). В идеальной системе все узлы равноправны и независимы, а расположенные на них базы являются равноправными поставщиками данных в общее пространство данных. База данных на каждом из узлов самодостаточна - она включает полный собственный словарь данных и полностью защищена от несанкционированного доступа,
3. Непрерывные операции (continuous operation). Это качество можно трактовать как возможность непрерывного доступа к данным (известное "24 часа в сутки, семь дней в неделю 1) в рамках DDB вне зависимости от их расположения и вне зависимости от операций, выполняемых на локальных узлах. Это качество можно выразить лозунгом "данные доступны всегда, а операции над ними выполняются непрерывно".
4. Прозрачность расположения (location independence). Это свойство означает полную прозрачность расположения данных. Пользователь, обращающийся к DDB, ничего не должен знать о реальном, физическом размещении данных в узлах информационной системы. Все операции над данными выполняются без учета их местонахождения. Транспортировка запросов к базам данных осуществляется встроенными системными средствами,
Обзор оценок эффективности
Оценить эффективность обработки информации в современных вычислительных и информационных сетях достаточно сложно, поэтому при анализе используются различные критерии.
Вычислительные сети можно изучать и анализировать с различных точек зрения, чем объясняется возникновение множества задач исследования.
Если рассматривать вычислительную сеть как экономический объект, имеющий стоимость, производительность, требующий соответствующие капиталовложения, трудовые ресурсы на производство и эксплуатацию, то естественно, возникает задача моделирования сети и выбора и параметров как сложной экономической системы.
Когда вычислительная сеть описывается как формальный объект, представимый в виде множества узлов, объединенных линиями связи, возникает математическая модель топологической структуры сети»
При анализе вычислительной сети как технического объект, представляющего собой совокупность аппаратных средств, объединенных для выполнения комплекса задач, характеристики сети, согласованность и четкость взаимодействия между отдельными ее компонентами определяются подбором аппаратных модулей, их совместимостью, тем, насколько они соответствуют ставящимися перед ними требованиями. В этом случае необходимо иметь модели выбора состава необходимых аппаратных средств вычислительной сета.
Если же рассматривать вычислительную сеть как средство, осуществляющее обмен информацией, то ее можно представить как множество информационных пунктов, связанных между собой, и, естественно, потребуется специфическая модель организации информационного обмена.
Таким образом, вычислительную сеть можно рассматривать как совокупность ресурсов различного типа. Это, прежде всего, вычислительные мощности, каналы связи, оперативная и постоянная память и т.д.
Поскольку распределенная система обработки информации предполагает возможную большую степень рассредоточения данных, то использование классических топологий (звезда, кольцо, и т.д.) становится неприемлемо, и в данной работе рассматривается вычислительная сеть с произвольной топологией (рисунок 2.1)- Это означает, что существует доступ из каждого узла сети к информации любого другого узла, и на линии связи между узлами сети не накладываются ограничения.
Как уже упоминалось выше, предполагается некоторое упрощение реальной вычислительной системы для облегчения процесса исследования свойств данной системы. При этом отсутствующие в математической модели свойства и качества реальной системы не оказывают существенного воздействия на исследуемые характеристики.
Схема обработки запросов состоит в следующем: запрос» инициированный на узле сети, поступает на входную очередь соответствующего узла. Программа обработки обрабатывает запросы в
порядке их поступления. Если запрашиваемые данные содержатся в локальной базе данных узла, на который поступил запрос, то запрос обрабатывается и выводится результат. Если запрашиваемые данные содержится на другом узле сети, то запрос пересылается на нужный узел сети, где он обрабатывается, и результат пересылается в первоначальный узел. Порядок обслуживания запросов в узлах не влияет на объем пересылаемых данных по каналам связи и поэтому не рассматривается. Для определения типа запроса (локально или удаленно обслуживаемый) используются специальные справочники, содержащиеся в локальной базе узла, инициирующего запрос.
Из вышеописанной схемы обработки запросов в системе следует, что в процессе обслуживания в течение каждой единицы времени по каналам связи пересылается некоторый объем данных. Общее значение этого объема зависит от распределения файлов по локальным базам данных. Соответственно, чем меньше средний объем пересылаемых данных по каналам сети за единицу времени, тем выше скорость обработки запросов. 23
Разработка алгоритма размещения файлов распределенной системы по узлам сети
Для решения поставленных задач будет использоваться эвристический алгоритм, который состоит из двух последовательных этапов: 1, На первом этапе формируется матрица начального размещения файлов по узлам вычислительной сети, оптимальная с точки зрения заданного критерия, причем на данном этапе не учитываются ограничительные условия. Т.е. для каждого файла РБД определяется тот узел сети, в котором его местонахождение оптимально с точки зрения заданного критерия. При такой формулировке, полученное размещение файлов будет самым оптимальным, поскольку не учитываются условия ограничения; 2. На втором этапе проводится поверка соблюдения заданных ограничений и производится процесс переразмещения файлов, если для начального размещения существует хотя бы один узел сети, где заданные ограничения не выполняются. Т.е. используется многоитерационный подход, на каждом шаге которого осуществляется перераспределение файла из переполненного узла таким образом, чтобы его перемещение привело к минимальному увеличению значения критерия. Выполнение перераспределения производится до тех пор, пока не будет найдено размещение, удовлетворяющее условиям ограничения, или не будет принято решение о невозможности нахождения такого размещения.
В приведенном в п. 3.1 2.1 классическом методе распределения информации по узлам вычислительной сети в процессе исследования обнаруживается существенный недостаток: при наличии некоторого переполненного узла Kj происходит перераспределение файлов из этого узла, после чего узел считается закрытым для перераспределения; однако при закрытии узла не учитывается неиспользованный объем памяти для размещения файлов в узле Kj (обозначим его - Ь/) и таким образом этот объем памяти становится недоступным для дальнейшего переразмещения других файлов и, следовательно, уменьшает общий объем памяти, доступный для дальнейшего переразмещения оставшихся файлов. В приведенной ниже первой ступени модификации метода этот недостаток устранен.
Для повышения качества разрабатываемого алгоритма в случае, когда процесс работы алгоритма завершается аварийно (т.е. первая ступень модификации алгоритма не размещает файлы: для какого-либо і-го файла не хватало места в процессе переразмещения), применяется вторая ступень модификации алгоритма: 1 Выявляется "проблемный" і-й файл, для которого не хватило места ни в одном из узлов в процессе переразмещения; 2. Значения векторов признаков Ми Р устанавливаются в 0; 3. Повторно выполняется процедура определения матрицы начального размещения (описана в п. 3.1.1); 4. Проводится анализ возможности размещения і-го файла: производится последовательный перебор узлов в порядке нарастания/убывания значения целевой функции (по отношению к / му файлу), проверяя выполнение условий ограничения для этого узла. Первый же узел, где выполняются условия ограничения, признается годным для размещения г-го файла, после чего файл становится неперемещаемым (элементу ntt вектора М присваивается значение 1); 5. Повторно выполняется процедура переразмещения (п. 3.1,2-2). Задача данной ступени модификации алгоритма в том, чтобы обеспечить гарантированное размещение того файла, который стал причиной аварийной работы предыдущей ступени модификации для обеспечения процесса ее работоспособности. 3.1.2.2.3 Третья ступень модификации
Анализ работы второй ступени модификации алгоритма позволил сделать вывод о том, что "проблемный" г-й файл, для которого не хватило места ни в одном из узлов в процессе переразмещения, является как правило одним из самых больших файлов в общем количестве данных (L,- max). Это наблюдение и легло в основу идеи третьей ступени модификации разрабатываемого алгоритма (аналогом данной ступени модификации может считаться алгоритм последовательного размещения элементов в радиоэлектронике). Из предварительно размещенных файлов выбирается тот, который имеет максимальный размер. Этот файл располагается поочередно в каждом узле, и подсчитывается значение выбранного критерия, в результате чего определяется оптимальное размещение этого файла (с учетом условий ограничений). Затем выбирается следующий по размеру файл, и все повторяется в том же порядке. Выполнение алгоритма заканчивается, когда все файлы размещены по узлам сети или выявляется принципиальная невозможность такого размещения.
![Рациональное управление системой психологической помощи на основе медицинского мониторинга и организации психопрофилактического процесса [Электронный ресурс]](/i/i/4409/168295.png "Рациональное управление системой психологической помощи на основе медицинского мониторинга и организации психопрофилактического процесса [Электронный ресурс] Склярова Татьяна Петровна")
