Содержание к диссертации
Введение
1 Анализ предметной области 11
1.1 Основы систем репликации 11
1.2 Синхронная репликация 13
1.2.1 Распределенная блокировка данных 13
1.2.2 Распределенное подтверждение изменений 15
1.3 Асинхронная репликация 16
1.3.1 Условия непротиворечивости 17
1.3.2 Протоколы непротиворечивости ... 21
1.4 Практическая реализация репликации различными СУБД 25
1.4.1 Объекты репликации 26
1.4.2 Механизм определения множества передаваемых данных 28
1.4.3 Фильтрация данных 29
1.4.4 Синхронная и асинхронная репликация 31
1.4.5 Разрешение конфликтов 33
1.4.6 Гетерогенная репликация 35
1.4.7 Требования к среде передачи информации 36
1.4.8 Безопасность 37
1.4.9 Дополнительные возможности репликации 37
1.5 Выводы 38
2 Формализация динамической объектной репликации 41
2.1 Общая архитектура 41
2.2 Графовая модель объектов 42
2.3 Аннулирование объектов 48
2.4 Маршрутизация 49
2.5 Модель транзакций 51
2.6 Непротиворечивость , 53
2.7 Выводы 54
3 Практическая реализация репликации 56
3.1 Определение изменения объекта 56
3.2 Алгоритм обработки кортежей объекта... 58
3.3 Пакетная передача данных 60
3.4 Алгоритмы маршрутизации 62
3.4.1 Определение маршрута без сохранения истории рассылки 64
3.4.2 Модифицированный алгоритм определения маршрута 66
3.4.3 Построение функции маршрутизации с учетом наследования 69
3.1.4. Протоколы аннулирования объекта 70
3.4.5 Протокол первичной копии 70
3.5 Алгоритмы актуализации 71
3.5.1 Обработка конфликтов 72
3.5.2 Копирование объекта из буферов репликации в БД 75
3.5.3 Обработка нарушения целостности ссылок 77
3.6 Алгоритмы транспортировки 81
3.6.1 Формирование сообщений транспортного уровня 81
3.6.2 Надежная доставка данных 83
3.6.3 Очистка репликационных таблиц 87
3.7 Программная реализация репликации 87
3.7.1 Реализация базовой части 89
3.7.2 Реализация транспортной части 120
3.8 Выводы 132
4 Экспериментальное исследование разработанной модели и методов 133
4.1 Конфигурация тестируемой системы 133
4.2 Система моделирования нагрузки 134
4.3 Настройки системы репликации 136
4.4 Проведение измерений 136
4.4.1 Замедление пользовательских транзакций записи 138
4.4.2 Подготовка данных 139
4.4.3 Актуализация данных 141
4.4.4 Формирование отправляемых данных 142
4.4.5 Запись полученных данных в БД 143
4.5 Выводы 144
Заключение 146
Литература 148
- Протоколы непротиворечивости
- Графовая модель объектов
- Определение маршрута без сохранения истории рассылки
- Система моделирования нагрузки
Введение к работе
Автоматизация технологических процессов и управление производством на основе современных программно-аппаратных комплексов составляет одно из главных направлений научно-технического прогресса. Создание на научной основе автоматизированных систем управления технологическими процессами (АСУ ТП), их интеграция в единую систему сбора и обработки данных и оперативного управления повышает качество и эффективность всех звеньев управления производством в народном хозяйстве.
Задача построения распределенных систем не является новой, поэтому на текущий момент существует большое количество теоретических исследований, а также практически реализованных программных средств, позволяющих осуществлять построение распределенных БД и систем управления ими. Значительный вклад в развитие теории БД и создание эффективных СУБД внесли К. Дейт, Э.Ф. Кодд, Д. Кренке, М.Р. Когаловский, Л.А. Калиниченко. Теории и практике автоматизированных распределенных систем посвящены труды С.Д. Кузнецова, Е.М. Бениаминова, В.В. Кульбы, С.С. Ковалевского, С.А. Косяченко, В.О. Сиротюка, Н.Д. Дубового, А.С. Бондаревского.
При создании распределенных АСУ ТП возникает задача по реализации автоматического обмена между удаленными базами данных (БД). На текущий момент многие реляционные системы управления базами данных (СУБД) поддерживают репликацию данных.
Несмотря на разнообразие средств репликации, они обладают следующими недостатками:
Сложность настройки. Как правило, конфигурирование системы репликации требует от администратора очень высокой квалификации и хорошего знания структуры БД, что приводит к значительным временным и финансовым затратам при настройке синхронизации БД со сложной структурой.
Невозможность реализации динамической репликации, предполагающей определение правил распространения данных, вычисляемых на основании самих копируемых данных. Существующие системы ограничены статическими схемами фильтрации передаваемых данных, что сильно снижает их гибкость.
Отсутствие поддержки непротиворечивости на уровне объектов. Существуют ситуации, при которых одновременное изменение одной и той же записи в различных БД нарушает целостность
объектов приложения, несмотря на поддержку непротиворечивости отдельных записей. Подобные конфликты принципиально неразрешимы на уровне существующих систем репликации, поскольку проблема возникает только на уровне логики приложения.
Устранение перечисленных недостатков в рамках существующих систем сильно затруднено, поскольку это требует создания программной надстройки над модулем репликации, осуществляющей его взаимодействие с пользовательским приложением. Для реализации подобной надстройки требуется возможность детального управления процессом передачи данных, что практически неосуществимо при использовании законченных программных продуктов.
В силу этого представляются актуальными исследования, направленные на разработку эффективных методов и средств динамической объектной репликации с целью повышения гибкости использования распределенных АСУ ТП и уровня непротиворечивости хранимых данных. Таким образом, объектом исследований являются распределенные АСУ ТП. Предмет исследований - репликация данных в распределенных АСУ ТП.
Цель работы заключается в разработке моделей и методов динамически настраиваемого межсерверного обмена, создании эффективных алгоритмов управления распределенными базами данных, обеспечивающих функционирование АСУ ТП в условиях отсутствия стабильных каналов связи.
Теоретические методы исследования базируются на фундаментальных положениях теории математической статистики и принципах управления реляционными базами данных.
Научная новизна работы состоит в разработке моделей, методов и алгоритмов динамической объектной репликации, позволяющих увеличить гибкость управления распределенными АСУ ТП, а также повысить уровень непротиворечивости данных за счет применения объектно-ориентированного подхода. В ходе выполнения диссертационной работы получен ряд новых научных результатов. При этом разработаны:
Графовая модель представления данных реляционной БД в виде объектов, по сравнению с репликацией кортежей расширяющая возможности синхронизации данных за счет наличия связей между отношениями, что повышает уровень непротиворечивости данных,
а также сокращает среднее время настройки правил обмена сложного объекта в 5-12 раз.
Метод наследования классов, позволяющий снизить избыточность описания структуры хранимых данных в среднем в 2-3 раза.
Метод реализации объектной FIFO непротиворечивости, основанный на графовом представлении данных, повышающий непротиворечивость данных по сравнению с FIFO непротиворечивостью репликации отдельных кортежей или транзакций.
Алгоритмы динамической маршрутизации для произвольного перенаправления информационных потоков в зависимости от состояния хранимых данных.
Алгоритм разрешения конфликтов одновременного изменения информации, предоставляющий повышенные гарантии непротиворечивости данных.
Алгоритм пакетного обмена для выборки, записи, шифрования и сжатия информации, обеспечивающий снижение сетевого обмена на 60%.
Практическая значимость результатов работы заключается в использовании разработанной модели, методов и алгоритмов в АСУ ТП компании ЗАО «Таймырская топливная компания». Система объединяет предприятия компании, расположенные в Москве, Красноярском крае, Норильском промышленном районе и на Кольском полуострове. Применение полученных результатов позволило реформировать товаропроводящую сеть за счет организации единого информационного пространства для всех предприятий компании. Унификация документооборота и информационная поддержка бизнес-процессов привели к повышению уровня логистического сервиса, снижению страховых запасов топлива на 10-15%. Уровень операционных затрат понижен на 5-10%, при этом время настройки репликации в 5-12 раз меньше времени, затрачиваемого при использовании стандартных средств администрирования СУБД. Перечисленные результаты получены в отсутствие высоких требований к качеству каналов связи, что особенно критично при использовании комплекса в условиях Крайнего Севера. Кроме того, результаты работы использованы в научно-исследовательской работе МИЭТ.
Достоверность полученных результатов подтверждается хорошим совпадением теоретически рассчитанных и практически полученных результатов, а также успешной промышленной
эксплуатацией комплекса, созданного с использованием разработанных в диссертации методов и средств.
Личный вклад автора. Все основные результаты получены автором лично. Главными из них являются:
Графовая модель представления данных реляционной БД в виде объектов.
Метод наследования классов.
Метод реализации объектной FIFO непротиворечивости, основанный на графовом представлении данных.
Алгоритмы динамической маршрутизации.
Алгоритм разрешения конфликтов одновременного изменения данных.
Алгоритм пакетного обмена.
Практическая реализация методов и средств динамической объектной репликации в промышленной распределенной АСУ ТП ЗАО «Таймырская топливная компания».
Автор диссертации принимал активное участие в разработке документации, методики испытаний и проведении установочных и сопроводительных работ в местах эксплуатации АСУ ТП ЗАО «Таймырская топливная компания».
Внедрение результатов работы. Разработанные в ходе выполнения диссертационной работы методы и средства внедрены в АСУ ТП ЗАО «Таймырская топливная компания», что позволило снизить уровень требуемых страховых запасов топлива на 10-15% и уменьшить операционные затраты на 5-10%. Результаты работы также использованы в научно-исследовательской работе МИЭТ в рамках договора на разработку модулей автоматизированной информационной системы учета движения материальных ценностей № 2157 от 01.09.2001.
На защиту выносятся:
-
Графовая модель представления объектов реляционной БД.
-
Метод наследования классов реплицируемых данных.
-
Метод реализации объектной FIFO непротиворечивости.
-
Алгоритмы динамической объектной репликации, реализующие предложенные в работе методы.
-
Результаты экспериментальных исследований и промышленного внедрения результатов работы.
Апробация работы. Основные положения и результаты диссертационной работы докладывались и обсуждались на трех
Всероссийских межвузовских научно-технических конференциях студентов и аспирантов «Микроэлектроника и информатика» (г. Москва, Зеленоград, Московский институт электронной техники), международной научно-технической конференции «Электроника и информатика 2002» (г. Москва, Зеленоград, Московский институт электронной техники) и международной научно-технической конференции «Новые информационные технологии и системы 2006» (г. Пенза, Пензенский государственный университет). Доклад на 13-й Всероссийской межвузовской научно-технической конференции студентов и аспирантов «Микроэлектроника и информатика - 2006» отмечен дипломом 1-й степени по секции «Автоматизированные информационные системы».
Публикации. Основное содержание диссертационной работы отражено в 10 работах, в том числе в 5 статьях и 5 тезисах докладов на Всероссийских конференциях.
Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения и списка литературы. Содержит 154 страницы машинописного текста, 26 страниц с рисунками и таблицами, список литературы из 82 наименований.
Протоколы непротиворечивости
Протокол непротиворечивости представляет собой стандарт обмена сообщениями между серверами репликации, гарантирующий выполнение определенных условий непротиворечивости. Ниже будут рассмотрены только протоколы на основе условий непротиворечивости, ориентированных на данные, поскольку они представляют наибольший интерес для практической реализации репликации БД. Протоколы непротиворечивости, ориентированные на клиента, подробно описаны в [48,59,69]. 1.3.2.1 Протоколы на базе первичной копии
Протоколы на базе первичной копии предполагают для каждого элемента данных существование первичной копии, находящейся на одном из серверов. Любое изменение данных вначале производится на первичной копии, после чего передается на остальные серверы.
Простейший протокол этого вида всю запись и чтение производит исключительно на первичной копии. В результате репликации данных не происходит вообще, хотя система и продолжает оставаться распределенной. Более интересными с практической точки зрения является протоколы, которые производят операции записи на первичной копии, но чтение всегда выполняют локально, Такие схемы называют протоколами первичного архивирования (primary-backup protocol) [44].
Первичное архивирование делится на блокирующее и неблокирующее. В блокирующих схемах сервер, производящий изменение данных, блокируется до того момента, когда сервер первичной копии разошлет изменение по всем серверам. В неблокирующих схемах изменение отправляется на сервер первичной копии без какого-либо ожидания. Протоколы первичного архивирования с блокировкой представляют собой простую реализацию последовательной непротиворечивости, в которой первичный сервер упорядочивает приходящие операции записи. При неблокирующем первичном архивировании последовательная непротиворечивость может быть гарантирована только в некоторых специальных случаях.
К схемам на базе первичной копии относятся также и протоколы локальной записи (local-write protocols). Они аналогичны протоколам первичного архивирования с той разницей, что первичный сервер может изменяться. При необходимости записи данных сервер становится первичным для этого набора данных и производит всю запись локально, после чего производит пересылку изменений всем серверам. Основная сложность данного протокола заключается в отслеживании для каждого набора местонахождения первичной копии. Эта задача решается с помощью широковещательных рассылок и иерархических служб локализации. Протоколы локальной записи могут быть применены для создания систем тиражирования с участием мобильных клиентов. Перед отключением от хранилища данных клиент регистрирует себя в качестве сервера первичной копии для данных, с которыми он собирается работать. После отключения все операции чтения и записи производятся локально. При следующем подключении к хранилищу клиент получает изменения, произведенные другими клиентами, актуализирует их и рассылает всем серверам вместе со своими изменениями. 1.3.2.2 Протоколы реплицируемой записи
В отличие от протоколов на базе первичной копии протоколы реплицируемой записи не предполагают наличие выделенного сервера, производящего запись. Изменения данных передаются на все реплицируемые серверы или их подмножество. Одной из основных задач, решаемых протоколами первичной записи, является глобальное упорядочивание операций записи с тем, чтобы все серверы получали одну и ту же последовательность операций.
Для упорядочивания операций записи можно воспользоваться алгоритмами полностью упорядоченной групповой рассылки на основании отметок времени Лампорта. Альтернативный вариант предполагает использование выделенного сервера (называемого секвенсором), производящего нумерацию всех изменений [72]. При использовании секвенсора все серверы должны принимать обновления строго в порядке увеличения их номеров, гарантируя при этом отсутствие пропусков в номерах полученных обновлений. Этот вариант упорядочивания аналогичен протоколам на основе первичной копии за исключением того, что выделенный сервер производит упорядочивание всех изменений, а не только тех, для которых он является сервером первичной копии. Указанные алгоритмы полностью упорядоченной групповой рассылки являются плохо масштабируемыми и требуют надежных каналов связи, что делает невозможным их применение для асинхронной репликации.
Протоколы реплицируемой записи позволяют реализовать FIFO-непротиворечивость без применения упорядоченной рассылки. Если гарантируется доставка сообщений адресату в порядке их отправки, то для реализации FIFO-непротиворечивости никаких действий со стороны приложения не требуется. Если же такой гарантии нет, то FIFO-непротиворечивость реализуется последовательной нумерацией изменений и обработкой их получателями строго в порядке увеличения номеров. Следует отметить тот факт, что FIFO-непротиворечивость не гарантирует совпадение данных на разных серверах при их одновременном изменении. Для этого применяются механизмы обнаружения и разрешения конфликтов.
Для реализации самого слабого из условий непротиворечивости -потенциальной непротиворечивости - может быть применено правило записи Томаса [70]. Согласно этому правилу каждый элемент данных обладает отметкой времени, отражающей время его последнего изменения. Реплицируемые серверы периодически опрашивают друг друга и загружают себе только те данные, отметка времени которых больше, чем у собственной копии. Применение этого правила гарантирует, что в течение конечного промежутка времени после завершения всех изменений все копии станут идентичными.
Графовая модель объектов
Как правило, при практической реализации систем репликации предполагается, что реплицируемые данные из БД не удаляются. Вместо этого они помечаются, как недоступные пользователю [21]. В качестве примера конфликта, возникающего при физическом удалении объектов, рассмотрим следующую ситуацию. Пусть в БД В} произведено обновление данных операцией ws а в БД В2 примерно в то же самое время произведено удаление тех же самых данных операцией d2. После выполнения этих операций происходит обмен данными с сервером БД В3. Если система реализует широко распространенную FIFO непротиворечивость данных, то порядок выполнения операций, полученных от различных серверов, не гарантируется. Таким образом, сервер БД В3 может получить как последовательность операций w}d2, так и d2w}. В последнем случае, в зависимости от реализации системы репликации, произойдет либо конфликт обновления удаленных данных, либо произойдет вставка уже удаленных данных, что нарушит непротиворечивость БД.
С целью увеличения гибкости реализации предлагаемая в данной работе система обмена не предполагает строгой гарантии упорядоченности доставки изменений. В связи с этим описанная выше ситуация распространяется на случай обмена между двумя БД. Например, в БД Bj производится изменение данных wj, после чего происходит их удаление операцией d]. Если в силу каких-либо причин сервер БД В2 получит операции в порядке d/Wj, произойдет нарушение непротиворечивости данных. Во избежание этой ситуации предположим, что реплицируемые данные никогда не удаляются. Если все же есть необходимость освободить БД от ненужных данных, то необходимо удалять только ту информацию, которая гарантировано не будет изменяться.
Предлагаемая система репликации является динамической, что означает возможность смены маршрута передачи данных. Для этого необходимо иметь возможность удалять данные из БД, в которые они ранее были переданы, но в последствие были исключены из рассылки согласно правилам репликации. Для обеспечения подобной возможности, а также для устранения возможных проблем удаления, указанных выше, введем в модель понятие аннулирования объектов. Аннулированный объект остается в базе, но он недоступен для изменения пользователем. Возможно, аннулированный объект недоступен и для просмотра -это остается целиком на усмотрение пользовательского приложения. Система репликации может перевести объект обратно из аннулированного состояния в актуальное в случае смены маршрута (рис, 2,5). произвольных подмножеств БД.
Следует обратить внимание на то, что функция маршрутизации не возвращает готовый маршрут - она возвращает только список БД, в которые необходимо передать объект в актуальном состоянии. На функцию F налагается следующее ограничение: она должна быть детерминированной, то есть удовлетворять условию k=j = F(k)=F(j). Иными словами, список БД-получателей объекта должен быть вычислен только на основании данных этого объекта, и никаких других. Вычисляя F(k) для каждого реплицируемого объекта к система репликации определяет маршрут его передачи.
Ситуация, при которой на момент проведения обмена объект к должен быть скопирован в БД Bh ...,Вп и удален из БД В„.ц, ,..,Вп+т изображена на рис. 2.6.
Сервер репликации каждой БД BteB содержит сведения о местоположении серверов всех БД, с которыми он может производить обмен. Сведения о местоположении являются данными, достаточными для связи с сервером. В качестве примера местоположения можно привести IP-адрес, почтовый адрес, имя очереди гарантированной доставки сообщений. Таким образом, зная маршрут передачи каждого объекта можно установить соединение с целевыми серверами репликации для передачи им этих объектов.
Предлагаемая система репликации использует традиционную модель транзакций [25]. Транзакция Г,- представляет собой упорядоченную последовательность операций чтения и записи, выполняемых над локальными копиями объектов. Обозначим начало транзакции 7} как ВОТ(Г-), конец транзакции - EOTfTj), j-ю операцию чтения - Гц, j-ю операцию записи - wy. Если операция чтения или записи элемента данных X возвращает или устанавливает значение С, то будем записывать это как т-и](Х=С) и Wij(X=C) соответственно.
Для реализации предлагаемой системы репликации достаточно использовать плоские транзакции, то есть транзакции, происходящие всегда в рамках одной БД. СУБД предоставляет следующие гарантия выполнения транзакций: Изолированность. Одновременно происходящие транзакции не влияют друг на друга настолько, насколько это необходимо для сохранения непротиворечивости данных. Атомарность. Транзакция либо происходит целиком, либо все ее изменения отменяются. Невозможно частичное сохранение результатов транзакции. Долговечность. После завершения транзакции все произведенные изменения остаются зафиксированными в БД. Рассмотрим понятие изолированности транзакций. Транзакции 7/ и 7} называются конфликтующими, если они обращаются к одним и тем же данным, при этом по крайней мере одна из операций над этими данными является записью. Изоляция транзакций предоставляет определенные гарантии по чтению и записи данных конфликтующими транзакциями. Стандарт ANSI SQL определяет четыре уровня изоляции в терминах допустимости определенных результатов чтений и записи, называемых феноменами [4].
Определение маршрута без сохранения истории рассылки
Первый алгоритм является более гибким и надежным. Он корректно отрабатывает смену маршрута объекта, даже если произведенные изменения были выполнены при отключенной системе репликации. Сведения об аннулировании объекта при первом подходе гарантированно отсылаются только на те БД, куда ранее этот объект был передан в актуальном состоянии. Однако в случае репликации крупных БД недостаток этого подхода превышает его преимущества, так как он требует хранить все последние множества В,, для всех объектов. Таким образом, если в БД В( N объектов и все они были скопированы в К БД, то в В,-необходимо хранить N K вспомогательных записей о БД-получателях. При построении маршрутов СУБД должна будет постоянно производить поиск среди этих N K записей. Даже при наличии всех необходимых индексов эта операция выборки может существенно замедлить работу репликации [24].
Более подробно остановимся на алгоритме, реализующем подход к маршрутизации без сохранения истории рассылки. Данный алгоритм производит вычисление маршрута объекта в две стадии: 1. Стадия получения данных о предыдущем списке БД-получателей. На этой стадии производится вычисление Мо=Рф перед каждым изменением объекта j. Для каждого пакета сохраняется только самое первое вычисленное значение М0, поскольку именно оно соответствует списку БД-получателей предыдущего пакета. 2. Стадия вычисления нового списка БД-получателей. Эта стадия происходит сразу после переключения пакета и обязательно в рамках транзакции, переключившей пакет. При этом для каждого объекта j в пакете производится вычисление M}=F(j). Далее полагаем B, Mi, ВС=М0\М,. В качестве одного из вариантов алгоритма маршрутизации без сохранения истории рассылки возможно определение маршрута путем сравнения списка БД-получателей до изменения объекта и сразу после изменения, не дожидаясь переключения пакета. Однако это потребует от приложения сообщать серзеру момент завершения обновления объекта. С целью увеличения гибкости системы репликации здесь не устанавливается подобное ограничение, а потому рассмотрение этого подхода будет оставлено в стороне. Покажем, что алгоритм определения маршрута без сохранения истории гарантирует существование в произвольный момент времени актуальных локальных копий каждого объекта у только в БД множества F(j), вычисленной в момент последнего переключения пакета. Предположим наличие упорядоченности транзакций. Это означает, что все изменения транзакций можно упорядочить так, как будто транзакции выполнялись последовательно. Рассмотрим четыре транзакции 7}_j, 7}, Ti+j и Ti+2. Транзакции Т;.} и Ti+j изменяют некоторый объект j. Транзакции 7} и Тм выполняют переключение пакета и определяют маршруту. Между переключениями пакетов может произойти более одной транзакции, изменяющей объект, а может не произойти ни одной. Проанализируем эти случаи: Если произошло более одной транзакции, изменяющей объект, то произведем замену последовательности транзакций Т\...Т к одной, содержащей все их операции записи. При этом все дальнейшие рассуждения не изменятся. Данное действие допустимо, поскольку здесь рассматривается только чередование операций записи, а не границы выполняющих их транзакции. Случай, когда объект не был изменен в промежутке между переключениями пакета, не рассматривается, поскольку для такого объекта маршрут не вычисляется и копирование в БД не производится. Обозначим за hj(F(x)) запись в БД множества B,.=F(x), g;(F(x)) - чтение множества Д., записанного ранее операцией И,-. Если ранее операция записи не производилась, то g(F(x)) 0. История выполнения операций с объектом выглядит следующим образом (чтение транзакций Т и Ті+! не показано, поскольку оно не изменяет объекта и не влияет на его маршрут): Транзакция ТІ читает объект в последнем подтвержденном состоянии сп и определяет на его основании множество Д.. Таким образом, сервер репликации, выполняющий транзакцию Ті, скопирует j в актуальном состоянии только в БД Brj=F(cn) и аннулирует в БД Д —Д Ш,.,-. Аналогично, транзакция Т 2 скопирует актуальные копии в БД Brj+2=F(cirV!) и аннулирует их в БД Brj\Bri+2. Таким образом, после произвольной транзакции переключения пакета Т2,-объект j будет скопирован в актуальном состоянии во множество БД X2rBri2}\(...(B %4\(Bl.:2\(Bl.io\B,.2))\Bl.4)...). В силу того, что VA.B А\(В\А)=А получаем Х2І=ВҐІ2Ь что и требовалось доказать. Условие упорядоченности транзакций, использованное при доказательстве корректности работы алгоритма, является достаточно строгим, поскольку не многие современные СУБД поддерживают этот уровень изоляции. Проанализируем модификацию этого алгоритма, которая является менее требовательной к СУБД.
Система моделирования нагрузки
Данный алгоритм производит вычисление маршрута объекта в две стадии: 1. Стадия получения данных о предыдущем списке БД-получателей. На этой стадии производится вычисление Мо=Рф перед каждым изменением объекта j. Для каждого пакета сохраняется только самое первое вычисленное значение М0, поскольку именно оно соответствует списку БД-получателей предыдущего пакета. 2. Стадия вычисления нового списка БД-получателей. Эта стадия происходит сразу после переключения пакета и обязательно в рамках транзакции, переключившей пакет. При этом для каждого объекта j в пакете производится вычисление M}=F(j). Далее полагаем B, Mi, ВС=М0\М,.
В качестве одного из вариантов алгоритма маршрутизации без сохранения истории рассылки возможно определение маршрута путем сравнения списка БД-получателей до изменения объекта и сразу после изменения, не дожидаясь переключения пакета. Однако это потребует от приложения сообщать серзеру момент завершения обновления объекта. С целью увеличения гибкости системы репликации здесь не устанавливается подобное ограничение, а потому рассмотрение этого подхода будет оставлено в стороне.
Покажем, что алгоритм определения маршрута без сохранения истории гарантирует существование в произвольный момент времени актуальных локальных копий каждого объекта у только в БД множества F(j), вычисленной в момент последнего переключения пакета.
Предположим наличие упорядоченности транзакций. Это означает, что все изменения транзакций можно упорядочить так, как будто транзакции выполнялись последовательно. Рассмотрим четыре транзакции 7}_j, 7}, Ti+j и Ti+2. Транзакции Т;.} и Ti+j изменяют некоторый объект j. Транзакции 7} и Тм выполняют переключение пакета и определяют маршруту. Между переключениями пакетов может произойти более одной транзакции, изменяющей объект, а может не произойти ни одной. Проанализируем эти случаи: Если произошло более одной транзакции, изменяющей объект, то произведем замену последовательности транзакций Т\...Т к одной, содержащей все их операции записи. При этом все дальнейшие рассуждения не изменятся. Данное действие допустимо, поскольку здесь рассматривается только чередование операций записи, а не границы выполняющих их транзакции. Случай, когда объект не был изменен в промежутке между переключениями пакета, не рассматривается, поскольку для такого объекта маршрут не вычисляется и копирование в БД не производится.
Обозначим за hj(F(x)) запись в БД множества B,.=F(x), g;(F(x)) - чтение множества Д., записанного ранее операцией И,-. Если ранее операция записи не производилась, то g(F(x)) 0. История выполнения операций с объектом выглядит следующим образом (чтение транзакций Т и Ті+! не показано, поскольку оно не изменяет объекта и не влияет на его маршрут):
Транзакция ТІ читает объект в последнем подтвержденном состоянии сп и определяет на его основании множество Д.. Таким образом, сервер репликации, выполняющий транзакцию Ті, скопирует j в актуальном состоянии только в БД Brj=F(cn) и аннулирует в БД Д —Д Ш,.,-. Аналогично, транзакция Т 2 скопирует актуальные копии в БД Brj+2=F(cirV!) и аннулирует их в БД Brj\Bri+2.
Таким образом, после произвольной транзакции переключения пакета Т2,-объект j будет скопирован в актуальном состоянии во множество БД X2rBri2}\(...(B %4\(Bl.:2\(Bl.io\B,.2))\Bl.4)...). В силу того, что VA.B А\(В\А)=А получаем Х2І=ВҐІ2Ь что и требовалось доказать.
Условие упорядоченности транзакций, использованное при доказательстве корректности работы алгоритма, является достаточно строгим, поскольку не многие современные СУБД поддерживают этот уровень изоляции. Проанализируем модификацию этого алгоритма, которая является менее требовательной к СУБД.
Предположим, что СУБД поддерживает уровень изоляции, называемый «Зафиксированное чтение». Он позволяет транзакциям видеть только зафиксированные изменения других транзакций, но не гарантирует повторяемости чтения и отсутствия «фантомов».
Для реализации непротиворечивости чтения объектов введем понятие блокировки объекта. Блокировка объекта представляет собой блокировку исключительного доступа, ассоциируемую с каждым объектом. Перед началом чтения или модификации объекта транзакция 7} обязана получить блокировку этого объекта. Если блокировка выдана другой транзакции 7}, то Г, обязана ожидать освобождения блокировки. Блокировка автоматически освобождается при завершении транзакции.
Для реализации блокировки объекта может быть использован любой механизм, предоставляемый СУБД. Например, можно создать таблицу со списком идентификаторов объектов и построить по ней уникальный индекс [53]. Запрос блокировки объекта будет эквивалентен добавлению строки в эту таблицу, снятие блокировки - удалению. При условии установки и снятия блокировки в рамках одной транзакции ни одной записи в таблицу со списком идентификаторов добавлено не будет. Вся блокировка будет произведена на уровне индекса.
Еще одним вариантом реализации этого функционала является установка блокировки исключительного доступа на корневой кортеж объекта перед его изменением. Этот подход эффективнее предыдущего, поскольку, в соответствии с алгоритмом маршрутизации без сохранения истории, при изменении объекта корневой кортеж всегда обновляется первым. Большинство современных СУБД устанавливает блокировку исісаючительного доступа на кортеж при его обновлении [31]. Таким образом, при использовании данного подхода блокировка объектов реализуется достаточно просто.
Похожие диссертации на Разработка методов и средств динамической объектной репликации для синхронизации распределенных автоматизированных систем управления технологическими процессами
