Одновременный доступ

Особенностью РБД является многопользовательский распределенный доступ к данным [11].

Сложность ее для РБД состоит н том, что механизм управления в одном узле не может в общем случае знать в каждый момент времени о взаимодействии с другими узлами. К тому же в узлах могут находиться и копии данных других локальных БД.

Взаимодействие элементов в РБД по-прежнему осуществляется посредством транзакции, которая становится распределенной (рис. 12.4) и, воздействуя на целостную БД, после своего завершения оставляет БД целостной. В транзакции выделяют две команды: читать (R) и писать-обновлять (W).

Здесь по-прежнему справедливы те же понятия, что используются в централизованных БД: синхронизация, расписание, последовательно-подобное расписание (ППР), конфликт, рестарт. Напомним, что две транзакции вступают в конфликт, если они работают с одним и тем же общим элементом данных и по крайней мере одна из них реализуется операцией "писать" (запись).

В СУРБД в каждом узле ведется свое расписание. Вектор расписаний всех узлов назовем распределенным расписанием (РР).

Рис. 12.4. Распределенная модель транзакции:

Ti – субтранзакции; I – порождающие транзакции; 2 – передача данных

Последовательное РР (ПРР) – это РР, в котором каждая составляющая последовательна. Последовательно-подобное РР (ППРР) эквивалентно ПРР.

Существует несколько методов синхронизации.

1. Блокировка, которая может быть: а) с главным узлом; б) с заданием блокировки с помощью предикатов; в) с главной копией.

2. Голосование по большинству.

3. Метод предварительного анализа конфликтов.

Блокировка

1. Выделенный узел становится приоритетным и управляет остальными узлами как в централизованной БД. Известно, что блокировка в централизованной БД предусматривает монопольный режим для записи и коллективный режим для чтения. Эти режимы используются и в блокировке с главным узлом, который руководит процессом синхронизации.

Применяют двух- и трехфазную транзакции. В двухфазной транзакции выделяют:

• расширение (блокировку ресурса);

• сжатие (возвращение ресурса и снятие блокировки).

Только главный узел выдает запрос на блокировку, который проходит по всей сети.

Действия по изменению данных допускаются только над предварительно заблокированными данными, при этом сначала должно быть проведено обновление всех копий. В таком режиме возможны тупики, которые могут устраняться снятием "младших" (позже поступивших) транзакций.

2. Любой кортеж t отношения г со схемой R, для которого предикат P(t) = true, не может быть вставлен в R, удален или изменен другой транзакцией до снятия блокировки.

Двухфазная блокировка работает здесь следующим образом.

В фазе расширения (подготовки) транзакция должна затребовать предикат-блокировку. Узел-координатор ведет таблицу блокировок. Блокировка осуществляется, если она не вступает в конфликт с другими блокировками. В противном случае транзакция переводится в режим ожидания или ей разрешается осуществить перехват ресурса.

В фазе сжатия (разблокировки) осуществляется удаление строки из таблицы блокировок: первая же разблокировка говорит о начале фазы сжатия.

Установление факта конфликта здесь по-прежнему проблематично: показано, что в общем случае проблема рекурсивно неразрешима.

Процедура установления факта конфликта определена математически для предикатов вида [атрибут]F[константа], где в качестве F используются операции из множества (<, =, >, ¹).

Тупиковые ситуации могут быть устранены в трехфазной транзакции (блокировка, выполнение, разблокировка).

Блокировки с главным узлом и с использованием предикатов сводятся к централизации процедуры синхронизации. В этом случае производительность БД ограничена возможностями своеобразного центра.

В свете сказанного дальнейшее развитие синхронизации пошло в направлении децентрализации.

3. В данном случае для любого элемента данных одна копия является главной, которую и блокирует транзакция в каждом узле. Очевидно, что имеется избыточность информации и ни один узел не является главным (децентрализованное управление).

Голосование по большинству

В общем случае предполагается избыточность РБД: в любом узле есть копия любого элемента.

Транзакция выполняется лишь в одном узле:

• команда чтения в своем узле работает без блокировок и синхронизации;

• при записи имя элемента и его новое значение заносится в список обновления.

После завершения транзакции список разносится по всем узлам и узел голосует за этот список (рис. 12.5).

Рис. 12.5. Алгоритм голосования по большинству:

А – конфликт есть; Б – текущая транзакция получает большую временною метку, чем ожидающая транзакция; BP, ТР – временное метки последнего изменения и текущей транзакции

Если большинство – "за", транзакция принимается и обновление проводится во всех узлах.

Узел голосует "за", если:

1) элемент данных, прочитанных транзакцией, не был изменен после чтения;

2) транзакция Т не конфликтует с другой транзакцией Τ', которая ожидает решения (если данный узел проголосовал "за", но T' еше не была принята или отвергнута в целом) в данном узле.

В позиции 1 используются временны́е метки (метки времени). Метка присваивается транзакции и каждому элементу данных (последней транзакции, которая его обновила).

Когда узел принимает список обновления, он сравнивает временны́е метки и определяет выполнение условий I и 2. Если условие 1 не выполняется, узел отвергает транзакцию, которая рестартует (рис. 12.5). Если условие 1 удовлетворяется, а 2 – нет, то узел не может голосовать "за" эту транзакцию, которая ожидает решения, пока его не получит. При выполнении обоих условий узел голосует "за".

Поскольку разные узлы получают списки обновления в разном порядке, они и голосуют в разном порядке, что может приводить к тупикам. Чтобы их избежать, узел голосует "против", если условие 1 выполняется, а 2 – нет и транзакция получает бо́льшую временну́ю метку (метку времени), чем ожидающая транзакция.

Метод предварительного анализа конфликтов

До сих пор синхронизировались все конфликтующие операции записи и чтения. Однако не все конфликты могут уничтожить последовательно подобие.

Определяются конфликты, которые действительно требуют синхронизации. Для этого выделяют классы, которые определяются множествами записей и чтения транзакций. Транзакция относится к данному классу, если множества чтения и записи ее принадлежат этому классу. С любым классом связан модуль транзакции (МТ) – компонента СУРБД, которая последовательно выполняет транзакции из этого класса. Тогда могут конфликтовать только транзакции разных классов, и их нужно синхронизировать. Конфликт классов моделируется графом конфликтов (рис. 12.6), вершины которого соответствуют множествам чтения и записи класса, а ребра представляют собой конфликты. Транзакции, не входящие в цикл, всегда последовательно подобны и не требуют синхронизации.

Граф конфликтов создается и анализируется статически, когда определены БД и классы. Классы, не входящие в цикл, помечаются как МТ и им сообщается о ненужности синхронизации.

Оставшиеся МТ должны синхронизировать свои транзакции.

Рис. 12.6. Граф конфликтов